Есть ли интеллектуальные коммивояжеры?

12

Шутки в сторону, у меня была проблема с маршрутизацией, которая является почти проблемой коммивояжера (TSP):

  • начальная точка определена
  • конечная точка совпадает с начальной
  • каждый узел должен быть посещен
  • общая стоимость должна быть сведена к минимуму

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

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

Я посмотрел на обобщения TSP, но не нашел подходящий алгоритм. Минимальные связующие деревья не учитывают возврат из веток (первое решение здесь стоит на 3 больше). Из того, что я понимаю, проблема кратчайшего пути в конечном итоге касается только двух узлов, а те, которые находятся вне оптимального пути, будут исключены. Особый случай проблемы маршрутизации транспортного средства, кажется, подходит лучше всего, хотя я не знаю, рассматривает ли он не прямые пути.

Мой вопрос: есть ли конкретное имя, определение для такого рода проблемы (семьи)? Какой алгоритм и инструмент вы бы использовали для его решения?

Я уверен, что это будет тяжело в вычислительном отношении, но меня интересуют как общие (бесконечные ресурсы), так и практические ответы.

lynxlynxlynx
источник
Вы изучали теорию графов?
nagytech
Примерно так же, как ссылки на Википедию выше и несколько ссылок глубже. В университете мы сделали только тривиальную LP и теорию принятия решений.
lynxlynxlynx

Ответы:

4

Это TSP . Вы просто не определили действительную метрику расстояния, потому что она не удовлетворяет неравенству треугольника: если существует маршрут от А до С через В, который короче указанного расстояния от А до С, то указанное расстояние от А до С это просто неправильно. Решение состоит в том, чтобы обновить матрицу расстояний, установив длину от A до C равной кратчайшей длине всех маршрутов от A до C.

Whuber
источник
Отлично, это довольно просто. Для небольших графиков, вероятно, даже не стоит предварительно рассчитывать новую матрицу расстояний, а вместо этого делать это на лету.
lynxlynxlynx