Игрушки для логиста

0. Филипп Синявский (phsin) 118 14.10.14 15:54 Сейчас в теме
Задача (Vehile Routing problem - VRP) была сформулирована более 40 лет назад и сейчас является одной из наиболее трудных и интересных комбинаторных задач. Она заключается в построении оптимальных маршрутов, чтобы удовлетворить условия поставки для некоторого количества покупателей.

Перейти к публикации

Комментарии
1. Михаил Горбов (MadHead) 56 15.10.14 01:14 Сейчас в теме
На мой взгляд самое сложное в данной задаче легально получить матрицу расстояний между точками, а лучше время проезда с учетом пробок. Если брать по прямой, то толку от такой оптимизации крайне мало
FFelix; monkbest; +2 Ответить
4. Антон Антонов (monkbest) 28 15.10.14 09:20 Сейчас в теме
(1) MadHead, собственно да. Мало того, что нужно раздобыть полный граф карты города. Всем ветвям графа нужно как-то проставить вес. Следующая проблема, что граф рельного города настолько большой, что вычисления оптимального маршрута - задача для мощного сервака, а не десктопа.
И тут получается вывод, что нужен сервис типа Яндекса, в котором есть средние скорости по каждому отрезку пути, есть все карты и есть огромные вычислительные мощности
6. Сергей (ildarovich) 5334 15.10.14 09:48 Сейчас в теме
(4) monkbest, никаких огромных мощностей не нужно: http://habrahabr.ru/post/211388/ там у них получилось от 60 до 250 ms на на Core i7 3.4 Ghz.
9. Филипп Синявский (phsin) 118 15.10.14 10:29 Сейчас в теме
(4) monkbest, вы можете опробовать Optaplanner на своём компьютере, думаю, вы будете приятно удивлены
7. Филипп Синявский (phsin) 118 15.10.14 10:14 Сейчас в теме
(1) MadHead, город можно сравнить с сильно связным графом
если вы ставите вопрос о том, что с реальными расстояниями будет точнее, то я с вами соглашусь.
в статье Vehicle routing with real road distances проводится сравнение вычислений с матрицей расстояний "по прямой" и "реальными" расстояниями, выигрыш составляет 5%

Если же сравнивать алгоритмы кластеризации (или деление по районам, как все обычно делают) с оптимизацией с расстояниями "по прямой", то думаю что выигрыш будет больше - порядка 20-30% , хотя с такими исследованиями пока не сталкивался.
2. Анатолий Шведов (ShtomBY) 15.10.14 01:30 Сейчас в теме
с учетом пробок? это было бы интереснее)
3. Сергей (ildarovich) 5334 15.10.14 09:08 Сейчас в теме
Ссылки интересные приведены
5. Наталья Резникова (natarezn) 15.10.14 09:33 Сейчас в теме
100 процентов не коммуникативно ?
8. Филипп Синявский (phsin) 118 15.10.14 10:26 Сейчас в теме
Geoffrey De Smet предлагает воспользоваться Java библиотекой GraphHopper, основанной на OpenStreetMap, Загрузка всей сети дорог Северной Америки занимает около 6GB.
10. Ольга Петровская (pt_olga) 62 22.10.14 19:20 Сейчас в теме
без наложения на карту и построения маршрута по конкретным географическим условиям и дорогам задача большого смысла не имеет, но разве что в будущем для летающих машин))
11. Сергей (ildarovich) 5334 22.10.14 20:06 Сейчас в теме
(10) pt_olga, будущее уже совсем рядомнаступило - DHL запускает беспилотную доставку в Германии(Ссылка)

А вот еще на ту же тему: Создателя Copter Express оштрафовали за доставку пиццы дронами. В последнем случае дело происходило в Сыктывкаре.
Прикрепленные файлы:
12. Иванов Дмитрий (mdmdvd) 53 30.10.14 15:02 Сейчас в теме
Можно попробовать сервис от Гугл Матрица Расстояний называется
13. Филипп Синявский (phsin) 118 30.10.14 15:35 Сейчас в теме
(12) mdmdvd, спасибо за интересную ссылку.
14. Сергей (ildarovich) 5334 30.10.14 20:43 Сейчас в теме
(12) mdmdvd, но там только 25 точек (входов и выходов суммарно) или 100 связей ограничение. То есть получится только 10 точек реально считать. Да и с лицензией как то мутно. С чего бы Гугл задарма такой сервис десктопным приложениям раздавало? Это для сайтов, как и у Яндекса, чтобы рекламу доставлять.
Оставьте свое сообщение