multiple travelling salesman problem python

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

Navigation Menu

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

Library to solve Traveling Salesperson Problems with pure Python code

fillipe-gsm/python-tsp

Folders and files, repository files navigation, python tsp solver.

python-tsp is a library written in pure Python for solving typical Traveling Salesperson Problems (TSP). It can work with symmetric and asymmetric versions.

Installation

Regular tsp problem.

Suppose we wish to find a Hamiltonian path with least cost for the following problem:

We can find an optimal path using a Dynamic Programming method with:

The solution will be [0, 1, 3, 2] , with total distance 17.

There are also heuristic-based approaches to solve the same problem. For instance, to use a local search method:

In this case there is generally no guarantee of optimality, but in this small instance the answer is normally a permutation with total distance 17 as well (notice in this case there are many permutations with the same optimal distance).

You can check here to see the list of available solvers .

Keep in mind that, by definition, the route always starts and finishes at node 0 (a closed path). So, in the previous example, after node 2 we go back to 0.

Open TSP problem

If your problem is of the "open" type, i.e., it is not required to go back to the origin, you can "trick" the solvers by setting all elements of the first column of the distance matrix to zero:

and we obtain [0, 2, 3, 1] , with distance 12. Keep in mind that we still start and end at 0, but since the distance from everyone to 0 is null, in practice it is the same as stopping at node 1.

Notice that in this case the distance matrix is actually asymmetric, but the methods here are applicable as well.

Computing a distance matrix

The previous examples assumed you already had a distance matrix. If that is not the case, the distances module has prepared some functions to compute an Euclidean distance matrix, a Great Circle Distance, street distances (via OSRM) and support for TSPLIB-type files. Check the docs folder for some examples.

A more intricate example

Let us attempt to solve the a280.tsp TSPLIB file. It has 280 nodes, so an exact approach may take too long. Hence, let us start with a Local Search (LS) solver:

When calling solve_tsp_local_search like this, we are starting with a random permutation, using the 2-opt scheme as neighborhood, and running it until a local optimum is obtained. Check the solvers documentation for more information.

In my specific run, I obtained a permutation with total distance 3064. The actual best solution for this instance is 2579, so our solution has a 18.8% gap. Remember this solver is a heuristic, and thus it has no business in finding the actual optimum. Moreover, you can get different results trying distinct perturbation schemes and starting points.

Since the local search solver only obtains local minima, maybe we can get more lucky with a metaheuristic such as the Simulated Annealing (SA):

In my execution, I got a 2830 as distance, representing a 9.7% gap, a great improvement over the local search. The SA input parameters are basically the same as the LS, but you can check the solvers documentation for more details as well.

If you are familiarized with metaheuristics, you would know that the SA does not guarantee a local minimum, despite its solution being better than the LS in this case. Thus, maybe we can squeeze some improvement by running a local search starting with its returned solution:

So, that was o.k., nothing groundbreaking, but a nice combo to try in some situations. Nevertheless, if we change the perturbation scheme to, say, PS3:

and there we go, a distance of 2746 or a 6.5% gap of the optimum. Notice we set the x_0 to the permutation returned by the SA in the last run.

Check again the solvers documentation to get an idea of these perturbation schemes.

In this case, PS3 and PS6 have larger neighborhood sizes, so we may get a better chance of improvement by switching to them in the LS step. Test other schemes and see if you can get different results.

Finally, if you don't feel like fine-tunning the solvers for each problem, a rule of thumb that worked relatively well for me is to run the SA with a 2-opt and follow it by a LS with PS3 or PS6, like

Methods available

See here for a list of available solvers and how to use them.

For developers

The project uses Python Poetry to manage dependencies. Check the website for installation instructions.

After that, clone the repo and install dependencies with poetry install .

Here are the detailed steps that should be followed before making a pull request:

You can also run all of these steps at once with the check-up bash script:

Finally (and of course), make sure all tests pass and you get at least 95% of coverage:

Python version support

To help keeping this library relatively up to date and maintainable but not to a point of becoming bleeding edge, it follows at least the supported version of Debian Stable . New features won't be backported to older versions, but this can be accomplished for bug fixes. Just open an issue in case you find a problem.

Release Notes and Changelog

Releases 0.4.x, release 0.4.1.

Add Lin and Kernighan and Record to Record methods to the list of heuristic solvers. Thanks @luanleonardo for this contribution.

Keep in mind that these solvers are more recent and less tested, so if you experience a problem feel free to open an issue.

Python support: Python >= 3.9

