An Investigation of Adaptive Operator Selection in Solving Complex Vehicle Routing Problem

Search operators play an important role in meta-heuristics. There are typically a variety of search operators available for solving a problem, and the selection and order of using the operators can greatly affect the algorithm performance. Adaptive operator selection (AOS) has been proposed to select operators during optimisation dynamically and adaptively. However, most existing studies focus on real-value optimisation problems, while combinatorial optimisation problems, especially complex routing problems, are seldom considered. Motivated by the effectiveness of AOS on real-value optimisation problems and the urgent need of efficiency in solving real routing problems, this paper investigates AOS in complex routing problems obtained from real-world scenarios, the multi-depot multi-disposal-facility multi-trip capacitated vehicle routing problems (M3CVRPs). Specifically, the stateless AOS, arguable the most classic, intuitive and commonly used category of AOS approaches, is integrated into the region-focused local search (RFLS), the state-of-the-art algorithm for solving M3CVRPs. Unexpectedly and yet within understanding, experimental results show that the original RFLS performs better than the RFLS embedded with stateless AOS approaches. To determine the causes, a novel neighbourhood analysis is conducted to investigate the characteristics of M3CVRP and the factors that affect the performance of the AOS. Experimental results indicate that the momentum assumption of stateless AOS, good operators in history will also work well in current stage, is not satisfied within most of the time during the optimisation of the complex problem, leading to the unstable performance of operators and the failure of stateless AOS.