Travelling Salesman Problem (TSP): Concepts and Code Explained Simply

Travelling Salesman Problem (TSP): Concepts and Code Explained Simply

• 

  Mr. Bambam Kumar Yadav/ 3 days ago
• 15
• 11 min read

Why is this TSP So Important?

The Travelling Salesman Problem ( TSP ) may just sound like an ongoing riddle, but its quite amazing impact is seen in real-world scenarios like :

• Best Delivery routing is done through a medium like Amazon, FedEx, or Swiggy.
• The computer chip manufacturing system is also available here
• Airline crew scheduling is also observed
• Genome sequencing is also essential
• Tour planning apps are also quite popular

Despite its best observed simplicity in various concepts, TSP is quite essential for an NP-hard type of problem. As this kind of number of cities is often found to be increasing by a number of times, then the number of possible routes is also observed to be increasing a lot exponentially.

The Basic Problem Statement

Given:

A list of cities is displayed.

The distance between each pair of such kinds of cities is also listed here.

Find:

The shortest possible route is to visit each city exactly at least once and return to the origin.

Let’s take and also consider some of the best examples of 4 cities:

A → B → C → D → A

This is also just one route. But with 4 categories of cities, there are equations like (4-1)!/2 = 3 routes (after accounting for rotations and reversals). For example, consider 10 cities; this will give about 181,440 routes!

Understanding the Graph Structure

TSP is best modeled using a mix of a complete weighted graph:

Node relations: Cities

Edges of the area: Routes between cities

Weights of the different areas: Distance or cost

The prime objective: Find the least or even a minimum-weight Hamiltonian Cycle.

Brute Force kind of Approach: Try all different types of Routes

Basic Concepts:

Generate all types of possible permutations of different cities and later calculate the required cost of each route for the same.

Downside for this :

The main time complexity observed is called O(n!), which then becomes quite impractical beyond the capacity of 10–12 cities.

Example of Python Code:

From different itertools, you are required to import permutations.

Source code for importing :

                            def tsp_brute_force(graph, start=0):
                        n = len(graph)
                        cities = list(range(n))
                        cities.remove(start)
                        
                        min_path = float('inf')
                        best_route = []

                        for perm in permutations(cities):
                            cost = 0
                            current = start
                            route = [start]
                            For the city in Perm:
                                cost += graph[current][city]
                                Current = city
                                route.append(city)
                            cost += graph[current][start]  # return to origin
                            route.append(start)

                            if cost < min_path:
                                min_path = cost
                                best_route = route

                        return best_route, min_path

                    # Sample graph (4 cities)
                    graph = [
                        [0, 29, 20, 21],
                        [29, 0, 15, 17],
                        [20, 15, 0, 28],
                        [21, 17, 28, 0]
                    ]

                    route, cost = tsp_brute_force(graph)
                    print("Best Route:", route)
                    print("Minimum Cost:", cost)
                            
                        

Optimized type of unique Approach: Dynamic set of Programming (Held-Karp)

Basic Concept:

Break all the huge problems into just overlapping types of subproblems using both bitmasking and memoization. All this will easily help you to achieve the results you want.

Time Complexity:

O(n² * 2ⁿ.) This is a major improvement over high factorial time!

Best Idea:

Use a set of bitmasks to just represent all visited cities, and then use techniques of recursion with unique memoization to store all the sub-results.

Python Source Code:

                            def tsp_dp(graph):
                            from functools import lru_cache
                            n = len(graph)

                            @lru_cache(None)
                            def visit(city, visited):
                                if visited == (1 << n) - 1:
                                    return graph[city][0]  # return to origin

                                min_cost = float('inf')
                                for next_city in range(n):
                                    if not (visited >> next_city) & 1:
                                        cost = graph[city][next_city] + visit(next_city, visited | (1 << next_city))
                                        min_cost = min(min_cost, cost)
                                return min_cost

                            return visit(0, 1 << 0)

                        # Reuse your previous type of graph
                        print("Minimum Cost with DP:", tsp_dp(graph))
                            
                        

