|
#!/usr/bin/env python3 |
|
""" |
|
Test Multiple route chains constraint |
|
|
|
We have several chain [A, B, C], [U, V, W], [X,Y] etc.. |
|
and a bund of regular node [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 |
|
import argparse |
|
|
|
|
|
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(): |
|
|
|
parser = argparse.ArgumentParser(description='Solve routing problem, given an input JSON file') |
|
parser.add_argument('-t, --timelimit', type=int, dest='timelimit', default=2, |
|
help='Maximum run time for solver, in seconds. Default is 2 seconds.') |
|
parser.add_argument('--debug', action='store_true', dest='debug', default=False, |
|
help="Turn on solver logging.") |
|
|
|
parser.add_argument('--usecache', action='store_true', dest='usecache', default=False, |
|
help="Turn on solver distance matrix cache.") |
|
|
|
parser.add_argument('--brokenway', action='store_true', dest='brokenway', default=False, |
|
help="Try some broken hacking.") |
|
|
|
args = parser.parse_args() |
|
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]] |
|
data['distance_windows'] = { |
|
2: [0, 1000], |
|
5: [0, 1200], |
|
6: [600, 1200], |
|
# 8: [600, 1200], |
|
# if 11, 12, 13, etc are set to [600, 1200], solver breaks |
|
13: [600, 1200], # try 11, 12, etc |
|
# 16: [600, 1200], # if uncommented, solver cannot use 11 to 16, so does the right thing |
|
} |
|
# Create the routing index manager.2 |
|
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), |
|
data['num_vehicles'], |
|
data['starts'], data['ends']) |
|
|
|
model_parameters = pywrapcp.DefaultRoutingModelParameters() |
|
num_nodes = len(data['distance_matrix']) |
|
# Create Routing Model. |
|
if args.usecache: |
|
model_parameters.max_callback_cache_size = 2 * num_nodes * num_nodes |
|
# Create Routing Model. |
|
routing = pywrapcp.RoutingModel(manager, model_parameters) |
|
# faster solver |
|
# I0802 11:51:53.658935 75 search.cc:260] End search (time = 4999 ms, branches = 26218, failures = 164186, memory used = 15.31 MB, speed = 5244 branches/s) |
|
else: |
|
routing = pywrapcp.RoutingModel(manager) |
|
# slower solver. |
|
# I0802 23:58:21.360351 76 search.cc:260] End search (time = 4998 ms, branches = 22876, failures = 76398, memory used = 15.31 MB, speed = 4577 branches/s) |
|
|
|
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") |
|
# can use distance dimension, as it is monotonically increasing |
|
|
|
# Sequence constraint |
|
for route in data['routes']: |
|
|
|
for i in range(len(route) - 1): |
|
current_index = manager.NodeToIndex(route[i]) |
|
current_active = routing.ActiveVar(current_index) |
|
next_index = manager.NodeToIndex(route[i+1]) |
|
next_active = routing.ActiveVar(next_index) |
|
solver.Add( |
|
current_active * distance_dimension.CumulVar(current_index) <= |
|
next_active * distance_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'])): |
|
start_i = manager.NodeToIndex(data['routes'][i][0]) |
|
end_i = manager.NodeToIndex(data['routes'][i][-1]) |
|
active_i = routing.ActiveVar(start_i) |
|
active_ie = routing.ActiveVar(end_i) |
|
for j in range(i+1, len(data['routes'])): |
|
# print(f'indices {i},{j}') |
|
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}') |
|
active_j = routing.ActiveVar(start_j) |
|
active_je = routing.ActiveVar(end_j) |
|
|
|
# first = distance_dimension.CumulVar(end_i) < distance_dimension.CumulVar(start_j) |
|
# second = distance_dimension.CumulVar(end_j) < distance_dimension.CumulVar(start_i) |
|
# first = active_i * distance_dimension.CumulVar(end_i) <= active_j * distance_dimension.CumulVar(start_j) |
|
# second = active_j * distance_dimension.CumulVar(end_j) <= active_i * distance_dimension.CumulVar(start_i) |
|
|
|
first = active_ie * distance_dimension.CumulVar(end_i) <= active_j * distance_dimension.CumulVar(start_j) |
|
second = active_je * distance_dimension.CumulVar(end_j) <= active_i * distance_dimension.CumulVar(start_i) |
|
|
|
# do not need conditional constraint |
|
# both_active_condition = active_j * active_i == 1 |
|
# conditional_constraint = routing.solver().ConditionalExpression( |
|
# both_active_condition, |
|
# routing.solver().Sum([first, second]) == 1, |
|
# 1) |
|
# solver.Add(conditional_constraint >= 1) |
|
|
|
# if neither route is active, sum will be 2. If one is |
|
# active but not both is active, sum will be 1. If both |
|
# are active, sum must be 1 to prevent interleaving, and |
|
# sum cannot be 2 |
|
# could also do a conditional constraint, but both work |
|
solver.Add(solver.Sum([first, second]) >= 1) |
|
|
|
################################################################# |
|
# Add disjunction to allow dropping or routes, events |
|
################################################################# |
|
|
|
# Add penalty to route nodes |
|
for route in data['routes']: |
|
route_indices = [] |
|
for i in range(len(route)): |
|
node_index = manager.NodeToIndex(route[i]) |
|
route_indices.append(node_index) |
|
if not args.brokenway: |
|
node_disjunction = routing.AddDisjunction([node_index], 100000) |
|
|
|
if args.brokenway and False: |
|
# add pickup deliver constraint for node 0 to all |
|
# zero_index = manager.NodeToIndex(route[0]) |
|
# for i in range(1, len(route)): |
|
# node_index = manager.NodeToIndex(route[i]) |
|
# print(f"pdp for {route[0]} to {route[i]}") |
|
# routing.AddPickupAndDelivery(zero_index, node_index) |
|
dest_indices = [] |
|
dest_index = route_indices.pop() |
|
dest_indices.append(dest_index) |
|
# dest_disjunction = route_disjunctions.pop() |
|
temp_route_indices = [r for r in route_indices] |
|
|
|
temp_dest_indices = [r for r in dest_indices] |
|
while len(temp_route_indices) > 0: |
|
source_disjunction = routing.AddDisjunction(route_indices, 0, len(route_indices)) |
|
dest_disjunction = routing.AddDisjunction(temp_dest_indices, 0, len(temp_dest_indices)) |
|
# see https://github.com/google/or-tools/blob/bad5c2032bd0cd2dc390681e6707b222873045cf/ortools/constraint_solver/routing.h#L716-L720 |
|
routing.AddPickupAndDeliverySets(source_disjunction, dest_disjunction) |
|
print(f"Good way added disjunction for {route_indices} to {temp_dest_indices}") |
|
temp_dest_indices.append(temp_route_indices.pop(-1)) |
|
|
|
if args.brokenway and True: |
|
sources = [r for r in route_indices] |
|
halfway = len(route_indices)//2 |
|
dests = [r for r in route_indices[halfway:]] |
|
sources = [r for r in route_indices[:halfway]] |
|
|
|
print(route_indices, sources, dests) |
|
|
|
if len(sources) == 0 or len(dests) == 0: |
|
continue |
|
for i in [1]: # in range(len(route_indices), 0, -1): |
|
# dests = route_indices[i:] |
|
# if len(dests) == 0: |
|
# continue |
|
# sources.pop() |
|
source_disjunction = routing.AddDisjunction(sources, 100000, len(sources)) |
|
dest_disjunction = routing.AddDisjunction(dests, 100000, len(dests)) |
|
# see https://github.com/google/or-tools/blob/bad5c2032bd0cd2dc390681e6707b222873045cf/ortools/constraint_solver/routing.h#L716-L720 |
|
# routing.AddPickupAndDeliverySets(source_disjunction, dest_disjunction) |
|
print(f"also added disjunction for {sources} and {dests}") |
|
|
|
|
|
# Add penalty for event. Event penalty should be higher than route penalty to avoid drop it |
|
for event_node in data['events']: |
|
event_index = manager.NodeToIndex(event_node) |
|
# print(f"adding disjunction for event {event_node} (node index {event_index})") |
|
routing.AddDisjunction([event_index], 1000000000) |
|
|
|
# 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 = args.debug |
|
search_parameters.time_limit.FromSeconds(args.timelimit) |
|
# [END parameters] |
|
|
|
# make the solver choose between an event and a route |
|
# Add distance window constraints for each location except depot. |
|
for location_idx, distance_window in data['distance_windows'].items(): |
|
if location_idx == 0: |
|
continue |
|
index = manager.NodeToIndex(location_idx) |
|
print(f"setting distance window for {location_idx} to {distance_window[0]}, {distance_window[1]}") |
|
distance_dimension.CumulVar(index).SetRange(distance_window[0], distance_window[1]) |
|
|
|
# Solve problem |
|
solution = routing.SolveWithParameters(search_parameters) |
|
if solution: |
|
print_solution(manager, routing, solution) |
|
else: |
|
print("NO SOLUTION FOUND!") |
|
|
|
|
|
if __name__ == '__main__': |
|
main() |