travelling salesperson problem

Reset password New user? Sign up

Existing user? Log in

Traveling Salesperson Problem

Already have an account? Log in here.

A salesperson needs to visit a set of cities to sell their goods. They know how many cities they need to go to and the distances between each city. In what order should the salesperson visit each city exactly once so that they minimize their travel time and so that they end their journey in their city of origin?

The traveling salesperson problem is an extremely old problem in computer science that is an extension of the Hamiltonian Circuit Problem . It has important implications in complexity theory and the P versus NP problem because it is an NP-Complete problem . This means that a solution to this problem cannot be found in polynomial time (it takes superpolynomial time to compute an answer). In other words, as the number of vertices increases linearly, the computation time to solve the problem increases exponentially.

The following image is a simple example of a network of cities connected by edges of a specific distance. The origin city is also marked.

Network of cities

Here is the solution for that network, it has a distance traveled of only 14. Any other path that the salesman can takes will result in a path length that is more than 14.

Relationship to Graphs

Special kinds of tsp, importance for p vs np, applications.

The traveling salesperson problem can be modeled as a graph . Specifically, it is typical a directed, weighted graph. Each city acts as a vertex and each path between cities is an edge. Instead of distances, each edge has a weight associated with it. In this model, the goal of the traveling salesperson problem can be defined as finding a path that visits every vertex, returns to the original vertex, and minimizes total weight.

To that end, many graph algorithms can be used on this model. Search algorithms like breadth-first search (BFS) , depth-first search (DFS) , and Dijkstra's shortest path algorithm can certainly be used, however, they do not take into consideration that fact that every vertex must be visited.

The Traveling Salesperson Problem (TSP), an NP-Complete problem, is notoriously complicated to solve. That is because the greedy approach is so computational intensive. The greedy approach to solving this problem would be to try every single possible path and see which one is the fastest. Try this conceptual question to see if you have a grasp for how hard it is to solve.

For a fully connected map with $n$ cities, how many total paths are possible for the traveling salesperson? Show Answer There are (n-1)! total paths the salesperson can take. The computation needed to solve this problem in this way grows far too quickly to be a reasonable solution. If this map has only 5 cities, there are $4!$, or 24, paths. However, if the size of this map is increased to 20 cities, there will be $1.22 \cdot 10^{17}$ paths!

The greedy approach to TSP would go like this:

Find all possible paths.
Find the cost of every paths.
Choose the path with the lowest cost.

Another version of a greedy approach might be: At every step in the algorithm, choose the best possible path. This version might go a little quicker, but it's not guaranteed to find the best answer, or an answer at all since it might hit a dead end.

For NP-Hard problems (a subset of NP-Complete problems) like TSP, exact solutions can only be implemented in a reasonable amount of time for small input sizes (maps with few cities). Otherwise, the best approach we can do is provide a heuristic to help the problem move forward in an optimal way. However, these approaches cannot be proven to be optimal because they always have some sort of downside.

Small input sizes

As described, in a previous section , the greedy approach to this problem has a complexity of $O(n!)$. However, there are some approaches that decrease this computation time.

The Held-Karp Algorithm is one of the earliest applications of dynamic programming . Its complexity is much lower than the greedy approach at $O(n^2 2^n)$. Basically what this algorithm says is that every sub path along an optimal path is itself an optimal path. So, computing an optimal path is the same as computing many smaller subpaths and adding them together.

Heuristics are a way of ranking possible next steps in an algorithm in the hopes of cutting down computation time for the entire algorithm. They are often a tradeoff of some attribute - such as completeness, accuracy, or precision - in favor of speed. Heuristics exist for the traveling salesperson problem as well.

The most simple heuristic for this problem is the greedy heuristic. This heuristic simply says, at each step of the network traversal, choose the best next step. In other words, always choose the closest city that you have not yet visited. This heuristic seems like a good one because it is simple and intuitive, and it is even used in practice sometimes, however there are heuristics that are proven to be more effective.

Christofides algorithm is another heuristic. It produces at most 1.5 times the optimal weight for TSP. This algorithm involves finding a minimum spanning tree for the network. Next, it creates matchings for the cities of an odd degree (meaning they have an odd number of edges coming out of them), calculates an eulerian path , and converts back to a TSP path.

Even though it is typically impossible to optimally solve TSP problems, there are cases of TSP problems that can be solved if certain conditions hold.

The metric-TSP is an instance of TSP that satisfies this condition: The distance from city A to city B is less than or equal to the distance from city A to city C plus the distance from city C to city B. Or,

\[distance_{AB} \leq distance_{AC} + distance_{CB}\]

This is a condition that holds in the real world, but it can't always be expected to hold for every TSP problem. But, with this inequality in place, the approximated path will be no more than twice the optimal path. Even better, we can bound the solution to a $3/2$ approximation by using Christofide's Algorithm .

The euclidean-TSP has an even stricter constraint on the TSP input. It states that all cities' edges in the network must obey euclidean distances . Recent advances have shown that approximation algorithms using euclidean minimum spanning trees have reduced the runtime of euclidean-TSP, even though they are also NP-hard. In practice, though, simpler heuristics are still used.

The P versus NP problem is one of the leading questions in modern computer science. It asks whether or not every problem whose solution can be verified in polynomial time by a computer can also be solved in polynomial time by a computer. TSP, for example, cannot be solved in polynomial time (at least that's what is currently theorized). However, TSP can be solved in polynomial time when it is phrased like this: Given a graph and an integer, x, decide if there is a path of length x or less than x . It's easy to see that given a proposed answer to this question, it is simple to check if it is less than or equal to x.

The traveling salesperson problem, like other problems that are NP-Complete, are very important to this debate. That is because if a polynomial time solution can be found to this problems, then $P = NP$. As it stands, most scientists believe that $P \ne NP$.

The traveling salesperson problem has many applications. The obvious ones are in the transportation space. Planning delivery routes or flight patterns, for example, would benefit immensly from breakthroughs is this problem or in the P versus NP problem .

However, this same logic can be applied to many facets of planning as well. In robotics, for instance, planning the order in which to drill holes in a circuit board is a complex task due to the sheer number of holes that must be drawn.

The best and most important application of TSP, however, comes from the fact that it is an NP-Complete problem. That means that its practical applications amount to the applications of any problem that is NP-Complete. So, if there are significant breakthroughs for TSP, that means that those exact same breakthrough can be applied to any problem in the NP-Complete class.

Problem Loading...

Note Loading...

Set Loading...

DSA Tutorial

Linked lists, stacks & queues, hash tables, shortest path, minimum spanning tree, maximum flow, time complexity, dsa reference, dsa examples, dsa the traveling salesman problem.

The Traveling Salesman Problem

The Traveling Salesman Problem states that you are a salesperson and you must visit a number of cities or towns.

Rules : Visit every city only once, then return back to the city you started in.

Goal : Find the shortest possible route.

Except for the Held-Karp algorithm (which is quite advanced and time consuming, ($O(2^n n^2)$), and will not be described here), there is no other way to find the shortest route than to check all possible routes.

This means that the time complexity for solving this problem is $O(n!)$, which means 720 routes needs to be checked for 6 cities, 40,320 routes must be checked for 8 cities, and if you have 10 cities to visit, more than 3.6 million routes must be checked!

Note: "!", or "factorial", is a mathematical operation used in combinatorics to find out how many possible ways something can be done. If there are 4 cities, each city is connected to every other city, and we must visit every city exactly once, there are $4!= 4 \cdot 3 \cdot 2 \cdot 1 = 24$ different routes we can take to visit those cities.

The Traveling Salesman Problem (TSP) is a problem that is interesting to study because it is very practical, but so time consuming to solve, that it becomes nearly impossible to find the shortest route, even in a graph with just 20-30 vertices.

If we had an effective algorithm for solving The Traveling Salesman Problem, the consequences would be very big in many sectors, like for example chip design, vehicle routing, telecommunications, and urban planning.

Checking All Routes to Solve The Traveling Salesman Problem

To find the optimal solution to The Traveling Salesman Problem, we will check all possible routes, and every time we find a shorter route, we will store it, so that in the end we will have the shortest route.

Good: Finds the overall shortest route.

Bad: Requires an awful lot of calculation, especially for a large amount of cities, which means it is very time consuming.

How it works:

Check the length of every possible route, one route at a time.
Is the current route shorter than the shortest route found so far? If so, store the new shortest route.
After checking all routes, the stored route is the shortest one.

Such a way of finding the solution to a problem is called brute force .

Brute force is not really an algorithm, it just means finding the solution by checking all possibilities, usually because of a lack of a better way to do it.

Speed: {{ inpVal }}

Finding the shortest route in The Traveling Salesman Problem by checking all routes (brute force).

Progress: {{progress}}%

n = {{vertices}} cities

{{vertices}}!={{posRoutes}} possible routes

Show every route: {{showCompares}}

The reason why the brute force approach of finding the shortest route (as shown above) is so time consuming is that we are checking all routes, and the number of possible routes increases really fast when the number of cities increases.

Finding the optimal solution to the Traveling Salesman Problem by checking all possible routes (brute force):

Using A Greedy Algorithm to Solve The Traveling Salesman Problem

Since checking every possible route to solve the Traveling Salesman Problem (like we did above) is so incredibly time consuming, we can instead find a short route by just going to the nearest unvisited city in each step, which is much faster.

Good: Finds a solution to the Traveling Salesman Problem much faster than by checking all routes.

Bad: Does not find the overall shortest route, it just finds a route that is much shorter than an average random route.

Visit every city.
The next city to visit is always the nearest of the unvisited cities from the city you are currently in.
After visiting all cities, go back to the city you started in.

This way of finding an approximation to the shortest route in the Traveling Salesman Problem, by just going to the nearest unvisited city in each step, is called a greedy algorithm .

Finding an approximation to the shortest route in The Traveling Salesman Problem by always going to the nearest unvisited neighbor (greedy algorithm).

As you can see by running this simulation a few times, the routes that are found are not completely unreasonable. Except for a few times when the lines cross perhaps, especially towards the end of the algorithm, the resulting route is a lot shorter than we would get by choosing the next city at random.

Finding a near-optimal solution to the Traveling Salesman Problem using the nearest-neighbor algorithm (greedy):

Time Complexity for Solving The Traveling Salesman Problem

To get a near-optimal solution fast, we can use a greedy algorithm that just goes to the nearest unvisited city in each step, like in the second simulation on this page.

Solving The Traveling Salesman Problem in a greedy way like that, means that at each step, the distances from the current city to all other unvisited cities are compared, and that gives us a time complexity of $O(n^2) $.

But finding the shortest route of them all requires a lot more operations, and the time complexity for that is $O(n!)$, like mentioned earlier, which means that for 4 cities, there are 4! possible routes, which is the same as $4 \cdot 3 \cdot 2 \cdot 1 = 24$. And for just 12 cities for example, there are $12! = 12 \cdot 11 \cdot 10 \cdot \; ... \; \cdot 2 \cdot 1 = 479,001,600$ possible routes!

See the time complexity for the greedy algorithm $O(n^2)$, versus the time complexity for finding the shortest route by comparing all routes $O(n!)$, in the image below.

Time complexity for checking all routes versus running a greedy algorithm and finding a near-optimal solution instead.

But there are two things we can do to reduce the number of routes we need to check.

In the Traveling Salesman Problem, the route starts and ends in the same place, which makes a cycle. This means that the length of the shortest route will be the same no matter which city we start in. That is why we have chosen a fixed city to start in for the simulation above, and that reduces the number of possible routes from $n!$ to $(n-1)!$.

Also, because these routes go in cycles, a route has the same distance if we go in one direction or the other, so we actually just need to check the distance of half of the routes, because the other half will just be the same routes in the opposite direction, so the number of routes we need to check is actually $ \frac{(n-1)!}{2}$.

But even if we can reduce the number of routes we need to check to $ \frac{(n-1)!}{2}$, the time complexity is still $ O(n!)$, because for very big $n$, reducing $n$ by one and dividing by 2 does not make a significant change in how the time complexity grows when $n$ is increased.

To better understand how time complexity works, go to this page .

Actual Traveling Salesman Problems Are More Complex

The edge weight in a graph in this context of The Traveling Salesman Problem tells us how hard it is to go from one point to another, and it is the total edge weight of a route we want to minimize.

So far on this page, the edge weight has been the distance in a straight line between two points. And that makes it much easier to explain the Traveling Salesman Problem, and to display it.

But in the real world there are many other things that affects the edge weight:

Obstacles: When moving from one place to another, we normally try to avoid obstacles like trees, rivers, houses for example. This means it is longer and takes more time to go from A to B, and the edge weight value needs to be increased to factor that in, because it is not a straight line anymore.
Transportation Networks: We usually follow a road or use public transport systems when traveling, and that also affects how hard it is to go (or send a package) from one place to another.
Traffic Conditions: Travel congestion also affects the travel time, so that should also be reflected in the edge weight value.
Legal and Political Boundaries: Crossing border for example, might make one route harder to choose than another, which means the shortest straight line route might be slower, or more costly.
Economic Factors: Using fuel, using the time of employees, maintaining vehicles, all these things cost money and should also be factored into the edge weights.

As you can see, just using the straight line distances as the edge weights, might be too simple compared to the real problem. And solving the Traveling Salesman Problem for such a simplified problem model would probably give us a solution that is not optimal in a practical sense.

It is not easy to visualize a Traveling Salesman Problem when the edge length is not just the straight line distance between two points anymore, but the computer handles that very well.

COLOR PICKER

Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail: [email protected]

Report Error

If you want to report an error, or if you want to make a suggestion, send us an e-mail: [email protected]

Traveling salesman problem

This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Traveling_salesman_problems

Author: Jessica Yu (ChE 345 Spring 2014)

Steward: Dajun Yue, Fengqi You

The traveling salesman problem (TSP) is a widely studied combinatorial optimization problem, which, given a set of cities and a cost to travel from one city to another, seeks to identify the tour that will allow a salesman to visit each city only once, starting and ending in the same city, at the minimum cost. 1

2.1 Graph Theory
2.2 Classifications of the TSP
2.3 Variations of the TSP
3.1 aTSP ILP Formulation
3.2 sTSP ILP Formulation
4.1 Exact algorithms
4.2.1 Tour construction procedures
4.2.2 Tour improvement procedures
5 Applications
7 References

The origins of the traveling salesman problem are obscure; it is mentioned in an 1832 manual for traveling salesman, which included example tours of 45 German cities but gave no mathematical consideration. 2 W. R. Hamilton and Thomas Kirkman devised mathematical formulations of the problem in the 1800s. 2

It is believed that the general form was first studied by Karl Menger in Vienna and Harvard in the 1930s. 2,3

Hassler Whitney, who was working on his Ph.D. research at Harvard when Menger was a visiting lecturer, is believed to have posed the problem of finding the shortest route between the 48 states of the United States during either his 1931-1932 or 1934 seminar talks. 2 There is also uncertainty surrounding the individual who coined the name “traveling salesman problem” for Whitney’s problem. 2

The problem became increasingly popular in the 1950s and 1960s. Notably, George Dantzig, Delber R. Fulkerson, and Selmer M. Johnson at the RAND Corporation in Santa Monica, California solved the 48 state problem by formulating it as a linear programming problem. 2 The methods described in the paper set the foundation for future work in combinatorial optimization, especially highlighting the importance of cutting planes. 2,4

In the early 1970s, the concept of P vs. NP problems created buzz in the theoretical computer science community. In 1972, Richard Karp demonstrated that the Hamiltonian cycle problem was NP-complete, implying that the traveling salesman problem was NP-hard. 4

Increasingly sophisticated codes led to rapid increases in the sizes of the traveling salesman problems solved. Dantzig, Fulkerson, and Johnson had solved a 48 city instance of the problem in 1954. 5 Martin Grötechel more than doubled this 23 years later, solving a 120 city instance in 1977. 5 Enoch Crowder and Manfred W. Padberg again more than doubled this in just 3 years, with a 318 city solution. 5

In 1987, rapid improvements were made, culminating in a 2,392 city solution by Padberg and Giovanni Rinaldi. In the following two decades, David L. Appelgate, Robert E. Bixby, Vasek Chvátal, & William J. Cook led the cutting edge, solving a 7,397 city instance in 1994 up to the current largest solved problem of 24,978 cities in 2004. 5

Description

Graph theory.

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V, E)} be a directed or undirected graph with set of vertices Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} and set of edges Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E = \{(x,y) | x, y \in V\}} . 3,6 Each edge Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e \in E} is assigned a cost Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_e} . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{H}} be the set of all Hamiltonian cycles, a cycle that visits each vertex exactly once, in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} . 6 The traveling salesman problem is to find the tour Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \in \mathbb{H}} such that the sum of the costs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_e} in the tour is minimized.

