|
#!/usr/bin/env python3 |
|
from __future__ import print_function |
|
from ortools.constraint_solver import routing_enums_pb2 |
|
from ortools.constraint_solver import pywrapcp |
|
import numpy as np |
|
import math |
|
|
|
def create_data_model(): |
|
"""Stores the data for the problem.""" |
|
data = {} |
|
fuel = 180 |
|
_locations = [ |
|
(0, 2), # start depot |
|
(1, 2), |
|
(2, 2), |
|
(3, 2), |
|
(4, 2), |
|
(5, 2), # end depot |
|
(5, 2), |
|
(1, 3), # locations to visit |
|
(2, 4), |
|
(3, 1), |
|
(4, 0)] |
|
data["locations"] = [(l[0] * 50, l[1] * 50) for l in _locations] |
|
data["num_locations"] = len(data["locations"]) |
|
data["time_windows"] = [ |
|
(0, 0), # start depot |
|
(0, 5), |
|
(4, 10), |
|
(6, 15), |
|
(12, 20), |
|
(8, 13), # end depot |
|
(8, 13), |
|
(0, 3), |
|
(7, 9), |
|
(10, 13), |
|
(14, 15)] |
|
data["num_vehicles"] = 2 |
|
data["fuel_capacity"] = fuel |
|
data["vehicle_speed"] = 10 |
|
data["starts"] = [0, 0] |
|
data["ends"] = [5, 5] |
|
distance_matrix = np.zeros((data["num_locations"], data["num_locations"]), dtype=int) |
|
for i in range(data["num_locations"]): |
|
for j in range(data["num_locations"]): |
|
if i == j: |
|
distance_matrix[i][j] = 0 |
|
else: |
|
distance_matrix[i][j] = euclidean_distance(data["locations"][i], data["locations"][j]) |
|
dist_matrix = distance_matrix.tolist() |
|
data["distance_matrix"] = dist_matrix |
|
assert len(data["distance_matrix"]) == len(data["locations"]) |
|
assert len(data["distance_matrix"]) == len(data["time_windows"]) |
|
assert len(data["starts"]) == len(data["ends"]) |
|
return data |
|
|
|
|
|
def euclidean_distance(position_1, position_2): |
|
return int(math.hypot((position_1[0] - position_2[0]), (position_1[1] - position_2[1]))) |
|
|
|
|
|
def print_solution(data, manager, routing, solution): |
|
print("Objective: {}".format(solution.ObjectiveValue())) |
|
total_distance = 0 |
|
total_load = 0 |
|
total_time = 0 |
|
fuel_dimension = routing.GetDimensionOrDie("Fuel") |
|
time_dimension = routing.GetDimensionOrDie("Time") |
|
dropped_nodes = "Dropped nodes:" |
|
for node in range(routing.Size()): |
|
if routing.IsStart(node) or routing.IsEnd(node): |
|
continue |
|
if solution.Value(routing.NextVar(node)) == node: |
|
dropped_nodes += " {}".format(manager.IndexToNode(node)) |
|
print(dropped_nodes) |
|
for vehicle_id in range(data["num_vehicles"]): |
|
index = routing.Start(vehicle_id) |
|
plan_output = "Route for vehicle {}:\n".format(vehicle_id) |
|
distance = 0 |
|
while not routing.IsEnd(index): |
|
fuel_var = fuel_dimension.CumulVar(index) |
|
time_var = time_dimension.CumulVar(index) |
|
plan_output += "{0} Fuel({1}) Time({2},{3}) ->".format(manager.IndexToNode(index), solution.Value(fuel_var), |
|
solution.Min(time_var), solution.Max(time_var)) |
|
previous_index = index = solution.Value(routing.NextVar(index)) |
|
distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id) |
|
fuel_var = fuel_dimension.CumulVar(index) |
|
time_var = time_dimension.CumulVar(index) |
|
plan_output += "{0} Fuel({1}) Time({2},{3}) ->".format(manager.IndexToNode(index), solution.Value(fuel_var), |
|
solution.Min(time_var), solution.Max(time_var)) |
|
plan_output += "Distance of the route: {}units\n".format(distance) |
|
plan_output += "Fuel of the route: {}\n".format(solution.Value(fuel_var)) |
|
plan_output += "Time of the route: {}\n".format(solution.Value(time_var)) |
|
print(plan_output) |
|
total_distance += distance |
|
total_load += solution.Value(fuel_var) |
|
total_time += solution.Value(time_var) |
|
print('Total Distance of all routes: {}units'.format(total_distance)) |
|
print('Total Fuel consumed of all routes: {}'.format(total_load)) |
|
print('Total Time of all routes: {}units'.format(total_time)) |
|
|
|
|
|
def main(): |
|
# Instantiate the data problem. |
|
data = create_data_model() |
|
|
|
# Create the routing index manager. |
|
manager = pywrapcp.RoutingIndexManager(len(data["distance_matrix"]), |
|
data["num_vehicles"], data["starts"], data["ends"]) |
|
|
|
# Create Routing Model. |
|
routing = pywrapcp.RoutingModel(manager) |
|
|
|
# Distance |
|
def distance_callback(from_index, to_index): |
|
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) |
|
|
|
# Fuel |
|
def fuel_callback(from_index, to_index): |
|
from_node = manager.IndexToNode(from_index) |
|
to_node = manager.IndexToNode(to_index) |
|
return -euclidean_distance(data["locations"][from_node], data["locations"][to_node]) |
|
|
|
fuel_callback_index = routing.RegisterTransitCallback(fuel_callback) |
|
routing.AddDimension( |
|
fuel_callback_index, |
|
data["fuel_capacity"], |
|
data["fuel_capacity"], |
|
True, |
|
'Fuel') |
|
penalty = 500 |
|
fuel_dimension = routing.GetDimensionOrDie('Fuel') |
|
for i in range(len(data["distance_matrix"])): |
|
if i == 0 or i == 5: # Depot |
|
continue |
|
if i > 5: # Locations |
|
index = manager.NodeToIndex(i) |
|
fuel_dimension.SlackVar(index).SetValue(0) |
|
routing.AddVariableMinimizedByFinalizer(fuel_dimension.CumulVar(i)) |
|
#routing.AddDisjunction([index], penalty) |
|
else: # refuel stations |
|
index = manager.NodeToIndex(i) |
|
routing.AddDisjunction([index], penalty) |
|
|
|
# Time |
|
def time_callback(from_index, to_index): |
|
from_node = manager.IndexToNode(from_index) |
|
to_node = manager.IndexToNode(to_index) |
|
return data["distance_matrix"][from_node][to_node] / data["vehicle_speed"] |
|
|
|
time_callback_index = routing.RegisterTransitCallback(time_callback) |
|
routing.AddDimension( |
|
time_callback_index, |
|
300, |
|
300, |
|
False, |
|
'Time') |
|
time_dimension = routing.GetDimensionOrDie('Time') |
|
for location_idx, time_window in enumerate(data["time_windows"]): |
|
if location_idx == 0 or location_idx == 5: # Depot |
|
continue |
|
index = manager.NodeToIndex(location_idx) |
|
time_dimension.CumulVar(index).SetRange( |
|
time_window[0], |
|
time_window[1]*10) |
|
routing.AddToAssignment(time_dimension.SlackVar(index)) |
|
# Add time window constraints for each vehicle start node |
|
# and "copy" the slack var in the solution object (aka Assignment) to print it |
|
for vehicle_id in range(data["num_vehicles"]): |
|
index = routing.Start(vehicle_id) |
|
time_dimension.CumulVar(index).SetRange(data["time_windows"][0][0], data["time_windows"][0][1]) |
|
routing.AddToAssignment(time_dimension.SlackVar(index)) |
|
|
|
for i in range(data['num_vehicles']): |
|
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i))) |
|
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i))) |
|
|
|
# Setting first solution heuristic. |
|
search_parameters = pywrapcp.DefaultRoutingSearchParameters() |
|
search_parameters.first_solution_strategy = ( |
|
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) |
|
|
|
# Solve the problem. |
|
solution = routing.SolveWithParameters(search_parameters) |
|
|
|
# Print solution on console. |
|
if solution: |
|
print_solution(data, manager, routing, solution) |
|
|
|
print("Solver status:", routing.status()) |
|
|
|
|
|
if __name__ == '__main__': |
|
main() |
