# Drone Arc Routing Problems and Metaheuristic Solution Approach
###### Abstract  
The drone arc routing problem (DARP) is one of the arc routing problems (ARPs) that has been studied by researchers recently. Unlike traditional ARPs, drones can travel directly between any two points in the graph. Due to the flexibility of drones, it is possible to use edges not defined in the graphs when deadheading the edges. This advantage of drones makes this problem more challenging than any other ARP. With this study, the energy capacities of drones are considered in a DARP. Thus, a novel DARP called the drone arc routing problem with deadheading demand (DARP-DD) is addressed in this study. Drone capacities are used both when servicing the edges and when deadheading the edges in the DARP-DD. A special case of the DARP-DD, called the multiple service drone arc routing problem with deadheading demand (MS-DARP-DD), is also discussed, where some critical required edges may need to be served more than once. To solve these challenging problems, a simulated annealing algorithm is used, and the components of the algorithm are designed. Additionally, novel neighbor search operators are developed in this study. The computational results show that the proposed algorithm and its components are effective and useful in solving the DARP-DD and MS-DARP-DD. capacitated arc routing problem; drone arc routing problem; deadheading demand; multiple service; simulated annealing algorithm +
Footnote †: journal:  
c c  
pose a threat to the country's borders and to take the necessary precautions. In addition, reconnaissance can be made using drones to perform military intelligence operations [8]. Studies have been conducted to determine routes for drones in a significant and wide range of application areas. However, the drone routing problem is generally considered a node routing problem in the literature. For example, in a recent study conducted by [PERSON] et al. [9], optimizing takeout delivery using drones and riders jointly was addressed. A two-stage heuristic algorithm was proposed to optimize order allocation and routing. [PERSON] et al. [10] and [PERSON] et al. [11] presented a literature review about drone routing studies and provided detailed information about them. In the node routing problem, the points (customers) that need to be serviced are located at the nodes [12]. On the other hand, in the arc routing problem, the points (customers) that need to be serviced are located on the arcs (edges) [13]. The tasks that drones are required to perform were defined on the edges by [PERSON] et al. [14], and the drone arc routing problem (DARP) was introduced to the literature [15; 1]. The main difference between the DARP and the known ARPs is the ability of the drones to travel directly between two points (nodes) without following the edges in the graph. Due to this ability of drones, the chance to traverse edges that are not defined in the graph occurs while deadheading the edges with drones. If a vehicle (drone) travels through an edge without performing a task, that edge is referred to as a deadheading edge [16]. Therefore, the distance between the deadheading edges is the Euclidean distance between the two points. Considering all of these, the DARP is described as obtaining the minimum cost tour to service all the required edges with a single drone. In other words, the stated DARP is the rural postman problem (RPP) with some assumptions [17]. [PERSON] et al. [18] focused on a DARP with a length constraint for drones, and the length-constrained K-drones rural postman problem (LC K-DRPP) was introduced to the literature. In this problem, the drone route is limited to a maximum length, necessitating the use of multiple drones to service the required edges. Similar to the DARP, after finishing the service of a required edge, the drone can travel directly to any vertex of another required edge without following the edges of the graph. Thus, this feature provides flexibility and efficiency in route planning. Moreover, the LC K-DRPP has the main features of the DARP suggested by [PERSON] et al. [14].