java - OptaPlanner CVRPTW - 持续交付

Question

我是 OptaPlanner 的新手，我正在尝试在我的项目中配置它来解决 CVRPTW 问题。我当前的配置与您可以在项目源代码中找到的示例非常相似，但我的要求不同。我的应用程序不断收到交付请求，其中:

• 平均服务时长为 5 分钟
• 到期时间 - 准备时间 = 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)。我知道规则 arrivalBeforeReadyTime 是一个额外的软约束，但我希望计划人员建议我使用预留交付方式向客户 4 交付。将规则 arrivalBeforeReadyTime 设置为额外的硬约束，大多数时候我会遇到以下异常:

org.drools.core.RuntimeDroolsException: java.lang.NullPointerException
    at org.drools.core.base.accumulators.SumAccumulateFunction.reverse(SumAccumulateFunction.java:85)

我有 2 个问题:

1. 当我收到上述异常时，我是否应该将其捕获为“问题未解决”？或者我必须调整我的配置吗？这是我不应该得到的东西吗？
2. 我应该如何管理持续交付场景？我是否应该定义不同的大时间窗口来独立求解？但如何定义这些窗口的边界呢？以及如何管理跨界计划的交付？ (这个解决方案对我来说似乎不正确)

编辑1:

将 OptaPlanner 版本从 6.0.0.CR3 更新到 6.0.0.CR4-Pre1 解决了 NullPointerException。该文档清楚地说明了实时规划，我已经在考虑以实时模式运行我的规划器。但由于在上面的例子中结果并不好，我试图了解我还可以做些什么来处理这种情况。我将规则 arrivalBeforeReadyTime 从软约束切换为硬约束，现在我没有得到 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、2、3。我使用与示例相同的配置，并将vehicleCapacity 作为硬约束。此外，如果我对其使用硬约束，客户 2 和 1 也会在准备时间之前得到服务。

Answer 1

如果您还没有阅读过 repeated planning 上的文档，请先阅读一般而言，更具体地讲 real-time planning具体来说。

您可以在演示中尝试实时规划，方法是在求解时单击 VRP map 上的任意位置。

1. 该异常是一个错误(在您的代码或我们的代码中)。它永远不应该发生。阅读上面引用的文档部分中的警告。如果您按照这些操作，并且相信该错误不在您的代码中，那么请file a jira .

2. 如果文档没有清楚地回答这个问题，请告诉我。

PS:确保您使用的是 6.0.0.CR4。 Drools <= CR3 有一个与 VRP 时间窗口中的阴影变量相关的错误。