Research On Two-Echelon Ground Vehicle And Its Mounted Unmanned Aerial Vehicle Cooperated Routing Problem

Completing the missions of target reconnaissance and information acquisition with a ground vehicle and its mounted UAV(unmanned aerial vehicle)is a typical application of Manned Vehicle-UAV Mission System,also is a kind of new cooperated model in military and civilian areas.When UAV collaborates with the ground vehicle,the ground vehicle is traveling on a road network near the reconnaissance area and keeping launching and recycling UAV,while UAV automatically flies to the target point to collect the target information and then returns to the vehicle before the battery runs out.As a ground mobile platform for small and medium-sized UAV,ground vehicles can carry UAV to patrol more extensive reconnaissance areas and make up the shortage of UAV's enduarence.Meanwhile,ground vehicles can only travel on the road network or flat hard ground while UAV is capable to rapid detect the ground vehicle unreachable areas and obtain more accurate target information.The emergence of this new cooperated mode inevitably requires the corresponding cooperated routing method to optimize both the ground vehicle and the UAV route.However,the current vehicle routing and UAV routing method have not considered the cooperated situation,which leads an inefficence support.In view of above,this paper focus on the Two-Echelon Ground Vehicle and Its Mounted UAV Cooperated Routing Problem(2E-GUCRP).The main work of this paper are as follows:Firstly,the characteristics of the cooperated work model and the challenges in the routing progress are analyzed.Vehicle-mounted UAV routing requires accurate synchronization: In the time dimension,the UAV is subject to the time limit of its endurance and needs to return to the ground vehicle to charge or change its battery in time.In the spatial dimension,the location of the next rendezvous node should not only be close to the area of undetected target,but also ensure that the UAV can arrive within the limits of endurance after the current reconnaissance mission.In view of the characteristics of this two-echolen cooperative routing problem,a mixed integer programming(MIP)model is established.Complex aspects such as different modalities of cooperation,synchronization and enduarence constraints are efficiently considered in the proposed MIP model.Secondly,the Split Algorithm,Route Assignment Algorithm,Clustered Assignment Algorithm,and Greedy Assignment Algorithm are proposed to construct feasible solutions of 2E-GUCRP in seconds.Through the experiment of random generated instances,we compare the efficiency of heuristic algorithms in different instance scales.In this paper,the quality of the heuristics is also verified by the algorithm of precise solution in some small-scale instances.Thirdly,an Adaptive Large Neighborhood Search(ALNS)algorithm is proposed to improve the quality of the heuristics,when the solution time is not constrained.Based on the charastices of this problem,we develop an improved ALNS algorithm by introducing new ground vehicle route removal operators,UAV route removal operators,insertion operators,and adaptive adjustment mechanisms.It runs in successive segments which change the number of calls of operators and compute their own statistics to adapt selection probabilities of operators.Results of extensive computational experiments show that the ALNS is highly effective in finding good-quality solutions on the randomly generated 2EGUCRP instances.Fourthly,through the analysis of the neighborhood search process,we provide insights into the fesiable solutions of the 2E-GUCRP and put forword a Cluster Embedded Search Progress(CESP)by analyzing the generalized distance between any two fesiable solutions and their clustering tendency.In particular,we propose a Cluster Embedded Multi-Start Neighborhood Search(CEMSNS)algorithm and a Cluster Embedded Large Neighborhood Search(CELNS)algorithm in combination with existing algorithms.The computational results on a large set of instances show that the CEMSNS and CELNS outperform existing heuristics in efficiency.Furthermore,based on the map of Changsha city,we construct a practical instance of the 4G signal collection of important landmarks.The practical instance indicates that the algorithms we proposed are able to solve medium-size instances to an accredited feasible solution within reasonable computing times.