Release 0.4.0

• Add Branch and Bound to the list of exact solvers. Thanks @luanleonardo for this contribution.

Python support: Python >= 3.8.1

Releases 0.3.X

Release 0.3.1.

• Replace heuristic log messages with regular prints. The logs could be compromised with outer level configurations and start to pollute the stdout. Prints are easier to manipulate.

Add a verbose parameter to heuristics to print execution messages in the stdout.

Thanks for @FrickTobias for pointing this issue and providing a fix.

Python support: Python >= 3.7.1

Release 0.3.0

• Add support for street distance matrix calculation via an OSRM server.

Releases 0.2.X

Release 0.2.1.

• Improve TSLIB support by using the TSPLIB95 library .

Python support: Python >= 3.6

Release 0.2.0

• Add distance matrix support for TSPLIB files (symmetric and asymmetric instances);
• Add new neighborhood types for local search based methods: PS4, PS5, PS6 and 2-opt;
• Local Search and Simulated Annealing use 2-opt scheme as default;
• Both local search based methods now respect a maximum processing time if provided;
• The primitive print to display iterations information is replaced by a proper log.

Releases 0.1.X

Release 0.1.2.

• Local search and Simulated Annealing random solution now begins at root node 0 just like the exact methods.

Release 0.1.1

• Improve Python versions support.

Release 0.1.0

• Exact (Brute force and Dynamic Programming);
• Heuristics (Local Search and Simulated Annealing).
• The local search-based algorithms can be run with neighborhoods PS1, PS2 and PS3.

Python support: Python >= 3.8

Contributors

• @FrickTobias
• @luanleonardo

Contributors 4

• Python 99.6%

Multiple Traveling Salesman Problem (mTSP)

The Multiple Traveling Salesman Problem (\(m\)TSP) is a generalization of the Traveling Salesman Problem (TSP) in which more than one salesman is allowed. Given a set of cities, one depot where \(m\) salesmen are located, and a cost metric, the objective of the \(m\)TSP is to determine a tour for each salesman such that the total tour cost is minimized and that each city is visited exactly once by only one salesman.

Problem Statement

The Multiple Traveling Salesman Problem (\(m\)TSP) is a generalization of the Traveling Salesman Problem (TSP) in which more than one salesman is allowed. Given a set of cities, one depot (where \(m\) salesmen are located), and a cost metric, the objective of the \(m\)TSP is to determine a set of routes for \(m\) salesmen so as to minimize the total cost of the \(m\) routes. The cost metric can represent cost, distance, or time. The requirements on the set of routes are:

• All of the routes must start and end at the (same) depot.
• Each city must be visited exactly once by only one salesman.

The \(m\)TSP is a relaxation of the vehicle routing problem (VRP); if the vehicle capacity in the VRP is a sufficiently large value so as not to restrict the vehicle capacity, then the problem is the same as the \(m\)TSP. Therefore, all of the formulations and solution approaches for the VRP are valid for the \(m\)TSP. The \(m\)TSP is a generalization of the TSP; if the value of \(m\) is 1, then the \(m\)TSP problem is the same as the TSP. Therefore, all of the formulations and solution approaches for the \(m\)TSP are valid for the TSP.

Bektas (2006) lists a number of variations on the \(m\)TSP.

• Multiple depots : Instead of one depot, the multi-depot \(m\)TSP has a set of depots, with \(m_j\) salesmen at each depot \(j\). In the fixed destination version, a salesman returns to the same depot from which he started. In the non-fixed destination version, a salesman does not need to return to the same depot from which he started but the same number of salesmen must return as started from a particular depot. The multi-depot \(m\)TSP is important in robotic applications involving ground and aerial vehicles. For example, see Oberlin et al. (2009).
• Specifications on the number of salesmen : The number of salesmen may be a fixed number \(m\), or the number of salesmen may be determined by the solution but bounded by an upper bound \(m\).
• Fixed charges : When the number of salesmen is not fixed, there may be a fixed cost associated with activating a salesman. In the fixed charge version of the \(m\)TSP, the overall cost to minimize includes the fixed charges for the salesmen plus the costs for the tours.
• Time windows : As with the TSP and the VRP, there is a variation of the \(m\)TSP with time windows. Associated with each node is a time window during which the node must be visited by a tour. The \(m\)TSPTW has many applications, such as school bus routing and airline scheduling.

Mathematical Formulation

Here we present an assignment-based integer programming formulation for the \(m\)TSP.

