Solving CVRPTW using OR Tools in Python
Introduction
This article is about solving well known optimization problem of Vehicle Routing. Though, there are multifarious platforms offering helps to solve various variants of the Vehicle Routing Problem (VRP), here we are going to look at VRP with restrictions on vehicle capacities and operating hours of destination nodes (Customers) as well as the hubs.
In this article we will see how to leverage OR tools to solve this problem in Python. I will be using PyCharm to code the model and .xlsx file to support the input data and finally, we will get the output in .xlsx file.
The Problem Statement
Let us begin with the problem we have in hand. Here we are going to pick up an example of Capacitated Vehicle Routing Problem with Time Window (CVRPTW).
- A pharmaceutical manufacturer wants to serve hospitals, pharmacies, clinic centers and other customers in Italy. There are a total of ~300 customer points across the nation and major hubs located in ‘Milan’ and ‘Rome’. Where Milan primarily serves the northern Italy and Rome serves the southern part. The manufacturer serves three category of products namely — Dry, Refrigerated and Frozen. Therefore, different types of vehicles like Frozen van, Refrigerated SUVs and other trucks (with average speed assumed as 60km/hr) are needed to serve the products. Although, in some cases multiple products can be combined and send through a single vehicle using special arrangements. Additionally, customers hold operating time and it is highly constraint to serve the products within respective time windows. Both the hub operates 24/7.
From above example, I will show you how to create routes of different vehicles only for Milan city and respective customers. The model also helps us with the fleet loading.
The Model — OR Tools & Python
As stated above, OR Tools are used to solve above problem in Python. For more information about OR Tools you can use below link:
Installing Packages:
The best method to install ‘ortools’ package in PyCharm is explained in below snapshot. One simply needs to search for ortools in the search menu of tab ‘Python Packages’ and click the install button that appears on the top-right
The Code:
Now since we have the package in our system, we are set to begin the most thrilling part — Coding
We will begin with importing the required packages and setting up the working directory:
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import pandas as pd
# setting up working directory
import os
os.getcwd()
os.chdir(directory address)Data Inputs: Next step is to import the data of ‘Demands’, ‘Time windows’, ‘Vehicle capacities’, ‘Distance matrix’ and ‘Time matrix’. Once done we will create a data model combining all the data points as shown below:
demandLB = import demand in pounds ('Customers', 'Demand(LB)')time_windows = import opening and closing hours of Hub and customers ('Site', 'OpenHours', 'CloseHours') - Format 1300 for 01:00 PM, 0000 for 12:00 AM and so on (the code accepts only Int)vehicle_capacitiesLB = import vehicle capacities in pounds ('Vehicle','Capacity(LB)') - user can define multiple vehicles of same capacity as multiple entries and vice versadistanceMatrix = import distance matrix that includes hub and customersTimeMatrix = import time matrix based on average speed of a vehicle - it should be in sync with the time windows format (hour to hour and minutes to minutes)# Storing all data into one data model - the function below returns set of all data points combineddef create_data_model():
data = {}
data['time_matrix']= TimeMatrix
data['time_windows']= time_windows
data['distance_matrix']= distanceMatrix
data['demandLB']= demandLB
data['vehicle_capacitiesLB']= vehicle_capacitiesLB
data['depot']= 0
return data
Problem Formulation: The code below details about defining objective function, creating variables & constraints and solve the model (OR tools use heuristics to solve the VRP, and there are several heuristics available to choose from — LINK ):
# Defining main() function
def main():
data = create_data_model() #Create node index to variable index mapping
manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']), len(data['vehicle_capacitiesLB']), data['depot']) # Create Routing Model
routing = pywrapcp.RoutingModel(manager)
# Create and register a transit callback
def time_callback(from_index, to_index):
"""Returns the travel time 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_callback_index = routing.RegisterTransitCallback(time_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Time Windows constraint.
time = 'Time'
routing.AddDimension(
transit_callback_index,
120, # allow waiting time (min)
900, # maximum time (min) per vehicle in a route (8 hours)
False, # Don't force start cumul to zero.
time)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot - (one can define time window constraints for depot as well by small modifications in below code) for location_idx, time_window in enumerate(data['time_windows']):
if location_idx == data['depot']:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
depot_idx = data['depot']
for vehicle_id in range(len(data['vehicle_capacitiesLB'])):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data['time_windows'][depot_idx][0],
data['time_windows'][depot_idx][1])
# Instantiate route start and end times to produce feasible times.
for i in range(len(data['vehicle_capacitiesLB'])):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i)))
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i)))
# Add Capacity Weight constraint.
def demand_callbackLB(from_index):
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['demandLB'][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callbackLB)
# Add Vehicle capacity weight Contraint
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data['vehicle_capacitiesLB'], # vehicle maximum capacities
True, # start cumul to zero
'Capacity')
# 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)
In above code, the optimization algorithm looks into the time matrix and find best solution to load the vehicles and deliver to customers without violating the defined constraints. Additionally, one can use distance matrix or cost matrix as optimization criteria, that way we can capture the impact of variable cost on the model solution.
Finally, we are using ‘PATH_CHEAPEST_ARC’ heuristics to solve the problem.
Solution: We need to create a function to print the solution. Function below takes in input data and solution generated from the model and print the results in desired format.
# function to print the results/solution
def print_solution(data, manager, routing, solution):
print(f'Objective: {solution.ObjectiveValue()}') # the objective function
time_dimension = routing.GetDimensionOrDie('Time')
total_time = 0
total_distance = 0
total_loadLB = 0
total_loadM3 = 0
for vehicle_id in range(len(data['vehicle_capacitiesLB'])):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
loading_output = 'Load for vehicle {}:'.format(vehicle_id)
route_distance = 0
route_loadLB = 0
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += '{0} Time({1},{2}) -> '.format(
manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var))
index = solution.Value(routing.NextVar(index))
node_index = manager.IndexToNode(index)
route_loadLB += data['demandLB'][node_index]
loading_output += ' {0} Load({1}) -> '.format(node_index, route_loadLB)
previous_index = index
route_distance += routing.GetArcCostForVehicle(previous_index, index, vehicle_id)
time_var = time_dimension.CumulVar(index)
plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index),
solution.Min(time_var),
solution.Max(time_var))
plan_output += 'Time of the route: {}min\n'.format(solution.Min(time_var))
plan_output += 'Distance of the route: {}m'.format(route_distance)
loading_output += 'Load of the route: {}'.format(route_loadLB)
print(plan_output)
print(loading_output)
total_distance += route_distance
total_loadLB += route_loadLB
total_time += solution.Min(time_var)
print('Total time of all routes: {}min'.format(total_time))
print('Total distance of all routes: {}m'.format(total_distance))
print('Total load of all routes: {}'.format(total_loadLB))Results: Based on the data explained at the beginning, we get below result from our code:
Above is how the solution looks like if we print it in PyCharm console. One can easily do the modifications in above discussed function and generate solution in .xlsx format (or any other). I am leaving this part to the readers to take up a challenge and modify the code above to generate solution in their desired format.
BONUS: The best thing about using OR-tools is, one with basic knowledge of python can easily use this tool to solve VRP problems. There are many more one can do with the above code to meet his/her industry need. We can perform some routing tasks such as:
1. Time limit: By using below code in main() function, we can converge the model by time
search_parameters.time_limit.seconds = 30
2. Search limit: If the requirement is to converge the model based on number of solutions it can generate, below code comes handy:
search_parameters.solution_limit = 100
If you are searching for the dataset, due to limitations on the medium platform, I cannot upload the dataset. If you need the dataset or any help in understanding above code or any other assistance you can email me at satpalc80@gmail.com.
If you have read it till here, please don’t forget to share it with your fellow members. Your sharing will encourage me to post more about industrial scale OR based solutions using open source platforms. Happy coding!!!
