# Drone Arc Routing Problems and Metaheuristic Solution Approach
## 2 Related Work  
The DARP was first described by [PERSON] et al. [14] in the literature. But in fact, there are arc routing problems in the literature that are suitable for the characteristics of a DARP. Therefore, information about these problems is presented. [PERSON] and [PERSON] [25] defined the crossing postman problem (XPP) as a general form and application of the undirected rural postman problem (RPP). In the XPP, the postman is allowed to enter or exit from any point of an edge in the undirected and disconnected graph. As a potential application of the XPP, [PERSON] and [PERSON] [25] gave an example of obtaining the minimum distance tour for a machine that cuts polygonal shapes from a material such as fabric or metal. In the following years, cutting path problems (CPPs) were studied as an application of the XPP in the literature. [PERSON] et al. [26] conducted a literature review about cutting path problems and this problem was classified. The endpoint cutting problem (ECP), continuous cutting problem (CCP), and intermittent cutting problem (ICP) are among these problems, sharing common characteristics with the DARP. The ECP is the problem of cutting shapes from a material so as to minimize the total cost (distance) by using predetermined entry and exit points on the shapes. In the CCP, each shape must be cut at once without dividing it into edges. Additionally, it is not necessary to use the predetermined points on the shapes; cutting can be started from any point of the shape. In the ICP, shapes can be cut into pieces and there is no restriction on the entry or exit points to be used. [PERSON] et al. (2018) defined the DARP in 2018, but the energy capacities of drones are not taken into account in the study. Therefore, the demands of the required edges on the graph can be met by using a single drone. That is why the DARP addressed in the study is actually a special case of the rural postman problem (RPP). They proposed an algorithm to solve the DARP. The proposed algorithm iteratively solves RPP instances with an increasing number of segments. For the solution of the RPP in each step, the branch and cut algorithm proposed by [PERSON] et al. (2018) for the windy general routing problem was applied. [PERSON] et al. (2018) and [PERSON] et al. (2018) focused on a DARP with a length constraint for drones in 2021 and 2022. That is why this problem is called the length-constrained K-drones rural postman problem (LC K-DRPP). The LC K-DRPP is more challenging than the DARP since it is necessary to service the required edges with multiple drones. However, the energy capacity of drones was not taken into account in the study. [PERSON] et al. (2018) a proposed branch-and-cut algorithm for the length-constrained K-vehicles rural postman problem (LC K-RPP) and matheuristic algorithms to solve the LC K-DRPP. In 2022, [PERSON] et al. (2018) carried out a polyhedral study and presented a new sophisticated branch-and-cut algorithm for the LC K-RPP. They also developed a global algorithm for the LC K-DRPP that iteratively solves instances of the LC K-RPP using the proposed branch-and-cut algorithm. [PERSON] et al. (2017) addressed the drone rural postman problem, where there is a single drone without an energy capacity constraint. They proposed a two-stage heuristic algorithm to solve the problem. This algorithm firstly reduces the graph and then solves the RPP on the reduced graph. The proposed two-phase heuristic was compared with the solution approach suggested by [PERSON] et al. (2018), and it was shown that the two-phase heuristic performed better. Many researchers have highlighted the importance of drones' energy consumption features. [PERSON] et al. (2019) presented a detailed survey on energy optimization techniques in unmanned aerial vehicle (UAV)-based cellular networks.