# Ant-Balanced Multiple Traveling Salesmen: ACO-BmTSP
## 2 Methodology
### Basics of the Multiple Travel Salesman Problem  
One of the best-known classic combinatorial problems is the traveling salesman problem, or the TSP for short [30]. According to [31], the TSP was studied in the eighteenth century by two mathematicians, [PERSON] and [PERSON]. The TSP has the objective of minimizing a value--usually the distance--while defining a sequence of locations, where each is visited exactly once by a salesman, who then returns to the starting city. The travel can be described as a graph \(G=(V,E)\) with a set of \(n\) vertices \(V\) connected by \(m\) edges \(E\), where \(V=\{v_{1},v_{2},...,v_{n}\}\) and \(E=\{e_{1},e_{2},...,e_{m}\}\). In this graph, the vertices represent the cities and the edges represent the roads or possible paths to go from one city to another, with an associated cost value. To be able to take a trip that passes through all of the graph vertices of the graph only once constitutes, in graph theory, the so-called Hamiltonian circuit. Considering the vertex \(v_{1}\) as the depot, in Figure 1, the Hamiltonian circuit has an associated cost of 21. This cost can have a different meaning depending on the problem and can be evaluated with an objective function. The graph in Figure 1 shows five vertices \(V=\{v_{1},v_{2},v_{3},v_{4},v_{5}\}\), each one representing a city, interconnected by edges. The paths taken from one vertex to another have an associated cost represented by the number near the line. The simplest way to solve the TSP is to try all possibilities by using exhaustive methods, but when the number of edges grows, those methods are too time-consuming and computationally expensive. On the other hand, exact methods are useful when they solve problems within a reasonable time, e.g., in the production-inventory-routing problem [32], in discrete truss topology design [33], and in wind farm layout problems [34]. Due to the TSP's time complexity, when the number of cities becomes high, heuristic and metaheuristic methods are used to solve the \begin{table}
\begin{tabular}{p{113.8 pt} p{113.8 pt} p{113.8 pt}} \hline \hline
**Approach** & **Advantages** & **Drawbacks** \\ \hline ACO & – Rapid discovery of good solutions [1] & – Premature convergence \\  & – Efficient in solving the TSP & – Falls easily into the trap of local optima \\  & & – Does not guarantee the optimal solution \\ \hline AC2 OptGA & – Efficient with medium- and large-sized instances & – Does not guarantee the optimal solution \\  & – Probability of a fall into local minima minimized & – Highly time-consuming \\ \hline GA to m-TSP [20] & – Reduction of 618 km per week & – Does not guarantee the optimal solution \\  & – Huge impact in several forms & – Highly time-consuming \\  & – Contributions to fostering smart cities & – Generally impossible to draw a fitness landscape with a huge search space \\ \hline FLA for mTSP [22] & – Efficient exploration of the solutions of features of spaces & – Generally impossible to draw a fitness landscape with a huge search space \\  & – Provides relevant information about optimization method improvement & – Generally impossible to draw a fitness landscape with a huge search neighborhoods \\  & – Gets relationships between the FL structure and the algorithmic performance & – Solution is not immediately provided \\ \hline BD-mTSP [23] & – Predicts travel distance based on dynamic parameters & – Leads to slightly better solutions \\ \hline GACO2 & – Efficient in solving small-sized mTSP instances & – Does not provide balanced tours \\  & – Allows the release of traveling salesmen & – Not tested on large-sized instances \\ \hline GABC-LS & – Efficient in solving small-sized mTSP instances & – Does not provide balanced tours \\  & – Uses only one method & – Highly time-consuming \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Advantages and drawbacks of the reviewed approaches. problem. Heuristics do not guarantee that the optimal solution to the problem is found, but they can return a quality solution in an adequate amount of time for several application needs.