Path Planning And Scheduling Of Truck Multi-Drone Cooperative Inspection

In recent years,low-cost rotorcraft UAV has entered the civilian market due to its high mobility and extendibility.However,the limited battery capacity and communication range strictly restrict the range of service offered by UAV.Therefore,in real applications,an UAV is often paired with a traditional delivery truck,which launches the UAV to execute mission nearby the target region.Such paradigm can significantly improve efficiency as well as save cost,and hence it has attracted much attention in academia.Nevertheless,existing literature,which mainly focus on the logistics operations,suffer from lack of attention on truckassisted drone surveillance scenario.In addition,few existing studies considers the collaboration between a delivery truck and multiple drones,whereas multiple drones working simultaneously can greatly improve efficiency.In view of the shortcomings of existing studies,the problem of path planning and scheduling of truck-assisted multi-drone surveillance is investigated in this paper.However,several challenges need to be addressed for solving the problem.First,the path of each drone as well as the truck needs to be optimized,such that the waste of each route is minimized under the premise of valid communication distance between the truck and each drone while drones are executing missions.Second,the tasks need to be assigned evenly to the drones,such that the waiting time of each drone and the truck is minimized.Third,in order to optimize the finish time of the whole task,the routing and scheduling of truck-assisted multi-drone need to be jointly designed,both spatially and temporally.To address the problem,two innovative and efficient heuristics are proposed in this paper:The first algorithm is Adaptive Memory based Tabu Search Algorithm(AMTSA).First,AMTSA optimizes the path planning of drones via quantifying the quality of each drone route.Second,AMTSA reasonably designs the truck route by defining the coverage ratio of drone routes on each parking point of the truck.Third,AMTSA achieves load balancing by adopting a simple yet effective algorithm to reasonably schedule the drones.Finally,AMTSA utilizes nested Tabu Search Algorithm to jointly optimize the routing of the truck and drones as well as the scheduling scheme,which ensures a much shorter finish time of the whole task.The experimental results show that the task finish time of the solution generated by AMTSA is nearly 100% shorter than other comparison algorithms,and its performance is not sensitive to the hovering time of each drone.The second algorithm is Hybrid Genetic Algorithm(HGA).Based on the framework of Genetic Algorithm,HGA innovatively proposes a procedure called Minimum Visiting Cost Crossover(MVCC)to construct a child solution from two parent solutions.MVCC ensures the finish time of the child solution is shorter than both of the parent solutions.In addition,HGA adopts chained Tabu Search Algorithm to optimize the path planning of the truck and the drones respectively,which offers satisfying performance with much shorter elapsed time as compared to AMTSA.Experiments show that the performance of HGA can achieve 80% of AMTSA,whereas the execution efficiency of HGA is 70% higher than AMTSA.