The Vehicle Routing Problem (VRP) Demystified: Solutions for Your Delivery Operations

The vehicle routing problem is a serious and one of the oldest challenges in the logistics and delivery business. George Dantzig and John Ramser first represented it in 1959 in their paper. In which they wrote the first mathematical approach and later applied it to the petrol deliveries.

You must have heard about the Traveling Salesman Problem (TSP). It is a subset of VRP and the only difference between TSP, and VRP is that TSP is a single-route node-service-combination problem, and VRP is a multiple-route-node-service-combination problem.

In this blog, we will provide a detailed guide on vehicle routing problem (VRP), its types, and potential solutions.

So, let’s jump into it!

What is the Vehicle Routing Problem (VRP)?

Vehicle routing problem is a classic problem in the logistics and delivery business that causes inefficient outcomes like inaccurate delivery routes, wastage of time & resources, and dissatisfaction among the customers.

Vehicle routing problem is a problem that involves finding the most efficient way to carry out delivery operations and deliver goods with a multi-route using a fleet of vehicles.

The goal of this problem is to find the best possible set of routes for the vehicles to reach every stop while minimizing the overall distance traveled, the number of vehicles used, delivery time, and fuel costs. This will also consider other factors, including capacity of each vehicle, the time window, and the service time required per stop.

To get a detailed explanation of what is vehicle routing problem, do check the below-given video:

Types of Vehicle Routing Problems

There are several types of vehicle routing problems that affect the logistics and operations to a great extent. Let’s talk about them one by one:

1. Traveling Salesman Problem (TSP)

Traveling Salesman Problem is a problem whose goal is to figure out the shortest possible route that can be assigned to a salesman. By following this route they can visit a set of cities and return to their starting location, covering each stop once. As the number of cities increases, finding the optimal solution becomes exponentially difficult. So, this problem is an NP-hard problem. Manufacturing, logistics, and transportation are some of the real-world applications of TSP. 

2. Capacitated Vehicle Routing Problem (CVRP)

Capacitated vehicle routing problem is a problem related to the capacity of delivery vehicles to carry parcels. The goal of CVRP is to figure out an optimal set of routes to reach each customer on time, considering the capacity of each delivery vehicle. This problem is known as mixed-integer linear problem (MILP) and is considered NP-hard. CVRP is widely studied and used as a benchmark problem for the development of new algorithms and heuristics. 

3. Vehicle Routing Problem with Time Windows (VRPTWs)

In the vehicle routing problem with time windows (VRPTWs), delivery drivers have to serve each customer in a specific time window, and the objective is to find the most efficient route for the drivers to serve each customer on time.

This problem is also formulated as MILP and is known to be NP-hard. This problem is more complex as time constraints should also be considered along with capacity constraints. VRPTWs have many real-world applications and use cases.

4. Pickup and Delivery Problem (PDP)

In the pickup and delivery problem (PDP), the delivery drivers must visit both pick-up and delivery locations. The objective of this problem is to determine an optimal set of routes for the vehicles to visit pick-up and delivery locations while considering capacity and time constraints. 

Just like other VRPs, PDP is also formulated as MILP and is known to be NP-hard. PDVRP has many real-life applications, and one of them is transporting goods from factories to warehouses.

5. Vehicle Routing Problem with Profits (VRPP)

In a delivery business, each customer is associated with a known profit and the objective of vehicle routing problem with profits is to determine the optimal set of routes to reach customers while maximizing the total profit. Again, this problem is NP-hard and formulated as MILP. Delivering high-value goods or services is one of the applications of VRPP.

6. Vehicle Routing Problem with Multiple Trips (VRPMT)

In vehicle routing problem with multiple trips (VRPMT) delivery drivers have to make multiple trips to carry out deliveries to a set of customers. The goal of this VRP is to find an optimal solution for planned routes considering capacity and time constraints along with managing multiple trips. This VRP is considered NP-hard and is formulated as a MILP. As an example, we can consider the distribution of goods to retailers or grocery stores.

7. ​​Open Vehicle Routing Problem (OVRP)

In the open vehicle routing problem (OVRP), there is no fixed starting point for the delivery vehicles. The main objective of this vehicle routing problem is to figure out a set of optimal routes for the delivery vehicles to reach to maximum customer while minimizing the travel time, distance, or any other routing constraints. One of the real-world applications of this NP-hard problem is the transportation of goods or services in urban areas.

8. Periodic Vehicle Routing Problem (PVRP)

