ПочатиПочніть безкоштовно

Задача комівояжера (TSP)

Задача комівояжера (TSP) — відома задача з багатьма застосуваннями в логістиці. У TSP продавцеві задано список міст і відстані між кожною парою. Потрібно знайти найкоротший маршрут, що стартує з початкового міста, проходить через усі інші та повертається назад. Обчислювально це складна задача, але Міллер–Такер–Землін (MTZ) показали, що її можна розв'язати за допомогою цілочисельного лінійного програмування. У цій вправі ви визначите цільову функцію та частину обмежень для TSP на невеликому наборі даних із 15 міст (див. зображення нижче). Ваша мета — попрактикуватися у використанні LpVariable.dicts разом зі списковими включеннями.

Photo of Cities

Три змінні Python n, cities і dist вже створені для вас \(^{1}\). Змінна n — це кількість міст, cities — список міст із номерами, а dist — це датафрейм 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=____)
Редагувати та запускати код