Есть ли ПО для нахождения оптимального маршрута?

Question

[Sergei Iamskoi]

Если ли готовые библиотеки, модули или еще ПО для нахождения оптимальных маршрутов на карте? Есть набор адресов, около 6000 (можно сократить, если разбить в рамках одного города, будет до 500) штук, нужно разбить их на группы по 10 штук и найти самые оптимальные маршруты. Может, есть какая-нить надстройка к Postgis? Пока даже не знаю с какой стороны подойти к задаче.
Сами адреса не проблема конвертировать в координаты.

Comments

[Sergei Iamskoi]

freeExec, поправил

[freeExec]

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

[Sergei Iamskoi]

freeExec, к сожалению оно не решает задачу с разделением на группы :( Как я понял есть такие реализации: закидывается пакет точек, и предлагаются именно для этих всех точек маршруты. А хотелось бы закинуть, допустим 30 точек, и в результате получить 3 группы по 10 точек с оптимальными маршрутами.

Answer 1

[grinat]

project-osrm.org
project-osrm.org/docs/v5.22.0/api/#trip-service

https://developers.google.com/maps/documentation/d... см. Optimize your waypoints