Capacitated Vehicle Routing Problem (CVRP) Optimization using Google-OR Tools and Python
Introduction
Linear Programming Problems (LPP) represent one of the most robust and powerful algorithmic approaches for solving numerous contemporary real-world issues. In this specific project, we address Vehicle Routing Problems (VRP), which generalize the Traveling Salesman Problem (TSP), a prominent area within Linear Programming and Optimization. VRP stands as a leading research domain and is esteemed within the realm of Advanced Operations Research.
The literature surrounding VRP encompasses multiple variations, among which we consider one of the pivotal papers that laid the foundation for Capacitated Vehicle Routing Problems (CVRP), authored by Achchutan et al.
Problem Statement
In this hypothetical yet realistic problem scenario, we consider a situation where banks employ multiple Cash-In-Transit (CIT) vehicles for the daily transportation of cash between cash chests and bank branches. Bank branches make frequent requests, nearly on a daily basis, for either cash to be delivered from the chest to the branch or to be collected from the branch and returned to the chest, sometimes both. These requirements are fulfilled by multiple dedicated CIT vehicles allocated to each cash chest.
Currently, each of these vehicles comes with a substantial monthly cost, covering a limited number of kilometers. Additional charges apply if any vehicle exceeds the predefined monthly kilometer limit. The primary objective of this problem is to minimize these costs to the greatest extent possible.
Background for CVRP
The Vehicle Routing Problem (VRP) is an extension of the classic Traveling Salesman Problem (TSP). TSP serves as a fundamental problem for students embarking on coding courses that involve data structures and algorithms. It holds equal importance for mathematicians and operations research scientists, often serving as one of the initial challenges in linear programming assignment and transportation problems.
To grasp the generalization of VRP from TSP, it’s essential to understand the nature of the Traveling Salesman Problem. TSP deals with a list of cities and the distances between each pair of them. Its objective is to determine the shortest path or route that allows for visiting each city once and returning to the original starting point. This problem can be tackled by a single person or vehicle, without any constraints on their travel time, distance, or the number of cities covered.
For example, if the total travel time for a given path is 30 hours, covering a distance of 500 kilometers while visiting 30 cities, it can be managed by a single entity. However, if constraints are introduced on any of the three parameters — distance, time, or the maximum number of cities — such as having only 24 hours of travel time available, a maximum distance limit of 300 kilometers, or a restriction to cover a maximum of 20 cities, the problem becomes infeasible. In linear programming terms, this is referred to as an “Infeasible Solution.”
In such cases, the only viable solution is to introduce a new individual or vehicle to fulfill the task while ensuring the shortest possible total distance. This situation gives rise to the Vehicle Routing Problem (VRP), which arises from the generalization of the conditions and objectives from a single vehicle to multiple vehicles. Hence, VRP can be considered a generalization of the Traveling Salesman Problem (TSP).
Data and Constraints
Data:
- The amount of cash requested by each branch, measured in Lakhs of Rupees, for both cash drops from the Cash Chest and pickups to the Cash Chest on a daily basis, was forecasted using time series prediction models to anticipate the demands for the following day
2. Matrix of Distances between each branch (in Kms)
Some constraints assumed are as follows:
- Average Speed of the vehicles in a chest — 60Kmph
2. Service Time or Halt Time at each Branch for the vehicle— 25 Minutes
3. Maximum cash that can be in a CIT vehicle at any point – Rs. 5Cr
4. Time Limit for vehicles (Must operate between) – 07:30 AM IST to 06:30 PM IST
Mathematical Formulation of VRP
In the Vehicle Routing Problem (VRP), we make assumptions that entail multiple vehicles departing from a central source, visiting various cities, and eventually returning to the depot. Each city is visited only once, by a single vehicle, and every vehicle must visit at least one city. Additionally, each city, denoted as ‘j,’ has a commodity demand represented by ‘Qj,’ and we have ‘V’ vehicles at our disposal, each with a capacity of ‘W.’ In most cases, the primary objective is to minimize the total distance traveled by all the vehicles combined.
When there are ’N’ cities to be covered, our graph consists of ‘N+2’ nodes, where ‘N+1’ serves as the initial depot (source), and ‘N+2’ functions as the final depot (destination), which is essentially the same as the source, serving an intuitive purpose
Constraint 1 guarantees that every node is accessible either from the source node or other city nodes. Constraint 2 ensures that from each city node, we must proceed to another city or reach the final destination (N+2). Constraints 3 and 4 ensure that exactly ‘V’ vehicles depart from the source and reach the destination. Constraint 5 is a binary restriction, set to 1 when a route exists between nodes and 0 otherwise.
Constraints 6 and 7 are in place to maintain that the load on a vehicle does not surpass the vehicle’s capacity denoted by ‘W.’ These constraints are further elucidated with visual representations in the accompanying image below.
When examining constraints 1 and 2, let’s focus on node 1 as depicted in the diagram above. Constraint 1 specifies that the summation of yellow and red lines entering node 1 should equal 1, and this applies uniformly to all nodes. Similarly, Constraint 2 dictates that the summation of violet and green lines departing from node 1 should be 1, extending this requirement to all nodes.
Constraint 3 designates that the number of yellow lines departing from N+1 must equal ‘V.’ Correspondingly, Constraint 4 stipulates that the number of green lines entering N+2 should be ‘V.’
Furthermore, Constraint 5 mandates that each line in the illustrated diagram represents a binary variable, assuming a value of 0 if the connection does not exist, and 1 if the connection is present
Limitations of VRP
VRP is classified as an NP-Hard problem, signifying that it cannot be efficiently solved within polynomial computational time when dealing with graphs containing a substantial number of nodes. In the context of a graph encompassing ’N’ cities, the count of potential forward journey paths between nodes ascends to N!/2. Within our specific scenario, where each chest is linked to approximately 100–200 branches, the result is an astounding count of over 10,157 possible paths. The table below illustrates the exponential growth in problem size.
Hence, the formulation described above renders it unfeasible to solve our problem within polynomial time. This predicament is precisely why researchers advocate employing initial solution strategies and metaheuristics.
First Solution and Meta Heuristics
Optimization solvers begin by striving to find a feasible solution within the specified constraints. In this problem, we employed the PATH_CHEAPEST_STRATEGY for the solver’s initial phase to establish a feasible solution. It initiates from a “start” node and connects it to the node that yields the most cost-effective route segment. The route is then extended by iteratively adding the last node to the route. Subsequently, the solver employs metaheuristics to iteratively refine the initial solution, gradually progressing toward the optimization objective. Throughout this process, the solver continuously modifies the initial solution and evaluates whether there is an enhancement in the objective value. If an improvement is detected, this becomes the new solution.
Furthermore, we have the flexibility to set a time limit for the optimizer. I utilized the GUIDED_LOCAL_SEARCH metaheuristic to enhance the initial solution. Several experiments were conducted with different time constraints for the solver. Although various strategies are available to reach both the initial and optimized solutions, the ones mentioned above are preferred for our specific problem. In the results presented in this document, the optimizer ran for 120 seconds.
VRP Problem Modelling
Within Google OR-Tools, VRP inherently focuses on minimizing the total distance traveled by all the vehicles combined. However, in our specific case, our primary goal is to minimize the number of vehicles employed. To achieve this objective, we employ a penalty-based approach. It is structured in a way that, for each new vehicle departing from the chest as part of the solution, a substantial penalty (10 Lacs) is imposed upon the objective function. This penalty significantly influences the solver to utilize the fewest possible vehicles while still complying with the constraints and fulfilling the demands.
Constraint Modelling
In our problem, we grapple with two significant constraints, distinct from the original VRP constraints. Below, you’ll find the details of these constraints and how they are represented in our model. For handling these constraints, we harness a feature provided by OR-Tools known as “dimension,” which assists in constraint modeling.
Vehicle Capacity: 5 Crores INR. This constraint stipulates that the cash load in any vehicle must not exceed 5 Crores INR at any given point in time. This guideline is set forth by the Ministry of Finance in India. Given that these capacity constraints pertain to the cash carried by the vehicle, which accumulates as the route progresses, we need to establish a dedicated dimension to account for these capacities.
Time Constraint: 7:30 AM to 6:30 PM. The CIT vehicles operate within a specific time window, from 7:30 AM to 6:30 PM, amounting to a total of 11 hours or 660 minutes, during which they must complete their cash drops and pickups for the day. This time allocation considers a 60-minute lunch break for the vehicle staff. Hence, the effective travel time available for the vehicles is 600 minutes, which is divided into 300 minutes each for the forward and return journeys. The enforcement of this constraint relies on other critical inputs, such as the duration of vehicle halts at branches and the average vehicle speed.
Time taken by a vehicle (T) = n * t + d/s
where n = number of branches on the route of the vehicle,
t = Halt time or service time at each branch in minutes,
d = total distance of the route in meters,
s = average speed of the vehicle in meters/minute
This is added as a new dimension to the problem stating T ≤ 300 for respective forward and return journeys.
Experimentation and Results
We’ve implemented the model and formulation described above using Python 3.7 with the Google OR-Tools library. For testing purposes, we chose Mumbai as the city. We collected data on the locations of 100 different branches within Mumbai by scraping information from Google Maps, which provided us with their respective latitudes and longitudes. Using these geographic coordinates as input for the Open Source Routing Machine (OSRM), we extracted the routable distances between each pair of branches, resulting in a 100x100 distance matrix. The branch locations and distances are available in the attached Excel file.
While solving for forward routes, we set distances from all branches to the cash chest as ‘0’ because all vehicle journeys should conclude at their respective last branches.
To ensure a comprehensive understanding of the solution, we considered two different distributions for cash requirements. The first distribution consists of random amounts between 50,000 and 20 Lakhs (small amounts), while the second distribution features higher-end values (large amounts) to assess sensitivity and dependencies. These distributions are also provided in the Excel file and on Kaggle.
It’s important to input a higher number of vehicles than are actually available because the initial solution is not optimized. The solver first seeks to obtain a feasible solution and then proceeds to optimize it. We used 30 vehicles for this problem.
The Python code for forward and return routes can be found on Kaggle, with the implementation of the methods methodized for ease of use. During each experimentation, I executed the code in a Kaggle notebook, which offers a cloud server with 16GB of RAM. A sample output when running the code for forward routes is displayed in the image below.
In the sample output image above, Vehicle 3 starts at the cash chest represented by ‘0’, and since there is no cash requirement, its load is ‘0’. From the cash chest, Vehicle 3 proceeds to Branch 16, where the cash requirement is calculated as the difference between the current branch’s load and the previous branch’s load, which is (1,505,605.0–0) = 1,505,605. From Branch 16, the vehicle then travels to Branch 64, where the cash requirement is (2,340,116–1,505,605) = 834,511. These cash requirement values are cumulatively added to the load to ensure that the cash in the vehicle does not exceed the vehicle’s capacity of 5 Crores. You can cross-verify the requirements at branches 16 and 64 from the attached Excel sheet, which contains drop and pickup amounts generated using random numbers ranging from 50,000 to 20 Lakhs.
The total distance of the route is given as 1,054,573 meters, out of which 1,000,000 (10 Lakhs) is a penalty. Therefore, the actual distance traveled by Vehicle 3 is 54,573 meters. The load of the vehicle represents the total cash transported by the vehicle, and it remains within the capacity limits.
Vehicle 4 is not used in this problem because using it would increase the total objective value of the problem by at least the amount of the penalty.
Forward Routes for Small Amounts Data (Total Cash Requirement: 9.8 Cr)
This table provides the traversal routes of the vehicles and the number of vehicles required, while adhering to all the constraints mentioned. In this specific case, the cash requirement is relatively small, but the time limit available for the vehicles (300 minutes) is exceeded, resulting in a larger number of vehicles being required. If only capacity is the constraint, 9.8 Crores can be served by just 2 CIT vehicles, given that each vehicle has a capacity of 5 Crores.
The endpoints in bold should be used as input for the return journey model to specify where the vehicles should start their return journeys.
Return Routes for Small Amounts Data (Total Cash Requirement: 13.9 Cr)
For the return journey, no new vehicles are introduced because all the pickup requirements can be managed by the same 10 vehicles that were used in the forward journey. These 10 vehicles are utilized for the return journey as they need to return to the cash chest (Destination) by 06:30 PM.
Forward Routes for Large Amounts Data (Total Cash Requirement: 49.7 Cr)
In this scenario, one additional vehicle is being utilized compared to the small amounts data due to capacity constraints being exceeded. Time constraints are not the limiting factor in this case. As with the forward journey, it’s important to provide the starting and ending points as input for the return model, which involves picking up cash from various branches and returning to the cash chest.
Return Routes for Large Amounts Data (Total Cash Requirement: 56.6 Cr)
In this case, we can observe that one additional vehicle was used for the return routes compared to the forward routes. Vehicle 4 started from the cash chest to fulfill specific requirements. The total cash to be picked up from different branches amounts to 56.6 Cr, and to meet this requirement, a minimum of 12 vehicles with a capacity of 5 Cr each is needed. Since only 11 vehicles were used in the forward route, all of them will be utilized, and the additional requirement will be met by employing a new vehicle that starts from the cash chest and returns by 06:30 PM.
Sensitivity Analysis
In all the cases mentioned above, we observed that the number of vehicles used ranged from 11 to 12. This is approximately the same number of vehicles used on a daily basis in the Mumbai chest, which is the focus of this pilot project. At first glance, it might seem that the solution hasn’t brought about any improvement over the current usage. However, it’s important to note that, on a daily basis in this chest, only 50%-60% of all the 100 branches are being visited, whereas in our problem, we visited 100% of the branches with the same number of vehicles. Therefore, there are multiple factors, like this one, that can significantly impact the number of vehicles used. Below, we explore some of these factors and their effects on the solution, specifically, the number of vehicles required.
The factors we considered that can have a substantial impact are:
- Speed of the vehicle: The team has provided a standard speed of 60 Kmph, but this can vary significantly depending on the location of the cash chest and branches, particularly in metro and non-metro areas.
- Halt Time at Branches: Currently, we use 25 minutes as the service time at branches when a vehicle visits a branch to drop off or pick up cash.
This analysis has been conducted for both small and large amounts datasets, and the total number of optimized vehicles used in each scenario is presented below.
As demonstrated in the tables above, it’s evident that the cost of operating the vehicles can potentially be reduced by half in an optimistic scenario. Achieving a significant reduction in costs is possible by minimizing the halt time at branches through improved staff efficiency. However, it’s important to note that the original cash requirements typically fall somewhere between the values of the small and large datasets. While the speed of vehicles remains a constant, it’s worth considering the impact of vehicle speed based on the specific location of the cash chest and branches.
Code Implementation and the associated Datasets on Kaggle
The working code on kaggle, associated datasets can be accessed here.
References
1. N.R. Achutan and L. Caccetta, “Integer Linear Programming Formulation for a Vehicle Routing Problem”, European Journal of Operations research 1991.
2. Google OR-Tools: https://developers.google.com/optimization/ Last Accessed: 22nd June 2020
3. Travelling Salesman Problem: https://www.csd.uoc.gr/~hy583/papers/ch11.pdf
4. Limitation: https://www.youtube.com/watch?v=kserookKlLM LA: 22nd June, 2020
5. GUIDED_LOCAL_SEARCH: http://en.wikipedia.org/wiki/Guided_Local_Search LA: 22nd June 2020