Consider a graph \(G=(V,A)\), where \(V\) is the set of \(n\) nodes, and \(A\) is the set of edges. Associated with each edge \((i,j) \in A\) is a cost (or distance) \(c_{ij}\). We assume that the depot is node 1 and there are \(m\) salesmen at the depot. We define a binary variable \(x_{ij}\) for each edge \((i,j) \in A\); \(x_{ij}\) takes the value 1 if edge \((i,j)\) is included in a tour and \(x_{ij}\) takes the value 0 otherwise. For the subtour elimination constraints, we define an integer variable \(u_i\) to denote the position of node \(i\) in a tour, and we define a value \(p\) to be the maximum number of nodes that can be visited by any salesman.

Objective Minimize \( \sum_{(i,j) \in A} c_{ij} x_{ij}\)

Constraints Ensure that exactly \(m\) salesmen depart from node 1 \(\sum_{j \in V: (1,j) \in A} x_{1j} = m\)

Ensure that exactly \(m\) salesmen return to node 1 \(\sum_{j \in V: (j,1) \in A} x_{j1} = m\)

Ensure that exactly one tour enters each node \(\sum_{i \in V: (i,j) \in A} x_{ij} = 1, \forall j \in V\)

Ensure that exactly one tour exits each node \(\sum_{j \in V: (i,j) \in A} x_{ij} = 1, \forall i \in V\)

Include subtour elimination constraints (Miller-Tucker-Zemlin) \(u_i – u_j + p \cdot x_{ij} \leq p-1, \forall 2 \leq i \neq j \leq n\)

The literature includes a number of alternative formulations. Some of the alternatives to the two-index variable, assignment-based formulation are a two-index variable formulation with the original subtour elimination constraints (see Laporte and Nobert, 1980), a three-index variable formulation (see Bektas, 2006), and a \(k\)-degree center tree-based formulation (see Christofides et al., 1981 and Laporte, 1992).

To solve this integer linear programming problem, we can use one of the NEOS Server solvers in the Mixed Integer Linear Programming (MILP) category. Each MILP solver has one or more input formats that it accepts.

Click here for a GAMS model for the bayg29 instance from the TSPLIB. The formulation was provided by Erwin Kalvelagen in a blog post here .

If we submit this model to FICO-Xpress with a CPU time limit of 1 hour, we obtain a solution with a total cost of 2176 (gap of 4.3%) and the following tours:

• Tour 1: i13 – i4 – i10 – i20 – i2 – i13 cost = 60 + 39 + 25 + 49 + 87 = 260
• Tour 2: i13 – i18 – i14 – i17 – i22 – i11 – i15 – i13 cost = 128 + 32 + 51 + 47 + 63 + 68 + 86 = 475
• Tour 3: i13 – i24 – i8 – i28 – i12 – i6 – i1 – i13 cost = 56 + 48 + 64 + 71 + 46 + 60 + 82 = 427
• Tour 4: i13 – i29 – i3 – i26 – i9 – i5 – i21 – i13 cost =160 + 60 + 78 + 57 + 42 + 50 + 82 = 529
• Tour 5: i13 – i19 – i25 – i7 – i23 – i27 – i16 – i13 cost = 71 + 52 + 72 + 111 + 74 + 48 + 57 = 485
• Bektas, T. 2006. The multiple traveling salesman problem: an overview of formulations and solution procedures. OMEGA: The International Journal of Management Science 34 (3), 209-219.
• Christofides, N., A. Mingozzi, and P. Toth. 1981. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Mathematical Programming 20 , 255-282.
• Laporte, G. 1992. The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research 59 , 345-358.
• Laporte, G. and Y. Nobert. 1980. A cutting planes algorithm for the \(m\)-salesmen problem. Journal of the Operational Research Society 31 , 1017-1023.
• Oberlin, P., S. Rathinam, and S. Darbha. 2009. A transformation for a heterogeneous, multi-depot, multiple traveling salesman problem. In Proceedings of the American Control Conference , 1292-1297, St. Louis, June 10 – 12, 2009.

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures
• Graph Data Structure And Algorithms
• Introduction to Graphs - Data Structure and Algorithm Tutorials
• Graph and its representations
• Types of Graphs with Examples
• Basic Properties of a Graph
• Applications, Advantages and Disadvantages of Graph
• Transpose graph
• Difference Between Graph and Tree

BFS and DFS on Graph

