5 Best Algorithms for the Travelling Salesman Problem

The travelling salesman problem (TSP) is one of the classic problems that asks to find the shortest route possible for a salesman to visit all the cities at once and return to the starting point. By listening, the problem seems easy to solve. However, in reality, there’s no exact algorithm, that can solve the travelling salesman problem.

Over the years, numerous algorithms have been introduced, numerous methodologies are implemented. But, this NP-hard problem became more and more complex, as the cities increase.

But, you don’t need to fret, as we’ve got the best 5 algorithms for the travelling salesman problem, that balances speed and accuracy.

Get data science certification from the World’s top Universities. Learn Executive PG Programs, Advanced Certificate Programs, or Masters Programs to fast-track your career.

The Algorithms for Travelling Salesman Problem in 2025

We’re going to dive deep into the top 5 algorithms for travelling salesman problem, analyzing them on the basis of time complexity, and their specific use case.

Brute Force Algorithm

The Brute Force algorithm is the simplest and most direct approach to solving the TSP. It involves generating all possible permutations of the cities and calculating the total travel distance for each permutation. The solution is the permutation that yields the minimum distance.

How it Works for Travelling Salesman Problem:

1. Generate all possible permutations of the cities, which would be (n-1)! permutations, where n is the number of cities.
2. For each permutation, calculate the total distance traveled by the salesman (the sum of the distances between consecutive cities in the permutation).
3. Select the permutation with the smallest total distance as the optimal solution.

Time Complexity:

The time complexity of the Brute Force algorithm is O(n!) because it generates and checks all permutations of the cities. This grows factorially with the number of cities, making it highly inefficient for larger instances of TSP.

Must Explore: What are Data Structures & Algorithm

When to Use for Travelling Salesman Problem:

The Brute Force approach is only feasible for small-sized instances, typically with fewer than 10 cities. As the number of cities increases, the algorithm becomes computationally impractical due to its exponential growth in complexity.

Held-Karp Algorithm (Dynamic Programming)

The Held-Karp algorithm is a more efficient solution to the TSP that uses dynamic programming. It improves upon the Brute Force approach by breaking the problem down into smaller subproblems and storing intermediate results, significantly reducing the number of redundant calculations.

How it Works for Travelling Salesman Problem:

1. Define a state dp(S, i), where S is a subset of cities and i is a city in that subset. dp(S, i) represents the shortest possible path that visits all cities in subset S and ends at city i.
2. The recursive relation is:

dp(S,i) = min (dp (S∖{i},j) + dist (j,i)) ∀j∈S∖{i}

1. Compute all dp(S, i) values for all subsets S of cities, starting with small subsets and progressively building up to larger ones.
2. Once the table is filled, the shortest tour can be reconstructed from the dp table.

Also Explore: Top 14 Most Common Data Mining Algorithms You Should Know

Time Complexity:

The time complexity of the Held-Karp algorithm is O(n² * 2^n), where n is the number of cities. This is a significant improvement over brute force, but the algorithm still becomes computationally expensive for larger numbers of cities (typically beyond 20-25 cities).

When to Use for Travelling Salesman Problem:

The Held-Karp algorithm is effective for solving TSPs with a moderate number of cities (around 20 to 25). It provides an exact optimal solution and is often used in smaller, well-defined problems where precision is essential.

Greedy Algorithm

The Greedy Algorithm is a simple heuristic method that builds a solution step-by-step by always selecting the locally optimal choice, assuming that this will lead to a globally optimal solution. The Greedy approach is fast but does not guarantee an optimal solution.

How it Works for Travelling Salesman Problem:

1. Start at an arbitrary city.
2. At each step, move to the nearest unvisited city based on the distance matrix (i.e., the city with the smallest distance from the current city).
3. Repeat this process until all cities have been visited.
4. Return to the starting city to complete the tour.

Time Complexity:

The time complexity of the Greedy algorithm is O(n²), where n is the number of cities. This is because, for each city, the algorithm needs to evaluate the distances to all other cities.

When to Use for Travelling Salesman problem:

The Greedy Algorithm is suitable for large-scale problems where a quick, approximate solution is needed. It is used in real-world situations where finding an exact solution is not necessary and computational resources are limited.

Additionally, the Greedy algorithm does not guarantee an optimal solution for travelling salesman problem. In many cases, it gets stuck in local minima and may produce significantly worse solutions than the optimal one.

 Also Read: Top 10 Data Structures & Algorithm Interview Questions & Answers

