-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathsolver_googleOR.py
101 lines (80 loc) · 3.26 KB
/
solver_googleOR.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
"""Simple Pickup Delivery Problem (PDP)."""
from __future__ import print_function
from pprint import pprint
import numpy as np
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
from googleOR_utils import print_solution, solution_to_dict
def create_data_model(hospital):
"""Stores the data for the problem."""
data = {}
# Add shadow node for lab because start/end can't be current delivery location
dummy_lab_indx = len(hospital.locations)
distances = np.zeros(tuple(idx+1 for idx in hospital.distances.shape))
distances[:dummy_lab_indx,:dummy_lab_indx] = hospital.distances
distances[dummy_lab_indx, 1:] = hospital.distances[0,:]
distances[1:, dummy_lab_indx] = hospital.distances[:,0]
data['distance_matrix'] = distances
data['pickups_deliveries'] = [
(
hospital.locations.index(sample.location),
hospital.locations.index(sample.destination)
)
for sample in hospital.samples if not sample.has_arrived()
]
data['num_vehicles'] = len(hospital.porters)
data['end_locations'] = [dummy_lab_indx]*data['num_vehicles']
data['start_locations'] = [
hospital.locations.index(porter.location) or dummy_lab_indx
for porter in hospital.porters
]
return data
def solver(hospital, _=None, max_time=480):
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_model(hospital)
pprint(data)
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data['distance_matrix']),
data['num_vehicles'],
data['start_locations'],
data['end_locations']
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Define cost of each arc.
def distance_callback(from_index, to_index):
"""Returns the manhattan 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)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Distance constraint.
dimension_name = 'Distance'
print(max_time)
routing.AddDimension(
transit_callback_index,
0, # no slack
int(max_time), # vehicle maximum travel distance
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if assignment:
print_solution(data, manager, routing, assignment)
return solution_to_dict(manager, routing, assignment, hospital)
else:
print("Failed")
return None
if __name__ == "__main__":
main()