Approximation category of Algorithms for Large Inputs

For different types of large city sets (like 50+), exact category solutions are often too slow. So we have to just use all the heuristics or even some approximation methods.

1. Nearest Neighbor Algorithm

Basic Concept:

Start at an interesting city, visit all the nearest types of unvisited cities until all are visited.

They are not guaranteed optimal solutions at all.

Program source code :

  
                            def tsp_nearest_neighbor(graph, start=0):
                            n = len(graph)
                            visited = [False] * n
                            path = [start]
                            visited[start] = True
                            total_cost = 0
                            current = start

                            for _ in range(n - 1):
                                nearest = None
                                min_dist = float('inf')
                                for j in range(n):
                                    if not visited[j] and 0 < graph[current][j] < min_dist:
                                        nearest = j
                                        min_dist = graph[current][j]
                                visited[nearest] = True
                                path.append(nearest)
                                total_cost += min_dist
                                current = nearest

                            total_cost += graph[current][start]
                            path.append(start)

                            return path, total_cost

                        route, cost = tsp_nearest_neighbor(graph)
                        print("Nearest Neighbor Route:", route)
                        print("Cost:", cost)
                          
                        

2. Genetic Algorithm (GA)

GA often uses the best evolution-inspired set of techniques, like different selection, crossover, and even some of the highly mutation ones, to evolve solutions over generations.

Good for very huge and interesting kinds of large TSP problems Needs some of the best fine-tuning, and also can easily get stuck in some kind of local minima

Different kinds of Libraries, like DEAP, PyGAD, and Pyevolve, are useful.

3. Simulated Annealing

Inspired by some of the great metal cooling, like this algorithm, one that accepts worse kinds of solutions with some probability to just escape local types of optima. Great for other randomized search categories.

Real-World Applications of TSP

Interesting type of some different Variations of TSP

Multiple sets of Travelling Salesmen Problem (mTSP) often highlight One team, another with multiple salesmen with different types of city allocation.

Asymmetric TSP (ATSP) Cost is distributed from range A to B ≠ B to A (real-world kind of road networks).

Time Window of all this TSP Cities must be visited during a specific time window for ease.

Prize-Collecting TSP Visit a general subset of different cities to maximize all the rewards you ever want.

TSP in both trending AI and Machine Learning

Reinforcement Learning, one of the best types, has been applied to all different learn heuristics.

Neural networks have also been tested to help you predict good routes for ease of use.

Google's OR-Tools often provides all kinds of state-of-the-art TSP solvers, with which we see constraint programming is highly observed.

Libraries that help you in solving TSP-related problems

1. Google type of OR-Tools

pip install ortools

2. NetworkX

Great and highly recommended for all graph visualizations, and also some brute force solutions.

3. TSPLIB

A standardized set of libraries is used for testing some of the huge datasets.

4. Concorde TSP-related Solver

One of the best and fastest exact solvers is used in all these academic research areas.One of the best and fastest exact solvers is used in all these academic research areas.

Summary for this trending topic

Final Thoughts and Conclusion

The Travelling Salesman Problem ( TSP ) is one of the areas that is just more than a puzzle then it's one of the best gateways into the world of algorithmic thinking, best optimization, and also even AI areas.

Whether you’re one of the student who is seen exploring the area of recursion, a best kind of data scientist optimizing delivery is waiting for you, or even a developer who is solving some real-world types of logistics, TSP just offers a rich kind of space to all learn and innovate in best possible way.

What’s Next on your mind?

Try solving all types of TSP for your best own city tour, or even some integration into a Python GUI map, you can challenge yourself just with the dynamic constraints. Diagrams, a downloadable PDF, or a Canva blog layout!

TSP is quite trending and one of the best means anytime. You should know this to excel in the world of the shortest possible routes. Be ready to explore and get what you want with ease over here. Be friendly with all routes and get what you want by achieving your dream career the way you want.

Enroll in a Python programming course in Noida and get what you want in your job.