Задача коммивояжёра (TSP)
Задача коммивояжёра (TSP) — широко известная задача с практическими приложениями в логистике. Коммивояжёру дан список городов и расстояния между каждой парой. Его цель — найти кратчайший маршрут, проходящий через все города ровно по одному разу и возвращающийся в начальный город. Задача вычислительно сложна, однако Миллер, Такер и Землин (MTZ) показали, что она решается с помощью целочисленного линейного программирования. В этом упражнении вы определите целевую функцию и некоторые ограничения для TSP на небольшом наборе данных из 15 городов (см. изображение ниже). Ваша задача — попрактиковаться в использовании LpVariable.dicts совместно со списковыми включениями.
Для вас уже созданы три переменные Python: n, cities и dist \(^{1}\). Переменная n — это количество городов, cities — список городов с номерами, а dist — DataFrame pandas с попарными расстояниями между городами. Вы можете изучить их в консоли. Кроме того, модель уже инициализирована.
\(^{1}\) Набор данных взят из: Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
Это упражнение является частью курса
Аналитика цепочек поставок на Python
Интерактивное практическое упражнение
Попробуйте выполнить это упражнение, дополнив этот пример кода.
# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____],
cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____],
lowBound=0, upBound=(n-1), cat=____)