Это мой код
from __future__ import print_function
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
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))
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data()
data['distance_matrix'] = distance_matrix
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['depot'])
print(data)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback.
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)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Thêm constraint về khoảng cách
dimension_name = 'Distance'
routing.AddDimension(
transit_callback_index,
0, # Thời gian delay cho phép
25000, # khoách cách tối đa 1 xe có thể đi (25000m)
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(1000)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
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(solution)
print_solution(data, manager, routing, solution)
и моя матрица расстояний
[[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]]
сначала я установил 4 автомобиля, и он дает мне следующий вывод:
Route for vehicle 0:
0 -> 6 -> 11 -> 4 -> 5 -> 15 -> 10 -> 12 -> 3 -> 16 -> 0
Distance of the route: 22751m
Route for vehicle 1:
0 -> 13 -> 0
Distance of the route: 14475m
Route for vehicle 2:
0 -> 1 -> 8 -> 0
Distance of the route: 23103m
Route for vehicle 3:
0 -> 7 -> 9 -> 2 -> 14 -> 0
Distance of the route: 22360m
Maximum of the route distances: 23103m
Когда я использую 6 автомобилей, кажется, что 2 автомобиля не используются:
Route for vehicle 0:
0 -> 13 -> 0
Distance of the route: 14475m
Route for vehicle 1:
0 -> 0
Distance of the route: 0m
Route for vehicle 2:
0 -> 0
Distance of the route: 0m
Route for vehicle 3:
0 -> 11 -> 10 -> 4 -> 5 -> 15 -> 0
Distance of the route: 19952m
Route for vehicle 4:
0 -> 7 -> 1 -> 8 -> 0
Distance of the route: 23135m
Route for vehicle 5:
0 -> 14 -> 2 -> 6 -> 12 -> 3 -> 16 -> 9 -> 0
Distance of the route: 24452m
Maximum of the route distances: 24452m
, тогда я обнаружил, что 3 - это лучший результат, и требуется около 6 минут, чтобы решить, где два выше (около 30 секунд) это выпущен с 3 автомобилями
Route for vehicle 0:
0 -> 13 -> 4 -> 5 -> 15 -> 10 -> 3 -> 0
Distance of the route: 24338m
Route for vehicle 1:
0 -> 2 -> 7 -> 1 -> 8 -> 0
Distance of the route: 23573m
Route for vehicle 2:
0 -> 14 -> 9 -> 16 -> 11 -> 12 -> 0
Distance of the route: 22202m
Maximum of the route distances: 24388m
Что это значит? Я новичок в этом