## 1 Introduction
This problem was coined in the work of [PERSON] and [PERSON] [30] by introducing an \"inevitable collision states\", i.e., a set of configurations (position and direction) of a vehicle that makes the vehicle fail to avoid collision with any object. A successful development of the framework of predicting the collision was introduced in Reference [31], and is called the \"reciprocal velocity obstacle\". This work defines \"obstacle\" in a more precise manner, by considering not only the position of the obstacle but also the velocity of the vehicle and the obstacle. Therefore, the collision time can be predicted [32; 33; 34; 35; 36]. The typical MTSP is mostly solved by utilizing a conventional graph model consisting of a set of nodes and a set of edges. However, such a graph model cannot be used to handle the issue of the collision, since the model only describes the information of position. In our work, we propose a novel graph model that contains information on position and speed options. Speed, together with node-to-node distance, is useful to determine the minimum arrival time difference between any two vehicles on a node, which in turn, can be used as a collision indicator. We assume that the safety area on each node corresponds to its minimum allowable arrival time difference. In order to find the optimal solution, we utilize an Ant Colony Optimization (ACO) algorithm on the proposed graph model, such that the solution is not only a sequence of visited nodes but also the speed that is applied for the node-to-node trip. The typical algorithm uses a single species of ant to find the optimal single vehicle's route search. However, it is inadequate to use that single species to solve CFMMSP. Therefore, we propose multiple species of ants, as each ant represents a specific vehicle. The main feature of such an ACO algorithm is in the assumption that each ant only recognizes pheromone trails from other ants in the same species. Based on the previous study, the problem that is similar to the CFMMSP has never been explored yet. The closest research was reported in References [13; 37; 38]. The research in Reference [13] focused on finding the route and speed for the Vehicle Routing Problem (VRP). However, this method uses an assumption of independent speed choice between any two edges, which is mechanically unrealistic because of the existence of acceleration constraints (see [36]). The issue of collision in MTSP appeared in References [37; 38; 39]. In Reference [37], a fleet of vehicles serves all nodes in an overlapped time-based batch. Accordingly, this problem may contain the possibility of collision, as well, since any two vehiclescan visit the same node in an overlapped time. In Reference [38], a variant of TSP, namely Close Enough Traveling Salesmen Problem (CETSP), is presented. This work considers the node more as an area with a predetermined radius rather than the nodes as points. Moreover, the area is allowed to be occupied by only one vehicle at any time. However, similar to Reference [13], the node-to-node travel time in both articles is assumed to be predetermined. This assumption is practically not realistic, because a single (autonomous) vehicle is controlled automatically by a computer-based control system [39]. The control system has to send some speed instructions to the AGV while traveling some paths [35]. Several published algorithms did not consider speed selection, because they was assumed that some constant speeds are applied to the paths [25; 26; 27]. The organization of this paper is described as follows. Section 2 introduces several terminologies needed to support the analysis and discussions. Section 3 describes the problem statement. Section 4 explains the proposed methods, including the proposed augmented graph and the application of ACO on the graph. Section 5 reveals the simulation results and discussions. Finally, Section 6 concludes the overall work and describes future works.