Charting New Routes: Comparing Swarm-Based Approaches to the Traveling Salesman Problem

Since the creation of mortal beings, they have constantly sought perfection in all aspects of life. One of the most important trials in the world is to find a stylish result. In reality, numerous complex problems, similar to transportation, warehousing, where to vend products, communication network design, scheduling, and planning, are frequently too large and complex to be optimally answered in a reasonable time. Nonetheless, chancing a result is still pivotal, so the volition is to originally accept a sour result with a respectable position of delicacy and optimization time [1].

Optimization problems have become so complicated that they are difficult for traditional programming approaches to decompose and optimize efficiently. A mass grounded metaheuristic optimization methods have been developed recently [2].

The machine learning models, especially ensemble learning approaches, to show great promise in solving complicated optimization issues by utilizing a variety of data-driven strategies to improve decision-making and prediction accuracy [3]. Used address challenging optimization issues is represented by swarm intelligence (SI) algorithms. Its goal is to model the collective behavior of basic agents as they attempt to accomplish goals like protecting against attacks and finding food. Even though each agent is one capable of basic tasks, when the work together and share knowledge, they can display extraordinary intelligence [4]. SI algorithms were first developed at the University of Michigan in the 1960s. John Holland and his associates wrote the first book on the GA in 1960, and it was later developed and published in 1970 and 1983 [5]. Have been extensively used by experimenters to optimize results and give sufficiently fit results for objective functions in optimization problems [2]. In similar problems, the ultimate thing is frequently to maximize or minimize an objective function, which is used to estimate the quality of the performing result. These algorithms aim to ameliorate or minimize the problem's objective function, and the Traveling Salesman Problem (TSP) is constantly used to test their effectiveness and estimate their performance. The TSP as it needs changing the shortest path to visit a set of big cities, the making it a perfect tool for assessing the effectiveness of different algorithms. A number of metaheuristic algorithms, including ACO, PSO, and EHO, are utilized to find a solution to the TSP, a classic problem in route optimization. Yet, a thorough comparison of the algorithms based on execution time, use of resources, and solution quality is still required. It is seen that (EHO) is quicker than the others, and hence all the more useful for big instances of (TSP) where repair has to be executed in a hurry. With emphasis laid on computational complexity and the quest for finding a balance between accuracy and efficiency, the present study attempts to evaluate the performance of these algorithms over various sets of datasets such that one can offer recommendations towards the optimal strategy to adopt for use in applications related to automated manufacturing, smart transportation, and logistics optimization.

In 1932, the mathematician Karl Menger first proposed the TSP. The problem formulation sounds surprisingly simple: consider a salesman who has to travel between several towns. He starts in his home town, visits each of the cities on some list exactly once, and then returns to the starting point. Reducing the overall distance traveled is the aim. Even while it seems straightforward, the more cities there are, the more challenging it becomes to solve this problem optimally. Mathematicians and scholars have been looking for effective answers for nearly a century. From its simple definition to the difficulty of illustrating its solutions is where TSP's beauty lies. The cities are very often real locations in practical applications, while travel routes are determined by distances. We will focus on the TSP instances that represent cities connected with road networks, where the distances represent the actual driven distance by automobiles. Maps will be used to display the results in order to improve comprehension and show how the solutions have practical applications. One could initially think that the issue can be resolved by just figuring out how long each potential tour is and choosing the shortest one. However, since the number of alternative tours grows factorially with the number of cities, this strategy is only practical for extremely small examples. For example, over 3 billion hours are feasible in only 14 cities. This "brute force" approach is computationally impractical for larger instances. Due to this, more complicated algorithms must be devised to successfully handle the problem, especially when large input datasets are involved [18], a classic graph-based optimization problem where a traveler must visit a given set of cities only once before returning to the starting point, while minimizing the total travel cost.

