The multi-depot vehicle routing problem(MDVRP)is one of the most essential and useful variants of the traditional vehicle routing problem(VRP)in supply chain management(SCM)and logistics studies.Many supply chains(SC)...The multi-depot vehicle routing problem(MDVRP)is one of the most essential and useful variants of the traditional vehicle routing problem(VRP)in supply chain management(SCM)and logistics studies.Many supply chains(SC)choose the joint distribution of multiple depots to cut transportation costs and delivery times.However,the ability to deliver quality and fast solutions for MDVRP remains a challenging task.Traditional optimization approaches in operation research(OR)may not be practical to solve MDVRP in real-time.With the latest developments in artificial intelligence(AI),it becomes feasible to apply deep reinforcement learning(DRL)for solving combinatorial routing problems.This paper proposes a new multi-agent deep reinforcement learning(MADRL)model to solve MDVRP.Extensive experiments are conducted to evaluate the performance of the proposed approach.Results show that the developed MADRL model can rapidly capture relative information embedded in graphs and effectively produce quality solutions in real-time.展开更多
为揭示电动车辆路径问题领域的研究与发展现状,对CNKI和Web of Science数据库中电动车辆路径问题1994-2022年间的期刊文献进行知识挖掘与分析。基于文献计量学的量化分析与知识图谱的可视化,通过分析文献外部特征和共被引情况,梳理研究...为揭示电动车辆路径问题领域的研究与发展现状,对CNKI和Web of Science数据库中电动车辆路径问题1994-2022年间的期刊文献进行知识挖掘与分析。基于文献计量学的量化分析与知识图谱的可视化,通过分析文献外部特征和共被引情况,梳理研究热点及热点演进趋势,归纳研究主题,总结出电动车辆路径问题的知识域包括研究主题和应用场景,其中,研究主题由变体研究、充电调度、求解方法三部分构成;对电动车辆路径问题在复杂实际问题、高效求解算法方面的未来发展进行展望,这将为电动车辆路径问题研究的深入化与国际化提供一定的推动作用。展开更多
In this work,we investigate a generalization of the classical capacitated arc routing problem,called the Multi-depot Capacitated Arc Routing Problem(MCARP).We give exact and approximation algorithms for different vari...In this work,we investigate a generalization of the classical capacitated arc routing problem,called the Multi-depot Capacitated Arc Routing Problem(MCARP).We give exact and approximation algorithms for different variants of the MCARP.First,we obtain the first constant-ratio approximation algorithms for the MCARP and its nonfixed destination version.Second,for the multi-depot rural postman problem,i.e.,a special case of the MCARP where the vehicles have infinite capacity,we develop a(2-1/2k+1)-approximation algorithm(k denotes the number of depots).Third,we show the polynomial solvability of the equal-demand MCARP on a line and devise a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line.Lastly,we conduct extensive numerical experiments on the algorithms for the multi-depot rural postman problem to show their effectiveness.展开更多
文摘The multi-depot vehicle routing problem(MDVRP)is one of the most essential and useful variants of the traditional vehicle routing problem(VRP)in supply chain management(SCM)and logistics studies.Many supply chains(SC)choose the joint distribution of multiple depots to cut transportation costs and delivery times.However,the ability to deliver quality and fast solutions for MDVRP remains a challenging task.Traditional optimization approaches in operation research(OR)may not be practical to solve MDVRP in real-time.With the latest developments in artificial intelligence(AI),it becomes feasible to apply deep reinforcement learning(DRL)for solving combinatorial routing problems.This paper proposes a new multi-agent deep reinforcement learning(MADRL)model to solve MDVRP.Extensive experiments are conducted to evaluate the performance of the proposed approach.Results show that the developed MADRL model can rapidly capture relative information embedded in graphs and effectively produce quality solutions in real-time.
文摘为揭示电动车辆路径问题领域的研究与发展现状,对CNKI和Web of Science数据库中电动车辆路径问题1994-2022年间的期刊文献进行知识挖掘与分析。基于文献计量学的量化分析与知识图谱的可视化,通过分析文献外部特征和共被引情况,梳理研究热点及热点演进趋势,归纳研究主题,总结出电动车辆路径问题的知识域包括研究主题和应用场景,其中,研究主题由变体研究、充电调度、求解方法三部分构成;对电动车辆路径问题在复杂实际问题、高效求解算法方面的未来发展进行展望,这将为电动车辆路径问题研究的深入化与国际化提供一定的推动作用。
基金supported by the National Natural Science Foundation of China(Nos.11671135,11871213,11901255)the Natural Science Foundation of Shanghai(No.19ZR1411800)。
文摘In this work,we investigate a generalization of the classical capacitated arc routing problem,called the Multi-depot Capacitated Arc Routing Problem(MCARP).We give exact and approximation algorithms for different variants of the MCARP.First,we obtain the first constant-ratio approximation algorithms for the MCARP and its nonfixed destination version.Second,for the multi-depot rural postman problem,i.e.,a special case of the MCARP where the vehicles have infinite capacity,we develop a(2-1/2k+1)-approximation algorithm(k denotes the number of depots).Third,we show the polynomial solvability of the equal-demand MCARP on a line and devise a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line.Lastly,we conduct extensive numerical experiments on the algorithms for the multi-depot rural postman problem to show their effectiveness.
