## Travelling Salesman Problem: Python, C++ Algorithm

## What is the Travelling Salesman Problem (TSP)?

Travelling Salesman Problem (TSP) is a classic combinatorics problem of theoretical computer science. The problem asks to find the shortest path in a graph with the condition of visiting all the nodes only one time and returning to the origin city.

The problem statement gives a list of cities along with the distances between each city.

Objective: To start from the origin city, visit other cities only once, and return to the original city again. Our target is to find the shortest possible path to complete the round-trip route.

## Example of TSP

Here a graph is given where 1, 2, 3, and 4 represent the cities, and the weight associated with every edge represents the distance between those cities.

The goal is to find the shortest possible path for the tour that starts from the origin city, traverses the graph while only visiting the other cities or nodes once, and returns to the origin city.

For the above graph, the optimal route is to follow the minimum cost path: 1-2-4-3-1. And this shortest route would cost 10+25+30+15 =80

## Different Solutions to Travelling Salesman Problem

Travelling Salesman Problem (TSP) is classified as a NP-hard problem due to having no polynomial time algorithm. The complexity increases exponentially by increasing the number of cities.

There are multiple ways to solve the traveling salesman problem (tsp). Some popular solutions are:

The brute force approach is the naive method for solving traveling salesman problems. In this approach, we first calculate all possible paths and then compare them. The number of paths in a graph consisting of n cities is n! It is computationally very expensive to solve the traveling salesman problem in this brute force approach.

The branch-and-bound method: The problem is broken down into sub-problems in this approach. The solution of those individual sub-problems would provide an optimal solution.

This tutorial will demonstrate a dynamic programming approach, the recursive version of this branch-and-bound method, to solve the traveling salesman problem.

Dynamic programming is such a method for seeking optimal solutions by analyzing all possible routes. It is one of the exact solution methods that solve traveling salesman problems through relatively higher cost than the greedy methods that provide a near-optimal solution.

The computational complexity of this approach is O(N^2 * 2^N) which is discussed later in this article.

The nearest neighbor method is a heuristic-based greedy approach where we choose the nearest neighbor node. This approach is computationally less expensive than the dynamic approach. But it does not provide the guarantee of an optimal solution. This method is used for near-optimal solutions.

## Algorithm for Traveling Salesman Problem

We will use the dynamic programming approach to solve the Travelling Salesman Problem (TSP).

Before starting the algorithm, let’s get acquainted with some terminologies:

- A graph G=(V, E), which is a set of vertices and edges.
- V is the set of vertices.
- E is the set of edges.
- Vertices are connected through edges.
- Dist(i,j) denotes the non-negative distance between two vertices, i and j.

Let’s assume S is the subset of cities and belongs to {1, 2, 3, …, n} where 1, 2, 3…n are the cities and i, j are two cities in that subset. Now cost(i, S, j) is defined in such a way as the length of the shortest path visiting node in S, which is exactly once having the starting and ending point as i and j respectively.

For example, cost (1, {2, 3, 4}, 1) denotes the length of the shortest path where:

- Starting city is 1
- Cities 2, 3, and 4 are visited only once
- The ending point is 1

The dynamic programming algorithm would be:

- Set cost(i, , i) = 0, which means we start and end at i, and the cost is 0.
- When |S| > 1, we define cost(i, S, 1) = ∝ where i !=1 . Because initially, we do not know the exact cost to reach city i to city 1 through other cities.
- Now, we need to start at 1 and complete the tour. We need to select the next city in such a way-

cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j) where i∈S and i≠j

For the given figure, the adjacency matrix would be the following:

Let’s see how our algorithm works:

Step 1) We are considering our journey starting at city 1, visit other cities once and return to city 1.

Step 2) S is the subset of cities. According to our algorithm, for all |S| > 1, we will set the distance cost(i, S, 1) = ∝. Here cost(i, S, j) means we are starting at city i, visiting the cities of S once, and now we are at city j. We set this path cost as infinity because we do not know the distance yet. So the values will be the following:

Cost (2, {3, 4}, 1) = ∝ ; the notation denotes we are starting at city 2, going through cities 3, 4, and reaching 1. And the path cost is infinity. Similarly-

cost(3, {2, 4}, 1) = ∝

cost(4, {2, 3}, 1) = ∝

Step 3) Now, for all subsets of S, we need to find the following:

cost(i, S, j)=min cost (i, S−{i}, j)+dist(i,j), where j∈S and i≠j

That means the minimum cost path for starting at i, going through the subset of cities once, and returning to city j. Considering that the journey starts at city 1, the optimal path cost would be= cost(1, {other cities}, 1).

Let’s find out how we could achieve that:

Now S = {1, 2, 3, 4}. There are four elements. Hence the number of subsets will be 2^4 or 16. Those subsets are-

1) |S| = Null:

2) |S| = 1:

{{1}, {2}, {3}, {4}}

3) |S| = 2:

{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

4) |S| = 3:

{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}

5) |S| = 4:

{{1, 2, 3, 4}}

As we are starting at 1, we could discard the subsets containing city 1.

The algorithm calculation:

1) |S| = Φ:

cost (2, Φ, 1) = dist(2, 1) = 10

cost (3, Φ, 1) = dist(3, 1) = 15

cost (4, Φ, 1) = dist(4, 1) = 20

cost (2, {3}, 1) = dist(2, 3) + cost (3, Φ, 1) = 35+15 = 50

cost (2, {4}, 1) = dist(2, 4) + cost (4, Φ, 1) = 25+20 = 45

cost (3, {2}, 1) = dist(3, 2) + cost (2, Φ, 1) = 35+10 = 45

cost (3, {4}, 1) = dist(3, 4) + cost (4, Φ, 1) = 30+20 = 50

