How to Solve Your Vehicle Routing Problem (Without a Degree in Applied Mathematics)
In this post, we show you how you can solve your vehicle routing problem, without needing a degree in applied mathematics.
Understanding the vehicle routing problem (VRP) is pretty simple, but solving it is a whole other matter. The vehicle routing problem (sometimes called the “traveling salesman problem”) is figuring out how to maximize the number of stops your vehicles can make while lowering operating costs.
The VRP is important for delivery companies, but also for any operation that involves making stops across several locations, like garbage trucks and forklifts stocking a warehouse. It also varies greatly in complexity. If you’re running a one-person delivery team that does 20 stops a day, then you have less variables to factor into your problem than if you had a fleet of vehicles handling hundreds of deliveries a day across dozens of post codes.
Still, the fundamentals are the same — when you’re solving your team’s vehicle routing problem, you need to factor in the number of vehicles, customer locations, traffic patterns, speed limits, time constraints, and other things like vehicle capacity and order priority.
There are two ways to do this — you can create a custom formula suited towards your business, or you can use route optimization software like Circuit that does it for you. Which way is best will depend on what kind of business you’re running.
Below, we focus on the problems delivery teams encounter when they try to solve the vehicle routing problem manually. We also look at different levels of vehicle routing problems, including:
- Solving single-vehicle routes
- Solving multi-vehicle routes
- Solving routes with time constraints and priority stops
Then we cover how our route optimization software works, by taking an in-depth look into how delivery services can use Circuit.
Throughout this post, we’re going to use real-world case studies from Circuit customers who use our software to solve the vehicle routing problem, while offering a better last-mile delivery experience to their customers. If you’re interested in quickly — and cost-effectively — creating fast and efficient routes, start your free trial today.
How to go about solving the vehicle routing problem manually
Before we get to using route optimization software, let’s look at how you can solve the VRP for your business.
But first, it’s important to know that VRP is a problem that gets increasingly difficult to solve with the size of nodes (a.k.a. stops). For example, a problem with 10 nodes can take around 3 milliseconds to solve, while a problem with 20 nodes can take up to 77 years to solve.
How is that possible? Because of the factorial growth at the root of the problem.
This is why almost all solutions rely on heuristic algorithms and metaheuristic algorithms. These are algorithms that you can use to solve your vehicle routing problem faster, but doing so sacrifices optimality or accuracy. It’s better to have a workable solution in your lifetime vs. an optimal solution 70 years down the line.
Now, this is going to get technical, so stick with us for a moment.
There are several ways to solve the VRP, including the “branch and cut” method, and a long list of what’s known as “exact methods.” But one of the more popular (and easiest) algorithms for solving the VRP is the Clark and Wright savings algorithm.
Its formulation is about as simple as a VRP solution gets: You have D (your central depot, or where your vehicles start and need to return throughout the day) and then you have N (nodes, or stops). You’ll list all the stops you have to make and then calculate the time it takes to make each stop individually as if going back from the depot to the location.
Once you have those travel times, you can start grouping stops together to figure out which grouping gives you the most time saved. After that, you go down the list until you can prioritize groupings based on the time saved.
In practice, the formula will look something like this:
But the problem with all of this — the different methodologies, algorithms, and formulations — is that it’s overkill for small to midsize businesses who have delivery drivers or courier companies that are focusing on last-mile delivery operations.
It’s overkill for two very clear reasons:
Reason #1: Manually solving your VRP is incredibly complicated
When you’re solving your delivery service’s vehicle routing problem, there are several factors you need to consider.
Let’s take the most straightforward type of delivery service — a single driver service that delivers products from a local business to residential customers within business hours. The more deliveries you can make in a day, the more profitable your business is because you’re spending fewer resources — such as time and fuel — on each delivery.
One of our customers — Sagar Khatri — knows this very well.
Sagar is a subcontracted courier. He picks up packages from warehouses and delivers them the same day. Because he is paid per parcel, he’s motivated to make as many deliveries as he can in a day. For Sagar, solving the vehicle routing problem literally gives him a raise.
When he started using Circuit, he doubled the number of deliveries he could make in a day. Sagar was able to double his number of deliveries for two reasons:
- He used our route optimization software to create fast and efficient routes. Unlike manual processes, Circuit gets the fastest route every time, in a matter of seconds.
- He used our free mobile app as a way to leave notes for each stop. Like many couriers, Sagar wants to cut down on time anywhere he can. When he loads his vehicle with packages, he leaves notes of the package’s physical description in the Circuit app on his phone. That way, when he gets to a stop, he can see what the package looks like on his phone. Now he isn’t sifting through a sea of brown and white packages in the back of his vehicle.
Reason #2: Manually solving your VRP is resistant to change
You’re not going to have a permanent set of customers. You’ll lose some, and you’ll gain some. And hopefully, you’ll gain more than you lose.
But if you’re using a manual VRP formula, you’re going to have to re-figure how you solved your vehicle routing problem as you grow. This means adding multiple drivers or factoring in things like time windows (such as when customers want their package before or after noon).
When we made Circuit, we wanted to make sure it would help our users grow their delivery businesses. For us, this meant making sure you could add new delivery clients and increase your vehicle capacity easily.
When you use Circuit, you can make as many routes as you need. And each route can have up to 500 stops. And you’ll still get the same accurate routes for drivers to follow, regardless of how many you need to plan.
Should you ever solve the vehicle routing problem manually?
Sometimes you’ll want to solve your company’s VRP manually. This usually happens when you’re dealing with a permanent stop schedule, and don’t need route optimization software.
Or if your logistics needs require more nuanced variables than your average route optimization software.
For example, let’s say you’re dealing with a fleet of garbage trucks that has to service-specific postcodes in a large city. Because your trucks need to drop off their waste load in the middle of the day you’re dealing with a capacitated vehicle routing problem (CVRP) — in other words, a routing problem with capacity constraints.
Every postcode has its residents put their bins in different areas (some at their curb whereas apartments and larger housing complexes have specific drop off points).
In this example, it might make sense for you to use a heuristic algorithm to figure out the best route for your trucks to take.
How using route optimization software solves the VRP
At Circuit we have two different offerings: the Circuit Route Planner and Circuit for Teams. Both services are built around our advanced route optimization software that you can use to solve your VRP in minutes, not hours.
The Circuit Route Planner is ideal for single-driver operations or delivery teams who need a way to create the fastest route possible for one driver. Circuit for Teams has other last-mile delivery features, like route monitoring, automatic delivery updates, and proof of delivery.
In this guide, we’re focusing on how delivery teams can use our route optimization to solve the vehicle routing problem, and not on all the other aspects of last mile delivery.
When you’re creating single-vehicle routes, you can use the Circuit Route Planner. For $20 a month, you can create as many routes as you want for one driver at a time.
You can either manually add stops to your route or you can upload a spreadsheet of all of your stops. Once your stops are in Circuit, you can customize your route to your needs.
This means you can set time constraints, any priority stops, and the estimated average time per stop.
- Time constraints: This is when you need your drivers to get to a specific location within a specific time. If you’re running a delivery company, this could be making sure all your commercial deliveries happen during business hours.
One of our customers — Applied Data Technologies — services computers at public schools and uses time constraints to make sure their technicians show up at each school during business hours.
- Priority stops: If you need to set a priority stop, you can do so with a click of a button. This tells our software to make sure that stop is made first in the route.
- Average time per stop: When you set your average time per stop, you’re telling our algorithm (approximately) how long you’ll spend at each stop. This helps us create the fastest (and most efficient) route, by knowing how long you’re likely to be at each stop — and how many stops you’re able to make in a day.
These are all critical variables that would normally drive a route planner crazy if they were manually planning a route. But with Circuit, it’s easy. Once your route is customized, just let our software create the fastest and most efficient route for you.
If you’re creating routes for multiple drivers, then you’ll want to use Circuit for Teams. We offer three different pricing plans — Dispatch, Recipient, and Enterprise.
- Dispatch is great if you just want a way to create fast routes for multiple drivers.
- Recipient is perfect for delivery teams who want to perfect their last-mile delivery operations by offering order tracking and proof of delivery
- Enterprise comes with all Circuit features, including letting you export all of your data within Circuit to other services.
Each plan comes with the same advanced route optimization software we discussed above, which means you can quickly create the fastest and most efficient routes that are tailored to your business’s needs.
When you create your route in Circuit, you can assign it to specific drivers.
Throughout the day, you can also make changes to the route based on customer orders or traffic patterns. Plus, if one of your drivers has to leave early — or can’t complete the rest of their route — you can re-assign stops to a different driver.
Next steps: Improving your Entire last-mile delivery operations
The vehicle routing problem is a problem worth solving. By knowing the order in which your vehicles should make their stops, you’ll save time and money. But doing this manually is unnecessary for a lot of businesses — especially small-to-midsize local businesses that offer home delivery, and even midsize courier companies.
For those companies, we recommend using route optimization software like Circuit.
You can easily add all your addresses to our web app, and customize time constraints, priority stops, and the average time per stop. Then you just click “Optimize” and our proprietary algorithm will generate the fastest route automatically.