To date, no known polynomial time algorithm can solve every TSP instance. This means that it is NP-hard. Owing to this complexity, there have been numerous research regarding combinatorial optimization. TSP has proved itself as a benchmark to test any new optimization techniques as it has broad applications in different fields such as manufacturing, chip design, and logistics [19-21].

 Another perspective on the limitations of AI is the inability of the conventional AI techniques to scale up with developments in machine learning and optimization for information systems possessing big datasets, as well as the recent expansion in the industry, particularly energy and pharmaceuticals. Computational intelligence, a field dedicated to developing intelligent computational models that can interpret raw numerical data in real time and provide high reliability and minimal errors for engineering and commercial applications, has been made possible by this gap [22].

 Several heuristic and metaheuristic methods, for example, PSO, ACO, and EHO, have been developed for seeking an approximate solution for TSP. Each has its merits in a different way by trading off the accuracy of the solution against computing efficiency. For the best answers in smaller TSP scenarios, precise methods like branch-bound and Dynamic Programming have also been investigated. However, even though these exact methods ensure optimality, they are usually restricted to issues with fewer cities due to their large computational demands [12-14].

The length of the optimal tour of TSP problems can be found as shown below [14], can be calculated by Eq. (1).

$optimal\text{ }\!\!~\!\!\text{ }tour={{d}_{p\left( n \right)p\left( 1 \right)}}+\left( \underset{i=1}{\overset{n-1}{\mathop \sum }}\,{{d}_{p\left( i \right)p\left( i+1 \right)}} \right)$                             (1)

where, p is an ordered list of cities, and $\mathrm{p}(\mathrm{i})$ and $p(i+1)$ are successive locations in the tour, and $\mathrm{p}(\mathrm{i})$ and $p(i+1)$ are consecutive cities, The distance between city $p(i)$ $\mathrm{p}(\mathrm{i})$ and city $p (i+1)$ $\mathrm{p}(\mathrm{i}+1)$ is shown by the formula $d(p(i), p(i+1))$.

TSP Applications

• Logistics and supply chains: By minimizing delivery vehicle and truck routes, TSP reduces fuel usage and travel time [23].
• Manufacturing and production: It is used to schedule machine tasks and reduce travel time in electronics manufacturing, e.g., factories that manufacture printed circuit boards (PCBs) [24].
• Communications and networking: It is used to build wireless and wired networks and enhance data routing protocols to reduce delay [25].
• Health and medicine: It enables DNA sequencing to speed up diagnosis and planning of ambulance routes [26].
• Power and resource management: It conserves operating costs by allocating work crews and planning power plant maintenance [27].
• Traffic control and urban planning: It conserves operating costs and traffic jams by route planning for trash collection and regulating traffic lights [28].

This overall distance is to be minimized over all city orderings. Because of its practical relevance as well as its theoretical importance, TSP remains one of the most studied optimization problems. It has been applied in network architecture enhancement, reduction of production costs, and optimization of delivery routes. Further, the problem applicability has grown in a number of areas because of novel variants, which include the Vehicle Routing Problem and the multiple Traveling Salesman Problem.

The different optimization algorithms such as PSO, ACO and EHO This section describes the methods used to solve the TSP.

5.1 Ant Colony Optimization (ACO)

Is a metaheuristic search and optimization method inspired by the "intelligent" foraging behavior of natural ant colonies, and is widely used to solve (mostly combinatorial) optimization problems, The basic principle of ACO is that a colony of artificial ants work together to find the best path in a graph that represents a possible solution to the target problem, The way the artificial ants cooperate with each other is inspired by the way natural ants cooperate to find the shortest path between two points in a given terrain, such as their nest and a food source, When an ant constructs a possible solution, it deposits pheromones proportional to the quality of the solution in the region of the search space where the solution is located. Over time, the ants tend to converge on paths that represent close to optimal solutions in the search space [32].

ping_mu_jie_tu_2025-07-23_160015.png

Figure 1. Flowchart of the ACO algorithm

Steps of the ACO Algorithm for Solving the TSP as shown in the Figure 1:

1. Parameter Initialization: The number of ants, the number of cities, the initial pheromone level, and the algorithm parameters are defined as follows:

• $\alpha$: pheromone influence
• Distance influence $\beta$
• Pheromone evaporation rate $(\rho)$

2. Solution Construction: Each ant builds probabilistically a tour to choose the next city based on pheromone level. Distances will be calculated by using the formula expressed in Eq. (2).

${{P}_{ij}}=\frac{T_{ij}^{a}\text{*}\eta _{ij}^{\beta }}{\mathop{\sum }_{k\epsilon allowed}T_{ij}^{a}\text{*}\eta _{ij}^{\beta }}$                                        (2)

${{P}_{ij}}$ = probability of moving from city (i) to city (j), $T_{ij}^{a}$ = Pheromone amount on edge i, j,

$\eta _{ij}^{\beta }$ = $\frac{1}{{{d}_{ij}}}$ : attractiveness (inverse of distance ${{d}_{ij}}$).

3. Pheromone Update: After all ants complete their tours, update the pheromone levels on the paths used by Eq. (3).

${{T}_{ij}}=\left( 1-p \right)\text{*}{{T}_{ij}}+\mathop{\sum }_{k=1}^{m}\vartriangle T_{ij}^{k}$                                   (3)

p: Pheromone evaporation rate,

$\vartriangle T_{ij}^{k}=\frac{Q}{{{L}_{k}}}$: Pheromone deposited by ant k, $Q$: constant,

${{L}_{k}}$: length of the tour constructed by ant k.

4. Iteration: Repeat the above steps until a stopping criterion is met (e.g., a maximum number of iterations or minimal improvement in solution quality).

5. Final Solution: The best tour found over all iterations represents the optimal or near-optimal solution for the TSP.

ACO Pseudocode

5.2 Particle Swarm Optimization (PSO)

The PSO algorithm was derived from the collective behavior of birds and fish; in the PSO algorithm, the population consists of a large number of particles. Each particle representing a potential solution is a point in the search space, with a fitness value and velocity. PSO is conceptually very simple, requiring no derived information about the optimization function and using only elementary mathematical operators [33].

Steps of the PSO Algorithm for Solving the TSP as shown in the Figure 2:

1. Initialization of Particles:

•    Each particle represents a solution (order of visiting cities).

•    Each particle is assigned a random position and velocity.

2. Fitness Evaluation: Fitness = Length of the Tour (Calculate the total distance between cities in the tour. The goal is to minimize this length).

3. Velocity Update: The velocity of each particle is updated based on its personal best position (pBest) and the global best position of the swarm (gBest) can be calculated by Eq. (4):

${{V}_{i}}\text{ }\!\!~\!\!\text{ }=\omega \text{* }\!\!~\!\!\text{ }{{V}_{i}}+\text{ }\!\!~\!\!\text{ }{{c}_{1}}\text{*}{{r}_{1}}\text{*}\left( pBes{{t}_{i}}-{{X}_{i}} \right)+{{c}_{2}}\text{*}{{r}_{2}}\text{*}\left( gBest-{{X}_{i}} \right)$     (4)

$\omega $: Inertia weight controls the impact of the previous velocity,

${{c}_{1}}$, ${{c}_{2}}$: Learning coefficients, with one directing towards pBest and the other towards $gBest$, 

${{r}_{1}},{{r}_{2}}$: Random numbers between (0 and 1).

4. Position Update: The position of the particles (the order of the cities) is changed based on the velocity updated in the TSP (this is done by swapping or adjusting the order of the cities).

5. Update pBest and gBest:

•    If the new solution is better than pBest, it is updated.

•    If the new solution is better than gBest, it is also updated.

6. Iteration: Repeat updating velocity and position until the specified number of iterations or convergence is reached.

PSO Pseudocode

ping_mu_jie_tu_2025-07-23_145626.png

Figure 2. Flowchart of the PSO algorithm

5.3 Elephant Herding Optimization (EHO)