Periodic Vehicle Routing Problem (PVRP) involves determining an optimal set of routes for delivery drivers to serve a set of customers who require periodic deliveries or pickups. Unlike VRP, in PVRP, allows delivery drivers to visit customers multiple times, according to a predefined schedule. Real-world applications of PVRP includes waste management where garbage is collected on a fixed day of every week or month.

9. Stochastic Vehicle Routing Problem (SVRP)

When there is uncertainty in customer demands and travel times, Stochastic Vehicle Routing Problem (SVRP) arises. Solution of this type of VRP is probability-based. This is a significant problem in the industries where demand and travel time varies a lot like delivering groceries and food during the rush hour traffic or rainy day. 

To solve this problem, you need special methods that can handle uncertain situations and give convincing results even when things don’t go as planned.

10. Multi-Depot Vehicle Routing Problem (MDVRP)

The goal of the Multi-Depot Vehicle Routing Problem (MDVRP) is to find the best set of routes for a fleet of vehicles to follow in order to serve a group of clients from multiple depots. The MDVRP aims to reduce the overall distance traveled by all vehicles for serving all customers. 

Each depot has a set of vehicles and a set of customers that it can serve. The MDVRP is applicable to sectors like trash management or public transportation where there are numerous depots that need to be maintained and each station has its own set of clients and vehicles to serve. 

11. The Green Vehicle Routing Problem (GVRP)

The Green Vehicle Routing Problem (GVRP), another variation of vehicle routing problem (VRP), considers factors such as fuel consumption, traffic congestion, and vehicle emissions to minimize the environmental impact of transportation. Industries looking to reduce their carbon footprint and comply with environmental regulations implement GVRP. 

GVRP requires the use of optimization that helps minimize transportation costs and minimizing environmental impact by involving the use of alternative fuels or vehicle technologies. Also developing environmental friendly routing strategies comprises the goal of solving the Green Vehicle Routing Problem (GVRP).

12. Dynamic Vehicle Routing Problem (DVRP)

In the Dynamic Vehicle Routing Problem (DVRP), the problem parameters such as customer demand and travel time are not known quantities but rather evolve over time in response to changes in the environment or customer behavior. DVRP is relevant to industries such as on-demand delivery, where the demand varies on factors such as time of day or location. 

The goal of DVRP is to create and implement routing strategies that can dynamically respond to changes in the environment and customer demand while minimizing the transportation costs during the whole journey.

13. Pickup and Delivery Problem with Time Windows (PDPTW)

In the Pickup and Delivery Problem with Time Windows (PDPTW), the goal is to find the best possible routes for a fleet of vehicles to travel in order to pick up goods from a set of locations and deliver them to a different set of locations while keeping in mind time window restrictions. The PDPTW aims to reduce the overall distance traveled by all vehicles while completing all pickup and delivery requests within each location’s designated time window. 

Each location has a particular time window during which the pickup or delivery operation can take place. The PDPTW is applicable to sectors like package delivery or freight transportation where timely and effective scheduling of pickup and delivery operations is necessary to meet client demands.

14. Inventory Routing Problem (IRP)

Identifying the best inventory and delivery schedule for a business that wants to restock its inventory at several locations while reducing transportation costs is the goal of the Inventory Routing Problem (IRP). The objective of the IRP is to identify the optimum delivery frequency, amount, and route for each location in order to maintain inventory levels within a specific range and reduce transportation costs. 

The IRP is relevant for industries such as fuel delivery or waste management, where inventory levels need to be maintained at multiple locations and transportation costs can be a significant part of the overall operation cost. 

15. Traveling Salesman Problem with Time Windows (TSPTW)

Finding the most efficient route a salesperson can take to visit a group of customers within their designated time windows is the goal of the Traveling Salesman Problem with Time Windows (TSPTW). It is a version of the traditional Traveling Salesman Problem (TSP).

The objective of the TSPTW is to discover the shortest route that visits all customers during their respective time windows. Each client has a defined time window during which they can be visited. The TSPTW is applicable to sectors like transportation where meeting deadlines is necessary to assure timely delivery or service.

16. Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD)

Finding the most efficient set of routes for a fleet of vehicles to simultaneously pick up goods from some sites and deliver items to other places is the goal of the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). 

The VRPSPD aims to reduce the overall distance traveled by all vehicles while ensuring that each vehicle’s capacity is not exceeded. Each stop can either be a pickup or a delivery point. The VRPSPD is applicable to sectors like waste collection or postal delivery where simultaneous pickup and delivery tasks must be coordinated well to reduce transportation costs. 

