本文介绍如何在 google or-tools 中为同一节点设置基于其在路径中位置（中间节点 or 终点）的不同成本，通过节点复制、活性约束与惩罚型不相容约束（disjunction）构建动态目标函数。
在标准车辆路径问题（VRP）建模中，节点成本通常被定义为静态值（如访问成本、服务时间或固定费用），但实际业务场景中，节点的代价可能取决于它在路径中的角色：例如，某客户若作为中途停靠点（part of route），仅产生装卸准备成本；而若作为该车次的终点（final destination），则需额外支付返程调度、结算或清场成本。Google OR-Tools 的 RoutingModel 默认不支持“位置感知”的动态节点成本，因其目标函数基于弧（arc）而非节点状态建模。但可通过建模技巧巧妙实现——核心思想是：将每个业务节点拆分为两个逻辑节点：node_part（仅允许出现在路径中间）和 node_final（仅允许作为路径终点），再通过约束与惩罚机制引导求解器选择最经济的定位方式。
✅ 实现步骤详解
-
节点复制与角色划分
对原始节点 i（i ≥ 1），创建两个索引：- i_part：代表“作为中间节点访问”，禁止连接至车辆终点（NextVar(i_part) ≠ vehicle_end）；
- i_final：代表“作为终点访问”，只允许后继为 vehicle_end（即 NextVar(i_final) == vehicle_end）。
-
强制互斥访问（One-or-None）
使用 AddDisjunction() 或显式约束确保二者至多被访问一个：# 方式1：使用 Disjunction（推荐） routing.AddDisjunction([index_part, index_final], penalty=0) # 方式2：硬约束（更严格） routing.solver().Add( routing.ActiveVar(index_part) + routing.ActiveVar(index_final) <= 1 ) -
嵌入位置敏感成本到目标函数
- 若 i_part 被跳过（未访问），则施加惩罚 costs[i]["final"]（即本应以终点身份服务，却未服务 → 损失机会成本）；
- 若 i_final 被跳过，则施加惩罚 costs[i]["part"]（即本可低成本中途服务，却放弃 → 承担最低服务成本）。
这种设计将“未选最优角色”的隐性代价显式引入目标函数，驱动求解器自动权衡。
-
处理仓库（depot）的特殊性
将 depot（节点 0）同时设为起点与终点，但设置所有 node → 0 弧的成本为 0：# 构建距离/成本矩阵时： for i in range(num_nodes): distance_matrix[i][0] = 0 # depot is free exit这样，每条路径自然以 → 0 结束，且 i_final 可安全连接至 vehicle_end（即 depot 的结束索引），而不增加额外成本。
? 示例代码片段（Python + OR-Tools v9+）
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
# 假设 costs = [{"part":0,"final":0}, {"part":2,"final":3}, ...]
num_customers = len(costs) - 1 # 排除 depot 0
manager = pywrapcp.RoutingIndexManager(
1 + 2 * num_customers, # depot + 2*customer nodes
num_vehicles=1,
depot=0
)
routing = pywrapcp.RoutingModel(manager)
# 定义 cost callback（含动态逻辑）
def cost_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
if from_node == 0 and to_node == 0: # depot->depot: invalid
return 0
if to_node == 0: # any node -> depot: free
return 0
# 解析 part/final 节点：node_id = (raw_id - 1) // 2 + 1
if from_node > 0:
raw_id = (from_node - 1) // 2 + 1
is_final = (from_node - 1) % 2 == 1 # odd index => _final
if is_final:
return costs[raw_id]["final"]
else:
return costs[raw_id]["part"]
return 0
transit_callback_index = routing.RegisterTransitCallback(cost_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# 添加 disjunction 惩罚（关键！）
for i in range(1, num_customers + 1):
idx_part = manager.NodeToIndex(2 * i - 1) # 1→1, 2→3, 3→5...
idx_final = manager.NodeToIndex(2 * i) # 1→2, 2→4, 3→6...
# 若跳过 part 节点，罚 final 成本；跳过 final 节点，罚 part 成本
routing.AddDisjunction([idx_part], penalty=costs[i]["final"])
routing.AddDisjunction([idx_final], penalty=costs[i]["part"])
# 求解
search_params = pywrapcp.DefaultRoutingSearchParameters()
search_params.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)
solution = routing.SolveWithParameters(search_params)⚠️ 注意事项与最佳实践
- 索引管理务必严谨：建议用字典映射 {"part": idx, "final": idx} 避免计算错误；
- 惩罚值需大于最大可能路径成本：否则求解器可能倾向全跳过节点，导致不可行解；
- 性能权衡：节点数量翻倍会增加搜索空间，对大规模实例建议启用 local_search_metaheuristic；
- 结果解析：遍历路径时需识别 idx_final（偶数索引）来判断哪个节点是终点，从而正确累加 "final" 成本。
该方法已在 Mizux 的官方 Gist 中完整实现，支持多车、容量约束与时间窗扩展。掌握此模式后，你可进一步建模如“首单免运费”“末单赠券”等营销策略驱动的动态成本逻辑。
