A genetic algorithm for vehicle routing problems with time windows based on cluster of geographic positions and time windows

The vehicle routing problem with time windows (VRPTW) has attracted many scholars' attention because it plays an important role in distribution and logistics. Many studies show that (meta-)heuristics are practical approaches for VRPTW. However, how to efficiently utilizing characteristics of customers' time windows and geographic distributions is neglected in last few years. Thus, this paper proposes an improved genetic algorithm (GA) for VRPTW based on a c lustering method and the l ongest c ommon s ubstring (LCS) of elite and inferior individuals. In the proposed algorithm, called CLCS-GA, cluster information of customers' geographic distributions and time windows is utilized to initialize three subpopulations with distinct properties. Moreover, during the evolutionary process, the LCS of elite and inferior individuals is utilized in the crossover and mutation operators to speedup the convergence and help individuals jump out of local optima. When performing the local search, which is a crucial operator for optimizing VRPTW, relatedness measured by customers' geographic distribution and time windows are considered, aiming to overcome the blindness of the common local search. Comprehensive properties of CLCS-GA are extensively testified by 56 VRPTW instances, in which seven state-of-art algorithms are adopted as peer algorithms. Moreover, distinct characteristics of the proposed strategies are also analyzed based on a set of experiments.