TSP - задача коммивояжёра
Traveling Salesman Problem: найти кратчайший маршрут через все точки с возвратом в исходную.
Классическая NP-трудная задача: N точек, известны расстояния между ними, требуется посетить каждую ровно один раз и вернуться в стартовую точку с минимальной длиной маршрута. В логистике возникает при планировании курьерских маршрутов, объезда торговых точек, инвентаризации складских ячеек. На практике решается эвристиками - nearest neighbor даёт быстрый старт, 2-opt/3-opt улучшают решение, для больших N применяют Lin-Kernighan или метаэвристики.
Задача коммивояжёра
Кликните по полю для добавления точки (до 30). Фиолетовая - стартовая. Nearest Neighbor строит маршрут жадно; 2-opt улучшает его перестановкой рёбер. Оптимум для больших N не гарантирован - задача NP-трудная.
Где мы это применяем
Услуги Advice LogisticsЧасто задаваемые вопросы
Почему TSP считается сложной задачей?+
Число возможных маршрутов растёт как N! - для 20 точек это уже 2.4·10¹⁸ вариантов. Точные алгоритмы (branch-and-bound, DP Held-Karp) работают до ~20-30 точек. Для больших N применяют эвристики: nearest neighbor, 2-opt/3-opt, Lin-Kernighan, генетические алгоритмы.
Как выбрать эвристику для TSP?+
До 50 точек хватает nearest neighbor + 2-opt (быстро, ошибка 5-15% от оптимума). Для 100-1000 точек - Lin-Kernighan или его открытая реализация LKH. Для 10 000+ - метаэвристики с географической декомпозицией.
Связанные термины
- Методы и модели · Транспорт · ЛогистикаVRP - задача маршрутизации транспорта
Vehicle Routing Problem: обобщение TSP на парк из нескольких машин, обслуживающих множество клиентов из одного склада.
- Методы и модели · Транспорт · ЛогистикаCVRP - VRP с ограничением по вместимости
Capacitated VRP: каждое ТС имеет предельную грузоподъёмность, суммарный заказ на маршруте не должен её превышать.