本文详解如何在 or-tools 的 vrp 求解器中为同一节点赋予“中途访问”与“终点访问”两种不同成本，通过节点复制、活动变量约束与惩罚型 disjunction 技巧实现位置感知的成本建模。
在标准车辆路径问题（VRP）中，节点成本通常是静态的——即无论该节点出现在路径中间还是末尾，其服务成本恒定。但现实中，许多场景要求成本依赖于节点在路径中的逻辑角色：例如，将货物运至中转站（中途节点）成本较低，而作为最终交付点（终点节点）则需额外装卸或结算开销。Google OR-Tools 原生不支持“位置敏感”的节点成本，但可通过建模技巧优雅实现。
核心思路是：将每个业务节点拆分为两个逻辑实体——part_node（可出现在路径中段）和 final_node（仅允许作为路径终点），并利用求解器的 ActiveVar、NextVar 和 Disjunction 机制协同约束其行为。
✅ 关键建模步骤
-
节点复制与索引映射
对原始节点 i（i ≥ 1），创建两个对应索引：- part_i：表示节点 i 以“中途角色”被访问（成本为 costs[i]["part"]）
- final_i：表示节点 i 以“终点角色”被访问（成本为 costs[i]["final"]）
同时，保留 depot（节点 0）作为所有路径的起点与隐式终点（注意：其 NextVar 可指向自身，但弧成本设为 0，不计入目标函数）。
-
强制位置语义约束
- 对每个 part_i：禁用其 NextVar 指向任何 final_j 或 End —— 即 part_i 后必须接另一个 part_j 或 depot，确保它不会成为终点。
- 对每个 final_i：将其 NextVar 仅允许指向 End（车辆终点）或 depot（0），且设置 routing.NextVar(final_i) == routing.End(vehicle)（或等价约束），保证其必为路径最后一站。
-
互斥访问：Disjunction + 活动变量约束
为避免同一节点被重复服务，对每对 (part_i, final_i) 添加硬约束：routing.AddConstraint( routing.ActiveVar(part_i) + routing.ActiveVar(final_i) <= 1 )更推荐使用软约束（带惩罚的 Disjunction），提升求解鲁棒性：
# 若 part_i 未被选中（即 dropped），则罚 cost_final[i]（因本应作为终点却未服务） routing.AddDisjunction([part_i], penalty=costs[i]["final"]) # 若 final_i 未被选中，则罚 cost_part[i]（因本应作为中途点却未服务） routing.AddDisjunction([final_i], penalty=costs[i]["part"])
-
成本注入目标函数
使用 SetArcCostEvaluatorOfAllVehicles() 定义弧成本矩阵，其中：- arc_cost[part_i → part_j] = 0（纯结构弧，成本由节点变量承担）
- arc_cost[part_i → final_j] = 0（非法，应通过 NextVar 约束禁止）
- arc_cost[final_i → End] = 0（终点弧无额外成本）
-
实际节点成本通过 FixedCharge 或 AddVariableMinimizedByFinalizer() 注入目标函数：更简洁的方式是，在添加 part_i 和 final_i 时，直接将其 ActiveVar 与对应成本相乘后加入目标：
objective += routing.ActiveVar(part_i) * costs[i]["part"] objective += routing.ActiveVar(final_i) * costs[i]["final"] routing.Minimize(objective)
⚠️ 注意事项与最佳实践
- Depot 处理：将 depot（节点 0）同时设为 Start 和 End，并确保 distance_callback(·, 0) = 0，使路径自然以 → 0 结束，但该弧不产生成本。
- 规模控制：节点复制会使变量数翻倍，对大规模实例需评估性能；可结合 first_solution_strategy（如 PATH_CHEAPEST_ARC）加速收敛。
- 调试技巧：启用 search_log=True 查看搜索过程；使用 PrintSolution() 提取 final_i 是否被激活，验证终点语义是否生效。
- 扩展性：该模式可推广至三重角色（如 transit/pickup/delivery），只需增加副本及对应约束。
通过上述建模，示例中 costs = [{"part":0,"final":0}, {"part":2,"final":3}, {"part":4,"final":2}, {"part":1,"final":3}] 将正确导向最优路径 0 → part_1 → part_3 → final_2，总成本 = 0 (depot) + 2 (part_1) + 1 (part_3) + 2 (final_2) = 5，完全匹配预期。
完整可运行示例见官方 Gist：https://www.php.cn/link/d42e8faa72ba342df9147902bebb0aac，涵盖 Python 实现细节与参数调优建议。
