OR-Tools中VRPTW场景下如何构建最少车辆使用约束？

环境 #

• Python 3.6
• OR-Tools 9.3.10497

业务场景 #

存在普通节点与特殊节点两类节点：

• 若车辆仅途经特殊节点或未途经任何节点，视为未被使用
• 车辆一旦途经普通节点，标记为已使用（仅计数一次）

示例数据 #

nodes = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]
norm_nodes = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
spec_nodes = [15,16,17]
depot_no = 18
vehicles = [0,1,2]

额外约束 #

• 节点15仅允许车辆0通行
• 节点16仅允许车辆1通行
• 节点17仅允许车辆2通行

尝试的约束实现代码 #

def vehicles_used_callback(from_index, to_index):
    from_no = manager.IndexToNode(from_index)
    to_no = manager.IndexToNode(to_index)
    if from_no in norm_nodes:
        vehicles_used_dimension.CumulVar(from_index).SetValue(0)
        return 1
    return 0

vehicles_used_callback_index = routing.RegisterTransitCallback(vehicles_used_callback)
routing.AddDimension(vehicles_used_callback_index, 0, 999999999, True, "vehicles_used")
vehicles_used_dimension = routing.GetDimensionOrDie("vehicles_used")

for vehicle_index, vehicle_no in enumerate(vehicles):
    index = routing.End(vehicle_index)
    vehicles_used_dimension.SetCumulVarSoftUpperBound(index, 0, 1)

问题现象 #

约束未生效，解决方案仅为每辆车分配1个普通节点+专属特殊节点，其余普通节点全部被丢弃，目标值异常：

assigned_vehicles:
{
    0: [0,15],
    1: [1,16],
    2: [2,17]
}

dropped_nodes:
[3,4,5,6,7,8,9,10,11,12,13,14]

solution.ObjectiveValue()
1200000003

问题分析与解决方案 #

原代码核心问题 #

1. 回调函数中直接调用vehicles_used_dimension.CumulVar(from_index).SetValue(0)违反OR-Tools规则——回调仅用于返回维度增量，不能直接修改变量值，变量状态由求解器自行维护。
2. 软上限约束SetCumulVarSoftUpperBound逻辑完全倒置：业务允许车辆被使用，该约束却惩罚车辆被使用的情况，导致求解器尽量少分配普通节点。

正确实现方式 #

方式1：用0-1维度标记车辆使用状态

定义维度，车辆途经普通节点时维度值从0变为1并保持不变，结合目标函数控制已使用车辆数：

def vehicle_used_callback(from_index, to_index):
    from_no = manager.IndexToNode(from_index)
    # 途经普通节点时返回增量1，否则返回0
    return 1 if from_no in norm_nodes else 0

# 注册回调并添加维度：初始值0，最大累积值1（确保仅计数一次）
vehicle_used_dim_idx = routing.RegisterTransitCallback(vehicle_used_callback)
routing.AddDimension(
    vehicle_used_dim_idx,
    0,
    1,
    True,  # 强制维度非递减，确保标记后状态不回退
    "vehicle_used"
)
vehicle_used_dim = routing.GetDimensionOrDie("vehicle_used")

# 给已使用的车辆添加固定成本，驱动求解器尽量减少已使用车辆数
for vehicle_idx in range(len(vehicles)):
    end_idx = routing.End(vehicle_idx)
    vehicle_used_dim.SetCumulVarSoftLowerBound(end_idx, 1, 1000)  # 1000为使用车辆的成本，可按需调整

方式2：用布尔变量直接跟踪车辆状态

通过routing.ActiveVar判断车辆是否访问普通节点，创建显式约束：

for vehicle_idx in range(len(vehicles)):
    # 创建布尔变量表示车辆是否被使用
    is_used = solver.BoolVar(f"vehicle_{vehicle_idx}_used")
    # 约束：只要车辆访问任意普通节点，标记为已使用
    for node in norm_nodes:
        node_idx = manager.NodeToIndex(node)
        solver.Add(is_used >= routing.ActiveVar(node_idx))
    # 将使用车辆的成本加入目标函数，最小化已使用车辆数
    solver.Minimize(solver.Sum(is_used) * 1000)

补充优化：确保普通节点不被丢弃 #

若业务要求所有普通节点必须被访问，需给节点设置高丢弃惩罚，避免求解器丢弃节点：

for node in norm_nodes:
    node_idx = manager.NodeToIndex(node)
    routing.AddDisjunction([node_idx], 100000)  # 惩罚值需大于路径成本，确保优先访问节点

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