# Drone Arc Routing Problems and Metaheuristic Solution Approach
## 4 Proposed Solution Approach
### Neighbor Search Operators  
In the development of the neighbor search operators, we took advantage of the merge and split operator, which is one of the local search operators suggested by [PERSON] et al. [30] for the CARP, and the shorten procedure, which is one of the post-optimization procedures for the rural postman problem suggested by [PERSON] et al. [31]. They proposed the shorten  
Figure 4: Sample drone routes. procedure to improve the obtained routes for the RPP. A shorten procedure consists of the reverse and postpone mechanisms. Eight different neighbor search operators are described to apply in the structure of the algorithm. In each iteration of the algorithm, one of these operators will be selected randomly. Each operator has an equal chance of selection. _K-Reverse Operator:_ A randomly selected \(k\) number of drone routes are merged. The value of \(k\) is 2 or 3. The merging process is performed according to the ascending route index and the routes are merged to obtain a single route. Two position values are randomly generated and the set of edges between these two positions is reversed in the single route. The obtained route is divided into \(k\) routes based on the drone capacities. _N-Reverse Operator:_ All drone routes are merged based on the ascending route index to obtain a giant route. Two position values are randomly generated and the set of edges between these two positions is reversed in the giant route. The obtained route is divided into \(n\) routes based on the drone capacities. _Intra-Route Reverse Operator:_ A route is randomly selected to change the order and direction of the edges on the route. Two position values are generated and the set of edges between these two positions is reversed to generate the neighbor solution. _Smart Reverse Operator:_ Two randomly selected routes are merged based on their index values in ascending order to obtain a single route. One of the repeating nodes in the merged route is randomly selected. The edges between the selected repeating nodes are reversed according to the defined priority rules. Four priority rules have been described. Whichever rule the repeating node first complies with, the related reverse process is performed in accordance with the rule. Assume that the repeating node is node \(i\). * Rule 1: If the route includes \((i-j)...(k-i)\), reverse it to \((i-k)...(j-i)\). * Rule 2: If there are \((i-j)...(i-k)\) on the route, first change the direction of the edge \((i-k)\) to \((k-i)\). Then reverse it to \((i-k)...(j-i)\). * Rule 3: If there are \((j-i)...(k-i)\) on the route, first change the direction of the edge \((j-i)\) to \((i-j)\). Then reverse it to \((i-k)...(j-i)\). * Rule 4: If there is \((j-i)...(i-k)\) on the route, change the direction of both edges. Then reverse it to \((i-k)...(j-i)\). The obtained route after the reverse process with one of the presented rules is divided into two based on the drone capacities and thus the neighbor solution is generated. _K-Route Shorten Operator:_ A randomly selected \(k\) number of drone routes are merged. The value of k is determined randomly between 2 and 5. In addition, \(k\) cannot have a value greater than the number of drones. The edges in the \(k\) number of selected routes are added to an edge pool and the nearest neighbor algorithm is used to generate a tour from the edges. The obtained tour is divided based on drone capacities to obtain \(k\) number of drone routes. The steps of the \(k\)-route shorten algorithm are presented below. * Step 1: Add all the edges in the selected routes to an edge pool and create an empty route. * Step 2: Obtain a route using the nearest neighbor algorithm with the edges in the edge pool. * Randomly select one of the edges nearest to the depot node from the edge pool, remove it from the edge pool, and add it to the route as the first edge to be visited in the route. * Randomly select one of the edges nearest to the last edge in the route from the edge pool and add it to the route by removing it from the edge pool.