Задача (Vehile Routing problem - VRP) была сформулирована более 40 лет назад и сейчас является одной из наиболее трудных и интересных комбинаторных задач. Она заключается в построении оптимальных маршрутов, чтобы удовлетворить условия поставки для некоторого количества покупателей.
На мой взгляд самое сложное в данной задаче легально получить матрицу расстояний между точками, а лучше время проезда с учетом пробок. Если брать по прямой, то толку от такой оптимизации крайне мало
(1) MadHead, собственно да. Мало того, что нужно раздобыть полный граф карты города. Всем ветвям графа нужно как-то проставить вес. Следующая проблема, что граф рельного города настолько большой, что вычисления оптимального маршрута - задача для мощного сервака, а не десктопа.
И тут получается вывод, что нужен сервис типа Яндекса, в котором есть средние скорости по каждому отрезку пути, есть все карты и есть огромные вычислительные мощности
(1) MadHead, город можно сравнить с сильно связным графом
если вы ставите вопрос о том, что с реальными расстояниями будет точнее, то я с вами соглашусь.
в статье проводится сравнение вычислений с матрицей расстояний "по прямой" и "реальными" расстояниями, выигрыш составляет 5%
Если же сравнивать алгоритмы кластеризации (или деление по районам, как все обычно делают) с оптимизацией с расстояниями "по прямой", то думаю что выигрыш будет больше - порядка 20-30% , хотя с такими исследованиями пока не сталкивался.
Geoffrey De Smet предлагает воспользоваться Java библиотекой , основанной на OpenStreetMap, Загрузка всей сети дорог Северной Америки занимает около 6GB.
без наложения на карту и построения маршрута по конкретным географическим условиям и дорогам задача большого смысла не имеет, но разве что в будущем для летающих машин))
(12) mdmdvd, но там только 25 точек (входов и выходов суммарно) или 100 связей ограничение. То есть получится только 10 точек реально считать. Да и с лицензией как то мутно. С чего бы Гугл задарма такой сервис десктопным приложениям раздавало? Это для сайтов, как и у Яндекса, чтобы рекламу доставлять.
С момента публикации прошло более 3 лет.
Просьба к автору поделится опытом практического применения. Используется ли где нибудь на текущий момент времени данный расчет маршрутов? Если используется, то насколько оптимально решается задача и как часто логисты вносят изменения в конечные маршруты? Сколько машин и адресов доставки обычно участвует в расчетах?
Сам optaplanner пока еще развивается, судя по дате последнего релиза: 7.4.1.Final от 24.10.2017.
