An Intensification-Enhanced Adaptive Hybrid Memetic Algorithm for the Multi-Depot Vehicle Routing Problem with Time Windows

Abstract

The Multi-Depot Vehicle Routing Problem with Time Windows (MDVRPTW) is categorized as NP-hard in terms of logistics planning, given the various constraints and some inherent combinatorial nature of the problem.  This consisted of multiple depots serving customers widely dispersed in a region and constrained by service time windows and vehicle capacity.  Achieving effective solutions will lower logistics operation costs and improve service levels.  There are different types of metaheuristic algorithms that have been applied to MDVRPTW, including Genetic Algorithms, Simulate Annealing, Tabu Search, and Differential Evolution, but each is faced with its own difficulty in avoiding premature convergence and maintaining a balance between exploration and exploitation.  A new variant of Memetic Algorithm is presented in this paper known as Intensification-Enhanced Adaptive Hybrid Memetic Algorithm (IA-AHMA) to tackle the MDVRPTW.  The framework employs adaptive penalty approaches, permutation-based crossover (PMX) operators, a hybrid 2-opt/relocate local search, and on-line parameter tuning to dynamically balance exploration and exploitation.  The outcomes of the experiments conducted with standard benchmark instances indicate that this method improved the quality of solutions compared to Differential Evolution (DE) and a traditional Genetic Algorithm (GA).  The best-found fitness was improved on average 7.8% over GA and 12.3% over DE while lowering variance by 31.6% and 24.1% respectively.  The results show that adding a form of adaptive intensification to a memetic framework works effectively for difficult multi-depot routing problems with time considerations.