Вариация проблемы коммивояжера - выберите хороший маршрут из множества узлов на основе ограничений - PullRequest
Новая
       14

Вариация проблемы коммивояжера - выберите хороший маршрут из множества узлов на основе ограничений

1 голос
/ 18 августа 2010

Версия TLDR: Наиболее важная проблема заключается в том, что в задаче TSP вместо нахождения кратчайшего гамильтонова цикла существуют хорошие способы поиска наилучшего пути (я полагаю, тот, который посещает большинство узлов).) длиной не более X с фиксированной начальной точкой.

Полная версия:

Меня интересуют некоторые идеи дляПроблема, которая включает в себя TSP.Во-первых, пример реальной проблемы TSP состоит в том, что у вас есть N географических мест для посещения, и вам нужны маршруты проезда для оптимального маршрута (или почти оптимального) для посещения всех, либо туда и обратно, либо от А до Я. Есть хороший JSреализация для этого в http://www.gebweb.net/optimap/ и решатель JS TSP доступны в http://code.google.com/p/google-maps-tsp-solver/.

Теперь рассмотрим, что у вас есть N = 100 - 1000+ местоположений.На этом этапе вы не можете рассчитать маршрут с любым разумным количеством времени / ресурсов, но даже если бы это было возможно, это не очень полезно для большинства реальных сценариев.Допустим, вы выбрали фиксированную начальную точку и, исходя из этого, из этих 1000+ местоположений вы хотите сгенерировать оптимальный подчиненный маршрут , который вписывается в (относительно небольшое) максимальное ограничение (например,маршрут, который может быть пройден за 1 день или 1 неделю).Как это можно решить в реальном времени?Мои мысли смягчаются:

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

  2. Найтиоптимальный маршрут с учетом местоположений, выбранных на шаге 1. Но вместо маршрута, который посещает все точки из этого набора, мне нужен лучший маршрут, который удовлетворяет максимальное ограничение , поэтому он не должен посещать все точки (это может посетить все, но это был бы крайний случай).Я особенно не уверен в том, как было бы лучше эффективно решить этот вопрос?

Любые ссылки или идеи приветствуются, особенно для пункта 2.

Отказ от ответственности : Конечно, суть проблемы не зависит от языка, я использую JS / Google Maps в качестве примера реального приложения.

1 Ответ

1 голос
/ 19 августа 2010

ОК, вот мой набросок решения в псевдокоде.Вам необходимо знать о приоритетных очередях 

Define a data structure Route {
  the route taken so far, 
  and can give the score (nodes visited)
  the distance traveled
  and the remaining nodes allowed
  the current location.
}

Define a Priority Queue of Routes which sorts on distance traveled.
Define a SortedSet of Routes which sorts on score called solutions.

Add a Route of Length 0, at the depot to the priority queue.
Loop until the head of the priority queue is greater than MAX
   Route r = take the head of the priority queue.
   for each potential remaining node n in r, 
     (in increasing order of distance from the current location)
      child = a new route of r with n appended
      if child distance < max, append to priority queue, otherwise break
   if no children were appended add r to solutions

. Это эффективно делает широкий поиск в пространстве решения в разумно эффективном объеме памяти.Более того, если он слишком медленный, то при зацикливании всех дочерних элементов вы можете ускорить алгоритм, выбрав только N ближайших соседей, где N настраивается.Вы можете пропустить оптимальное решение, но оно должно быть разумным в большинстве случаев.

...