带时间窗口的路线的总持续时间不是最佳的

我准备了一个说明问题的测试案例。的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 –

带时间窗口的路线的总持续时间不是最佳的

回答

相关问题