Шутки в сторону, у меня была проблема с маршрутизацией, которая является почти проблемой коммивояжера (TSP):
- начальная точка определена
- конечная точка совпадает с начальной
- каждый узел должен быть посещен
- общая стоимость должна быть сведена к минимуму
Два года назад я думал, что TSP будет идеальным совпадением, поэтому я проверил некоторые примеры данных tsp_solveи Concorde. К счастью, было быстро очевидно, что кратчайший путь TSP не является реальным кратчайшим путем , поскольку проблема облегчается нереалистичным требованием, чтобы узлы посещались ровно один раз . Эта картина представляет собой одностадийную ручную попытку оптимизации вычисленного решения, и она уже сохраняет расстояние до самого длинного используемого ребра.
Проблема вновь возникла, так как я пытаюсь найти оптимальные маршруты к подмножествам сайтов картирования / мониторинга. Данные о местоположении и дорожной сети довольно точны и точны, поэтому подобное упражнение имеет смысл.
Я посмотрел на обобщения TSP, но не нашел подходящий алгоритм. Минимальные связующие деревья не учитывают возврат из веток (первое решение здесь стоит на 3 больше). Из того, что я понимаю, проблема кратчайшего пути в конечном итоге касается только двух узлов, а те, которые находятся вне оптимального пути, будут исключены. Особый случай проблемы маршрутизации транспортного средства, кажется, подходит лучше всего, хотя я не знаю, рассматривает ли он не прямые пути.
Мой вопрос: есть ли конкретное имя, определение для такого рода проблемы (семьи)? Какой алгоритм и инструмент вы бы использовали для его решения?
Я уверен, что это будет тяжело в вычислительном отношении, но меня интересуют как общие (бесконечные ресурсы), так и практические ответы.
источник
Ответы:
Это TSP . Вы просто не определили действительную метрику расстояния, потому что она не удовлетворяет неравенству треугольника: если существует маршрут от А до С через В, который короче указанного расстояния от А до С, то указанное расстояние от А до С это просто неправильно. Решение состоит в том, чтобы обновить матрицу расстояний, установив длину от A до C равной кратчайшей длине всех маршрутов от A до C.
источник