cost (4, {2}, 1) = dist(4, 2) + cost (2, Φ, 1) = 25+10 = 35

cost (4, {3}, 1) = dist(4, 3) + cost (3, Φ, 1) = 30+15 = 45

cost (2, {3, 4}, 1) = min [ dist[2,3]+Cost(3,{4},1) = 35+50 = 85,

dist[2,4]+Cost(4,{3},1) = 25+45 = 70 ] = 70

cost (3, {2, 4}, 1) = min [ dist[3,2]+Cost(2,{4},1) = 35+45 = 80,

dist[3,4]+Cost(4,{2},1) = 30+35 = 65 ] = 65

cost (4, {2, 3}, 1) = min [ dist[4,2]+Cost(2,{3},1) = 25+50 = 75

dist[4,3]+Cost(3,{2},1) = 30+45 = 75 ] = 75

cost (1, {2, 3, 4}, 1) = min [ dist[1,2]+Cost(2,{3,4},1) = 10+70 = 80

dist[1,3]+Cost(3,{2,4},1) = 15+65 = 80

dist[1,4]+Cost(4,{2,3},1) = 20+75 = 95 ] = 80

So the optimal solution would be 1-2-4-3-1

## Pseudo-code

Implementation in c/c++.

Here’s the implementation in C++ :

## Implementation in Python

Academic solutions to tsp.

Computer scientists have spent years searching for an improved polynomial time algorithm for the Travelling Salesman Problem. Until now, the problem is still NP-hard.

Though some of the following solutions were published in recent years that have reduced the complexity to a certain degree:

- The classical symmetric TSP is solved by the Zero Suffix Method.
- The Biogeography‐based Optimization Algorithm is based on the migration strategy to solve the optimization problems that can be planned as TSP.
- Multi-Objective Evolutionary Algorithm is designed for solving multiple TSP based on NSGA-II.
- The Multi-Agent System solves the TSP of N cities with fixed resources.

## Application of Traveling Salesman Problem

Travelling Salesman Problem (TSP) is applied in the real world in both its purest and modified forms. Some of those are:

- Planning, logistics, and manufacturing microchips : Chip insertion problems naturally arise in the microchip industry. Those problems can be planned as traveling salesman problems.
- DNA sequencing : Slight modification of the traveling salesman problem can be used in DNA sequencing. Here, the cities represent the DNA fragments, and the distance represents the similarity measure between two DNA fragments.
- Astronomy : The Travelling Salesman Problem is applied by astronomers to minimize the time spent observing various sources.
- Optimal control problem : Travelling Salesman Problem formulation can be applied in optimal control problems. There might be several other constraints added.

## Complexity Analysis of TSP

So the total time complexity for an optimal solution would be the Number of nodes * Number of subproblems * time to solve each sub-problem. The time complexity can be defined as O(N 2 * 2^N).

- Space Complexity: The dynamic programming approach uses memory to store C(S, i), where S is a subset of the vertices set. There is a total of 2 N subsets for each node. So, the space complexity is O(2^N).

Next, you’ll learn about Sieve of Eratosthenes Algorithm

- Linear Search: Python, C++ Example
- DAA Tutorial PDF: Design and Analysis of Algorithms
- Heap Sort Algorithm (With Code in Python and C++)
- Kadence’s Algorithm: Largest Sum Contiguous Subarray
- Radix Sort Algorithm in Data Structure
- Doubly Linked List: C++, Python (Code Example)
- Singly Linked List in Data Structures
- Adjacency List and Matrix Representation of Graph

- Google OR-Tools
- Español – América Latina
- Português – Brasil
- Tiếng Việt

## Traveling Salesperson Problem

This section presents an example that shows how to solve the Traveling Salesperson Problem (TSP) for the locations shown on the map below.

The following sections present programs in Python, C++, Java, and C# that solve the TSP using OR-Tools

## Create the data

The code below creates the data for the problem.

The distance matrix is an array whose i , j entry is the distance from location i to location j in miles, where the array indices correspond to the locations in the following order:

The data also includes:

- The number of vehicles in the problem, which is 1 because this is a TSP. (For a vehicle routing problem (VRP), the number of vehicles can be greater than 1.)
- The depot : the start and end location for the route. In this case, the depot is 0, which corresponds to New York.

## Other ways to create the distance matrix

In this example, the distance matrix is explicitly defined in the program. It's also possible to use a function to calculate distances between locations: for example, the Euclidean formula for the distance between points in the plane. However, it's still more efficient to pre-compute all the distances between locations and store them in a matrix, rather than compute them at run time. See Example: drilling a circuit board for an example that creates the distance matrix this way.

Another alternative is to use the Google Maps Distance Matrix API to dynamically create a distance (or travel time) matrix for a routing problem.

## Create the routing model

The following code in the main section of the programs creates the index manager ( manager ) and the routing model ( routing ). The method manager.IndexToNode converts the solver's internal indices (which you can safely ignore) to the numbers for locations. Location numbers correspond to the indices for the distance matrix.

The inputs to RoutingIndexManager are:

- The number of rows of the distance matrix, which is the number of locations (including the depot).
- The number of vehicles in the problem.
- The node corresponding to the depot.

## Create the distance callback

To use the routing solver, you need to create a distance (or transit) callback : a function that takes any pair of locations and returns the distance between them. The easiest way to do this is using the distance matrix.

The following function creates the callback and registers it with the solver as transit_callback_index .

The callback accepts two indices, from_index and to_index , and returns the corresponding entry of the distance matrix.

## Set the cost of travel

The arc cost evaluator tells the solver how to calculate the cost of travel between any two locations — in other words, the cost of the edge (or arc) joining them in the graph for the problem. The following code sets the arc cost evaluator.

