# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
###### Abstract  
This paper addresses a MinMax variant of the Dubins multiple traveling salesman problem (mTSP). This routing problem arises naturally in mission planning applications involving fixed-wing unmanned vehicles and ground robots. We first formulate the routing problem, referred to as the one-in-a-set Dubins mTSP problem (MD-GmTSP), as a mixed-integer linear program (MILP). We then develop heuristic-based search methods for the MD-GmTSP using tour construction algorithms to generate initial feasible solutions relatively fast and then improve on these solutions using variants of the variable neighborhood search (VNS) metaheuristic. Finally, we also explore a graph neural network to implicitly learn policies for the MD-GmTSP using a learning-based approach; specifically, we employ an S-sample batch reinforcement learning method on a shared graph neural network architecture and distributed policy networks to solve the MD-GMTSP. All the proposed algorithms are implemented on modified TSPLIB instances, and the performance of all the proposed algorithms is corroborated. The results show that learning based approaches work well for smaller sized instances, while the VNS based heuristics find the best solutions for larger instances. m 202330 May 20233  
heading angle. The motion of a Dubins vehicle can be fully defined using the following set of equations:  
\[\dot{x}=v_{0}\cos\theta,\;\dot{y}=v_{0}\sin\theta,\;\dot{\theta}=\frac{v_{0}}{ \rho}u,\;-1\leq u\leq 1 \tag{1}\]  
where \(u\) is the input to the vehicle and \(\rho\) is the minimum turning radius of the vehicle. [PERSON] proposed that in an obstacle-free environment, the shortest path between any two configurations on a 2D plane for a Dubins vehicle must be either the \(CCC\) type or the \(CSC\) type or a combination of sub-paths of these two types; here, \(C\) represents an arc of a circle with a radius of \(\rho\), and \(S\) represents a straight line segment. These paths can be expressed as \(LSL\), \(RSR\), \(RSL\), \(LSR\), \(RLR\), or \(LRL\), where \(L\) and \(R\) indicate clockwise and counterclockwise turns of a \(C\) segment, respectively, as illustrated in Figure 1. When the vehicle is also capable of reversing, the shortest path problem was solved by [PERSON] and [PERSON] in [19]. Optimal solutions to these problems were also derived by [PERSON] and [PERSON] (1991) [20] as well as [PERSON] et al. (1994) [21], utilizing the Pontryagin maximum principle [22]. [PERSON] and [PERSON] (2005) [23] and [PERSON] et al. (2007) [24] have further expanded upon [PERSON] research by applying it to routing problems involving car-like mobile robots or fixed-wing aerial vehicles that maintain a constant forward speed and adhere to curvature constraints while making turns. The vehicle routing problem for a [PERSON] vehicle is called the Dubins traveling salesman problem (DTSP) [25]. In the DTSP, the challenge is not only to find the optimal order of the targets to visit but also to determine suitable heading angles for the vehicle when visiting the targets. A feasible solution to the DTSP involves a curved path where the radius of curvature at any point along the path is at least equal to the turning radius \(\rho\geq 0\), and each target is visited at least once. Since the problem involves both discrete and continuous decision variables, with the target order being discrete and the heading angles being continuous, finding an optimal solution to the DTSP is an NP-hard problem, as shown by [PERSON] et al. [26]. Currently, no exact algorithm exists in the literature that can find an optimal solution to the DTSP. However, over the last two decades, several heuristics and approximation algorithms have been developed to find feasible solutions for the DTSP [23; 24; 27; 28; 29; 30; 31; 32; 33; 34].