python - 如何在Google or-tools中设置车辆最大行驶距离和GlobalSpanCostCoefficient

Question

我在做什么错，我有 4 辆车，但他们的路线不平衡这是我的距离矩阵

[[0, 10998, 352, 4733, 11077, 12001, 3017, 5404, 7411, 5920, 9778, 4402, 7005, 7105, 273, 11398],
[11579, 0, 11612, 18702, 21349, 22273, 13340, 8814, 4382, 14235, 20050, 14725, 18134, 17377, 11660, 21670],
[722, 11083, 0, 4819, 11163, 12087, 3102, 5490, 7497, 6005, 9864, 4487, 7091, 7191, 410, 11484],
[3787, 14785, 4139, 0, 6160, 5863, 1679, 9191, 11198, 11475, 3500, 480, 922, 6394, 3827, 6481],
[11540, 21533, 11605, 6261, 0, 1108, 6979, 15940, 17947, 16504, 2906, 5912, 5692, 5926, 11653, 506],
[12496, 22490, 12562, 6557, 1700, 0, 7936, 16896, 18903, 17460, 3080, 5764, 5989, 6882, 12609, 298],
[2721, 13719, 3073, 1598, 7377, 8300, 0, 8125, 10132, 10427, 4286, 1266, 1708, 7611, 2761, 7698],
[8811, 5626, 8843, 15934, 18580, 19504, 10572, 0, 2040, 8603, 17281, 11957, 15365, 14608, 8891, 18902],
[7723, 4157, 7755, 14846, 17492, 18416, 9484, 4957, 0, 10379, 16193, 10869, 14277, 13520, 7803, 17814],
[7703, 14185, 7533, 11854, 17523, 18447, 9884, 8592, 10599, 0, 16224, 11269, 12486, 13551, 7581, 17845],
[10133, 20127, 10198, 3353, 2817, 2598, 5446, 14533, 16540, 15097, 0, 3005, 2785, 4519, 10246, 2464],
[5025, 17258, 7330, 1010, 5680, 5383, 2917, 11665, 13672, 12713, 3020, 0, 442, 5914, 5065, 6001],
[4419, 15417, 4771, 569, 5900, 5603, 2311, 9823, 11830, 12107, 3240, 220, 0, 6134, 4458, 6221],
[7370, 17364, 7436, 5657, 6286, 7210, 6350, 11770, 13777, 12334, 4987, 5308, 5088, 0, 7484, 6608],
[410, 11260, 410, 4290, 11339, 12263, 2574, 5666, 7673, 5918, 10040, 3959, 5180, 7367, 0, 11661],
[8307, 22309, 12381, 5878, 1402, 603, 6430, 16715, 18722, 17279, 2401, 5084, 5309, 6701, 12428, 0]]

和我的代码：

def print_solution(data, manager, routing, solution):
max_route_distance = 0
for vehicle_id in range(data['num_vehicles']):
    index = routing.Start(vehicle_id)
    plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} -> '.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(
            previous_index, index, vehicle_id)
    plan_output += '{}\n'.format(manager.IndexToNode(index))
    plan_output += 'Distance of the route: {}m\n'.format(route_distance)
    print(plan_output)
    max_route_distance = max(route_distance, max_route_distance)
print('Maximum of the route distances: {}m'.format(max_route_distance))

data = create_data()

manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                       data['num_vehicles'], data['depot'])
print(data)
routing = pywrapcp.RoutingModel(manager)

def distance_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)
    return data['distance_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
dimension_name = 'Distance'
routing.AddDimension(
    transit_callback_index,
    0,  # zero slack
    25000,  # max distance
    True,  # start cumul to zero
    dimension_name)

distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)


search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

solution = routing.SolveWithParameters(search_parameters)

if solution:
    print(solution)
    print_solution(data, manager, routing, solution)

输出：

Route for vehicle 0:
 0 ->  13 -> 0
Distance of the route: 14475m

Route for vehicle 1:
 0 ->  2 ->  9 -> 0
Distance of the route: 14060m

Route for vehicle 2:
 0 ->  7 ->  1 ->  8 -> 0
Distance of the route: 23135m

Route for vehicle 3:
 0 ->  14 ->  6 ->  3 ->  11 ->  12 ->  10 ->  4 ->  5 ->  15 -> 0
Distance of the route: 21137m

Maximum of the route distances: 23135m

标签： pythonor-tools

Answer 1

使用 GlobalSpan，求解器将尝试在您的情况下最小化最长的路线，即车辆 2...（全局跨度max(ends) - min(starts)，这里所有车辆都从 0 开始）

Route for vehicle 2:
 0 ->  7 ->  1 ->  8 -> 0
Distance of the route: 23135m

然后求解器也尝试最小化剩余的路线，但没有任何平衡（只尝试最小化所有跨度的总和，即路线距离）。

OR-Tools 不提供任何“最小化偏差”约束。

如果启用 lns

    search_params.time_limit.seconds = 30
    search_params.local_search_metaheuristic = (
            routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

然后你会发现：

Route for vehicle 0:
 0 ->  13 -> 0
Distance of the route: 14475m

Route for vehicle 1:
 0 ->  2 ->  9 -> 0
Distance of the route: 14060m

Route for vehicle 2:
 0 ->  7 ->  1 ->  8 -> 0
Distance of the route: 23135m

Route for vehicle 3:
 0 ->  14 ->  6 ->  11 ->  4 ->  5 ->  15 ->  10 ->  12 ->  3 -> 0
Distance of the route: 20741m

Maximum of the route distances: 23135m