A Case Study of Vehicle Route Optimization
This work addresses practical route optimization for logistics and transportation industries, but it is incremental as it builds on existing methods like GA and ACO.
The paper tackled the rich Vehicle Routing Problem (rVRP) by incorporating real-world constraints and proposing a two-stage strategy with a Timeline algorithm for time windows and pause times, applying Genetic Algorithm and Ant Colony Optimization individually, and showed that their approach handles all constraints in a reasonable time across eight problem instances.
In the last decades, the classical Vehicle Routing Problem (VRP), i.e., assigning a set of orders to vehicles and planning their routes has been intensively researched. As only the assignment of order to vehicles and their routes is already an NP-complete problem, the application of these algorithms in practice often fails to take into account the constraints and restrictions that apply in real-world applications, the so called rich VRP (rVRP) and are limited to single aspects. In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times, and apply a Genetic Algorithm (GA) and Ant Colony Optimization (ACO) individually to the problem to find optimal solutions. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.