In this example, the arc cost evaluator is the transit_callback_index , which is the solver's internal reference to the distance callback. This means that the cost of travel between any two locations is just the distance between them. However, in general the costs can involve other factors as well.

You can also define multiple arc cost evaluators that depend on which vehicle is traveling between locations, using the method routing.SetArcCostEvaluatorOfVehicle() . For example, if the vehicles have different speeds, you could define the cost of travel between locations to be the distance divided by the vehicle's speed — in other words, the travel time.

## Set search parameters

The following code sets the default search parameters and a heuristic method for finding the first solution:

The code sets the first solution strategy to PATH_CHEAPEST_ARC , which creates an initial route for the solver by repeatedly adding edges with the least weight that don't lead to a previously visited node (other than the depot). For other options, see First solution strategy .

## Add the solution printer

The function that displays the solution returned by the solver is shown below. The function extracts the route from the solution and prints it to the console.

The function displays the optimal route and its distance, which is given by ObjectiveValue() .

## Solve and print the solution

Finally, you can call the solver and print the solution:

This returns the solution and displays the optimal route.

## Run the programs

When you run the programs, they display the following output.

In this example, there's only one route because it's a TSP. But in more general vehicle routing problems, the solution contains multiple routes.

## Save routes to a list or array

As an alternative to printing the solution directly, you can save the route (or routes, for a VRP) to a list or array. This has the advantage of making the routes available in case you want to do something with them later. For example, you could run the program several times with different parameters and save the routes in the returned solutions to a file for comparison.

The following functions save the routes in the solution to any VRP (possibly with multiple vehicles) as a list (Python) or an array (C++).

You can use these functions to get the routes in any of the VRP examples in the Routing section.

The following code displays the routes.

For the current example, this code returns the following route:

As an exercise, modify the code above to format the output the same way as the solution printer for the program.

## Complete programs

The complete TSP programs are shown below.

## Example: drilling a circuit board

The next example involves drilling holes in a circuit board with an automated drill. The problem is to find the shortest route for the drill to take on the board in order to drill all of the required holes. The example is taken from TSPLIB, a library of TSP problems.

Here's scatter chart of the locations for the holes:

The following sections present programs that find a good solution to the circuit board problem, using the solver's default search parameters. After that, we'll show how to find a better solution by changing the search strategy .

The data for the problem consist of 280 points in the plane, shown in the scatter chart above. The program creates the data in an array of ordered pairs corresponding to the points in the plane, as shown below.

## Compute the distance matrix

The function below computes the Euclidean distance between any two points in the data and stores it in an array. Because the routing solver works over the integers, the function rounds the computed distances to integers. Rounding doesn't affect the solution in this example, but might in other cases. See Scaling the distance matrix for a way to avoid possible rounding issues.

## Add the distance callback

The code that creates the distance callback is almost the same as in the previous example. However, in this case the program calls the function that computes the distance matrix before adding the callback.

## Solution printer

The following function prints the solution to the console. To keep the output more compact, the function displays just the indices of the locations in the route.

## Main function

The main function is essentially the same as the one in the previous example , but also includes a call to the function that creates the distance matrix.

## Running the program

The complete programs are shown in the next section . When you run the program, it displays the following route:

Here's a graph of the corresponding route:

The OR-Tools library finds the above tour very quickly: in less than a second on a typical computer. The total length of the above tour is 2790.

Here are the complete programs for the circuit board example.

## Changing the search strategy

The routing solver does not always return the optimal solution to a TSP, because routing problems are computationally intractable. For instance, the solution returned in the previous example is not the optimal route.

To find a better solution, you can use a more advanced search strategy, called guided local search , which enables the solver to escape a local minimum — a solution that is shorter than all nearby routes, but which is not the global minimum. After moving away from the local minimum, the solver continues the search.

The examples below show how to set a guided local search for the circuit board example.

For other local search strategies, see Local search options .

The examples above also enable logging for the search. While logging isn't required, it can be useful for debugging.

When you run the program after making the changes shown above, you get the following solution, which is shorter than the solution shown in the previous section .

For more search options, see Routing Options .

The best algorithms can now routinely solve TSP instances with tens of thousands of nodes. (The record at the time of writing is the pla85900 instance in TSPLIB, a VLSI application with 85,900 nodes. For certain instances with millions of nodes, solutions have been found guaranteed to be within 1% of an optimal tour.)

## Scaling the distance matrix

Since the routing solver works over the integers, if your distance matrix has non-integer entries, you have to round the distances to integers. If some distances are small, rounding can affect the solution.

To avoid any issue with rounding, you can scale the distance matrix: multiply all entries of the matrix by a large number — say 100. This multiplies the length of any route by a factor of 100, but it doesn't change the solution. The advantage is that now when you round the matrix entries, the rounding amount (which is at most 0.5), is very small compared to the distances, so it won't affect the solution significantly.

If you scale the distance matrix, you also need to change the solution printer to divide the scaled route lengths by the scaling factor, so that it displays the unscaled distances of the routes.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2023-01-16 UTC.

Data Science Tutorials

Data Science and Machine Learning in Python and R

## Solving the Travelling Salesman Problem (TSP) with Python

In this tutorial, we would see how to solve the TSP problem in Python. The following sections are covered.

- Approach to Solving the TSP Problem
- The Routing Model and Index Manager
- The Distance Callback
- Travel Cost and Search Parameters
- Function to the Print the Solution
- Putting it all Together

## 1. Approach to Solving the TSP Problem

To be able to solve a TSP problem in Python, we need the following items:

- List of cities
- List of distances between the cities
- Number of vehicles
- Starting location of the vehicles

List of Cities

In this problem we have a list of 12 cities. They are listed below. The indices of the cities are provided against the name.

