Understanding the Vehicle Routing Problem (VRP)

Hand moving pawn on a conceptual vehicle routing problem. Shortcut to success or career guidance concept. Composite image between a hand photography and a 3D background.
Featured image credit: Olivier Le Moal/iStockphoto.com

The vehicle routing problem (VRP) is nothing new and has been a big challenge for every field service business for decades.

On the surface, vehicle routing and scheduling problems may sound like typical business problems. However, they are complicated by multiple parameters and resource constraints.

Let’s say you have almost 1000 deliveries to make every day using 20 vehicles.

How will you decide what vehicles should serve what deliveries and in what order?

You must do all this while factoring in fuel consumption, traffic peak times, under-construction or bad roads, and specific time windows for each customer.

In real life, route planning has many uncertainties, such as changing customer demands, traffic jams, and unexpected weather conditions.

These uncertainties can lead to increased transportation costs if not handled properly. Worse still, these complexities grow exponentially as the number of vehicles and customers increases.

It’s a no-brainer that solving the VRP is crucial to facilitating the seamless movement of goods and services from one place to another, but finding the right solution to the VRP is a Herculean task. So, how can you solve the dynamic VRP?

Before discussing that, let’s first get the basics right, starting with what the VRP is.

What Is the Vehicle Routing Problem?

The VRP is the challenge of figuring out the optimal routes from a depot to a set of destinations each with operational or business-specific constraints. These constraints include cost controls, vehicle limitations, route length, and time windows.

[By PierreSelim. – Own work., Public Domain]

VRP was first named and documented in the 1950s, but the first classic VRP, known as the traveling salesman problem, originated in the 1800s.

Now, let’s take a closer look at the most common VRPs and the tools you can use to unravel them.

What Are the Common VRPs?

Below are some of the real-life VRPs field service businesses often face in day-to-day operations.

Vehicle Routing Problem with Time Windows (VRPTWs)

Customers often demand that their deliveries be made during a specific period. This limits pick-up and delivery times, as your driver has to show up at a customer’s door within a prioritized timeframe.

Note, the driver can arrive before the scheduled delivery time, but never outside the set time window.

Falling behind schedule will annoy your customers and will cause increased customer attrition and a significant drop in the revenue and profit margin.

So, you need to factor in time windows in the most cost-efficient way, while planning your routes. That’s what VRPTW is all about.

Time windows can be:

  • Soft time windows: Serving outside the time window is allowed, but it comes with hefty penalties.
  • Hard time windows: Time violations are not allowed at all. A driver must wait if he or she arrives way ahead of the scheduled time until the time window opens and cannot show up late.
  • Disjoint time windows: Showing up between two time windows, a driver has to wait until the next time window opens.
  • Multiple time windows: A set of non-overlapping time windows with different lengths.

Now, let’s understand this with a real-life scenario and the approach to a solution.

Real-Life Scenario

Let’s take the example of FedEx. A parcel has arrived at the destination country and is accepted by a last-mile carrier.

The package needs to be moved to the distribution center. From there, a courier will take the parcel to deliver it to a customer who will be waiting for it on Wednesday, from 10 to 11 in the morning. This doesn’t look like a soft time window, right?

So, the courier driver cannot afford to be late. But, 15 other packages need to be delivered, each with a specified timeframe as well.

VRPTWs must be solved everywhere, from postal, restaurant, or supermarket deliveries to security patrol services and bus routing.

Approach to Solution

Now, how can the driver show up on time everywhere, while taking the shortest routes?

We need to connect the dots: Identify a set of routes with the least traveling expenses and maximal customer satisfaction which, in this case, can be achieved by adhering to the prioritized time windows.

Pickup and Delivery Vehicle Routing Problem (PDVRP)

On-demand delivery businesses, such as courier delivery and food delivery companies, need to plan delivery routes each day; sometimes even multiple times a day, depending on the nature and scale of the business.

Several resource constraints, parameters, and schedules need to be considered while chalking out these routes.

