Research On Coordinated Arc Routing Optimization With Ground Vehicles And Drones

In order to maintain the stability of urban traffic system,reduce the impact of congestion,traffic accidents and other adverse factors on the operation of the urban traffic system,the city is mainly through police cars for traffic patrol.Different from the vehicle routing problem,the patrol problem visits the arcs in the road network instead of nodes,and the essence of the problem is arc routing.However,ground vehicle patrols are not flexible and time-sensitive enough.Combining drones with vehicles can give full play to the flexibility,maneuverability and timeliness of drones,and solve the problem of limited battery life of drones.In this case,coordinated arc routing optimization with vehicles and drones has become a new research direction.This thesis takes urban traffic patrolling as the application background.According to the different coordination mode of vehicles and drones,it focuses on three aspects: single-vehicle and single-drone cooperation,single-vehicle and multi-drone cooperation,and multivehicle and multi-drone cooperation.The main research contents of this thesis are as follows:(1)Aiming at the arc routing problem of single-vehicle and single-drone performing small-scale patrol tasks,a two-stage heuristic algorithm based on greedy rule is proposed.In the first stage,all tasks are assigned to the vehicle,and an optimal vehicle route is obtained through a heuristic algorithm.In the second stage,through the heuristic routing optimization thought of "trial distribution",tasks in the vehicle route are assigned to the drone one by one.Meanwhile,the greedy rule is used to determine whether each "trial distribution " can optimize the route until all the tasks are traversed.A simulated road network is established on the classic Sioux Falls network to conduct experiments.Experimental results of different tasks show that the total time required for the vehicle and drone is reduced by up to 30%compared with that required by the ground vehicle alone.(2)An improved randomized variable neighborhood descent algorithm is proposed to solve the arc routing problem of singlevehicle and multi-drone performing large-scale patrol tasks.In order to solve the problem,a randomized variable neighborhood descent algorithm combined with simulated annealing is designed.The algorithm contains multiple problem-based neighborhood structures and the simulated annealing mechanism,so that it has global optimization and high solving performance,and is suitable for the application scenarios of large-scale patrol tasks.For the initial solution,the coding mode of the tasks is designed to represent the task combination performed in a drone flight,and the task coding is initialized to generate the initial solution.Experimental results show that compared with VND algorithm,VND-SA algorithm and RVND algorithm,the proposed method in this thesis can show superior performance in tasks of different scales,and a good balance is achieved between the solution results and the running time.(3)In order to improve the execution efficiency of large-scale patrol tasks,a multi-vehicle and multi-drone mode is proposed,and an arc routing framework based on divide-and-conquer strategy is designed.Through the divide-and-conquer strategy,the multi-vehicle and multi-drone problem is decomposed into multiple single-vehicle and multi-drone sub-problems,and the solving process is divided into the task allocation stage and the sub-problems arc routing planning stage.In the task allocation stage,a route distance grouping task allocation method is adopted,and the distance between each route is defined,which can identify a potential better allocation scheme.In the arc route planning stage of single-vehicle and multi-drone,a feasible initial solution is generated by a heuristic algorithm,and an improved adaptive large neighborhood search algorithm is proposed to achieve arc routing optimization.The experimental results verify the feasibility and superiority of the divide-and-conquer strategy and the improved adaptive large neighborhood search algorithm in solving the large-scale multivehicle and multi-drone arc routing problem.In summary,based on the background of urban traffic patrolling and considering patrol tasks of different scales,this thesis establishes mathematical models for different problems and designs efficient and feasible algorithms to solve them,which provides references for the research and application of cooperative arc routing problems of vehicles and drones.There are 52 figures,18 tables and 102 references.