Capacitated Vehicle Routing Problem (CVRP) with Python+Pulp and Google Maps API
The vehicle routing problem (VRP) is a combinatorial and integer programming which ask “What is the optimal set of routes for a fleet of vehicles in order to deliver to a given set of customers?” It generalizes the well-known traveling salesman problem (TSP).
There are many variants of vehicle routing problem. Some popular examples are as follows:
- CVRP (Capacitated Vehicle Routing Problem) : Vehicles have a limited carrying capacity of the goods that must be delivered.
- VRPTW (Vehicle Routing Problem with Time Windows) : The delivery locations have time windows within the deliveries (or visits) must be made.
- VRPPD (Vehicle Routing Problem with Pickup and Delivery) : A number of goods need to be moved from certain pickup locations to other delivery locations. The goal is to find optimal routes for a fleet of vehicles to visit the pickup and drop-off locations.
- VRPP (Vehicle Routing Problem with Profits) : It is a maximization problem where it is not mandatory for vehicles to visit all nodes. The aim is to visit nodes maximize the sum of collected profits under specific circumstances while respecting a given vehicle time limit. For example, assume there are two sets of customers, Ones are frequent customers that are mandatory for delivery, and another set is the non-frequent potential customers with known and estimated profits. Both sets have known demands and service requirements over a planning horizon of multiple days. The objective is to determine vehicles’ routes that maximize the net profit, while satisfying vehicles’ capacity, route duration and consistency constraints. Vehicles are required to start and end at the same depot.
In this post, I explain CVRP and show python+pulp based solution. The rest of this post is organized as follows:
- Definition of the Problem
- Which kind of model we should use?
- Formulate according to given constraints and model
- Coding with solver (Pulp)
- Visualization of results (Google Maps API)
1. Definition of the Problem
The capacitated vehicle routing problem (CVRP) is a VRP in which vehicles with limited carrying capacity need to pick up or deliver items to various locations. The items have a quantity, such as weight or volume, and each vehicle has a maximum capacity that they can carry. The problem is to pick up or deliver the items with the least cost, while never exceeding the capacity of the vehicles.
So, I will set a customer number, vehicle number, demand of each customer and capacity of vehicles as following.
- customer number : 9 (plus one depot)
- vehicle number : 4
- demand of each customer : random values between 10 and 20
- vehicle capacity : 50 (assume that all vehicles have the same capacity)
2. Which kind of model should we use?
Graph theory is often used (numerical data is added to nodes and edges of graphs) for the vehicle routing problems. This is because it is possible to think in a way that selecting (or not selecting) routes by passing (or not passing) edges. In this context, assigning ‘1’ to an edge means that a route is being selected. Yes! It can be said that this corresponds to the integer optimization problem. This post will also explain the CVRP problem using a graph.
Fig1 describes the graph, decision variables, objective function and constraints of CVRP.
3. Formulate according to given constraints and model
Based on the definition of parameters in Fig1, I formulated constraints for the decision variables and the objective function of CVRP.
- (1) objective function which means “minimize the travel cost (sum of traveling distance) of all vehicles”
- (2) constraint which means “only one visit per vehicle per customer’s location”
- (3) constraint which means “depart from depot”
- (4) constraint which means “the number of vehicles coming in and out of a customer’s location is the same”
- (5) constraint which means “the delivery capacity of each vehicle should not exceed the maximum capacity”
- (6) constraint for “removal of subtours”
- (7) constraint for decision variables
4. Coding with solver (Pulp)
Based on the given formulas, I wrote python code for solving CVRP with pulp, which is an open-source package that allows mathematical programs to be described in Python.
Fig3 shows the random generated locations & demand of customers. Row number 0 is the depot, which has no demand. In this example, the Empire state building is set as a depot. ☺
And the following is printed results, which show that one of four vehicles was unnecessary, and the total moving distance of the other three vehicles is 14028m. Yes! This is the optimal result calculated under the given conditions!
Vehicle Requirements: 3
Moving Distance: 14028.05. Visualization of results (Google Maps API)
Then, Let’s visualize! _plot_on_gmaps defined in the python code is a function for plotting each customer on Google Maps. Fig4 shows the distribution of 9 customers and 1 depot (Empire state building).
And under parts of the python code, which start from following comments are visualization sections.
#visualization : plotting on google maps
...# visualization : plotting with matplotlib
...
Fig5 shows the optimal routing result, which minimizes a moving distance under the given conditions, and three different colors are three different vehicles. But, I thought that this mapped routing result does not look elegant and each route is not easily distinguishable. So, I just plotted each customer and routing results using matplotlib. Fig6 shows the optimal routing result on a plane coordinate system. Yeah! This is much easy to grasp!
SUMMARY
In this post, I explained CVRP (Capacitated Vehicle Routing Problem) and introduced the python code which calculates optimal routing using pulp. Mapped results show that output of the python code makes sense.
However, the problem set in this post is extremely simplified (for example, the capacities of all vehicles are the same). In other words, it is extremely complicated to make the model that considers all possible constraints in the real field.
Therefore, in order to create VRP solution as a system in the real field, it is necessary to consider how constraints can be reflected properly on the model.