Suppose graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is a complete graph, where every pair of distinct vertices is connected by a unique edge. 6 Let the set of vertices be Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V = \{v_1, v_2, ..., v_n\}} . The cost matrix is given by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C = (c_{ij})_{n \times n}} where the cost of the edge joining node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_i} to node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_j} , denoted Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_{ij}} , is given in entry Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (i,j)} .

In the context of the traveling salesman problem, the verticies correspond to cities and the edges correspond to the path between those cities. When modeled as a complete graph, paths that do not exist between cities can be modeled as edges of very large cost without loss of generality. 6 Minimizing the sum of the costs for Hamiltonian cycle is equivalent to identifying the shortest path in which each city is visiting only once.

Classifications of the TSP

The TRP can be divided into two classes depending on the nature of the cost matrix. 3,6

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is undirected
Applies when the distance between cities is the same in both directions
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is directed
Applies when there are differences in distances (e.g. one-way streets)

An ATSP can be formulated as an STSP by doubling the number of nodes. 6

Variations of the TSP

Formulation.

Given a set of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} cities enumerated Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0, 1, ..., n-1} to be visited with the distance between each pair of cities Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} is given by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_{ij}} . 1 Introduce decision variables Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{ij}} for each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (i,j)} such that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{ij} = \begin{cases} 1 ~~\text{if city }j\text{ is visited immediately after city }i\\ 0 ~~\text{otherwise} \end{cases} }

The objective function is then given by

To ensure that the result is a valid tour, several contraints must be added. 1,3

There are several other formulations for the subtour elimnation contraint, including circuit packing contraints, MTZ constraints, and network flow constraints.

aTSP ILP Formulation

The integer linear programming formulation for an aTSP is given by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \text{min} & ~~ \sum_i \sum_j c_{ij}y_{ij}\\ \text{s.t} & ~~ \sum_j y_{ij} = 1, ~~ i = 0, 1, ..., n-1 \\ & ~~ \sum_i y_{ij} = 1, ~~ j = 0, 1, ..., n-1 \\ & ~~ \sum_i \sum_j y_{ij} \le |S| - 1 ~~ S \subset V, 2 \le |S| \le n - 2 \\ & ~~ y_{ij} \in \{0,1\}, ~ \forall i,j \in E \\ \end{align} }

sTSP ILP Formulation

The symmetric case is a special case of the asymmetric case and the above formulation is valid. 3, 6 The integer linear programming formulation for an sTSP is given by

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \text{min} & ~~ \sum_i \sum_j c_{ij}y_{ij}\\ \text{s.t} & ~~ \sum_{i < k} y_{ik} + \sum_{j > k} y_{kj} = 2, ~~ k \in V \\ & ~~ \sum_i \sum_j y_{ij} \le |S| - 1 ~~ S \subset V, 3 \le |S| \le n - 3 \\ & ~~ y_{ij} \in \{0,1\} ~ \forall i,j \in E \\ \end{align} }

Exact algorithms

The most direct solution algorithm is a complete enumeration of all possible path to determine the path of least cost. However, for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} cities, the problem is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(n!)} time, and this method is practical only for extremely small values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

Branch-and-bound algorithms are commonly used to find solutions for TSPs. 7 The ILP is first relaxed and solved as an LP using the Simplex method, then feasibility is regained by enumeration of the integer variables. 7

Other exact solution methods include the cutting plane method and branch-and-cut. 8

Heuristic algorithms

Given that the TSP is an NP-hard problem, heuristic algorithms are commonly used to give a approximate solutions that are good, though not necessarily optimal. The algorithms do not guarantee an optimal solution, but gives near-optimal solutions in reasonable computational time. 3 The Held-Karp lower bound can be calculated and used to judge the performance of a heuristic algorithm. 3

There are two general heuristic classifications 7 :

Tour construction procedures where a solution is gradually built by adding a new vertex at each step
Tour improvement procedures where a feasbile solution is improved upon by performing various exchanges

The best methods tend to be composite algorithms that combine these features. 7

Tour construction procedures

Tour improvement procedures, applications.

The importance of the traveling salesman problem is two fold. First its ubiquity as a platform for the study of general methods than can then be applied to a variety of other discrete optimization problems. 5 Second is its diverse range of applications, in fields including mathematics, computer science, genetics, and engineering. 5,6

Suppose a Northwestern student, who lives in Foster-Walker , has to accomplish the following tasks:

Drop off a homework set at Tech
Work out a SPAC
Complete a group project at Annenberg

Distances between buildings can be found using Google Maps. Note that there is particularly strong western wind and walking east takes 1.5 times as long.

It is the middle of winter and the student wants to spend the least possible time walking. Determine the path the student should take in order to minimize walking time, starting and ending at Foster-Walker.

Start with the cost matrix (with altered distances taken into account):

Method 1: Complete Enumeration

All possible paths are considered and the path of least cost is the optimal solution. Note that this method is only feasible given the small size of the problem.

From inspection, we see that Path 4 is the shortest. So, the student should walk 2.28 miles in the following order: Foster-Walker → Annenberg → SPAC → Tech → Foster-Walker

Method 2: Nearest neighbor

Starting from Foster-Walker, the next building is simply the closest building that has not yet been visited. With only four nodes, this can be done by inspection:

Smallest distance is from Foster-Walker is to Annenberg
Smallest distance from Annenberg is to Tech
Smallest distance from Tech is to Annenberg ( creates a subtour, therefore skip )
Next smallest distance from Tech is to Foster-Walker ( creates a subtour, therefore skip )
Next smallest distance from Tech is to SPAC
Smallest distance from SPAC is to Annenberg ( creates a subtour, therefore skip )
Next smallest distance from SPAC is to Tech ( creates a subtour, therefore skip )
Next smallest distance from SPAC is to Foster-Walker

So, the student would walk 2.54 miles in the following order: Foster-Walker → Annenberg → Tech → SPAC → Foster-Walker

Method 3: Greedy

With this method, the shortest paths that do not create a subtour are selected until a complete tour is created.

Smallest distance is Annenberg → Tech
Next smallest is SPAC → Annenberg
Next smallest is Tech → Annenberg ( creates a subtour, therefore skip )
Next smallest is Anneberg → Foster-Walker ( creates a subtour, therefore skip )
Next smallest is SPAC → Tech ( creates a subtour, therefore skip )
Next smallest is Tech → Foster-Walker
Next smallest is Annenberg → SPAC ( creates a subtour, therefore skip )
Next smallest is Foster-Walker → Annenberg ( creates a subtour, therefore skip )
Next smallest is Tech → SPAC ( creates a subtour, therefore skip )
Next smallest is Foster-Walker → Tech ( creates a subtour, therefore skip )
Next smallest is SPAC → Foster-Walker ( creates a subtour, therefore skip )
Next smallest is Foster-Walker → SPAC

So, the student would walk 2.40 miles in the following order: Foster-Walker → SPAC → Annenberg → Tech → Foster-Walker

As we can see in the figure to the right, the heuristic methods did not give the optimal solution. That is not to say that heuristics can never give the optimal solution, just that it is not guaranteed.

Both the optimal and the nearest neighbor algorithms suggest that Annenberg is the optimal first building to visit. However, the optimal solution then goes to SPAC, while both heuristic methods suggest Tech. This is in part due to the large cost of SPAC → Foster-Walker. The heuristic algorithms cannot take this future cost into account, and therefore fall into that local optimum.

We note that the nearest neighbor and greedy algorithms give solutions that are 11.4% and 5.3%, respectively, above the optimal solution. In the scale of this problem, this corresponds to fractions of a mile. We also note that neither heuristic gave the worst case result, Foster-Walker → SPAC → Tech → Annenberg → Foster-Walker.

Only tour building heuristics were used. Combined with a tour improvement algorithm (such as 2-opt or simulated annealing), we imagine that we may be able to locate solutions that are closer to the optimum.

The exact algorithm used was complete enumeration, but we note that this is impractical even for 7 nodes (6! or 720 different possibilities). Commonly, the problem would be formulated and solved as an ILP to obtain exact solutions.

