【作者】 金鑫；

【导师】 秦虎；

【作者基本信息】 华中科技大学 ， 管理科学与工程， 2022， 博士

【摘要】 弧路径优化问题是运筹优化领域中经典的组合优化问题。在物流运输系统以及生产生活中,弧路径优化问题在邮政投递、道路洒水服务、城市垃圾收集和快递企业干线运输等方面均有着广泛的应用,具有重要的研究价值和实际应用价值。本文从弧路径优化的角度出发,首先在限容量弧路径优化问题的基础上分别考虑不同的因素,对混合图上需求可拆分的限容量弧路径优化问题、带时变惩罚值的限容量弧路径优化问题以及计重收费下需求可拆分多车场多车型的限容量弧路径优化问题三种扩展问题进行了研究。最后,探索了如何运用深度强化学习方法求解限容量弧路径优化问题。首先,针对道路洒水服务中路网存在单行道和双行道,以及道路可以由多辆车协同作业的情况,凝练出混合图上需求可拆分的限容量弧路径优化问题,并建立此问题的三下标边流模型。同时,提出森林表示法,设计出基于贪婪规则的深度优先遍历算法以检查解的可行性,并提出动态规划方法决策每条车辆路径中无向边的最优行驶方向以计算解的目标值。然后,在对车辆路径优化问题中经典邻域搜索算子进行适应性改动的基础上,提出两种新的邻域搜索算子,并设计出基于森林表示法的禁忌搜索算法框架。最后,在需求可拆分的限容量弧路径优化问题的81个算例上,将此算法与现有文献中两种最好的算法进行对比,实验结果表明此算法优于现有最好算法。并根据企业实际应用背景构建出SDMCARP的243个算例,实验结果表明此算法的性能远远优于CPLEX。其次,针对路肩清洗服务中按规划中作业车辆的工作时间制定出对应道路的禁止停车时段会带来潜在影响的情况,凝练出带时变惩罚值的限容量弧路径优化问题,并建立此问题的四下标边流模型。同时,设计出动态规划方法对每条车辆路径中有需求边的最优开始服务时间进行决策以最小化惩罚成本。在对车辆路径优化问题中现有经典邻域搜索算子进行适应性改动的基础上,设计出两种快速邻域搜索算子以加速搜索过程。然后,提出关于邻域搜索算子执行顺序的动态调整策略,并设计出基于动态优先级策略的变邻域搜索算法。最后,根据企业的实际应用背景构建出CARPTPC的57个算例,实验结果验证了此算法的性能。第三,针对快递企业干线运输过程中所存在的多车型、多车场、需求可拆分、时间窗和计重收费方式等实际因素,凝练出计重收费下需求可拆分多车场多车型的限容量弧路径优化问题,并建立此问题的三下标边流模型。同时,设计出基于回溯的深度优先搜索算法求解出每条有需求的边对应所有可能的车队服务模式组合,以确定邻域的搜索范围进而提出对应的车队服务模式搜索算子。然后,提出将邻域空间拆分为同构车队和异构车队下的搜索策略,并设计出基于邻域分解的混合搜索算法。最后,在现有文献所提出的84个标准算例上,将此算法与文献中两种最好的精确算法进行对比,实验结果验证了算法的性能。最后,针对当前限容量弧路径优化问题的求解算法需要根据特定的问题结构进行设计的情况,将此问题转换为一个从序列到序列的问题,设计出基于深度强化学习的两阶段启发式算法:第一阶段通过所设计的深度强化学习网络模型预测得到所有的有需求边序列,第二阶段通过动态规划方法将序列最优地划分为多条考虑车辆容量约束的车辆路径。大量的数值实验结果表明,深度强化学习方法具有用于解决实际问题的巨大潜力,而且在求解时间方面具有很大的优势。更多还原

