Comments 49
Да уж — алгоритм поиска оптимального пути к единственной точке (алгоритм Дейкстры) вообще не имеет смысла использовать для задачи коммивояжера, когда нам нужен кольцевой маршрут по всем точкам. Более того, задавая требуемую точность нахождения пути между двумя точками алгоритмом Дейкстры с эвристиками, абсолютно не очевидно, как посчитать точность кольцевого маршрута из найденных сегментов между множеством точек — то есть оценить адекватность построенного маршрута мы не сможем. Алгоритмы типа отжига оперируют ошибкой для всего пути, что разумно. Про вычислительную сложность не стоит и говорить, а еще на практике необходимо оптимизировать количество пересечений улиц (да, не стоит в шахматном порядке метаться между домами на разных сторонах улицы, а надо проехать сначала одну сторону улицы, потом развернуться и проехать другую сторону) и т.п. — что с посегментным поиском пути не реализуемо в принципе.
Простой алгоритм Дейкстры правда неоптимален, поэтому мы используем иерархический вариант, которому помогает естественная декомпозицая дорожного графа на города, округа и районы. Нам поэтому не приходится обсчитывать честную волну по огромному графу. Большая часть расстояний (вроде расстояния Москва — Санкт-Петербург) посчитаны заранее и не вычисляются в рантайме.
На графах не бывает пробок :) При назначенных весах (время прохождения ребра) нет никаких проблем работать с пробками.
Еще раз — представленное решение настолько плохо, что любой Open Source роутинг типа PgRouting или Spatialite Routing будет на порядки быстрее (100-1000 раз, навскидку). Иерархический подход дело хорошее, но это оптимизация, а у вас проблема в подходе. Никаких "25 млн полноценных маршрутов", как вы пишите в предыдущем комментарии, у вас нет — вы ищите 5000 сегментов между 5000 точек одного маршрута. Вот даже "тупой" итеративный алгоритм разбиения на два работает лучше вашего: построить один путь между двумя наиболее удаленными точками (для начала евклидова дистанция подойдет) методом Дейкстры, найти наиболее удаленную от маршрута точку и добавить ее в маршрут как промежуточную (посчитав 2 пути от нее — к первой и последней) и т.п. Сколько здесь итераций и путей, уже понятно? Попробуйте, удивитесь, насколько это будет проще и быстрее.
Это те самые веса, которые зависят от времени? От того времени, которое затратили на предыдущую часть маршрута? Ну да, ну да.
>любой Open Source роутинг типа PgRouting или Spatialite Routing будет на порядки быстрее
А можно тут пруф? Это же не сложно, очевидно. Причем насколько я понимаю, не для одиночного маршрута, потому что PgRouting умеет вроде решать задачу TSP?
Да, это несложно. Выкладывайте нужный кусок вашего маршрутного графа и набор точек и вашу реализацию и результат. Я лично берусь показать вариант с PgRouting и, если будет смысл, еще каким движком.
Просто вы очень смело утверждаете про два-три порядка, и по вашим постам видно, что недоверять вам нет никакого резона, но циферок-то никаких нет, сравнить мы как читатели со стороны ничего не можем. Было бы неплохо какие-то реальные измерения. Хотя я понимаю, что это может быть трудозатратно.
Если раньше на один большой запрос нам требовалось 50 ядер на полчаса, то теперь — 13 ядер на 2 минуты. Это примерно 200 000 маршрутов в секунду на ядро.
Какая-то подмена понятий. Маршрут коммивояжера для задачи коммивояжера — это маршрут со всеми остановками. Откуда взялись "200 000 маршрутов в секунду на ядро"?!!! Вероятно, имеются в виду ребра графа, но это паршивый результат, так что автор статьи подменил термины...
P.S. Ну и вообще результаты выглядят печально — PostgreSQL/PgRouting на маршрут с 5000 остановок тратит единицы секунд вычислений на одном ядре (карта OSM по территории Европы).
Пример с 5000 остановок несколько не про то, как мне кажется. Там считается 5000 маршрутов, а не 25 млн.
Как я понял из статьи, вам нужно решить задачу коммивояжера — построить один маршрут с 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
После того, как матрицу посчитали, можно решать уже саму задачу нахождения оптимального пути. Задача коммивояжёра на 5000 точек проще, чем эта же задача с многими коммивояжёрами. Тем не менее, чтобы её решить точно, нужно перебрать 5000! вариантов — это число с 16000 знаками. Атомов в видимой вселенной — это число с 80 знаками. Такие задачи решаются приближённо, но всё равно оптимальный путь между 5000 точек за секунды не найти. Мне кажется, что PgRouting всё же за секунды считает просто длину маршрута через фиксированный порядок из 5000 точек.
Да, я читал. Полный перебор всех вариантов это интересно, но практического смысла не имеет. Давайте не будем обсуждать "сферического коня в вакууме". Обратите внимание, что есть определенная точность задания веса каждого ребра и плюс к тому дополнительные факторы — к примеру, между остановкой грузовика на обочине и посещением водителем (экспедитором) крыльца ближайшего дома пройдет несколько минут (запаковаться, вылезти из кабины, открыть кузов, достать посылку, закрыть кузов, дойти до двери дома,...). Так что точности решения задачи порядка 5-10% вполне достаточно на практике, а для этого можно выбрать такие параметры, что PgRouting построит маршрут через заданные 50000 точек за минуты.
Тоже есть Open Source движки специально для этой задачи, от гугла, к примеру. Посмотрите их документацию, познавательно — поймете, как сделать так же с помощью PgRouting или других движков. Задачу можно решать, построив единый маршрут через все точки и разделив его на нужное число частей, а потом назначив каждой части ближайшего коммивояжера. Можно заранее кластеризовать точки маршрута на нужное число кластеров (по кластеру на коммивояжера, в простейшем случае) и построить маршрут в каждом кластере отдельно. И да, лучший вариант — использовать оба метода и выбрать оптимальный результат.
PgRouting за секунды находит маршрут (то есть назначает порядок прохождения) через 5000 точек. Посмотрите же сами, и документация у них отличная.
Один маршрут на 5000 точек — похоже на экзотику (непонятно, где в реальной жизни это может быть применимо), а вот VRP на 5000 точек — вполне актуальная задача.
UPD: tuxxon уже ответил выше
Выше я уже объяснил, как из одного маршрута на 5000 точек получить набор маршрутов. И да, это работает и очень быстро в PgRouting — он бесплатный и с открытым кодом, что вам мешает взять и посмотреть самим?
1) я посмотрел доку PgRouting
pgr_TSP(matrix_cell_sql,...)
...
Example:
SELECT * FROM pgr_TSP(
$$
SELECT * FROM pgr_dijkstraCostMatrix(
...
ну то есть решение TSP-задачи никоим образом не избавляет нас от необходимости иметь матрицу расстояний, что логично.
Вы пишете выше, что PgRouting за секунды решает TSP-задачу на 5000 точек — имеется в виду режим, в котором нужно сначала вычислять матрицу? Или более простая функция,
pgr_eucledianTSP, которая на вход берет просто координаты и считает евклидовы расстояния? Если второе, то так может быть, ведь там можно применять А*-алгоритм. Если первое, т.е. расстояния по графу дорог — извините, не верю в несколько секунд.2) Про разрезание TSP-маршрута тоже подозрительно. Откуда следует, что так можно делать? Его же можно многими способами разрезать, как из них выбрать оптимальный для VRP-задачи? Кажется, легко подобрать пример, когда разрезанный TSP-маршрут не будет оптимальным для VRP-задач. Рассмотрим «звезду»: нам надо объехать точки
по оси Х вправо (1,0) (2,0) ... (5,0)
по оси Х влево (-1,0) (-2,0) ... (-5,0)
По оси Y вверх (0,1) .. (0, 5)
по оси Y вниз (0, -1) .. (0, -5)
Стартуем в нуле.Оптимальный TSP-объезд может выглядеть так: направо до (5,0), по диагонали налево-вверх до (0, 5), вниз до (0, -5), по диагонали до (-5, 0), обратно в начало координат. Он содержит в себе два длинных диагональных перехода между лучами. Очевидно, при разрезании его на несколько маршрутов эти переходы могут быть не нужны, т.к. дешевле отправлять машины по лучам.
Пусть одна машина вмещает 4 единицы, тогда оптимальные маршруты будут, на глаз, такие:
route 1 - (2, 0) (3, 0) (4, 0) (5, 0) - именно в таком порядке, чтобы пустым ехать обратно
route 2 - (0, 2) (0, 3) (0, 4) (0, 5)
route 3 - (-2, 0) (-3, 0) (-4, 0) (-5, 0)
route 4 - (0, -2) (0, -3) (0, -4) (0, -5)
route 5 - (1, 0) (0, 1) (-1, 0) (0, -1)
Эти маршруты (в частности, route 5) не являются отрезками решения оптимального TSP-маршрута.
ну и
3) У нас VRPTW-задача. Локации имеют окна доставки, в которые нужно попадать, в этом смысл. Объезд этих локаций одним коммивояжером вообще никак не поможет.
Знаете, вы сами себе противоречите раз за разом. В статье сказано про вашу задачу (явная задача коммивояжера, TSP):
Поиск оптимального маршрута между множеством точек
Далее, в комменте пишите
Вы неправильно понимаете, мы решаем не TSP, а VRP на 5000 точек.
А теперь уже
3) У нас VRPTW-задача.
Уж будьте любезны с темой статьи и обсуждения определиться.
Как насчет того, что ваше утверждение про разрезание TSP неверно? Пример, который я привожу выше — это простейшая VRP задача, без Time Windows.
Эти маршруты (в частности, route 5) не являются отрезками решения оптимального TSP-маршрута.
Выше я описал два пути:
- построить один оптимальный маршрут по всем точкам и разделить его на части (выделить кластеры точек), после чего назначить каждому коммивояжеру ближайший участок. Далее нужно по каждому набору точек еще раз оптимальный маршрут посчитать, определить начальную и конечную точку (они могут совпадать или не совпадать) — и эти маршруты могут частично не совпадать с исходным, в этом нет никакой проблемы, если их длина с достаточной точностью совпадает (как я уже писал, нужно контролировать точность решения).
- точки можно кластеризовать заранее одним или несколькими способами (простейший способ функциями кластеризации PostGIS с евклидовой метрикой), и по этим кластерам построить отдельные маршруты.
Теперь, опять же как я писал выше, из полученных двумя путями наборов маршрутов выбирается оптимальный набор. На практике оба пути дают хороший результат, при использовании же обоих — отличный результат.
Но только все эти манипуляции
1) очевидно, не оптимальны — вы теряете несколько процентов от оптимума уже в момент кластеризации
2) на практике, довольно сложны и трудоемки. Вам надо потюнить параметры кластеризации, потюнить параметры решения TSP-задач, обернуть это все в конвейер, если вы решаете задачу больше одного раза.
Гораздо лучше иметь сразу нормальный VRP-солвер, не пытаться сделать его из TSP-солвера и такой-то матери.
Как я понимаю, в вашей работе нужно примерно оценить количество машин, тогда ваш подход понятен и правилен: из имеющихся инструментов с небольшими доработками получим результат, который на 10% хуже оптимума. Нам же надо попадать в оптимум, поэтому, возвращаясь к теме статьи, нам нужна честная большая матрица расстояний, посчитанная максимально быстро.
1) Точность нам нужна равная точности дорожного графа и не более, так как это уже не имеет смысла.
2) Параметры pgr_TSP достаточно выбрать один раз, разделение пути на отрезки тоже не требует сложных параметров.
который на 10% хуже оптимума
Пока что видим, что ваш вариант из статьи — примерно в 1000 раз медленнее, точность неизвестна. Выложите примеры, для тех же 5000 точек, как в статье названо, посмотрим. Заодно расскажите, как вы с точностью в разы выше 10% умеете оценивать время в пути — а иначе проблема у вас будет уже в исходных весах маршрутного графа.
нам нужна честная большая матрица расстояний
Нужна минимально необходимая матрица, а все остальное — потери времени.
Гораздо лучше иметь сразу нормальный VRP-солвер
Как так — у вас же только что была уже VRPTW-задача и вы ставили минусы комментариям про VRP? VRP у вас уже была и вы уже передумали :)
Итого, вы рекламируете какой-то велосипед, который даже описать толком не можете, не говоря уж о точных характеристиках.
Пример кода из рабочего проекта:
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 точек (и больше). Где используется — логистика по территории Германии. Зачем столько точек — предварительная оценка времени и расстояния для дневной доставки и назначение нужного количества машин, далее уже для каждого назначенного автомобиля (или байка, или пешехода — есть разные сценарии доставки) вычисляются свои оптимальные маршруты.
Я вряд ли смогу повторить на своей стороне, потому что надо дорожный граф засунуть в постгрес. Можете ли сказать,
1) верно ли я понимаю, что вы сначала отдельным запросом вычисляете матрицу с помощью pgr_dijkstraCostMatrix, и дальше этот подзапрос не пересчитывается заново? Сколько времени занимает вычисление матрицы для 5к точек в постгресе?
2) что делает pgr_dijkstraSymmetrizeCostMatrix? В доке по pgRouting я такой функции не вижу
3) в pgr_TSP можно задавать processing time и еще всякие параметры отжига. Верно ли, что если давать ему работать не несколько секунд, а больше (скажем, полчаса), то общий TSP-маршрут будет сильно (на 5-10%) оптимальнее?
1) Все вычисляется вместе на каждый запрос — ровно так, как здесь показано. Используется оптимизация выборки необходимого участка дорожной сети — скажем, 5000 ребер — так, чтобы гарантированно получить результат и не обрабатывать большую дорожную сеть на каждый запрос (заранее оцениваем, какой участок дорожной сети нужен для роутинга по городу/району/блоку домов — это один параметр для каждого города/района — размер буфера вокруг заданного набора адресов).
2) PgRouting не умеет работать с oneway, которые очень нужны — потому я написал враппер, который конвертирует матрицу с oneway ребрами в симметричную, необходимую для pgr_TSP. Этот момент упоминается где-то в документации по PgRouting — мол, любую матрицу можно привести к требуемой симметричной, думайте сами :)
3) Нет, в моих тестах для большого количества точек результат получался обычно заметно хуже — решение сваливается в первый попавшийся локальный оптимум. На практике все зависит от качества подготовленной маршрутной сети — нужно разделить двусторонние дороги из OSM на пару односторонних (oneway) для избежания виляния между сторонами дороги и т.п.
Раз режим поиска точка-точка уже предельно оптимизирован, мы можем оптимизировать расчёт ряда в матрице. Ряд — это расстояния от одной точки до всех остальных. Пока мы ищем расстояние до самой дальней точки, мы попутно вычисляем расстояния до более близких. Значит, вычисление ряда эквивалентно вычислению расстояния до самой дальней точки.
Ну раз «ряд — расстояние от одной до всех», то это и есть почти классический Дейкстра в чистом виде, которых проходит по всем вершинам. В чем смысл предложения?
На график добавлена линия тренда, которая показывает, что время вычислений растет чуть медленнее, чем линейно по N, порядок N**0.74
Не обращая внимания на то, что никакой линии не добавлено, чего это у вас там N^0.74? N это вроде было количество вершин. Так если вы сделали поиск оптимального пути в графе за O(N^0.74), то вам полагается написать научную статью, открывающую глаза всему миру, который использует алгоритм Дейкстры, который по-определению не лучше чем O(N*log(N)). Только вот, боюсь, или я что-то недопонял или вы написали что-то не так. Ну просто потому что поиск путей от одной вершины до всех остальных даже в теории не может быть лучше O(N), потому что… внезапно, поиск *до всех остальных*, и каждая вершина должна быть посещена хотя бы раз.
что, оказывается, для этой задачи есть алгоритмы с линейной сложностью
К чести статьи, там почти что прямым текстом пишут «it can be done in O(|S| + |T|) point-to-point queries» (где S и T — множества стартовых и конечных точек). Т.е. оно, конечно, линейно, но не в том смысле, как пишете вы. А вы перевернули это с ног на голову.
Если у вас point-to-point query в общем случае занимает O(1) вычислительного времени, то вы совершаете революцию в нашем дремучем мире и вам не на хабр, а в Nature какой-нибудь надо.
Просьба вычитать статью и не писать такой откровенный бред, а также отправить автора на внеклассный курс алгоритмов :)
А могла бы получиться достойная и интересная статья…
— Представьте себя на месте кандидата, который собеседуется в Яндекс, славящийся своим подходом и вопросами о вычислительной сложности. Если вам кандидат начнет такое затирать (про поиск путей от одной до всех вершин быстрее, чем линейно), как вы пишете в статье, он сразу получит red flag, собеседование закончится досрочно или как?
Не обращая внимания на то, что никакой линии не добавлено, чего это у вас там N^0.74? N это вроде было количество вершин. Так если вы сделали поиск оптимального пути в графе за O(N^0.74), то вам полагается написать научную статью, открывающую глаза всему миру, который использует алгоритм Дейкстры, который по-определению не лучше чем O(N*log(N)).
N в тексте — это не количество вершин в графе, а количество точек, до которых требуется найти кратчайший путь. Статью, к сожалению, писать не придётся, потому что сложность Дейкстры, о которой вы пишите, зависит от количества вершин.
Только вот, боюсь, или я что-то недопонял или вы написали что-то не так. Ну просто потому что поиск путей от одной вершины до всех остальных даже в теории не может быть лучше O(N), потому что… внезапно, поиск *до всех остальных*, и каждая вершина должна быть посещена хотя бы раз.
Да, есть такая интуитивная ловушка, что для вычисления ряда алгоритм должен быть не хуже, чем O(n). На самом деле, если время прохода по ряду пренебрежимо мало (1 мс) относительно других вычислений (1 минута), то сложность может быть лучше линейной. Простой способ это показать — построить график, что и сделано в тексте.
Простой способ это показать — построить график, что и сделано в тексте.
*смотрит по сторонам* я все еще на Хабре?
Все-таки сходите на внеклассный курс алгоритмов, пожалуйста. У вас, слышал, ШАД есть, там, говорят, и этому тоже учат. Алгоритмическую сложность графиками доказывать, ну перестаньте, пожалуйста.
У нас это была одна из первых лабораторных работ в универе по алгоритмам — написать несколько сортировок и посмотреть на картинки, попробовать их зааппроксимировать соответствующими ассимптотическими функциями. Да, картинки и графики можно использовать и они зачастую наглядны, но делать выводы об алгоритме исходя из картинок — ну, такое.
На самом деле, если время прохода по ряду пренебрежимо мало (1 мс) относительно других вычислений (1 минута),
Простите, каких «других вычислений»? Собственно, вся ваша задача это же вот насчитать вашу матрицу, а это эквивалентно «количество рядов» * «время прохода по ряду» в вашей терминологии. Т.е. никаких «других вычислений», кроме поисков путей не производится. А если у вас поиск путей работает «пренебрежимо мало», а 1 минуту занимает условное выделение памяти под все это дело, так зачем вообще статью про поиск путей писать? :)
N в тексте — это не количество вершин в графе, а количество точек, до которых требуется найти кратчайший путь. Статью, к сожалению, писать не придётся, потому что сложность Дейкстры, о которой вы пишите, зависит от количества вершин.
Ну да, я понял. Но так еще раз, цитата из статьи по ссылке «can be done in O(|S| + |T|) point-to-point queries». Т.е. ваше N это как раз это |S|+|T|. И вроде как по определению задачи N << |V|. Но проблема в том, что point-to-point это в общем случае никак не O(1), при наивном подходе это вот Дейкстра, который O(|E| + |V|*log|V|). Да, конечно там есть разные оптимизации, но не до константы времени же (разве что если вы устраиваете огромную lookup table, но наверное все-таки нет). Итого сложность общего алгоритма, навскидку, примерно O(N * (|E| + |V|*log|V|)). Используя оценку снизу |E| > |V| >> N из второго предложения, это уж точно никак не лучше, чем O(N^2*logN). Вы же утверждаете, показывая на ваш график, что что-то такое у вас работает как O(N^0.74). Т.е. мало того, что существенный множитель (собственно, поиск путей) у вас оказался «константой», так еще и степень уменьшилась. Не верю-с. Так не бывает.
Погодите, вы же в статье про реальный кейс говорите, а не теоретический. То есть вы считаете матрицу весов для всепланетарного дорожного графа даже при роутинге по одной улице города? И грузите всю матрицу в память? Абсурд какой-то… Хотя приведенное вами время вычислений вполне соответствует такому подходу…
И ещё здорово было бы увидеть статью про уровни иерархического Дейкстры, в каких случаях происходит переход от уровня к уровню и т.п.
Алгоритм Дейкстры с уровнями иерархии никак не работает, нужно сделать некоторую минимизированную выборку необходимых ребер, чтобы большую маршрутную сеть не грузить целиком — вот для этой выборки и используются разные оптимизации. Вот алгоритм A* умеет выбирать наиболее быстро ведущие к цели ребра (детали реализации могут варьироваться в разных движках), так что ему можно скормить маршрутную сеть с дополнительным набором прямых соединений (предварительно посчитанных ребер) между городами и он пройдет, к примеру, по одному такому прямому соединению, соединяющему два города, а не по множеству отдельных сегментов между ними, а в пределах городов будет использовать уже множество исходных ребер для построения маршрута. Если ребра передаются полным списком (PgRouting), нужно оптимизировать этот передаваемый набор ребер, а вот в Spatialite Routing можно работать с целой маршрутной сетью — она оптимизируется предварительно и "на лету" изменения внести уже нельзя.
Алгоритм Дейкстры с уровнями иерархии никак не работает
Девятнадцатая ссылка из статьи про Дейкстру в английской википедии:
Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm
у всех давно и прекрасно работает
В статье сказано, что они используют комбинацию нескольких алгоритмов, и только в одном из шагов используют алгоритм Дейкстры:
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".
Алгоритм Дейкстры это вполне конкретный алгоритм, и не надо его смешивать с производными алгоритмами — их очень много разных, но настолько универсальных, как алгоритм Дейкстры, больше не придумали.
Приведу набор ссылок на 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. Приведенные в статье цифры некорректны более, чем полностью, построение маршрута(ов) выполняется намного быстрее.
Также можно привести задачу VRP к TSP — разделить один построенный маршрут на несколько
Ну нет же, это выглядит очевидно неверным. Я выше привел пример.
Это известный способ решения задачи VRP — кластеризация точек до или после (разделение и перестроение участков маршрута).
А вот чтобы не быть голословными — объясните нам, как это вы VRP решаете с помощью одного лишь алгоритма Дейкстры, как указано в статье? Если вы все еще не понимаете — с помощью алгоритма Дейкстры можно только подготовить матрицу расстояний.
как это вы VRP решаете с помощью одного лишь алгоритма Дейкстры, как указано в статье
Этого не указано в статье. Если вы считаете иначе, то приведите цитату, пожалуйста.
Мы с вами как будто на разных языках разговариваем. Вы то ли троллите, то ли правда не понимаете, что там написано. Поэтому я прекращу комментировать, можете считать, что я слился.
Яндекс.Маршрутизация vs Sygic. Замещаем импортозамещение
По Москве лучше работает Яндекс, а по дальнобою межгород — Sygic
Правда, некоторые моменты в вашей статье остались неясными, например, про мобильное приложение и ключ :) Это же не масштабируемо. Они что-то даже цены не пишут (или я не нашел), ради интереса запросил ключ через сайт, пока не ответили.
Что я из нее узнал?
Также не ясна сама задача: почему водитель, когда уже сел в машину, просто не может открыть телефон и сказать: «Сири, проложи маршрут»? Выполняют ли водители совмещенные поездки (берут сразу несколько заказов и доставляют их по точкам). Может ли точка назначения товара быть точкой отправления для следующего товара? Привязана ли доставка к окнам времени, когда машину могут загрузить — разгрузить.
Я сам не всегда так делаю, но очень полезно в начале статьи писать, на кого она рассчитана и какого рода информацию содержит. На хабре очень разношерстная публика — во всех сразу не угодить, да и людское время тратить зря не стоит. Наверное в Яндексе есть ребята, способные написать (если ими позволят) о решении интересных технических проблем, наверное, есть и те, кто увлекательно рассказывает житейские истории. Просто не стоит подавать второе под соусом первого, а то возникает ощущение обманутых ожиданий.
Пишите чаще и успехов Вам в ваших исследованиях. Спасибо.
Тем более что алгоритм Дейкстры по умолчанию строит связь со всеми узлами. Нужно лишь продолжать поиск пока не будут посещены все узлы. Задача оптимизации полученной матрицы это уже отдельная задача.
Просто оставлю ссылку.
Сотни тысяч маршрутов в секунду на ядро. Опыт Яндекс.Маршрутизации