This doesn't make sense, because not applying partial route constraints should lead to at least as many solutions. The full code is below, but the relevant portion is here:
routing.CloseModel()
partial_route_list = data['partial_routes']
routing.ApplyLocksToAllVehicles(partial_route_list, False)
All lists in data['partial_routes'] only include transit nodes as per the user manual. When data['partial_routes'] = [[], [0, 1], [], [], []] (I have 5 vehicles) or some other variant, OR-Tools can find a solution. But when data['partial_routes'] = [[], [], [], [], []], it fails to find a solution.
Full code:
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'],
data['start'],
data['end'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Add resource constraints (which vehicles are allowed to visit which nodes)
for index in range(len(data['node_name'])):
allowed_vehicles = [-1]
if data['num_ramp'][index] > 0 or np.isnan(data['num_ramp'][index]):
allowed_vehicles.extend(
[key for key, val in enumerate(data['vehicle_type']) if val == 'van' and key in data['allowed_vehicles'][index]])
if data['num_dock_high'][index] > 0 or data['num_dock_high'][index]:
allowed_vehicles.extend(
[key for key, val in enumerate(data['vehicle_type']) if val == 'truck' and key in data['allowed_vehicles'][index]])
routing.VehicleVar(index).SetValues(allowed_vehicles)
# Create and register a transit distance 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_distance_callback_index = routing.RegisterTransitCallback(distance_callback)
# Add Distance constraint.
routing.AddDimension(
transit_distance_callback_index,
0, # no slack
sum([sum(x) for x in data['distance_matrix']]), # vehicle maximum travel distance
True, # start cumul to zero
'Distance')
distance_dimension = routing.GetDimensionOrDie('Distance')
# Add capacity constraints.
def demand_weight_callback(from_index):
"""Returns the weight demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demand_weight'][from_node]
demand_weight_callback_index = routing.RegisterUnaryTransitCallback(demand_weight_callback)
routing.AddDimensionWithVehicleCapacity(
demand_weight_callback_index,
0, # null capacity slack
data['vehicle_capacity_weight'], # vehicle maximum capacities
True, # start cumul to zero
'Weight Capacity')
def demand_volume_callback(from_index):
"""Returns the volume demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demand_volume'][from_node]
demand_volume_callback_index = routing.RegisterUnaryTransitCallback(demand_volume_callback)
routing.AddDimensionWithVehicleCapacity(
demand_volume_callback_index,
0, # null capacity slack
data['vehicle_capacity_volume'], # vehicle maximum capacities
True, # start cumul to zero
'Volume Capacity')
def demand_pallet_callback(from_index):
"""Returns the pallet demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demand_pallet'][from_node]
demand_pallet_callback_index = routing.RegisterUnaryTransitCallback(demand_pallet_callback)
routing.AddDimensionWithVehicleCapacity(
demand_pallet_callback_index,
0, # null capacity slack
data['vehicle_capacity_pallet'], # vehicle maximum capacities
True, # start cumul to zero
'Pallet Capacity')
# Define pickup and delivery constraints
for request in data['pickups_deliveries']:
pickup_index = manager.NodeToIndex(request[0])
delivery_index = manager.NodeToIndex(request[1])
routing.AddPickupAndDelivery(pickup_index, delivery_index)
routing.solver().Add(
routing.VehicleVar(pickup_index) == routing.VehicleVar(
delivery_index))
routing.solver().Add(
distance_dimension.CumulVar(pickup_index) <=
distance_dimension.CumulVar(delivery_index))
# Create and register a transit time callback.
def transit_time_callback(from_index, to_index):
"""Returns the travel time only between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['time_matrix'][from_node][to_node]
transit_time_callback_index = routing.RegisterTransitCallback(transit_time_callback)
# Create and register a time callback.
def time_callback(from_index, to_index):
"""Returns the travel and dock time between the two nodes."""
# Convert from routing variable Index to time matrix NodeIndex.
transit_time = transit_time_callback(from_index, to_index)
to_node = manager.IndexToNode(to_index)
if to_node in data['pickups']:
dock_time = data['load_time'][to_node]
else:
dock_time = data['unload_time'][to_node]
return transit_time + dock_time
time_callback_index = routing.RegisterTransitCallback(time_callback)
# Add time windows constraint.
routing.AddDimension(
time_callback_index,
3 * MIN_PER_HR * SEC_PER_MIN, # allow waiting time
24 * MIN_PER_HR * SEC_PER_MIN, # maximum time per vehicle
False, # Don't force start cumul to zero.
'Time')
time_dimension = routing.GetDimensionOrDie('Time')
# Add time window constraints for each location.
for location_idx, time_window in enumerate(data['time_windows']):
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add driving duration constraint.
routing.AddDimension(
transit_time_callback_index,
3 * MIN_PER_HR * SEC_PER_MIN, # allow waiting time
24 * MIN_PER_HR * SEC_PER_MIN, # maximum time per vehicle
False, # Don't force start cumul to zero.
'Driving Duration')
driving_duration_dimension = routing.GetDimensionOrDie('Driving Duration')
for v in range(data['num_vehicles']):
# Limit max on-duty time for each vehicle
routing.solver().Add(
time_dimension.CumulVar(routing.End(v)) - time_dimension.CumulVar(routing.Start(v)) <= MAX_TIME_ON_DUTY)
# Limit max driving time for each vehicle
routing.solver().Add(driving_duration_dimension.CumulVar(routing.End(v)) <= MAX_TIME_DRIVING)
# Minimize on-duty duration.
for i in range(data['num_vehicles']):
routing.AddVariableMaximizedByFinalizer(
time_dimension.CumulVar(routing.Start(i)))
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i)))
# Define cost of each arc for each vehicle
for v in range(data['num_vehicles']):
def cost_callback(from_index, to_index):
"""Returns the cost 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)
cost_per_mi = data['cost_per_mi'][v]
if data['node_name'][from_node] != data['node_name'][to_node]:
if data['is_hub'][to_node] is True:
stop_cost = data['cost_per_hub_to_hub'][v]
else:
stop_cost = data['cost_per_stop'][v]
else:
stop_cost = 0
return data['distance_matrix'][from_node][to_node] / METERS_PER_MI * cost_per_mi + stop_cost
cost_callback_index = routing.RegisterTransitCallback(cost_callback)
routing.SetArcCostEvaluatorOfVehicle(cost_callback_index, v)
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 30
search_parameters.solution_limit = 5
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)
# Collect multiple solutions.
solution_collector = routing.solver().AllSolutionCollector()
for location_idx in range(len(data['time_windows'])):
index = manager.NodeToIndex(location_idx)
time_var = time_dimension.CumulVar(index)
duration_var = driving_duration_dimension.CumulVar(index)
next_var = routing.NextVar(index)
solution_collector.Add(time_var)
solution_collector.Add(duration_var)
solution_collector.Add(next_var)
for v in range(data['num_vehicles']):
index = routing.Start(v)
time_var = time_dimension.CumulVar(index)
duration_var = driving_duration_dimension.CumulVar(index)
next_var = routing.NextVar(index)
solution_collector.Add(time_var)
solution_collector.Add(duration_var)
solution_collector.Add(next_var)
index = routing.End(v)
time_var = time_dimension.CumulVar(index)
duration_var = driving_duration_dimension.CumulVar(index)
solution_collector.Add(time_var)
solution_collector.Add(duration_var)
routing.AddSearchMonitor(solution_collector)
# Lock partial routes
# Reference: https://github.com/google/or-tools/blob/master/examples/python/cvrptw_plot.py
routing.CloseModel()
partial_route_list = data['partial_routes']
routing.ApplyLocksToAllVehicles(partial_route_list, False)
# Solve
solution = routing.SolveWithParameters(search_parameters)
This may be overkill, but data is defined below:
{
"node_name": [
"Cleveland Food Hub",
"Cleveland Food Hub",
"Cleveland Food Hub",
"Cleveland Food Hub",
"Dummy Food Hub",
"Dummy Food Hub",
"Dummy Food Hub",
"East",
"MLK",
"MCHS",
"Cleveland Food Hub",
"Choffin",
"Refugee Response",
"Refugee Response",
"Refugee Response",
"Refugee Response",
"Refugee Response"
],
"delivery_notes": [
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
NaN
],
"is_hub": [
true,
true,
true,
true,
true,
true,
true,
false,
false,
false,
true,
false,
NaN,
NaN,
NaN,
NaN,
NaN
],
"num_dock_high": [
2.0,
2.0,
2.0,
2.0,
1.0,
1.0,
1.0,
0.0,
0.0,
1.0,
2.0,
0.0,
NaN,
NaN,
NaN,
NaN,
NaN
],
"num_ramp": [
1.0,
1.0,
1.0,
1.0,
1.0,
1.0,
1.0,
1.0,
1.0,
0.0,
1.0,
1.0,
NaN,
NaN,
NaN,
NaN,
NaN
],
"distance_matrix": [
[
0,
0,
0,
0,
126018,
126018,
126018,
127656,
129435,
129815,
0,
125621,
40935,
40935,
24559,
40939,
24517
],
[
0,
0,
0,
0,
126018,
126018,
126018,
127656,
129435,
129815,
0,
125621,
40935,
40935,
24559,
40939,
24517
],
[
0,
0,
0,
0,
126018,
126018,
126018,
127656,
129435,
129815,
0,
125621,
40935,
40935,
24559,
40939,
24517
],
[
0,
0,
0,
0,
126018,
126018,
126018,
127656,
129435,
129815,
0,
125621,
40935,
40935,
24559,
40939,
24517
],
[
123102,
123102,
123102,
123102,
0,
0,
0,
7510,
9289,
9669,
123102,
4207,
90590,
90590,
90599,
90594,
90642
],
[
123102,
123102,
123102,
123102,
0,
0,
0,
7510,
9289,
9669,
123102,
4207,
90590,
90590,
90599,
90594,
90642
],
[
123102,
123102,
123102,
123102,
0,
0,
0,
7510,
9289,
9669,
123102,
4207,
90590,
90590,
90599,
90594,
90642
],
[
122953,
122953,
122953,
122953,
7958,
7958,
7958,
0,
3332,
3712,
122953,
2818,
87035,
87035,
87044,
87038,
87086
],
[
124709,
124709,
124709,
124709,
9713,
9713,
9713,
3332,
0,
502,
124709,
5168,
88790,
88790,
88800,
88794,
88842
],
[
125089,
125089,
125089,
125089,
10093,
10093,
10093,
3712,
502,
0,
125089,
5548,
89170,
89170,
89180,
89174,
89222
],
[
0,
0,
0,
0,
126018,
126018,
126018,
127656,
129435,
129815,
0,
125621,
40935,
40935,
24559,
40939,
24517
],
[
121938,
121938,
121938,
121938,
4204,
4204,
4204,
2866,
5216,
5596,
121938,
0,
84376,
84376,
84385,
84380,
84428
],
[
24281,
24281,
24281,
24281,
91665,
91665,
91665,
93303,
89558,
89332,
24281,
85598,
0,
0,
9,
4,
51
],
[
24281,
24281,
24281,
24281,
91665,
91665,
91665,
93303,
89558,
89332,
24281,
85598,
0,
0,
9,
4,
51
],
[
24272,
24272,
24272,
24272,
91674,
91674,
91674,
93312,
89568,
89341,
24272,
85608,
9,
9,
0,
6,
42
],
[
24278,
24278,
24278,
24278,
91668,
91668,
91668,
93306,
89562,
89336,
24278,
85602,
4,
4,
6,
0,
48
],
[
24230,
24230,
24230,
24230,
91716,
91716,
91716,
93354,
89610,
89383,
24230,
85650,
51,
51,
42,
48,
0
]
],
"time_matrix": [
[
0,
0,
0,
0,
4723,
4723,
4723,
4836,
4985,
5022,
0,
4685,
1980,
1980,
2111,
1981,
2099
],
[
0,
0,
0,
0,
4723,
4723,
4723,
4836,
4985,
5022,
0,
4685,
1980,
1980,
2111,
1981,
2099
],
[
0,
0,
0,
0,
4723,
4723,
4723,
4836,
4985,
5022,
0,
4685,
1980,
1980,
2111,
1981,
2099
],
[
0,
0,
0,
0,
4723,
4723,
4723,
4836,
4985,
5022,
0,
4685,
1980,
1980,
2111,
1981,
2099
],
[
4607,
4607,
4607,
4607,
0,
0,
0,
618,
767,
804,
4607,
421,
3879,
3879,
3881,
3880,
3892
],
[
4607,
4607,
4607,
4607,
0,
0,
0,
618,
767,
804,
4607,
421,
3879,
3879,
3881,
3880,
3892
],
[
4607,
4607,
4607,
4607,
0,
0,
0,
618,
767,
804,
4607,
421,
3879,
3879,
3881,
3880,
3892
],
[
4649,
4649,
4649,
4649,
602,
602,
602,
0,
363,
399,
4649,
329,
3855,
3855,
3857,
3856,
3868
],
[
4783,
4783,
4783,
4783,
736,
736,
736,
352,
0,
83,
4783,
456,
3989,
3989,
3991,
3990,
4002
],
[
4827,
4827,
4827,
4827,
779,
779,
779,
396,
85,
0,
4827,
500,
4032,
4032,
4034,
4033,
4045
],
[
0,
0,
0,
0,
4723,
4723,
4723,
4836,
4985,
5022,
0,
4685,
1980,
1980,
2111,
1981,
2099
],
[
4525,
4525,
4525,
4525,
423,
423,
423,
341,
478,
514,
4525,
0,
3754,
3754,
3756,
3755,
3767
],
[
2070,
2070,
2070,
2070,
3962,
3962,
3962,
4075,
4223,
4241,
2070,
3925,
0,
0,
2,
1,
13
],
[
2070,
2070,
2070,
2070,
3962,
3962,
3962,
4075,
4223,
4241,
2070,
3925,
0,
0,
2,
1,
13
],
[
2068,
2068,
2068,
2068,
3965,
3965,
3965,
4078,
4225,
4244,
2068,
3928,
3,
3,
0,
2,
10
],
[
2069,
2069,
2069,
2069,
3963,
3963,
3963,
4076,
4224,
4242,
2069,
3927,
1,
1,
1,
0,
12
],
[
2057,
2057,
2057,
2057,
3976,
3976,
3976,
4090,
4237,
4256,
2057,
3940,
15,
15,
11,
14,
0
]
],
"time_windows": [
[
21600,
36000
],
[
21600,
36000
],
[
21600,
36000
],
[
21600,
36000
],
[
28800,
43200
],
[
28800,
43200
],
[
28800,
43200
],
[
50400,
57600
],
[
28800,
36000
],
[
28800,
36000
],
[
21600,
36000
],
[
50400,
57600
],
[
21600,
72000
],
[
21600,
72000
],
[
21600,
72000
],
[
21600,
72000
],
[
21600,
72000
]
],
"demand_weight": [
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
50.0,
100.0,
80.0,
80.0,
100.0,
75.0,
0.0,
0.0,
0.0,
0.0,
0.0
],
"demand_volume": [
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
25.0,
25.0,
25.0,
50.0,
75.0,
25.0,
0.0,
0.0,
0.0,
0.0,
0.0
],
"demand_pallet": [
0.0,
0.0,
0.0,
0.0,
0.0,
0.0,
1.0,
1.0,
1.0,
2.0,
3.0,
1.0,
0.0,
0.0,
0.0,
0.0,
0.0
],
"load_description": [
NaN,
NaN,
NaN,
NaN,
NaN,
NaN,
"interesting",
"why not?",
"testing",
"echo\nbye!",
"test\nhello\ngoodbye",
"fascinating",
NaN,
NaN,
NaN,
NaN,
NaN
],
"load_time": [
1800,
1800,
1800,
1800,
1200,
1200,
1200,
900,
900,
900,
1800,
900,
0,
0,
0,
0,
0
],
"unload_time": [
1200,
1200,
1200,
1200,
900,
900,
900,
600,
600,
600,
1200,
600,
0,
0,
0,
0,
0
],
"allowed_vehicles": [
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
],
[
0,
1,
2,
3,
4
]
],
"vehicle_type": [
"van",
"van",
"truck",
"truck",
"truck"
],
"vehicle_capacity_weight": [
3500,
4650,
4300,
7200,
17000
],
"vehicle_capacity_volume": [
260,
480,
800,
950,
1700
],
"vehicle_capacity_pallet": [
2,
3,
8,
8,
12
],
"cost_per_mi": [
1.0,
1.25,
2.0,
2.25,
2.5
],
"cost_per_stop": [
5,
5,
5,
5,
5
],
"cost_per_hub_to_hub": [
50,
50,
50,
50,
50
],
"num_vehicles": 5,
"pickups_deliveries": [
[
0,
6
],
[
1,
7
],
[
2,
8
],
[
3,
9
],
[
4,
10
],
[
5,
11
]
],
"pickups": [
0,
1,
2,
3,
4,
5
],
"start": [
12,
13,
14,
15,
16
],
"end": [
12,
13,
14,
15,
16
],
"partial_routes": [
[],
[
0,
1
],
[],
[],
[]
]
}