计算机科学 ›› 2025, Vol. 52 ›› Issue (1): 331-344.doi: 10.11896/jsjkx.231200132

• 人工智能 • 上一篇    下一篇

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

蔡俊创, 朱庆灵, 林秋镇, 李坚强, 明仲   

  1. 深圳大学计算机与软件学院 广东 深圳 518060
  • 收稿日期:2023-12-20 修回日期:2024-05-26 出版日期:2025-01-15 发布日期:2025-01-09
  • 通讯作者: 明仲(mingz@szu.edu.cn)
  • 作者简介:(caijunchuang2020@email.szu.edu.cn)
  • 基金资助:
    国家自然科学基金(62272315,62376163,62203308);广东省区域联合基金(2022B1515120076);广东省自然科学基金(2023A1515011238);深圳市科技计划项目(JCYJ20220531101411027)

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

CAI Junchuang, ZHU Qingling, LIN Qiuzhen, LI Jianqiang, MING Zhong   

  1. College of Computer Science and Software Engineering,Shenzhen University,Shenzhen,Guangdong 518060,China
  • Received:2023-12-20 Revised:2024-05-26 Online:2025-01-15 Published:2025-01-09
  • About author:CAI Junchuang,born in 1995,postgra-duate.His main research interests include intelligent optimization algorithms and their applications in the field of logistics.
    MING Zhong,born in 1967,Ph.D,professor,is a senior member of CCF(No.05569S).His main research interests include software engineering and artificial intelligence.
  • Supported by:
    National Natural Science Foundation of China(62272315,62376163,62203308),Guangdong Regional Joint Foundation Key Project(2022B1515120076),Natural Science Foundation of Guangdong Province,China(2023A1515011238) and Shenzhen Science and Technology Program(JCYJ20220531101411027).

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

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

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

中图分类号: 

  • TP301