17. Dial-a-Ride Problem (DARP)

This variation of the Vehicle Routing Problem (VRP) involves finding optimal routes for a fleet of vehicles to handle a variety of pick-up and drop-off requests from different passengers. The objective of the Dial-a-Ride Problem (DARP) is to reduce the overall travel distance and time for all cars while completing all pickup and drop-off requests. Each passenger specifies their pickup and drop-off locations as well as the desired pickup and drop-off timings.

The DARP is applicable to sectors like healthcare or public transit when it is necessary to transport people quickly and efficiently from one place to another. Advanced optimization algorithms are required by the DARP because they can handle the complexity of each passenger request and produce workable solutions that reduce transportation costs while maintaining high levels of service quality.

18. School Bus Routing Problem (SBRP)

In order to determine the best set of routes for a fleet of school buses to convey students from their homes to schools and back, one must solve the “School Bus Routing Problem” (SBRP), another vehicle routing problem. Each student in the SBRP has a specified pick-up and drop-off location and time.

The objective is to reduce the overall travel distance and time for all buses while making sure that no student is missed or comes late. The SBRP is relevant for school transportation systems, where safety, efficiency, and reliability are critical for the transportation of students.

19. Arc Routing Problem (ARP)

The goal of the Arc Routing Problem (ARP) is to find the best set of routes for a fleet of vehicles to travel in order to service a number of arcs or edges in a transportation network. The objective of the ARP is to reduce the overall distance traveled by all vehicles while ensuring that each arc or edge is serviced within a predetermined time window.

Each arc or edge in the network must be visited by one or more vehicles. The ARP is relevant for sectors like trash pickup or mail delivery where it’s important to effectively service network edges to save on transportation expenses.

20. Chinese Postman Problem (CPP)

The Chinese Postman Problem (CPP) is a graph theory problem that aims to determine the quickest way for a postman to visit each street in a particular city or region at least once before heading back to the starting point. Being an NP-hard problem, it is difficult to develop an effective algorithm that can tackle this problem for huge graphs. The CPP has uses in circuit design, DNA sequencing, and transportation planning. Many methods, most notably the Hierholzer’s algorithm, which effectively finds the best solution for Eulerian graphs, have been developed to solve the CPP.

21. Zone Routing Problem (ZRP)

The Zone Routing problem (ZRP) is a transportation optimization problem that entails choosing the most optimal set of routes for a fleet of cars to travel in order to cover a number of zones or locations. The objective of the ZRP is to reduce the overall distance traveled by all vehicles while ensuring that each zone or region is serviced within a predetermined time window. 

Each zone or region must be served by one or more vehicles. The ZRP is applicable to sectors like public transportation or healthcare where it is important to efficiently serve particular zones or areas to minimize the cost of transportation.

22. Pickup and Delivery Problem with Profits (PDPP)

The goal of the Pickup and Delivery Problem with Profits (PDPP) is to choose the best set of routes for a fleet of vehicles to pick up and deliver goods to clients while maximizing the profit made from each delivery. 

The objective of the PDPP is to maximize the total profit made by the vehicle fleet while guaranteeing that all pickups and deliveries are done within a predetermined time window. Each customer has a designated pickup and delivery location and time. The PDPP is applicable to sectors like e-commerce or logistics, where businesses strive to optimize earnings by streamlining their delivery processes.

23. Capacitated Arc Routing Problem (CARP)

The Capacitated Arc Routing Problem (CARP) is a transportation optimization problem in which the goal is to find the best possible set of routes for a fleet of vehicles to travel in order to service a collection of edges or arcs in a graph, each of which has a limited capacity. Every arc has a demand in the CARP, and the objective is to reduce the overall distance traveled by all cars while making sure that no vehicle’s capacity is exceeded. 

The CARP is applicable to sectors like trash management or products transportation where the objective is to reduce transportation costs while maintaining high levels of service quality. Each vehicle has a restricted carrying capacity in these sectors.

Why You Need to Solve Vehicle Routing Problem?

All businesses that include the process of planning and optimizing delivery routes face vehicle routing problems. This includes determining the cost-efficient, effective, and time-saving way to deliver goods or services to a number of customers while considering various factors like time, distance, fuel cost, profitability, vehicle capacity, time windows, and traffic conditions.

There are several benefits of solving vehicle routing problems:

1. Reduce logistics expenses

