Планируем путешествие — задача коммивояжера (TSP) для построения оптимального маршрута

С вами Алексей Ложкинс, эксперт по анализу данных и машинному обучению в ПГК Диджитал. Мы разрабатываем цифровые продукты для логистической отрасли, в первую очередь, для ж/д перевозок.

В кулуарах московского офиса ПГК мы обсуждаем и нерабочие темы. Топовую строчку в темах неформального общения занимает отпуск. Мы решили рассмотреть задачу планирования отпуска, как задачу оптимизации маршрута по выбранным достопримечательностям. Для этого воспользовались классической постановкой задачи коммивояжера.

Моделирование маршрута в виде задачи коммивояжера позволит построить маршрут по всем запланированным локациям без повторений с заданным критерием качества (время, стоимость). Рассмотрим несколько подходов к решению оптимизационной задачи (TSP) с использованием пакета ORTools.

Читать далее