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.

From 2000 till 2024, it has been two decades of research to implement artificial intelligence (AI) and metaheuristic algorithms to determine the solution of the Traveling Salesman Problem (TSP), a popular NP-hard combinatorial optimization problem. It was all about creating and enhancing various algorithms like Branch and Bound (BB), Dynamic Programming (DP), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and recently Elephant Herding Optimization (EHO).

1) Evolution and Trends in TSP Algorithms:

TSP solutions in the early stages were exact in nature like BB and DP [6, 7], which did not work for large datasets since they were exponential in terms of memory and time requirements. SI techniques like ACO and PSO were introduced to combat the same. ACO is inspired by ant foraging behavior [8] and PSO incorporates social optimization. Both of them were susceptible to premature convergence and parameter sensitivity [9]. EHO inspired by elephant herd behavior assisted in improving execution times and solution quality for large TSP instances [10], and the strengths and weaknesses of the studies reviewed are summarized in Table 1.

2) Thematic Grouping of Literature:

The literature studied can be classified as:

$\bullet$ Algorithmic Efficiency Improvements:

· Zhang [11] strengthened often used paths to improve ACO, speeding up the solution process.

· Emambocus [12] achieved more accurate results using PSO with genetic algorithms.

· Marqas et al. [13] improved performance on huge datasets by optimizing EHO parameters.

$\bullet$ Handling Large-Scale Datasets:

· Robati et al. [14] modified PSO to make efficient usage feasible in larger instances of TSP.

· Li et al. [15] and Zhang and Gao [16] confirmed EHO's effectiveness in scaling across large-dimensional datasets.

$\bullet$ Dynamic and Adaptive Algorithms:

· A model of ACO that is capable of adapting to varying city distances was introduced by Zhou et al. [17].

3) Relevance to Current Study:

This paper evaluates three popular algorithms ACO, PSO, and EHO using different dataset sizes. EHO consistently outperforms ACO in terms of optimal cost, especially as the number of cities increases. This highlights the increasing use of swarm-based methods in areas such as dynamic routing, transportation planning, and intelligent logistics systems. and presents an EHO framework that decomposes the problem to enable solution quality and scalability. The framework fills current research gaps and provides a more flexible method than TPS in resolving complex and large-size instances.

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).

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

TSP Applications

$\bullet$ Logistics and supply chains: By minimizing delivery vehicle and truck routes, TSP reduces fuel usage and travel time [23].

$\bullet$ 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].

$\bullet$ Communications and networking: It is used to build wireless and wired networks and enhance data routing protocols to reduce delay [25].

$\bullet$ Health and medicine: It enables DNA sequencing to speed up diagnosis and planning of ambulance routes [26].

$\bullet$ Power and resource management: It conserves operating costs by allocating work crews and planning power plant maintenance [27].

$\bullet$ 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.

Different exact algorithms such as BB and DP are used to solve the TSP.

General fashion for BB algorithms involves modeling the result space as a tree and also covering the tree exploring the most promising subtrees first [29].

This is continued until either there are no subtrees into which to further break the problem, or we have arrived at a point where, if we continue, only inferior results will be set up. can be used to process TSP containing 40–60 cities [18].

This section will analyze the results of the proposed algorithms for solving the TSP by using a number of performance indicators that came from the implementation of the following algorithms: ACO, PSO, BB, DP, and EHO. A number of criteria were used to analyze the performance, including memory consumption (data space, instruction space, environment stack space), execution time, CPU consumption, time and space complexity, and solution quality (optimal cost), these metrics evaluate the effectiveness and practicality of different methods for real-world applications in logistics, transport, and robotics.

$\bullet$ Execution Time: In a real-time scenario, such as robotics and transport route optimization, this metric gauges how fast an algorithm can compute a solution.

$\bullet$ CPU Consumption: It is a measure of computational efficiency having an impact on cost in the cloud and the lifespan of the battery in the embedded device.

$\bullet$ Space and Time Complexity: This describes scalability—exact algorithms (i.e., Branch & Bound) require exponential memory and time, but metaheuristic algorithms (ACO, PSO, EHO) offer effective, low-memory solutions.

$\bullet$ Solution Quality: This analyzes how close a computed solution is to the optimal one, also known as the answer, and tradeoffs in speed and accuracy for scenarios like network planning and logistics.

The effectiveness of the algorithms (ACO, PSO, EHO) for solving TSP depends on the parameter values. Tuning the parameters ensures faster convergence rates and higher-quality solutions.

Key Parameters' Effect on Performance:

$\bullet$ ACO: (β, p) shape the balance between exploration and exploitation.

$\bullet$ PSO: (ω, c1, c2) Compute the convergence speed and diversity of searches.

$\bullet$ EHO:(N, a) control exploration and stability.

Optimization Strategies:

$\bullet$ Manual Tuning: Empirically made changes on the basis of experimental findings.

$\bullet$ Adaptive Tuning: Dynamic parameter adjustments during execution.

On a laptop computer (HP EliteBook x360 1030 G3) with an Intel(R) Core (TM) i5-8350U CPU @ 1.70GHz 1.90GHz, 16 GB of RAM, and Microsoft Windows 10 Pro, the code was run and the results were extracted using MATLAB. The comparison is shown below.

We may infer from the data that the meta-heuristic algorithms (ACO, PSO, and EHO) performed better as the number of cities rose as compared to the BB and DP algorithms. EHO came out for providing notably lower optimal costs than the other algorithms, while ACO and PSO demonstrated balanced performance between execution time and ideal cost. The conventional algorithms (BB and DP) are less efficient when working with more cities because of their great temporal and spatial complexity.

Critical Analysis:

Based on the research results, the performance of each algorithm is highly sensitive to the size and type of problem. ACO and PSO are suitable for deterministic methods, while EHO and BB are ideal for small TSP cases.

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 TSPsuch 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.