# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
```
functionneighborhoodChange(\(x\), \(x^{\prime}\)\(k\)) if\(f(x^{\prime})<f(x)\)then \(x\gets x^{\prime}\); \(k\gets 1\)\(\triangleright\) Make a move else \(k\gets k+1\)\(\triangleright\) Next neighborhood
```
**Algorithm 6** Steps for neighborhood change by [PERSON] and [PERSON] [73]

Depending on the problem, multiple local search methods can be nested to optimize the VND search. The objective of the local search heuristics is to find the local minimum among all the \(l_{max}\) neighborhoods. As a result, the likelihood of reaching a global minimum is higher when using VND with a larger \(l_{max}\) than when using a single-neighborhood structure. Figure 4: A sample 2–opt move for a given tour. Figure 5: All possible combinations of 3-Opt moves for a given tour. Exploration of Neighborhoods for MD-GmTSP

We use a combination of four different neighborhood structures to explore the neighborhoods for MD-GmTSP. An \(x\)-point move is nested with a \(k\)-opt search (2-opt or 3-opt) to explore distant neighborhoods during local search coupled with greedy and random insertion techniques. The neighborhood structures are discussed in detail below. * One-point move: Given a solution \(x\), a one-point move transfers a target \(T_{j}\) from tour \(\tau_{v}\) to a new feasible position in another tour \(\tau_{v^{\prime}}\) (\(\
eq\)\(\tau_{v}\)). The target to be moved is chosen from the tour having the largest tour length and is relocated to a tour having the smallest tour length. The computational complexity of these local search operators is \(O(n^{2})\) for a given solution \(x^{\prime}\). * Two-point move: A two-point move swaps a pair of nodes rather than transferring a node between tours as in a one-point move. A target \(T_{j}\) belonging to the tour \(\tau_{v}\) having the largest tour length is swapped with a target \(T_{j^{\prime}}\) belonging to another tour \(\tau_{v^{\prime}}\) (\(\
eq\)\(\tau_{v}\)). After performing two-point moves from the solution \(x^{\prime}\), the best solution \(x^{\prime\prime}\) is returned depending on the search strategy employed (FirstImprovement or SteepestDescent). #### 5.2.3 General Variable Neighborhood Search (GVNS)

The general variable neighborhood search (GVNS) [73] merges the techniques used in both VND (deterministic descent to a local optimum) and BVNS (stochastic search) to reach increasingly distant neighborhoods in the search space. In GVNS, a sequential VND search (\(VND_{seq}\)) improves the initial solution as compared to a local search heuristic (as in the case of BVNS). Algorithm 8 details the steps of GVNS as proposed by [PERSON] and [PERSON]. _Initialization:_ Choose the set of neighborhood structures denoted by \(N_{\kappa}(\kappa=1,\ldots,\kappa_{max})\) that will be used in the shaking phase and the set of neighborhood structures \(N_{l}(l=1,\ldots,l_{max})\) that will be used in the local search process; find an initial solution \(x\); choose a termination/stopping condition. _Repeat_ the following steps until the termination condition is met:

1. Set \(\kappa\gets 1\). 2. _Repeat_ the following steps until \(\kappa=\kappa_{\max}\): 1. _Shaking_: Generate a feasible solution \(x^{\prime}\) at random from the \(\kappa\)th neighborhood of \(x(x^{\prime}\in N_{l}(x))\); 2. _Local search by VND_: * Set \(l\gets 1\) * _Repeat_ the following steps until \(l=l_{max}\) * _Exploration of neighborhood_. Find the best neighbor \(x^{\prime\prime}\) of \(x^{\prime}\) in \(N_{l}(x^{\prime})\) * _Move or not_. If \(f(x^{\prime\prime})<f(x^{\prime})\), set \(x^{\prime}\gets x^{\prime\prime}\) and \(l\gets 1\); otherwise set \(l\gets l+1\) 3. _Move or not_: If the local optimum \(x^{\prime\prime}\) is better than the incumbent, move there \((x\gets x^{\prime\prime})\) and continue the search with \(N_{1}(\kappa\gets 1)\); otherwise set \(\kappa\leftarrow\kappa+1\);Neighborhood Search Structures for MD-GmTSP

To ensure the effectiveness of GVNS, it is crucial to employ suitable local search strategies during the execution of Local Search by VND (\(VND_{seq}\)).