# Hyper-Heuristic Based on ACO and Local Search for Dynamic Optimization Problems +
## 3 HULK: Hyper-Heuristic Based on ACO and Local Search Operators
### Choosing and Applying Local Search Operator
#### 3.2.2 Unstringing and Stringing Local Search Operator  
The US heuristic is the core part of the Generalized Insertion Procedure-Unstringing and Stringing (GENIUS) [32]. The US repeatedly removes (unstringing) and inserts (stringing) nodes searching for solution improvements. The main feature of the algorithm is that the stringing nodes can be made between non-adjacent nodes, resulting in a route where both nodes become adjacent to the node being inserted. All movements are based on local and global neighbourhoods. The asymmetric version of US was proposed and implemented in [43], considering the node \(V_{x}\) to be inserted between any two nodes \(V_{i}\) and \(V_{j}\). For a given orientation of a tour, consider \(V_{k}\) a node in the sub tour from \(V_{j}\) to \(V_{i}\)  
Figure 1: An example of 2–_opt_ move. Figure 2: A forbidden movement resulting in closed circuits (cycles). and \(V_{l}\) a node in the sub tour from \(V_{i}\) to \(V_{j}\). We also consider for any node \(V_{h}\) on the tour, \(V_{h+1}\) its successor and \(V_{h-1}\) its predecessor. The re-insertion of \(V_{x}\) between \(V_{i}\) and \(V_{j}\) can be done in several ways using different types of insertions and removals. Since the potential number of choices for \(V_{i}\), \(V_{j}\) and \(V_{x}\) could be large, we use a candidate set based on the closest neighbours. Once \(V_{x}\) is chosen, its neighbours will be the \(q\) nodes that have lower value arcs with \(V_{x}\). To choose the best place to insert a node in the tour, we look only for the neighbourhood of each node involved with stringing or unstringing movements. In [9; 32], only symmetric problem instances were considered and tackled with Type I and Type II removals (Figure 3a,b) and Type I and Type II insertions (Figure 4a,b). In [8; 10; 43], other two types of removals and other two types of insertions were considered in order to tackle asymmetric problem instances: Type III and Type IV removals (Figure 3c,d), and Type III and Type IV insertions (Figure 4c,d). The unstringing procedure removes a node from the tour and reconnects the tour with the remaining nodes trying to obtain an improved closed tour. The procedure consists of four types of removals defined as follows:  
* Unstringing Type I: consider \(V_{j}\) belonging to the neighbourhood of \(V_{i+1}\) and \(V_{k}\) belonging to the neighbourhood of \(V_{i-1}\), with \(V_{k}\) being part of the sub tour \((V_{i+1},\ldots,V_{j-1})\). The removal of node \(V_{i}\) results in the deletion of arcs \((V_{i-1},V_{i})\), \((V_{i},V_{i+1})\), \((V_{k},V_{k+1})\) and \((V_{j},V_{j+1})\) and the insertion of arcs \((V_{i-1},V_{k})\), \((V_{i+1},V_{j})\) and \((V_{k+1},V_{j+1})\). Additionally, the sub tours \((V_{i+1},\ldots,V_{k})\) and \((V_{k+1},\ldots,V_{j})\) are reversed. * Unstringing Type II: consider \(V_{j}\) belonging to the neighbourhood of \(V_{i+1}\), \(V_{k}\) belonging to the neighbourhood of \(V_{i-1}\), with \(V_{k}\) being part of the sub tour \((V_{i+1},\ldots,V_{i-2})\), and \(V_{l}\) belonging to the neighbourhood of \(V_{k+1}\), with \(V_{l}\) being part of the sub tour \((V_{j},\ldots,V_{k-1})\). The removal of node \(V_{i}\) results in the deletion of arcs \((V_{i-1},V_{i})\), \((V_{i},V_{i+1})\), \((V_{j-1},V_{j})\), \((V_{k},V_{k+1})\) and \((V_{l},V_{l+1})\) and the insertion of arcs \((V_{i-1},V_{k})\), \((V_{l+1},V_{j-1})\), \((V_{i+1},V_{j})\) and \((V_{l},V_{k+1})\). As before, the sub tours \((V_{i+1},\ldots,V_{j-1})\) and \((V_{l+1},\ldots,V_{k})\) are reversed. * Unstringing Type III: consider \(V_{j}\) belonging to the neighborhood of \(V_{i+1}\) and \(V_{k}\) belonging to the neighborhood of \(V_{i-1}\) with \(V_{k}\) being part of the sub tour \((V_{i+1},\ldots,V_{j-1})\). The removal of node \(V_{i}\) results in the deletion of arcs \((V_{i-1},V_{i})\), \((V_{i},V_{i+1})\), \((V_{j-1},V_{j})\), and \((V_{i+1},V_{j})\). Figure 4: (**a**) Stringing Type I, (**b**) stringing Type II, (**c**) stringing Type III, and (**d**) stringing Type IV.