Google OR-Tools

  • 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.

travelling salesman problem python solution

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.

Guru99

Travelling Salesman Problem: Python, C++ Algorithm

Alyssa Walker

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.

Example of TSP

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

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:

Algorithm for Traveling Salesman Problem

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

Algorithm for Traveling Salesman Problem

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

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:

kindsonthegenius

You might also like, introduction to vehicle routing with python.

  • Interview Problems on DP
  • Practice DP
  • Tutorial on Dynamic Programming
  • Optimal Substructure
  • Overlapping Subproblem
  • Memoization
  • Tabulation vs Memoization
  • 0/1 Knapsack
  • Unbounded Knapsack
  • Coin Change
  • Egg Dropping Puzzle
  • Matrix Chain Multiplication
  • Palindrome Partitioning
  • DP on Arrays
  • DP with Bitmasking
  • DP on Trees
  • DP on Graph

Related Articles

  • Solve Coding Problems
  • Dynamic Programming
  • What is memoization? A Complete tutorial
  • Dynamic Programming (DP) Tutorial with Problems
  • 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

  • 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. 

Euler1

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  

Please Login to comment...

  • lokeshpotta20
  • serjeelranjan
  • sagartomar9927
  • tapeshdua420
  • akashcherukuri007
  • akshaytripathi19410

Improve your Coding Skills with Practice

 alt=

Python and the Travelling Salesman Problem

Python and the Travelling Salesman Problem image

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

secure.food

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 .

travelling-salesman-problem

Here are 250 public repositories matching this topic..., guofei9987 / scikit-opt.

Genetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Ant Colony Optimization Algorithm,Immune Algorithm, Artificial Fish Swarm Algorithm, Differential Evolution and TSP(Traveling salesman)

  • Updated Feb 17, 2024

N-Wouda / ALNS

Adaptive large neighbourhood search (and more!) in Python.

  • Updated Oct 31, 2023

chaitjo / graph-convnet-tsp

Code for the paper 'An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem' (INFORMS Annual Meeting Session 2019)

  • Updated Feb 10, 2022

fikisipi / elkai

elkai is a Python library for solving travelling salesman problems (TSP) based on LKH 3

  • Updated May 9, 2023

afourmy / pyTSP

A 2D/3D visualization of the Traveling Salesman Problem main heuristics

  • Updated Oct 10, 2018

tanmoyie / Operations-Research-Theory

Some lecture notes of Operations Research (usually taught in Junior year of BS) can be found in this repository along with some Python programming codes to solve numerous problems of Optimization including Travelling Salesman, Minimum Spanning Tree and so on.

  • Updated Apr 10, 2019

rhgrant10 / acopy

A Python implementation of the Ant Colony Optimization Meta-Heuristic

  • Updated Dec 26, 2022

PyVRP / VRPLIB

Python package to read and write vehicle routing problem instances.

  • Updated Feb 16, 2024

rameziophobia / Travelling_Salesman_Optimization

Python implementation for TSP using Genetic Algorithms, Simulated Annealing, PSO (Particle Swarm Optimization), Dynamic Programming, Brute Force, Greedy and Divide and Conquer

  • Updated Jun 13, 2023

diogomatoschaves / geneal

A genetic algorithm implementation in python

  • Updated Feb 22, 2024

jedrazb / python-tsp-simulated-annealing

Visualisation of Simulated Annealing algorithm to solve TSP

  • Updated May 5, 2019

lccasagrande / TSP-GA

A Genetic Algorithm in Python for the Travelling Salesman Problem

  • Updated Feb 10, 2023

chenmingxiang110 / tsp_solver

Solving tsp (travel sales problem) using ruin & recreate method.

  • Updated Jun 19, 2021

paulorocosta / learning-2opt-drl

Learning 2-opt Heuristics for the TSP via Deep Reinforcement Learning

  • Updated Oct 20, 2020

mahdims / Branch-and-price-

This is my implementation of a branch and price algorithm to solve the humanitarian aid distribution problem. This problem is a VRP with a specific objective function

lstolcman / HMO-project

Solver for Capacitance Vehicle Routing Problem - School bus routing problem with bus stop selection

  • Updated Jan 23, 2018

henry-yeh / GLOP

[AAAI 2024] GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time

  • Updated Dec 20, 2023

CarlossShi / tsp-meta-heuristic

Python implementation of Tabu Search (TB), Genetic Algorithm (GA), and Simulated Annealing (SA) solving Travelling Salesman Problem (TSP). Term project of Intelligent Optimization Methods, UCAS course 070105M05002H. 禁忌搜索, 遗传算法, 模拟退火解旅行商问题的Python实现. 中国科学院大学现代智能优化方法大作业.

  • Updated Sep 2, 2022

viktor-platform / sample-travelling-salesman

  • Updated Jun 28, 2023

ganyariya / MTSP_ACO

multi traveling salesman problem with ant colony optimization

  • Updated Jun 22, 2022

Improve this page

Add a description, image, and links to the travelling-salesman-problem topic page so that developers can more easily learn about it.

Curate this topic

Add this topic to your repo

