# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
In this algorithm, we construct new tours by inserting new targets at positions that lead to the smallest increase in tour lengths. ```
Initialization: Start with \(m\) initial Dubins tours \(\tau_{v},\forall v\in[1,m]\) starting and ending at the depot \((T_{0},\theta_{0})\). Repeat: While the set of unvisited targets \(N_{u}\) is non-empty
```
1. Identify the tour with the shortest Dubins tour length \(\tau_{v_{min}}\leftarrow\min(D_{v}),\forall v\in[1,m]\)
2. Choose a target \(T_{j}\) from the list of unvisited targets \(N_{u}\) according to one of the following greedy strategy. 1. Random: Choose a random target \(T_{j}\in N_{u}\) 2. Nearest: Find a target \(T_{j}\in N_{u}\) such that the Dubins distance \(d(T_{j},T_{j^{\prime}})\) is minimum \(\forall T_{j^{\prime}}\in\tau_{v_{min}}\) 3. Farthest: Find a target \(T_{j}\in N_{u}\) such that the Dubins distance \(d(T_{j},T_{j^{\prime}})\) is maximum \(\forall T_{j^{\prime}}\in\tau_{v_{min}}\) ```
3. Determine a position \(i\) in the tour \(\tau_{v_{min}}\) such that the increase in tour length \(\Delta D_{v_{\min}}(T_{j})=D(T_{i-k},T_{j})+D(T_{j},T_{(i+1,k})-D(T_{i-k},T_{( i+1)+k})\) is minimum; insert \(T_{j}\) in \(\tau_{v_{min}}\). 4. Remove \(T_{j}\) from the set of unvisited targets \(N_{u}\)
```

**Algorithm 1** Greedy k-insertion for MD-GmTSP. ### Neighborhood Search: Improvement Phase

In the improvement phase, we use VNS-based local search heuristics to enhance the incumbent solution from the construction phase. These heuristics modify the current solution by performing a sequence of operations to produce a new feasible solution that improves the objective function. The algorithm evaluates the effect of modifying the current solution systematically and replaces it with a new solution if it is better. The algorithm may also be allowed to make changes that lead to poorer solutions with the hope of finding a better solution later. Let \(I\) denote a problem instance of the MD-GmTSP. Let \(X\) represent the set of feasible solutions for this instance. For any \(x\in X\), let \(f(x)\) denote a function that calculates the objective cost, which, in the case of the MD-GmTSP, corresponds to the Dubins tour length of the largest tour within \(x\). It is important to note that the solution set \(X\) is finite but the size of the set can exponentially increase with the size (number of targets) of an instance of MD-GmTSP. Our goal is to find a solution \(x^{\prime}\) such that \(f(x^{\prime})\leq f(x),\forall x\in X\). To facilitate this search, we define a neighborhood \(N(x)\subset X\) for each solution \(x\in X\), where \(N\) is a function that maps from a solution \(x\) to a set of solutions in its neighborhood. A solution \(x*\) is defined to be locally optimal or is said to be a local optimum with respect to a neighborhood \(N\) if \(f(x*)\leq f(x^{\prime}),\forall x^{\prime}\in N(x*)\). Improvement heuristics aim to find a locally optimal solution before the termination condition is met. In this paper, we investigate three improvement heuristics based on VNS for solving the MD-GmTSP, namely (1) basic variable neighborhood search (BVNS), (2) variable neighborhood descent (VND), and (3) general variable neighborhood search (GVNS). #### 5.2.1 Basic Variable Neighborhood Search (BVNS)

BVNS [39] uses a stochastic approach to reach the global minimum. In this approach, the neighborhood search is continued in a random direction, away from the initial solution. The steps of BVNS are explained in Algorithm 3. Initialization: Choose a set of neighborhood structures denoted by \(N_{k}(\kappa=1,\ldots,\kappa_{max})\) for the search process; find an initial solution \(x\); select a termination/stopping condition and 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_{k}(x))\); 2.