## 3 Multi-Directional and Parallel Ant Colony Optimization (MPACO)  
MPACO algorithm orients \"multiple directional searches\", in which each group of ants start at any point, as opposed to the ACO algorithm, where all agents start from the same start point (Ant Colony). Moreover, MPACO algorithm has the characteristic of \"parallelism\", in which each agent searches in multiple directions simultaneously. This section explains how MPACO works in a static network environment. Figure 3 illustrates the detailed procedures of the MPACO algorithm. Figure 3a depicts the initial situation of the MPACO algorithm. The agents of each group start at the start point and the terminal point as usual, not just the start point of the maze. If the number of groups (randomly selected starting points) is \(v\), each group is composed of \(AN/v\) agents, where \(AN\) is the number of overall agents. When the agents from different groups often occur together with each other in a node, this node is defined as a collision node (\(q\)). The existence of the collision node implies that the node may have a higher probability to be used as one of the paths. For this reason, when the collision node is detected, the pheromone is diffused and calculated. The pheromone value is estimated using a GPR-based updating method. As shown in Figure 3b, the collision node \(q\) is detected, and the amount of pheromone (Figure 3c) is adjusted using a GPR around the collision node. Equation (18) defines the GPR-type pheromone distribution \(\mathrm{D}\), where \(X\) denotes a node belonging to radius \(w\) in the detected collision node. \[\mathrm{D}(Y_{*})\sim\mathrm{N}\!\left(\mathrm{m}(X),\;\mathrm{k}(X,X_{*})\right) \tag{18}\]  
\[\mathrm{M}^{(int)}=\underset{\forall(i,j)\in A}{\arg}\cdot\mathrm{max}\tau_{ij} \tag{19}\]Figure 3: Conceptual framework of MPACO algorithm and procedures. **(a)** Initial search from two different nodes; **(b)** Discovery of the collision node q; **(c)** GPR based pheromone renewal in Node q; **(d)** Choice of the node with the highest pheromone at the iteration “int”; **(e)** Searches with multi directions at the nodes including M(int+1) at the following the iteration “int + 1”; **(f)** Discovery of the collision nodes q1 & q2 at the following iteration; **(g)** GPR based pheromone updating in Node q1 & q2; **(h)** Search and connection of the divided routes. Equation (18) is derived using the prediction procedure provided in Section 2.2. The pheromone value (\(Y_{\star}\)) of node \(X_{\star}\) is predicted based on the GPR, and used as the updated pheromone value. The parameter radius w depends on the characteristics of the problem. This research study uses 2 as the value for each experimental measurement. After updating the pheromone, a new node (Equation (19)) with the highest pheromone in the network is selected. The node selected is called an intermediate node (M\({}^{(int)}\)), as shown in Figure 3d. The reasoned M\({}^{(int)}\) node is added as a new starting node of the agents, as shown in Figure 3e, and additional collision nodes (Figure 3f) are detected in the following iteration. Then, the GPR-type pheromone is updated at the additional nodes, as shown in Figure 3g, using Equation (18). Finally, the strongest pheromone points are linked with each other, and determine a final effective route, as shown in Figure 3h. When an agent diffuses pheromones in the shortened route using the cost function, MPACO algorithm with collision nodes and intermediate nodes generates the route to the large network faster and more efficiently than ACO algorithm. When these collision and intermediate nodes are not found, the MPACO algorithm follows the route search procedure of the ACO algorithm. Figure 4 depicts a flowchart of MPACO algorithm that produces an optimal candidate route. As shown in Figure 4, two collision nodes are detected in the initial searches. Then, the intermediate node is reasoned using the GPR rule. The node is registered to starting node lists. Then, the final route is completed using the same iterations.