Introduction
VRP is a combinatorial optimization and integer programming problem that asks “What is the optimum route for a fleet of vehicles to take in order to deliver to a set of customers?”. This is a generalization of the well-known traveling salesman problem (TSP). If you are not familiar with the TSP problem, it is this: Given a set of cities and the distance between every pair of cities, the challenge is to find the shortest route that visits every city exactly once and returns to the starting point.
Every organization always looks for a window where they can minimize the cost of the process whether its production or distribution or promotions.
VRP is an amazing process which provides you a best and faster way to cover your targets in most efficient ways through optimizing the transportation system.
The VRP concerns the service of a delivery company. The process of delivering things from one or more depots that have a given set of home vehicles, driven by drivers who can move along a given road network, to a set of clients.
To determine the global cost of each route, the cost of travel and the travel time between each customer and the depot must be known. To achieve this, our original graph is transformed into one where the vertices represent the customers and depots, and the arcs represent the routes between them. On the original road network, each arc has the lowest cost between the two points. Since shortest path problems are relatively simple to solve, this is not a difficult task. The original sparse graph is transformed into a complete one.
According to wikipedia, The VRP has many direct applications in industry. In fact, the use of computer optimization programs can give savings of 5% to a company as transportation is usually a significant component of the cost of a product (10%) – indeed, the transportation sector makes up 10% of the EU’s GDP. Consequently, any savings created by the VRP, even less than 5%, are significant.
The objective of the VRP is to minimize the total route cost.
The objective function of a VRP can be very different depending on the particular application of the result but a few of the more common objectives are:
- Using the global distance traveled as well as the fixed costs associated with used vehicles and drivers, minimize global transportation costs
- Reduce the number of vehicles needed to serve all customers
- Least variation in travel time and vehicle load
- Reduce penalties for low quality service
- Maximize a collected profit/score.
The scope of the optimization shows the power of the VRP and how everyone is adjusting to it. In addition to VRP, there are other optimization algorithms, but VRP stands out due to its generalized form and ease of implementation.
The process of optimizing is complex, and there are also many constraints associated with it
The two main approach to routes are intra- route and inter-route are as follows:
- Inter-Route: Few studies examine inter-route constraints, which are global constraints. Hempsch and Irnich propose a generic model for VRPs with inter-route constraints and devise efficient local search techniques for evaluating neighborhood solutions taking inter-route constraints into account.
Most of the extensions are intra-route constraints, i.e., constraint affecting only one route. Among them are limited vehicle capacities, time windows for serving customers, and priority relationships (e.g., pickups and deliveries).
There are lot of challenges to it and are as follows
Reaching out to each customer
If fail to reach out to the customer within given range of data and time, it would be biggest bad mark for service provider
- Covers each customer on same path
It is important to cover everyone on the same path or else it would take another round for transportation to reach out
- Aware of dead end and one way route
This is a part where driver needs to follows the exact instruction provided by service provider
- Coming back to the warehouse
The amount of load on a vehicle can also optimize the cost and time.
- Sometimes there are some conditions that product should be delivered within some given constraints like office time, non office time, also other restrictions given by service providers to get back to the warehouse before the specific time.
To Conclude
In order to handle all those challenges and restrictions I think VRP is an outstanding solution to most of the delivery organizations and also for other processes like production line and others.
The way these optimization works and has an impact in terms of time and cost is really exceptional. The records on money saving can differ but we all know how much time can be saved by using VRP and we all know that time is money.