如何在OR-Tools的VRP中于指定节点重置维度值为0？

问题场景 #

• 使用Python的OR-Tools求解车辆路径问题（VRP）时，因取派约束存在实际位置重复的节点（如多个Depot节点对应同一物理位置）
• 每个以Depot为起止的子路线最多可访问3个节点（Depot+2个门店），车辆可返回重复Depot执行多条子路线，总访问节点数无限制
• 核心需求：每当车辆访问Depot副本节点时，统计实际访问位置的维度值必须重置为0

原代码问题 #

直接通过dim.CumulVar(_idx(i)).SetValue(0)强制固定Depot节点的累积变量值，会导致求解器的约束冲突，无法找到可行解。这是因为OR-Tools的维度累积变量是动态计算的，强制赋值会破坏路径累积的逻辑链。

修复方案 #

通过添加等式约束替代强制赋值，让求解器在路径规划过程中自动满足Depot节点累积值为0的要求，同时调整维度回调逻辑和参数适配需求：

from ortools.constraint_solver.pywrapcp import RoutingIndexManager, RoutingModel, DefaultRoutingSearchParameters
from ortools.constraint_solver.routing_enums_pb2 import FirstSolutionStrategy, LocalSearchMetaheuristic
import numpy as np, pandas as pd

def solve_mixed_vrp(dist, n_vehicles, nodes):
    manager = RoutingIndexManager(len(dist), n_vehicles, 0)
    model = RoutingModel(manager)
    _node, _idx = manager.IndexToNode, manager.NodeToIndex

    # 设置路径成本回调：非对角线节点距离为1，自身为0
    model.SetArcCostEvaluatorOfAllVehicles(model.RegisterTransitCallback(
        lambda _i, _j: dist[_node(_i), _node(_j)]))
    
    # 定义位置统计回调：非Depot节点间位置不同则+1，目标为Depot时增量为0
    def route_locations(_i, _j):
        node_i = _node(_i)
        node_j = _node(_j)
        if nodes.at[node_j, 'lct'] == 0:
            return 0
        return 1 if nodes.at[node_i, 'lct'] != nodes.at[node_j, 'lct'] else 0

    # 添加位置统计维度：上限设为2（对应Depot+2个门店的子路线）
    model.AddDimension(model.RegisterTransitCallback(route_locations), 
                      0, 2, True, "route_locations")
    dim = model.GetDimensionOrDie("route_locations")

    # 为所有Depot节点添加约束：累积值必须为0
    for i in range(len(nodes)):
        if nodes.at[i, 'lct'] == 0:
            model.AddConstraint(dim.CumulVar(_idx(i)) == 0)

    # 配置搜索参数，提升求解效率
    search_params = DefaultRoutingSearchParameters()
    search_params.local_search_metaheuristic = LocalSearchMetaheuristic.AUTOMATIC
    search_params.first_solution_strategy = FirstSolutionStrategy.PATH_CHEAPEST_ARC
    search_params.time_limit.seconds = 10

    solution = model.SolveWithParameters(search_params)
    return solution, model, manager

# 示例执行
nodes = pd.DataFrame({"lct":[0,0,1,2,3,4]})  # 节点0和1对应同一Depot位置
nn, nv = len(nodes), 1
dist = (np.ones((nn,nn)) - np.identity(nn)).astype(int)

sol, model, manager = solve_mixed_vrp(dist, nv, nodes)

# 输出结果
if sol:
    print("找到可行解：")
    route = []
    index = model.Start(0)
    while not model.IsEnd(index):
        route.append(manager.IndexToNode(index))
        index = sol.Value(model.NextVar(index))
    route.append(manager.IndexToNode(index))
    print("路径：", route)
else:
    print("未找到可行解")

关键修复点 #

1. 约束替代强制赋值：用model.AddConstraint(dim.CumulVar(_idx(i)) == 0)替代SetValue(0)，允许求解器动态调整路径以满足Depot节点的累积值要求
2. 回调逻辑优化：当目标节点为Depot时，设置增量为0，配合约束实现累积值重置
3. 维度参数调整：将维度上限设为2，匹配“Depot+2个门店”的子路线限制
4. 搜索参数优化：使用明确的初始解策略并添加时间限制，提升求解成功率和效率

内容的提问来源于stack exchange，提问作者Leo