# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase  
Construction heuristics are commonly used to address vehicle routing problems, and they can be broadly categorized into three classes: insertion heuristics, savings heuristics, or clustering heuristics. In this work, we focus on insertion-based heuristics for the MD-GmTSP, where the algorithm starts with a closed sub-tour comprising a few targets and progressively inserts new targets into the tour until all the targets are visited. Specifically, we explore two types of insertion heuristics for the MD-GmTSP: (1) greedy k-insertion for MD-GmTSP and (2) cheapest k-insertion for MD-GmTSP. The key differentiator between these algorithms is the order of target selection and the position at which each target is inserted. The heuristics begin with a tour starting at a depot (initial location). A new target is inserted into the tour such that the increase in tour length is minimized. Greedy insertion algorithms, namely Nearest Insertion and Farthest Insertion, select an unvisited target whose distance from any target in the current tour is minimum and maximum, respectively, for insertion. In contrast, the cheapest-insertion algorithm selects an unvisited target whose insertion causes the lowest increase in tour length. The main steps involved in these construction heuristics for the MD-GmTSP are discussed below. Consider a set of \(t\) targets and their associated heading angles, \(V=\{(T_{1},\theta_{1}),\ldots,(T_{i},\theta_{i}),\ldots,(T_{t},\theta_{t})\}\) to be visited by a \(m\) Dubins vehicles, and let \((T_{0},\theta_{0})\) correspond to the depot target. To simplify the presentation, we also refer to any target configuration \((T_{i},\theta_{i})\) as a target. Let \(\tau_{v}=\{(T_{0},\theta_{0}),\ldots,(T_{i},\theta_{i}),\ldots,(T_{0},\theta_ {0})\}\), \(i\in[1,p]\) denote a Dubins tour for vehicle \(v\in v\), through \(p(\leq t)\) cities, starting and ending at the depot. Let \(d_{v}(T_{i},T_{i+1})\) denote the length of the shortest Dubins path from \((T_{i},\theta_{i})\) to \((T_{i+1},\theta_{i+1})\). Consider a target \((T_{j},\theta_{j})\) from the set of unvisited targets. The increase in tour length by inserting the \(T_{j}\) between targets \(T_{i}\) and \(T_{i+1}\) in tour \(\tau_{v}\), without changing the associated heading angles, would be \(\Delta D_{v}(T_{j})=d_{v}(T_{i},T_{j})+d_{v}(T_{j},T_{i+1})-d_{v}(T_{i},T_{i+1})\). We wish to insert the new unvisited target \(T_{j}\) in a tour \(\tau_{v}\) at a position such that the increase in length of tour \(v\) (\(\Delta D_{v}(T_{j})\)) results in a minimum increase in length of the largest of the \(m\) torus. One way of achieving this is by greedily inserting the new target \(T_{j}\) in the smallest of the \(m\) torus without affecting the rest of the tour(s). A relaxed version of the above approach is to allow modifications to the heading angles of \(k\) (\(\geq 0\)) targets adjacent to the newly inserted target such that the increase in tour length is minimum. Given a Dubins tour \(\tau_{v}=\{(T_{0},\theta_{0}),\ldots,(T_{p},\theta_{p}),\ldots,(T_{0},\theta_ {0})\}\), let \(D_{v}(T_{i-k},T_{(i+1)+k})\) be the length of the shortest possible Dubins sub-tour through targets \(T_{i-k},\ldots,T_{i},T_{i+1},\ldots,T_{(i+1)+k}\) with predefined headings \(\theta_{i-k},\ldots,\theta_{(i+1)+k}\). Then, \(\Delta D_{v}(T_{j})=D(T_{i-k},T_{j})+D(T_{j},T_{(i+1,k})-D(T_{i-k},T_{(i+1)+k})\) describes the increase in the tour length of vehicle \(v\) by inserting target \(T_{j}\). This version allows for the heading angles of \(2k\) targets between \(T_{i-k}\) and \(T_{(i+1)+k}\) to be optimized when the target \(T_{j}\) in inserted into the tour. Algorithm 1 presents a formal description of the \(k-\)greedy MD-GmTSP tour construction heuristic. In the cheapest k-insertion method (Algorithm 2), during each iteration, the algorithm finds the most promising target (from the set of unvisited targets) and the position for insertion in the current tour simultaneously.