Stefan Voigt, Catholic University of Eichstätt-Ingolstadt

Abstract

We present an effective metaheuristic framework based on the recently proposed hybrid adaptive large neighborhood search (HALNS) for the vehicle routing problem (VRP) with availability profiles and VRPs with depot location decisions. The HALNS generates a population of solutions by executing an ALNS several times. Then, the population is subject to a crossover phase, during which new individuals are created by re-applying the ALNS that utilizes information from the population. We streamline the HALNS for the capacitated VRP and the VRP with time windows. The versions implemented use specialized removal operators, a simple insertion operator, an improved crossover mechanism, and unlike the HALNS, no adaptive operator selection, leading to the description as hybrid large neighborhood search (HLNS). In the case of the CVRP, we extend the HLNS by a strong local search based on the open-source implementation of Vidal’s hybrid genetic search. The HLNS achieves competitive results on small to medium size benchmark instances, but is less effective for large-scale instances due to the lack of sparsification techniques or neighborhood limitations. Despite this shortcoming, the HLNS is a simple framework that can be easily adapted for further VRP variants.

[Challenge Paper]   [Video]