Unmanned aerial vehicle service network design for urban monitoring

Abstract

This study examines the multi-depot location-routing problems of unmanned aerial vehicles (UAVs) for urban monitoring (MDLRP-UM). MDLRP-UM arises in various practical applications, including daily police patrols in urban residential areas, forest fire patrols, urban infrastructure status monitoring and data collection, traffic flow monitoring at important intersections, and monitoring of urban temperature and humidity, among others. These diverse applications can be modeled as a general mixed-integer quadratically constrained problem (MIQCP), where we jointly plan the service routes of the UAVs, the frequency on each route, and the location of the depots to minimize the total cost. To solve the proposed problem, we decompose it into a master problem and sub-problems. We then propose an iterative algorithm (termed as “Frequency-Time-Frequency Strategy”) to solve the sub-problems, which is to find the optimal frequency and corresponding single service time for a given single route. The “Frequency-Time-Frequency Strategy” is further nested within a tailored adaptive large neighborhood search (ALNS) based heuristic algorithm to solve the master problem. The efficiency and effectiveness of the proposed solution method are demonstrated by a series of numerical studies.