Elastic Strategy-Based Adaptive Genetic Algorithm for Solving Dynamic Vehicle Routing Problem With Time Windows

With the rapid development of the economy, the increasingly diversified and personalized needs of consumers, the timeliness of logistics distribution has attracted more and more attention of enterprises and customers. However, modern logistics enterprises need to consider the emergence of several dynamic demands in the distribution process to realize the dynamic planning of the routes. This paper puts forward an adaptive genetic algorithm (AGA) with the elastic strategy to solve the dynamic vehicle routing problem with time windows (DVRPTWs), and the proposed algorithm is denoted as AGA-ES-TW. Firstly, AGA designs a population initialization method considering time windows, and designs an adaptive local search strategy that realizes the adaptive local adjustment of different individuals. Meanwhile, AGA develops adaptive crossover and mutation operators, which could adaptively adjust the probability of evolution for different individuals. The experiments prove the better performance of AGA on the traditional vehicle routing problem with time windows (VRPTWs). Then, AGA cooperates with an elastic strategy to deal with DVRPTWs. This paper major considers four types of dynamic demands: the increase of distribution nodes, the decrease of distribution nodes, the change of distribution road conditions, and the change of time windows. The proposed AGA-ES-TW could detect the types of different demands, and adaptively adopt diverse strategies to deal with the corresponding demands, then plan reasonable routes. The experiments on benchmark data sets indicate that AGA-ES-TW performs well on solving DVRPTWs. Furthermore, this paper constructs the distribution information of 100 SF express stations in Xi'an based on actual information, and employs AGA-ES-TW to solve the actual DVRPTWs.