Vanderbei, R. J. (2001). Linear programming: Foundations and extensions (2nd ed.). Boston: Kluwer Academic.
Schrijver, A. (n.d.). On the history of combinatorial optimization (till 1960).
Matai, R., Singh, S., & Lal, M. (2010). Traveling salesman problem: An overview of applications, formulations, and solution approaches. In D. Davendra (Ed.), Traveling Salesman Problem, Theory and Applications . InTech.
Junger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., & Wolsey, L. (Eds.). (2009). 50 years of integer programming, 1958-2008: The early years and state-of-the-art surveys . Heidelberg: Springer.
Cook, W. (2007). History of the TSP. The Traveling Salesman Problem . Retrieved from http://www.math.uwaterloo.ca/tsp/history/index.htm
Punnen, A. P. (2002). The traveling salesman problem: Applications, formulations and variations. In G. Gutin & A. P. Punnen (Eds.), The Traveling Salesman Problem and its Variations . Netherlands: Kluwer Academic Publishers.
Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59 (2), 231–247.
Goyal, S. (n.d.). A suvey on travlling salesman problem.
Pages with math errors
Pages with math render errors

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.

$USA$

Traveling Salesman Problem

The Traveling Salesman Problem, or TSP for short, is one of the most intensively studied problems in computational mathematics. These pages are devoted to the history, applications, and current research of this challenge of finding the shortest route visiting each member of a collection of locations and returning to your starting point.

$travelling salesperson problem$

The work described here is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) and the Department of Combinatorics and Optimization at the University of Waterloo .

Data Structures & Algorithms
DSA - Overview
DSA - Environment Setup
DSA - Algorithms Basics
DSA - Asymptotic Analysis
Data Structures
DSA - Data Structure Basics
DSA - Data Structures and Types
DSA - Array Data Structure
Linked Lists
DSA - Linked List Data Structure
DSA - Doubly Linked List Data Structure
DSA - Circular Linked List Data Structure
Stack & Queue
DSA - Stack Data Structure
DSA - Expression Parsing
DSA - Queue Data Structure
Searching Algorithms
DSA - Searching Algorithms
DSA - Linear Search Algorithm
DSA - Binary Search Algorithm
DSA - Interpolation Search
DSA - Jump Search Algorithm
DSA - Exponential Search
DSA - Fibonacci Search
DSA - Sublist Search
DSA - Hash Table
Sorting Algorithms
DSA - Sorting Algorithms
DSA - Bubble Sort Algorithm
DSA - Insertion Sort Algorithm
DSA - Selection Sort Algorithm
DSA - Merge Sort Algorithm
DSA - Shell Sort Algorithm
DSA - Heap Sort
DSA - Bucket Sort Algorithm
DSA - Counting Sort Algorithm
DSA - Radix Sort Algorithm
DSA - Quick Sort Algorithm
Graph Data Structure
DSA - Graph Data Structure
DSA - Depth First Traversal
DSA - Breadth First Traversal
DSA - Spanning Tree
Tree Data Structure
DSA - Tree Data Structure
DSA - Tree Traversal
DSA - Binary Search Tree
DSA - AVL Tree
DSA - Red Black Trees
DSA - B Trees
DSA - B+ Trees
DSA - Splay Trees
DSA - Tries
DSA - Heap Data Structure
DSA - Recursion Algorithms
DSA - Tower of Hanoi Using Recursion
DSA - Fibonacci Series Using Recursion
Divide and Conquer
DSA - Divide and Conquer
DSA - Max-Min Problem
DSA - Strassen's Matrix Multiplication
DSA - Karatsuba Algorithm
Greedy Algorithms
DSA - Greedy Algorithms
DSA - Travelling Salesman Problem (Greedy Approach)
DSA - Prim's Minimal Spanning Tree
DSA - Kruskal's Minimal Spanning Tree
DSA - Dijkstra's Shortest Path Algorithm
DSA - Map Colouring Algorithm
DSA - Fractional Knapsack Problem
DSA - Job Sequencing with Deadline
DSA - Optimal Merge Pattern Algorithm
Dynamic Programming
DSA - Dynamic Programming
DSA - Matrix Chain Multiplication
DSA - Floyd Warshall Algorithm
DSA - 0-1 Knapsack Problem
DSA - Longest Common Subsequence Algorithm
DSA - Travelling Salesman Problem (Dynamic Approach)
Approximation Algorithms
DSA - Approximation Algorithms
DSA - Vertex Cover Algorithm
DSA - Set Cover Problem
DSA - Travelling Salesman Problem (Approximation Approach)
Randomized Algorithms
DSA - Randomized Algorithms
DSA - Randomized Quick Sort Algorithm
DSA - Karger’s Minimum Cut Algorithm
DSA - Fisher-Yates Shuffle Algorithm
DSA Useful Resources
DSA - Questions and Answers
DSA - Quick Guide
DSA - Useful Resources
DSA - Discussion
Selected Reading
UPSC IAS Exams Notes
Developer's Best Practices
Questions and Answers
Effective Resume Writing
HR Interview Questions
Computer Glossary

Travelling Salesman Problem (Greedy Approach)

Travelling salesperson algorithm.

The travelling salesman problem is a graph computational problem where the salesman needs to visit all cities (represented using nodes in a graph) in a list just once and the distances (represented using edges in the graph) between all these cities are known. The solution that is needed to be found for this problem is the shortest possible route in which the salesman visits all the cities and returns to the origin city.

If you look at the graph below, considering that the salesman starts from the vertex ‘a’, they need to travel through all the remaining vertices b, c, d, e, f and get back to ‘a’ while making sure that the cost taken is minimum.

There are various approaches to find the solution to the travelling salesman problem: naive approach, greedy approach, dynamic programming approach, etc. In this tutorial we will be learning about solving travelling salesman problem using greedy approach.

As the definition for greedy approach states, we need to find the best optimal solution locally to figure out the global optimal solution. The inputs taken by the algorithm are the graph G {V, E}, where V is the set of vertices and E is the set of edges. The shortest path of graph G starting from one vertex returning to the same vertex is obtained as the output.

Travelling salesman problem takes a graph G {V, E} as an input and declare another graph as the output (say G’) which will record the path the salesman is going to take from one node to another.

The algorithm begins by sorting all the edges in the input graph G from the least distance to the largest distance.

The first edge selected is the edge with least distance, and one of the two vertices (say A and B) being the origin node (say A).

Then among the adjacent edges of the node other than the origin node (B), find the least cost edge and add it onto the output graph.

Continue the process with further nodes making sure there are no cycles in the output graph and the path reaches back to the origin node A.

However, if the origin is mentioned in the given problem, then the solution must always start from that node only. Let us look at some example problems to understand this better.

Consider the following graph with six cities and the distances between them −

From the given graph, since the origin is already mentioned, the solution must always start from that node. Among the edges leading from A, A → B has the shortest distance.

Then, B → C has the shortest and only edge between, therefore it is included in the output graph.

There’s only one edge between C → D, therefore it is added to the output graph.

There’s two outward edges from D. Even though, D → B has lower distance than D → E, B is already visited once and it would form a cycle if added to the output graph. Therefore, D → E is added into the output graph.

There’s only one edge from e, that is E → F. Therefore, it is added into the output graph.

Again, even though F → C has lower distance than F → A, F → A is added into the output graph in order to avoid the cycle that would form and C is already visited once.

The shortest path that originates and ends at A is A → B → C → D → E → F → A

The cost of the path is: 16 + 21 + 12 + 15 + 16 + 34 = 114.

Even though, the cost of path could be decreased if it originates from other nodes but the question is not raised with respect to that.

The complete implementation of Travelling Salesman Problem using Greedy Approach is given below −

To Continue Learning Please Login

The Travelling Salesperson Problem

First Online: 15 May 2022

Cite this chapter

Neil Urquhart 6

Part of the book series: Natural Computing Series ((NCS))

412 Accesses

1 Citations

This chapter introduces the Travelling Salesperson Problem (TSP) which underpins almost all other delivery type problems. Within the TSP, a route must be found that visits a set of locations within the shortest possible distance, and each location must be visited once. The TSP has the useful properties of being very easy to understand, whilst presenting a considerable computational challenge to solve as it does not scale up well. If we are to understand more complex problems, then a review of the TSP is a useful starting point. We examine a number of heuristics (such as Nearest Neighbour and 2-opt) which may be used to generate solutions. Through a case study, we discuss the software engineering practicalities of implementing TSP solvers and compare the performance of the heuristics discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Available as PDF
Read on any device
Instant download
Own it forever
Available as EPUB and PDF
Compact, lightweight edition
Dispatched in 3 to 5 business days
Free shipping worldwide - see info
Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

The TSP was originally described as the Travelling Salesman, but many recent publications refer to it as the Travelling Salesperson Problem. For consistency, this book uses the term Salesperson, but many of the cited publications use Salesman.

I very deliberately use the ambiguous term reasonable . What is a reasonable time to a patient user is an eternity to an impatient user. Hardware specifications constantly improve and a reasonable computer of this year may be regarded as underpowered and obsolete by next year.

Bocks, F. 1958. An Algorithm for Solving Travelling-salesman and Related Network Optimisation Problems . Fourteenth National Meeting: Operations Research Society of America.

Google Scholar

Brady, R.M. 1985. Optimization Strategies Gleaned from Biological Evolution. Nature 317 (6040): 804–806. Bandiera_abtest: a Cg_type: Nature Research Journals Number: 6040 Primary_atype: Research Publisher: Nature Publishing Group. https://www.nature.com/articles/317804a0 .

Cook, W. 2012. In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation . Princeton: Princeton University Press.

MATH Google Scholar

Cook, W., D. Applegate, R.E. Bixby, and V. Chvátal. 2020. Concorde TSP Solver. http://www.math.uwaterloo.ca/tsp/concorde.html .

Croes, G.A. 1958. A Method for Solving Traveling-Salesman Problems. Operations Research 6 (6): 791–812.

Article MathSciNet Google Scholar

Cummings, Nigel. 2000. A Brief History of the Travelling Salesman Problem. Inside OR .

Dantzig, G.B., and J.H. Ramser. 1959. The Truck Dispatching Problem. Management Science 6 (1): 80–91. https://doi.org/10.1287/mnsc.6.1.80 .

Dantzig, G., R. Fulkerson, and S. Johnson. 1954. Solution of a Large-Scale Traveling-Salesman Problem. Journal of the Operations Research Society of America 2 (4): 393–410. Publisher: INFORMS. http://www.jstor.org/stable/166695 .

Flood, M.M. 1956. The Traveling-Salesman Problem. Operations Research 4 (1): 61–75.

Freisleben, B., and P. Merz. 1996. New Genetic Local Search Operators for the Traveling Salesman Problem. In Parallel Problem Solving from Nature — PPSN IV , Lecture Notes in Computer Science, ed. H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, 890–899. Heidelberg: Springer.

Johnson, D.S. 1990. Local optimization and the Traveling Salesman Problem. In Automata, Languages and Programming , Lecture Notes in Computer Science, ed. M.S. Paterson, 446–461. Heidelberg: Springer.

Kernighan, B.W., and S. Lin. 1973. Heuristic Solution of a Signal Design Optimization Problem. Bell System Technical Journal 52 (7): 1145–1159.

Article Google Scholar

Knuth, D.E. 1973. The Art of Computer Programming . Boston: Addison-Wesley.

Menger, Karl. 1932. Das botenproblem, Ergebnisse eines Mathematischen Kolloquiums , vol. 2, 11–12. Leipzig: Teubner.

Mukhopadhyay, A., D. Whitley, and R. Tinós. 2021. An Efficient Implementation of Iterative Partial Transcription for the Traveling Salesman Problem. In Proceedings of the Genetic and Evolutionary Computation Conference , GECCO ’21, Association for Computing Machinery, New York, NY, USA, 252–260. https://doi.org/10.1145/3449639.3459368

Varadarajan, S., and D. Whitley. 2021. A Parallel Ensemble Genetic Algorithm for the Traveling Salesman Problem. In Proceedings of the Genetic and Evolutionary Computation Conference , GECCO ’21, Association for Computing Machinery, New York, NY, USA, 636–643. https://doi.org/10.1145/3449639.3459281 .

Varadarajan, S., D. Whitley, and G. Ochoa. 2020. Why Many Travelling Salesman Problem Instances are Easier Than You Think. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference , GECCO ’20, Association for Computing Machinery, New York, NY, USA, 254–262. https://doi.org/10.1145/3377930.3390145 .

Villanueva, J.C. 2018. How Many Atoms Are There in the Universe? Universe Today . https://www.universetoday.com/36302/atoms-in-the-universe/ .

Watson, J., C. Ross, V. Eisele, J. Denton, J. Bins, C. Guerra, D. Whitley, and A. Howe. 1998. The Traveling Salesrep Problem, Edge Assembly Crossover, and 2-opt. In Parallel Problem Solving from Nature - PPSN V , Lecture Notes in Computer Science, ed. A.E. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel, 823–832. Berlin: Springer.