Usually, with PDVRP, the challenge is combining delivery and pickup points to help reduce travel time and cut fuel costs.

An ideal route should pair delivery and pickup points while keeping the route the shortest or fastest one possible.

Real-Life Scenario

Let’s consider the example of Uber. The system needs to assign drivers to locations efficiently so that it doesn’t take much time to reach there and pick up a customer.

Approach to Solution

Assign routes to the drivers or vehicles to pick up and deliver passengers. The customer’s request must be met as soon as possible by reducing the total length of the vehicle’s routes.

Capacity Constraint Vehicle Routing Problem (CVRP)

Each vehicle has a maximum load capacity (both weight and volume) which must be considered. So, it is often challenging to save costs by loading more items and serving more customers in one trip without exceeding the vehicle’s capacity. 

There might also be additional complications, such as:

  • The varying sizes of parcels for delivery and pickup, 
  • The different capacities of all the vehicles, and multiple depots
  • Multiple depots
  • Multi-compartment vehicles

Real-Life Scenario

Take Tesco, a grocery and general merchandise retailer, as an example. They use over-the-road vehicles for good distribution. They transport the goods on pallets and each vehicle can accommodate only a limited number of pallets, while each business unit (BU) demands a different number of pallets. For example, a large retail store requires several times more pallets than the vehicle can fit.

Approach to Solution

The best approach should be assigning the shortest routes so that the total amount of units for the vehicle meets its capacity limitations.

[By Lady-Shirakawa. CC BY-SA 3.0, Link]

Why Is the VRP Difficult to Solve?

Although we have described the above VRPs in isolation, they are often combined in real life, thus exploding the overall size of the problem.

For instance, the placement of delivery and pickup addresses in a route affects whether you will have enough space in your vehicle for another pickup. 

Also, if you do have space, adding or leaving out another pickup or delivery will impact your time window for other customers. 

So, solving the VRP is difficult even for the most experienced dispatchers and seasoned drivers. Because it is a combinatorial optimization problem where the contributing factors are sometimes uncertain, unaccounted for, and cannot be predicted.

Why Do You Need An Effective Solution for VRP?

The primary reason why you need an effective VRP solution is to reduce logistics expenses. There are other reasons include the following:

  • It helps achieve sustainable growth. 
  • It boosts efficiency and productivity. 
  • It saves time as well as increases customer satisfaction, thereby increasing revenue and improving profitability.

How to Solve the Vehicle Routing Problem?

There are a couple of solutions to address the VRP, such as:

Manual Solving (including Google Maps)

Based on previous experience, the ideal driver should be able to pull off a route plan manually. But, that will be a time-consuming and nerve-racking task to do. 

Additionally, there’s a high probability that the drivers will make mistakes during the manual process. Simply put, manual solving is the most inefficient method to address the VRP.

A free route planner like Google Maps cannot help either. It would be able to guide your driver to the best route considering traffic but cannot provide the right order that your driver should follow to deliver all the packages on time. 

The Google Maps route planner is not intended for everyday use, especially when you are managing a large fleet of vehicles with 100 or more deliveries. Such a basic tool can only address some of the routing problems. 

Learn if Google Maps is right for your delivery business.

Preset Solvers

This is a faster and better method than solving the VRP manually. However, preset solvers only satisfy or solve two or three basic constraints. It can only be applied in “academic settings” that require in-depth research, but not in the real world. 

Route Optimization Software

A route optimization software, or vehicle routing software, is the best solution to solve the VRP.

With a route planner, the unsolvable VRPs and all the constraints can be addressed in less than 30 seconds. It will even give you optimal routes that are faster, save fuel, cut costs, and adhere to the time windows of each customer.

A delivery route planner is a cost-effective and scalable solution that offers multi-vehicle and multi-stop routing as well as ensures the safety of deliveries and your drivers.


Want To See For Yourself How Route4Me Can Boost Your Profits?

