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)...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.展开更多
文章针对绿色物流中多车场多车型带时间窗的车辆路径问题(Green Vehicle Routing Problem with Time Windows for Multi-depot and Heterogeneous Vehicles, GVRPTW-MDHV),考虑实时载重对车辆油耗和碳排放的影响,引入综合排放模型(Compr...文章针对绿色物流中多车场多车型带时间窗的车辆路径问题(Green Vehicle Routing Problem with Time Windows for Multi-depot and Heterogeneous Vehicles, GVRPTW-MDHV),考虑实时载重对车辆油耗和碳排放的影响,引入综合排放模型(Comprehensive Modal Emission Model, CMEM)对车辆油耗和碳排放进行度量,最终以车辆油耗成本、碳排放成本、固定发车费用、车辆租用费用、车辆人力成本和时间窗惩罚成本之和最小化为优化目标,构建了GVRPTW-MDHV数学模型,并根据模型特点设计改进差分进化算法。算例仿真结果表明,构建的模型和提出的算法能够为不同车场合理调配不同型号车辆,有助于科学规划车辆路径,有效减少油耗量和碳排放量,降低总配送成本。展开更多
基金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.
文摘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.
文摘文章针对绿色物流中多车场多车型带时间窗的车辆路径问题(Green Vehicle Routing Problem with Time Windows for Multi-depot and Heterogeneous Vehicles, GVRPTW-MDHV),考虑实时载重对车辆油耗和碳排放的影响,引入综合排放模型(Comprehensive Modal Emission Model, CMEM)对车辆油耗和碳排放进行度量,最终以车辆油耗成本、碳排放成本、固定发车费用、车辆租用费用、车辆人力成本和时间窗惩罚成本之和最小化为优化目标,构建了GVRPTW-MDHV数学模型,并根据模型特点设计改进差分进化算法。算例仿真结果表明,构建的模型和提出的算法能够为不同车场合理调配不同型号车辆,有助于科学规划车辆路径,有效减少油耗量和碳排放量,降低总配送成本。