Download references

Author information

Authors and affiliations.

School of Computing, Edinburgh Napier University, Edinburgh, UK

Neil Urquhart

You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Neil Urquhart .

Rights and permissions

Reprints and permissions

Copyright information

About this chapter

Urquhart, N. (2022). The Travelling Salesperson Problem. In: Nature Inspired Optimisation for Delivery Problems. Natural Computing Series. Springer, Cham. https://doi.org/10.1007/978-3-030-98108-2_1

Download citation

DOI : https://doi.org/10.1007/978-3-030-98108-2_1

Published : 15 May 2022

Publisher Name : Springer, Cham

Print ISBN : 978-3-030-98107-5

Online ISBN : 978-3-030-98108-2

eBook Packages : Computer Science Computer Science (R0)

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Publish with us

Policies and ethics

Find a journal
Track your research

school Campus Bookshelves
menu_book Bookshelves
perm_media Learning Objects
login Login
how_to_reg Request Instructor Account
hub Instructor Commons

Margin Size

Download Page (PDF)
Download Full Book (PDF)
Periodic Table
Physics Constants
Scientific Calculator
Reference & Cite
Tools expand_more
Readability

selected template will load here

This action is not available.

6.6: Hamiltonian Circuits and the Traveling Salesman Problem

Last updated
Save as PDF
Page ID 34209

David Lippman
Pierce College via The OpenTextBookStore

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

In the last section, we considered optimizing a walking route for a postal carrier. How is this different than the requirements of a package delivery driver? While the postal carrier needed to walk down every street (edge) to deliver the mail, the package delivery driver instead needs to visit every one of a set of delivery locations. Instead of looking for a circuit that covers every edge once, the package deliverer is interested in a circuit that visits every vertex once.

Hamiltonian Circuits and Paths

A Hamiltonian circuit is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex. A Hamiltonian path also visits every vertex once with no repeats, but does not have to start and end at the same vertex.

Hamiltonian circuits are named for William Rowan Hamilton who studied them in the 1800’s.

One Hamiltonian circuit is shown on the graph below. There are several other Hamiltonian circuits possible on this graph. Notice that the circuit only has to visit every vertex once; it does not need to use every edge.

This circuit could be notated by the sequence of vertices visited, starting and ending at the same vertex: ABFGCDHMLKJEA. Notice that the same circuit could be written in reverse order, or starting and ending at a different vertex.

Unlike with Euler circuits, there is no nice theorem that allows us to instantly determine whether or not a Hamiltonian circuit exists for all graphs.[1]

Does a Hamiltonian path or circuit exist on the graph below?

We can see that once we travel to vertex E there is no way to leave without returning to C, so there is no possibility of a Hamiltonian circuit. If we start at vertex E we can find several Hamiltonian paths, such as ECDAB and ECABD.

With Hamiltonian circuits, our focus will not be on existence, but on the question of optimization; given a graph where the edges have weights, can we find the optimal Hamiltonian circuit; the one with lowest total weight.

To answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches. The first option that might come to mind is to just try all different possible circuits.

Brute Force Algorithm (a.k.a. exhaustive search)

List all possible Hamiltonian circuits
Find the length of each circuit by adding the edge weights
Select the circuit with minimal total weight.

Apply the Brute force algorithm to find the minimum cost Hamiltonian circuit on the graph below.

To apply the Brute force algorithm, we list all possible Hamiltonian circuits and calculate their weight:

$\begin{array}{|l|l|} \hline \textbf { Circuit } & \textbf { Weight } \\ \hline \text { ABCDA } & 4+13+8+1=26 \\ \hline \text { ABDCA } & 4+9+8+2=23 \\ \hline \text { ACBDA } & 2+13+9+1=25 \\ \hline \end{array}$

Note: These are the unique circuits on this graph. All other possible circuits are the reverse of the listed ones or start at a different vertex, but result in the same weights.

From this we can see that the second circuit, ABDCA, is the optimal circuit.

The Brute force algorithm is optimal; it will always produce the Hamiltonian circuit with minimum weight. Is it efficient? To answer that question, we need to consider how many Hamiltonian circuits a graph could have. For simplicity, let’s look at the worst-case possibility, where every vertex is connected to every other vertex. This is called a complete graph.

Suppose we had a complete graph with five vertices like the air travel graph above. From Seattle there are four cities we can visit first. From each of those, there are three choices. From each of those cities, there are two possible cities to visit next. There is then only one choice for the last city before returning home.

This can be shown visually:

Counting the number of routes, we can see there are $4 \cdot 3 \cdot 2 \cdot 1=24$ routes. For six cities there would be $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=120$ routes.

Number of Possible Circuits

For $n$ vertices in a complete graph, there will be $(n-1) !=(n-1)(n-2)(n-3) \cdots 3 \cdot 2 \cdot 1$ routes. Half of these are duplicates in reverse order, so there are $\frac{(n-1) !}{2}$ unique circuits.

The exclamation symbol, !, is read “factorial” and is shorthand for the product shown.

How many circuits would a complete graph with 8 vertices have?

A complete graph with 8 vertices would have $(8-1) !=7 !=7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=5040$ possible Hamiltonian circuits. Half of the circuits are duplicates of other circuits but in reverse order, leaving 2520 unique routes.

While this is a lot, it doesn’t seem unreasonably huge. But consider what happens as the number of cities increase:

$\begin{array}{|l|l|} \hline \textbf { Cities } & \textbf { Unique Hamiltonian Circuits } \\ \hline 9 & 8 ! / 2=20,160 \\ \hline 10 & 9 ! / 2=181,440 \\ \hline 11 & 10 ! / 2=1,814,400 \\ \hline 15 & 14 ! / 2=43,589,145,600 \\ \hline 20 & 19 ! / 2=60,822,550,204,416,000 \\ \hline \end{array}$

As you can see the number of circuits is growing extremely quickly. If a computer looked at one billion circuits a second, it would still take almost two years to examine all the possible circuits with only 20 cities! Certainly Brute Force is not an efficient algorithm.

Unfortunately, no one has yet found an efficient and optimal algorithm to solve the TSP, and it is very unlikely anyone ever will. Since it is not practical to use brute force to solve the problem, we turn instead to heuristic algorithms ; efficient algorithms that give approximate solutions. In other words, heuristic algorithms are fast, but may or may not produce the optimal circuit.

Nearest Neighbor Algorithm (NNA)

Select a starting point.
Move to the nearest unvisited vertex (the edge with smallest weight).
Repeat until the circuit is complete.

Consider our earlier graph, shown to the right.

From D, the nearest neighbor is C, with a weight of 8.

From C, our only option is to move to vertex B, the only unvisited vertex, with a cost of 13.

From B we return to A with a weight of 4.

The resulting circuit is ADCBA with a total weight of $1+8+13+4 = 26$.

We ended up finding the worst circuit in the graph! What happened? Unfortunately, while it is very easy to implement, the NNA is a greedy algorithm, meaning it only looks at the immediate decision without considering the consequences in the future. In this case, following the edge AD forced us to use the very expensive edge BC later.

LA to Chicago: $100
Chicago to Atlanta: $75
Atlanta to Dallas: $85
Dallas to Seattle: $120

Total cost: $450

In this case, nearest neighbor did find the optimal circuit.

Going back to our first example, how could we improve the outcome? One option would be to redo the nearest neighbor algorithm with a different starting point to see if the result changed. Since nearest neighbor is so fast, doing it several times isn’t a big deal.

Repeated Nearest Neighbor Algorithm (RNNA)

Do the Nearest Neighbor Algorithm starting at each vertex
Choose the circuit produced with minimal total weight

Starting at vertex A resulted in a circuit with weight 26.

Starting at vertex B, the nearest neighbor circuit is BADCB with a weight of 4+1+8+13 = 26. This is the same circuit we found starting at vertex A. No better.

Starting at vertex C, the nearest neighbor circuit is CADBC with a weight of 2+1+9+13 = 25. Better!

Starting at vertex D, the nearest neighbor circuit is DACBA. Notice that this is actually the same circuit we found starting at C, just written with a different starting vertex.

The RNNA was able to produce a slightly better circuit with a weight of 25, but still not the optimal circuit in this case. Notice that even though we found the circuit by starting at vertex C, we could still write the circuit starting at A: ADBCA or ACBDA.

Try it Now 5

The table below shows the time, in milliseconds, it takes to send a packet of data between computers on a network. If data needed to be sent in sequence to each computer, then notification needed to come back to the original computer, we would be solving the TSP. The computers are labeled A-F for convenience.

$\begin{array}{|l|l|l|l|l|l|l|} \hline & \mathrm{A} & \mathrm{B} & \mathrm{C} & \mathrm{D} & \mathrm{E} & \mathrm{F} \\ \hline \mathrm{A} & \_ \_ & 44 & 34 & 12 & 40 & 41 \\ \hline \mathrm{B} & 44 & \_ \_ & 31 & 43 & 24 & 50 \\ \hline \mathrm{C} & 34 & 31 & \_ \_ & 20 & 39 & 27 \\ \hline \mathrm{D} & 12 & 43 & 20 & \_ \_ & 11 & 17 \\ \hline \mathrm{E} & 40 & 24 & 39 & 11 & \_ \_ & 42 \\ \hline \mathrm{F} & 41 & 50 & 27 & 17 & 42 & \_ \_ \\ \hline \end{array}$

a. Find the circuit generated by the NNA starting at vertex B.

b. Find the circuit generated by the RNNA.

At each step, we look for the nearest location we haven’t already visited.

From B the nearest computer is E with time 24.

From E, the nearest computer is D with time 11.

From D the nearest is A with time 12.

From A the nearest is C with time 34.

From C, the only computer we haven’t visited is F with time 27

From F, we return back to B with time 50.

The NNA circuit from B is BEDACFB with time 158 milliseconds.

While certainly better than the basic NNA, unfortunately, the RNNA is still greedy and will produce very bad results for some graphs. As an alternative, our next approach will step back and look at the “big picture” – it will select first the edges that are shortest, and then fill in the gaps.

Sorted Edges Algorithm (a.k.a. Cheapest Link Algorithm)

1. Select the cheapest unused edge in the graph.

2. Repeat step 1, adding the cheapest unused edge to the circuit, unless:

a. adding the edge would create a circuit that doesn’t contain all vertices, or

b. adding the edge would give a vertex degree 3.

3. Repeat until a circuit containing all vertices is formed.

Using the four vertex graph from earlier, we can use the Sorted Edges algorithm.

The cheapest edge is AD, with a cost of 1. We highlight that edge to mark it selected.

The next shortest edge is AC, with a weight of 2, so we highlight that edge.

For the third edge, we’d like to add AB, but that would give vertex A degree 3, which is not allowed in a Hamiltonian circuit. The next shortest edge is CD, but that edge would create a circuit ACDA that does not include vertex B, so we reject that edge. The next shortest edge is BD, so we add that edge to the graph.

Notice that the algorithm did not produce the optimal circuit in this case; the optimal circuit is ACDBA with weight 23.

While the Sorted Edge algorithm overcomes some of the shortcomings of NNA, it is still only a heuristic algorithm, and does not guarantee the optimal circuit.

Your teacher’s band, Derivative Work , is doing a bar tour in Oregon. The driving distances are shown below. Plan an efficient route for your teacher to visit all the cities and return to the starting location. Use NNA starting at Portland, and then use Sorted Edges.

\( \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline & & & & & & & & & & \\ & \text { Ashland } & \text { Astoria } & \text { Bend } & \text { Corvallis } & \text { Crater Lake } & \text { Eugene } & \text { Newport } & \text { Portland } & \text { Salem } & \text { Seaside } \\ \hline \text { Ashland } & \_ & 374 & 200 & 223 & 108 & 178 & 252 & 285 & 240 & 356 \\ \hline \text { Astoria } & 374 & \_ & 255 & 166 & 433 & 199 & 135 & 95 & 136 & 17 \\ \hline \text { Bend } & 200 & 255 & \_ & 128 & 277 & 128 & 180 & 160 & 131 & 247 \\ \hline \text { Corvallis } & 223 & 166 & 128 & \_ & 430 & 47 & 52 & 84 & 40 & 155 \\ \hline \text { Crater Lake } & 108 & 433 & 277 & 430 & \_ & 453 & 478 & 344 & 389 & 423 \\ \hline \text { Eugene } & 178 & 199 & 128 & 47 & 453 & \_ & 91 & 110 & 64 & 181 \\ \hline \text { Newport } & 252 & 135 & 180 & 52 & 478 & 91 & \_ & 114 & 83 & 117 \\ \hline \text { Portland } & 285 & 95 & 160 & 84 & 344 & 110 & 114 & \_ & 47 & 78 \\ \hline \text { Salem } & 240 & 136 & 131 & 40 & 389 & 64 & 83 & 47 & \_ & 118 \\ \hline \text { Seaside } & 356 & 17 & 247 & 155 & 423 & 181 & 117 & 78 & 118 & \_ \\ \hline \end{array}\)

