帶時間窗口的路線的總持續時間不是最佳的

我準備了一個說明問題的測試案例。的route包括三個要點：帶時間窗口的路線的總持續時間不是最佳的

1001 - depot. 
1002 - timewindow 10:00-15:00. 
1003 - timewindow 8:00-15:00.

我預計該航線將是1001-1003-1002，卻收到1001-1002-1003。

據我所知，軟分數限制不會優化停機時間間隔= readyTime - arrivalTime。

儘管總旅行時間最短（僅通過矩陣計算），但現在路線的總持續時間超過了可能。

我能以某種方式優化總路線持續時間嗎？在此先感謝。

VRP文件：

NAME: P1568C3-n3-k1 
COMMENT: P1568C3-n3-k1 
TYPE: CVRPTW 
DIMENSION: 3 
EDGE_WEIGHT_TYPE: EXPLICIT 
EDGE_WEIGHT_FORMAT: FULL_MATRIX 
EDGE_WEIGHT_UNIT_OF_MEASUREMENT: SEC 
CAPACITY: 4 
NODE_COORD_SECTION 
1001 52.086 23.687 address 
1002 52.089 23.71 address 
1003 52.095 23.742 address 
EDGE_WEIGHT_SECTION 
0 0.1675 0.4053 
0.1675 0 0.2378 
0.4893 0.3218 0 
DEMAND_SECTION 
1001 0 21600 54000 0 
1002 1 36000 54000 1800 
1003 1 28800 54000 1800 
DEPOT_SECTION 
1001 
-1 
EOF

結果XML：

<vehicleList id="11"> 
    <VrpVehicle id="12"> 
     <id>0</id> 
     <capacity>4</capacity> 
     <depot class="VrpTimeWindowedDepot" reference="10"/> 
     <nextCustomer class="VrpTimeWindowedCustomer" id="13"> 
     <id>1002</id> 
     <location class="VrpRoadLocation" reference="5"/> 
     <demand>1</demand> 
     <previousStandstill class="VrpVehicle" reference="12"/> 
     <nextCustomer class="VrpTimeWindowedCustomer" id="14"> 
      <id>1003</id> 
      <location class="VrpRoadLocation" reference="7"/> 
      <demand>1</demand> 
      <previousStandstill class="VrpTimeWindowedCustomer" reference="13"/> 
      <vehicle reference="12"/> 
      <readyTime>28800</readyTime> 
      <dueTime>54000</dueTime> 
      <serviceDuration>1800</serviceDuration> 
      <arrivalTime>38038</arrivalTime> 
     </nextCustomer> 
     <vehicle reference="12"/> 
     <readyTime>36000</readyTime> 
     <dueTime>54000</dueTime> 
     <serviceDuration>1800</serviceDuration> 
     <arrivalTime>36000</arrivalTime> 
     </nextCustomer> 
    </VrpVehicle> 
    </vehicleList>

來源

2016-10-04 Victor Kostomarov

在optaplanner-examples實施，這是繼學術論文的問題定義，將比分實現軟得分的道路上只是時間花。 當前的分數限制不包括在離開倉庫之前車輛丟失時間（如果有的話）的任何處罰。

你可以看到，在例如UI如果您在左下角點擊「約束匹配」：

-489驅動回車廠
-406：-168爲駕駛從倉庫到最近的客戶，-238到其他客戶。

因此，OptaPlanner確實會返回最優解，您只是有不同的問題定義。只需添加一個軟約束來懲罰倉庫的開放時間直到出發時間。

來源

2016-10-07 12:50:44

請注意，您的數據很奇怪，因爲從C驅動到A需要18％的時間，然後通過B驅動從A驅動到C。由於三角不等式（但在現實世界中可能），這不太可能。 –

我已經按照你的要求完成了工作，現在一切都按照我的問題定義工作。新的軟約束： '規則「depotOpeningTime」當 $客戶：TimeWindowedCustomer（previousStandstill = NULL，$ arrivalTime：arrivalTime！）不TimeWindowedCustomer（previousStandstill == $客戶）然後 scoreHolder.addSoftConstraintMatch（kcontext， - $ arrivalTime.longValue（））; end' 非常感謝！ @GeoffreyDeSmet –

帶時間窗口的路線的總持續時間不是最佳的

回答

相關問題