0. New York – 1. Los Angeles – 2. Chicago – 3. Minneapolis – 4. Denver – 5. Dallas – 6. Seattle – 7. Boston – 8. San Francisco – 9. St. Louis – 10. Houston – 11. Phoenix – 12. Salt Lake City

List of Distances

It is normally better to represent the list of distances as a square matrix with intersecting cells holding distance between the row and column headers. If we use indexes i and j for this matrix, then data[i][j] is the distance between city i and city j.

Number of Vehicles

In this case, since it a TSP, the number of vehicles is 1. The Python code is

Starting Point

In this example, the starting point or ‘depot’ is location 0, that is New York.

## 2. The Routing Model and Index Manager

To solve the TSP in Python, you need to create the RoutingIndexManager and the RoutingModel. The RoutingIndexManager manages conversion between the internal solver variables and NodeIndexes. In this way, we can simply use the NodeIndex in our programs.

The RoutingIndexManager takes three parameters:

- number of location, including the depot (number of rows of the distance matrix
- number of vehicles
- the starting node (depot node)

The code below creates the routing model and index manager

## 3. The Distance Callback

To be able to use the solver, we need to create a distance callback. What is a distance callback? This is a function that takes two locations and returns the distance between them. Since these distances are available in the distance matrix, then we can use the distance matrix. The two functions passed to the distance callback are routing variable indexes, so we need to convert them to distance matrix NodeIndex using IndexToNode() method from the RoutingIndexManager.

The code below does that

## 4. The Travel Cost and Search Parameters

The cost of travel is the cost to travel the distance between two nodes. In the case of the solver, you need to set an arc cost evaluator function that does this calculation. This function takes as parameter the transit_callback_index returned by the distance_callback. In our case, the travel cost is simply the distance between the locations.

However, in a real world scenario, there may be other factors to be considered.

We also need to set the search parameters as well as the heuristic for finding the first solution. In this case, the strategy is PATH_CHEAPEST_ARCH. This heuristic repeatedly adds edge with the least weight that don’t lead to a previously visited node..

## 5. Function to Print the Solution

The function below prints out the solution to the screen by extracting the route from the solution

## 6. Putting it all together

Finally, call the SolveWithParameters() method of the routing model and then call the print_solution function.

The final output of the program is given below:

## Python and the Travelling Salesman Problem

## Understanding the Travelling Salesman Problem

The Travelling Salesman Problem is a classic algorithmic problem in computer science and operations research. It focuses on optimization. In this context, a salesman is given a list of cities and must determine the shortest route to visit each city once and return to his original location.

Python, with its robust set of libraries and packages, is a is an excellent language for solving the TSP with its robust set of libraries and packagesess of creating a Python program to solve the TSP.

## Step 1: Importing the Required Libraries

For this Python program, we will need to import the following libraries:

## Step 2: Creating a List of Cities

Next, we need to create a list of cities. In this example, we generate a list of 50 random cities using numpy:

## Step 3: Calculating the Distance Between Cities

Step 4: solving the problem.

Once we have our distances, we can solve the problem using a technique called Simulated Annealing:

Python provides a flexible and powerful platform for solving complex problems like the TSP. The ability to leverage Python's robust libraries and concise syntax makes it an ideal choice for tackling such tasks. If you need assistance with your Python project, consider hiring Python developers .

If you're interested in enhancing this article or becoming a contributing author, we'd love to hear from you.

Please contact Sasha at [email protected] to discuss the opportunity further or to inquire about adding a direct link to your resource. We welcome your collaboration and contributions!

## Simulated Annealing

Simulated Annealing is a probabilistic technique used for finding an approximate solution to an optimization problem. In the context of the TSP, Simulated Annealing can be applied to find the shortest possible route that a salesman can take to visit each city once and return to his original location.

## Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is a well-known algorithmic problem in the field of computational mathematics and computer science. It involves a hypothetical scenario where a salesman must travel between a number of cities, starting and ending his journey at the same city, with the objective of finding the shortest possible route that allows him to visit every city only once. The TSP is a classic example of an NP-hard optimization problem. For more details, you can visit the Wikipedia page .

Effortlessly Scale Your Tech Team with Expert Remote Laravel and Python Developers Skilled in Protobuf

Enhance Your Tech Team with Expert Laravel and Python Developers Skilled in Jenkins CI

Effortlessly Scale Your Tech Team with Expert Remote Laravel & Python Developers Skilled in Amazon EC2

- DSA Tutorial
- Data Structures
- Linked List
- Recursion & Backtracking
- Dynamic Programming
- Binary Tree
- Binary Search Tree
- Divide & Conquer
- Mathematical
- Backtracking
- Branch and Bound
- Pattern Searching

- Explore Our Geeks Community
- What is memoization? A Complete tutorial
- Dynamic Programming (DP) Tutorial with Problems
- Tabulation vs Memoization
- Optimal Substructure Property in Dynamic Programming | DP-2
- Overlapping Subproblems Property in Dynamic Programming | DP-1
- Steps for how to solve a Dynamic Programming Problem

## Advanced Topics

- Bitmasking and Dynamic Programming | Set 1 (Count ways to assign unique cap to every person)
- Digit DP | Introduction
- Sum over Subsets | Dynamic Programming

## Easy problems in Dynamic programming

- Count number of coins required to make a given value (Coin Change II)
- Subset Sum Problem
- Introduction and Dynamic Programming solution to compute nCr%p
- Cutting a Rod | DP-13
- Painting Fence Algorithm
- Longest Common Subsequence (LCS)
- Longest Increasing Subsequence (LIS)
- Longest subsequence such that difference between adjacents is one
- Maximum size square sub-matrix with all 1s
- Min Cost Path | DP-6
- Longest Common Substring (Space optimized DP solution)
- Count ways to reach the nth stair using step 1, 2 or 3
- Count Unique Paths in matrix
- Unique paths in a Grid with Obstacles

## Medium problems on Dynamic programming

- 0/1 Knapsack Problem
- Printing Items in 0/1 Knapsack
- Unbounded Knapsack (Repetition of items allowed)
- Egg Dropping Puzzle | DP-11
- Word Break Problem | DP-32
- Vertex Cover Problem (Dynamic Programming Solution for Tree)
- Tile Stacking Problem
- Box Stacking Problem | DP-22
- Partition problem | DP-18

## Travelling Salesman Problem using Dynamic Programming

- Longest Palindromic Subsequence (LPS)
- Longest Common Increasing Subsequence (LCS + LIS)
- Find all distinct subset (or subsequence) sums of an array
- Weighted Job Scheduling
- Count Derangements (Permutation such that no element appears in its original position)
- Minimum insertions to form a palindrome | DP-28
- Ways to arrange Balls such that adjacent balls are of different types

## Hard problems on Dynamic programming

- Palindrome Partitioning
- Word Wrap Problem
- The Painter's Partition Problem
- Program for Bridge and Torch problem
- Matrix Chain Multiplication | DP-8
- Printing brackets in Matrix Chain Multiplication Problem
- Maximum sum rectangle in a 2D matrix | DP-27
- Maximum profit by buying and selling a share at most k times
- Minimum cost to sort strings using reversal operations of different costs
- Count of AP (Arithmetic Progression) Subsequences in an array
- Introduction to Dynamic Programming on Trees
- Maximum height of Tree when any Node can be considered as Root
- Longest repeating and non-overlapping substring

Travelling Salesman Problem (TSP):

Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to find if there exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact, many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.

For example, consider the graph shown in the figure on the right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The problem is a famous NP-hard problem. There is no polynomial-time know solution for this problem. The following are different solutions for the traveling salesman problem.

Naive Solution:

1) Consider city 1 as the starting and ending point.

