or-tools中服务节点条件分配问题：仅行程超阈值时分配

你的实现存在4个核心问题：

• 笔误：代码中ourDurationVar未定义，实际应为之前声明的tourDurationVar，属于直接导致约束不生效的低级问题。
• 循环依赖：你用包含服务节点耗时的总行程时长作为触发条件，会出现死锁：不分配服务节点时总时长低于阈值，无需分配；分配后总时长达标，符合分配要求，但求解器不会主动探索这种需要先假设节点激活才能满足触发条件的场景。
• 可选节点无分配动力：你给服务节点的disjunction设置惩罚为0，不分配没有任何成本，求解器会优先选择不分配节点的可行解，规避需要额外添加节点的场景。
• 缺少节点与车辆的绑定规则：你没有限制服务节点的可分配车辆，求解器可能将其分配给其他车辆，导致对应车辆的约束永远无法触发。

步骤1：绑定服务节点到指定车辆 #

提前限制该服务节点仅允许分配给对应的目标车辆，避免跨车分配：

// 限制服务节点只能分配给指定vehicleId
routingModel.setVehicleAllowedForIndex(orToolsIndexForServiceNode, listOf(vehicleId).toIntArray())

步骤2：使用大M法重构约束，消除循环依赖 #

你可以根据业务对「总行程时长是否包含服务节点耗时」的定义选择对应逻辑，以下为触发阈值不含服务节点耗时的实现（推荐，可彻底避免死锁，只要车辆原有取派任务时长达标就必须分配服务节点）：

val cumulVarAtVehicleStartNode: IntVar = journeyDurationsDimension.cumulVar(routingIndexManager.getStartIndex(vehicleId))
val tourDurationMaxVar: IntVar = journeyDurationsDimension.cumulVar(routingIndexManager.getEndIndex(vehicleId))
val tourDurationVar = solver.makeDifference(tourDurationMaxVar, cumulVarAtVehicleStartNode).`var`()

val thresholdInHours = 5
val thresholdSec = thresholdInHours * 60 * 60
// 大M取值大于所有可能的最大行程时长即可，这里设为24小时的秒数
val M = 24 * 60 * 60

// 服务节点允许不分配，设置极小的分配惩罚引导求解器优先满足分配条件
routingModel.addDisjunction(listOf(orToolsIndexForServiceNode).toLongArray(), 1)
val isServiceNodeActiveVar = routingModel.activeVar(orToolsIndexForServiceNode)
val solver = routingModel.solver()

// 约束1：如果服务节点未分配，那么总行程时长必须小于阈值
solver.addConstraint(
    solver.makeLessOrEqual(
        tourDurationVar,
        solver.makeSum(thresholdSec - 1, solver.makeProduct(M, isServiceNodeActiveVar)).`var`()
    )
)

// 约束2：如果服务节点已分配，那么总行程时长必须大于等于阈值
solver.addConstraint(
    solver.makeGreaterOrEqual(
        tourDurationVar,
        solver.makeDifference(thresholdSec, solver.makeProduct(M, solver.makeDifference(1, isServiceNodeActiveVar).`var`())).`var`()
    )
)

步骤3：调整搜索策略（可选） #

如果求解器仍然优先跳过服务节点，可以调整首次解策略为PARALLEL_CHEAPEST_INSERTION，让求解器在生成初始解时优先尝试插入可选节点：

val searchParams = RoutingSearchParameters.newBuilder()
    .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PARALLEL_CHEAPEST_INSERTION)
    .build()
routingModel.solveWithParameters(searchParams)

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