The main goal of adopting an effective route planning solution is to cut down on logistics expenses significantly. By optimizing delivery routes and minimizing the number of vehicles required for transportation, you can notice a huge impact on your daily logistics expenses. Also, by minimizing fuel costs and other operational costs you can improve your business’s profitability.

2. Achievable sustainable growth

By reducing carbon footprints, an effective VRP solution can help your business achieve sustainable growth. You can reduce the environmental impact and contribute to a more sustainable future by optimizing your delivery routes and reducing the number of vehicles on the road.

3. Save time and increase customer satisfaction

By optimizing delivery routes and saving delivery times using an effective VRP solution can save a lot of time spent in manual route planning. Hence you can utilize this time in other productive tasks of your business and ultimately leading to higher customer satisfaction. This increases the chances of customer retention and repeat business.

What are the Different Ways to Solve Vehicle Routing Problem?

As we are on the same page, knowing what exactly is vehicle routing problem and its types. Now it is the time to look at its solution. Vehicle Routing problems have several solutions. They are:

1. Manually using two-index flow formulation

In the two-index VF formulation, we define the binary decision variable xij that assumes value 1 if and only if there is a route that goes from customer i to j directly, for i, j ∈ N . In addition, yj is a continuous decision variable corresponding to the cumulated demand on the route that visits node j ∈ N up to this visit. With these parameters and decision variables, the two-index flow formulation of the CVRP if given by:

2. Using Google OR-tools

Google OR-tools provide a set of powerful optimization tools for solving various types of vehicle routing problems. Here are the steps to use Google OR-tools to solve VRPs:

Step-1: Define the problem

Firstly, you have to define the problem by specifying the number of vehicles, set of customers, delivery stops, and other delivery constraints such as vehicle capacity and time windows.

Step-2: Formulate the problem

Then, the next step is to formulate the problem as a mathematical model using the OR-tools routing library. The model should consider the objective function, the constraints, and the decision variables.

Step-3: Define the search strategy

In order to find the optimal solution, the third step is to define the search strategy. The Google OR-tools provides several strategies, such as local search, guided local search, simulated annealing.

Step-4: Solve the problem

The last step is to solve the problem using the OR-tools solver. Here is the general code outline to solve a VRP using Google OR-tools:

3. Using route optimization software

The problem with solving vehicle routing problems using the above 2 method is the two-index flow formulation method is too lengthy and humanly complex to perform, while Google OR-tools require a lot of programming knowledge and proficiency in coding. Also, chances of generating errors are more and once an error is generated, you are back to square one.

Now the question arises, isn’t there a single method that is easy to perform and quick to get solutions to various vehicle routing problems?

The answer is yes, with using a proficient route optimization software, you can get quick and easy solutions to VRPs.

Upper Route Planner is one such route optimization software that helps you solve VRPs with its powerful route planning and optimization methods.

Using Upper Route Planner, all you need is a list of stops and available drivers, feed the data in the software, wait for a few seconds, and your optimized routes will be ready in a blink of an eye.

The goal of VRP is to minimize the total cost of delivering goods to customers considering various constraints like distance, time, capacity, fuel costs, profitability, and time window. Route optimization on the other hand does the same task automatically. Algorithms of route optimization software helps you find the optimal routes that minimize overall delivery costs.

Using Upper will lead you to reduced fuel costs, reduced vehicle maintenance costs, and improved customer satisfaction. So, you worry less about customer retention and focus more on serving new customers as well.

Another benefit of using route optimization software like Upper is that you get many other features along with route planning and optimization like:

• Route Scheduling
• Smart Excel Import
• One-click Dispatch
• Proof of Delivery
• Reports and Analytics
• API Integration
• Business-Specific Customization

Conclusion

Vehicle Routing Problem is a complex optimization problem that arises in real-life where the challenge is to find an optimized and efficient route for delivery operations considering various constraints and minimizing delivery costs.

There are several types of VRP, each having unique challenges and solutions. Solving VRPs can result in a reduction in operational costs and a positive graph can be seen in sales. There are various methods to solve VRP ranging from exact methods such as branch and bound and dynamic programming to heuristic and metaheuristic algorithms such as Clarke and Wright savings algorithm, sweep algorithm, and genetic algorithms.

But with increasing automation, these methods have gone outdated and are considered time consuming & complex. So, if you are a delivery business owner facing Vehicle Routing Problems (VRPs), it is the right time to switch to a robust route optimization software that is fast, reliable, and easy-to-use.

When looking for such software, Upper Route Planner is the best choice available in the market. Before trying anything else, get your business the 7 days FREE TRIAL of Upper and start exploring its features.