2) Generate all (n-1)! Permutations of cities.

3) Calculate the cost of every permutation and keep track of the minimum cost permutation.

4) Return the permutation with minimum cost.

Time Complexity: ?(n!)

Dynamic Programming:

Let the given set of vertices be {1, 2, 3, 4,….n}. Let us consider 1 as starting and ending point of output. For every other vertex I (other than 1), we find the minimum cost path with 1 as the starting point, I as the ending point, and all vertices appearing exactly once. Let the cost of this path cost (i), and the cost of the corresponding Cycle would cost (i) + dist(i, 1) where dist(i, 1) is the distance from I to 1. Finally, we return the minimum of all [cost(i) + dist(i, 1)] values. This looks simple so far.

Now the question is how to get cost(i)? To calculate the cost(i) using Dynamic Programming, we need to have some recursive relation in terms of sub-problems.

Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i . We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note that 1 must be present in every subset.

Below is the dynamic programming solution for the problem using top down recursive+memoized approach:-

For maintaining the subsets we can use the bitmasks to represent the remaining nodes in our subset. Since bits are faster to operate and there are only few nodes in graph, bitmasks is better to use.

For example: –

10100 represents node 2 and node 4 are left in set to be processed

010010 represents node 1 and 4 are left in subset.

NOTE:- ignore the 0th bit since our graph is 1-based

Time Complexity : O(n 2 *2 n ) where O(n* 2 n) are maximum number of unique subproblems/states and O(n) for transition (through for loop as in code) in every states.

Auxiliary Space: O(n*2 n ), where n is number of Nodes/Cities here.

For a set of size n, we consider n-2 subsets each of size n-1 such that all subsets don’t have nth in them. Using the above recurrence relation, we can write a dynamic programming-based solution. There are at most O(n*2 n ) subproblems, and each one takes linear time to solve. The total running time is therefore O(n 2 *2 n ). The time complexity is much less than O(n!) but still exponential. The space required is also exponential. So this approach is also infeasible even for a slightly higher number of vertices. We will soon be discussing approximate algorithms for the traveling salesman problem.

Next Article: Traveling Salesman Problem | Set 2

References:

http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf

http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule. Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

- DSA in Java
- DSA in Python
- DSA in JavaScript

## Please Login to comment...

- lokeshpotta20
- serjeelranjan
- sagartomar9927
- tapeshdua420
- akashcherukuri007
- akshaytripathi19410
- 10 Best ChatGPT Plugin for Developers in 2024
- How to Write a Book With ChatGPT
- 10 Best Kodi IPTV Addons
- 10 Best Softwares to Make a Transparent PNG in 2024
- 100 Days of GATE Data Science & AI – A Complete Guide For Beginners

## Improve your Coding Skills with Practice

## What kind of Experience do you want to share?

- Coding Problems

## Travelling Salesman Problem (TSP)

Problem statement, example 1: travelling salesman problem, example 2: travelling salesman problem, 1. simple approach, c++ code implementation, java code implementation, python code implementation, 2. travelling salesman problem using dynamic programming, c code implementation, 3. greedy approach, practice questions, frequently asked questions, 1. which algorithm is used for the travelling salesman problem, 2. what is the complexity of the travelling salesman problem, 3. how is this problem modelled as a graph problem, 4: what is the difficulty level of the travelling salesman problem.

Travelling Salesman Problem (TSP) – Given a set of cities and the distance between every pair of cities as an adjacency matrix, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. The ultimate goal is to minimize the total distance travelled, forming a closed tour or circuit.

The TSP is referred to as an NP-hard problem, meaning there is no known algorithm to solve it in polynomial time for large instances. As the number of cities increases, the number of potential solutions grows exponentially, making an exhaustive search unfeasible. This complexity is one of the reasons why the TSP remains a popular topic of research. Learn More .

Input –

## Confused about your next job?

Output –

Here, the TSP Tour is 0-2-1-3-0 and the cost of the tour is 48.

