1. Learn
    2. /
  2. Курси
    3. /
  3. Аналітика ланцюга постачань у Python
Connected

Вправа

Задача комівояжера (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,

Інструкції 1/3

undefined XP
    1
    2
    3
  • Використайте LpVariable.dicts, щоб створити словник x із бінарними змінними для кожної пари міст, а також створити словник u з цілочисельною змінною LpVariable для кожного міста.