Hybrid adaptive large neighborhood search for vehicle routing problemswith depot location decisions

This article considers three variants of the vehicle routing problem (VRP). These variants determine therespective depot locations from which customers are supplied, i.e., the two-echelon VRP (2E-VRP), the locationrouting problem (LRP), and the multi-depot VRP (MDVRP). Both the LRP and the MDVRP can be formulatedas special cases of the 2E-VRP, so that all three problem classes can be readily solved via a single solutionapproach. We develop such a unified solution approach for all three problem classes based on the recentlyproposed hybrid adaptive large neighborhood search (HALNS). The HALNS uses a population of solutionsgenerated by an efficient ALNS. Individuals of this population are subject to a crossover and selection phase,using elements of genetic algorithms resulting in a hybrid heuristic. Computational experiments on several setsof instances from literature demonstrate the competitive performance of the HALNS. The HALNS outperformsall approaches for solving the 2E-VRP and is on par with heuristics that are dedicated either to the LRP orthe MDVRP. Furthermore, the HALNS shows superior robustness, i.e., the variance of results from severalruns is comparatively low. The HALNS especially outperforms all existing pure ALNS implementations onthese problem classes, demonstrating the value of hybridization. Additionally, the HALNS finds three newbest-known solutions for LRP instances.

Automated summary

This article examines three variants of the vehicle routing problem and proposes a unified solution approach based on hybrid adaptive large neighborhood search. Experimental results demonstrate the competitive performance and superior robustness of this approach.