Solving the Vehicle Routing Problem (2024)

The Vehicle Routing Problem (VRP) is an combinatorial optimization problem of finding a set of routes for a fleet of vehicles that minimizes travel time. The Vehicle Routing Problem can be thought of as multiple Travelling Salesman Problems (TSP) combined together.

Real-world Vehicle Routing Problems are everywhere, and using algorithms for the optimization of vrps can greatly impact the efficiency of any fleet of vehicles.

We see real-world examples of VRP every day:

• Meal prep companies delivering food from central kitchens to customer locations
• Delivery trucks that bring you groceries from local stores
• Couriers who deliver packages to delivery points
• Field service technicians dispatch for customer demands
• Laundry pickup and deliveries to a set of customers

The term Route Optimization is most often used in the context of optimizing a VRP problem in the world of operations research. There are both open-source solvers as well as commercial VRP Routing APIs. Since it isn’t feasible to find the optimal solution, solvers typically use metaheuristic algorithms to find an efficient solution quickly – there’s no point in finding the absolute best route if it takes you a few days to find!

The Vehicle Routing Problem is. Essentially, you have a fleet of vehicles and a set of customer locations or delivery points. You’re trying to figure out:

1. Which delivery truck should I assign each customer location to?
2. In what sequence should the delivery truck visit those locations?

The objective function is typically to minimize travel time, but you can also optimize for shortest route , fewest number of vehicles, or total cost.

Any real-life application of the VRP typically has constraints to meet as well, such as vehicle capacity constraints (CVRP), time constraints (VRPTW), or any other constraints that describe a given real-world business use-case.

In this article, we’ll break down:

• How to solve the Vehicle Routing Problem
• Why the Vehicle Routing Problem is so tough to solve and some ways to solve it
• How a deeper understanding of the VRP can help your day-to-day operations
• How to solve the VRP using software

But before we get into that, let’s explain some of the basics.

How do you solve a route problem?

Formulation of the VRP is easy. Solving it is hard. Vehicle Routing Problem (VRP) and its variants including the Capacitated Vehicle Routing Problem (CVRP) and Vehicle Routing Problem with Time-windows (VRPTW) remain one of the most difficult and popular optimization problems in the field of operations research.

There are numerous approaches to the optimization problem, which can roughly be split into exact methods and approximation methods using metaheuristics. Exact methods are mostly an academic exercise as they don’t work well for large-scale routing problems. Besides, real-life applications of the VRP typically don’t need the most optimal solution – just any solution that’s good enough will already be extremely valuable.

This is why most algorithms for the VRP use metaheuristics: they are fast, practical, and flexible (in terms of adding more constraints to the solver).

Metaheuristics come in many different variants as well. A subset of the most popular and effective heuristic algorithms for combinatorial optimization problems include local search, tabu search, genetic algorithms, simulated annealing.

To solve a route problem, you can do the route planning manually or with software. Manual route planning is when you plan out routes with Excel and/or use Google Maps as a route planner. The recommended approach is to use purpose-built algorithms instead. Humans are simply not good at solving routing and scheduling problems. When choosing your software approach, you also have many options:

• (recommended) Use route planning software that is built to be easy-to-use and accessible for anyone, even without a computer science degree.
• Use a Route Optimization API for maximum flexibility and integrate a solver into your own stack.
• Use an open-source VRP solver, which is free, but it does require a lot of maintenance and typically don’t perform as well as commercial routing software. The ETAs are inaccurate as you’ll need to use something like OSRM to generate a travel time matrix, which doesn’t account for traffic.
• Create your own linear programming formulation and use off-the-shelf generic linear programming solvers.

Why is the Vehicle Routing Problem so tough to solve?

The VRP is a class of optimization problem combining multiple Travelling Salesman Problems together. The TSP is already known to be NP-hard, so you can imagine how complicated the combinatorial optimization problem can get when you multiply the number of drivers and toss in real-world constraints such as time-windows, vehicle capacities, real-life traffic conditions that impact travel times, stochastic service time at locations, etc.

But that’s only part of the reason why VRPs are an ongoing exercise in problem solving. To understand why Vehicle Routing Problems are tough to solve – and why NP-hard problems are such a hard nut to crack in general – we have to first understand something called time complexity.

Time complexity is a term used to describe how the computation time scales as the problem size scales. Here’s are some examples to illustrate:

Let’s say you want to calculate the total distance of a route that has 4 stops. In other words, you’re not trying to find the shortest path, you’re just summing up the total distance. Simple enough — you just add up all the distances from Stop 1 to 2, from Stop 2 to 3, and from Stop 3 to 4. And then you're done.

If you now need to add 4 more stops to your route plan, you just need to calculate a total of 8 numbers to get the total distance. In other words, the number of calculations you need to perform scales linearly with the problem input size.

This is what we call a linear problem. As things scale and get bigger, the time it takes to solve the problem scales accordingly, in a linear fashion.

‍