【Abstract】 The Arc Routing Problem(ARP)is a classical combinatorial optimization problem in the Operation Research.In the logistics transportation systems,routine production and daily life,ARP has a wide range of applications in postal delivery,water sprinkling service,and line-haul transportation process of express firm,which has important research value and practical application value.From the angle of ARP,this dissertation considers different factors on the basis of the Capacitated Arc Routing Problem firstly.Three extended problems are studied,namely,the Split-Delivery Mixed Capacitated Arc-Routing Problem(SDMCARP),the Capacitated Arc-Routing Problem with Time-Dependent Penalty Cost(CARPTPC)and the SplitDelivery Multi-Depot Heterogeneous Fleet Capacitated Arc-Routing Problem with Toll-byweight Cost(SDMDHFCARPTC).Then,how to apply the deep reinforcement learning method to solve the Capacitated Arc Routing Problem(CARP)is investigated.Firstly,considering the one-way and two-way roads in the city road network,and the roads that need to be served(or sprinkled)could be partially served by more than one vehicle,the SDMCARP is presented and a mathematical formulation is formulated.Moreover,the forest representation is proposed.A depth-first traversal method based on the greedy rule is designed for the feasibility checking of a solution,and an effective dynamic programming method is proposed for the objective calculation,which decides the optimal visiting direction of each edge in every vehicle route.Based on two neighborhood operators adapted from the classic neighborhood operators in the vehicle routing problem,two new neighborhood operators are proposed and a forest-based tabu search algorithm is designed to solve this problem.Subsequently,the proposed algorithm is compared with two state-ofthe-art heuristic algorithms based on 81 standard instances of the split delivery capacitated arc routing problem.Numerical experiments show that the proposed algorithm ourperforms two state-of-the-art heuristic algorithms.In addition,the proposed algorithm is compared with the CPLEX based on 243 generated SDMCARP instances,and the numerical experiments show that the proposed algorithm generates high quality solution in a much shorter time than CPLEX.Secondly,the CARPTPC is investigated by considering the potential impact of formulating the corresponding road’s no-parking period according to the working hours of the operating vehicle in a practical application of road shoulder cleaning,and the mathematical formulation is formulated.A dynamic programming method is designed to calculate the minimum penalty cost,which determines the optimal service beginning time of each edge in the vehicle route.Based on the neighborhood operators adapted from the classic neighborhood operators in the vehicle routing problem,two new fast neighborhood operators are proposed to accelerate the search process of metaheuristic algorithm.Moreover,a priority maintenance strategy is introduced for dynamically ordering the neighborhood operators,and a dynamic-priority-strategy-based variable neighborhood search algorithm is designed to solve this problem.Subsequently,the proposed algorithm is compared with the CPLEX based on 57 generated instances,and the numerical experiments show that the proposed algorithm generates high quality solution in a much shorter time than CPLEX,especially when the problem scale is quite large.Thirdly,the SDMDHFCARPTC is studied in view of considering several practical features in the line-haul transporatation process of express firm,such as heterogeneous fleet,multi-depot,time windows,split delivery and toll-by-weight scheme,and the mathematical formulation is formulated.Moreover,a depth-first traversal method based on the backtracking is designed to find all the combinations of fleet patterns to fully serve each required edge,which can clarify the neighborhood space to design the fleet pattern neighborhood operator.A neighborhood search strategy for dividing the neighborhood into two parts is introduced: the homogeneous fleet neighborhood and the heterogeneous fleet neighborhood,and a neighborhood-decomposition-based hybrid search algorithm is designed to solve this problem.Subsequently,the proposed algorithm is compared with two state-of-the-art exact methods based on 84 standard instances.Numerical experiments demonstrate the effectiveness the proposed algorithm.At last,in view of the algorithms for solving the CARP are needed to be designed according to the specific knowledge of problem,the CARP is converted into a sequence-tosequence problem.A deep-reinforcement-learning-based two-stage heuristic method is developed: at the first stage,the improved deep reinforcement learning network model predicts the visited sequence of the required edges;and at the second stage,the designed dynamic programming method divides the visited sequence into multiple vehicle routes optimally,which considers the vehicle capacity constraints.Numerical experiments show that the deep reinforcement learning method has great potential for solving the practical problems,and it has great advantages in terms of computation time.更多还原