What is the travelling salesman problem?

• complexity
• algorithm
• TSP
• bigonotation
• NPproblem

But first, what it is?

The Traveling Salesman Problem (TSP) is a classic conundrum in the field of computer science and optimization. It's essentially a question of finding the shortest possible route that visits a set of given cities and returns to the original city, with the constraint that each city must be visited exactly once.

With the cities placed like this

We can have a potential path that go through all the cities and ends back in the starting point like these two

For this simple problem, especially with this placement of the cities, It's pretty easy to determine the shortest path even by a glance of the eye, and it looks like this

But what if we have more than just 7 cities like in our case and located in a bit more chaotic way? How hard it actually is to solve this problem for n cities?

Complexity

This problem is NP-hard, meaning there's no known polynomial-time algorithm that can solve it for all cases in a reasonable amount of time.

But what if we consider finding the best solution by Brut force? To measure this type of complexity, it is common to use the Big O notation. It describes roughly how many computations we have to perform in relation to the amount parameters, in our case, cities.

The Big O notation for this problem is O(n!) which means that the computational complexity grows rapidly with the growth of . Take a look at the graph to see how for different problem complexities, the number of operation grows.

You can see that we are in the worst case scenario. How we can approach this then?

How can this be solved?

There are few different solutions to this problem, all of which reduces the complexity. These solutions we can divide into three groups:

1. Exact algorithms
   • Dynamic Programming: The time complexity of the dynamic programming approach for the TSP is 𝑂(𝑛2⋅2𝑛)O(n2⋅2n), where 𝑛n is the number of cities. This makes it impractical for large instances due to its exponential growth with the number of cities.
   • Branch and Bound: The time complexity of branch and bound algorithms varies depending on the specific implementation and heuristics used. In the worst case, it can also be exponential, but more efficient pruning strategies can significantly reduce the search space and improve performance.
2. Approximation Algorithms:
   • Nearest Neighbor: The nearest neighbor algorithm has a time complexity of 𝑂(𝑛2)O(n2), making it more scalable than exact algorithms. However, its solutions may not always be optimal.
   • Genetic Algorithms: The time complexity of genetic algorithms for the TSP varies depending on parameters such as population size, number of generations, and mutation rates. In general, it can be 𝑂(𝑘⋅𝑛⋅𝑔)O(k⋅n⋅g), where 𝑘k is the population size, 𝑛n is the number of cities, and 𝑔g is the number of generations. Genetic algorithms often provide good approximate solutions but may not guarantee optimality.
   • Simulated Annealing: The time complexity of simulated annealing depends on the cooling schedule and the number of iterations. It's typically expressed as 𝑂(𝑛⋅𝑇)O(n⋅T), where 𝑛n is the number of cities and 𝑇T is the number of iterations. Simulated annealing can find high-quality solutions but doesn't guarantee optimality.
3. Heuristic Algorithms: - Ant Colony Optimization: The time complexity of ant colony optimization algorithms for the TSP depends on factors such as the number of ants, the number of iterations, and the pheromone update mechanism. It's generally considered to be 𝑂(𝑛2)O(n2) or 𝑂(𝑛3)O(n3) for moderate-sized instances. - Iterated Local Search: The time complexity of iterated local search algorithms varies depending on the local search procedure and the number of iterations. It's often expressed as 𝑂(𝑛⋅𝑚⋅𝑘)O(n⋅m⋅k), where 𝑛n is the number of cities, 𝑚m is the number of iterations, and 𝑘k is the complexity of the local search. Overall, the TSP remains a challenging problem to solve optimally, especially for large instances, due to its exponential nature. While optimal solutions are desired, in many real-world scenarios, finding a good solution quickly is more important than finding the absolute best solution. Thus, heuristic and approximation algorithms are often favored in practice.

Why am I talking about it?

So, this is a problem solvable, as you have read already above, using a genetic algorithm. For quite some time I was thinking about solving this problem using a genetic algorithm.

In the next article we are going to talk more about genetic algorithms and how we can use this approach for our problem.

So I hope to see you all very soon in How can we apply genetic algorithm to solve traveling salesman problem?.