2D Travelling Salesman Problem: Optimization Algorithms in…

What is the 2D Travelling Salesman Problem?

The 2D Travelling Salesman Problem (TSP) involves finding the shortest possible route that visits a set of cities and returns to the starting point. Each city must be visited exactly once, making it an NP-hard problem with no known efficient solution for large numbers of cities.

This problem is not only relevant in logistics but also appears in various fields such as DNA sequencing, network routing, and even planning delivery routes.

Nearest Neighbor Algorithm

The Nearest Neighbor algorithm starts at a random city and repeatedly visits the nearest unvisited city until all cities are visited. Although simple, it often provides good results for small to medium-sized problems but can get stuck in local optima.

This method is fast and easy to implement but may not always produce the optimal solution.

live demo · related simulation● LIVE

2-opt Local Search

The 2-opt algorithm improves a given tour by iteratively removing two edges from it and reconnecting the remaining parts in all possible ways. This process is repeated until no further improvement can be made.

While more effective than Nearest Neighbor, 2-opt still has limitations as it only considers local improvements and may not find the global optimum.

Simulated Annealing

Simulated Annealing is a probabilistic technique inspired by the annealing process in metallurgy. It starts with an initial solution (tour) and gradually improves it, allowing for occasional worse solutions to escape local optima.

By carefully controlling the cooling schedule, Simulated Annealing can explore more of the solution space and potentially find better solutions than other methods.

Frequently asked questions

Why are there different algorithms for solving TSP?

Different algorithms offer varying trade-offs between computational complexity, solution quality, and ease of implementation. Some may work well on small problems but struggle with larger ones, while others can handle larger instances more effectively.

Can these algorithms always find the optimal solution?

No, TSP is an NP-hard problem, meaning that finding the optimal solution becomes exponentially harder as the number of cities increases. These algorithms are designed to find good solutions in a reasonable amount of time but cannot guarantee optimality for all cases.

How does Simulated Annealing avoid getting stuck in local optima?

Simulated Annealing allows occasional worse solutions by using a probability function that depends on the current temperature. As the temperature decreases, it becomes less likely to accept worse solutions, but this process helps escape local optima and explore more of the solution space.

What is the significance of the cooling schedule in Simulated Annealing?

The cooling schedule determines how quickly the temperature decreases. A poorly chosen cooling rate can lead to either too many or too few improvements, affecting the quality of the final solution and the algorithm's overall performance.

Try it live

Everything above runs in your browser — open 2D Travelling Salesman — Nearest Neighbour, 2-opt & Simulated Annealing and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open 2D Travelling Salesman — Nearest Neighbour, 2-opt & Simulated Annealing simulation

2D Travelling Salesman Problem: Optimization Algorithms in Action