OptaPlanner CVRPTW - 容量问题的解决方案

我有以下CVRPTW问题，我试图找到OptaPlanner的一个很好的解决方案。时间是在hh：mm：ss格式。OptaPlanner CVRPTW - 容量问题的解决方案

我的DRL文件就像this。此外，我还定义了在准备时间之前与抵达有关的一个硬性限制。我的求解器配置是这样this，与终止标签的区别：

<termination> 
    <terminationCompositionStyle>OR</terminationCompositionStyle> 
    <maximumSecondsSpend>10</maximumSecondsSpend> 
    <scoreAttained>0hard/-750000soft</scoreAttained> 
</termination>

这是问题陈述：

PROBLEM STATEMENT: 
CustID ReadyTIME DueTIME  ServiceDUR DEMAND 
1  20:38:18 20:44:18 00:05:00 2 
2  20:20:53 20:26:53 00:05:00 4 
3  20:51:39 20:57:39 00:05:00 3 
4  20:20:18 20:26:18 00:05:00 6 
5  20:34:15 20:40:15 00:05:00 5 
6  20:21:40 20:27:40 00:05:00 10

我有2辆与既有的10个项目和1个油库容量。

这是溶液（客户通过车辆编组和由到达时间排序）：

Vehicle 1 Capacity 10 - from Depot [1] 
[6]  D: 10 Ar.T: 20:21:40 Prev.D: 00:02:21 Next.D: --:--:-- 

Vehicle 2 Capacity 10 - from Depot [1] 
[4]  D: 6 Ar.T: 20:20:18 Prev.D: 00:01:08 Next.D: 00:02:21 
[2]  D: 4 Ar.T: 20:27:42 Prev.D: 00:02:24 Next.D: 00:03:38 
[5]  D: 5 Ar.T: 20:36:03 Prev.D: 00:03:21 Next.D: 00:02:09 
[1]  D: 2 Ar.T: 20:43:26 Prev.D: 00:02:23 Next.D: 00:07:23 
[3]  D: 3 Ar.T: 20:55:40 Prev.D: 00:07:14 Next.D: --:--:--

（d =需求，Ar.T =到达时间，Prev.D =距离从先前的位置，下一步。 D距离下一个位置）

正如你所看到的车辆2必须运输6 + 4 + 5 + 2 + 3 = 20项，这大于容量。我不明白为什么解决者建议我这个解决方案，如果有一个硬配合相对容量的限制。

考虑到我的规则，这不是一个可接受的解决方案。我错过了什么吗？求解器没有提供解决方案吗？它是否考虑到“解决失败”终止？

来源

2013-10-08 user2664655

正确的，如果我错了，但你有：

的（6 + 4 + 5 + 2 + 3 + 10）中的总需求
总容量（2辆，每组10）

这是不可能的运30个项目时，你的车只能运输20项目。 没有可行的解决方案（因此OptaPlanner提供了它找到的最好的不可行解决方案）。

注意：如果同一车辆可以多次使用，则添加额外的Vehicle实例并添加一个约束来惩罚具有相同车牌的多个Vehicle实例的使用。

来源

2013-10-08 17:59:45

有趣的是，有时很容易证明不可行性（如在这个数据集中）。但通常不是（并且证明不可行性也是完整的）。例如，假设3辆需求（每辆需求6辆）和2辆车（两辆10辆）。即使'3 * 6 <2 * 10'，这是不可行的：没有车辆可以容纳多于一个物品，但是这里比车辆多一个物品。 –

我假设OptaPlanner允许多次使用同一辆车，所以这是一个错误的假设。您建议添加车辆实例，但新实例具有不同的ID，对吧？因此，为了考虑多种用途，我是否应该将问题模拟为拥有2辆以上的车辆？ – user2664655

是的，干净的方法是将'Vehicle'重命名为'VehicleTrip'，然后再次添加'Vehicle'（并将每个'VehicleTrip'链接到1'Vehicle。然后添加一个软约束来减少每辆车的次数（平方旅行的次数有帮助）。 –

OptaPlanner CVRPTW - 容量问题的解决方案

回答

相关问题