OR-tools VRP求解异常咨询：单车辆包揽全部节点

我是OR-tools的新手，此前已使用其他求解器完成基础车辆路径问题（VRP）的求解，距离矩阵等计算均正确。现希望通过OR-tools实现并添加自定义约束，基于官方示例编写了代码，但求解结果中两台车辆仅停留在配送中心，另一台车辆包揽了所有住宅节点，目标值为0，咨询该异常结果的原因及解决办法。

原代码片段 #

# Depot and houses are created correctly
points = [depot] + houses

manager = pywrapcp.RoutingIndexManager(
            len(points), 3, 0
        )

routing = pywrapcp.RoutingModel(manager)

def time_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)

    # Distance matrix is created correctly
    return distance_matrix[from_node][to_node] / WALKING_M_PER_S

    # Create the time callback.
    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Time constraint.
    time_dimension_name = "Time"
    routing.AddDimension(
        transit_callback_index,
        90,  # time at each node
        3600,  # vehicle maximum travel distance
        True,  # start cumul to zero
        time_dimension_name,
    )
    time_dimension = routing.GetDimensionOrDie(time_dimension_name)
    time_dimension.SetGlobalSpanCostCoefficient(100)

    # Allow to drop nodes
    penalty = 1
    for node in range(1, 4):
        routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    # Add verbose logging
    search_parameters.log_search = True

    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print("Objective: {}".format(solution.ObjectiveValue()))
        # Inspect solution.
        routes = []
        for vehicle_id in range(3):
            index = routing.Start(vehicle_id)
            route = []
            while not routing.IsEnd(index):
                node_index = manager.IndexToNode(index)
                route.append(node_index)
                index = solution.Value(routing.NextVar(index))
            routes.append(route)
            print(route)
        return routes
    else:
        print("No solution found.")
        return None

求解输出片段 #

WARNING: All log messages before absl::InitializeLog() is called are written to STDERR
I0000 00:00:1699732434.288710   66746 routing.cc:2525] All Unperformed Solution (283, time = 12 ms, memory used = 263.57 MB)
I0000 00:00:1699732434.289000   66746 search.cc:276] Start search (memory used = 263.57 MB)
I0000 00:00:1699732434.289640   66746 search.cc:276] Root node processed (time = 0 ms, constraints = 2585, memory used = 263.57 MB)
I0000 00:00:1699732434.444527   66746 search.cc:276] Solution #0 (0, time = 155 ms, branches = 34, failures = 0, depth = 33, memory used = 273.32 MB)
I0000 00:00:1699732434.444631   66746 search.cc:276] Finished search tree (time = 155 ms, branches = 34, failures = 34, memory used = 273.32 MB)
I0000 00:00:1699732434.444888   66746 search.cc:276] End search (time = 155 ms, branches = 34, failures = 34, memory used = 273.32 MB, speed = 219 branches/s)
Objective: 0
[0]
[0]
[0, 283, 282, 281, 280, 279, 278, 277, 276, 275, 274, 273, 272, 271, 270, 269, 268, 267, 266, 265, 264, 263, 262, 261, 260, 259, 258, 257, 256, 255, 254, 253, 252, 251, 250, 249, 248, 247, 246, 245, 244, 243, 242, 241, 240, 239, 238, 237, 236, 235, 234, 233, 232, 231, 230, 229, 228, 227, 226, 225, 224, 223, 222, 221, 220, 219, 218, 217, 216, 215, 214, 213, 212, 211, 210, 209, 208, 207, 206, 205, 204, 203, 202, 201, 200, 199, 198, 197, 196, 195, 194, 193, 192, 191, 190, 189, 188, 187, 186, 185, 184, 183, 182, 181, 180, 179, 178, 177, 176, 175, 174, 173, 172, 171, 170, 169, 168, 167, 166, 165, 164, 163, 162, 161, 160, 159, 158, 157, 156, 155, 154, 153, 152, 151, 150, 149, 148, 147, 146, 145, 144, 143, 142, 141, 140, 139, 138, 137, 136, 135, 134, 133, 132, 131, 130, 129, 128, 127, 126, 125, 124, 123, 122, 121, 120, 119, 118, 117, 116, 115, 114, 113, 112, 111, 110, 109, 108, 107, 106, 105, 104, 103, 102, 101, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

原因分析 #

• 缩进错误导致核心逻辑未执行：time_callback函数中，return语句之后的所有配置代码（注册回调、添加时间维度等）都被包裹在函数内部，函数执行到return直接退出，导致路由模型未应用任何时间约束和成本评估规则，求解器默认以0成本处理所有弧，自然出现单车辆包揽所有节点的结果。
• 服务时长参数理解错误：routing.AddDimension的第二个参数是松弛时间（slack），用于设置车辆可在节点等待的最长时间，而非服务时长。你将90秒服务时长设置为slack，实际服务时长未被添加到模型中。
• 可丢弃节点范围过小：仅对1-3号节点设置了可丢弃属性，大部分住宅节点未被配置，与“尽可能多完成任务”的需求不符。
• 目标函数权重配置不合理：仅设置了最小化最长路径时间的权重，未将“减少未访问节点惩罚”作为核心目标，求解器没有动力分配任务到多台车辆。

解决办法 #

1. 修复缩进错误，确保核心逻辑执行 #

将time_callback函数外的配置代码移出函数体，保证回调注册、维度添加等代码正常运行：

def time_callback(from_index, to_index):
    """Returns the travel time between the two nodes."""
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return distance_matrix[from_node][to_node] / WALKING_M_PER_S

# 这部分代码必须放在time_callback函数外部！
transit_callback_index = routing.RegisterTransitCallback(time_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

2. 正确添加服务时长 #

服务时长需通过时间维度为每个非depot节点添加固定停留时间，修改AddDimension并补充节点服务时间配置：

time_dimension_name = "Time"
routing.AddDimension(
    transit_callback_index,
    0,  # slack：无等待需求，设为0
    3600,  # 车辆最大总时间（秒）
    True,  # 起始点累积时间为0
    time_dimension_name,
)
time_dimension = routing.GetDimensionOrDie(time_dimension_name)

# 为每个非depot节点添加90秒服务时长
for node in range(1, manager.GetNumberOfNodes()):
    node_index = manager.NodeToIndex(node)
    time_dimension.CumulVar(node_index).SetMin(time_dimension.CumulVar(node_index).Min() + 90)
    time_dimension.CumulVar(node_index).SetMax(time_dimension.CumulVar(node_index).Max() + 90)

3. 为所有住宅节点添加可丢弃设置 #

将所有非depot节点设置为可丢弃，设置合理的惩罚值（需大于访问节点的总成本，确保求解器优先访问节点）：

penalty = 1000  # 惩罚值需足够大，驱动求解器优先访问节点
for node in range(1, manager.GetNumberOfNodes()):
    routing.AddDisjunction([manager.NodeToIndex(node)], penalty)

4. 调整目标函数权重 #

将“减少未访问节点惩罚”作为核心目标，同时保留时间跨度优化：

# 降低最长路径时间的权重，优先保证访问更多节点
time_dimension.SetGlobalSpanCostCoefficient(10)
# Disjunction的惩罚会自动加入目标函数，无需额外配置

5. 优化求解策略（可选） #

使用更适合多车辆分配的初始解策略，并启用局部搜索提升解质量：

search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION
)
search_parameters.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
)
search_parameters.time_limit.seconds = 10  # 设置求解时间限制

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