[1]FENG L,HUANG Y X,ZHOU L,et al.Explicit evolutionary multitasking for combinatorial optimization:A case study on capacitated vehicle routing problem[J].IEEE Transactions on Cybernetics,2020,51(6):3143-3156.
[2]YANG H X,GAO J,SHAO E L.Vehicle routing problem with time window of takeaway food considering one-order-multi-product order delivery[J].Computer Science,2022,49(S1):191-198.
[3]BERBEGLIA G,CORDEAU J F,LAPORTE G.Dynamic pickup and delivery problems[J].European Journal of Operational Research,2010,202(1):8-15.
[4]SAVELSBERGH M W,SOL M.The general pickup and deli-very problem[J].Transportation Science,1995,29(1):17-29.
[5]CAI J C,ZHU Q L,LIN Q Z,et al.A Survey of Dynamic Pickup and Delivery Problems[J].Neurocomputing,2023(14):1.1-1.16.
[6]AVELSBERGH M,SOL M.Drive:Dynamic routing of inde-pendent vehicles[J].Operations Research,1998,46(4):474-490.
[7]SWIHART M R,PAPASTAVROU J D.A stochastic and dynamic model for the single-vehicle pick-up and delivery problem[J].European Journal of Operational Research,1999,114(3):447-464.
[8]ARSLAN A M,AGATZ N,KROON L,et al.Crowdsourced delivery—a dynamic pickup and delivery problem with ad hoc dri-vers[J].Transportation Science,2019,53(1):222-235.
[9]MITROVIĆ-MINIĆ S,KRISHNAMURTI R,LAPORTE G.Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows[J].Transportation Research Part B:Methodological,2004,38(8):669-685.
[10]GENDREAU M,GUERTIN F,POTVIN J Y,et al.Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries[J].Transportation Research Part C:Emerging Technologies,2006,14(3):157-174.
[11]MA Y,HAO X T,HAO J Y,et al.A hierarchical reinforcement learning based optimization framework for large-scale dynamic pickup and delivery problems[J].Advances in Neural Information Processing Systems,2021,34:23609-23620.
[12]SU Z Y,LI W T,LI J C,et al.Heterogeneous fleet vehiclescheduling problems for dynamic pickup and delivery problem with time windows in shared logistics platform:Formulation,instances and algorithms[J].International Journal of Systems Science:Operations & Logistics,2022,9(2):199-223.
[13]XU X F,WEI Z F.Dynamic pickup and delivery problem with transshipments and LIFO constraints[J].Computers & Industrial Engineering,2023,175:108835.
[14]TAO Y,ZHUO H B,LAI X F.The pickup and delivery problem with multiple depots and dynamic occasional drivers in crowdshipping delivery[J].Computers & Industrial Enginee-ring,2023,182:109440.
[15]ULMER M W,THOMAS B W,CAMPBELL A M,et al.The restaurant meal delivery problem:Dynamic pickup and delivery with deadlines and random ready times[J].Transportation Science,2021,55(1):75-100.
[16]DU J H,ZHANG Z Q,WANG X,et al.A hierarchical optimization approach for dynamic pickup and delivery problem with LIFO constraints[J].Transportation Research Part E:Logistics and Transportation Review,2023,175:103131.
[17]LI X J,LUO W L,YUAN M X,et al.Learning to optimize industry-scale dynamic pickup and delivery problems[C]//2021 IEEE 37th International Conference on Data Engineering(ICDE).2021:2511-2522.
[18]GHIANI G,MANNI A,MANNI E.A scalable anticipatory poli-cy for the dynamic pickup and delivery problem[J].Computers & Operations Research,2022,147:105943.
[19]CAI J C,ZHU Q L,LIN Q Z.Variable neighborhood search for a new practical dynamic pickup and delivery problem[J].Swarm and Evolutionary Computation,2022,75:101182.
[20]VONOLFEN S,AFFENZELLER M.Distribution of waitingtime for dynamic pickup and delivery problems[J].Annals of Operations Research,2016,236:359-382.
[21]PUREZA V,LAPORTE G.Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows[J].INFOR:Information Systems and Operational Research,2008,46(3):165-175.
[22]GHIANI G,MANNI E,QUARANTA A,et al.Anticipatory algorithms for same-day courier dispatching[J].Transportation Research Part E:Logistics and Transportation Review,2009,45(1):96-106.
[23]SÁEZ D,CORTÉS C E,NÚÑEZ A.Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery pro-blem based on genetic algorithms and fuzzy clustering[J].Computers & Operations Research,2008,35(11):3412-3438.
[24]SCHILDE M,DOERNER K F,HARTL R F,et al.Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports[J].Computers & Operations Research,2011,38(12):1719-1730.
[25]SCHILDE M,DOERNER K F,HARTL R F.Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem[J].European Journal of Operational Research,2014,238(1):18-30.
[26]HAO J Y,LU J W,LI X J,et al.Introduction to the dynamic pickup and delivery problem benchmark--ICAPS 2021 competition[J].arXiv:2202.01256,2022.
[27]LI H,ZHANG Q F.Multiobjective optimization problems with complicated Pareto sets,MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation,2008,13(2):284-302.
[28]KNOWLES J D,WATSON R A,CORNE D W.Reducing local optima in single-objective problems by multi-objectivization[C]//International Conference on Evolutionary Multi-Criterion Optimization.2001:269-283.
[29]LOCHTEFELD D F,CIARALLO F W.Multiobjectivization via helper-objectives with the tunable objectives problem[J].IEEE Transactions on Evolutionary Computation,2011,16(3):373-390.
[30]MA X L,HUANG Z T,LI X D,et al.Multiobjectivization of single-objective optimization in evolutionary computation:a survey[J].IEEE Transactions on Cybernetics,2021,53(6):3702-3715.
[31]SEGURA C,SEGREDO E,GONZÁLEZ Y,et al.Multiobjectivisation of the antenna positioning problem[C]//International Symposium on Distributed Computing and Artificial Intelligence.2011:319-327.
[32]JENSEN M T.Helper-objectives:Using multi-objective evolutionary algorithms for single-objective optimisation[J].Journal of Mathematical Modelling and Algorithms,2004,3:323-347.
[33]LOCHTEFELD D F,CIARALLO F W.Multi-objectivization via decomposition:An analysis of helper-objectives and complete decomposition[J].European Journal of Operational Research,2015,243(2):395-404.
[34]CARRABS F,CORDEAU J F,LAPORTE G.Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading[J].INFORMS Journal on Computing,2007,19(4):618-632.
[35]ALCALÁ-FDEZ J,SANCHEZ L,GARCIA S,et al.KEEL:a software tool to assess evolutionary algorithms for data mining problems[J].Soft Computing,2009,13:307-318.
[36]WANG H F,CHEN Y Y.A genetic algorithm for the simultaneous delivery and pickup problems with time window[J].Computers & Industrial Engineering,2012,62(1):84-95.
[37]LIU S C,TANG K,YAO X.Memetic search for vehicle routing with simultaneous pickup-delivery and time windows[J].Swarm and Evolutionary Computation,2021,66:100927.
[38]FENG L,ZHOU L,GUPTA A,et al.Solving generalized vehicle routing problem with occasional drivers via evolutionary multitasking[J].IEEE Transactions on Cybernetics,2019,51(6):3171-3184.
[39]TIAN Y,ZHANG T,XIAO J H,et al.A coevolutionary framework for constrained multiobjective optimization problems[J].IEEE Transactions on Evolutionary Computation,2020,25(1):102-116.
[40]LI J Q,CAI J C,SUN T,et al.Multitask-based evolutionary optimization for vehicle routing problems in autonomous transportation[J].IEEE Transactions on Automation Science and Engineering,2023,21(3):2400-2411.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!