# Drone Arc Routing Problems and Metaheuristic Solution Approach
## 4 Proposed Solution Approach
### Neighbor Search Operators
Repeat this step until there are no more edges in the edge pool. * Step 3: Divide the obtained route into k number of routes based on the drone capacities. _Edge Postpone Operator:_ A randomly selected \(k\) number of drone routes are merged based on their index values in ascending order to obtain a single route. The value of \(k\) is determined randomly between 2 and 5. In addition, \(k\) cannot have a value greater than the number of drones. Then, the deadheading edges are added to the merged route. Infact, the process of adding the deadheading edges to the route is to use the shortest path when traversing from one required edge to another. The shortest paths can be obtained with the Floyd-Warshall algorithm. Repeated edges are encountered with the addition of the deadheading edges to the route. In this case, if it is possible, the deadheading edges on the route are converted into the required edges. The process of converting the deadheading edges into required edges is performed using the postpone mechanism described by [PERSON] et al. [31]. Thus, if the same edge is encountered multiple times on the route, the edge is serviced when it is traversed for the last time by the drone. The neighbor solution is then obtained by dividing the obtained route into \(k\) routes based on the drone capacities. Please note that drones can traverse directly between any two nodes on the graph, and this is actually the shortest path between these two nodes. But, so as to apply edge postpone and route-repairing operators, it is assumed that the drones can only traverse between the nodes of the components that view each other in the mechanism of edge postpone and route-repairing operators. Thus, different shortest paths are obtained using the Floyd-Warshall algorithm. So, the probability of deadheading on the required edges increases, which enables the effective use of the edge postpone and route-repairing operators. Edge Direction and Smart Edge Direction Change OperatorThe direction of an edge on a randomly selected route is changed using the edge direction change operator. The smart edge direction change operator is employed separately for each drone route. If the consecutive edges in the route contain common nodes, the direction of the edges is changed so that the common nodes are next to each other. These two operators are used as a single operator when selecting the neighbor search operator in the structure of the algorithm. However, both operators are not applied to the current solution at the same time. Between two operators, one will be selected at random. Route-Repairing OperatorThe aim of this operator is to obtain a new route with a shorter distance than the current one by ignoring the edge demands and drone capacity on the route. Therefore, this problem is similar to the RPP. The shorten procedure suggested by [PERSON] et al. [31] is used for this reason. However, the shorten procedure will only be applied to a randomly chosen drone route and a randomly chosen initial point. The steps of the shorten procedure are listed below:  
* Step 1: Randomly select a drone route. * Step 2: Add the deadheading edges to the selected route. * Step 3: Randomly select a required edge on the route and make the selected required edge the starting point without altering the direction of the tour. * Step 4: Run the postpone mechanism. If the same edge is encountered multiple times on the route, the edge is serviced when it is traversed for the last time by drone. * Step 5: Run the reverse mechanism. In the reverse mechanism, if (\(i,j\)) is a required edge, it is checked whether there is a path (\(i\), \(j\),..., \(k\), \(i\)) in the tour that contains a non-required edge (\(k\), \(i\)). If there is a path with these features, the reversed version of this path (\(i\), \(k\),..., \(j\), \(i\)) should be used in the tour. * Step 6: Remove the deadheading edges on the relevant drone route.