# Enhanced Path Planning by Repositioning the Starting Point +
## 2 Background and Related Work  
To address the multi-drone path optimization challenges outlined in the previous section, our research builds upon the multiple Traveling Salesman Problem (mTSP) framework. The mTSP extends the classical Traveling Salesman Problem (TSP) [35] by incorporating \(m\) concurrent salesmen. While the standard TSP requires a single salesman to visit every city in a territory exactly once before returning home via the shortest possible route, the mTSP involves multiple salesmen working collaboratively to minimize their combined travel distance. Each salesman visits a subset of cities exactly once, with all salesmen departing from and returning to a common location known as the Depot [33]. The computational complexity of the mTSP exceeds that of the already challenging TSP, establishing it as an NP-hard optimization problem [36]. The scholarly landscape surrounding mTSP solutions has been systematically analyzed by several researchers. [PERSON] et al. [37] provide a comprehensive taxonomic overview of solution methodologies, organizing approaches into three primary categories based on their computational strategy. Their classification encompasses six exact solution methods, ten heuristic approaches, and three transformation-based techniques, offering researchers a structured framework for understanding the diverse solution landscape. Building upon this foundation, [PERSON] and [PERSON] [34] present an even more detailed categorization of mTSP variants, organizing them into five comprehensive groups based on fundamental problem characteristics. Their first category examines salesman properties, including type, quantity, and cooperative behavior patterns. The second classification focuses on depot characteristics, encompassing variations such as single versus multiple depots, fixed versus mobile configurations, open versus closed path requirements, and refueling considerations. The third group addresses city distribution patterns, distinguishing between the standard mTSP where all salesmen share the same city set and the colored mTSP where cities are partitioned between salesman groups. Their fourth category differentiates problems based on objective function complexity, separating single-objective from multi-objective formulations. Finally, the fifth group categorizes constraint types, examining energy limitations, capacity restrictions, and time window requirements. This comprehensive framework illuminates the rich diversity within the mTSP family. For our experimental investigation, we employ a specific mTSP variant with carefully defined characteristics. All drones operate from a single mobile depot, departing together and returning to the same location upon mission completion, creating closed-path trajectories. The optimization objective focuses exclusively on minimizing total distance traveled, which under simplified operational assumptions (where energy consumption occurs only during flight) directly corresponds to energy minimization. Following the formulation presented in [34], we can express this mathematically using Equations (1) and (2). For a drone \(U_{i}\) beginning its mission at starting point \(H\), visiting an assigned sequence of ground stations \(S_{i_{1}},\ldots,S_{i_{n}}\) and returning to \(H\), the mission cost \(C\) is calculated as follows:\[C(Mission_{U_{i}})=C(H,S_{i_{1}})+\sum_{k=1}^{n-1}C(S_{i_{k}},S_{i_{k+1}}) \tag{1}\] \[+C(S_{i_{k}},H)\]  
The total operational cost for \(d\) drones is then defined as follows:  
\[Total\ Cost=\sum_{i=1}^{d}C(Mission_{U_{i}}) \tag{2}\]  
Our proposed methodology employs the local search [38] variant of mTSP optimization. Local search techniques have demonstrated significant effectiveness in addressing mTSP challenges [37; 39; 40], establishing their importance within AI-driven optimization frameworks [41]. The local search methodology applies to optimization problems requiring the identification of superior solutions among multiple candidates.