Two-Echelon Arc Routing Problem With Drones in Traffic Patrol

Traditional patrolling methods relying on ground vehicles or fixed cameras are insufficient in adapting to dynamic changes in traffic flow due to their limited mobility and fixed positions, especially during emergencies like traffic accidents occur. In this paper, we investigate a new Truck-Drone collaborative Traffic Patrolling (TDTP) mode, where multiple trucks and drones work in a collaborative manner to enhance the efficiency of performing traffic patrolling tasks. The drone can be launched and recovered by trucks at certain points along the truck route, making it possible for both trucks and drones to perform patrol tasks simultaneously. A crucial aspect of TDTP is the coordinated arc routing scheduling of multiple trucks and drones, which is referred to as the Truck-Drone Arc Routing Problem (TD-ARP). We formulate the TD-ARP as a mixed-integer linear programming model with the objective of minimizing the total patrol time of all trucks and drones. Due to the difficulty of solving large instances of TD-ARP to optimality, we construct a divide and conquer based framework TA-TDAR (Task Allocation phase and Truck Drone fleet Arc Routing phase) for TD-ARP. TA involves the assignment of tasks to different truck-drone fleets, each comprising a truck and multiple drones, while TDAR focuses on path planning for the truck-drone fleets. Two phases are iteratively performed until the stopping criteria are met. In TA phase, a Task Allocation Heuristic method (TAH) is designed. Based on the task allocation results, an Adaptive Large Neighborhood Search algorithm with Local Search (ALNSLS) is embedded into TDAR phase to achieve a satisfactory scheduling scheme of each truck-drone fleet. Extensive experiments are conducted to validate the superiority of the proposed TAH-ALNSLS. The results show that our method has a potential improvement of up to 40% compared to the comparison methods, which stems from the divide and conquer framework and problem specific operators. Furthermore, several management implications are provided to assist practitioners in making efficient decisions.