# Drone Arc Routing Problems and Metaheuristic Solution Approach
## 2 Related Work
They discussed four different types of energy optimization in UAV-based cellular networks: optimization of the propulsion energy, optimization of the communication energy, joint optimization, and optimization of the energy consumption in UAV-assisted cellular networks. Then, they reviewed conventional (exact, heuristic, and metaheuristic methods) and machine learning algorithms to solve these energy optimization problems. [PERSON] et al. (2019) focused on the energy consumption patterns of small drones in their study. They conducted experimental study using a small drone to collect its energy consumption data. They developed four different models for predicting the drone's energy consumption patterns, which include a theoretical model, a simple linear regression model, a cubic polynomial regression model, and a machine learning-based model. It is noted that the drone could consume more energy due to its avionics, but this issue was not taken into account in the study. In addition, it was stated in the studies by [PERSON] and [PERSON] (2018) and [PERSON] et al. (2019) that drones consume more energy while servicing the edges. [PERSON] et al. (2018) stated that battery consumption may be proportional to the activities performed by the drone. Additionally, they reported that the drones' battery consumption can increase when servicing the edges. A structure similar to the issue of energy consumption encountered in surveillance drones was described in the literature. [PERSON] and [PERSON] (2016) introduced the capacitated arc routing problem with deadheading demand to the literature. In this study, they addressed the multi-robot coverage problem. The problem indicated that even if the robot passes through a path without performing a task (deadheading), it consumes its remaining energy and when it performs a task, it consumes more energy due to the activation of the cameras or sensors on it. They proposed a mathematical model as an exact solution method to solve the small-sized instances. Moreover, they developed a constructive heuristic method to solve the medium- and large-sized instances. Examining the studies in the literature reveals that the DARP is considered a special version of the RPP. However, the problems addressed in this study is a special case of the CARP. Thus, in this study, drone routes were obtained to perform edge monitoring and inspection tasks with drones while taking into account their energy capacity, which is highlighted in the literature as a significant issue. Therefore, it is clear that considering the energy capacities of the drones makes the problem more realistic and applicable to real-world scenarios. This study also discusses a novel case of the DARP-DD, where some critical areas or borders need to be monitored more than once with surveillance drones. This special case (MS-DARP-DD) is encountered in real-life applications, especially when strategic or critical areas need to be monitored repeatedly in order to ensure the security of these areas. This work also presents novel neighbor search operators, which have been demonstrated to be useful in ARPs and are easily applicable to the structure of metaheuristic algorithms.