• Breadth First Search or BFS for a Graph
• Depth First Search or DFS for a Graph
• Applications, Advantages and Disadvantages of Depth First Search (DFS)
• Applications, Advantages and Disadvantages of Breadth First Search (BFS)
• Iterative Depth First Traversal of Graph
• BFS for Disconnected Graph
• Transitive Closure of a Graph using DFS
• Difference between BFS and DFS

Cycle in a Graph

• Detect Cycle in a Directed Graph
• Detect cycle in an undirected graph
• Detect Cycle in a directed graph using colors
• Detect a negative cycle in a Graph | (Bellman Ford)
• Cycles of length n in an undirected and connected graph
• Detecting negative cycle using Floyd Warshall
• Clone a Directed Acyclic Graph

Shortest Paths in Graph

• How to find Shortest Paths from Source to all Vertices using Dijkstra's Algorithm
• Bellman–Ford Algorithm
• Floyd Warshall Algorithm
• Johnson's algorithm for All-pairs shortest paths
• Shortest Path in Directed Acyclic Graph
• Multistage Graph (Shortest Path)
• Shortest path in an unweighted graph
• Karp's minimum mean (or average) weight cycle algorithm
• 0-1 BFS (Shortest Path in a Binary Weight Graph)
• Find minimum weight cycle in an undirected graph

Minimum Spanning Tree in Graph

• Kruskal’s Minimum Spanning Tree (MST) Algorithm
• Difference between Prim's and Kruskal's algorithm for MST
• Applications of Minimum Spanning Tree
• Total number of Spanning Trees in a Graph
• Minimum Product Spanning Tree
• Reverse Delete Algorithm for Minimum Spanning Tree

Topological Sorting in Graph

• Topological Sorting
• All Topological Sorts of a Directed Acyclic Graph
• Kahn's algorithm for Topological Sorting
• Maximum edges that can be added to DAG so that it remains DAG
• Longest Path in a Directed Acyclic Graph
• Topological Sort of a graph using departure time of vertex

Connectivity of Graph

• Articulation Points (or Cut Vertices) in a Graph
• Biconnected Components
• Bridges in a graph
• Eulerian path and circuit for undirected graph
• Fleury's Algorithm for printing Eulerian Path or Circuit
• Strongly Connected Components
• Count all possible walks from a source to a destination with exactly k edges
• Euler Circuit in a Directed Graph
• Word Ladder (Length of shortest chain to reach a target word)
• Find if an array of strings can be chained to form a circle | Set 1
• Tarjan's Algorithm to find Strongly Connected Components
• Paths to travel each nodes using each edge (Seven Bridges of Königsberg)
• Dynamic Connectivity | Set 1 (Incremental)

Maximum flow in a Graph

• Max Flow Problem Introduction
• Ford-Fulkerson Algorithm for Maximum Flow Problem
• Find maximum number of edge disjoint paths between two vertices
• Find minimum s-t cut in a flow network
• Maximum Bipartite Matching
• Channel Assignment Problem
• Introduction to Push Relabel Algorithm
• Introduction and implementation of Karger's algorithm for Minimum Cut
• Dinic's algorithm for Maximum Flow

Some must do problems on Graph

• Find size of the largest region in Boolean Matrix
• Count number of trees in a forest
• A Peterson Graph Problem
• Clone an Undirected Graph
• Introduction to Graph Coloring

Traveling Salesman Problem (TSP) Implementation

• Introduction and Approximate Solution for Vertex Cover Problem
• Erdos Renyl Model (for generating Random Graphs)
• Chinese Postman or Route Inspection | Set 1 (introduction)
• Hierholzer's Algorithm for directed graph
• Boggle (Find all possible words in a board of characters) | Set 1
• Hopcroft–Karp Algorithm for Maximum Matching | Set 1 (Introduction)
• Construct a graph from given degrees of all vertices
• Determine whether a universal sink exists in a directed graph
• Number of sink nodes in a graph
• Two Clique Problem (Check if Graph can be divided in two Cliques)

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. 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 known solution for this problem.   

Examples: 

In this post, the implementation of a simple solution is discussed.

• Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider any point as a starting point.
• Generate all (n-1)! permutations of cities.
• Calculate the cost of every permutation and keep track of the minimum cost permutation.
• Return the permutation with minimum cost.

Below is the implementation of the above idea 

Time complexity:  O(n!) where n is the number of vertices in the graph. This is because the algorithm uses the next_permutation function which generates all the possible permutations of the vertex set.  Auxiliary Space: O(n) as we are using a vector to store all the vertices.

Please Login to comment...

Similar reads.

• NP Complete

Improve your Coding Skills with Practice

What kind of Experience do you want to share?