Как смоделировать проблему маршрутизации транспортного средства, когда потребительский спрос превышает вместимость транспортного средства

Question

Я совершенно новичок в optaplanner и ищу предложения о том, как смоделировать проблему маршрутизации транспортных средств в ситуациях, когда спрос Заказчика превышает количество любого отдельного транспортного средства. В качестве упрощенного примера c можно привести 1-склад, 1-грузовик (вместимость 50) и 1-заказчик (спрос 100). Грузовик в этом случае, очевидно, должен совершить две поездки в оба конца к клиенту, каждый раз собирая по 50 единиц. Для меня это не выглядит так, как если бы пример использовался в таких ситуациях.

В общем, у меня есть депо, парк транспортных средств, каждый с вместимостью предметов, и набор сайтов, каждый из которых содержит количество предметов. Транспортные средства должны коллективно перемещать все предметы с площадок в склад. Это почти идентично примеру проблемы с маршрутизацией транспортных средств, но, если я что-то упустил, этот пример, похоже, не учитывает вероятность того, что грузовикам может понадобиться совершить несколько поездок и посетить один и тот же клиентский сайт несколько раз. Есть ли другой пример, который был бы более уместным?

В добавлении, я думаю, я мог бы смоделировать это, если бы мог создать переменную планирования списка (У каждого транспортного средства мог быть список путевых точек в качестве переменной планирования). Но, похоже, это еще не поддерживается?

Answer 1

В готовом примере VRP в примере с optaplanner это действительно не охватывается.

Типичный подход, который я часто вижу, состоит в том, чтобы выяснить «гранулярность спроса». Например, учитывая, что ваш самый маленький тип транспортного средства имеет вместимость 50, я, вероятно, попробую сначала с требованием зернистости 10. Таким образом, один клиент по запросу 90 разделяется на 9 посещений из 10. Один клиент по запросу 23 разделяется на 10, 10 и 3. Затем просто назначьте посещение транспортных средств, как в примере vrp в optaplanner-examples (посещение заменяет Customer на @PlanningEntity). Несколько советов:

• Также используйте перемещения subChainSwap и subChainChange (см. Раздел Выбор перемещений в главе документации).
• Если для одного посещения есть время обслуживания и только несколько посещений в одном и том же месте, то только при его использовании один раз, используйте шаблон проектирования "сворачивание" (не уверен, если он еще задокументирован), чтобы справиться с этим в ArrivalTimeUpdatingVariableListener.

Как только вы реализовали это и использовали optaplanner-benchmark для оценки его стоимости, затем попробуйте запросить гранулярность 15. Затем попробуйте запросить гранулярность 20 или 5. Вы торгуете потенциальным качеством решения в сравнении с производительностью и затраченным временем в тот момент. Посмотрите на графики BEST_SCORE, чтобы сравнить эффект гранулярности этих требований.