В статье вообще не сказано про VRP — вы это придумали уже позже, в комментариях. Потому я и задаю вопрос, что вообще непонятно, что же вы делаете. В статье сказано только про алгоритм Дейкстры.
Погодите, вы же в статье про реальный кейс говорите, а не теоретический. То есть вы считаете матрицу весов для всепланетарного дорожного графа даже при роутинге по одной улице города? И грузите всю матрицу в память? Абсурд какой-то… Хотя приведенное вами время вычислений вполне соответствует такому подходу…
Да, это несложно. Выкладывайте нужный кусок вашего маршрутного графа и набор точек и вашу реализацию и результат. Я лично берусь показать вариант с PgRouting и, если будет смысл, еще каким движком.
Это известный способ решения задачи VRP — кластеризация точек до или после (разделение и перестроение участков маршрута).
А вот чтобы не быть голословными — объясните нам, как это вы VRP решаете с помощью одного лишь алгоритма Дейкстры, как указано в статье? Если вы все еще не понимаете — с помощью алгоритма Дейкстры можно только подготовить матрицу расстояний.
1) Точность нам нужна равная точности дорожного графа и не более, так как это уже не имеет смысла.
2) Параметры pgr_TSP достаточно выбрать один раз, разделение пути на отрезки тоже не требует сложных параметров.
который на 10% хуже оптимума
Пока что видим, что ваш вариант из статьи — примерно в 1000 раз медленнее, точность неизвестна. Выложите примеры, для тех же 5000 точек, как в статье названо, посмотрим. Заодно расскажите, как вы с точностью в разы выше 10% умеете оценивать время в пути — а иначе проблема у вас будет уже в исходных весах маршрутного графа.
нам нужна честная большая матрица расстояний
Нужна минимально необходимая матрица, а все остальное — потери времени.
Гораздо лучше иметь сразу нормальный VRP-солвер
Как так — у вас же только что была уже VRPTW-задача и вы ставили минусы комментариям про VRP? VRP у вас уже была и вы уже передумали :)
Итого, вы рекламируете какой-то велосипед, который даже описать толком не можете, не говоря уж о точных характеристиках.
В статье сказано, что они используют комбинацию нескольких алгоритмов, и только в одном из шагов используют алгоритм Дейкстры:
During phase 1 we use plain Dijkstra to reach the core, while during phase 2, we use a speed-up technique in order to accelerate the search within the core. The full power of this core-based routing approach can be unleashed by using a goal-directed technique during phase 2. Our experimental study in Section 5 shows that when using ALT during phase 2, we end in a very robust technique that is superior to plain ALT.
И даже в описании статьи:
Abstract:
In "Combining Speed-up Techniques for Shortest-Path Computations", basic speed-up techniques for Dijkstra's algorithm have been combined.
A* алгоритм — как раз один из семейства "basic speed-up techniques for Dijkstra's algorithm".
Алгоритм Дейкстры это вполне конкретный алгоритм, и не надо его смешивать с производными алгоритмами — их очень много разных, но настолько универсальных, как алгоритм Дейкстры, больше не придумали.
1) Все вычисляется вместе на каждый запрос — ровно так, как здесь показано. Используется оптимизация выборки необходимого участка дорожной сети — скажем, 5000 ребер — так, чтобы гарантированно получить результат и не обрабатывать большую дорожную сеть на каждый запрос (заранее оцениваем, какой участок дорожной сети нужен для роутинга по городу/району/блоку домов — это один параметр для каждого города/района — размер буфера вокруг заданного набора адресов).
2) PgRouting не умеет работать с oneway, которые очень нужны — потому я написал враппер, который конвертирует матрицу с oneway ребрами в симметричную, необходимую для pgr_TSP. Этот момент упоминается где-то в документации по PgRouting — мол, любую матрицу можно привести к требуемой симметричной, думайте сами :)
3) Нет, в моих тестах для большого количества точек результат получался обычно заметно хуже — решение сваливается в первый попавшийся локальный оптимум. На практике все зависит от качества подготовленной маршрутной сети — нужно разделить двусторонние дороги из OSM на пару односторонних (oneway) для избежания виляния между сторонами дороги и т.п.
Эти маршруты (в частности, route 5) не являются отрезками решения оптимального TSP-маршрута.
Выше я описал два пути:
построить один оптимальный маршрут по всем точкам и разделить его на части (выделить кластеры точек), после чего назначить каждому коммивояжеру ближайший участок. Далее нужно по каждому набору точек еще раз оптимальный маршрут посчитать, определить начальную и конечную точку (они могут совпадать или не совпадать) — и эти маршруты могут частично не совпадать с исходным, в этом нет никакой проблемы, если их длина с достаточной точностью совпадает (как я уже писал, нужно контролировать точность решения).
точки можно кластеризовать заранее одним или несколькими способами (простейший способ функциями кластеризации PostGIS с евклидовой метрикой), и по этим кластерам построить отдельные маршруты.
Теперь, опять же как я писал выше, из полученных двумя путями наборов маршрутов выбирается оптимальный набор. На практике оба пути дают хороший результат, при использовании же обоих — отличный результат.
SELECT * FROM pgr_TSP(
$$
SELECT * FROM pgr_dijkstraSymmetrizeCostMatrix(
$_$
SELECT * FROM pgr_dijkstraValidateCostMatrix(
$__$
SELECT * FROM pgr_dijkstraCostMatrix(
$___$
SELECT id,source,target,cost,reverse_cost FROM ...
$___$,
(select array_agg(n.id)
from ... ),
directed := true
)
$__$
)
$_$
)
$$,
start_id := ...,
end_id := ...,
...
)
Тут у меня матрица очень навороченная для поддержки oneway и проч., по умолчанию нужны лишь pgr_TSP и pgr_dijkstraCostMatrix. Построение матрицы никак не связано с роутингом по ней — можно заменить функцию роутинга, например. Да, приведенная конструкция за несколько секунд находит маршрут через 5000 точек (и больше). Где используется — логистика по территории Германии. Зачем столько точек — предварительная оценка времени и расстояния для дневной доставки и назначение нужного количества машин, далее уже для каждого назначенного автомобиля (или байка, или пешехода — есть разные сценарии доставки) вычисляются свои оптимальные маршруты.
Алгоритм Дейкстры с уровнями иерархии никак не работает, нужно сделать некоторую минимизированную выборку необходимых ребер, чтобы большую маршрутную сеть не грузить целиком — вот для этой выборки и используются разные оптимизации. Вот алгоритм A* умеет выбирать наиболее быстро ведущие к цели ребра (детали реализации могут варьироваться в разных движках), так что ему можно скормить маршрутную сеть с дополнительным набором прямых соединений (предварительно посчитанных ребер) между городами и он пройдет, к примеру, по одному такому прямому соединению, соединяющему два города, а не по множеству отдельных сегментов между ними, а в пределах городов будет использовать уже множество исходных ребер для построения маршрута. Если ребра передаются полным списком (PgRouting), нужно оптимизировать этот передаваемый набор ребер, а вот в Spatialite Routing можно работать с целой маршрутной сетью — она оптимизируется предварительно и "на лету" изменения внести уже нельзя.
Также можно привести задачу VRP к TSP — разделить один построенный маршрут на несколько или кластеризовать исходные точки на несколько кластеров и построить по ним отдельные маршруты.
P.S. Приведенные в статье цифры некорректны более, чем полностью, построение маршрута(ов) выполняется намного быстрее.
Выше я уже объяснил, как из одного маршрута на 5000 точек получить набор маршрутов. И да, это работает и очень быстро в PgRouting — он бесплатный и с открытым кодом, что вам мешает взять и посмотреть самим?
Вы ищите оптимальный маршрут с 5000 остановок. Разумеется, надо найти их оптимальный порядок — а задача просто найти путь решается и вовсе за миллисекунды. В полученном (одном) итоговом маршруте у вас будет именно 5000 остановок. И именно эта задача решается намного быстрее и проще, чем вы делаете.
Да, я читал. Полный перебор всех вариантов это интересно, но практического смысла не имеет. Давайте не будем обсуждать "сферического коня в вакууме". Обратите внимание, что есть определенная точность задания веса каждого ребра и плюс к тому дополнительные факторы — к примеру, между остановкой грузовика на обочине и посещением водителем (экспедитором) крыльца ближайшего дома пройдет несколько минут (запаковаться, вылезти из кабины, открыть кузов, достать посылку, закрыть кузов, дойти до двери дома,...). Так что точности решения задачи порядка 5-10% вполне достаточно на практике, а для этого можно выбрать такие параметры, что PgRouting построит маршрут через заданные 50000 точек за минуты.
Тоже есть Open Source движки специально для этой задачи, от гугла, к примеру. Посмотрите их документацию, познавательно — поймете, как сделать так же с помощью PgRouting или других движков. Задачу можно решать, построив единый маршрут через все точки и разделив его на нужное число частей, а потом назначив каждой части ближайшего коммивояжера. Можно заранее кластеризовать точки маршрута на нужное число кластеров (по кластеру на коммивояжера, в простейшем случае) и построить маршрут в каждом кластере отдельно. И да, лучший вариант — использовать оба метода и выбрать оптимальный результат.
PgRouting за секунды находит маршрут (то есть назначает порядок прохождения) через 5000 точек. Посмотрите же сами, и документация у них отличная.
На графах не бывает пробок :) При назначенных весах (время прохождения ребра) нет никаких проблем работать с пробками.
Еще раз — представленное решение настолько плохо, что любой Open Source роутинг типа PgRouting или Spatialite Routing будет на порядки быстрее (100-1000 раз, навскидку). Иерархический подход дело хорошее, но это оптимизация, а у вас проблема в подходе. Никаких "25 млн полноценных маршрутов", как вы пишите в предыдущем комментарии, у вас нет — вы ищите 5000 сегментов между 5000 точек одного маршрута. Вот даже "тупой" итеративный алгоритм разбиения на два работает лучше вашего: построить один путь между двумя наиболее удаленными точками (для начала евклидова дистанция подойдет) методом Дейкстры, найти наиболее удаленную от маршрута точку и добавить ее в маршрут как промежуточную (посчитав 2 пути от нее — к первой и последней) и т.п. Сколько здесь итераций и путей, уже понятно? Попробуйте, удивитесь, насколько это будет проще и быстрее.
Да уж — алгоритм поиска оптимального пути к единственной точке (алгоритм Дейкстры) вообще не имеет смысла использовать для задачи коммивояжера, когда нам нужен кольцевой маршрут по всем точкам. Более того, задавая требуемую точность нахождения пути между двумя точками алгоритмом Дейкстры с эвристиками, абсолютно не очевидно, как посчитать точность кольцевого маршрута из найденных сегментов между множеством точек — то есть оценить адекватность построенного маршрута мы не сможем. Алгоритмы типа отжига оперируют ошибкой для всего пути, что разумно. Про вычислительную сложность не стоит и говорить, а еще на практике необходимо оптимизировать количество пересечений улиц (да, не стоит в шахматном порядке метаться между домами на разных сторонах улицы, а надо проехать сначала одну сторону улицы, потом развернуться и проехать другую сторону) и т.п. — что с посегментным поиском пути не реализуемо в принципе.
Если раньше на один большой запрос нам требовалось 50 ядер на полчаса, то теперь — 13 ядер на 2 минуты. Это примерно 200 000 маршрутов в секунду на ядро.
Какая-то подмена понятий. Маршрут коммивояжера для задачи коммивояжера — это маршрут со всеми остановками. Откуда взялись "200 000 маршрутов в секунду на ядро"?!!! Вероятно, имеются в виду ребра графа, но это паршивый результат, так что автор статьи подменил термины...
P.S. Ну и вообще результаты выглядят печально — PostgreSQL/PgRouting на маршрут с 5000 остановок тратит единицы секунд вычислений на одном ядре (карта OSM по территории Европы).
В статье вообще не сказано про VRP — вы это придумали уже позже, в комментариях. Потому я и задаю вопрос, что вообще непонятно, что же вы делаете. В статье сказано только про алгоритм Дейкстры.
Погодите, вы же в статье про реальный кейс говорите, а не теоретический. То есть вы считаете матрицу весов для всепланетарного дорожного графа даже при роутинге по одной улице города? И грузите всю матрицу в память? Абсурд какой-то… Хотя приведенное вами время вычислений вполне соответствует такому подходу…
Да, это несложно. Выкладывайте нужный кусок вашего маршрутного графа и набор точек и вашу реализацию и результат. Я лично берусь показать вариант с PgRouting и, если будет смысл, еще каким движком.
Это известный способ решения задачи VRP — кластеризация точек до или после (разделение и перестроение участков маршрута).
А вот чтобы не быть голословными — объясните нам, как это вы VRP решаете с помощью одного лишь алгоритма Дейкстры, как указано в статье? Если вы все еще не понимаете — с помощью алгоритма Дейкстры можно только подготовить матрицу расстояний.
1) Точность нам нужна равная точности дорожного графа и не более, так как это уже не имеет смысла.
2) Параметры pgr_TSP достаточно выбрать один раз, разделение пути на отрезки тоже не требует сложных параметров.
Пока что видим, что ваш вариант из статьи — примерно в 1000 раз медленнее, точность неизвестна. Выложите примеры, для тех же 5000 точек, как в статье названо, посмотрим. Заодно расскажите, как вы с точностью в разы выше 10% умеете оценивать время в пути — а иначе проблема у вас будет уже в исходных весах маршрутного графа.
Нужна минимально необходимая матрица, а все остальное — потери времени.
Как так — у вас же только что была уже VRPTW-задача и вы ставили минусы комментариям про VRP? VRP у вас уже была и вы уже передумали :)
Итого, вы рекламируете какой-то велосипед, который даже описать толком не можете, не говоря уж о точных характеристиках.
В статье сказано, что они используют комбинацию нескольких алгоритмов, и только в одном из шагов используют алгоритм Дейкстры:
И даже в описании статьи:
A* алгоритм — как раз один из семейства "basic speed-up techniques for Dijkstra's algorithm".
Алгоритм Дейкстры это вполне конкретный алгоритм, и не надо его смешивать с производными алгоритмами — их очень много разных, но настолько универсальных, как алгоритм Дейкстры, больше не придумали.
1) Все вычисляется вместе на каждый запрос — ровно так, как здесь показано. Используется оптимизация выборки необходимого участка дорожной сети — скажем, 5000 ребер — так, чтобы гарантированно получить результат и не обрабатывать большую дорожную сеть на каждый запрос (заранее оцениваем, какой участок дорожной сети нужен для роутинга по городу/району/блоку домов — это один параметр для каждого города/района — размер буфера вокруг заданного набора адресов).
2) PgRouting не умеет работать с oneway, которые очень нужны — потому я написал враппер, который конвертирует матрицу с oneway ребрами в симметричную, необходимую для pgr_TSP. Этот момент упоминается где-то в документации по PgRouting — мол, любую матрицу можно привести к требуемой симметричной, думайте сами :)
3) Нет, в моих тестах для большого количества точек результат получался обычно заметно хуже — решение сваливается в первый попавшийся локальный оптимум. На практике все зависит от качества подготовленной маршрутной сети — нужно разделить двусторонние дороги из OSM на пару односторонних (oneway) для избежания виляния между сторонами дороги и т.п.
Выше я описал два пути:
Теперь, опять же как я писал выше, из полученных двумя путями наборов маршрутов выбирается оптимальный набор. На практике оба пути дают хороший результат, при использовании же обоих — отличный результат.
Пример кода из рабочего проекта:
Тут у меня матрица очень навороченная для поддержки oneway и проч., по умолчанию нужны лишь pgr_TSP и pgr_dijkstraCostMatrix. Построение матрицы никак не связано с роутингом по ней — можно заменить функцию роутинга, например. Да, приведенная конструкция за несколько секунд находит маршрут через 5000 точек (и больше). Где используется — логистика по территории Германии. Зачем столько точек — предварительная оценка времени и расстояния для дневной доставки и назначение нужного количества машин, далее уже для каждого назначенного автомобиля (или байка, или пешехода — есть разные сценарии доставки) вычисляются свои оптимальные маршруты.
Знаете, вы сами себе противоречите раз за разом. В статье сказано про вашу задачу (явная задача коммивояжера, TSP):
Далее, в комменте пишите
А теперь уже
Уж будьте любезны с темой статьи и обсуждения определиться.
Алгоритм Дейкстры с уровнями иерархии никак не работает, нужно сделать некоторую минимизированную выборку необходимых ребер, чтобы большую маршрутную сеть не грузить целиком — вот для этой выборки и используются разные оптимизации. Вот алгоритм A* умеет выбирать наиболее быстро ведущие к цели ребра (детали реализации могут варьироваться в разных движках), так что ему можно скормить маршрутную сеть с дополнительным набором прямых соединений (предварительно посчитанных ребер) между городами и он пройдет, к примеру, по одному такому прямому соединению, соединяющему два города, а не по множеству отдельных сегментов между ними, а в пределах городов будет использовать уже множество исходных ребер для построения маршрута. Если ребра передаются полным списком (PgRouting), нужно оптимизировать этот передаваемый набор ребер, а вот в Spatialite Routing можно работать с целой маршрутной сетью — она оптимизируется предварительно и "на лету" изменения внести уже нельзя.
Приведу набор ссылок на Open Source движки для тех, кому интересны задачи роутинга:
OR-Tools: построить набор маршрутов по заданным точкам:
https://developers.google.com/optimization/routing/vrp
OR-Tools: построить один маршрут по заданным точкам:
https://developers.google.com/optimization/routing/tsp
PgRouting: построить один маршрут по заданным точкам:
http://docs.pgrouting.org/latest/en/pgr_TSP.html
Также можно привести задачу VRP к TSP — разделить один построенный маршрут на несколько или кластеризовать исходные точки на несколько кластеров и построить по ним отдельные маршруты.
P.S. Приведенные в статье цифры некорректны более, чем полностью, построение маршрута(ов) выполняется намного быстрее.
Выше я уже объяснил, как из одного маршрута на 5000 точек получить набор маршрутов. И да, это работает и очень быстро в PgRouting — он бесплатный и с открытым кодом, что вам мешает взять и посмотреть самим?
Вы ищите оптимальный маршрут с 5000 остановок. Разумеется, надо найти их оптимальный порядок — а задача просто найти путь решается и вовсе за миллисекунды. В полученном (одном) итоговом маршруте у вас будет именно 5000 остановок. И именно эта задача решается намного быстрее и проще, чем вы делаете.
Да, я читал. Полный перебор всех вариантов это интересно, но практического смысла не имеет. Давайте не будем обсуждать "сферического коня в вакууме". Обратите внимание, что есть определенная точность задания веса каждого ребра и плюс к тому дополнительные факторы — к примеру, между остановкой грузовика на обочине и посещением водителем (экспедитором) крыльца ближайшего дома пройдет несколько минут (запаковаться, вылезти из кабины, открыть кузов, достать посылку, закрыть кузов, дойти до двери дома,...). Так что точности решения задачи порядка 5-10% вполне достаточно на практике, а для этого можно выбрать такие параметры, что PgRouting построит маршрут через заданные 50000 точек за минуты.
Тоже есть Open Source движки специально для этой задачи, от гугла, к примеру. Посмотрите их документацию, познавательно — поймете, как сделать так же с помощью PgRouting или других движков. Задачу можно решать, построив единый маршрут через все точки и разделив его на нужное число частей, а потом назначив каждой части ближайшего коммивояжера. Можно заранее кластеризовать точки маршрута на нужное число кластеров (по кластеру на коммивояжера, в простейшем случае) и построить маршрут в каждом кластере отдельно. И да, лучший вариант — использовать оба метода и выбрать оптимальный результат.
PgRouting за секунды находит маршрут (то есть назначает порядок прохождения) через 5000 точек. Посмотрите же сами, и документация у них отличная.
На графах не бывает пробок :) При назначенных весах (время прохождения ребра) нет никаких проблем работать с пробками.
Еще раз — представленное решение настолько плохо, что любой Open Source роутинг типа PgRouting или Spatialite Routing будет на порядки быстрее (100-1000 раз, навскидку). Иерархический подход дело хорошее, но это оптимизация, а у вас проблема в подходе. Никаких "25 млн полноценных маршрутов", как вы пишите в предыдущем комментарии, у вас нет — вы ищите 5000 сегментов между 5000 точек одного маршрута. Вот даже "тупой" итеративный алгоритм разбиения на два работает лучше вашего: построить один путь между двумя наиболее удаленными точками (для начала евклидова дистанция подойдет) методом Дейкстры, найти наиболее удаленную от маршрута точку и добавить ее в маршрут как промежуточную (посчитав 2 пути от нее — к первой и последней) и т.п. Сколько здесь итераций и путей, уже понятно? Попробуйте, удивитесь, насколько это будет проще и быстрее.
Как я понял из статьи, вам нужно решить задачу коммивояжера — построить один маршрут с 5000 остановок. Вы же сами в начале статьи пишите:
Терминологию см. в вики хотя бы, задача древняя и терминология давно устоялась: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0
Да уж — алгоритм поиска оптимального пути к единственной точке (алгоритм Дейкстры) вообще не имеет смысла использовать для задачи коммивояжера, когда нам нужен кольцевой маршрут по всем точкам. Более того, задавая требуемую точность нахождения пути между двумя точками алгоритмом Дейкстры с эвристиками, абсолютно не очевидно, как посчитать точность кольцевого маршрута из найденных сегментов между множеством точек — то есть оценить адекватность построенного маршрута мы не сможем. Алгоритмы типа отжига оперируют ошибкой для всего пути, что разумно. Про вычислительную сложность не стоит и говорить, а еще на практике необходимо оптимизировать количество пересечений улиц (да, не стоит в шахматном порядке метаться между домами на разных сторонах улицы, а надо проехать сначала одну сторону улицы, потом развернуться и проехать другую сторону) и т.п. — что с посегментным поиском пути не реализуемо в принципе.
Какая-то подмена понятий. Маршрут коммивояжера для задачи коммивояжера — это маршрут со всеми остановками. Откуда взялись "200 000 маршрутов в секунду на ядро"?!!! Вероятно, имеются в виду ребра графа, но это паршивый результат, так что автор статьи подменил термины...
P.S. Ну и вообще результаты выглядят печально — PostgreSQL/PgRouting на маршрут с 5000 остановок тратит единицы секунд вычислений на одном ядре (карта OSM по территории Европы).