Описание Области
Задача коммивояжера (англ. 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
кратко