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.展开更多
针对现有多车场车辆路径问题研究多局限于同质商品配送的现状,提出考虑车场商品库存差异与客户多商品需求的多车场协同配送车辆路径问题(multi-depot collaborative distribution vehicle routing problem with multi-commodity,MDCDVRP...针对现有多车场车辆路径问题研究多局限于同质商品配送的现状,提出考虑车场商品库存差异与客户多商品需求的多车场协同配送车辆路径问题(multi-depot collaborative distribution vehicle routing problem with multi-commodity,MDCDVRPMC),通过订单拆分处理异构需求,构建以运输成本最小化为目标的混合整数规划模型,并设计增强型自适应大邻域搜索(enhanced adaptive large neighborhood search,EALNS)算法进行求解。该算法融合K-means聚类、节约算法和贪婪重组策略生成初始解,采用自适应大邻域搜索算法避免早熟收敛,结合2-opt邻域操作与模拟退火Metropolis准则实现深度优化。最后,采用Gurobi求解器与自适应大邻域搜索(ALNS)、遗传算法(genetic algorithm,GA)和蚁群算法(ant colony optimization,ACO)进行标准案例测试,验证模型正确性与算法性能。结果表明:EALNS在保证解质量的前提下,求解效率显著提升(求解时间仅为Gurobi的2%);相较于对比算法,其求解质量提升13%~35%,解稳定性提高20%~40%,展现出更优的收敛性能和鲁棒性。研究成果为复杂物流环境下多车场的协同配送提供了高效解决方案,有效拓展了车辆路径优化理论在实际物流场景中的应用范围。展开更多
针对多仓库异质车队带时间窗的车辆路径问题(Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows,MDHFVRPTW),以车辆数费用和物流成本最小为目标,综合客户需求、时间约束等因素构建数学模型,并提出改进智能水...针对多仓库异质车队带时间窗的车辆路径问题(Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows,MDHFVRPTW),以车辆数费用和物流成本最小为目标,综合客户需求、时间约束等因素构建数学模型,并提出改进智能水滴算法(Improved Intelligent Waterdrop Algorithm,IIWD)求解。引入大邻域搜索方法及模拟退火可接受概率准则,重新定义了算法的水滴路径,有效优化智能水滴算法的局部搜索能力。Cordeau标准测试算例和实际算例的求解结果显示,算法在寻优能力上较其他算法更强,求解时间也有明显提升,充分验证了算法的有效性与可行性。展开更多
基金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.
文摘针对现有多车场车辆路径问题研究多局限于同质商品配送的现状,提出考虑车场商品库存差异与客户多商品需求的多车场协同配送车辆路径问题(multi-depot collaborative distribution vehicle routing problem with multi-commodity,MDCDVRPMC),通过订单拆分处理异构需求,构建以运输成本最小化为目标的混合整数规划模型,并设计增强型自适应大邻域搜索(enhanced adaptive large neighborhood search,EALNS)算法进行求解。该算法融合K-means聚类、节约算法和贪婪重组策略生成初始解,采用自适应大邻域搜索算法避免早熟收敛,结合2-opt邻域操作与模拟退火Metropolis准则实现深度优化。最后,采用Gurobi求解器与自适应大邻域搜索(ALNS)、遗传算法(genetic algorithm,GA)和蚁群算法(ant colony optimization,ACO)进行标准案例测试,验证模型正确性与算法性能。结果表明:EALNS在保证解质量的前提下,求解效率显著提升(求解时间仅为Gurobi的2%);相较于对比算法,其求解质量提升13%~35%,解稳定性提高20%~40%,展现出更优的收敛性能和鲁棒性。研究成果为复杂物流环境下多车场的协同配送提供了高效解决方案,有效拓展了车辆路径优化理论在实际物流场景中的应用范围。
文摘针对多仓库异质车队带时间窗的车辆路径问题(Multi-Depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows,MDHFVRPTW),以车辆数费用和物流成本最小为目标,综合客户需求、时间约束等因素构建数学模型,并提出改进智能水滴算法(Improved Intelligent Waterdrop Algorithm,IIWD)求解。引入大邻域搜索方法及模拟退火可接受概率准则,重新定义了算法的水滴路径,有效优化智能水滴算法的局部搜索能力。Cordeau标准测试算例和实际算例的求解结果显示,算法在寻优能力上较其他算法更强,求解时间也有明显提升,充分验证了算法的有效性与可行性。
