Vehicle Routing Problems 101
by Anand Seshadri
The Opex 101 series is an introduction to the tools, trends, and techniques that will help you make the most of your organization’s data. Intended for business leaders and practitioners alike, these posts can help guide your analytics journey by demystifying essential topics in data science and operations research.
Have you ever wondered how UPS delivers packages so efficiently? Or how garbage collectors visit thousands of homes all over a city in a single day?
The problem of collecting or delivering products across multiple locations while minimizing cost is a tough one, and therefore well known to Operations Research (OR) practitioners.
The Problem
This problem is called the Vehicle Routing Problem (VRP), and is stated as follows:
Given a set of vehicles and a set of locations, and assuming a fixed cost of traversing any location-location pair, find the path that reaches all locations at minimum cost.
The problem, as stated, might not seem all that hard to solve. An obvious approach to cracking the VRP is to determine all the possible routes and pick the least expensive one. So why don’t people do this all the time? Well, it turns out that this process, known as enumeration, is only feasible for very small problems.
In mathematical terms, the VRP is classified as an NP-hard problem, meaning that the required solution time increases exorbitantly with size. The number of possible solutions to the VRP is of the order of n!, where n is the number of nodes (locations the vehicle must reach) in the network. Given the factorial growth rate of possible solutions, and assuming a computer used for enumeration can process a billion computations per second, the total time taken to solve the VRP for different numbers of nodes using this brute-force approach is given in Table 1 below.
As you can see, the solution time gets out of control almost immediately, even with modest network sizes.
Heuristics for the Vehicle Routing Problem
Most real-world vehicle routing problems involve hundreds or thousands of nodes. Given the time required for brute-force enumeration, obtaining the exact optimal solution just isn’t realistic.
Fortunately, experts have developed heuristics that quickly yield near-optimal solutions for very large networks. One of the first heuristics for the VRP was developed by Clarke and Wright, known as the “savings algorithm.”
At a high level, the savings algorithm works by finding the low-hanging fruit. Consider a depot D, and a network with n nodes. A truck with a certain capacity needs to make stops at all the nodes in the network, starting from and returning to the depot. The first question the savings algorithm asks: starting with a very naïve route (i.e., going from the central depot to Node 1, then back to the depot, then Node 2, then back to the depot, etc.), what simple route change reduces total travel distance the most?
The algorithm combines pairs of locations (e.g. depot to Node 1, then to Node 2, then back to the depot) to see which pairs create the most savings, with savings being the reduction in overall distance traveled. The savings for a given location pair (i, j) is the sum of the distances from the depot to those locations (since it doesn’t have to travel out and back for both) minus the distance between the locations (the newly added travel distance).
The Clarke and Wright algorithm works by ranking the pairs of locations (i, j) by their savings, and then building out routes accordingly. The pair of locations with the highest savings is connected first, and then more pairs are folded into the route until there are no locations left, or some other termination criteria is reached. Let’s explore this heuristic more below.
A Quick and Dirty Example
Consider a city where trash is collected by a fleet of vehicles, each with a capacity of 23 tons. Imagine that the city is required to pick up trash from a set of nine neighborhoods scattered throughout the town. For simplicity, let’s say each house in the neighborhood places its garbage at a central drop-off point. Location 1 is the depot from which all vehicles begin their trip. The weight of the waste to be collected (in tons) from each neighborhood is given below:
All location pairs’ distances (below the diagonal) and corresponding savings (above the diagonal) are given in the figure below:
For a vehicle capacity of 23 tons, the application of the savings algorithm yields the following routes:
- Step 1: The algorithm begins by choosing the location pair with the highest savings, location pair (6,10).
- Step 2: The algorithm continues with the location pairs in the order of their savings. The location pairs chosen next are (9, 10), (8, 9), (5, 6), (8, 10), (7, 10), and (7, 6) (stopping here for brevity).
- Step 3: Location pair (9, 10) is joined to (6, 10) to form the route 6→10→9, subsuming the first two savings pairs. Continuing in manner above (and assuming symmetric distances between the location pairs), we get the route 6→10→9→8. The next location pair is (5, 6). However with the addition of location 5, the total demand is 24 tons, greater than the vehicle capacity of 23. So location pair (5, 6) is skipped, and the next pair is checked for feasibility.
- Step 4: Location pair (8, 10) cannot be added to the route as Location 10 already has nodes on both ends (it’s positioned between Node 6 and Node 9 right now) — we really can only add stops to the beginning or end of our route (this particular pair has both nodes in the route already anyway). So we skip it, and (7, 10) gets skipped based on Node 10’s in-the-middle positioning as well.
- Step 5: The next location pair is (7, 6). Inclusion of Location 7 satisfies the capacity constraints (neatly filling up our truck exactly to its 23-ton capacity), and Node 6 is a terminal node of the route already, meaning we can put this pair right at the beginning. Therefore, location pair (7, 6) is added to get the route 7→6→10→9→8. The vehicle starts from and returns to Node 1, the depot, to drop off its trash and start anew. After this first iteration, the route is 1→7→6→10→9→8→1.
- Step 6: The location pairs included the route obtained in Step 5 are removed, and the process repeats. The final solution for this VRP is illustrated below.
The Clarke and Wright savings algorithm is very efficient, even for large networks. A comparison of the execution times for the brute force and the savings algorithm is given in Table 2 below:
Clarke-Wright is the only heuristic discussed here, but operations researchers have developed many other heuristic algorithms for the VRP , some of which even solve it to optimality!
The Vehicle Routing Problem is an important, oft-studied problem with applications in logistics, manufacturing, parcel delivery, and more. The VRP is a difficult problem to solve exactly, especially for large networks. However, heuristics like the Clarke-Wright savings algorithm are capable of efficiently solving large-scale, real-world problems.
If you enjoyed this Opex 101 entry, check out another great post of ours which discusses one of the many variants of this classic problem.
If there’s a topic you’d like us to cover as part of Opex 101, let us know in the comments below!
_________________________________________________________________
If you liked this blog post, check out more of our work, follow us on social media (Twitter, LinkedIn, and Facebook), or join us for our free monthly Academy webinars.
