关键词: 动态取送货问题, 分解方法, 多目标进化算法, 局部搜索, 组合优化

Abstract: Due to the constraints of industrial dynamic pickup and delivery problems(DPDPs),such as docks,time windows,capacity,and last-in-first-out loading,most of the existing vehicle routing algorithms only optimize a single weighted objective function,which is difficult to maintain the diversity of solutions,so it is easily get stuck in local optimal region and stop converging.To alleviate this issue,this paper introduces a decomposition-based multi-objective evolutionary algorithm with efficient local search for solving the above DPDPs.Firstly,our algorithm models the DPDP into a multi-objective optimization problem(MOP),which is further decomposed into multiple sub-problems and solves them simultaneously.Then,crossover operation is used to enhance the diversity of solutions,followed by using an efficient local search to speed up the convergence.By this way,our algorithm can better balance the diversity and convergence of solutions when solving this MOP.Finally,the best solution can be selected from the population to complete the pickup and delivery tasks.Simulation results on 64 test problems from practical scenario of Huawei company demonstrate that our algorithm outperforms other competitive algorithms for tackling DPDPs.Meanwhile,the algorithm is also tested on 20 large-scale delivery problems of JD Logistics to validate its generalization.

Key words: Dynamic pickup and delivery problem, Decomposition method, Multi-objective evolutionary algorithm, Local search, Combinatorial optimization