Title: Balancing exploration and exploitation in the memetic algorithm via a switching mechanism for the large-scale VRPTW
Authors: Ying Zhang, Dandan Zhang, Longfei Wang, Zhu He and Haoyuan Hu
Abstract: 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.