Using NNA with a large number of cities, you might find it helpful to mark off the cities as they’re visited to keep from accidently visiting them again. Looking in the row for Portland, the smallest distance is 47, to Salem. Following that idea, our circuit will be:

Using Sorted Edges, you might find it helpful to draw an empty graph, perhaps by drawing vertices in a circular pattern. Adding edges to the graph as you select them will help you visualize any circuits or vertices with degree 3.

We start adding the shortest edges:

The graph after adding these edges is shown to the right. The next shortest edge is from Corvallis to Newport at 52 miles, but adding that edge would give Corvallis degree 3.

Continuing on, we can skip over any edge pair that contains Salem or Corvallis, since they both already have degree 2.

The graph after adding these edges is shown to the right. At this point, we can skip over any edge pair that contains Salem, Seaside, Eugene, Portland, or Corvallis since they already have degree 2.

At this point the only way to complete the circuit is to add:

Crater Lk to Astoria 433 miles

The final circuit, written to start at Portland, is:

Portland, Salem, Corvallis, Eugene, Newport, Bend, Ashland, Crater Lake, Astoria, Seaside, Portland.

Total trip length: 1241 miles.

While better than the NNA route, neither algorithm produced the optimal route. The following route can make the tour in 1069 miles:

Portland, Astoria, Seaside, Newport, Corvallis, Eugene, Ashland, Crater Lake, Bend, Salem, Portland

Try it Now 6

Find the circuit produced by the Sorted Edges algorithm using the graph below.

AB: Add, cost 11

BG: Add, cost 13

AE: Add, cost 14

EC: Skip (degree 3 at E)

FG: Skip (would create a circuit not including C)

BF, BC, AG, AC: Skip (would cause a vertex to have degree 3)

GC: Add, cost 36

CF: Add, cost 37, completes the circuit

Final circuit: ABGCFEA

[1] There are some theorems that can be used in specific circumstances, such as Dirac’s theorem, which says that a Hamiltonian circuit must exist on a graph with n vertices if each vertex has degree n /2 or greater.

12.9 Traveling Salesperson Problem

Learning objectives.

After completing this section, you should be able to:

Distinguish between brute force algorithms and greedy algorithms.
List all distinct Hamilton cycles of a complete graph.
Apply brute force method to solve traveling salesperson applications.
Apply nearest neighbor method to solve traveling salesperson applications.

We looked at Hamilton cycles and paths in the previous sections Hamilton Cycles and Hamilton Paths . In this section, we will analyze Hamilton cycles in complete weighted graphs to find the shortest route to visit a number of locations and return to the starting point. Besides the many routing applications in which we need the shortest distance, there are also applications in which we search for the route that is least expensive or takes the least time. Here are a few less common applications that you can read about on a website set up by the mathematics department at the University of Waterloo in Ontario, Canada:

Design of fiber optic networks
Minimizing fuel expenses for repositioning satellites
Development of semi-conductors for microchips
A technique for mapping mammalian chromosomes in genome sequencing

Before we look at approaches to solving applications like these, let's discuss the two types of algorithms we will use.

Brute Force and Greedy Algorithms

An algorithm is a sequence of steps that can be used to solve a particular problem. We have solved many problems in this chapter, and the procedures that we used were different types of algorithms. In this section, we will use two common types of algorithms, a brute force algorithm and a greedy algorithm . A brute force algorithm begins by listing every possible solution and applying each one until the best solution is found. A greedy algorithm approaches a problem in stages, making the apparent best choice at each stage, then linking the choices together into an overall solution which may or may not be the best solution.

To understand the difference between these two algorithms, consider the tree diagram in Figure 12.187 . Suppose we want to find the path from left to right with the largest total sum. For example, branch A in the tree diagram has a sum of 10 + 2 + 11 + 13 = 36 10 + 2 + 11 + 13 = 36 .

To be certain that you pick the branch with greatest sum, you could list each sum from each of the different branches:

A : 10 + 2 + 11 + 13 = 36 10 + 2 + 11 + 13 = 36

B : 10 + 2 + 11 + 8 = 31 10 + 2 + 11 + 8 = 31

C : 10 + 2 + 15 + 1 = 28 10 + 2 + 15 + 1 = 28

D : 10 + 2 + 15 + 6 = 33 10 + 2 + 15 + 6 = 33

E : 10 + 7 + 3 + 20 = 40 10 + 7 + 3 + 20 = 40

F : 10 + 7 + 3 + 14 = 34 10 + 7 + 3 + 14 = 34

G : 10 + 7 + 4 + 11 = 32 10 + 7 + 4 + 11 = 32

H : 10 + 7 + 4 + 5 = 26 10 + 7 + 4 + 5 = 26

Then we know with certainty that branch E has the greatest sum.

Now suppose that you wanted to find the branch with the highest value, but you only were shown the tree diagram in phases, one step at a time.

After phase 1, you would have chosen the branch with 10 and 7. So far, you are following the same branch. Let’s look at the next phase.

After phase 2, based on the information you have, you will choose the branch with 10, 7 and 4. Now, you are following a different branch than before, but it is the best choice based on the information you have. Let’s look at the last phase.

After phase 3, you will choose branch G which has a sum of 32.

The process of adding the values on each branch and selecting the highest sum is an example of a brute force algorithm because all options were explored in detail. The process of choosing the branch in phases, based on the best choice at each phase is a greedy algorithm. Although a brute force algorithm gives us the ideal solution, it can take a very long time to implement. Imagine a tree diagram with thousands or even millions of branches. It might not be possible to check all the sums. A greedy algorithm, on the other hand, can be completed in a relatively short time, and generally leads to good solutions, but not necessarily the ideal solution.

Example 12.42

Distinguishing between brute force and greedy algorithms.

A cashier rings up a sale for $4.63 cents in U.S. currency. The customer pays with a $5 bill. The cashier would like to give the customer $0.37 in change using the fewest coins possible. The coins that can be used are quarters ($0.25), dimes ($0.10), nickels ($0.05), and pennies ($0.01). The cashier starts by selecting the coin of highest value less than or equal to $0.37, which is a quarter. This leaves $ 0.37 − $ 0.25 = $ 0.12 $ 0.37 − $ 0.25 = $ 0.12 . The cashier selects the coin of highest value less than or equal to $0.12, which is a dime. This leaves $ 0.12 − $ 0.10 = $ 0.02 $ 0.12 − $ 0.10 = $ 0.02 . The cashier selects the coin of highest value less than or equal to $0.02, which is a penny. This leaves $ 0.02 − $ 0.01 = $ 0.01 $ 0.02 − $ 0.01 = $ 0.01 . The cashier selects the coin of highest value less than or equal to $0.01, which is a penny. This leaves no remainder. The cashier used one quarter, one dime, and two pennies, which is four coins. Use this information to answer the following questions.

Is the cashier’s approach an example of a greedy algorithm or a brute force algorithm? Explain how you know.
The cashier’s solution is the best solution. In other words, four is the fewest number of coins possible. Is this consistent with the results of an algorithm of this kind? Explain your reasoning.
The approach the cashier used is an example of a greedy algorithm, because the problem was approached in phases and the best choice was made at each phase. Also, it is not a brute force algorithm, because the cashier did not attempt to list out all possible combinations of coins to reach this conclusion.
Yes, it is consistent. A greedy algorithm does not always yield the best result, but sometimes it does.

Your Turn 12.42

The traveling salesperson problem.

Now let’s focus our attention on the graph theory application known as the traveling salesperson problem (TSP) in which we must find the shortest route to visit a number of locations and return to the starting point.

Recall from Hamilton Cycles , the officer in the U.S. Air Force who is stationed at Vandenberg Air Force base and must drive to visit three other California Air Force bases before returning to Vandenberg. The officer needed to visit each base once. We looked at the weighted graph in Figure 12.192 representing the four U.S. Air Force bases: Vandenberg, Edwards, Los Angeles, and Beal and the distances between them.

Any route that visits each base and returns to the start would be a Hamilton cycle on the graph. If the officer wants to travel the shortest distance, this will correspond to a Hamilton cycle of lowest weight. We saw in Table 12.11 that there are six distinct Hamilton cycles (directed cycles) in a complete graph with four vertices, but some lie on the same cycle (undirected cycle) in the graph.

Since the distance between bases is the same in either direction, it does not matter if the officer travels clockwise or counterclockwise. So, there are really only three possible distances as shown in Figure 12.193 .

The possible distances are:

So, a Hamilton cycle of least weight is V → B → E → L → V (or the reverse direction). The officer should travel from Vandenberg to Beal to Edwards, to Los Angeles, and back to Vandenberg.

Finding Weights of All Hamilton Cycles in Complete Graphs

Notice that we listed all of the Hamilton cycles and found their weights when we solved the TSP about the officer from Vandenberg. This is a skill you will need to practice. To make sure you don't miss any, you can calculate the number of possible Hamilton cycles in a complete graph. It is also helpful to know that half of the directed cycles in a complete graph are the same cycle in reverse direction, so, you only have to calculate half the number of possible weights, and the rest are duplicates.

In a complete graph with n n vertices,

The number of distinct Hamilton cycles is ( n − 1 ) ! ( n − 1 ) ! .
There are at most ( n − 1 ) ! 2 ( n − 1 ) ! 2 different weights of Hamilton cycles.

TIP! When listing all the distinct Hamilton cycles in a complete graph, you can start them all at any vertex you choose. Remember, the cycle a → b → c → a is the same cycle as b → c → a → b so there is no need to list both.

Example 12.43

Calculating possible weights of hamilton cycles.

Suppose you have a complete weighted graph with vertices N, M, O , and P .

Use the formula ( n − 1 ) ! ( n − 1 ) ! to calculate the number of distinct Hamilton cycles in the graph.
Use the formula ( n − 1 ) ! 2 ( n − 1 ) ! 2 to calculate the greatest number of different weights possible for the Hamilton cycles.
Are all of the distinct Hamilton cycles listed here? How do you know? Cycle 1: N → M → O → P → N Cycle 2: N → M → P → O → N Cycle 3: N → O → M → P → N Cycle 4: N → O → P → M → N Cycle 5: N → P → M → O → N Cycle 6: N → P → O → M → N
Which pairs of cycles must have the same weights? How do you know?
There are 4 vertices; so, n = 4 n = 4 . This means there are ( n − 1 ) ! = ( 4 − 1 ) ! = 3 ⋅ 2 ⋅ 1 = 6 ( n − 1 ) ! = ( 4 − 1 ) ! = 3 ⋅ 2 ⋅ 1 = 6 distinct Hamilton cycles beginning at any given vertex.
Since n = 4 n = 4 , there are ( n − 1 ) ! 2 = ( 4 − 1 ) ! 2 = 6 2 = 3 ( n − 1 ) ! 2 = ( 4 − 1 ) ! 2 = 6 2 = 3 possible weights.
Yes, they are all distinct cycles and there are 6 of them.
Cycles 1 and 6 have the same weight, Cycles 2 and 4 have the same weight, and Cycles 3 and 5 have the same weight, because these pairs follow the same route through the graph but in reverse.

TIP! When listing the possible cycles, ignore the vertex where the cycle begins and ends and focus on the ways to arrange the letters that represent the vertices in the middle. Using a systematic approach is best; for example, if you must arrange the letters M, O, and P, first list all those arrangements beginning with M, then beginning with O, and then beginning with P, as we did in Example 12.42.

Your Turn 12.43

The brute force method.

The method we have been using to find a Hamilton cycle of least weight in a complete graph is a brute force algorithm, so it is called the brute force method . The steps in the brute force method are:

Step 1: Calculate the number of distinct Hamilton cycles and the number of possible weights.

Step 2: List all possible Hamilton cycles.

Step 3: Find the weight of each cycle.

Step 4: Identify the Hamilton cycle of lowest weight.

Example 12.44

Applying the brute force method.

On the next assignment, the air force officer must leave from Travis Air Force base, visit Beal, Edwards, and Vandenberg Air Force bases each exactly once and return to Travis Air Force base. There is no need to visit Los Angeles Air Force base. Use Figure 12.194 to find the shortest route.

