# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
The performance of \(VND_{seq}\) is influenced by the choice of neighborhood structures and the order in which these neighborhoods are explored. A combination of \(x-\)point and \(k-\)edge move neighborhoods are used in this paper to solve the MD-GmTSP. The details of these neighborhoods are provided below and illustrated in Figure 6.

1. **One-point move**: In GVNS, we use the same One-point move operator as in BVNS. 2. **Two-point move**: In GVNS, we use the same Two-point move operator as in BVNS. 3. **Or-opt2 move**: An or-opt2 move selects a string of two adjacent nodes belonging to the tour having the maximum length and transfers it into a new tour. After performing the or-opt2 move for all strings of nodes \(x^{\prime}\), the best solution \(x^{\prime\prime}\) is returned by the operator depending on the search strategy employed. The _or-opt2_ operator generates \(x^{\prime\prime}\in N_{2}(x^{\prime})\) as compared to generic or-opt\(k\) move operator generates \(x^{\prime\prime}\in N_{k}(x^{\prime})\). For our use case, no improvement was observed for \(k>2\), which can be attributed to the complexity in the MD-GmTSP problem. 4. **Three-point move**: The three-point move operation involves selecting a pair of adjacent nodes from the tour with the maximum length and exchanging them with a node from another tour. By repeatedly applying three-point moves starting from the initial solution \(x^{\prime}\), the operator generates a new solution \(x^{\prime\prime}\). Depending on the chosen search strategy, the best solution \(x^{\prime\prime}\in N_{3}(x^{\prime})\) is returned by the operator. 5. **2-opt move**: We use a 2-opt move operator to improve the resulting tours \(x^{\prime\prime}\) obtained from the rest of the operators by performing intra-tour local optimization. Local Search by VND for MD-GmTSP

A nested local search strategy is employed to solve the MD-GmTSP using GVNS. The \(VND_{seq}\) as specified in Algorithm 9 explores the neighbors of a given solution according to a particular sequence. This sequence is determined based on the non-decreasing order of neighborhood size. Based on the local search in each neighborhood, if the obtained solution (\(x^{\prime\prime}\)) is better than the current best (\(x^{\prime}\)), the 2-opt search is carried out for possible intra-tour improvements. The resulting solution replaces the current best (\(x^{\prime}\gets x^{\prime\prime}\)), and

Figure 6: Local search operators. The black and the red paths denote the tours of the vehicles involved in each move. The blue arrow in the Or-opt2 move shows the string of two adjacent nodes that is transferred between tours. the search restarts at the first neighborhood. Otherwise, the search continues with a larger neighborhood search operator. ```
1:procedure\(VND_{seq}(x^{\prime},l_{max})\)
2:\(l\gets 1\)
3:while\(l<l_{max}\)do
4:if\(l=1\)then
5:\(x^{\prime\prime}\leftarrow\text{onepoint}(x^{\prime})\)
6:if\(l=2\)then
7:\(x^{\prime\prime}\leftarrow\text{twopoint}(x^{\prime})\)
8:if\(l=3\)then
9:\(x^{\prime\prime}\leftarrow\text{or\_opt2}(x^{\prime})\)
10:if\(l=4\)then
11:\(x^{\prime\prime}\leftarrow\text{tbreepoint}(x^{\prime})\)
12:if\(f(x^{\prime\prime})<f(x^{\prime})\)then
13:\(x^{\prime\prime}\gets 2\_opt(x^{\prime\prime})\)
14:\(x^{\prime}\gets x^{\prime\prime};l\gets 1\)
15:else
16:\(l\gets l+1\)
17:return\(x^{\prime}\)
```

**Algorithm 9**\(VND_{seq}\)

Using heuristics to solve NP-hard problems provides a distinct advantage over traditional solvers as it can produce feasible solutions quickly. The quality of the solution can be further improved by employing improvement heuristics, but this often comes at the cost of computational power and time. Heuristics are rule-based approaches that prioritize improving computational efficiency over finding the optimal solution. Recently, there has been significant interest in learning-based approaches from the combinatorial optimization research community. These approaches utilize models that can solve large problem instances in real-time.