Оптапланер / графоппер: как решить минимаксную оптимизацию VRP?

Question

У меня есть проблема планирования маршрута, которая состоит из N транспортных средств и> 2N путевых точек. Я хочу оптимизировать их маршрут так, чтобы максимально сократить время / стоимость всех транспортных средств.

Единственными опциями в JVM являются либо optaplanner, либо graphhopper.

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

Answer 1

Смотрите страницу OptaPlanner на маршрутизации транспортных средств:

Вот пример с доставкой набора данных Бельгии в 50 мест (~ ваши путевые точки) с 10 транспортными средствами (не все из них используются) в течение примерно 32 часов реального времени вождения по дороге (без учета трафика):

Посмотрите пример optaplanner-webexamples, чтобы увидеть это в действии (включая карты Google и визуализацию openstreetmap), и посмотрите пример маршрутизации транспортных средств optaplanner-examples, чтобы поиграть с большими наборами данных, случаями с несколькими депо и / или временными окнами.

Вышеуказанный случай минимизирует общую продолжительность (32 часа), но с некоторыми изменениями в vehicleRoutingScoreRules.drl Вы можете изменить его, чтобы свести к минимуму максимальную продолжительность на транспортное средство (просто суммируйте продолжительность на транспортное средство и оштрафуйте квадрат этого числа, см. раздел "Справедливость / балансировка нагрузки" в документах OptaPlanner).