面向工业动态取送货问题的分解多目标进化算法  

Decomposition-based Multi-objective Evolutionary Algorithm for Industrial Dynamic Pickup andDelivery Problems

作　　者：蔡俊创 朱庆灵 林秋镇[1] 李坚强[1] 明仲[1] CAI Junchuang;ZHU Qingling;LIN Qiuzhen;LI Jianqiang;MING Zhong(College of Computer Science and Software Engineering,Shenzhen University,Shenzhen,Guangdong 518060,China)

机构地区：[1]深圳大学计算机与软件学院,广东深圳518060

出　　处：《计算机科学》2025年第1期331-344,共14页Computer Science

基　　金：国家自然科学基金(62272315,62376163,62203308);广东省区域联合基金(2022B1515120076);广东省自然科学基金(2023A1515011238);深圳市科技计划项目(JCYJ20220531101411027)。

摘　　要：由于工业动态取送货问题具有垛口、时间窗、容量、后进先出装载等多种约束,现有的车辆路径算法大多只优化一个加权目标函数,在求解过程中难以保持解的多样性,所以容易陷入局部最优区域而停止收敛。针对上述问题,提出了一种融合高效局部搜索策略的分解多目标进化算法。首先,该算法将工业动态取送货问题建模成多目标优化问题,进一步将其分解为多个子问题并同时进行求解。然后,利用交叉操作增强解的多样性,再使用局部搜索加快收敛速度。因此,该算法在求解该多目标优化问题时能够更好地平衡解的多样性和收敛性。最后,从种群中选择一个最好的解来完成当前时段的取送货任务。基于64个华为公司实际测试问题的仿真结果表明,该算法在求解工业动态取送货问题上的性能表现最优;同时,在20个京东物流大规模配送问题上的实验也验证了该算法良好的泛化性。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.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]