Minimum weight Hamiltonian Cycle : EACBDE= 32

Wondering how the Hamiltonian Cycle Problem and the Traveling Salesman Problem differ? The Hamiltonian Cycle problem is to find out if there exists a tour that visits each city exactly once. Here, we know that the Hamiltonian Tour exists (due to the graph being complete), and there are indeed many such tours. The problem is to find a minimum weight Hamiltonian Cycle.

There are various approaches to finding the solution to the travelling salesman problem- simple (naïve) approach, dynamic programming approach, and greedy approach. Let’s explore each approach in detail:

- Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider any point as a starting point.
- Now, we will generate all possible permutations of cities which are (n-1)!.
- Find the cost of each permutation and keep track of the minimum cost permutation.
- Return the permutation with minimum cost.
- Time complexity: O(N!), Where N is the number of cities.
- Space complexity: O(1).

In the travelling salesman problem algorithm, we take a subset N of the required cities that need to be visited, the distance among the cities dist, and starting cities s as inputs. Each city is identified by a unique city id which we say like 1,2,3,4,5………n

Here we use a dynamic approach to calculate the cost function Cost(). Using recursive calls, we calculate the cost function for each subset of the original problem.

To calculate the cost(i) using Dynamic Programming , we need to have some recursive relation in terms of sub-problems.

We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on.

There are at most O(n2^n) subproblems, and each one takes linear time to solve. The total running time is, therefore, O(n^22^n). The time complexity is much less than O(n!) but still exponential. The space required is also exponential.

- Time Complexity: O(N^2*2^N).
- First of them is a list that can hold the indices of the cities in terms of the input matrix of distances between cities
- And the Second one is the array which is our result
- Perform traversal on the given adjacency matrix tsp[][] for all the cities and if the cost of reaching any city from the current city is less than the current cost update the cost.
- Generate the minimum path cycle using the above step and return their minimum cost.
- Time complexity: O(N^2*logN), Where N is the number of cities.
- Space complexity: O(N).
- City Tour Problem
- Shortest Common Substring

Ans . Travelling Salesman Problem uses Dynamic programming with a masking algorithm.

Ans.: The complexity of TSP using Greedy will be O(N^2 LogN) and using DP will be O(N^2 2^N).

Ans .: The TSP can be modelled as a graph problem by considering a complete graph G = (V, E). A tour is then a circuit in G that meets every node. In this context, tours are sometimes called Hamiltonian circuits.

Ans.: It is an NP-hard problem.

- Travelling Salesman Problem

## Previous Post

Longest common subsequence, minimum spanning tree – kruskal algorithm.

## The traveling salesman and 10 lines of Python

October 25, 2016*.

Tags: programming , optimization

Update (21 May 18): It turns out this post is one of the top hits on google for “python travelling salesmen”! That means a lot of people who want to solve the travelling salesmen problem in python end up here. While I tried to do a good job explaining a simple algorithm for this, it was for a challenge to make a progam in 10 lines of code or fewer. That constraint means it’s definitely not the best code around for using for a demanding application, and not the best for learning to write good, readable code. On the other hand, it is simple and short, and I explain each line. So stick around if you’re up for that. Otherwise, while I haven’t used it myself, Google has a library “OR-Tools” that has a nice page about solving the travelling salesmen problem in python via their library. So maybe check that out!

Update (29 May 19): I wrote a small Julia package to exactly solve small TSP instances: https://github.com/ericphanson/TravelingSalesmanExact.jl .

A few weeks ago I got an email about a high performance computing course I had signed up for; the professor wanted all of the participants to send him the “most complicated” 10 line Python program they could, in order to gauge the level of the class And to submit 10 blank lines if we didn’t know any Python!" .

I had an evening free and wanted to challenge myself a bit, and came up with the idea of trying to write an algorithm for approximating a solution to the traveling salesman problem . A long time ago, I had followed a tutorial for implementing a genetic algorithm in java for this and thought it was a lot of fun, so I tried a genetic algorithm first and quickly found it was hard to fit in ten lines. I changed to a simulated annealing approach and found a nice pedagogical tutorial here: theprojectspot.com//simulated_annealing (in java, however). I should mention: I don’t really know python, and haven’t done any non-tutorial-level programming in general. So I’m sure there’s a lot to improve here, and I hope the reader proceeds at their own risk.

Warnings aside, here’s the result which has been fixed up a little since then :

which you can download here if you want. A few sample outputs:

Note Thank you to Monish Kaul for pointing out this problem! : if you’re using your own list of cities, it can help to rescale the coordinates so they run between 0 and a 100 by a simple affine transformation

To illustrate, I generated some cities via

which gives cities with coordinates between 0 and 0.01. Running the code with these cities gives a terrible result:

But if we run the code with rescaled_cities (and plot with the original coordinates), we find a much nicer result:

## A line by line reading

As the professor mentioned in his reply, the code is completely unreadable. I thought it would be good to document it somewhere, and why not here.

This first line is just Python imports to use different commands.

The goal here is to make an list of “cities”, each which are simply a list of two coordinates, chosen as random integers from 0 to 100. I think a better practice usually would to make a constant for the grid size and the number of cities, and use that throughout the script. But with the 10 line requirement, all that will have to be hardcoded.

To explain the command itself, starting from the innermost command, range(100) returns the list [0,1,2,...,100] . Then random.sample( ,2) randomly chooses a set of size 2 from the list. This in fact makes it so that for each city, it’s first and second coordinates will never be the same. Since we just want to come up with some cities for the algorithm to run on, this doesn’t really matter; we could’ve hardcoded a list of cities here instead I see them as allowing math-y set-like notation, but I’ll leave the explanation to the experts on the other side of the link. I’ll use them a lot to save space. This last piece thus repeats the random sampling 15 times and forms a list of these pairs of coordinates, which I called cities .