Step 1: Since there are 4 vertices, there will be ( 4 − 1 ) ! = 3 ! = 6 ( 4 − 1 ) ! = 3 ! = 6 cycles, but half of them will be the reverse of the others; so, there will be ( 4 − 1 ) ! 2 = 6 2 = 3 ( 4 − 1 ) ! 2 = 6 2 = 3 possible distances.

Step 2: List all the Hamilton cycles in the subgraph of the graph in Figure 12.195 .

To find the 6 cycles, focus on the three vertices in the middle, B, E, and V . The arrangements of these vertices are BEV, BVE, EBV, EVB, VBE , and VEB . These would correspond to the 6 cycles:

1: T → B → E → V → T

2: T → B → V → E → T

3: T → E → B → V → T

4: T → E → V → B → T

5: T → V → B → E → T

6: T → V → E → B → T

Step 3: Find the weight of each path. You can reduce your work by observing the cycles that are reverses of each other.

1: 84 + 410 + 207 + 396 = 1097 84 + 410 + 207 + 396 = 1097

2: 84 + 396 + 207 + 370 = 1071 84 + 396 + 207 + 370 = 1071

3: 370 + 410 + 396 + 396 = 1572 370 + 410 + 396 + 396 = 1572

4: Reverse of cycle 2, 1071

5: Reverse of cycle 3, 1572

6: Reverse of cycle 1, 1097

Step 4: Identify a Hamilton cycle of least weight.

The second path, T → B → V → E → T , and its reverse, T → E → V → B → T , have the least weight. The solution is that the officer should travel from Travis Air Force base to Beal Air Force Base, to Vandenberg Air Force base, to Edwards Air Force base, and return to Travis Air Force base, or the same route in reverse.

Your Turn 12.44

Now suppose that the officer needed a cycle that visited all 5 of the Air Force bases in Figure 12.194 . There would be ( 5 − 1 ) ! = 4 ! = 4 × 3 × 2 × 1 = 24 ( 5 − 1 ) ! = 4 ! = 4 × 3 × 2 × 1 = 24 different arrangements of vertices and ( 5 − 1 ) ! 2 = 4 ! 2 = 24 2 = 12 ( 5 − 1 ) ! 2 = 4 ! 2 = 24 2 = 12 distances to compare using the brute force method. If you consider 10 Air Force bases, there would be ( 10 − 1 ) ! = 9 ! = 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 362 , 880 ( 10 − 1 ) ! = 9 ! = 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 362 , 880 different arrangements and ( 10 − 1 ) ! 2 = 9 ! 2 = 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 2 = 181 , 440 ( 10 − 1 ) ! 2 = 9 ! 2 = 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 2 = 181 , 440 distances to consider. There must be another way!

The Nearest Neighbor Method

When the brute force method is impractical for solving a traveling salesperson problem, an alternative is a greedy algorithm known as the nearest neighbor method , which always visit the closest or least costly place first. This method finds a Hamilton cycle of relatively low weight in a complete graph in which, at each phase, the next vertex is chosen by comparing the edges between the current vertex and the remaining vertices to find the lowest weight. Since the nearest neighbor method is a greedy algorithm, it usually doesn’t give the best solution, but it usually gives a solution that is "good enough." Most importantly, the number of steps will be the number of vertices. That’s right! A problem with 10 vertices requires 10 steps, not 362,880. Let’s look at an example to see how it works.

Suppose that a candidate for governor wants to hold rallies around the state. They plan to leave their home in city A , visit cities B, C, D, E , and F each once, and return home. The airfare between cities is indicated in the graph in Figure 12.196 .

Let’s help the candidate keep costs of travel down by applying the nearest neighbor method to find a Hamilton cycle that has a reasonably low weight. Begin by marking starting vertex as V 1 V 1 for "visited 1st." Then to compare the weights of the edges between A and vertices adjacent to A : $250, $210, $300, $200, and $100 as shown in Figure 12.197 . The lowest of these is $100, which is the edge between A and F .

Mark F as V 2 V 2 for "visited 2nd" then compare the weights of the edges between F and the remaining vertices adjacent to F : $170, $330, $150 and $350 as shown in Figure 12.198 . The lowest of these is $150, which is the edge between F and D .

Mark D as V 3 V 3 for "visited 3rd." Next, compare the weights of the edges between D and the remaining vertices adjacent to D : $120, $310, and $270 as shown in Figure 12.199 . The lowest of these is $120, which is the edge between D and B .

So, mark B as V 4 V 4 for "visited 4th." Finally, compare the weights of the edges between B and the remaining vertices adjacent to B : $160 and $220 as shown in Figure 12.200 . The lower amount is $160, which is the edge between B and E .

Now you can mark E as V 5 V 5 and mark the only remaining vertex, which is C , as V 6 V 6 . This is shown in Figure 12.201 . Make a note of the weight of the edge from E to C , which is $180, and from C back to A , which is $210.

The Hamilton cycle we found is A → F → D → B → E → C → A . The weight of the circuit is $ 100 + $ 150 + $ 120 + $ 160 + $ 180 + $ 210 = $ 920 $ 100 + $ 150 + $ 120 + $ 160 + $ 180 + $ 210 = $ 920 . This may or may not be the route with the lowest cost, but there is a good chance it is very close since the weights are most of the lowest weights on the graph and we found it in six steps instead of finding 120 different Hamilton cycles and calculating 60 weights. Let’s summarize the procedure that we used.

Step 1: Select the starting vertex and label V 1 V 1 for "visited 1st." Identify the edge of lowest weight between V 1 V 1 and the remaining vertices.

Step 2: Label the vertex at the end of the edge of lowest weight that you found in previous step as V n V n where the subscript n indicates the order the vertex is visited. Identify the edge of lowest weight between V n V n and the vertices that remain to be visited.

Step 3: If vertices remain that have not been visited, repeat Step 2. Otherwise, a Hamilton cycle of low weight is V 1 → V 2 → ⋯ → V n → V 1 V 1 → V 2 → ⋯ → V n → V 1 .

Example 12.45

Using the nearest neighbor method.

Suppose that the candidate for governor wants to hold rallies around the state but time before the election is very limited. They would like to leave their home in city A , visit cities B , C , D , E , and F each once, and return home. The airfare between cities is not as important as the time of travel, which is indicated in Figure 12.202 . Use the nearest neighbor method to find a route with relatively low travel time. What is the total travel time of the route that you found?

Step 1: Label vertex A as V 1 V 1 . The edge of lowest weight between A and the remaining vertices is 85 min between A and D .

Step 2: Label vertex D as V 2 V 2 . The edge of lowest weight between D and the vertices that remain to be visited, B, C, E , and F , is 70 min between D and F .

Repeat Step 2: Label vertex F as V 3 V 3 . The edge of lowest weight between F and the vertices that remain to be visited, B, C, and E , is 75 min between F and C .

Repeat Step 2: Label vertex C as V 4 V 4 . The edge of lowest weight between C and the vertices that remain to be visited, B and E , is 100 min between C and B .

Repeat Step 2: Label vertex B as V 5 V 5 . The only vertex that remains to be visited is E . The weight of the edge between B and E is 95 min.

Step 3: A Hamilton cycle of low weight is A → D → F → C → B → E → A . So, a route of relatively low travel time is A to D to F to C to B to E and back to A . The total travel time of this route is: 85 min + 70 min + 75 min + 100 min + 95 min + 90 min = 515 min or 8 hrs 35 min 85 min + 70 min + 75 min + 100 min + 95 min + 90 min = 515 min or 8 hrs 35 min

Your Turn 12.45

Check your understanding, section 12.9 exercises.

As an Amazon Associate we earn from qualifying purchases.

This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction

Authors: Donna Kirk
Publisher/website: OpenStax
Book title: Contemporary Mathematics
Publication date: Mar 22, 2023
Location: Houston, Texas
Book URL: https://openstax.org/books/contemporary-mathematics/pages/1-introduction
Section URL: https://openstax.org/books/contemporary-mathematics/pages/12-9-traveling-salesperson-problem

© Dec 21, 2023 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.

Interview Q

DAA Tutorial

Asymptotic analysis, analysis of sorting, divide and conquer, lower bound theory, sorting in linear time, binary search trees, red black tree, dynamic programming, greedy algorithm, backtracking, shortest path, all-pairs shortest paths, maximum flow, sorting networks, complexity theory, approximation algo, string matching.

Interview Questions

Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse

