Постановка задачи о коммивояжере

Классическая постановка задачи о коммивояжере выглядит следующим образом:

Имеется N городов, которые должен обойти коммивояжер по кратчайшему пути. При этом на его маршрут накладывается два ограничения:

• · маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
• · в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом, не побывав ни в одном городе дважды.

Целью решения является нахождения самого короткого маршрута, удовлетворяющего всем условиям.

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

Безусловно, реальная жизнь накладывает различные ограничения на поиск оптимального варианта, но это не означает, что потребность в эффективном решении Задачи коммивояжера за реальное время не будет расти в будущем. Рассмотрим несколько практических приложений задачи.

• 1. Доставка продуктов в магазины с оптового склада производителя (в этом случае может быть более уместна постановка транспортной задачи — доставка в несколько магазинов с нескольских складов).
• 2. Доставка бутилированной воды
• 3. Мониторинг объектов (базовые станции сотовых операторов, нефтянные вышки)
• 4. Пополнение банкоматов наличными деньгами
• 5. Сбор сотрудников для доставки вахтовым методом
• 6. Расклейка афиш
• 7. И т.д.