## 2 Background Knowledge  
### Routing Generation Methods and Ant Colony Optimization  
The purpose of routing generation is to search for the more effective paths among numerous alternative paths. A number of metaheuristic algorithms have been applied to find more efficient routes. Table 1 summarizes several existing meta-heuristics and the relevant applications to generate more efficient routs in complex networks. Among a number of meta-heuristic algorithms, swarm-based optimization methods [10; 12; 14] have been widely used for more efficient route generations. One of the representative swarm-based optimization is ACO. ACO is an algorithm derived by [PERSON] [15; 16], based on the cooperative behavior \begin{table}
\begin{tabular}{c c} \hline \hline
**Route Generation Based Research Studies** & **Applications and Characteristics** \\ \hline [PERSON], [PERSON] and [PERSON] [10] & Particle Swarm Optimization-based Energy efficient route generation to maximize vehicle mileage \\ \hline [PERSON], [PERSON], [PERSON] and [PERSON] [11] & Route generation of large-scale networks using genetic algorithm \\ \hline [PERSON], Liu, [PERSON], Hu, Zhang and Xiao [12] & Clustering routing algorithm based on glowworm swarm optimization \\ \hline [PERSON], [PERSON] and [PERSON] [13] & Generation of efficient distributed model to reduce communication load using intelligent routing algorithm \\ \hline [PERSON], [PERSON], [PERSON], [PERSON], [PERSON] and [PERSON] [14] & Power distribution network routing generation using ACO \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Existing research studies for route generation. of ants in finding the shortest route from their colony to the food location. Table 2 shows that the algorithm has been utilized as one of the meta-heuristics in solving the route problem in complex and difficult networks. In a general ACO algorithm, each ant acts as an artificial agent that moves to the target probabilistically. At each step, the agent moves based on the graph topology of the problem, deposits the pheromone, and updates the pheromone amount, using iterations to increase the probability of the optimal route production. Figure 1a depicts how agents move to produce an efficient route using ACO in a multilayered graph. All agents start at the same position (e.g., the Ant Colony) at the beginning of each iteration. However, agents in Figure 1b are initially located at random places, and search for the shortest path more efficiently. Section 3 provides the detailed process and method. The agents (the number of agents = AN) move from the first layer, the ant colony, up to the last layer, the food location. In each destination point, an agent can select one of the directly connected neighbor nodes, and diffuses its pheromone. The route is stronger as the concentration of pheromone is stronger. \[\mathrm{P}^{(k)}_{ij}\ =\ \frac{\tau_{ij}}{\sum_{j\in N^{(k)}_{ij}}\tau_{ij}}, \ \ \ \ \ \ if\ j\in N^{(k)}_{i} \tag{1}\] \begin{table}
\begin{tabular}{l l} \hline \hline \multicolumn{1}{c}{**Research Studies Using ACO**} & \multicolumn{1}{c}{**Application Fields**} \\ \hline [PERSON], [PERSON], [PERSON] and [PERSON] [17]; [PERSON], & \\ [PERSON] and [PERSON] [18]; [PERSON], [PERSON], [PERSON] and [PERSON] [19] & Transportation and scheduling issues \\ \hline [PERSON] and [PERSON] [20]; [PERSON] and [PERSON] [21] & Efficient route production \\ \hline [PERSON], [PERSON] and [PERSON] [22] & Permutation flow shop scheduling problem \\ \hline [PERSON], [PERSON] and [PERSON] [1] & Traveling salesman problem \\ \hline [PERSON], [PERSON], [PERSON], [PERSON] and [PERSON] [23] & Wireless sensor network design \\ \hline [PERSON] and [PERSON] [24] & The quadratic assignment problem \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Several applications using Ant Colony Optimization. Figure 1: Conceptual comparisons between ACO algorithm and MPACO algorithm: (**a**) Optimal route search in ACO algorithm; (**b**) Optimal route search in MPACO algorithm.