What Is The Vehicle Routing Problem (VRP)?

The Vehicle Routing Problem (VRP) is everywhere, and solving it is critical in helping to facilitate the movement of goods and services from one place to another.

We see examples of VRP every day:

• Meal prep companies delivering food from central kitchens to hungry homes
• Delivery vans that bring you groceries from local stores
• Couriers who deliver packages to your office

Most people have a baseline understanding of what the Vehicle Routing Problem is. Essentially, you have a fleet of vehicles and a collection of stops. You’re trying to figure out:

1. Which vehicle should I assign to each stop?
2. What order should the vehicles visit those stops to minimize distance and travel time (while satisfying any other constraints you might have)

The problem statement is easy to put together. It’s the solutions that are difficult to find. In fact, the Vehicle Routing Problem remains one of the most difficult math problems in existence. So.. It’s okay if you’ve been struggling to plan your routes efficiently. People have been struggling with this VRP for a very long time.

In this article, we’ll break down: 

• Why the Vehicle Routing Problem is so tough to solve, 
• How a deeper understanding of the VRP can help your day-to-day operations 
• How you can 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?

Solving a route problem essentially means finding an acceptable solution that has your fleet visiting all of the required stops. The tricky part is finding a solution that does this efficiently and cost-effectively — what we refer to as optimized routes for fleets.

To solve a route problem, you can plan your routes manually or with software. Manual route planning is when you plan out routes with pen and paper, physical maps or even just plotting out stops on a tool like Google Maps. Planning routes with software is when you use route planning software that helps you process all the possible route configurations using powerful algorithms. But, only the latter is well equipped to solve VRPs.

Why is the Vehicle Routing Problem so tough to solve?

The Vehicle Routing Problem can be thought of as multiple Travelling Salesman Problems (TSP) combined together. Solving a TSP means finding the shortest possible route an individual can take between a handful (or possibly hundreds) of addresses, so you can imagine how complicated it can get when you multiply the number of drivers.

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, we have to first understand something called time complexity. 

Time complexity is when a problem gets more and more complicated the longer the project goes on for. Here’s are some examples to illustrate:

Let’s say you have a route with 4 stops, and you want to find the total distance traveled. Simple enough — you just plot out the addresses in a logical sequence; usually a round trip that brings you back to your start position or depot. From here, you would 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 need to add 4 more stops to your route plan, you would already have a good idea of how this would affect your time to process everything, since the only variable changing is the number of total stops. In this case, having double the amount of stops would roughly take double the amount of time to plan out.

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 planning scenario, with 10 stops that need to be planned, and some common constraints like delivery time windows and vehicle load capacities.

In order to find the most optimal route for your team, you would have to plot 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.

For example, with 10 stops, there can be more than 300,000 roundtrip permutations and combinations. With 15 stops, the number of possible routes could exceed 87 billion.

Now, when you add another 10 stops to this problem, it takes much longer than double the time to solve, because there are more factors to consider and more combinations to check.

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.

What is a capacitated routing problem?

One of the most common types of VRPs is the capacitated routing problem. It’s also commonly known as the CVRP, in case you come across that term online. Essentially, this is when you plan routes for multiple vehicles, while satisfying capacity constraints. 

Each of your vehicles has a limit in terms of how much it can carry. This is something that is difficult to account for with manual route planning. This would classify as one of those exponential problems that gets more complicated, the bigger it gets. But understanding how to solve it is important for your home delivery business.

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 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 base your optimizations on either time or distance.

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. 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 base optimizations on 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.