# Drone Arc Routing Problems and Metaheuristic Solution Approach
###### Abstract
In this study, surveillance drones used in search and rescue operations, control of regional borders, inspection of infrastructure, wind turbines, etc., are discussed. Surveillance drones travel from the depot (central point) to the areas that need to be serviced and the borders in the relevant areas are monitored or inspected [19]. Drones use sensors and cameras to perform monitoring and inspection tasks. With their limited energy capacity, the drones should go to the areas that need to be served, perform monitoring tasks in those regions, and then return to the depot. That is to say, drones must perform their tasks and complete their routes without exceeding their energy capacity [4]. There is an important issue to be emphasized about the energy consumption of drones. While surveillance drones do not serve the edges, they only consume as much energy as the traveled distance; when serving the edges, they consume as much energy as demanded by both the traveled distance and the sensors, imaging, and communication devices (avionics) activated during surveillance [20; 21; 22]. Namely, drone capacities are used both when serving the edges and deadheading the edges. The related problem is called the drone arc routing problem with deadheading demand (DARP-DD). With this study, a DARP-DD considering the energy capacity of drones is addressed, and all required edges are served by drones only once in DARP-DD. Moreover, a special case may be encountered in the DARP-DD investigated. In some special cases, it may be necessary to provide multiple services to some required edges. This need can arise due to several reasons, such as ensuring more precise imaging of the relevant edge due to its importance, maintaining security for strategic or critical areas, improving data accuracy and reliability by collecting data from the same area multiple times, and taking preventive measures by frequently monitoring certain areas. The prob lem encountered in this case is called the multiple service drone arc routing problem with deadheading demand (MS-DARP-DD). The DARP-DD and MS-DARP-DD have real-life applications. For example, the parts that need to be monitored in forest areas can be represented by edges. In this case, the monitoring operations of the edges described in the forest area by energy-capacitated surveillance drones are an application area of the DARP-DD. On the other hand, in cases where some strategic and critical edges need to be monitored more than once to ensure the security of the forest area, drones are expected to respond to this demand. In this case, the application area of the MS-DARP-DD is encountered. The MS-DARP-DD enhances security measures in strategic areas and facilitates proactive monitoring of sensitive locations. The mentioned application area can be expanded as traffic monitoring by representing traffic roads in a city with edges, inspection of railway lines by representing rails with edges, and surveillance of regional borders by representing country borders with edges. The simulated annealing algorithm [23; 24] is proposed to solve these two novel problems in this study. This algorithm has many components, which include solution representation, neighbor search operators, constraint handling strategy, and parameter values such as initial temperature value, final temperature value, cooling rate, and the number of iterations. So, the components of the algorithm are designed in accordance with these problems. The proposed algorithm is initially applied to solve the capacitated arc routing problem (CARP), which is known as one of the most challenging ARPs belonging to the NP-hard class. Thus, the success of the proposed algorithm in solving ARPs has been proven by using the most challenging problems in the literature. In the continuation of this study, the proposed algorithm is then utilized to solve the test problems generated for the DARP-DD and MS-DARP-DD. The performance of the algorithm is analyzed in detail.