# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
_Local search_: Apply a local search method with \(x^{\prime}\) as an initial solution; denote the obtained local optimum as \(x^{\prime\prime}\); 3. _Move or not_: If \(x^{\prime\prime}\) is better than the incumbent \(x\), set \(x\gets x^{\prime\prime}\) and continue the search process with \(N_{1}(\kappa\gets 1)\); otherwise, set \(\kappa\leftarrow\kappa+1\);

Neighborhood Structures

In this work, we use \(k-\)exchange operators to explore neighborhoods of MD-GmTSP using BVNS. A solution \(\chi^{\prime}\) is considered to be in the \(k-\)exchange neighborhood of solution \(\chi\) if there is exactly one vehicle \(V_{i}\) such that:

1. \(\chi^{\prime}\) and \(\chi\) differ only in the order of target visits in the tour of vehicle \(V_{i}\). 2. The tour for vehicle \(V_{i}\) in \(\chi^{\prime}\) differs from the tour of vehicle \(V_{i}\) in \(\chi\) by at most \(k\) edges. Shake

Local Search

After obtaining the solution \(x^{\prime}\) from the Shake procedure, we proceed to enhance it through local search. During this step, all feasible neighbors of \(x^{\prime}\) within the current neigh

Figure 3: Different Shake neighborhoods. The black and the red paths indicate the tours of the vehicles involved in the shake process. borhood are explored to identify a potential solution \(x^{\prime\prime}\) that has a lower cost. It is worth noting that there is a possibility for the current neighborhood of \(x^{\prime}\) to be empty. In that case, we set \(x^{\prime\prime}\) to be the same as \(x^{\prime}\), and the search continues in the next neighborhood. Exploration of neighborhoods can be of two types: (a) steepest descent and (b) first descent. The steepest descent and first descent heuristics are detailed in Algorithms 4 and 5, respectively. For a strong NP-hard problem like the MD-GmTSP, the steepest descent heuristic is a highly time-consuming process. In this work, a first improvement version of the 2-opt and 3-opt algorithms explores the different neighborhood structures of the MD-GmTSP. ```
Initialization: Find an initial solution \(x\); Choose the neighborhood structures \(N(x)\), and the objective function \(f(x)\) that calculates the length of the longest tour in \(x\), Repeat:  Find \(x^{\prime}=\operatorname*{\textit{argmin}}_{x\in N(x)}f(x)\)  If \(f(x^{\prime})<f(x)\) set \(x^{\prime}\gets x^{\prime\prime}\) and iterate; otherwise, stop
```

**Algorithm 4**SteepestDescent Heuristic by [PERSON] and [PERSON] [73]

```
Initialization: Find an initial solution \(x\); Choose the neighborhood structures \(N(x)\), and the objective function \(f(x)\) that calculates the length of the longest tour in \(x\), Repeat:  Find first solution \(x^{\prime}\in N(x)\)  If \(f(x^{\prime})>f(x)\) find next solution \(x^{\prime\prime}\in N(x)\); set \(x^{\prime}\gets x^{\prime\prime}\) and iterate (2); otherwise  set \(x\gets x^{\prime}\) and iterate (1);  If all solutions of \(N(x)\) have been considered, stop. ```

**Algorithm 5**FirstImprovement heuristic by [PERSON] and [PERSON] [73]

### 2-opt

Given a solution, the 2-opt algorithm, introduced by [PERSON] in 1958 [74], is a local search heuristic that explores all possible 2-Exchange neighborhoods of the solution. Its objective is to gradually enhance a feasible tour by iteratively swapping two edges in the current tour with two new edges, aiming to reach a local optimum where no further improvements are possible. During each improving step, the 2-opt algorithm selects two distinct edges that connect \((i,i^{\prime})\) and \((j,j^{\prime})\) from the tour. It then replaces these edges with the edges connecting \((i,j)\) and \((i^{\prime},j^{\prime})\), provided that this change reduces the tour length. This process continues until a termination condition is encountered (See Figure 4



#### 5.2.2 Variable Neighborhood Descent (VND)

The main difference between the BVNS and the VND approach is that in the VND, the neighborhood changes are deterministic. Algorithm 7 explains the VND metaheuristic in detail.