# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 2 Literature Review  
The traveling salesman problem (TSP) is one of the most well-known optimization problems in the literature [41]. Several methods, ranging from exact techniques (branch and bound/cut/price) [41] to fast heuristics and approximation algorithms [42; 43], have been developed to solve the TSP. Heuristics generally aim to trade off optimality for computational efficiency. The mTSP deals with a generalization of the TSP with multiple vehicles. mTSPs are much harder to solve to optimality compared to the single TSP because targets have to be allocated to vehicles in addition to finding a tour for each of the vehicles. Numerous variants and generalizations of the mTSP have been addressed in the literature. For example, mTSP with motion constraints are addressed in [24; 44]; fuel constraints are addressed in [45]; capacity and other resource constraints are addressed in [46; 47]. Many recent methods have focused on the application of metaheuristics like genetic algorithms  
Figure 2: Dubins path between targets with discretized heading angles.  
(GA) [48; 49], simulated annealing (SA) [50], memetic search [51], tabu search [52], swarm optimization [53], and other methods [54; 55] to solve the mTSP problem for the single-depot and multi-depot case.  
The mTSP problem can be classified into two main types based on its objectives: the MinSum TSP and the MinMax TSP. In MinSum mTSP, the goal is to minimize the sum of the path costs for visiting all targets by the \(m\) vehicles, while in the MinMax mTSP [56; 57; 58], the objective is to minimize the maximum among the \(m\) path costs. While there are several approximation algorithms for the MinSum mTSP [24], there are very few theoretical results for the MinMax mTSP [59; 60; 61]. Even further, the MinMax mTSP for vehicles with turning radius constraint (Dubins-type vehicle) has received limited or no attention in the literature primarily due to the computational complexity involved in solving the problem.  
For the case when all the vehicles are homogeneous without motion constraints, there are several heuristics [62; 63; 64; 65; 66] in the literature for solving MinMax mTSPs and related vehicle routing problems. In [62], the authors present four heuristics and found that a linear program (LP)-based heuristic in combination with load balancing and region partitioning ideas performed the best. In [63], the authors present an ant-colony-based metaheuristic to solve the min-max problem with limited computational experiments. A transformation-based method by decoupling the task partitioning problem amongst the vehicles and the routing problems is presented in [65]. In [66], a new heuristic denoted as MD is presented for a min-max vehicle routing problem. Through extensive computational results, the MD algorithm is shown to be the best amongst the considered min-max algorithms in [66].  
Recently, MinMax mTSPs with other constraints have also been considered in surveillance applications. In [67], a mixed-integer linear program (MILP) based approach is presented along with market based heuristics for a min-max problem with additional revisit constraints to the targets. In [68], a min-max routing problem is considered where the vehicles are functionally heterogeneous, i.e., there are vehicle-target assignment constraints that specify the sub-set of targets that each vehicle can visit. Both approximation algorithms and heuristics were presented in [68]. In [69], insertion based heuristics are presented for a team of underwater autonomous vehicles with functional heterogeneity. An energy-aware VNS is presented for a vehicle routing problem in [70] where there is a fuel or energy constraint for each of the vehicles. There is also recent work [71] on generalized min-max routing problems where the targets are partitioned into sets, and a vehicle is only required to visit exactly one target from each set.