A “tour” will just be a list of 15 numbers indicating an order to visit the cities. We’ll assume you need a closed loop, so the last city will be automatically connected to the first. Here we just choose a random order to start off with. Python also has a random.shuffle() command, but then we would need two lines: one to create a list, and another to shuffle it. By asking for a random sample of 15 numbers from a list of 15 elements, we get a shuffled list created for us in one line.

We start off a for-loop. In the tutorial I was reading (linked above), they do something like

and this was my attempt to write that in one line. I don’t actually really know why you want an exponentially decreasing temperature in a simulated annealing algorithm Briefly searching, I found this paper which might be relevant? ; I just followed the tutorial. The command numpy.logspace(0,5,num=100000) gives a list of 100,000 numbers between \(10^0\) and \(10^5\) so that the (base 10) logarithm of these numbers is evenly spaced. So choosing numbers in this alone should recover exponentially distributed temperatures. However, they are in lowest-first order. Since we want the temperature to start high, I added [::-1] which reverses the list.

This one is terribly long, but only because I skipped using variables to save a few lines. If we define

then the code becomes a lot cleaner:

which is a little easier to understand. First, if we accept the condition on the if statement, we will update our old tour to this new tour. The idea is that in the metaphor with statistical mechanics, the sum of the distances between all the cities is the energy of the system, which we wish to minimize. We consider the Gibbs factor \(\mathrm{e}^{-\Delta E / T}\) of the exponential of the (negative) change in energy over temperature which should be something like the probability of transitioning to the new state from the old one. I only sum the distances from and to the i th and j th cities, because the rest of the distances are the same for the two tours and will cancel. If this factor has \(\mathrm{e}^{-\Delta E / T}>1\) then the new energy is lower, and we should definitely take the new tour. Otherwise, even if it’s worse, we want to take the new tour with some probability so that we don’t get stuck in a local minimum. We will choose it with probability \(\mathrm{e}^{-\Delta E / T}\) by choosing a uniformly random number in \(r \in [0,1]\) by Python’s random.random() and asking for \(\mathrm{e}^{-\Delta E / T} > r\) . This was a little confusing to me at first, but if I just think of \(\mathrm{e}^{-\Delta E / T} = \frac{3}{4}\) , then we accept as long as \(\frac{3}{4}\) is larger than our uniformly random number, which should happen \(\frac{3}{4}\) of the time Yes, somehow this convinces me when the same formula with a variable did not. .

We actually finish the algorithm here. We choose to update our tour or not as described above, lower the temperature, randomly swap two cities, and try again until we run out of temperatures (here, I put 100,000 of them). At the end, whatever is in the variable tour is our best guess as to the optimal route. I have no idea how to figure out analytically any type of convergence result or confidence in this output. This is partly why we have the next two lines Thanks to Vincent for suggesting an improvement in line 9! .

In these two lines, the Python module matplotlib plots the cities and connects them according to our best guess tour. I’m pretty impressed that it’s a two line problem! The pictures are nice, and for a small number of cities, fairly convincing to the eye that it’s at least a pretty good route. That is, the algorithm did something! Considering that we used \(10^5\) loop iterations and a brute force solution of searching over all possible \(15! \sim 10^{12}\) tours would take much longer (though would be guaranteed to be optimal), I’m happy with the result Happy, though perhaps not content: of course, I want something better than “it looks pretty good” . As for the code itself, we just have to get everything in order. First, the list comprehension

writes out the cities in order according to the tour, and includes the first one again at the end (using that % in Python is modulo). Then we select for the first or second coordinate by adding a [0] or [1] index:

The string 'xb-' tells matplotpy to draw x’s on the points, and connect them with blue lines. Lastly, the command plt.plot( ) generates this plot, and plt.show() displays it.

## And that’s it!

In retrospect, I think simulated annealing was a good fit for the ten line constraint. Looking at the code, lines 1-3 are just mandatory import statements and choosing an instance of TSM to solve. Lines 4-8 are the whole algorithm, and it is almost a transcription of pseudocode. In the tutorial actually, they save the best route as they go, because sometimes it’s better than the last route, and there’s basically no cost to doing so in that context. I drop that here to save space, but for a small amount of cities and large number of temperatures, it still works out fine. I originally submitted the code with ten cities and 10,000 temperatures, and the professor told me that it was quite fast, even compared to lengthier implementations. I think that may be an artifact of the small number of cities, and that the code probably doesn’t scale as well. At ten cities the speed up over brute force is only \(10! \sim 10^6\) versus \(10^4\) loops, so it becomes much more impressive at the fifteen city mark. On my computer it still only takes a few seconds for the \(10^5\) loops, but of course it takes about ten times longer for each additional number in that exponent, so it’s not really feasible to check the scaling much past fifteen cities and with more cities, it becomes harder to see by eye how good or bad the final route is. .

Going forward, it would be interesting to try to learn about estimating the optimality of the results of such an algorithm, and more about the choice of temperature schedule. I’m not sure I will any time soon though. Another interesting thing would be trying to write a parallel version, maybe for a GPU. Since the size of the solution space grows factorially with the number of cities, I think there should be a big regime where it’s feasible to store all of the cities on each computational node yet have too many cities to find even an approximate solution in a reasonable amount of time with a single node.

The algorithm I implemented here has a global temperature and current route, and each iteration of the loop needs the result of the one before it. But that doesn’t really seem essential. Each node could run it’s own copy of the algorithm (with it’s own temperature and current route), and just broadcast it’s best-yet route to all (or just some of) the other nodes every so often. Each node could then just adopt the best route they receive as their current route, and continue iterating from there. Since we are trying to iterate towards the optimal solution by random swaps in this huge solution space, the likelihood of two nodes duplicating work should be very low, so this method could provide a decent speed-up. I’m not sure how the scaling with the number of nodes would be, however. Anyway, I’m sure all of this is old territory in the optimization world. Lots to learn.

