# A Case Study of Vehicle Route Optimization

**Authors:** Veronika Lesch, Maximilian König, Samuel Kounev, Anthony Stein, Christian Krupitzer  
**arXiv:** [2111.09087](https://arxiv.org/abs/2111.09087)  
**Date:** 2021-11-17  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2111.09087v1/

## Key points

- Extensive research has been conducted on the classical Vehicle Routing Problem (VRP) focusing on assigning orders to vehicles and planning their routes.
- Existing algorithms often struggle to incorporate real-world constraints and restrictions, known as rich VRP (rVRP), limiting practical application.
- A team of researchers led by Veronika Lesch, Maximilian König, Samuel Kounev, Anthony Stein, and Christian Krupitzer proposed a novel approach that integrates key real-world constraints and requirements.
- The study introduces a two-stage strategy along with a Timeline algorithm designed to efficiently handle time windows and pause times.
- Genetic Algorithm (GA) and Ant Colony Optimization (ACO) are applied individually to find optimal solutions considering all relevant constraints.
- Evaluation against four state-of-the-art algorithms demonstrated the effectiveness of their approach in handling given constraints within a reasonable timeframe.
- Collaboration with a company partner involved real-world scenarios with up to 100 orders and 13 vehicles.
- The paper provides an in-depth discussion on related work in transportation problems such as Traveling Salesman Problem (TSP) and VRP dating back to the last century.
- Various extensions of VRP are explored in the literature, including capacitated VRP (C-VRP) that imposes capacity constraints on vehicle fleets.

## Summary

Over the past few decades, extensive research has been conducted on the classical Vehicle Routing Problem (VRP), which focuses on assigning orders to vehicles and planning their routes. However, existing algorithms often struggle to incorporate real-world constraints and restrictions, known as rich VRP (rVRP), limiting their practical application. To address this challenge, a team of researchers led by Veronika Lesch, Maximilian König, Samuel Kounev, Anthony Stein, and Christian Krupitzer proposed a novel approach that integrates key real-world constraints and requirements. Their study introduces a two-stage strategy along with a Timeline algorithm designed to efficiently handle time windows and pause times. By applying Genetic Algorithm (GA) and Ant Colony Optimization (ACO) individually to the problem at hand, the team aimed to find optimal solutions that consider all relevant constraints. The evaluation of eight different problem instances against four state-of-the-art algorithms demonstrated that their approach effectively handles all given constraints within a reasonable timeframe. Furthermore, the researchers conducted their evaluation in collaboration with a company partner using real-world scenarios involving up to 100 orders and 13 vehicles. The paper provides an in-depth discussion on related work in transportation problems such as Traveling Salesman Problem (TSP) and VRP dating back to the last century. Various extensions of VRP are explored in the literature, including capacitated VRP (C-VRP) introduced by Cordeau et al., which imposes capacity constraints on vehicle fleets. Overall, this study offers a comprehensive analysis of how incorporating real-world constraints can enhance traditional VRP solutions. The detailed evaluation and discussion presented in the paper shed light on the effectiveness of their proposed approach in addressing complex routing challenges faced in practical applications.