# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
The _SoftMax_ function is used for creating a probabilistic policy that can be optimized using gradient-based techniques. In the context of a policy network, the parameters of the _SoftMax_ function are typically learned from data that reflects the characteristics of the agents being modeled. As such, the policy network may need to be retrained when those characteristics change, such as when different turning radius constraints or a different number of agents are introduced. S-Samples Batch Reinforcement Learning

The parameter \(\theta\) for our model is estimated by maximizing the expected reward of the policy, i.e.,

Figure 4:9

Figure 5:0 Figure 5:1

where \(D\) is the training set, \(\lambda\) is an assignment of cities representing which agent visits it, \(R(\lambda)\) is the reward of the assignment, and \(\lambda\), \(\pi_{\theta}\) is the distribution of the assignments over \(\theta\), i.e., \(\pi_{\theta}(\lambda)=\prod_{i\in\{1,\ldots,n\}}p_{ai}\). However, the inner sum over all assignments in Equation (20) is intractable to compute. REINFORCE [91] is used as the estimator for the gradient of the expected reward. An S-sample batch approximation decreases variances in the gradient estimate and speeds up convergence. Figure 5:2

The variance during training is decreased by introducing an advantage function \(A(\lambda_{s})\):

Figure 5:3

This results in a new optimization function:

Figure 5:4

Figure 5:5

The pyDubins [92] code computes the rewards for every assignment, which calculates the DTSP tour lengths and returns the negative of the maximum tour length over all agents as the reward for the assignment. ## 7 Computational Results

Algorithms were implemented using an Intel NUC Kit (NUC8i7 HVK) equipped with an Intel Core i7 processor and 32 GB of RAM. The effectiveness of the proposed methods was evaluated by solving instances from the TSPLIB library [40], which contains sample instances for the TSP and related problems with varying sizes ranging from 16 to 176 cities. To adapt the TSPLIB instances for the MD-GmTSP, each city was associated with a set of \(h=8\) candidate heading angles. The minimum turning radius (\(\rho\)) was calculated for each instance based on the layout of the cities. Specifically, \(\rho\) was computed as follows:

Figure 5:6where \((x_{i},y_{i})\) and \((x_{j},y_{j})\) are the 2D coordinates of city \(i\) and city \(j\), respectively, for all \(i,j\in I\). ### MILP Results

Each instance was solved using the MILP formulation for MD-GmTSP described in Section 3. The CPLEX 12.10 [87] solver was used with a computational time limit of 10,800 s (3 h) to generate optimal results. Table 1 presents the results of the MD-GmTSP for \(m=3\) homogeneous vehicles and \(h=8\) heading angle discretizations. CPLEX was able to generate feasible solutions within the time limit only for instances with fewer than 52 cities and did not find optimal solutions for any of the instances. The optimality gap for the best result, obtained on the Ulysses-22 instance with 22 cities, was 14.09%. ### VNS-Based Heuristics Results

The algorithms discussed in Section 5, including the construction heuristics and the variable neighborhood search (VNS)-based improvement heuristics, were implemented in Python3 and tested on the same set of TSPLIB instances for \(m=3\) vehicles and \(h=8\) (discrete heading angles). #### 7.2.1 Quality of Initial Feasible Solutions

Table 2 presents a comparison of the performance of different construction heuristics (\(k=0\) relaxation) on the MD-GmTSP. The construction phase allowed angle optimization only for new unvisited targets to be inserted into tours while keeping the rest of the tour unchanged (\(k=0\)). The initial feasible solutions were generated without imposing any time limit. The results demonstrate that the cheapest construction method produced min-max tours with an average cost that was 11.81% higher than the nearest construction method. However, the nearest and farthest construction methods produced tours with identical min-max costs.