EHO are optimization problems that require a swarm-based metaheuristic search approach, which was defined by Wang towards the end of 2015, The algorithm simulates how real elephants in a clan would herd their herds [2, 9].

 The following is a summary of the herding behavior:

• The swarms of elephants are divided into several smaller groups, known as clans, that are made up of several female elephants and their calves [2, 9].

• A matriarch, or adult female, is in charge of overseeing every clan [2, 9]. 

• A male calf in a clan leaves the group when it reaches adulthood [2, 9]. 

Steps of the EHO Algorithm for Solving the TSP as shown in the Figure 3:

1. Initialization: Randomly initialize positions (tours) for each elephant in clans. 

2. Fitness Evaluation:

•    Fitness = Total distance of the tour (sum of distances between cities).

•    Minimize this fitness function.

3. Clan Grouping: Divide elephants into clans (subgroups).

4. Position Update: Update position of each elephant by Eq. (5).

    $X_{ij}^{t+1}=X_{best,j}^{t}+a\text{*}\left( X_{ij}^{t}-X_{center,j}^{t} \right)\text{*}r$    (5)

$X_{ij}^{t}$: position of elephant i, $X_{best,j}^{t}$: Best elephant in the clan, $X_{center,j}^{t}$: clan center, $a$: learning rate, $r$: random value in [0,1].

5. Migration (Separation Operator): Replace worst elephant (longest tour) with a random tour by Eq. (6).

 ${{X}_{worst}}={{X}_{new\text{ }\!\!~\!\!\text{ }  random\text{ }\!\!~\!\!\text{ }}}$    (6)

${{X}_{worst}}$: is the current solution of the worst elephant, i.e., the elephant with the longest tour, ${{X}_{new~random~}}$: is a newly generated random solution, created by randomly shuffling the cities to form a new tour.

6. Update Global Best: If a new best tour is found, update the global best solution.

7. Iteration: Repeat until convergence or maximum iterations reached.

EHO Pseudocode

ping_mu_jie_tu_2025-07-23_150244.png

Figure 3. Flowchart of the EHO algorithm

• EHO: This algorithm always provided the optimal cost in most cases and had low execution time, especially in big city sets. It was highly scalable and efficient and thus particularly well-suited for big and intricate datasets.

Trends:

• For 5 and 10 cities: All algorithms provide solutions within reasonable execution time. EHO performs better than others regarding solution quality.
• For 14 and 19 cities: Classical algorithms begin lagging behind. EHO performs very well; ACO and PSO scale fairly well.
• For 100 and 150 cities: Swarm-based algorithms alone (ACO, PSO, EHO) provide solutions within reasonable time. EHO and ACO perform better than PSO on cost quality.

Follows from the analysis in the above discussion that both as can be seen from the carried-out analysis, execution of TSP algorithms primarily relies on both dataset size (number of cities) and time of execution necessary. Traditional algorithms such as BB and DP executed perfectly with small problem sizes (e.g., 10 or 5 cities), yielding accurate and efficient outcomes. However, their lack of computational efficiency was felt as problems turned increasingly complex. As a contrast, metaheuristic algorithms, EHO, ACO, and PSO were found more scalable and flexible with bigger data sets.

Out of the tested algorithms, EHO returned the best costs with highest quality for all except one instance of the problem sizes and demonstrated its global search capability and convergence property. ACO, on the other hand, had a very good cost-effectiveness/executions time ratio, particularly on large instances. PSO was also good but demonstrated variability with parameter settings.

Future directions:

For increasing the convergence rate and solution quality in the future research on TSP, researcher could focus on hybrid solutions incorporating local search and swarm intelligence together with AI-supported learning mechanisms. More sophisticated variations of TSP such as the Vehicle Routing Problem and Dynamic TSP can further be augmented by adaptive and real-time optimization routines. Machine learning algorithms can further facilitate dynamic adjustment of parameters such that algorithms may automatically adapt to evolving problem instances. Additionally, the use of deep learning frameworks can facilitate faster computation and increased accuracy in real-world applications like smart logistics, autonomous navigation, and cooperative robots.