Halvor Bø09.04.2022
Hundreds of thousands of trucks drive on the road every day. We have worked on a secret project involving routing trucks around Trondheim. In this article we will share some of our learnings from working through the problem to a prototype.
Routing vehicles is hard. That’s why…
Centuries ago, salesmen visited their customers using the shortest possible route and tried to overcome problems related to their traveling path. Business strategies have evolved in this digital world, and the salesmen’s problems are now interpreted as Vehicle Routing Problems (VRP). In 1959, the VRP was first published by John Ramser and George Dantzig to find the best optimal routes for vehicles. They were the first to use the algorithm to solve the Travel Salesman Problem (TSP).
Vehicle route optimization algorithms are widely being acknowledged today. As per the World Academy of Science, Engineering, and Technology, the ICVRP 2022: 16. International Conference on Vehicle Routing Problem will be held on December 15-16, 2022, in Barcelona, Spain. The conference aims at bringing together research scholars, researchers, and academic scientists to present and exchange their research outcomes and ideas regarding the VRP. Furthermore, educators, practitioners, and researchers will share and discuss the most recent trends, innovations, challenges, concerns, and solutions adopted in the VRP realm.
Undoubtedly, the VRP has become a global concern and grabbing the attention of IT developers and engineers. The VRP is also one of the biggest challenges in supply chain management. Therefore, effective and sustainable distribution systems and transportation management is the need of the hour. To this end, various algorithms and mathematical models have been developed to find optimal routes and cut transportation costs.
This article will take a deep dive to understand the VRP, some of its essential variants, and recommended algorithms to discover the best optimal vehicle routes.
The Vehicle Routing Problem (VRP) is about finding the optimal routes for fleets of vehicles belonging to the NP-hard combinatorial problems class. The key objectives of VRP are to identify a minimal number of vehicles, minimal costs, or the minimal travel time of traveled routes. Moreover, the VRP involves several constraints encompassing time intervals and vehicle capacity. The former is called Vehicle Routing Problem with Time Windows (VRPTW), and the latter is known as the Capacitated Vehicle Routing Problem (CVRP). The subsequent sections list more variants of VRP.
The VRP has been grabbing the attention of automotive engineers for more than 50 years. However, the VRP has paramount importance in real life due to its broad applications. The VRP applies to transportation, manufacturing, communications, travel, logistics, distribution, military, civil systems, etc. D.Jayaranthna et al. discovered in their case study, 2022 – Industrial Vehicle Routing Problem – VRP had increased by leaps and bound at a rate of 6% consistently.
Researchers want to know the routing problems related to electric and hybrid vehicles. The purpose of finding these problems is to determine the optimal route for vehicles. The VRP has several variants that are listed below:
Traveling Salesman Problem (TSP)
The TSP is an NP-hard problem concerned with finding the possible shortest and most efficient route for a vehicle among a set of points and locations. For example, a person wants to visit all the destinations or cities from the list. However, distances among destinations are known, and each destination should be visited once. So, in this scenario, what should be the shortest route that he can visit each destination once and can return to the origin-destination? The following figure demonstrates the illustration of TSP.
Let us consider an equation for TSP, which is G = (V, E). In this equation, “V” is a set of cities, and it can be derived as V = {1…, n}. On the other hand, “E” in the equation denotes a set of weighted edges – elaborated as E = {dij} where dij is the distance between nodes i and j. G = (V, E) should return the shortest Hamiltonian Cycle H that passes through every city only once.
Dantzig et al. define the TSP algorithm.
Recommendation: What Do I Need to Know About Vehicle Route Optimization?
Why Are Hill Climbing and Simulated Annealing Better Algorithms?
What Are Real-World Applications of Hill Climbing and Simulated Annealing Algorithms?
How Hill Climbing and Simulated Annealing Help Developers to Achieve Effective Results?