## Search code, repositories, users, issues, pull requests...

Provide feedback.

We read every piece of feedback, and take your input very seriously.

## Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

- Notifications

Solution to TSP (Travelling salesman problem) using Particle Swarm Optimization (PSO) - Language: Python

## marcoscastro/tsp_pso

- Python 100.0%

## IMAGES

## VIDEO

## COMMENTS

Implementation in Python Academic Solutions to TSP Application of Traveling Salesman Problem Complexity Analysis of TSP Example of TSP Here a graph is given where 1, 2, 3, and 4 represent the cities, and the weight associated with every edge represents the distance between those cities.

Travelling Salesman Problem (TSP) : Given a set of cities and distances between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. Note the difference between Hamiltonian Cycle and TSP.

How do I solve a Travelling Salesman problem in python? I did not find any library, there should be a way using scipy functions for optimization or other libraries. My hacky-extremelly-lazy-pythonic bruteforcing solution is:

Traveling Salesperson Problem bookmark_border On this page Create the data Create the routing model Create the distance callback Set the cost of travel Set search parameters This section...

Solving Geographic Travelling Salesman Problems using Python Using pyconcorde to find optimal solutions to real-world routing problems Mike Jones · Follow Published in Towards Data Science · 12 min read · Jul 12, 2023 -- An optimal car driving route between 79 UK cities. Image by author. Map data from OpenStreetMap.

Solving the Travelling Salesman Problem (TSP) with Python by kindsonthegenius January 23, 2021 In this tutorial, we would see how to solve the TSP problem in Python. The following sections are covered. Approach to Solving the TSP Problem The Routing Model and Index Manager The Distance Callback Travel Cost and Search Parameters

Implementing, Solving, and Visualizing the Traveling Salesman Problem with Python Translate an optimization model from math to Python, optimize it, and visualize the solution to gain quick feedback on modeling errors Carlos J. Uribe · Follow Published in Towards Data Science · 23 min read · May 9, 2023 -- 2 Photo by John Matychuk on Unsplash

It focuses on optimization. In this context, a salesman is given a list of cities and must determine the shortest route to visit each city once and return to his original location. Python and the Travelling Salesman Problem. Python, with its robust set of libraries and packages, is a is an excellent language for solving the TSP with its robust ...

0:00 / 30:49 The Travelling Salesman Problem with Google's OR-Tools.OR-Tools for TSP: https://developers.google.com/optimization/routing/tspGoogle Maps Distance Matrix AP...

The travelling salesperson problem (TSP) is a classic optimization problem where the goal is to determine the shortest tour of a collection of n "cities" (i.e. nodes), starting and ending in the same city and visiting all of the other cities exactly once.

python vehicle-routing-problem vrp tsp operations-research metaheuristic adaptive-large-neighbourhood-search travelling-salesman-problem flow-shop scheduling-problem alns rcpsp cutting-stock-problem Updated on Oct 31, 2023 Python chaitjo / graph-convnet-tsp Star 272 Code Issues Pull requests

In this article, we'll be seeing the basic approach and its complexity to solve one of the classic optimization problems, i.e. Travelling Salesman Problem.

The Travelling Salesman Problem (TSP, or travelling salesperson problem) is one of the most common problems in the area of operations research. The problem can be defined as follows: In the above…

There are very few tasks that can't be coerced into classification or regression problems. But let's shift gears today and discuss some of those problems. Two high impact problems in OR include the "traveling salesman problem" and the "vehicle routing problem.". The latter is much more tricky, involves a time component and often ...

Step-by-step modeling and solution of the Traveling Salesman Problem using Python and Pyomo. In this post, we will go through one of the most famous Operations Research problem, the TSP(Traveling ...

1) Consider city 1 as the starting and ending point. 2) Generate all (n-1)! Permutations of cities. 3) Calculate the cost of every permutation and keep track of the minimum cost permutation. 4) Return the permutation with minimum cost. Time Complexity: ? (n!) Dynamic Programming: Let the given set of vertices be {1, 2, 3, 4,….n}.

There are various approaches to finding the solution to the travelling salesman problem- simple (naïve) approach, dynamic programming approach, and greedy approach. Let's explore each approach in detail: 1. Simple Approach. Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider any point as a starting point.

GitHub - rohanp/travelingSalesman: Various algorithms for solving the Traveling Salesman problem in python! master Code README Traveling Salesman Problem Formally, the problem asks to find the minimum distance cycle in a set of nodes in 2D space.

Finding an approximate solution to the Travelling Salesman Problem using Variable Neighborhood Search in a reasonable time. ... Travelling Salesman simulation with python program and visulalization with pygame. ... Evolution in Your Code — Understanding and Coding Genetic Algorithm From Scratch — Part 1.

The Traveling Salesman Problem ( TSP) is a classic optimization problem in which a salesman must visit a set of cities exactly once and return to the starting city while minimizing the total distance traveled. The TSP is NP-hard, which means that finding an exact solution for large instances of the problem is computationally infeasible.

That means a lot of people who want to solve the travelling salesmen problem in python end up here. While I tried to do a good job explaining a simple algorithm for this, it was for a challenge to make a progam in 10 lines of code or fewer. That constraint means it's definitely not the best code around for using for a demanding application ...

Solution to TSP (Travelling salesman problem) using Particle Swarm Optimization (PSO) - Language: Python - GitHub - marcoscastro/tsp_pso: Solution to TSP (Travelling salesman problem) using Particle Swarm Optimization (PSO) - Language: Python ... Search code, repositories, users, issues, pull requests... Search Clear.