# Ant-Balanced Multiple Traveling Salesmen: ACO-BmTSP
## 2 Methodology
### Basics of the Multiple Travel Salesman Problem
A heuristic's main purpose is to find a good solution simply and quickly. On the other hand, metaheuristics are models that serve as a guide for building heuristics. Many of those models are based on natural phenomena. The TSP has many different real-world applications, such as school bus routing, management of pickup and delivery, and others [35], making it a prevalent problem to solve. However, some problems require additional salesmen. Thus, the multiple TSP (mTSP) is defined to generalize the usual TSP. This generalization uses more than one salesman to find a solution. It can be defined as a set of \(n\) nodes and \(m\) salesmen initially located at a single depot node. All salesmen start and return to the depot, and all remaining cities are visited only once by a unique salesman [36]. To model the single-depot mTSP precisely, assuming that the problem is symmetrical, that is, \(c_{ij}=c_{ji}\), the equations are:  
\[\min\sum_{j=1}^{n}\sum_{i=1}^{n}c_{ij}x_{ij} \tag{1}\]  
\[\sum_{j=1}^{n}x_{1j}=\sum_{j=1}^{n}x_{j1}=m \tag{2}\]  
\[\sum_{j=2}^{n}x_{ij}=1,\quad i=1,2,...,n \tag{3}\]  
\[\sum_{i=2}^{n}x_{ij}=1,\quad j=1,2,...,n \tag{4}\]  
\[u_{i}-u_{j}+nx_{ij}\leq n-1,\quad 2\leq i\
eq j\leq n \tag{5}\]  
\[x_{ij}\in\{0,1\},\quad i,j=1,2,...,n \tag{6}\]  
The objective function is described by (1), with the goal of minimizing the total associated cost, which is subjected to several constraints. Constraint (2) ensures that exactly \(m\) traveling salesmen start and return to the initial depot (vertex 1). Restrictions (3) and (4) ensure that exactly one edge enters and exits each graph city. The sub-tour elimination constraint (5) defines an integer variable \(u_{i}\) for the position of node \(i\) in a tour, and \(n\) represents the maximum number of nodes visited by any salesman. Finally, (6) defines the variable \(x_{ij}\) as binary. The mTSP is more appropriate than the TSP for many practical applications, and it can be used to simulate many real-life applications [37], e.g., disaster management, cooperative missions, monitoring and surveillance, transportation and delivery, multi  
Figure 1: Example of a graph. robot task allocation and scheduling, WSN data collection network connectivity, search and rescue, and precision agriculture, among others [37]. Many variants of the mTSP have been reported in the related literature. The most important for this study is the understanding of the variant classification according to the objective function; two main formulations of the mTSP exist [37]:  
1. MiniMax mTSP: In this mTSP variant, the objective function consists of minimizing the most extended tour cost among the tours of all salesmen. 2. MiniSum mTSP: In this mTSP variant, the objective function consists of minimizing the sum of the tour costs of all salesmen. Although a majority of reported works about the mTSP sought to minimize the total distance traveled by all the salesmen (minisum), minimizing the maximum distance traveled by any salesman (minimax) is of more practical significance, since it is related to balancing the workload among salesmen [38].