To associate your repository with the travelling-salesman-problem topic, visit your repo's landing page and select "manage topics."

IMAGES

  1. Python Simulated Annealing for Travelling Salesman Problem

    travelling salesman problem python solution

  2. Python Traveling Salesman Problem 03 Generate Tour Awal

    travelling salesman problem python solution

  3. Solving Travelling Salesman (TSP) Using 2-Opt Algorithm in Python

    travelling salesman problem python solution

  4. Travelling Salesman Problem Python Solution

    travelling salesman problem python solution

  5. Travelling Sales Man problem/python program for travelling salesman

    travelling salesman problem python solution

  6. Traveling salesman problem (TSP) implementation with python code

    travelling salesman problem python solution

VIDEO

  1. Traveling Salesman Problem + Python + Nearest Neighbor

  2. pyevolve evolutionary algorithms

  3. Traveling Salesman Problem + Python + Simulated Annealing

  4. Traveling Salesman Problem| NP- Class Problem

  5. maximize the profit as the salesman #leetcodechallenge #leetcode

  6. PYTHON PROGRAMMING ON CUSTOMER RELATIONSHIP MANAGEMENT

COMMENTS

  1. Traveling Salesman Problem (TSP) Implementation

    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.

  2. Solving Geographic Travelling Salesman Problems using Python

    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.

  3. Traveling Salesperson Problem

    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...

  4. Travelling Salesman Problem: Python, C++ Algorithm

    Example of TSP Different Solutions to Travelling Salesman Problem Algorithm for Traveling Salesman Problem Implementation in C/C++ Implementation in Python Academic Solutions to TSP Application of Traveling Salesman Problem Complexity Analysis of TSP Example of TSP

  5. python

    How do I solve the 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:

  6. Solving Travelling Salesperson Problems with Python

    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.

  7. Solving the Travelling Salesman Problem (TSP) with Python

    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.

  8. Travelling Salesman Problem using Dynamic Programming

    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!)

  9. Python and the Travelling Salesman Problem

    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 set of libraries and packagesess of creating a Python program to solve the TSP. Step 1: Importing the Required Libraries

  10. How to Solve Traveling Salesman Problem

    I aimed to solve this problem with the following methods: dynamic programming, simulated annealing, and 2-opt. First, let me explain TSP briefly. Artificial Intelligence: Unorthodox Lessons: How to Gain Insight and Build Innovative Solutions

  11. Model and solution of the Traveling Salesman Problem with Python and

    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...

  12. traveling-salesman-problem · GitHub Topics · GitHub

    SonnyFixit / Travelling_salesman_problem. This code implements a genetic algorithm for solving the Traveling Salesman Problem (TSP) on a set of cities from a distance matrix, utilizing techniques such as tournament selection, PMX crossover, inversion and exchange mutations, and elitism to optimize the route and minimize total distance.

  13. travelling-salesman-problem · GitHub Topics · GitHub

    To associate your repository with the travelling-salesman-problem topic, visit your repo's landing page and select "manage topics." GitHub is where people build software. More than 100 million people use GitHub to discover, fork, and contribute to over 420 million projects.

  14. Evolution of a salesman: A complete genetic algorithm tutorial for Python

    31 Drawing inspiration from natural selection, genetic algorithms (GA) are a fascinating approach to solving search and optimization problems. While much has been written about GA (see: here and here ), little has been done to show a step-by-step implementation of a GA in Python for more sophisticated problems. That's where this tutorial comes in!

  15. The Travelling Salesman Problem

    The problem. This is a common setup of the Travelling Salesman Problem (or TSP ). The Travelling Salesman Problem (TSP) is a classic optimization problem that has been around for centuries. At its ...

  16. Traveling Salesman Problem: Branch and Bound Solution

    The problem involves determining the sequence in which the cities should be visited by a salesperson so that the resulting trip covers the shortest possible distance and each city is visited exactly once. Solution of a traveling salesman problem: the black line shows the shortest possible loop that connects every red dot. Source: Wikipedia.

  17. Solving the Traveling Salesman Problem using PuLP in Python

    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...

  18. Implementing, Solving, and Visualizing the Traveling Salesman Problem

    Photo by John Matychuk on Unsplash. 👁️ This is article #3 of the series covering the project "An Intelligent Decision Support System for Tourism in Python". I encourage you to check it out to get a general overview of the whole project. If you're only interested in how to implement a model of the TSP in Python, you're still at the right place: this article is self-contained, and I ...

  19. Traveling Salesman Problem (TSP) using Genetic Algorithm (Python)

    Traveling Salesman Problem. For decades, the Traveling Salesman Problem (TSP) has been an intriguing challenge for mathematicians, computer scientists, and operations researchers.

  20. Python: Genetic Algorithms and the Traveling Salesman Problem

    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 ...

  21. Solving the Travelling Salesman Problem for Germany using NetworkX in

    Solving the Travelling Salesman Problem for Germany using NetworkX in Python Discovering the shortest route to travel across the capital cities of 16 federal states of Germany while visiting each city once using the Christofides algorithm. Himalaya Bir Shrestha · Follow Published in Towards Data Science · 12 min read · Jun 20, 2022 3