|
#!/usr/bin/env python3 |
|
""" |
|
Test Multiple route chains constraint |
|
|
|
We have several chain [A, B, C], [U, V, W], [X,Y] etc.. |
|
and a bunch of regular nodes [1,2,3,...] |
|
constraints: |
|
* Can't interleave chains e.g. "A -> B -> X -> C -> Y" is forbidden |
|
* Can have regular node inside a chain e.g. "A -> 3 -> B -> 1 -> C" is OK |
|
""" |
|
|
|
from ortools.constraint_solver import routing_enums_pb2 |
|
from ortools.constraint_solver import pywrapcp |
|
|
|
|
|
def print_solution(manager, routing, solution): |
|
"""Prints solution on console.""" |
|
print(f'Objective: {solution.ObjectiveValue()}') |
|
max_route_distance = 0 |
|
for vehicle_id in range(manager.GetNumberOfVehicles()): |
|
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)) |
|
|
|
|
|
def main(): |
|
data = {} |
|
data['distance_matrix'] = [ |
|
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], |
|
[ |
|
0, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, |
|
1016, 868, 1210 |
|
], |
|
[ |
|
0, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, |
|
1130, 788, 1552, 754 |
|
], |
|
[ |
|
0, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, |
|
1164, 560, 1358 |
|
], |
|
[ |
|
0, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, |
|
1050, 674, 1244 |
|
], |
|
[ |
|
0, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, |
|
514, 1050, 708 |
|
], |
|
[ |
|
0, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, |
|
514, 1278, 480 |
|
], |
|
[ |
|
0, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, |
|
662, 742, 856 |
|
], |
|
[ |
|
0, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, |
|
320, 1084, 514 |
|
], |
|
[ |
|
0, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, |
|
274, 810, 468 |
|
], |
|
[ |
|
0, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, |
|
730, 388, 1152, 354 |
|
], |
|
[ |
|
0, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, |
|
650, 274, 844 |
|
], |
|
[ |
|
0, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, |
|
536, 388, 730 |
|
], |
|
[ |
|
0, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, |
|
342, 422, 536 |
|
], |
|
[ |
|
0, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, |
|
342, 0, 764, 194 |
|
], |
|
[ |
|
0, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, |
|
422, 764, 0, 798 |
|
], |
|
[ |
|
0, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, |
|
536, 194, 798, 0 |
|
], |
|
] |
|
data['num_vehicles'] = 1 |
|
data['starts'] = [1] |
|
data['ends'] = [0] |
|
|
|
data['events'] = [2, 3, 4, 5] |
|
data['routes'] = [[6, 7], [8, 9, 10], [11, 12, 13, 14, 15, 16]] |
|
|
|
# Create the routing index manager. |
|
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), |
|
data['num_vehicles'], |
|
data['starts'], data['ends']) |
|
|
|
# Create Routing Model. |
|
routing = pywrapcp.RoutingModel(manager) |
|
solver = routing.solver() |
|
|
|
# Dimensions |
|
# 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) |
|
|
|
# Add Distance constraint. |
|
dimension_name = 'Distance' |
|
routing.AddDimension( |
|
transit_callback_index, |
|
0, # no slack |
|
99999999999, # vehicle maximum travel distance |
|
True, # start cumul to zero |
|
dimension_name) |
|
#distance_dimension = routing.GetDimensionOrDie(dimension_name) |
|
#distance_dimension.SetGlobalSpanCostCoefficient(0) |
|
|
|
# Count dimensions |
|
routing.AddConstantDimension(1, 1000000, True, "Count") |
|
count_dimension = routing.GetDimensionOrDie("Count") |
|
|
|
# Sequence constraint |
|
for route in data['routes']: |
|
for i in range(len(route) - 1): |
|
current_index = manager.NodeToIndex(route[i]) |
|
next_index = manager.NodeToIndex(route[i+1]) |
|
solver.Add( |
|
count_dimension.CumulVar(current_index) < |
|
count_dimension.CumulVar(next_index)) |
|
|
|
# Enforce same vehicle on route sequence |
|
# note(mizux): this is not needed for a single vehicle problem... |
|
for route in data['routes']: |
|
for i in range(len(route) - 1): |
|
current_index = manager.NodeToIndex(route[i]) |
|
next_index = manager.NodeToIndex(route[i + 1]) |
|
# same vehicle condition |
|
solver.Add( |
|
routing.VehicleVar(current_index) == routing.VehicleVar(next_index)) |
|
|
|
# Forbid interleaved routes |
|
# i.e. we have for any pair of chain X, Y "end_X < start_Y OR end_Y < start_X" |
|
for i in range(len(data['routes'])): |
|
for j in range(i+1, len(data['routes'])): |
|
#print(f'indices {i},{j}') |
|
start_i = manager.NodeToIndex(data['routes'][i][0]) |
|
end_i = manager.NodeToIndex(data['routes'][i][-1]) |
|
start_j = manager.NodeToIndex(data['routes'][j][0]) |
|
end_j = manager.NodeToIndex(data['routes'][j][-1]) |
|
#print(f'{end_i} < {start_j}') |
|
#print(f'{end_j} < {start_i}') |
|
first = count_dimension.CumulVar(end_i) < count_dimension.CumulVar(start_j) |
|
second = count_dimension.CumulVar(end_j) < count_dimension.CumulVar(start_i) |
|
solver.Add(solver.Sum([first, second]) == 1) |
|
|
|
# Setting first solution heuristic. |
|
# [START parameters] |
|
search_parameters = pywrapcp.DefaultRoutingSearchParameters() |
|
search_parameters.first_solution_strategy = ( |
|
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) |
|
search_parameters.local_search_metaheuristic = ( |
|
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) |
|
search_parameters.log_search = True |
|
search_parameters.time_limit.FromSeconds(5) |
|
# [END parameters] |
|
|
|
# Solve problem |
|
solution = routing.SolveWithParameters(search_parameters) |
|
if solution: |
|
print_solution(manager, routing, solution) |
|
else: |
|
print("NO SOLUTION FOUND!") |
|
|
|
|
|
if __name__ == '__main__': |
|
main() |