## 4 Proposed Methods
### Ant Colony Optimization  
Ant Colony Optimization (ACO) was first introduced in Reference [28]. This algorithm is powerful for routing problems such as traveling salesman problem (TSP), vehicle routing problem (VRP), and their variants [17; 27]. The algorithm mimics the behavior of a colony of ants in foraging activities. Suppose that, at the beginning, the colony has no information about the location of the food source. An ant system (AS) consists of a set of artificial ants which perform foraging activities, from their nest to a food source. Some ants begin to move randomly to any direction and deposit a chemical called \"pheromone\", whose trails will be traced by other ants. This process is iterated such that the optimal route is that with the maximum number of pheromone trails. In this study, we used an ACO algorithm for finding trajectories for a multiple-vehicle system. The algorithm is different from the typical ones. It involves more than one species of ants whose pheromone the others cannot detect trails of. In the cases of CFMTSP, a species represents a vehicle. We develop an algorithm such that each species performs a collision-free trajectory, i.e., all species can prevent collision with each other. In this study, we assume that any two species are not colliding with each other if the difference of their arrival times exceeds a minimum allowable value. Suppose that there exist \(N_{\text{u}}\) ant species. Each species consists of \(N_{\text{m}}\) ants. The \(r\)-th ant of the \(k\)-th species, denoted by \(\partial^{k,r}\), \(k\in\{1,2,\ldots,N_{\text{u}}\}\), \(r\in\{1,2,\ldots,N_{\text{m}}\}\), represents the \(k\)-th vehicle. Each ant is assumed to be able to recognize only the trails produced by ants of the same species. Therefore, if there exists a large concentration of pheromone in a sub-route, if it comes from different species, then it is less possible for the ant to choose that sub-route as a choice. As the typical ACO algorithms, as one ant passes a sub-route, it leaves pheromone trails along the sub-routes. From now on, the others will smell the trails, and based on the largest amount of pheromones, it will choose the sub-route. Even though there are pheromones produced by other different ant species, the ant cannot recognize them. This behavior is similar to the behavior of some colonies of ants in the real world, that is, they cannot recognize the trail of other different ant species, as reported in Reference [40]. Researchers in that study have discovered that a species of ants, i.e., _Lasius nigers_ (_La. nigers_), is unable to recognize the pheromone trails produced by _Novomessor cockerelli_ (_N. cockerelli_) and _Linepithema humilis_ (_Li. humilis_). The reason is that their pheromone trails are constructed by different chemicals. In this model, we applied the amount of pheromone applied to the proposed augmented graph \(G^{\text{a}}\) to augmented edges \({}^{h}\xi\). Define \(n\), \({}^{h}\tau^{k}\), and \(\Delta^{h}\tau^{k,r}\) as the iteration, the total amount of pheromoneleft by the \(k\)-th ant species on augmented edges \({}^{h}\xi\), and the increase of pheromone amount left by each \(r\)-th ant of the \(k\)-th ant species, respectively. We formulate \({}^{h}\tau^{k}\) as follows. \[{}^{h}\tau^{k}(n)={}^{h}\tau^{k}(n-1)+\sum_{r=1}^{N_{\text{m}}}\Delta^{h}\tau^{ k,r}(n), \tag{8}\]  
if a solution is found and the \(i\)-th and \(j\)-th nodes are the part of the augmented edge passed through by the \(k\)-th ant species, and  
\[{}^{h}\tau^{k}(n)=\rho^{h}\tau^{k}(n-1), \tag{9}\]  
where \(\rho\epsilon\ (0,1]\) is defined as evaporation rate, if the search fails to find a solution. Furthermore, \(\Delta^{h}\tau^{k,r}\) is formulated as follows:  
\[\Delta^{h}\tau^{k,r}=\frac{Q}{d^{k,r}}, \tag{10}\]  
where \(d^{k,r}\) is the total distance traveled by the \(r\)-th ant from the \(k\)-th species, and \(Q\) is a positive constant.