# Ant-Balanced Multiple Traveling Salesmen: ACO-BmTSP
## 2 Methodology
### The Proposed Approach: ACO-BmTSP Algorithm  
This work focuses on an implementation of ACO consisting of a substantial modification in its application. Instead of using an ant to create a tour, an ant picket is used in the proposed algorithm. This algorithm, ACO-BmTSP, replaces lines 4 and 5 of Algorithm 1. The first step of this technique is to initialize all of the ACO parameters (line 1:3 of Algorithm 2; the cost of each ant is zero at the beginning, \(c_{j}=0\); the ant picket begins at the deposit, \(u_{j}=\{Deposit\}\), and the set of unpicked nodes includes all except the deposit). As the single-depot variant of the mTSP was used, all the ants of the picket were positioned in this city (by analogy, the initial graph node; line 2). Instead of considering only one ant, as in the classical single TSP, in this algorithm (ACO-BmTSP), a group of ants \(m\) was considered to obtain a solution. Each ant \(j\) stores a tour, in the set \(u_{j}\), and all ants' tours forms a potential solution of the problem. Therefore, in Algorithm 2, for each instance (a solution of the problem), the tours were built in the \"while\" loop as follows: The ant of the picket whose cost is minimum (line 5) selects an unpicked city based on the pheromone path (line 6); it updates its set of visited cities (line 7), the cost traveled according to the distance \(d_{p_{j}p_{i}}\) between the last and current cities (line 8), and the global set of unpicked cities (line 9). The instance is finished when there is no city to pick, and the ants return to the deposit. The pheromone is spread as in the original ACO. Each solution created in an ant picket iteration is evaluated by using the objective function (10). This function minimizes the cost of the tours and promotes balanced tours. Since it is a continuous function, it suppresses the insensibility mentioned in the previous section, where each tour variation leads to a variation in the objective function. In this function, \(S_{j}\) is a set of \(|S_{j}|\) arcs traveled by the salesman \(k\). \[f=\sqrt{\sum_{k=1}^{m}\left(\sum_{j=1}^{|S_{j}|}c_{j}\right)^{2}},\qquad j\in S _{j} \tag{10}\]  
```
1:\(c_{j}=0\), \(\forall j\in\{1,2,\ldots,m\}\)
2:\(u_{j}=\{Deposit_{j}\}\), \(\forall j\in\{1,2,\ldots,m\}\)
3:\(P=\{1,2,\ldots,n\}\setminus\{Deposits\}\)
4:while\(P\
eq\emptyset\)do
5: Find the ant \(j\) with the lowest cost \(c_{j}\)
6: Select \(p_{i}\in P\) according to the transition rules
7:\(u_{j}=u_{j}\cup p_{i}\)
8:\(c_{j}=c_{j}+d_{p_{j}p_{i}}\)
9:\(P=P\backslash\{p_{i}\}\)
10:endwhile
11: Return the tour solution
```  
**Algorithm 2** Ant picket algorithm. Minimizing function (10) leads to a solution with the minimum cost and balanced tours. Although this perception is evident concerning the minimum cost, obtaining balanced tours may not be straightforward. This intention becomes apparent if the following optimization problem is considered: Suppose that two salesmen have a route of 100 units to travel, and they want to divide the route so that each one travels the same path distance. This problem can be formulated to determine the distance each one travels as follows:  
\[ \begin{array}{c}\text{Minimize}:\\ c_{1}^{2}+c_{2}^{2}\\ \text{s.t.}:\\ c_{1}+c_{2}=100.\end{array} \]  
The solution of this problem is \(c_{1}=c_{2}=50\). Thus, squaring the factors that each salesman travels leads to balanced tours. The same reasoning was successfully applied to minimize robotic manipulator trajectories and determine their \"balanced\" intermediate configurations [42; 43]. Using integer programming formulation and the same deposit, this problem can be represented by Equations (11)-(16), where \(x_{ij}^{k}\) is one if the arc \((ij)\) belongs to tour \(k\), and zero otherwise. The square root of the objective function (11) could be eliminated, since the optimization result would be the same. \(u_{i}^{k}\) is the position of node \(i\) in the tour \(k\). The other variables have the same meanings as those used when considering Equations (1)-(6).