Skip to content

Instantly share code, notes, and snippets.

@jmarca

jmarca/README.md

Created March 5, 2021 01:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jmarca/c78b0b5d785e36cf89f15692d68165b0 to your computer and use it in GitHub Desktop.
Save jmarca/c78b0b5d785e36cf89f15692d68165b0 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
README.md

broken

This demonstrates the problem, but has not yet hit a solution.

Modification of https://gist.github.com/Mizux/f200bd2b0fc6ad622922b0ca9e868823

Added disjunctions, and conditions (using distance_window) that require some nodes to be dropped.

The ideal solution drops the range 11 to 16, keeps node 2.

The current solver run is dropping node 2, keeping 11 to 16

Raw
chain_modified_with_disjunctions.py
#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment