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 - 容量問題的解決方案

回答

相關問題