Data Structures
Linked List
Binary Tree
Binary Search Tree
Segment Tree
Disjoint Set Union
Fenwick Tree
Red-Black Tree
Advanced Data Structures
Dynamic Programming or DP
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 all combinations of coins to make a given value sum (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
Top 20 Dynamic Programming Interview Questions

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

Please Login to comment...

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

public class Point (2D point data type) --------------------------------------------------------------------------------------- Point(double x, double y) // create the point (x, y) String toString() // return string representation void draw() // draw point using standard draw void drawTo(Point that) // draw line segment between the two points double distanceTo(Point that) // return Euclidean distance between the two points

public class Tour (TSP tour data type) ------------------------------------------------------------------------------------------------- Tour() // create an empty tour Tour(Point a, Point b, Point c, Point d) // create a 4 point tour a->b->c->d->a for debugging void show() // print the tour to standard output void draw() // draw the tour to standard draw double distance() // return the total distance of the tour void insertNearest(Point p) // insert p using nearest neighbor heuristic void insertSmallest(Point p) // insert p using smallest increase heuristic

% more tsp1000.txt 775 768 185.0411 457.8824 247.5023 299.4322 701.3532 369.7156 563.2718 442.3282 144.5569 576.4812 535.9311 478.4692 383.8523 458.4757 329.9402 740.9576 ... 254.9820 302.2548

% java NearestInsertion Tour distance = 27868.7106 (185.0411, 457.8824) (198.3921, 464.6812) (195.8296, 456.6559) (216.8989, 455.126) (213.3513, 468.0186) (241.4387, 467.413) (259.0682, 473.7961) (221.5852, 442.8863) ... (264.57, 410.328)

% java SmallestInsertion Tour distance = 17265.6282 (185.0411, 457.8824) (195.8296, 456.6559) (193.0671, 450.2405) (200.7237, 426.3461) (200.5698, 422.6481) (217.4682, 434.3839) (223.1549, 439.8027) (221.5852, 442.8863) ... (186.8032, 449.9557)

This type of vacation rental cancellation is on the rise. Are you next?

A few days before flying to Bali, Indonesia, I received an unexpected email from Airbnb: My host had sold my vacation home.

"We’re reaching out with the unfortunate news that your reservation was canceled," it said. "Your refund is on its way."

But wait – I didn't want my money back. I needed a place to stay while I was in Indonesia. Airbnb assured me I had nothing to worry about. It would find a new rental and cover my extra expenses. But, as always, some restrictions applied.

Check out Elliott Confidential , the newsletter the travel industry doesn't want you to read. Each issue is filled with breaking news, deep insights, and exclusive strategies for becoming a better traveler. But don't tell anyone!

Sales cancellations are on the rise

Selling a vacation rental out from under a guest is becoming a big problem, insiders said. There are no statistics on the number of vacation rentals with active reservations that are for sale. But Justin Gordon, who runs the rental price comparison site HiChee , says more hosts are putting their rentals on platforms like Airbnb and Vrbo while they wait to sell their properties. He has seen the disruption it causes guests who are about to leave for vacation.

"I felt so sorry for the guests," he said.

Did I mention the Indonesia rental? That wasn't my first cancellation. I rented a condo in Oahu, Hawaii, a few years ago through Vrbo. A week before I checked in, I got an email saying my stay had been canceled because the property was sold.

"Many homeowners are investors, buying properties low and selling high or holding them for a set number of years as a part of their financial strategy," said Matthew Deal, managing director of Element Vacation Homes , a central Florida vacation rental company.

A cancellation can have consequences for the seller. For example, if you list your home on Vrbo, you might have to pay the platform a cancellation fee, which gets higher as your arrival day approaches.

"In addition to financial penalties, repeat offenders may see limited search visibility on the Vrbo app and site, temporary suspension, or revocation of their Premier Host status," said spokesperson Nola Lu.

Airbnb has similar restrictions. "We expect Hosts to honor accepted reservations," said spokesperson Aaron Swor.

What are your rights when your vacation rental is sold?

If your vacation rental is sold before you arrive, you have some rights – though not as many as you'd assume.

For rentals booked directly through the owner, your rental contract will outline your right to a refund. If you're dealing with a host who has only one rental or can't accommodate you at a different property, you'll get a full refund, but you'll have to start over and find a new vacation rental. Pro tip: Use a credit card to book. If the owner flakes out and tries to keep your money, you can always dispute the charges.
For rentals booked through a popular vacation rental platform like Airbnb or Vrbo, the platform will offer a full refund or or accommodate you at a different rental property. If there's a price difference – and there usually is – then the platform may offer to cover the extra cost.
If you booked through a property management company, your rights may not be spelled out in your contract, but chances are the company will have a plan "B" ready. For example, Element Vacation Rentals has a policy to promptly present multiple options to displaced guests, including comparable properties from its portfolio and those of its competitors. Ask about the policy before you make a reservation.

At least, that is what's supposed to happen if there's a cancellation. But let's talk about what actually does happen.

'Expensive in every way': What travelers should expect this summer

Flying cars are coming! Here's how they could change the way you travel.

What if an owner sells a vacation rental?

When an owner sells your vacation rental from under you, you'll probably feel confused and upset. And even as you're processing the loss of your rental, your host may ask you for a favor.

When the owners of Gerri Detweiler's Airbnb rental sold their place, her host asked her to cancel the rental. The reason? The host didn't want to incur a fee from Airbnb. So Detweiler, a personal finance expert from Sarasota, Florida, canceled the stay.

"I didn't bother booking another rental with Airbnb," she said.

For both of my cancellations, I had no choice. I was only days away from checking in.

To their credit, both Airbnb and Vrbo helped me. Vrbo found a new rental in Hawaii and covered the price difference. Airbnb offered a coupon and sent me a few options for a replacement rental in Bali. The only one available on such short notice was thousands of dollars more than my original rental, so Airbnb increased the amount of the coupon to cover the extra cost.

The difference between the platforms was in their approach to the situation. Vrbo transferred me to a special team that took care of everything quickly. With Airbnb, it felt like more of a negotiation. But in the end, I was grateful to have the protection of both vacation rental platforms.

'Flying feels different': Here's how air travel has changed recently

Air travel smells worse than ever. Here's how to fix it.

This could happen to you

This isn't an abstract issue. Two of this year's hottest housing markets – Orlando and Tampa, Florida – are popular with vacation renters and are likely to have lots of homes that are also on the market.

But that's not the real problem. It's that most vacation rental customers don't know their rights when they rent. They either assume that they have no choice but to take the refund and that they're on their own. Or they believe the vacation rental company must find them a comparable rental and cover any price difference.

But you're not on your own unless you rented directly through an individual – and even then, the previous owner may be able to refer you to another rental. And your vacation rental platform won't automatically find you a new place and pay for it. You may have to negotiate.

The best solution is disclosure. Vacation rental owners should tell you if their property is for sale. Then you can make an informed decision about whether you still want to rent the place – and take your chances.

Elliott's tips for avoiding a vacation rental cancellation

Getting surprised by a vacation rental sale is preventable. Here are a few strategies:

Talk to the owner : Before you rent a vacation home, ask if the place is for sale. If it is, ask what would happen if the unit were to be sold. If it's sold, talk to the new owners," said hospitality consultant Steve Turk. "See if they'll honor your reservation."
Read the reviews – all of them : If you're renting on a popular platform, don't just skim the reviews. Read them. Sometimes, hosts will stop caring about their rental unit if they know they're going to sell. "Check to see if recent guests have posted any negative reviews," advised Pete Evering, a business development manager at Utopia Property Management , a rental management company.
Do your research : If you have the address of the rental, run a quick online search. If it shows up on Zillow or Realtor.com , you know you have a problem. Gordon from HiChee is considering developing technology that would notify travelers in case their booked rental shows up for sale on the internet.

Christopher Elliott is an author, consumer advocate, and journalist. He founded Elliott Advocacy , a nonprofit organization that helps solve consumer problems. He publishes Elliott Confidential , a travel newsletter, and the Elliott Report , a news site about customer service. If you need help with a consumer problem, you can reach him here or email him at [email protected] .

Money blog: Slippery floors and a burst of heat - tricks shops use to get you to spend more

In the final part of our psychology of shopping series, we speak to fair fashion campaigner Venetia La Manna about the tricks fast fashion companies use to get people to spend, spend, spend. Read this and the rest of today's consumer news in the Money blog.

Thursday 6 June 2024 07:33, UK

Asda goes from cheapest to most expensive supermarket for petrol
Five switching offers launch in quick succession offering up to £200 - and this is best time of month to do it
Ed Conway : Claim of £2k tax rise under Labour is over four years - same maths suggests Tories have raised taxes by £13k in last four years
Ian King : Why European rates decision could impact global economy - and your holiday money

Essential reads

How brands get you to buy more, more, more
Top chef shares his take on an Italian classic - and Warwickshire Cheap Eats
Women in Business : 'I quit well-paid job while seven months pregnant after men said I didn't understand - now I'm a CEO'
How much are student loans, when do you start paying back and what is the interest?
Your rights when deliveries or returns don't arrive - and why leaving instructions could jeopardise them
Best of the Money blog - an archive

Ask a question or make a comment

By Emily Mee , news reporter

We've all been there. You have a bad day and you need a little pick-me-up - so you head straight to your favourite website to buy something new.

That hit of dopamine you get when buying something is what many businesses rely on - and no one seems to understand it better than fast fashion brands.

But not only is this hurting our wallets, it's also harming the planet.

In the final part of our psychology of shopping series, we spoke to fair fashion campaigner Venetia La Manna ( @venetialamanna ) - who advocates for a more sustainable approach to clothing - about the little tricks fast fashion companies use to get people to spend, spend, spend...

Always in a rush - and slippery floors

Many of the techniques fashion companies use involve ensuring people feel rushed to make purchasing decisions.

Ms La Manna says websites and social media pages are set up to make them look "very immediate" so we "always feel like we have to buy something before it's gone" - meaning you're not able to sit with a purchase and think about whether you need it.

Fast fashion companies also keep an eye on trends and push out products as soon as possible to make sure people are "buying very, very quickly without necessarily much thought".

And the sense of urgency is not just limited to online stores.

Ms La Manna says physical clothes shops will make sure their floors are slippery "so you can almost whizz around with more ease".

Often they will also have loud music to encourage "shopping in a frenzy".

They know what you want

Fashion sites use "highly advanced" search engine optimisation to find out what kind of products their customers are searching for and push these items to them, Ms La Manna says.

They also work with popular online influencers and get them to post affiliate links - meaning if you want to look like your favourite influencer or celebrity, you can buy what they're wearing "in just a few clicks".

Ultimately, they are making things "very easy to buy" and often have shopfronts on popular social media sites like Instagram and TikTok.

Plus, there is the issue of affordability.

Many are driving their prices down so low that "it makes you feel like 'hey, why not' when it's cheaper than a sandwich or a coffee", Ms La Manna says.

Heaters at the entrance

Physical shops use other techniques to entice customers to buy.

For example, Ms La Manna says the heat changes when you go into the shop so you're "invited into a warmer environment".

Shops are also set out in a specific way, often placing cheaper items near checkouts and easy outfit formulas near each other.

The dopamine hit

With lots going on in the world, we may be more susceptible to falling into the spending trap than ever.

"The world is really heavy and people are struggling. Buying fast fashion or buying stuff gives us a momentary hit of dopamine, and of course we need that - when we're suffering, when we're feeling low, [shopping] is an easy one to reach for," Ms La Manna says.

Despite practising "slow fashion" - trying to buy less and more consciously - for years, Ms La Manna says she still has moments where she feels that buying something would make her feel better.

But she says it's possible to get much-needed dopamine hits from elsewhere - including by being active in your community, or by taking your time to find something you really, really want (ideally secondhand!).

Why does it matter?

Aside from being bad for your wallet, Ms La Manna says overconsumption is also bad for the planet and for the garment workers making your clothes.

She says many big fashion companies don't pay their garment workers a fair living wage - with many unable to provide food for their families, living in poverty and lacking paid time off.

The overproduction of clothing is also harming communities in the global south who are left to deal with vast piles of unwanted items, she says.

The majority of clothes taken to charity shops or recycling bins don't end up being resold - instead they are shipped off largely to places in the global south, where communities are "left to deal with a problem that's not theirs".

For more information on slow fashion, Ms La Manna suggests checking out The Or Foundation, Remake and the Clean Clothes Campaign.

Asda has gone from selling the cheapest petrol out of the supermarket chains to now costing the most, according to the latest fuel price figures.

RAC says Asda's big rivals, Morrisons, Sainsbury's and Tesco, all sold a litre of unleaded petrol for 2.1p less on average at the end of May.

Diesel was also coming out costlier at Asda, with the supermarket 2.5p per litre more expensive than the rest of its supermarket competition.

Drivers are being urged - by the RAC - to change their refuelling habits to find the best prices.

What makes up the cost of a litre of petrol?

The price you pay for fuel at the pumps is governed by wholesale fuel prices, which are affected by several factors.

These include the global price of crude oil, which itself is governed by supply and demand and oil refinery production and capacity.

Distribution costs, fuel duty (currently 52.95p a litre in the UK), VAT (currently at 20%) and profit margins dictated by fuel retailers all come into account when working out why prices of fuel rise and fall.

Fuel duty rate and VAT largely stay the same, though oil prices and the strength of the pound to the US dollar (refined fuel is sold in dollars per metric tonne) can cause prices to be extremely volatile.

How have UK petrol prices changed in the 21st century

Unleaded fuel in 2000 had an average cost of 80.35p, while the average cost of diesel in the same year was 81.73p.

The lowest average cost for unleaded petrol in the last 24 years came in 2002, where the average was 73.5p. Diesel also had its cheapest average cost in this year at 75.6p.

Unsurprisingly, the most expensive average prices for fuel have fallen in recent years. In 2022, the average cost of unleaded fuel was 165.06p and the average cost of diesel was 178.13p.

P Diddy has sold off his stake in the media company he founded more than a decade ago.

The rapper, whose real name is Sean Combs, released his shares of Revolt with the company saying the have been fully redeemed and retired.

Revolt has not disclosed how much Combs was paid for his stake in the hip-hop news and entertainment company, which he founded in 2013.

It also announced a new ownership structure that will give its employees an equity stake in the company.

The move comes after several lawsuits were filed against Combs , accusing him of sexual assault and rape.

In November, he was sued by R&B singer Cassie, who said he subjected her to a years-long abusive relationship that included beatings and rape.

Combs settled the lawsuit with Cassie, whose full name is Casandra Ventura, a few days after it was filed.

Three in five secondary school teachers and nearly 80% of primary school teachers are spending their own money on supporting students, according to new research.

A report by the National Foundation for Educational Research, based on a survey of 1,282 teachers and senior leaders, found a quarter of teachers had already spent £100 of their own cash on their pupils or school this academic year.

Some 79% of primary school teachers and 62% of secondary school educators reported spending their own money at some point.

And nearly one in five primary and 17% of secondary teachers said they were spending money on meeting pastoral needs such as providing food or clothes.

Jude Hillary, the NFER's co-head of UK policy and practice, said the report "clearly highlights the high level of need among young people".

She said teachers were "going above and beyond to meet pupils' pastoral needs using their personal funds" and the "unrecognised" support was coming at a time when staff themselves are facing their own cost pressures.

Tesco has started re-stocking its packs of a dozen eggs online, after lengthy supply issues forced them to stop selling them.

The supermarket had already re-started selling them in stores, but online shoppers had to buy two packs of six eggs if they wanted 12, costing them very slightly more.

The shortages began in the autumn of 2022 as farmers left the industry or pulled back on production due to rising costs.

An outbreak of bird flu last year also impacted the sector.

Customers of Loveholidays have had their travel plans thrown into chaos after the parent company of two of its partners unexpectedly went bust.

In a post on Facebook, the holiday firm said FTI Group, which owns YouTravel and Meeting Point, had filed for insolvency.

As a result, the accommodation and transfer arrangements of some travellers have been affected.

A "small number" of hotels have already started contacting Loveholiday travellers, asking them to pay for their rooms again.

In the comments of the post, one person said they had been "threatened to be removed by police" for refusing to pay again.

"We are supposed to go home Thursday evening and worried our transfers and flights might be affected because we are refusing to pay again," Scott Love wrote.

"Shambles this and has ruined our holiday for me, my partner and three children."

Several other people commented, asking the provider to tell them if their trip had been impacted.

Loveholidays said it was "working hard" to honour its customers bookings and "minimise disruption" to any holiday.

It also said it was "absolutely committed" to covering costs and was working with affected customers, and the hotels involved, to make sure that happens.

Those who are on holiday and need support have been advised to contact the holiday support team by calling the number on their booking documents.

"If you're travelling with us soon and are wondering if your holiday is affected: Please don't worry. There is nothing you need to do - our team is working hard to honour any impacted bookings with another partner," Loveholidays added.

Sky News has contacted the company for comment.

Chef Tom Brown has announced he is closing his high-end Hackney restaurant Cornerstone due to high costs of the tasting menu format and changing diner preferences.

The seafood-focused restaurant first opened in 2018 and earned a Michelin star in 2021.

In a statement, Brown said Cornerstone had been his "proudest moment" and his "home for the last six years", and added that his focus would now be on his nearby Pearly Queen site.

First Direct is ending its text message banking service after 25 years, according to a report.

An email seen by This Is Money said the service - which texts customers mini bank statements and alerts them to their balance dropping below a certain amount - will be stopped on 10 August.

First Direct told the outlet that customers could get "more detailed and up-to-date information" by logging onto its app or online banking.

Tesco has partnered with Virgin Red to offer Clubcard holders the chance to turn points into experiences.

Those signed up to the supermarket's loyalty scheme will get twice the points value when they turn points earned on their shopping into Virgin Points.

A bonus 5,000 points is available for anyone who signs up to auto-exchange all their Clubcard points to Virgin Points for the first time.

McDonald's has lost the EU trademark for "Big Mac" when it comes to chicken sandwiches after a long-running dispute with an Irish restaurant chain.

The European Court of Justice upheld a complaint from Galway-based Supermac's against the US fast food giant.

The trademark for the words "Big Mac" was initially registered with the EU International Property Office (EUIPO) in respect of meat, fish and chicken sandwiches as well as a range of restaurant services by McDonald's in 1996.

Generally, the rights of a holder to an EU trademark are revoked if it has not been put to genuine use within a continuous period of five years.

Supermac's argued McDonald's had insufficiently used the contested trademark in relation to "chicken sandwiches".

McDonald's and the EUIPO put forward examples of advertisements and display boards relating to "Grand Big Mac Chickens".

However, the court found the evidence was not sufficient to prove McDonald's had used the contested trademark enough in relation to poultry products.

Supermac's complaint was upheld and McDonald's protection of the phrase for such purposes was overturned.

Subway is following in the steps of some of its fast-food rivals with the introduction of self-service kiosks and its own dedicated app.

Customers will be able to place orders via digital screens sent to the kitchen instead of making their way along the chain of ingredients.

The self-service kiosks will be in all UK stores before the end of the year, The Grocer reports.

The sandwich shop chain is also launching a new app which will enable online orders - and offer customers points towards its "Subway Rewards" loyalty scheme, it said.

The points can eventually be converted into "Subway Cash" to spend on menu items.

Dan Holm, digital leader at Subway, said: "As we think about Subway's future, we're doubling down on our global digital commitment to streamline and simplify the guest experience from start to finish."

Rishi Sunak's claim in last night's debate that Labour will raise everyone's taxes by £2,000 comes from a "dossier" published by the Tories last month, which purported to calculate their tax and spending plans.

The headline "finding" was that over the course of the next four years, Labour had roughly £59bn of spending plans but only £20bn of revenue-raising plans.

That leaves a £39bn hole. Divide that by the number of households in the country (18.4m) and you get a figure of just over £2,000.

Now, there are all sorts of objections to the way the Conservatives have carried out this exercise.

For one thing, they deployed a weapon Labour don't have: because they're the party of government, they were able to ask Treasury civil servants to cost some Labour policies.

Today there has been a backlash - including from the Treasury's permanent secretary himself - about the way the Tories have portrayed these sums.

The £2,000 figure isn't really a Treasury calculation or an "independent" one, as Mr Sunak called it last night. It's a Conservative figure - but it was put together in part with figures commissioned from civil servants.

Labour also says many of the policies in that Tory dossier won't cost half as much as the Conservatives claim.

Regardless, while £2,000 sounds like a big number, it's actually a cumulative total from four years. A far more representative figure to take from the dossier is £500 - the annual figure.

And while that's not to be sniffed at (if you believe it - which you probably shouldn't) it's far, far smaller than the tax rises we've all experienced under this Conservative government since 2019.

