17370845950

本文介绍如何在 google or-tools 中为同一节点设置基于其在路径中位置（中间节点 or 终点）的不同成本，通过节点复制、活性约束与惩罚型不相容约束（disjunction）构建动态目标函数。

在标准车辆路径问题（VRP）建模中，节点成本通常被定义为静态值（如访问成本、服务时间或固定费用），但实际业务场景中，节点的代价可能取决于它在路径中的角色：例如，某客户若作为中途停靠点（part of route），仅产生装卸准备成本；而若作为该车次的终点（final destination），则需额外支付返程调度、结算或清场成本。Google OR-Tools 的 RoutingModel 默认不支持“位置感知”的动态节点成本，因其目标函数基于弧（arc）而非节点状态建模。但可通过建模技巧巧妙实现——核心思想是：将每个业务节点拆分为两个逻辑节点：node_part（仅允许出现在路径中间）和 node_final（仅允许作为路径终点），再通过约束与惩罚机制引导求解器选择最经济的定位方式。

✅ 实现步骤详解

1. 节点复制与角色划分
   对原始节点 i（i ≥ 1），创建两个索引：

   • i_part：代表“作为中间节点访问”，禁止连接至车辆终点（NextVar(i_part) ≠ vehicle_end）；
   • i_final：代表“作为终点访问”，只允许后继为 vehicle_end（即 NextVar(i_final) == vehicle_end）。

2. 强制互斥访问（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
   )

3. 嵌入位置敏感成本到目标函数

   • 若 i_part 被跳过（未访问），则施加惩罚 costs[i]["final"]（即本应以终点身份服务，却未服务 → 损失机会成本）；
   • 若 i_final 被跳过，则施加惩罚 costs[i]["part"]（即本可低成本中途服务，却放弃 → 承担最低服务成本）。
     这种设计将“未选最优角色”的隐性代价显式引入目标函数，驱动求解器自动权衡。

4. 处理仓库（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 中完整实现，支持多车、容量约束与时间窗扩展。掌握此模式后，你可进一步建模如“首单免运费”“末单赠券”等营销策略驱动的动态成本逻辑。