java - Optaplanner - CVRP - 中途返回仓库

Question

我的问题是 Capacitated Vehicle Routing Problem (CVRP) 的修改最终也将包括时间窗口。

由于时间窗口已经内置在示例中，所以对我来说弄清楚它们应该不会太难。但是，我需要更改 CVRP 示例的核心约束之一，但我不知道如何做到这一点。

我的模型

在我尝试建模的系统中，车辆可以离开其仓库，前往多个不同的客户，然后加载在 Material 上。然而，我的模型与示例的不同之处在于，Vehicle 可以访问任何Depot 中链来存放其当前负载。

问题

我一直在查看 documentation试图找出如何做到这一点，到目前为止我的基本理解是我必须更改 Depot 的定义(也许通过实现 Standstill)才能成为车辆访问地点链的一部分，和/或可能只是将 Depot 集成到 Customer 中，并具有某种特殊规则，即访问 Depot 清空车辆而不是增加需求。

我也一直在研究影子变量和变量监听器，但我不知道这是否是正确的方法。这一切都有点令人困惑。

任何人都可以提供一些提示或建议，或者在我把自己挖得太深之前指出正确的方向，从哪里开始？

Answer 1

根据 Geoffrey 的建议，将您的 Vehicle 重命名为类(class) VehicleTrip并通过给它一个值 previousVehicleTrip 让它指向上一个和下一个行程和nextVehicleTrip ，并为其指定一个变量开始时间和结束时间(Kotlin 中的代码示例):

class VehicleTrip(
    ...,
    var startTime: LocalDateTime? = null,
    var endTime: LocalDateTime? = null,
    val previousVehicleTrip?: VehicleTrip = null,
    val nextVehicleTrip?: VehicleTrip = null
) : Standstill {
    ...
}

您可以在启动 VehicleTrips 时设置这些值。当你得到 StackOverFlowError基于VehicleTrip.hashCode() ，只需覆盖 hashCode() VehicleTrip的功能类(class)。 (也许有人有更好的建议来处理这个问题？)

更新影子变量。

在您的 Customer 中类，你应该有一个变量 arrivalTime (就像在 CVRPTW 示例中一样)这是一个自定义影子变量。在此变量的监听器类中，您通常只更新车辆到达客户的时间，以及此行程中下一个客户的到达时间。现在，您还需要更新当前客户所在行程之后的所有行程时间。

例如，您可能有两次行程 VT1和VT2 ，和三个客户C1 , C2 ，和C3 。当更改为

VT1 - C1 - VT2 - C2 - C3

到

VT1 - C2 - C1 - VT2 - C3

您想要更新的内容是(按顺序)

1. C2.arrivalTime
2. C1.arrivalTime
3. VT1.endTime
4. VT2.startTime
5. C3.arrivalTime
6. VT2.endTime

请注意，在 TimeWindowedCustomer 中例如，变量监听器只执行步骤 1. 和 2.，因此我们必须添加步骤 3. 到 6.

为此，请首先添加 @CustomShadowVariable VehicleTrip 的开始和结束时间的注释(并且不要忘记将 VehicleTrip 标记为计划实体)，它使用与时间窗口客户相同的变量监听器类:

class VehicleTrip(
   ...,
   @CustomShadowVariable(
        variableListenerRef = PlanningVariableReference(
            entityClass = TimeWindowedCustomer::class, 
            variableName = "arrivalTime"
        ))
   var startTime: LocalDateTime? = null,
   ...
) : Standstill {
    ...
}

现在在ArrivalTimeUpdatingVariableListener类中，您可以添加步骤 3. 到 6.，类似于步骤 1. 和 2. 的实现方式。确保保持更新这些变量的顺序，并通知 ScoreDirector使用 beforeVariableChanged() 更改变量时和afterVariableChanged()方法。