17370845950

本文详解如何在 or-tools 的 vrp 求解器中为同一节点赋予“中途访问”与“终点访问”两种不同成本，通过节点复制、活动变量约束与惩罚型 disjunction 技巧实现位置感知的成本建模。

在标准车辆路径问题（VRP）中，节点成本通常是静态的——即无论该节点出现在路径中间还是末尾，其服务成本恒定。但现实中，许多场景要求成本依赖于节点在路径中的逻辑角色：例如，将货物运至中转站（中途节点）成本较低，而作为最终交付点（终点节点）则需额外装卸或结算开销。Google OR-Tools 原生不支持“位置敏感”的节点成本，但可通过建模技巧优雅实现。

核心思路是：将每个业务节点拆分为两个逻辑实体——part_node（可出现在路径中段）和 final_node（仅允许作为路径终点），并利用求解器的 ActiveVar、NextVar 和 Disjunction 机制协同约束其行为。

✅ 关键建模步骤

1. 节点复制与索引映射
   对原始节点 i（i ≥ 1），创建两个对应索引：

   • part_i：表示节点 i 以“中途角色”被访问（成本为 costs[i]["part"]）
   • final_i：表示节点 i 以“终点角色”被访问（成本为 costs[i]["final"]）
     同时，保留 depot（节点 0）作为所有路径的起点与隐式终点（注意：其 NextVar 可指向自身，但弧成本设为 0，不计入目标函数）。

2. 强制位置语义约束

   • 对每个 part_i：禁用其 NextVar 指向任何 final_j 或 End —— 即 part_i 后必须接另一个 part_j 或 depot，确保它不会成为终点。
   • 对每个 final_i：将其 NextVar 仅允许指向 End（车辆终点）或 depot（0），且设置 routing.NextVar(final_i) == routing.End(vehicle)（或等价约束），保证其必为路径最后一站。

3. 互斥访问：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"])

4. 成本注入目标函数
   使用 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./link/d42e8faa72ba342df9147902bebb0aac，涵盖 Python 实现细节与参数调优建议。