Now, let’s look at a route optimization scenario, with 10 stops that need to be planned, and some common constraints like delivery time windows and vehicle capacities.

In order to find the shortest route for your fleet of vehicles, you would have to calculate out all the possible combinations of those 10 stops (while satisfying constraints), and then check each one to find the best solution. The number of combinations is overwhelming.

With 10 stops, there can are more than 3.6 million permutations. With 57 stops, the number of possible routes jump to a 57 quattuorvigintillion, which is a number with 75 zeroes!

This is what we call an exponential problem. As things scale and get bigger, the time it takes to find the ideal solution increases exponentially. Things become more complicated, eventually to a point where it is virtually impossible for a human to calculate without some help.

‍

Planning routes isn’t hard, which is why people have been able to do things manually for so long. The difficult part is planning optimized routes, and when you add constraints that are important for your business, planning optimized routes gets nearly impossible for a human to do without some help.

‍

Why is the Vehicle Routing Problem important for me?

“Interestingly enough, humans are intuitively good at solving Vehicle Routing Problems,” says Roger Tsui, Senior Algorithms Engineer at Routific. “We just can’t do it at a large scale, and we find it difficult to factor in a handful of constraints. It gets too complicated.”

But in general, if there are no other constraints to account for that might throw things off, we want our routes to resemble a loop (or multiple loops if you have more than one driver) that have very minimal overlap. Kind of like a flower petal.

“A deeper understanding of the Vehicle Routing Problem will help you understand how complicated it is to get to a solution like this,” continued Tsui. “That's why we rely on computers, algorithms, and route planning software to handle it.”

Each routing situation is different, but with Routific, you can flexibly configure your real-world constraints and choose your objective function as either travel time, shortest distance, or fewest number of vehicles.

Optimizing for time

If you are optimizing routes for time, then you are solving the Vehicle Routing Problem by finding the solution that would take the shortest total duration to complete.

This is particularly useful for cases where you pay your drivers an hourly wage, which typically is also the largest contributor to delivery cost. If you are able to build solutions that complete routes in the shortest amount of time, you are able to cut down on costs.

Optimizing for distance

Your other option for optimizing routes is to optimize for shortest distance. This means that you’ll be solving the VRP by finding the solution that would take your drivers the least amount of miles to complete, while reducing or eliminating any idle time your drivers may have.

This is particularly useful for cases where you pay your drivers based on their mileage. If you optimize your routes based on distance, you can reduce your overall costs, while still optimizing your routes.

Assigning the right drivers

The ability to assign the right drivers to the right stops is a huge benefit. Sometimes there are vehicles that have certain capacities, or drivers with certain constraints like availability during the day if you have shifts. Take a look at Bear’s Blooms.

Tess and Parker, owners of Bear’s Blooms, deliver flowers to customers on a weekly basis, but they need to divide up their delivery schedule throughout the week, by region. So they need to know:

• What customers will be receiving a delivery each day
• What region will be receiving a delivery each day
• What drivers are available to deliver to those zones

There are a few factors here to consider when planning out delivery routes, making it a bit messy to handle manually.

Tess spends about an hour each morning planning routes; a process that would take twice as long if they did not have Routific in place. “I start by uploading a CSV of our orders to Routific every morning, and divide routes by postal code,” explained Tess. Her team assigns delivery days to customers based on their postal code and lets them know what day to expect delivery in advance. “It’s simple and straightforward.”

How do you solve the Vehicle Routing Problem?

When you do a quick Google search on the Vehicle Routing Problem, you’ll probably come across a few scientific articles and a handful of TED Talk style presentations, diving into the intricacies of the VRP. That’s because the Vehicle Routing Problem remains an active area of study for data scientists and engineers.

Right now, solving the Vehicle Routing Problem really just means using an algorithm to find the closest possible solution based on time or distance. Most of the time, these algorithms don’t aim to “solve” the problem — they try to get close to the solution in a reasonable amount of computer time.

That’s why not all algorithms are made equally. Some intentionally take a longer time to process, to deliver a more optimal solution; while others will place more of a focus on a speedy processing time, while delivering a solution that is sub-optimal, but still very good.

It all boils down to what your team values the most.

Routific provides a solution to the Vehicle Routing Problem with our Route Optimization API. Our algorithm can save a business up to 40% of driving time and fuel and reduce route planning time by 95%. Our Routing Engine API is used across the world in 900+ cities, across a plethora of industries, and can account for common delivery constraints such as:

• Time-windows
• Capacity constraints
• Visit durations
• Multiple depots
• Open-ended routes
• Type constraints
• Driver shifts

If you run a business that does home deliveries – or if you are faced with a Vehicle Routing Problem – chances are we’ve dealt with your use case before. It might be time to try vehicle routing software.

For a deeper dive into how Routific tackles the Vehicle Routing Problem, and for a better understanding of the problem as a whole, you can learn even more here.

And if you’re ready to check out Routific for yourself, you can try our route planning software free for 7 days here.