OptaPlanner/Timefold中VRP子行程固定的模型调整方案可行性问询

问题 #

我基于OptaPlanner/Timefold搭建了带取货（PICKUP）和退货（DROPOFF）的路径规划（VRP）模型，现有模型结构如下：

1. Vehicle作为PlanningEntity，包含LoadJob类型的PlanningListVariable列表tour：

@PlanningEntity
class Vehicle {
    @PlanningId lateinit var planningId: String

    @PlanningListVariable lateinit var tour: MutableList<LoadJob>
    
    // ...
} 

2. LoadJob同样是PlanningEntity，通过InverseRelationShadowVariable关联Vehicle，还包含位置、负载等属性及到达时间相关的影子变量与变量监听器：

@PlanningEntity
class LoadJob {
    @PlanningId lateinit var id: String

    @InverseRelationShadowVariable(sourceVariableName = "tour") //
    var vehicle: Vehicle? = null

    lateinit var location: Location
        private set

    lateinit var load: Load
        private set

    // ... 更多到达时间相关的影子变量和变量监听器
}

当前模型已支持单车辆多子行程（通过检测PlanningListVariable中的循环实现），现在需要支持用户固定车辆上的子行程。已知PlanningListVariable暂不支持变量固定，重构为链式规划变量成本较高，因此考虑调整模型：

• 将Vehicle改为ProblemFact
• 新增Tour作为PlanningEntity，包含PlanningListVariable列表tour、时间约束（earliestStart、latestEnd）及Vehicle引用：

@PlanningEntity
class Tour {
    @PlanningId lateinit var planningId: String

    @PlanningListVariable lateinit var tour: MutableList<LoadJob>

    lateinit var earliestStart: OffsetDateTime

    lateinit var latestEnd: OffsetDateTime

    lateinit var vehicle: Vehicle
    
    // ...
} 

计划通过约束确保Tour的时间限制被遵守，在转换/持久化层处理锁定行程的增删、预留对应时间段。

核心问题 #

该方案是否有效？OptaPlanner/Timefold能否支持此模型？

后续问题 #

1. 若方案无效，更优方案是什么？
2. 若方案有效，是否有更便捷的方式分组同一车辆的所有行程？是否采用约束流的groupBy方法？

回答 #

核心方案有效性判断 #

这个方案完全有效，OptaPlanner/Timefold完全支持该模型：

• 将Vehicle改为ProblemFact合理，因为它属于固定的问题输入属性，无需作为规划实体参与变量调整
• Tour作为PlanningEntity承载PlanningListVariable，符合框架对列表变量的使用规范，框架会正确处理列表内LoadJob的排序、分配逻辑
• 通过约束保证Tour的时间窗口，结合转换层处理锁定行程的逻辑，可实现用户固定子行程的需求：初始化问题时，为锁定子行程创建对应的Tour实例，设置固定的tour列表、时间窗口和关联车辆；同时可给锁定Tour添加不可变标记，通过硬约束强制其tour列表不被规划器修改。

后续问题解答 #

1. 若方案无效的替代方案
   若因特殊场景该方案不适用，有两种低成本替代方案：

   • 自定义变量固定逻辑：在LoadJob的变量监听器中，对锁定子行程相关的LoadJob，强制其归属的Vehicle和在tour中的位置不变。但需手动处理冲突，复杂度较高。
   • 使用规划固定标记：将锁定的子行程预先分配到车辆的tour中作为初始解的固定部分，通过@PlanningPin标记这些LoadJob（Timefold 1.0+、OptaPlanner 8.28+已支持列表变量的固定标记），禁止规划器移动它们。

2. 同一车辆行程分组的便捷方式
   当方案有效时，约束流的groupBy是最便捷的分组方式：

   • 可直接通过约束流按Tour的vehicle属性分组，获取同一车辆的所有Tour实例，进而处理跨Tour的约束（如车辆总负载、行程时间不重叠等）。
   • 示例约束流伪代码：

     constraintFactory.from(Tour::class.java)
         .groupBy(Tour::vehicle, sum(Tour::totalLoad))
         .filter { vehicle, totalLoad -> totalLoad > vehicle.maxLoad }
         .penalize("Vehicle overload", HardSoftScore.ONE_HARD)
     

   • 若仅需在初始化或结果处理时分组，也可直接用集合API（如tourList.groupBy { it.vehicle }），但约束流方式更适合规划过程中实时校验跨行程规则。

内容的提问来源于stack exchange，提问作者greyhairredbear