路线的总持续时间 windows 不是最优的

Question

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

Answer 1

在optaplanner-examples实现中，按照学术论文的问题定义，分数实现软分数只是花在路上的时间。 当前的分数限制不包括车辆在离开站点之前的损失时间（如果有）的任何惩罚。

您可以在示例中看到 UI 如果您单击左下角的按钮 "constraint matches":

-489 回车厂
-406：-168 用于从仓库开往最近的客户，-238 用于开往其他客户。

所以 OptaPlanner 做了 return 最优解， 你只是有一个不同的问题定义。只需添加一个软约束来惩罚站点的开放时间到出发时间。

路线的总持续时间 windows 不是最优的

Total duration of the route with time windows is not optimal

optaplanner