A Coordinated Vehicle–Drone Arc Routing Approach Based on Improved Adaptive Large Neighborhood Search

Sensors

卷:22

Manhao Ma¹  Guohua Wu²  Kexin Zhao²  Jiaqi Cheng² 

[1] College of Systems Engineering, National University of Defense Technology, Changsha 410073, China;

[2] School of Traffic & Transportation Engineering, Central South University, Changsha 410075, China;

关键词: vehicle–drone;    arc routing problem;    traffic patrol;    routing optimization;    adaptive large neighborhood search;   

DOI  :  10.3390/s22103702

来源: DOAJ

【 摘 要 】

Through urban traffic patrols, problems such as traffic congestion and accidents can be found and dealt with in time to maintain the stability of the urban traffic system. The most common way to patrol is using ground vehicles, which may be inflexible and inefficient. The vehicle–drone coordination maximizes utilizing the flexibility of drones and addresses their limited battery capacity issue. This paper studied a vehicle–drone arc routing problem (VD-ARP), consisting of one vehicle and multiple drones. Considering the coordination mode and constraints of the vehicle–drone system, a mathematical model of VD-ARP that minimized the total patrol time was constructed. To solve this problem, an improved, adaptive, large neighborhood search algorithm (IALNS) was proposed. First, the initial route planning scheme was generated by the heuristic rule of “Drone-First, Vehicle-Then”. Then, several problem-based neighborhood search strategies were embedded into the improved, adaptive, large neighborhood search framework to improve the quality of the solution. The superiority of IALNS is verified by numerical experiments on instances with different scales. Several critical factors were tested to determine the effects of coordinated traffic patrol; an example based on a real road network verifies the feasibility and applicability of the algorithm.

【 授权许可】

Unknown