Google OR-Tools 中实现节点位置依赖的动态路径成本建模

本文介绍如何在 or-tools 的 vrp 求解器中建模「同一节点在路径中不同位置（中间 or 终点）具有不同成本」的场景，通过节点复制、活动变量约束与惩罚型 disjunction 技术实现动态成本嵌入。

在标准车辆路径问题（VRP）中，节点成本通常被建模为边权重（如 distance_matrix[i][j]）或固定服务成本，但 google OR-Tools 原生不支持「节点成本随其在路径中的逻辑位置（如是否为最后一个非仓库节点）动态变化」的直接表达。上述问题中，每个客户节点 i 有两个成本：part（作为中间节点时的开销）和 final（作为该车辆路径的最终客户时的开销），而仓库（depot）始终为起点和终点（索引 0）。目标是最小化路径中所有“被访问且承担对应角色”的节点成本之和。

核心思路是将语义上“一个节点两种角色”转化为物理上“两个独立节点”，再通过求解器约束强制互斥选择与角色绑定：

✅ 实现步骤详解

1. 节点复制（node Duplication）
   对每个客户节点 i ∈ {1, 2, …, n}，创建两个索引：

   • regular_i：代表“作为中间节点出现”（即路径中非末尾客户）
   • final_i：代表“作为该车辆路径最后一个客户出现”

   Depot（索引 0）保持唯一，但需特殊处理：它既是起点，也作为每条路径的显式终点（0 → … → final_i → 0），但 final_i → 0 这段弧的成本设为 0，不计入目标函数。

2. 约束节点后继关系（NextVar Control）
   使用 routing.NextVar(index) 显式限制每个节点的合法后继：

   • regular_i 的后继只能是其他 regular_j 或 final_j（不能是 depot），确保它不会成为路径终点；
   • final_i 的后继只能是 depot（0）或 -1（表示被丢弃），即：routing.AddToAssignment(routing.NextVar(final_i) == 0) 或通过 AllowedValues 限定。

3. 互斥访问约束（Disjunction / ActiveVar Sum）
   防止同一客户被重复访问（如既选 regular_1 又选 final_1）：

   # 确保 regular_i 和 final_i 至多被激活一个 routing.AddVariableMinimizedByFinalizer(routing.ActiveVar(regular_i)) routing.AddVariableMinimizedByFinalizer(routing.ActiveVar(final_i)) routing.solver().Add(     routing.ActiveVar(regular_i) + routing.ActiveVar(final_i) <= 1 )

4. 动态成本嵌入（Penalty-based Objective）
   利用 AddDisjunction() 引入软约束，将“未被选中”转化为目标函数中的显式惩罚：

   • 对 regular_i：若未被激活（即未作为中间节点使用），则需支付 part[i] 成本（因客户必须被服务，未被中间服务就只能由 final 承担）→ 但更合理的是：对 final_i 设置 part[i] 的惩罚，表示“若不选 final_i，则必须以 part 方式服务，但此时它无法成为终点” —— 实际建模中，我们反向设计：
     • 为 final_i 添加 disjunction，惩罚值为 part[i]：若 final_i 被丢弃（ActiveVar=0），则加罚 part[i]（意味着该客户只能以“中间”方式服务，但需保证其确实在某路径中）；
     • 为 regular_i 添加 disjunction，惩罚值为 final[i]：若 regular_i 被丢弃，加罚 final[i]（意味着它必须作为终点被服务）。
   • 最终目标函数 = 所有被激活节点的 part/final 成本之和 + 所有触发的惩罚项。

5. Depot 处理技巧
   将 depot（0）同时设为 Start 和 End：

   for vehicle_id in range(num_vehicles):     routing.Start(vehicle_id)  # = 0     routing.End(vehicle_id)    # = 0

   并设置 distance_callback(i, 0) = 0 对所有客户 i，使 final_i → 0 不增加成本，仅用于拓扑闭合。

? 示例代码片段（python + OR-Tools）

from ortools.constraint_solver import pywrapcp, routing_enums_pb2  # 假设 costs = [{"part":0,"final":0}, {"part":2,"final":3}, ...] n = len(costs) - 1  # 客户数（不含 depot 0）  # 创建路由模型 manager = pywrapcp.RoutingIndexManager(n * 2 + 1, num_vehicles, 0, 0) routing = pywrapcp.RoutingModel(manager)  # 定义回调：distance from i to j (0 for any -> depot) def distance_callback(from_index, to_index):     from_node = manager.IndexToNode(from_index)     to_node = manager.IndexToNode(to_index)     if to_node == 0:  # depot         return 0     # 实现客户间距离逻辑（此处简化为 0，重点在 node cost）     return 0  transit_callback_index = routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)  # --- 关键：添加 dynamic node cost via penalties --- for i in range(1, n + 1):     regular_idx = manager.NodeToIndex(i)           # original node i     final_idx   = manager.NodeToIndex(i + n)       # duplicated final node      # 1. 互斥：regular_i 和 final_i 至多一个 active     routing.solver().Add(         routing.ActiveVar(regular_idx) + routing.ActiveVar(final_idx) <= 1     )      # 2. 约束 next：regular_i 不能指向 depot；final_i 只能指向 depot     routing.AddToAssignment(routing.NextVar(regular_idx) != 0)     routing.AddToAssignment(routing.NextVar(final_idx) == 0)      # 3. Disjunction penalties     # 若 final_i 未被选，则罚 part[i]（客户需以 part 方式服务）     routing.AddDisjunction([final_idx], costs[i]["part"], 1)     # 若 regular_i 未被选，则罚 final[i]（客户需以 final 方式服务）     routing.AddDisjunction([regular_idx], costs[i]["final"], 1)  # 求解... search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = (     routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) solution = routing.SolveWithParameters(search_parameters)

⚠️ 注意事项与最佳实践

• 索引管理务必清晰：建议用字典映射逻辑节点 i 到 regular_idx / final_idx，避免硬编码错误；
• 惩罚值需足够大：AddDisjunction(penalty) 中的 penalty 应显著大于任何可行路径成本差异，否则求解器可能“故意丢弃节点”来降低总成本（违背服务全覆盖前提）；
• 验证路径结构：解析解时，需识别 final_i 是否被激活，并确认其前驱是否为 regular_j 或其他 final_k（实际应只接 regular 或起始 depot）；
• 性能考量：节点数量翻倍会增加搜索空间，对大规模实例建议结合 LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH 提升鲁棒性。

该方法虽引入额外变量，但完全兼容 OR-Tools 的 CP-SAT 与 RoutingModel 架构，是解决“位置敏感节点成本”问题的成熟工程实践。完整可运行示例见官方 Gist：https://www.php.cn/link/d42e8faa72ba342df9147902bebb0aac。