-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathvrp.py
180 lines (151 loc) · 7.5 KB
/
vrp.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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
"""Vehicle Routing Problem"""
from __future__ import print_function
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
import math
import json
#time for tester
import time
import vrp_data_problem as data_problem
import vrp_printer as printer
import vrp_constraints
def return_lambda_gateway_response(code, body):
"""
This function wraps around the endpoint responses in a uniform and Lambda-friendly way
:param code: HTTP response code (200 for OK), must be an int
:param body: the actual content of the response
"""
return {"statusCode": code, "body": json.dumps(body)}
def get_routing_assignment(data, routing, assignment, distance_matrix, violated_points):
cluster = []
violated_cluster = []
for vehicle_id in xrange(data.num_vehicles):
if routing.IsVehicleUsed(assignment, vehicle_id):
index = routing.Start(vehicle_id)
if data.transport_mode == "N1":
index = assignment.Value(routing.NextVar(index))
route_dist = 0
route_load = 0
route = []
while not routing.IsEnd(index):
node_index = routing.IndexToNode(index)
next_node_index = routing.IndexToNode(
assignment.Value(routing.NextVar(index)))
route_dist += distance_matrix[node_index][next_node_index]
route_load += data.parcels[node_index]
route.append([data.locations[node_index][0], data.locations[node_index][1]])
index = assignment.Value(routing.NextVar(index))
if data.transport_mode != "1N1":
node_index = routing.IndexToNode(index)
route.append([data.locations[node_index][0], data.locations[node_index][1]])
if (data.maximum_distance != 0 and route_dist > data.maximum_distance) or (route_load < data.min_parcels):
violated_cluster.append(route)
else:
cluster.append(route)
return {
"cluster": cluster,
"violated_points": violated_points,
"violated_cluster": violated_cluster
}
def handle(event, context):
start_time = time.time()
"""Entry point of the program"""
# Instantiate the data problem.
try:
body = event.get('body')
event = json.loads(body)
locations = event["points"]
min_parcels = event.get("min_parcels", 0)
maximum_distance = event.get("max_distance", 0)
num_vehicles = event["vehicle_num"]
min_vehicles = event.get("min_vehicles", False)
max_parcels = event.get("max_parcels", 20)
transport_mode = event["transport_mode"]
distance_calculation = event.get("distance_calculation", "VINCENTY")
except KeyError as e:
print("Missing required input: " + str(e))
cluster = {"title": "Missing required input: " + str(e)}
return return_lambda_gateway_response(400, cluster)
if min_parcels < 0 or maximum_distance < 0 or num_vehicles < 0 or max_parcels < 0:
cluster = {"title": "Numerical input cannot be negative"}
return return_lambda_gateway_response(400, cluster)
if transport_mode != "1N" and transport_mode != "N1" and transport_mode != "1N1":
cluster = {"title": "Invalid transport_mode"}
return return_lambda_gateway_response(400, cluster)
if distance_calculation != "VINCENTY" and distance_calculation != "OSRM":
cluster = {"title": "Invalid distance_calculation"}
return return_lambda_gateway_response(400, cluster)
if distance_calculation == "OSRM" and len(locations) > 100:
cluster = {"title": "Bad request: OSRM cannot be used with more than 100 points"}
return return_lambda_gateway_response(400, cluster)
data = data_problem.DataProblem(locations, num_vehicles, min_parcels,
max_parcels, maximum_distance, transport_mode, distance_calculation)
# Define weight of each edge
distance = vrp_constraints.CreateDistanceEvaluator(data)
distance_matrix = distance.get_distance_matrix()
distance_evaluator = distance.distance_evaluator
print("Violated points: " + str(distance.get_violated_points))
if len(data.locations) <= 1:
cluster = {
"cluster": [],
"violated_points": distance.get_violated_points,
"violated_cluster": []
}
return return_lambda_gateway_response(200, cluster)
# Create Routing Model
routing = pywrapcp.RoutingModel(data.num_locations, data.num_vehicles, data.depot)
if data.num_locations > 100:
routing.SetArcCostEvaluatorOfAllVehicles(distance.cluster_distance_evaluator)
else:
routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
if maximum_distance != 0:
vrp_constraints.add_distance_dimension(routing, data, distance_evaluator)
# still need when min_parcels = 0 because we have max_parcels
parcels_evaluator = vrp_constraints.CreateParcelsEvaluator(data).parcels_evaluator
vrp_constraints.add_parcels_constraints(routing, data, parcels_evaluator)
# Setting first solution heuristic (cheapest addition).
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.time_limit_ms = 25000
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_MOST_CONSTRAINED_ARC)
#minimize the total number of vehicle
if min_vehicles:
if data.num_vehicles*data.min_parcels >= data.num_locations:
routing.SetFixedCostOfAllVehicles(1000000)
else:
routing.SetFixedCostOfAllVehicles(10000)
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
if assignment is None:
print("change distance to soft constraint")
print("\nThe program took " + str(time.time() - start_time) + " seconds to run")
start_time = time.time()
routing = pywrapcp.RoutingModel(data.num_locations, data.num_vehicles, data.depot)
if data.num_locations > 100:
routing.SetArcCostEvaluatorOfAllVehicles(distance.cluster_distance_evaluator)
else:
routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
if maximum_distance != 0:
vrp_constraints.add_distance_soft(routing, data, distance_evaluator)
parcels_evaluator = vrp_constraints.CreateParcelsEvaluator(data).parcels_evaluator
vrp_constraints.add_parcels_constraints(routing, data, parcels_evaluator)
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.time_limit_ms = 60000
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_MOST_CONSTRAINED_ARC)
if min_vehicles:
if data.num_vehicles*data.min_parcels >= data.num_locations:
routing.SetFixedCostOfAllVehicles(1000000)
else:
routing.SetFixedCostOfAllVehicles(100)
assignment = routing.SolveWithParameters(search_parameters)
if assignment is None:
print("No solution found")
cluster = "No solution found"
else:
cluster = get_routing_assignment(data, routing, assignment, distance_matrix, distance.get_violated_points)
p = printer.ConsolePrinter(data, routing, assignment, distance_matrix)
p.print()
print("\nThe program took " + str(time.time() - start_time) + " seconds to run")
return return_lambda_gateway_response(200, cluster)