Genetic Algorithm

The Genetic Algorithm (GA) is an optimization method inspired by the process of natural selection. It uses a population of candidate solutions and evolves them over multiple generations using processes like selection, crossover, and mutation for the travelling salesman problem.

How it Works for Travelling Salesman Problem:

1. Initialization: It generates an initial population of random tours (solutions).
2. Selection: Evaluate each individual in the population based on the fitness function (e.g., the total length of the tour). Select individuals with shorter tours for reproduction.
3. Crossover: Combine two or more parent tours to produce offspring tours. This mimics sexual reproduction and introduces diversity into the population.
4. Mutation: Apply small random changes to offspring tours (e.g., swapping two cities in the tour) to prevent the algorithm from converging prematurely.
5. Repeat: The process is repeated over several generations, with the population evolving towards better solutions.

Time Complexity:

The time complexity of the Genetic Algorithm depends on the number of generations g, population size p, and the number of cities n. It can be estimated as O(g * p * n), where g is the number of generations, p is the population size, and n is the number of cities.

Travelling salesman problem use case:

Genetic algorithms are ideal when you need an approximate solution for large instances of the TSP. They are particularly useful in scenarios where finding an exact solution is computationally prohibitive, and a good-enough solution is acceptable.

Furthermore, genetic algorithms do not guarantee optimality for travelling salesman problem. Their performance depends heavily on the choice of parameters (such as mutation rate, population size, and number of generations) and may converge to a suboptimal solution.

Must Explore: Selection Sort Algorithm in Data Structure: Code, Function & Exampleed Certificate Programs, or Masters Programs to fast-track your career.

Ant Colony Optimization (ACO)

Ant Colony Optimization (ACO) is a bio-inspired algorithm based on the behavior of ants searching for food. Ants leave pheromones on the paths they take, and subsequent ants are more likely to follow stronger pheromone trails, eventually converging on the shortest path.

How it Works for Travelling Salesman Problem:

1. Initialization: Start by randomly placing a number of ants on the cities.
2. Construct Solutions: Each ant constructs a solution (tour) by moving from city to city, probabilistically choosing the next city based on pheromone levels and distance.
3. Pheromone Update: After each iteration, update the pheromone levels on the paths. Shorter paths receive more pheromones, attracting future ants to follow them.
4. Evaporation: To prevent premature convergence, pheromones evaporate over time, reducing their influence.
5. Repeat: The process repeats for multiple iterations until convergence, where the ants collectively find the optimal or near-optimal path.

Time Complexity:

The time complexity of ACO is approximately O(a * i * n), where “a” is the number of ants, “I” is the number of iterations, and “n” is the number of cities. The complexity depends on the number of ants and iterations, which are tunable parameters.

Travelling Salesman Problem Use Case:

ACO is useful for large-scale TSP instances, where finding an optimal solution is computationally expensive. It provides a good balance between computational efficiency and solution quality and is often used in real-world routing and logistics problems.

In addition, it also has a limitation. ACO is an approximate method and may not always converge to the optimal solution. Its performance depends on the parameter settings (e.g., pheromone evaporation rate, number of ants) and problem characteristics.

Conclusion

The Travelling Salesman Problem is a challenging optimization problem with wide-ranging real-world applications. While the Brute Force algorithm guarantees an optimal solution, its exponential time complexity makes it impractical for large problems. The Held-Karp algorithm offers a more efficient exact solution for moderately sized instances, but still suffers from exponential growth for larger datasets.

For larger problems or when exact solutions are not required, Greedy Algorithms, Genetic Algorithms, and Ant Colony Optimization provide feasible approximate solutions. Each of these heuristic and metaheuristic methods offers a different balance of computational efficiency and solution quality, making them suitable for various practical applications, from logistics and routing to manufacturing and data analysis.

Choosing the best algorithm depends on the problem size, available computational resources, and the acceptable trade-off between optimality and efficiency. 

Unlock the power of data with our popular Data Science courses, designed to make you proficient in analytics, machine learning, and big data!

Explore our Popular Data Science Courses

Elevate your career by learning essential Data Science skills such as statistical modeling, big data processing, predictive analytics, and SQL!

Top Data Science Skills to Learn

Stay informed and inspired with our popular Data Science articles, offering expert insights, trends, and practical tips for aspiring data professionals!

Read our popular Data Science Articles