Пример Optaplanner VRP, несколько транспортных средств требуется на одну остановку в одном временном окне

Question

Мы используем настраиваемый учебный пример VRP , чтобы оптимизировать ежедневные маршруты для сервисных инженеров, которые едут к клиентам, чтобы выполнить определенные задачи по ремонту и установке. У нас есть время windows, и мы оптимизируем более 1000 задач на несколько недель в будущем.

Наша (упрощенная) модель предметной области состоит из:

• Инженер - парень, выполняющий всю работу
• Задание - одно рабочее задание в определенном месте
• DailyRoute - маршрут Инженера на данный день, состоит из связанного списка задач

---

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

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

Пока что мы пришли со следующими идеями:

• Разрешить одиночное задание перемещается только в DailyRoute в в тот же день , как и маршрут, назначенный другим заданием
  • может быть сделано с помощью SelectionFilter
• Используйте CompositeMoves для одновременного перемещения обеих параллельных задач на разные дни
  • Нужен ли нам собственный MoveIteratorFactory для выбора подключенных задач?
  • Или это можно сделать с помощью CartesianProductMoveSelector вместо этого?
  • Можем ли мы использовать соседний выбор для второго перемещения, предпочитая тот же день, что и первый назначенный день первого хода (уже сделан ли ход в то время)?

Answer 1

Для двух инженеров, работающих параллельно над одной и той же задачей, см. Документы «Шаблоны проектирования», в частности «Задержка до последнего шаблона». Там нет примера, но наши службы поддержки помогли реализовать его несколько раз - он работает.

Для нескольких остановок в одном и том же месте: я видел, как пользователи разбивали такие посещения на более мелкие части, чтобы позволить optaplanner чтобы выбрать, какие из этих частей для агрегирования. Это работает, но не идеально: чем более мелкозернистые фрагменты, тем больше пространство поиска - тем более может помочь добавление нестандартного перемещения, которое фокусируется на объединении всех фрагментов (но я не буду начинать с этого). Вообще говоря: если наименьшее транспортное средство имеет вместимость 100, я бы провел несколько экспериментов с разделением до половины этой емкости - и они тоже попробовали четверть, просто чтобы посмотреть, что лучше всего работает с помощью optaplanner-benchmark.