Research On Optimization Of Capacitated Arc Routing Problems Considering Various Factors

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.