OptaPlanner CVRPTW - постоянные поставки
Я новичок в OptaPlanner и пытаюсь настроить его в своем проекте для решения проблемы CVRPTW. Моя текущая конфигурация очень похожа на пример, который вы можете найти в исходном коде проекта, но мои требования отличаются. Моя заявка постоянно получает запросы на доставку, где:
- Средняя продолжительность обслуживания 5 минут
- DueTime - ReadyTime = 10 минут
- Среднее расстояние (по времени) между локациями составляет около 2,5 минут
- Только 1 депо
Моя идея - перезапускать алгоритм решения каждый раз, когда поступает новый запрос. Это необходимо для меня, чтобы понять, выполним ли запрос или его нужно сдвинуть вперед или назад во времени. Если вы рассмотрите следующую формулировку проблемы (местоположения опущены, но довольно равноудалены от местоположения депо):
CUST_ID READY_TIME DUE_TIME SERV_DUR DEMAND
1 12:45:00 12:55:00 00:05:00 1
2 12:35:00 12:45:00 00:05:00 8
3 12:25:00 12:35:00 00:05:00 5
4 13:25:00 13:35:00 00:05:00 5
Учитывая, что доступно 2 автомобиля, каждый из которых может вместить до 10 человек, я получаю следующее решение (расписание для каждого автомобиля):
**Vehicle 1 Capacity 10 - delivery sequence starting from Depot [1]**
Cust[3] D: 5 Ar.T: 12:25:00 Ap.T: 12:23:08 Prev.D: 00:01:52 Next.D: 00:03:46
Cust[4] D: 5 Ar.T: 12:33:56 Ap.T: 12:30:00 Prev.D: 00:03:56 Next.D: --:--:--
**Vehicle 2 Capacity 10 - delivery sequence starting from Depot [1]**
Cust[2] D: 8 Ar.T: 12:35:00 Ap.T: 12:33:03 Prev.D: 00:01:57 Next.D: 00:03:05
Cust[1] D: 1 Ar.T: 12:42:47 Ap.T: 12:40:00 Prev.D: 00:02:47 Next.D: --:--:--
Где D - спрос, Ar.T - время прибытия, Ap.T - время приближения (время, когда необходимо покинуть предыдущее местоположение, чтобы прибыть пунктуально к выбранному), Prev.D - расстояние (во времени) от предыдущего местоположения и Next.D - расстояние (во времени) от следующего местоположения.
Как вы можете видеть, клиент 4 получает доставку слишком рано (время прибытия 12:33:56, а время готовности 13:25:00). Я понимаю, что правило прибытие BeforeReadyTime является дополнительным мягким ограничением, но я ожидаю, что планировщик предложит мне доставить клиенту 4 с использованием зарезервированной доставки. Установка правила прибытие BeforeReadyTime в качестве дополнительного жесткого ограничения, в большинстве случаев я получаю следующее исключение:
org.drools.core.RuntimeDroolsException: java.lang.NullPointerException
at org.drools.core.base.accumulators.SumAccumulateFunction.reverse(SumAccumulateFunction.java:85)
У меня есть 2 вопроса:
- Когда я получу исключение выше, я должен поймать его как "нерешенную проблему"? Или я должен настроить свою конфигурацию? Это то, что я не должен получить?
- Как мне управлять сценарием непрерывных поставок? Должен ли я определять разные большие временные окна для самостоятельного решения? Но как определить границы этих окон? А как управлять поставками, запланированными через границы? (мне кажется, это решение неверно)
РЕДАКТИРОВАТЬ 1:
Обновление версии OptaPlanner с 6.0.0.CR3 до 6.0.0.CR4-Pre1 решило исключение NullPointerException. Документация о планировании в реальном времени ясна, и я уже рассматривал возможность запуска моего планировщика в режиме реального времени. Но так как в приведенном выше примере результат был плохим, я пытался понять, что еще я мог сделать, чтобы справиться с этой ситуацией. Я перевел правило прибытие BeBeforeReadyTime с мягкого ограничения на жесткое, теперь я не получаю исключение NullPointerException, кажется, что расписание работает правильно, и в результате получается следующее (например):
ПОСТАНОВКА ЗАДАЧИ:
CUSTID RTIME DTIME SERVDUR DEMAND
1 12:45:00 12:55:00 00:05:00 5
2 12:35:00 12:45:00 00:05:00 3
3 12:25:00 12:35:00 00:05:00 10
4 14:25:00 14:35:00 00:05:00 2
РЕШЕНИЕ
**Vehicle 1 Capacity 10 - delivery sequence starting from Depot [1]**
Cust[3] D: 10 Ar.T: 12:25:00 Ap.T: 12:23:08 Prev.D: 00:01:52 Next.D: 00:02:26
Cust[2] D: 3 Ar.T: 12:32:26 Ap.T: 12:30:00 Prev.D: 00:02:26 Next.D: 00:03:05
Cust[1] D: 5 Ar.T: 12:42:47 Ap.T: 12:40:00 Prev.D: 00:02:47 Next.D: --:--:--
**Vehicle 2 Capacity 10 - delivery sequence starting from Depot [1]**
Cust[4] D: 2 Ar.T: 14:25:00 Ap.T: 14:22:53 Prev.D: 00:02:07 Next.D: --:--:--
Как видите, 1-я доставка невозможна, так как сумма требований превышает вместимость автомобиля. Должен ли я считать это правильным? Я имею в виду, что в этом случае хорошим решением было бы использование обоих транспортных средств для управления клиентами 1,2,3. Я использую ту же конфигурацию, что и в примере, с vehicleCapacity в качестве жесткого ограничения. Кроме того, клиенты 2 и 1 обслуживаются до времени готовности, даже если я использую жесткие ограничения для этого.
1 ответ
Если вы еще этого не сделали, сначала прочитайте документацию по повторному планированию в целом и, в частности, конкретно по планированию в реальном времени.
Вы можете попробовать планирование в реальном времени в демоверсии, щелкнув в любом месте на карте VRP во время ее решения.
Это исключение является ошибкой (в вашем или нашем коде). Это никогда не должно случиться. Прочитайте предупреждения в разделе документации, указанном выше. Если вы следовали им и считаете, что ошибки нет в вашем коде, пожалуйста, отправьте jira.
Дайте мне знать, если документы не дадут четкого ответа на этот вопрос.
PS: убедитесь, что вы используете 6.0.0.CR4. У Drools <= CR3 была ошибка, связанная с теневыми переменными во временных окнах VRP.