company_banner

Сотни тысяч маршрутов в секунду на ядро. Опыт Яндекс.Маршрутизации



    Пару недель назад Даня Тарарухин рассказал на Хабре, как появился наш сервис, Яндекс.Маршрутизация, и как он помогает компаниям с логистикой. Создавая платформу, мы решили несколько интересных проблем, одной из которых и посвящён сегодняшний пост. Я хочу поговорить о самом планировании маршрутов и необходимых для этого ресурсах.

    Поиск оптимального маршрута между множеством точек — классическая задача дискретной оптимизации. Для её решения нужно знать расстояния и времена в пути между всеми точками. То есть — знать матрицу расстояний и времён. Ещё два года назад долгое вычисление матрицы было для нас очень критичной проблемой и блокировало развитие. Сам поиск оптимального решения при известной матрице занимал 10 минут, а вот вычисление всех ячеек матрицы для больших задач (на несколько тысяч заказов) занимало часы.

    Чтобы решить задачу с пятью тысячами заказов, нужно знать расстояния и времена в пути между всеми точками. Это две матрицы чисел размерностью 5000х5000. Мы планируем маршруты курьеров на весь день, и утром курьер доедет от точки до точки за одно время, а вечером — за другое. Значит, нужно вычислять матрицы времён и расстояний для каждого часа дня. Не все часы дня уникальны, но пробочное время (утро и вечер) нужно покрыть хорошо. Поэтому мы пришли к конфигурации с тринадцатью часовыми срезами. Итого нам нужно два куба (времён и расстояний) размерностью 13х5000х5000 каждый. Это 325 млн маршрутов, посчитанных по реальному графу дорог, в котором 165 млн ребёр. Расчёт одного маршрута в хорошо оптимизированном алгоритме команды Яндекс.Карт занимает порядка 10 мс, суммарно получаем 900 часов вычислений. Даже при распараллеливании на 900 CPU нужно ждать 1 час. Такой сервис мы не могли запустить, нужен был более подходящий алгоритм.

    Для дальнейшего чтения полезно знать алгоритм Дейкстры для поиска кратчайшего пути в графе. Его можно представить как «волну», исходящую из точки старта маршрута и идущую кругом по всему графу до тех пор, пока не встретится точка финиша. Время работы алгоритма при этом пропорционально пройденным рёбрам графа, то есть площади, которую покрыла волна:



    Почти каждый кандидат в разработчики на собеседовании догадывается до первого шага оптимизации такой задачи: можно запускать волну с двух сторон и заканчивать поиск, когда волны встретятся. Суммарная площадь двух волн половинного радиуса меньше одной большой.



    Реальный граф дорог достаточно сильно структурирован, и это можно использовать. Когда вы ищете кратчайшее расстояние между Москвой и Питером, в классической Дейкстре вы будете вынуждены распространять волну по кругу и перебирать все улицы и переулки Москвы, подмосковных городов и деревень, улицы Твери и Новгорода. Это огромный объём вычислений, но можно заранее подготовиться и запомнить оптимальные маршруты между городами (aka шорткаты) и не повторять их в рантайме. Тогда для поиска маршрута между двумя точками в иерархической Дейкстре вам останется посчитать кратчайшие расстояния до нужного шортката. Так как уровней иерархии может быть не два, а 5-6, то они драматически снижают время поиска.

    Команда роутера Карт уже достаточно давно реализовала такие оптимизации. Именно они позволили достичь 10 мс для поиска маршрута между двумя точками. :) Так что пока мы не приблизились к решению нашей проблемы.

    Раз режим поиска точка-точка уже предельно оптимизирован, мы можем оптимизировать расчёт ряда в матрице. Ряд — это расстояния от одной точки до всех остальных. Пока мы ищем расстояние до самой дальней точки, мы попутно вычисляем расстояния до более близких. Значит, вычисление ряда эквивалентно вычислению расстояния до самой дальней точки.



    Смотрим на время вычисления ряда по такому алгоритму и вспоминаем, что последовательное вычисление 5000 маршрутов заняло бы порядка 5000 * 10 мс = 50 с:


    На графике показано время вычисления строки в матрице расстояний размером 1*N для разных N (по реальным данным). Видно, что вычисление строки интересующего нас размера 1*5000 укладывается в 1,3 секунды. На график добавлена линия тренда, которая показывает, что время вычислений растет чуть медленнее, чем линейно по N, порядок N**0.74

    Уже неплохо! С таким алгоритмом мы можем посчитать наш куб за 13 * 5000 * 1,3 с = 84 500 с = почти 24 часа. Он легко параллелится по рядам, и при использовании 50 CPU расстояния вычисляются за полчаса. Порядок сложности алгоритма вычисления куба — O(N**1.74):


    График оценочного времени вычисления 13 матриц размером N*N по рядам на 50 CPU (домножили предыдущий график на 13*N/50). По этому графику мы принимали решение, что если к нам придет клиент с 5000 заказов, то мы должны уложиться в полчаса со всеми тринадцатью часовыми срезами. А вот если заказов станет 10 000, то всё плохо: придётся добавлять железо или увеличивать время.

    В таком виде два с половиной года назад мы запустили первую версию нашего API, решающего логистическую задачу. Клиенты достаточно часто жаловались на долгое время решения, и их легко понять: ты запустил задачу решаться, ждёшь 1 час, получаешь решение и понимаешь, что забыл поправить время смены у водителя, исправляешь и всё начинается сначала. Водители начинают нервничать, так как рискуют попасть в утренний час пик, а то и вовсе не успеют доставить заказ в срок. Нужно было что-то делать. «Закидывать» проблему железом не хотелось: мы готовились к большим нагрузкам, потребовалось бы много железа, да и закупка серверов происходит не одномоментно.

    Изучение академических статей показало, что, оказывается, для этой задачи есть алгоритмы с линейной сложностью*! (В статье по ссылке есть большой обзор всевозможных современных способов ускорения Дейкстры, в том числе и для матричного случая.) Вычислять матрицу за линейное время — это не укладывалось в голове. Один из наших разработчиков вызвался написать прототип, и вот что получилось:


    Время вычисления одной матрицы размера N*N на одном CPU с помощью алгоритма «быстрых матриц». Сложность получается порядка O(N**1,1). Высокие N выбиваются из линии тренда, поскольку на время уже больше влияет генерация ответа и его скачивание по сети.

    115 секунд на матрицу 5000х5000 при использовании одного ядра и почти линейная зависимость от N. Фантастика стала реальностью! Идея алгоритма комбинирует две описанные выше идеи: Дейкстру для рядов и иерархический поиск. Очевидно, что, начав вычислять второй ряд, мы в какой-то момент вновь будем обходить ту же область графа, которую мы только что проходили, вычисляя предыдущий ряд. Поэтому давайте запоминать в узлах иерархического графа кратчайшие расстояния до всех destinations. Когда мы начнём вычислять следующий ряд, то, дойдя до такого узла, мы разом получим почти все расстояния до других точек.



    Полтора года назад это позволило нам сэкономить полчаса времени седения волос логиста и существенно уменьшить потребление железа. Если раньше на один большой запрос нам требовалось 50 ядер на полчаса, то теперь — 13 ядер на 2 минуты. Это примерно 200 000 маршрутов в секунду на ядро. Тот редкий случай, когда новый алгоритм не просто закрывает класс проблем, а расширяет наши представления о возможном.


    * Статья «Route Planning in Transportation Networks», см. параграф 2.7.2 «Batched Shortest Paths»
    Яндекс
    Как мы делаем Яндекс

    Комментарии 49

      +3

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

        +2

        Да уж — алгоритм поиска оптимального пути к единственной точке (алгоритм Дейкстры) вообще не имеет смысла использовать для задачи коммивояжера, когда нам нужен кольцевой маршрут по всем точкам. Более того, задавая требуемую точность нахождения пути между двумя точками алгоритмом Дейкстры с эвристиками, абсолютно не очевидно, как посчитать точность кольцевого маршрута из найденных сегментов между множеством точек — то есть оценить адекватность построенного маршрута мы не сможем. Алгоритмы типа отжига оперируют ошибкой для всего пути, что разумно. Про вычислительную сложность не стоит и говорить, а еще на практике необходимо оптимизировать количество пересечений улиц (да, не стоит в шахматном порядке метаться между домами на разных сторонах улицы, а надо проехать сначала одну сторону улицы, потом развернуться и проехать другую сторону) и т.п. — что с посегментным поиском пути не реализуемо в принципе.

          +1
          На графе дорог с пробками такие алгоритмы, как A*, плохо работают. Грубо говоря, ехать прямо через центр Москвы может быть дольше, чем по МКАДу и наоборот — всё зависит от того, где пробка.

          Простой алгоритм Дейкстры правда неоптимален, поэтому мы используем иерархический вариант, которому помогает естественная декомпозицая дорожного графа на города, округа и районы. Нам поэтому не приходится обсчитывать честную волну по огромному графу. Большая часть расстояний (вроде расстояния Москва — Санкт-Петербург) посчитаны заранее и не вычисляются в рантайме.
            +1

            На графах не бывает пробок :) При назначенных весах (время прохождения ребра) нет никаких проблем работать с пробками.


            Еще раз — представленное решение настолько плохо, что любой Open Source роутинг типа PgRouting или Spatialite Routing будет на порядки быстрее (100-1000 раз, навскидку). Иерархический подход дело хорошее, но это оптимизация, а у вас проблема в подходе. Никаких "25 млн полноценных маршрутов", как вы пишите в предыдущем комментарии, у вас нет — вы ищите 5000 сегментов между 5000 точек одного маршрута. Вот даже "тупой" итеративный алгоритм разбиения на два работает лучше вашего: построить один путь между двумя наиболее удаленными точками (для начала евклидова дистанция подойдет) методом Дейкстры, найти наиболее удаленную от маршрута точку и добавить ее в маршрут как промежуточную (посчитав 2 пути от нее — к первой и последней) и т.п. Сколько здесь итераций и путей, уже понятно? Попробуйте, удивитесь, насколько это будет проще и быстрее.

              +1
              Нет же. В соседнем треде я попытался объяснить, что мы не считаем маршрут с 5000 фиксированными остановками. Упрощая, мы ищем оптимальный порядок их объезда.
                +1

                Вы ищите оптимальный маршрут с 5000 остановок. Разумеется, надо найти их оптимальный порядок — а задача просто найти путь решается и вовсе за миллисекунды. В полученном (одном) итоговом маршруте у вас будет именно 5000 остановок. И именно эта задача решается намного быстрее и проще, чем вы делаете.

                +1
                >При назначенных весах (время прохождения ребра)
                Это те самые веса, которые зависят от времени? От того времени, которое затратили на предыдущую часть маршрута? Ну да, ну да.

                >любой Open Source роутинг типа PgRouting или Spatialite Routing будет на порядки быстрее
                А можно тут пруф? Это же не сложно, очевидно. Причем насколько я понимаю, не для одиночного маршрута, потому что PgRouting умеет вроде решать задачу TSP?
                  +1

                  Да, это несложно. Выкладывайте нужный кусок вашего маршрутного графа и набор точек и вашу реализацию и результат. Я лично берусь показать вариант с PgRouting и, если будет смысл, еще каким движком.

                    +3
                    Так я к Яндексу не имею никакого отношения, я просто почитать зашел.

                    Просто вы очень смело утверждаете про два-три порядка, и по вашим постам видно, что недоверять вам нет никакого резона, но циферок-то никаких нет, сравнить мы как читатели со стороны ничего не можем. Было бы неплохо какие-то реальные измерения. Хотя я понимаю, что это может быть трудозатратно.
                      +2

                      Как раз не проблема — пример с PgRouting я выложить могу, скажем, участок дорожной сети OSM по Германии и роутинг на нем. Интересно? Я уже обещал на хабре статью про роутинг написать, вот как раз думаю, что туда включить. Пока тут комментарии писал, много всего уже вспомнил подходящего:)

                        +1
                        Да, конечно интересно.
            +1
            Если раньше на один большой запрос нам требовалось 50 ядер на полчаса, то теперь — 13 ядер на 2 минуты. Это примерно 200 000 маршрутов в секунду на ядро.

            Какая-то подмена понятий. Маршрут коммивояжера для задачи коммивояжера — это маршрут со всеми остановками. Откуда взялись "200 000 маршрутов в секунду на ядро"?!!! Вероятно, имеются в виду ребра графа, но это паршивый результат, так что автор статьи подменил термины...


            P.S. Ну и вообще результаты выглядят печально — PostgreSQL/PgRouting на маршрут с 5000 остановок тратит единицы секунд вычислений на одном ядре (карта OSM по территории Европы).

              +2
              Нам нужно знать все кратчайшие расстояния из 5000 точек в 5000 точек. Это 25 млн полноценных маршрутов, не рёбер. Мы их точно высчитываем за 115 секунд на одном ядре. Делим одно на другое — получаем 200к маршрутов в секунду на ядро.

              Пример с 5000 остановок несколько не про то, как мне кажется. Там считается 5000 маршрутов, а не 25 млн.
                0

                Как я понял из статьи, вам нужно решить задачу коммивояжера — построить один маршрут с 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

                  +3
                  Да, в итоге нам нужно решить CVRPTW — задача коммивояжёра, только коммивяжёров у нас много и надо решить, какому коммивояжёру какой заказ отдать. Перед тем, как начать её решать, нужно посчитать матрицу расстояний между всеми точками. Текст как раз про то, как мы эту матрицу решаем.

                  После того, как матрицу посчитали, можно решать уже саму задачу нахождения оптимального пути. Задача коммивояжёра на 5000 точек проще, чем эта же задача с многими коммивояжёрами. Тем не менее, чтобы её решить точно, нужно перебрать 5000! вариантов — это число с 16000 знаками. Атомов в видимой вселенной — это число с 80 знаками. Такие задачи решаются приближённо, но всё равно оптимальный путь между 5000 точек за секунды не найти. Мне кажется, что PgRouting всё же за секунды считает просто длину маршрута через фиксированный порядок из 5000 точек.
                    +2
                    Вот тут можно ознакомиться с современным состоянием дел в решении задачи коммивояжёра. Решение задачи оптимального обхода 50000 пабов Великобритании — это был прорыв, который решали днями на суперкомпьютере.
                      0

                      Да, я читал. Полный перебор всех вариантов это интересно, но практического смысла не имеет. Давайте не будем обсуждать "сферического коня в вакууме". Обратите внимание, что есть определенная точность задания веса каждого ребра и плюс к тому дополнительные факторы — к примеру, между остановкой грузовика на обочине и посещением водителем (экспедитором) крыльца ближайшего дома пройдет несколько минут (запаковаться, вылезти из кабины, открыть кузов, достать посылку, закрыть кузов, дойти до двери дома,...). Так что точности решения задачи порядка 5-10% вполне достаточно на практике, а для этого можно выбрать такие параметры, что PgRouting построит маршрут через заданные 50000 точек за минуты.

                      0

                      Тоже есть Open Source движки специально для этой задачи, от гугла, к примеру. Посмотрите их документацию, познавательно — поймете, как сделать так же с помощью PgRouting или других движков. Задачу можно решать, построив единый маршрут через все точки и разделив его на нужное число частей, а потом назначив каждой части ближайшего коммивояжера. Можно заранее кластеризовать точки маршрута на нужное число кластеров (по кластеру на коммивояжера, в простейшем случае) и построить маршрут в каждом кластере отдельно. И да, лучший вариант — использовать оба метода и выбрать оптимальный результат.


                      PgRouting за секунды находит маршрут (то есть назначает порядок прохождения) через 5000 точек. Посмотрите же сами, и документация у них отличная.

                      +3
                      Вы неправильно понимаете, мы решаем не TSP, а VRP на 5000 точек.
                      Один маршрут на 5000 точек — похоже на экзотику (непонятно, где в реальной жизни это может быть применимо), а вот VRP на 5000 точек — вполне актуальная задача.

                      UPD: tuxxon уже ответил выше
                        0

                        Выше я уже объяснил, как из одного маршрута на 5000 точек получить набор маршрутов. И да, это работает и очень быстро в PgRouting — он бесплатный и с открытым кодом, что вам мешает взять и посмотреть самим?

                          +2
                          Простите, вы что-то очень странное пишете. Кажется, вы говорите о какой-то сферической TSP-задаче в вакууме.

                          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-задача. Локации имеют окна доставки, в которые нужно попадать, в этом смысл. Объезд этих локаций одним коммивояжером вообще никак не поможет.
                            –3

                            Знаете, вы сами себе противоречите раз за разом. В статье сказано про вашу задачу (явная задача коммивояжера, TSP):


                            Поиск оптимального маршрута между множеством точек

                            Далее, в комменте пишите


                            Вы неправильно понимаете, мы решаем не TSP, а VRP на 5000 точек.

                            А теперь уже


                            3) У нас VRPTW-задача.

                            Уж будьте любезны с темой статьи и обсуждения определиться.

                              +2
                              Ну я вам сразу написал, вы неправильно понимаете, какую задачу мы решаем. Возможно, в тексте Тихона это не совсем удачно написано, но вроде очевидно, что 5000 заказов никак одной машиной в реальной жизни нельзя развезти, то есть, это не может быть TSP-задача на 5000 точек.

                              Как насчет того, что ваше утверждение про разрезание TSP неверно? Пример, который я привожу выше — это простейшая VRP задача, без Time Windows.
                                +1
                                Эти маршруты (в частности, route 5) не являются отрезками решения оптимального TSP-маршрута.

                                Выше я описал два пути:


                                • построить один оптимальный маршрут по всем точкам и разделить его на части (выделить кластеры точек), после чего назначить каждому коммивояжеру ближайший участок. Далее нужно по каждому набору точек еще раз оптимальный маршрут посчитать, определить начальную и конечную точку (они могут совпадать или не совпадать) — и эти маршруты могут частично не совпадать с исходным, в этом нет никакой проблемы, если их длина с достаточной точностью совпадает (как я уже писал, нужно контролировать точность решения).
                                • точки можно кластеризовать заранее одним или несколькими способами (простейший способ функциями кластеризации PostGIS с евклидовой метрикой), и по этим кластерам построить отдельные маршруты.

                                Теперь, опять же как я писал выше, из полученных двумя путями наборов маршрутов выбирается оптимальный набор. На практике оба пути дают хороший результат, при использовании же обоих — отличный результат.

                                  +3
                                  Это все отлично и правильно, более того, логисты руками «на коленках» именно так и делают: кластеризуют точки на глазок, а потом внутри кластеров, по сути, решают TSP-задачу с окнами. Или не решают, а отдают на откуп водителю. В начале статьи есть ссылка на мою статью, там даже картинка с кластерами приведена.

                                  Но только все эти манипуляции
                                  1) очевидно, не оптимальны — вы теряете несколько процентов от оптимума уже в момент кластеризации
                                  2) на практике, довольно сложны и трудоемки. Вам надо потюнить параметры кластеризации, потюнить параметры решения TSP-задач, обернуть это все в конвейер, если вы решаете задачу больше одного раза.
                                  Гораздо лучше иметь сразу нормальный VRP-солвер, не пытаться сделать его из TSP-солвера и такой-то матери.

                                  Как я понимаю, в вашей работе нужно примерно оценить количество машин, тогда ваш подход понятен и правилен: из имеющихся инструментов с небольшими доработками получим результат, который на 10% хуже оптимума. Нам же надо попадать в оптимум, поэтому, возвращаясь к теме статьи, нам нужна честная большая матрица расстояний, посчитанная максимально быстро.
                                    0

                                    1) Точность нам нужна равная точности дорожного графа и не более, так как это уже не имеет смысла.


                                    2) Параметры pgr_TSP достаточно выбрать один раз, разделение пути на отрезки тоже не требует сложных параметров.


                                    который на 10% хуже оптимума

                                    Пока что видим, что ваш вариант из статьи — примерно в 1000 раз медленнее, точность неизвестна. Выложите примеры, для тех же 5000 точек, как в статье названо, посмотрим. Заодно расскажите, как вы с точностью в разы выше 10% умеете оценивать время в пути — а иначе проблема у вас будет уже в исходных весах маршрутного графа.


                                    нам нужна честная большая матрица расстояний

                                    Нужна минимально необходимая матрица, а все остальное — потери времени.


                                    Гораздо лучше иметь сразу нормальный VRP-солвер

                                    Как так — у вас же только что была уже VRPTW-задача и вы ставили минусы комментариям про VRP? VRP у вас уже была и вы уже передумали :)


                                    Итого, вы рекламируете какой-то велосипед, который даже описать толком не можете, не говоря уж о точных характеристиках.

                              +2

                              Пример кода из рабочего проекта:


                              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 точек (и больше). Где используется — логистика по территории Германии. Зачем столько точек — предварительная оценка времени и расстояния для дневной доставки и назначение нужного количества машин, далее уже для каждого назначенного автомобиля (или байка, или пешехода — есть разные сценарии доставки) вычисляются свои оптимальные маршруты.

                                0
                                О, это интересно!
                                Я вряд ли смогу повторить на своей стороне, потому что надо дорожный граф засунуть в постгрес. Можете ли сказать,

                                1) верно ли я понимаю, что вы сначала отдельным запросом вычисляете матрицу с помощью pgr_dijkstraCostMatrix, и дальше этот подзапрос не пересчитывается заново? Сколько времени занимает вычисление матрицы для 5к точек в постгресе?

                                2) что делает pgr_dijkstraSymmetrizeCostMatrix? В доке по pgRouting я такой функции не вижу

                                3) в pgr_TSP можно задавать processing time и еще всякие параметры отжига. Верно ли, что если давать ему работать не несколько секунд, а больше (скажем, полчаса), то общий TSP-маршрут будет сильно (на 5-10%) оптимальнее?
                                  +1

                                  1) Все вычисляется вместе на каждый запрос — ровно так, как здесь показано. Используется оптимизация выборки необходимого участка дорожной сети — скажем, 5000 ребер — так, чтобы гарантированно получить результат и не обрабатывать большую дорожную сеть на каждый запрос (заранее оцениваем, какой участок дорожной сети нужен для роутинга по городу/району/блоку домов — это один параметр для каждого города/района — размер буфера вокруг заданного набора адресов).


                                  2) PgRouting не умеет работать с oneway, которые очень нужны — потому я написал враппер, который конвертирует матрицу с oneway ребрами в симметричную, необходимую для pgr_TSP. Этот момент упоминается где-то в документации по PgRouting — мол, любую матрицу можно привести к требуемой симметричной, думайте сами :)


                                  3) Нет, в моих тестах для большого количества точек результат получался обычно заметно хуже — решение сваливается в первый попавшийся локальный оптимум. На практике все зависит от качества подготовленной маршрутной сети — нужно разделить двусторонние дороги из OSM на пару односторонних (oneway) для избежания виляния между сторонами дороги и т.п.

                    +3
                    Не очень понятны детали, автор как-то ловко жонглирует терминами и избегает адекватного анализа сложности.

                    Раз режим поиска точка-точка уже предельно оптимизирован, мы можем оптимизировать расчёт ряда в матрице. Ряд — это расстояния от одной точки до всех остальных. Пока мы ищем расстояние до самой дальней точки, мы попутно вычисляем расстояния до более близких. Значит, вычисление ряда эквивалентно вычислению расстояния до самой дальней точки.

                    Ну раз «ряд — расстояние от одной до всех», то это и есть почти классический Дейкстра в чистом виде, которых проходит по всем вершинам. В чем смысл предложения?

                    На график добавлена линия тренда, которая показывает, что время вычислений растет чуть медленнее, чем линейно по 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, собеседование закончится досрочно или как?
                      0
                      Не обращая внимания на то, что никакой линии не добавлено, чего это у вас там N^0.74? N это вроде было количество вершин. Так если вы сделали поиск оптимального пути в графе за O(N^0.74), то вам полагается написать научную статью, открывающую глаза всему миру, который использует алгоритм Дейкстры, который по-определению не лучше чем O(N*log(N)).


                      N в тексте — это не количество вершин в графе, а количество точек, до которых требуется найти кратчайший путь. Статью, к сожалению, писать не придётся, потому что сложность Дейкстры, о которой вы пишите, зависит от количества вершин.

                      Только вот, боюсь, или я что-то недопонял или вы написали что-то не так. Ну просто потому что поиск путей от одной вершины до всех остальных даже в теории не может быть лучше O(N), потому что… внезапно, поиск *до всех остальных*, и каждая вершина должна быть посещена хотя бы раз.


                      Да, есть такая интуитивная ловушка, что для вычисления ряда алгоритм должен быть не хуже, чем O(n). На самом деле, если время прохода по ряду пренебрежимо мало (1 мс) относительно других вычислений (1 минута), то сложность может быть лучше линейной. Простой способ это показать — построить график, что и сделано в тексте.
                        +3
                        Простой способ это показать — построить график, что и сделано в тексте.


                        *смотрит по сторонам* я все еще на Хабре?

                        Все-таки сходите на внеклассный курс алгоритмов, пожалуйста. У вас, слышал, ШАД есть, там, говорят, и этому тоже учат. Алгоритмическую сложность графиками доказывать, ну перестаньте, пожалуйста.
                        У нас это была одна из первых лабораторных работ в универе по алгоритмам — написать несколько сортировок и посмотреть на картинки, попробовать их зааппроксимировать соответствующими ассимптотическими функциями. Да, картинки и графики можно использовать и они зачастую наглядны, но делать выводы об алгоритме исходя из картинок — ну, такое.

                        На самом деле, если время прохода по ряду пренебрежимо мало (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). Т.е. мало того, что существенный множитель (собственно, поиск путей) у вас оказался «константой», так еще и степень уменьшилась. Не верю-с. Так не бывает.
                          0
                          Размер графа конечно же константа в рассматриваемом контексте: он никак не меняется от того, считаем мы расстояния до 100 точек или до 5000 точек.
                            +1

                            Погодите, вы же в статье про реальный кейс говорите, а не теоретический. То есть вы считаете матрицу весов для всепланетарного дорожного графа даже при роутинге по одной улице города? И грузите всю матрицу в память? Абсурд какой-то… Хотя приведенное вами время вычислений вполне соответствует такому подходу…

                      +1
                      Давно не пользовался вашим построением маршрутов, но раньше замечал такую особенность: я так понял, что алгоритм не различал варианты проезда перекрёста: прямо, направо и налево. Из-за чего мне, например, предлагалось повернуть 3 раза налево, ради экономии нескольких метров, вместо того чтобы ехать чаще по прямой и только 1 раз повернуть налево. Даже для поворота направо требуется как минимум скинуть скорость, а для поворота налево требуется пропустить всю встречку, а это долго.
                      Кривенько проиллюстрирую
                      image

                      И ещё здорово было бы увидеть статью про уровни иерархического Дейкстры, в каких случаях происходит переход от уровня к уровню и т.п.
                        0
                        Насколько я знаю, этой проблемой занимались и должно было стать лучше. Над темами будущих статей мы сейчас думаем, спасибо.
                          0

                          Алгоритм Дейкстры с уровнями иерархии никак не работает, нужно сделать некоторую минимизированную выборку необходимых ребер, чтобы большую маршрутную сеть не грузить целиком — вот для этой выборки и используются разные оптимизации. Вот алгоритм A* умеет выбирать наиболее быстро ведущие к цели ребра (детали реализации могут варьироваться в разных движках), так что ему можно скормить маршрутную сеть с дополнительным набором прямых соединений (предварительно посчитанных ребер) между городами и он пройдет, к примеру, по одному такому прямому соединению, соединяющему два города, а не по множеству отдельных сегментов между ними, а в пределах городов будет использовать уже множество исходных ребер для построения маршрута. Если ребра передаются полным списком (PgRouting), нужно оптимизировать этот передаваемый набор ребер, а вот в Spatialite Routing можно работать с целой маршрутной сетью — она оптимизируется предварительно и "на лету" изменения внести уже нельзя.

                            +2
                            Алгоритм Дейкстры с уровнями иерархии никак не работает

                            Девятнадцатая ссылка из статьи про Дейкстру в английской википедии:
                            Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm
                            у всех давно и прекрасно работает

                              0

                              В статье сказано, что они используют комбинацию нескольких алгоритмов, и только в одном из шагов используют алгоритм Дейкстры:


                              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

                          Приведу набор ссылок на 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. Приведенные в статье цифры некорректны более, чем полностью, построение маршрута(ов) выполняется намного быстрее.

                            +1
                            Также можно привести задачу VRP к TSP — разделить один построенный маршрут на несколько


                            Ну нет же, это выглядит очевидно неверным. Я выше привел пример.
                              +1

                              Это известный способ решения задачи VRP — кластеризация точек до или после (разделение и перестроение участков маршрута).


                              А вот чтобы не быть голословными — объясните нам, как это вы VRP решаете с помощью одного лишь алгоритма Дейкстры, как указано в статье? Если вы все еще не понимаете — с помощью алгоритма Дейкстры можно только подготовить матрицу расстояний.

                                0
                                как это вы VRP решаете с помощью одного лишь алгоритма Дейкстры, как указано в статье

                                Этого не указано в статье. Если вы считаете иначе, то приведите цитату, пожалуйста.

                                Мы с вами как будто на разных языках разговариваем. Вы то ли троллите, то ли правда не понимаете, что там написано. Поэтому я прекращу комментировать, можете считать, что я слился.
                                  +1

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

                            +1
                            Классно, что людям есть о чём написать, о чём поспорить… Для меня статья прозвучала так — у нас было медленно, а потом мы «прочитали книжки», и всё стало быстро!) Осталось с комментаторами разобраться, и объяснить, что мы делали!)
                              0
                              Со времен рассказа Дани Тарарухина мы проверили Sygic.
                              Яндекс.Маршрутизация vs Sygic. Замещаем импортозамещение
                              По Москве лучше работает Яндекс, а по дальнобою межгород — Sygic
                                0
                                Спасибо, интересный текст. Насколько я понимаю, основная проблема — это отсутствие у яндексной маршрутизации полноценной поддержки грузового графа дорог. Это известная задача, пока что начали с Москвы и ее «грузового каркаса».

                                Правда, некоторые моменты в вашей статье остались неясными, например, про мобильное приложение и ключ :) Это же не масштабируемо. Они что-то даже цены не пишут (или я не нашел), ради интереса запросил ключ через сайт, пока не ответили.
                                +1
                                Допустим, я дочитал статью внимательно и до конца.
                                Что я из нее узнал?

                                Также не ясна сама задача: почему водитель, когда уже сел в машину, просто не может открыть телефон и сказать: «Сири, проложи маршрут»? Выполняют ли водители совмещенные поездки (берут сразу несколько заказов и доставляют их по точкам). Может ли точка назначения товара быть точкой отправления для следующего товара? Привязана ли доставка к окнам времени, когда машину могут загрузить — разгрузить.

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

                                Пишите чаще и успехов Вам в ваших исследованиях. Спасибо.
                                  0
                                  Последовательный расчёт 5000 маршрутов типа точка-точка ущербен изначально.
                                  Тем более что алгоритм Дейкстры по умолчанию строит связь со всеми узлами. Нужно лишь продолжать поиск пока не будут посещены все узлы. Задача оптимизации полученной матрицы это уже отдельная задача.
                                  Просто оставлю ссылку.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое