Всем привет!
Выбираем API для построения маршрутов, нужно что бы один маршрут состоял из нескольких точек, куда водиле надо заехать.
Количество запросов на построение маршрутов с точками - где-то 100 - 200 в день, желательно с оптимизацией.
Если кто-то сталкивался, подскажите варианты оных API и что по ценам?

(0) https://tech.yandex.ru/routing/
Довольно дорого

Аналогов с актуальными сведениями по РФ других не знаю, думаю есть но там просто расстояния между точками по дорогам, без учета пробок и текущей/прогнозируемой ситуации на дорогах.

(1)+ Если вам не требуется с учетом пробок то можно сделать сильно дешевле.

берем open street map, пропускаем через pgrouting, запиливаем свой сервис? это первое, что на ум пришло.

(2) Как? Мне тоже скоро надо будет.

(4) Примерно как в (3), только еще куча математики

(5)+ Я только простейшую делал, когда точки складов все заранее известны http://catalog.mista.ru/public/442306/

Если же точки заранее не известны то надо сетку на карту с неким шагом/точностью и считать все маршруты между всеми точками сетки.

Затем эти маршруты использовать находя (причем правильно по дорогам) ближайшую рассчитанную точку к "куда водиле надо заехать" и таким образом и считать, незначительно теряя на точности.

(4) Надо именно определять маршрут готовых рейсов или предварительно делать разбиение исходя их имеющегося автопарка/пула заказов?

(2) нет, не требуются, нужно проложить маршрут через точки

(6) точки заранее известны

(9) А вы кто? Сеть типа Связного или помельче?

(8) OSRM, google, yandex, city guide
Есть еще куча других, например 2gis, Айтоб и прочее
В общем сервисов расчета маршрута дохрена

(10)+ Это к чему, у них вышла проблема что слишком много складов/точек оно несколько часов думает-пересчитывает если добавить/удалить точки.

Но когда уже рассчитано (точки не меняются с днями отправлений машин) то все мгновенно.

Osm2pgrouting - база данных в постгре, уже с методами. Только правильно запрос строить к постгре нужно. Она сама все считает, математики ненужно

(11) Большинство умеет только между двумя точками (даже третью нельзя добавить) построить длину или оптимальный маршрут по дорогам.
Тут же задача найти оптимальные маршруты объезда/посещения нескольких точек, таких почти нет.

(13) Задача не относится к картам ибо пробки не нужны.

Она сводится к графу где есть расстояния между точками. Не нужен pgRouting короче, оно лишнее.

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

(10) Нет, не Связной однозначно, есть 20+ филиалов по стране, в среднем до 10 маршрутов ежедневно с каждого филиала

+(16) точек в одном маршруте до 20

(16) (17) А тогда фигня, меньше получаса будет на 1С считать, даже ВК не надо.

(18)+ Хотя нет, надо знать сколько всего в каждом филиале клиентов-точек, по которым может быть "точек в одном маршруте до 20"

(18) Пользовались API яндекса и гугла, но выбираем дневные лимиты...

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

+(20) яндексу описали ситуацию, жду ответа.., мож ответят)

(19)+ 20*20=400, а вот 20*200 = уже сильно много

(20) заплатите за сервис, если реально нужен и экономит то стоит купить.. а менеджерам задержку на вывод поставить, например не чаще 1 раза в 30 секунд количество обращений сразу упадет.

(14) Вы заблуждаетесь.

(24) вопрос: сколько -> (22)

(25) Возможно сейчас ситуация изменилась, я исследовал это дело пару лет назад.

Но примеры приведите с ссылками как у меня в (1)
Где сразу понятно что можно много точек и строит оптимальный маршрут между ними, меняя порядок точек как надо.

Сначала надо определиться с количеством точек, количеством рейсов, регионом.
У нас 100 рейсов в день, по 10-15 точек. Регион - Москва и область. При такой плотности точек смысла в формировании маршрута - нет. Достаточно разбить регион на 20-30 связанных областей и уже по областям набирать рейсы. В рейс попадают максимум две области. развоз получается достаточно эффективный. Порядок доставки в приделах рейса определяет сам водитель.

(27)+ Ну и почитать про https://ru.wikipedia.org/wiki/Задача_коммивояжёра

(5) Ясн.

(28) Это не работает для регионов/областей которые на порядок больше Московской области.

(31)+ По площади больше с длинными перегонами между точками.

(31) С учетом того, что в России плотность дорог малая, на больших площадях с длинными перегонами можно тоже достаточно легко оптимизировать.
   Сложности возникают, если надо сформировать оптимальный маршрут, если имеется возможность изменять время доставки. Т.е. доставка по 10 заказм сегодня, завтра и послезавтра, может быть менее эффективна, чем доставка 5 заказов сегодня, 10 заказов завтра и 15 заказов послезавтра.

(33) И вот это ни один сервис из (11) не умеет в принципе.

(29) Задача коммивояжера к формированию оптимального развоза имеет очень отдаленное отношение. Согласитесь, что проблема загрузить фуру посылок и развезти эти посылки по ВСЕМ городам России не часто встречается.
  Короче. Оптимальный алгоритм формирования рейсов определяется спецификой решаемых задач и в 95% случаев не связан с API типа Google или Yandex.

(29) Я могу вам дать почитать и про другие задачи, например CVRP. Но зачем письками меряться? Если не верите что перечисленные сервисы решают описанные задачи - не верьте.

Вот вам пример OSRM
http://map.project-osrm.org/?z=13¢er=55.012965%2C82.949696&loc=55.017099%2C82.955532&loc=55.037073%2C82.912273&loc=54.998395%2C82.869186&loc=55.043172%2C82.951241&hl=en&alt=0

Вот вам graphhopper.com
Лень если честно работу работать подбирая варианты

Самый простой способ - пообщаться с диспетчером, который расскажет вам по каким критериям он формирует рейсы, немного подумать и все. Часто критерии будут типа этот водитель не любит ездить в этот район, а в этом районе он просто живет.

(36) Кидаете эти 4 заказа в одну машину, а водитель сам определит как ему ехать. Другой вопрос, если эти 4 заказа нельзя доставить 1 машиной, а может потребоваться 1-2-3 или 4 машины и не по весу, а по дорожным условиям. Вот это не оптимизируешь.

(35) Не понял где там подбор маршрута оптимального то?

В смысле порядка точек из указанных как лучше между ними ехать а не по каким дорогам.
Маршрут по дорогам между двумя точками и как дальнейшее между несколькими по очереди 1-2-3-4 это все умеют.

А покажи сервис который скажет ты сначала едь 4 от своего текущего положения, а уже затем 2-1-3 - так будет быстрее.

(39) к (36)

(38) И это можно оптимизировать, но пока таких сервисов нет и еще долго не будет.

(39) OSRM умеет и гугл тоже умеет, делал такое с доставкой продуктов

(42) Покажите на видео или где это понятно написано

(26)
http://tech.yandex.ru/maps/jsapi/doc/2.1/terms/index-docpage/
http://tech.yandex.ru/maps/commercial/

(43) http://project-osrm.org/docs/v5.5.1/api/#trip-service

еще есть вот такой сервис
https://zig-zag.org/

(43) еще что показать? читай умные книжки, пользуйся гуглом ) за что людят деньги платят? наймите специалистов в конце то концов.

(45) Теперь понял это "плагин Трип"

(48) в логистике еще проблема есть, допустим дорога 5 км, клиенты по правую и левую сторону, только по правую по пути, а по левую в обратную сторону т.к. развернуться можно только через 5 км.

(48)+ https://github.com/Project-OSRM/osrm-backend/issues/1623

(48)+
"Сервис поездки
Плагин trip решает проблему коммивояжера с помощью жадной эвристики (алгоритм дальнего введения). Возвращенный путь не обязательно должен быть самым быстрым путем, поскольку TSP является NP-сложным, это всего лишь приблизительное значение. Обратите внимание, что если входные координаты не могут быть объединены одним отключением (например, координаты находятся на нескольких отключенных островах), возвращается несколько отключений для каждого подключенного компонента."

И это (29)

покупаете прокси и фигачите через яндекс.карты.

на ИС не смотрел? мне на глаза попадалось несколько публикаций типа как тебе надо

(52) Им даже прокси не надо, у них 20+ филиалов по стране, в каждом интернет. Если там, в каждом филиале еще и 1С есть, тут даже админа привлекать ненужно.

(51) все же откройте для себя что-то кроме задачи коммивояжера. https://en.m.wikipedia.org/wiki/Vehicle_routing_problem
Это огромный пласт задач.

(55)  "Обобщает известную проблему коммивояжера (TSP). Впервые он появился в статье Джорджа Данцига и Джона Рамзера в 1959 году"

(55) Покажите плиз свое решение типа моего (6) на любую из "огромный пласт задач"

В чем я ошибся то? Кроме того что не был в курсе что коммивояжера уже прикрутили к нескольким разным сервисам.

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

Это самое дешевое решение про которое и написал практически сразу.

А пытаться прикрутить в продакшен нерабочие или непонятно работающие сервисы но зато бесплатные - это немного странно.
Не лучше ли самим наваять то что подходит лучше, да используя сервисы но не в части "плагинов коммивояжера"?

(54) юзеры работают через рдп, нешний ip один для всех. Была идея сделать пул прокми и через них формировать маршруты

пасиб всем, варианты уловил

(57) Свои самописки слать не буду, поскольку в виде отдельного решения они не оформлялись. Недавно копался в типовых,  могу сослаться на типовой функционал Управления перевозками (ITOBовского). Они строят решение, даже с учетом временных окон. Используют некоторые из сервисов, что я упоминал.
(58) Да решений обобщенной задачи очень немного. И с вами соглашусь, что можно и свое построить. С оговорками, что без внесения кучи информации, которую логист держит зачастую в голове, типовое решение выданное логистом будет скорее всего превосходить по качеству решение найденное алгоритмом.

(61) Угу проще взять нечто для расстояний по дорогам между двумя точками и дать пользователю (логисту) инструмент в руки где он сможет порядок точек переставлять мышкой и видеть итог суммарный по длине общего маршрута.

Этот полуавтомат и проще сделать и вероятно оптимальнее чем полный автомат.

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

(0) Пользуемся вот этим : https://ant-logistics.com/index.html
Умеет строить маршрут по точкам. Ну... это все умеют.
С учетом времени работы. С этим у прочих хуже. Например есть несколько точек на одном маршруте. В маршруте несколько сот. В каждой соте есть точки с разным допустимым временем посещения. Оно умеет построить маршрут и раскидать точки к которым нужно заехать на прямом пути и на обратном.

+ (64) Имеет по ВЕБ-апи принять запрос с точками маршрута. И отправить по апи уже построенный маршрут. Само построение правда делается только на сайте. И только оператором.