They amount, all told, to an average of around £3,000 a year per household or, if we grit our teeth and tot it up as the Tories did in their dossier, over £13,000 over the course of the parliament.

Which rather dwarfs that £2,000 figure.

Be the first to get Breaking News

Install the Sky News app for free

COMMENTS

Travelling salesman problem
The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
Traveling Salesman Problem (TSP) Implementation
Learn how to solve the TSP problem using a naive approach that generates all possible permutations of cities and calculates their costs. See C++, Java, Python3 and C# code examples and output for a 4-city graph.
Traveling Salesperson Problem
Learn about the traveling salesperson problem, an NP-Complete problem that involves finding the shortest path to visit a set of cities. Explore its relationship to graphs, complexity, solutions, special kinds, and applications.
DSA The Traveling Salesman Problem
Learn about the Traveling Salesman Problem, a classic optimization problem in computer science. Find out how to solve it by brute force, greedy algorithm, and other methods.
12.10: Traveling Salesperson Problem
For the following exercises, use your solutions to Exercises 25-30 and the nearest neighbor method to find a Hamilton cycle to solve the traveling salesperson problem of finding a reasonably short route to leave from city U, visit each of the other cities listed and return to city U. Indicate the distance required to travel the route you found.
Traveling salesman problem
The traveling salesman problem (TSP) is a widely studied combinatorial optimization problem, which, given a set of cities and a cost to travel from one city to another, seeks to identify the tour that will allow a salesman to visit each city only once, starting and ending in the same city, at the minimum cost. 1.
PDF The Traveling Salesman Problem
The traveling salesman problem is solved if there exists a shortest route that visits each destination once and permits the salesman to return home. (This route is called a Hamiltonian Cycle and will be explained in Chapter 2.) The traveling salesman problem can be divided into two types: the problems where there is a path between ...
Traveling Salesperson Problem
Learn how to solve the TSP for 12 locations in the US using Python, C++, Java, or C#. The web page provides the data, the code, and the output for the problem.
Traveling Salesman Problem
Learn about the TSP, a classic problem of finding the shortest route visiting each location and returning to the start. Explore its history, applications, world records, data, news, and current research at the University of Waterloo.
PDF The Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is one of the most well-known combinatorial optimization problems. Its popularity and importance can be attributed to its simple deﬁnition but high complexity to solve it, making it an ideal research problem for design of new algorithms, development of complexity theory, and analysis of search ...
Traveling Salesman Problem
The Traveling Salesman Problem (TSP) is perhaps the most studied discrete optimization problem. Its popularity is due to the facts that TSP is easy to formulate, difficult to solve, and has a large number of applications. It appears that K. Menger was the first researcher to consider the Traveling Salesman Problem (TSP). He observed that the ...
COS 126: Traveling Salesperson Problem
The traveling salesperson problem is a notoriously difficult combinatorial optimization problem, In principle, one can enumerate all possible tours and pick the shortest one; in practice, the number of tours is so staggeringly large (roughly N factorial) that this approach is useless. For large N, no one knows an efficient method that can find ...
Travelling Salesman Problem (Greedy Approach)
Learn how to solve the travelling salesman problem using greedy algorithm, which finds the shortest path in a graph by choosing the minimum edge at each step. See examples, code and output in C, C++ and Java.
The Travelling Salesperson Problem
The Travelling Salesperson Problem Footnote 1 (TSP) has a long history (Cook 2012; Cummings 2000), and the formulation of the modern TSP is widely attributed to Karl Menger who introduced the Das Botenproblem at a mathematics conference in 1932 (Menger 1932).Mengers' problem involved finding the shortest route for postal messengers who must visit a set of points.
6.6: Hamiltonian Circuits and the Traveling Salesman Problem
This page titled 6.6: Hamiltonian Circuits and the Traveling Salesman Problem is shared under a CC BY-SA 3.0 license and was authored, remixed, and/or curated by David Lippman (The OpenTextBookStore) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.
12.9 Traveling Salesperson Problem
Learn how to solve the traveling salesperson problem using brute force and greedy algorithms. Find the shortest route to visit a number of locations and return to the starting point in a complete weighted graph.
PDF 1Traveling Salesperson Problem (TSP)
The Traveling Salesperson Path Problem is the same thing but does not require returning to the start. Both problems are NP-hard. 1. Step 2: De ne our subproblems Based on the above, lets make our subproblems C(S;t) = The minimum-cost path starting at x and ending at t going through all vertices in S
How to Solve Traveling Salesman Problem
The traveling salesman problem is a classic problem in combinatorial optimization. This problem is finding the shortest path a salesman should take to traverse a list of cities and return to the origin city. The list of cities and the distance between each pair are provided. TSP is beneficial in various real-life applications such as planning ...
Travelling Salesman Problem
Learn the definition, solution and implementation of the Travelling Salesman Problem, an NP-hard graph computational problem. See examples and code in C, C++, Java and Python.
Travelling Salesman Problem using Dynamic Programming
Learn how to solve the TSP problem using dynamic programming with top down recursive+memoized approach. See the C++, Java, Python, C# and Javascript code and the time complexity analysis.
Computer Scientists Break Traveling Salesperson Record
The traveling salesperson problem is one of a handful of foundational problems that theoretical computer scientists turn to again and again to test the limits of efficient computation. The new result "is the first step towards showing that the frontiers of efficient computation are in fact better than what we thought," Williamson said.
COS 126: Traveling Salesperson Problem
The traveling salesperson problem is a notoriously difficult combinatorial optimization problem, In principle, one can enumerate all possible tours, but, in practice, the number of tours is so staggeringly large (roughly N factorial) that this approach is useless. For large N, no one knows an efficient method that can find the shortest possible ...
Traveling Salesman Problem
The Travelling Salesman Problem (TSP) is a very well known problem in theoretical computer science and operations research. The standard version of TSP is a hard problem to solve and belongs to the NP-Hard class. In this tutorial, we'll discuss a dynamic approach for solving TSP. Furthermore, we'll also present the time complexity analysis ...
How to avoid a vacation rental cancellation
Here are a few strategies: Talk to the owner: Before you rent a vacation home, ask if the place is for sale. If it is, ask what would happen if the unit were to be sold. If it's sold, talk to the ...
Money blog: Subway drastically changing how you order
Aldi has come out on top again as the cheapest supermarket - by £3.32 for a shop. The discount chain claimed first place in the latest Which? analysis, once again above rival Lidl, with a 69-item ...

Traveling Salesperson Problem

Relationship to Graphs

DSA Tutorial

Checking All Routes to Solve The Traveling Salesman Problem

Using A Greedy Algorithm to Solve The Traveling Salesman Problem

Other Algorithms That Find Near-Optimal Solutions to The Traveling Salesman Problem

Time Complexity for Solving The Traveling Salesman Problem

Actual Traveling Salesman Problems Are More Complex

COLOR PICKER

Contact Sales

Report Error

Top Tutorials

Traveling salesman problem

Description

Classifications of the TSP

Variations of the TSP

aTSP ILP Formulation

sTSP ILP Formulation

Exact algorithms

Heuristic algorithms

Tour construction procedures

Navigation menu

Traveling Salesperson Problem

Create the data

Other ways to create the distance matrix

Create the routing model

Create the distance callback

Set the cost of travel

Set search parameters

Add the solution printer

Solve and print the solution

Run the programs

Save routes to a list or array

Complete programs

Example: drilling a circuit board

Compute the distance matrix

Add the distance callback

Solution printer

Main function

Running the program

Changing the search strategy

Scaling the distance matrix

Traveling Salesman Problem

Travelling Salesman Problem (Greedy Approach)

The Travelling Salesperson Problem

Cite this chapter

Access this chapter

Author information

Corresponding author

Rights and permissions

Copyright information

About this chapter

Download citation

Share this chapter

Margin Size

6.6: Hamiltonian Circuits and the Traveling Salesman Problem

Hamiltonian Circuits and Paths

Brute Force Algorithm (a.k.a. exhaustive search)

Number of Possible Circuits

Nearest Neighbor Algorithm (NNA)

Repeated Nearest Neighbor Algorithm (RNNA)

Try it Now 5

Sorted Edges Algorithm (a.k.a. Cheapest Link Algorithm)

Try it Now 6

12.9 Traveling Salesperson Problem

Brute Force and Greedy Algorithms

Example 12.42

Your Turn 12.42

Finding Weights of All Hamilton Cycles in Complete Graphs

Example 12.43

Your Turn 12.43

Example 12.44

Your Turn 12.44

The Nearest Neighbor Method

Example 12.45

Your Turn 12.45

DAA Tutorial

Help Others, Please Share

Learn Latest Tutorials

Preparation