I am solving the multi-depot multiple vehicles vehicle routing problem using OR-Tools and so far I have managed to set up a model in which one vehicle leaves from each depot and between them they visit each node within their maximum time allowance and then exit via the dummy node 0. However, as this is a real-world problem, at each node the vehicle is required to stop for a set time to carry out a service, with each node having a set waiting time, such as in the table below:
| Node | Duration |
|---|---|
| 4 | 9 |
| 38 | 8 |
| ... | ... |
| 8545 | 17 |
I am unsure how to add these to each node, although the arc lengths between nodes so far represent the travel time between each node (with the assumption that all vehicles are travelling at the same speed). So my question is how I can add these wait times into the model, while still minimizing the travel time for each vehicle and keeping them below their maximum threshold of 25200 seconds (corresponding to a 7-hour shift). I have included my working code below:
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
The distance matrix was fed in from a csv laid out like so:
| Blank | 4 | 38 | 71 | 90 | 94 | ... | 8545 |
|---|---|---|---|---|---|---|---|
| 4 | 0 | 1280 | 1762 | 1406 | 1589 | ... | 1017 |
| 38 | 1280 | 0 | 681 | 202 | 385 | ... | 1433 |
| 71 | 1762 | 681 | 0 | 503 | 0 | ... | 0 |
| 90 | 1406 | 202 | 503 | 0 | 0 | ... | 1559 |
| 94 | 1589 | 385 | 0 | 0 | 0 | ... | 1742 |
| .. | .. | ... | ... | ... | ... | 0 | ... |
| 8545 | 1017 | 1433 | 0 | 1559 | 1742 | ... | 0 |
CareDist_Matrix = np.loadtxt(open("CareDistances-FULL.csv", "rb"), dtype=int, delimiter=",", skiprows=1)
CareDist_Matrix
And the main body of the model follows:
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = CareDist_Matrix
data['num_vehicles'] = 6
data['starts'] = [3, 7, 14, 104, 185, 220]
data['ends'] = [0, 0, 0, 0, 0, 0]
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
max_route_distance = 0
for vehicle_id in range(data['num_vehicles']):
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))
"""Entry point of the program."""
# 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)
# 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
25200, # 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.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
if __name__ == '__main__':
main()