Salesman_TRA_DP9. Коммивояжер, поиск гамильтонового цикла. Минимум стоимости объезда всех пунктов с возвратом в исходный. Планирование поставок, логистика, ритейл. 9 пунктов.

Описание Области

Задача коммивояжера (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.

https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0

Дано:

  Населенные пункты, которые требуется обойти.

  Затраты на дорогу от одного пункта к другому.

  Исходное положение коммивояжера.

Требуется:

  Обойти все деревни

  Побывать в каждой только один раз

  Вернуться домой, в начало пути

  Минимизировать затраты на дорогу

Найти:

Маршрут минимальной стоимости, для посещения всех пунктов не более одного раза с возвратом в исходный.

Особенности Объекта

Установка соответствует коммивояжеру, посещающему населенные пункты.

Операция соответствует посещению населенного пункта.

Число интервалов соответствует числу населенных пунктов, которые требуется посетить.

Начальный вариант соответствует пункту отправления коммивояжера.

Критерий – минимум суммарных затрат от посещения всех населенных пунктов, который задается критерием «Переключение». Потери от переходов операций соответствуют затратам на дорогу от одного населенного пункта к другому.

Схема Объекта

Рисунок. Потоковая схема объекта «с именами»

Особенности Решения S.Salesman_TRA_DP9.

Особенности Задачи

подробнее…

Задача коммивояжера для 9 деревень. Коммивояжер начинает путешествие с деревни «Марфино» и завершает в ней же.

Расстояние между деревнями задано в матрице переналадок:

Рисунок. Матрица переналадок операций.

кратко

Исходные данные

подробнее…

Выбор маршрута путешествия коммивояжера:

Рисунок. Фрагмент формы – стадия, установка, операция, поток

Примечание. Видна заданная начальная и конечная точка путешествия

кратко

Результаты решения

подробнее…

Фрагменты расписания

Рисунок. Фрагмент расписания выполнения операций

Объяснения решения

Рисунок. Фрагмент трассы объяснений хода рассуждений Решателя DP

кратко