Fast Local Searches For The Vehicle Routing Problem With Time Windows

Abstract

The purpose of this paper is to present new deterministic local searches for solving the vehicle routing problem with time windows. The proposed algorithms are based on a new three-phase approach. In the first phase an initial solution is created with one ofthe two proposed route construction heuristics. In the second phase a special local search operator based on ejection chains is used to reduce the number of routes. Finally, in the third phase well-known Or-opt exchanges are used to minimize the total distance of the routes. The findings of computational experiments indicate that the proposed methods are competitive with the best approaches proposed earlier in the literature in terms of solution quality, while being much faster. Moreover, the proposed algorithms may easily be used to create initial solutions for a wide variety of vehicle routing algorithms.

Résumé

L’objectif de cet article est de présenter de nouvelles recherches locales déterministes pour résoudre le problème de tournées de véhicules avec fenêtres de temps. Les algorithmes proposés sont basés sur une nouvelle approche en trois étapes. Dans la première étape, une solution de départ est obtenue avec l’une des deux heuristiques de construction de route proposées. Dans la seconde étape, une recherche spéciale basée sur des chaînes d’éjection est utilisée de manière à réduire le nombre de routes. Finalement, dans une troisième étape, un voisinage classique Or-Opt est utilisé pour minimiser la longueur totales des routes. Les résultats des calculs expérimentaux indiquent que les méthodes proposées sont, en terme de qualité, concurrentielles avec les meilleures approches proposées auparavant dans la littérature tout en étant nettement plus rapides. En outre, les algorithmes proposés peuvent facilement être utilisés pour obtenir des solutions initiales pour un large éventail d’algorithmes de tournées de véhicules.

Additional information

Notes on contributors

Olli Bräysy

Olli Bräysy is currently a Research Scientist at SINTEF Applied Mathematics, Department of Optimization in Oslo, Norway. He received the master, licentiate and doctoral degrees from Department of Mathematics and Statistics at the University of Vaasa, Finland in years 1998–2001. His research interests are focused on different routing and scheduling problems and heuristic and metaheuristic solution methods.