Whether you want to slash the time it takes you to plan routes for your drivers, increase the number of stops they can make, or keep your customers satisfied knowing that your drivers show up on time… Route4Me helps you achieve that!

Start Free 7 Day Trial

How to Choose the Right Map Route Planner to Solve the VRP?

While assessing the different route planners, pay attention to the ones that offer the following core functionalities:

Visualization of Route Plans

Route planning is a visual process. This means that being able to see where each customer location is, which driver will serve it, and how inserting or deleting an address will impact the overall route will make route planning much more seamless.

So, find VRP software that can help you modify routes on the fly.

Advanced Algorithm

A route planner app should come with an AI-powered algorithm that will create optimal routes with accurate directions to work by considering all the constraints, including traffic jams, specific time windows, vehicle load capacities, and pickup and delivery schedules, while, at the same time, saving on fuel and drive time.

Proof Of Delivery

The best route planners come with an eSignature feature that helps drivers capture electronic customer signatures and store or save them as digital proof of delivery. So, you must consider this feature.

ALSO READ: Proof of Delivery – Advantages and Benefits

Real-Time Tracking

When it comes to your field service business, knowing the location of your vehicles and drivers is crucial. 

For instance, if a field rep is behind the schedule, you can track the vehicles in real-time to find out the reason and understand how the delay will affect the ETAs of the remaining deliveries. 

You can then either re-adjust the routes instantly or inform the customers about the updated ETAs. This will enhance your customer service and increase the accountability of your drivers.

So, GPS tracking is a must for every field service business.

ALSO READ: 4 Ways Vehicle Location Tracking Can Reduce Your Expenses and Improve Productivity

Geocoding Capabilities

You wouldn’t want your drivers to end up at the wrong address or waste time searching for the right address. That’s why you need a route planner app that comes with geocoding capabilities.

A geocoder auto-corrects any wrong addresses entered into the system so you never need to worry about the accuracy of the customers’ addresses.

ALSO READ: How To Eliminate Costly Mistakes Caused By Incorrect Addresses And Drop-off Locations

In order to ensure that you pick a delivery scheduling software that really works for you, consider eighteen more points as laid out in our article: How to Choose the Best Route Planner.

Conclusion about the Vehicle Routing Problem

No matter how experienced your managers and drivers are, you can’t always anticipate what will happen on the road and adjust your route instantly to meet your customers’ unanticipated requests. 

So, you need an advanced tech solution to plan your routes as well as track your drivers and vehicles. Essentially, using an advanced route optimizer is the most efficient way to resolve your VRPs and make planning and modifying routes seem like a walk in the park!

Do you have any questions about the vehicle routing problem? Please feel free to leave your comments below.


Want To See For Yourself How Route4Me Can Boost Your Profits?

Whether you want to slash the time it takes you to plan routes for your drivers, increase the number of stops they can make, or keep your customers satisfied knowing that your drivers show up on time… Route4Me helps you achieve that!

Start Free 7 Day Trial

About author: Rahul Dasgupta

Rahul Dasgupta is a content writer with over 20 years of work experience. He holds a master’s degree in computer science and has written thousands of blog posts on route planning and scheduling, making it easy for readers to learn about these complex topics. Rahul enjoys playing tennis in his spare time and loves cuddling with his pet labrador Shinu. Rahul is a big fan of Roger Federer, Messi, and Bill Gates - he admires their drive to be the best at what they do and their philanthropic efforts.


About Route4Me

Route4Me has over 40,000 customers globally. Route4Me's Android and iPhone mobile apps have been downloaded over 2 million times since 2009. Extremely easy-to-use, Route4Me's apps create optimized routes, synchronize routes to mobile devices, enable communication with drivers and customers, offer turn-by-turn directions, delivery confirmation, and more. Behind the scenes, Route4Me's operational optimization platform combines high-performance algorithms with data science, machine learning, and big data to plan, optimize, and analyze routes of almost any size in real-time.