Balancing Exploration and Exploitation in the Memetic Algorithm via a Switching Mechanism for the Large-Scale VRPTW

This paper presents an effective memetic algorithm for the large-scale vehicle routing problem with time windows (VRPTW). Memetic algorithms consist of an evolutionary algorithm for the global exploration and a local search algorithm for the exploitation. In this paper, a switching mechanism is introduced to balance quantitatively between exploration and exploitation, to improve the convergent performance. Specifically, a similarity measure and a sigmoid function is defined to guide the crossover. Experimental results on Gehring and Homberger’s benchmark show that this algorithm outperforms previous approaches and improves 34 best-known solutions out of 180 large-scale instances. Although this paper focuses on the VRPTW, the proposed switching mechanism can be applied to accelerate more general genetic algorithms.