本文介绍如何在 or-tools 的 vrp 求解器中建模「同一节点在路径中不同位置（中间 or 终点）具有不同成本」的场景，通过节点复制、活动变量约束与惩罚型 disjunction 技术实现动态成本嵌入。
在标准车辆路径问题（VRP）中，节点成本通常被建模为边权重（如 distance_matrix[i][j]）或固定服务成本，但 Google OR-Tools 原生不支持「节点成本随其在路径中的逻辑位置（如是否为最后一个非仓库节点）动态变化」的直接表达。上述问题中，每个客户节点 i 有两个成本：part（作为中间节点时的开销）和 final（作为该车辆路径的最终客户时的开销），而仓库（depot）始终为起点和终点（索引 0）。目标是最小化路径中所有“被访问且承担对应角色”的节点成本之和。
核心思路是将语义上“一个节点两种角色”转化为物理上“两个独立节点”，再通过求解器约束强制互斥选择与角色绑定：
✅ 实现步骤详解
-
节点复制（Node Duplication）
对每个客户节点 i ∈ {1, 2, ..., n}，创建两个索引：- regular_i：代表“作为中间节点出现”（即路径中非末尾客户）
- final_i：代表“作为该车辆路径最后一个客户出现”
Depot（索引 0）保持唯一，但需特殊处理：它既是起点，也作为每条路径的显式终点（0 → ... → final_i → 0），但 final_i → 0 这段弧的成本设为 0，不计入目标函数。
-
约束节点后继关系（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 限定。
-
互斥访问约束（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 ) -
动态成本嵌入（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 成本之和 + 所有触发的惩罚项。
- 对 regular_i：若未被激活（即未作为中间节点使用），则需支付 part[i] 成本（因客户必须被服务，未被中间服务就只能由 final 承担）→ 但更合理的是：对 final_i 设置 part[i] 的惩罚，表示“若不选 final_i，则必须以 part 方式服务，但此时它无法成为终点” —— 实际建模中，我们反向设计：
-
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。
