solution travelling salesman problem

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

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 \text{min} \sum_i \sum_j c_{ij}y_{ij} }

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

Navigation menu

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures
• Traveling Salesman Problem (TSP) Implementation
• Bitonic Travelling Salesman Problem
• Travelling Salesman Problem using Dynamic Programming
• Proof that traveling salesman problem is NP Hard
• Traveling Salesman Problem using Genetic Algorithm
• Travelling Salesman Problem using Hungarian method
• Travelling Salesman Problem (TSP) using Reduced Matrix Method
• Traveling Salesman Problem using Branch And Bound
• Travelling Salesman Problem | Greedy Approach
• Bitmasking and Dynamic Programming | Travelling Salesman Problem
• Travelling Salesman Problem implementation using BackTracking
• Approximate solution for Travelling Salesman Problem using MST
• Using Stacks to solve Desert Crossing Problem in Python
• Java Program to Solve Travelling Salesman Problem Using Incremental Insertion Method
• Python Program for Number of stopping station problem
• Transportation Problem | Set 7 ( Degeneracy in Transportation Problem )
• Transportation Problem | Set 1 (Introduction)
• Transportation Problem Set 8 | Transshipment Model-1
• The Knight's tour problem

Traveling Salesman Problem (TSP) in Python

The Traveling Salesman Problem (TSP) is a classic algorithmic problem in the fields of computer science and operations research. It involves finding the shortest possible route that visits a set of cities and returns to the origin city. The challenge of TSP lies in its NP-hard nature, meaning that as the number of cities increases, the problem becomes exponentially more complex to solve optimally.

What is Traveling Salesman Problem (TSP)?

In TSP, a “salesman” starts at a home city, visits a list of given cities exactly once, and returns to the home city, minimizing the total travel distance or cost. This problem can be applied to various practical scenarios, including logistics, planning, and manufacturing.

Approaches to Solve Traveling Salesman Problem (TSP):

There are several approaches to solving TSP, ranging from exact algorithms that guarantee an optimal solution to heuristic and metaheuristic methods that provide approximate solutions. Some common methods include:

• Brute Force: Checking all possible permutations of cities to find the shortest route. This method guarantees an optimal solution but is computationally infeasible for large datasets due to its factorial time complexity.
• Dynamic Programming: The Held-Karp algorithm uses dynamic programming to reduce the time complexity to 𝑂(𝑛2⋅2𝑛) O ( n 2⋅2 n ), which is still exponential but more efficient than brute force for moderately sized problems.
• Greedy Algorithms: These provide quick but often suboptimal solutions by making locally optimal choices at each step.
• Genetic Algorithms: These use principles of natural selection and genetics to find approximate solutions.
• Simulated Annealing: This probabilistic technique approximates the global optimum of a given function by iterative improvement.

Implementing of Traveling Salesman Problem (TSP) in Python

Let’s implement a simple solution using dynamic programming ( Held-Karp algorithm ) in Python. This method involves breaking the problem into smaller subproblems and solving each subproblem only once, storing the results to avoid redundant calculations.

Step-by-Step Implementation:

• Define the Problem: Represent the cities and the distances between them using a distance matrix.
• Initialize the Dynamic Programming Table: Create a table to store the minimum costs of visiting subsets of cities.
• Iterate Through Subsets: Compute the minimum costs for visiting subsets of cities and update the table.
• Compute the Optimal Path: Reconstruct the optimal path from the dynamic programming table.

Below is the implementation of the above approach:

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.

Please Login to comment...

Similar reads.

• Dynamic Programming

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

• Travelling salesman problem

The travelling salesman problem (often abbreviated to TSP) is a classic problem in graph theory . It has many applications, in many fields. It also has quite a few different solutions.

The problem

The problem is usually stated in terms of a salesman who needs to visit several towns before eventually returning to the starting point. There are various routes he could take, visiting the different towns in different orders. Here is an example:

There are several different routes that will visit every town. For example, we could visit the towns in the order A , B , C , D , E , then back to A . Or we could use the route A , D , C , E , B then back to A .

But not all routes are possible. For example, we cannot use a route A , D , E , B , C and then back to A , because there is no road from C to A .

The aim is to find the route that visits all the towns with the minimum cost . The cost is shown as the weight of each edge in the graph. This might be the distance between the towns, or it might be some other measure. For example, it might be the time taken to travel between the towns, which might not be proportionate to the distance because some roads have lower speed limits or are more congested. Or, if the salesman was travelling by train, it might be the price of the tickets.

The salesman can decide to optimise for whatever measure he considers to be most important.

Alternative applications and variants

TSP applies to any problem that involves visiting various places in sequence. One example is a warehouse, where various items need to be fetched from different parts of a warehouse to collect the items for an order. In the simplest case, where one person fetches all the items for a single order and then packs and dispatches the items, a TSP algorithm can be used. Of course, a different route would be required for each order, which would be generated by the ordering system.

Another interesting example is printed circuit board (PCB) drilling. A PCB is the circuit board you will find inside any computer or other electronic device. They often need holes drilled in them, including mounting holes where the board is attached to the case and holes where component wires need to pass through the board. These holes are usually drilled by a robot drill that moves across the board to drill each hole in the correct place. TSP can be used to calculate the optimum drilling order.

The TSP algorithm can be applied to directed graphs (where the distance from A to B might be different to the distance from B to A ). Directed graphs can represent things like one-way streets (where the distance might not be the same in both directions) or flight costs (where the price of a single airline ticket might not be the same in both directions).

There are some variants of the TSP scenario. The mTSP problem covers the situation where there are several salesmen and exactly one salesman must visit each city. This applies to delivery vans, where there might be several delivery vans. The problem is to decide which parcels to place on each van and also to decide the route of each van.

The travelling purchaser problem is another variant. In that case, a purchaser needs to buy several items that are being sold in different places, potentially at different prices. The task is to purchase all the items, minimising the total cost (the cost of the items and the cost of travel). A simple approach would be to buy each item from the place where it is cheapest, in which case this becomes a simple TSP. However, it is not always worth buying every item from the cheapest place because sometimes the travel cost might outweigh the price difference.

In this article, we will only look at the basic TSP case.

Brute force algorithm

We will look at 3 potential algorithms here. There are many others. The first, and simplest, is the brute force approach.

We will assume that we start at vertex A . Since we intend to make a tour of the vertices (ie visit every vertex once and return to the original vertex) it doesn't matter which vertex we start at, the shortest loop will still be the same.

So we will start at A , visit nodes B , C , D , and E in some particular order, then return to A .

To find the shortest route, we will try every possible ordering of vertices B , C , D , E , and record the cost of each one. Then we can find the shortest.

For example, the ordering ABCDEA has a total cost of 7+3+6+7+1 = 24.

The ordering ABCEDA (i.e. swapping D and E ) has a total cost of 7+3+2+7+1 = 20.

Some routes, such as ADEBCA are impossible because a required road doesn't exist. We can just ignore those routes.

After evaluating every possible route, we are certain to find the shortest route (or routes, as several different routes may happen to have the same length that also happens to be the shortest length). In this case, the shortest route is AECBDA with a total length of 1+8+3+6+1 = 19.

The main problem with this algorithm is that it is very inefficient. In this example, since we have already decided that A is the start/end point, we must work out the visiting order for the 4 towns BCDE . We have 4 choices of the first town, 3 choices for the second town, 2 choices for the third town, and 1 choice for the fourth town. So there are 4! (factorial) combinations. That is only 24 combinations, which is no problem, you could even do it by hand.

If we had 10 towns (in addition to the home town) there would be 10! combinations, which is 3628800. Far too many to do by hand, but a modern PC might be able to do that in a fraction of a second if the algorithm was implemented efficiently.

If we had 20 towns, then the number of combinations would be of order 10 to the power 18. If we assume a computer that could evaluate a billion routes per second (which a typical PC would struggle to do, at least at the time of writing), that would take a billion seconds, which is several decades.

Of course, there are more powerful computers available, and maybe quantum computing will come into play soon, but that is only 20 towns. If we had 100 towns, the number of combinations would be around 10 to the power 157, and 1000 towns 10 to the power 2568. For some applications, it would be quite normal to have hundreds of vertices. The brute force method is impractical for all but the most trivial scenarios.

Nearest neighbour algorithm

The nearest neighbour algorithm is what we might call a naive attempt to find a good route with very little computation. The algorithm is quite simple and obvious, and it might seem like a good idea to someone who hasn't put very much thought into it. You start by visiting whichever town is closest to the starting point. Then each time you want to visit the next town, you look at the map and pick the closest town to wherever you happen to be (of course, you will ignore any towns that you have visited already). What could possibly go wrong?

Starting at A , we visit the nearest town that we haven't visited yet. In this case D and E are both distance 1 from A . We will (completely arbitrarily) always prioritise the connections in alphabetical order. So we pick D .

As an aside, if we had picked E instead we would get a different result. It might be better, but it is just as likely to be worse, so there is no reason to chose one over the other.

From D , the closest town is C with a distance of 6 (we can't pick A because we have already been there).

From C the closest town is E with distance 2. From E we have to go to B because we have already visited every other town - that is a distance of 8. And from B we must return to A with a distance of 7.

The final path is ADCEBA and the total distance is 1+6+2+8+7 = 24.

The path isn't the best, but it isn't terrible. This algorithm will often find a reasonable path, particularly if there is a natural shortest path. However, it can sometimes go badly wrong.

The basic problem is that the algorithm doesn't take account of the big picture. It just blindly stumbles from one town to whichever next town is closest.

In particular, the algorithm implicitly decides that the final step will be B to A . It does this based on the other distances, but without taking the distance BA into account. But what if, for example, there is a big lake between B and A that you have to drive all the way around? This might make the driving distance BA very large. A more sensible algorithm would avoid that road at all costs, but the nearest neighbour algorithm just blindly leads us there.

We can see this with this revised graph where BA has a distance of 50:

The algorithm will still recommend the same path because it never takes the distance BA into account. The path is still ADCEBA but the total distance is now 1+6+2+8+50 = 67. There are much better routes that avoid BA .

An even worse problem can occur if there is no road at all from B to A . The algorithm would still guide us to town B as the final visit. But in that case, it is impossible to get from B to A to complete the journey:

Bellman–Held–Karp algorithm

The Bellman–Held–Karp algorithm is a dynamic programming algorithm for solving TSP more efficiently than brute force. It is sometimes called the Held–Karp algorithm because it was discovered by Michael Held and Richard Karp, but it was also discovered independently by Richard Bellman at about the same time.

The algorithm assumes a complete graph (ie a graph where every vertex is connected to every other). However, it can be used with an incomplete graph like the one we have been using. To do this, we simply add extra the missing connections (shown below in grey) and assign them a very large distance (for example 1000). This ensures that the missing connections will never form part of the shortest path:

The technique works by incrementally calculating the shortest path for every possible set of 3 towns (starting from A ), then for every possible set of 4 towns, and so on until it eventually calculates the shortest path that goes from A via every other town and back to A .

Because the algorithm stores its intermediate calculations and discards non-optimal paths as early as possible, it is much more efficient than brute force.

We will use the following notation. We will use this to indicate the distance between towns A and B :

And we will use this to indicate the cost (ie the total distance) from A to C via B :

Here are some examples:

The first example is calculated by adding the distance AB to BC , which gives 10. The second example is calculated by adding AC to CB . But since there is no road from A to C , we give that a large dummy distance of 1000, so that total cost is 1003, which means it is never going to form a part of the shortest route. The third example is calculated by adding the distance AD to DE , which gives 8.

In the first step, we will calculate the value of every possible combination of 2 towns starting from A . There are 12 combinations: AB(C) , AB(D) , AB(E) , AC(B) , AC(D) , AC(E) , AD(B) , AD(C) , AD(E) , AE(B) , AE(C) , AE(D) .

These values will be stored for later use.

For step 2 we need to extend our notation slightly. We will use this to indicate the lowest cost from A to D via B and C (in either order):

To be clear, this could represent one of two paths - ABCD or ACBD whichever is shorter. We can express this as a minimum of two values:

This represents the 2 ways to get from A to D via B and C :

• We can travel from A to C via B , and then from C to D .
• We can travel from A to B via C , and then from B to D .

We have already calculated A to C via B (and all the other combinations) in step 1, so all we need to do is add the values and find the smallest. In this case:

• A to C via B is 10, C to D is 6, so the total is 16.
• A to B via C is 1003, B to D is 1000, so the total is 2003.

Clearly, ABCD is the best route.

We need to repeat this for every possible combination of travelling from A to x via y and z . There are, again, 12 combinations: AB(CD) , AB(CE) , AB(DE) , AC(BD) , AC(BE) , AC(DE) , AD(BC) , AD(BE) , AD(CE) , AE(BC) , AE(BD) , AE(CD) .

We store these values, along with the optimal path, for later use.

In the next step, we calculate the optimal route for travelling from A to any other town via 3 intermediate towns. For example, travelling from A to E via B , C , and D (in the optimal order) is written as:

There are 3 paths to do this:

• A to D via B and C , then from D to E .
• A to C via B and D , then from C to E .
• A to B via C and D , then from B to E .

We will choose the shortest of these three paths:

Again we have already calculated all the optimal intermediate paths. This time there are only 4 combinations we need to calculate: AB(CDE) , AC(BDE) , AD(BCE) , and AE(BCD) .

We are now in a position to calculate the optimal route for travelling from A back to A via all 4 other towns:

We need to evaluate each of the 4 options in step 3, adding on the extra distance to get back to A :

We can then choose the option that has the lowest total cost, and that will be the optimal route.

Performance

The performance of the Bellman–Held–Karp algorithm can be expressed in big-O notations as:

The time performance is approximately exponential. As the number of towns increases, the time taken will go up exponentially - each time an extra town is added, the time taken will double. We are ignoring the term in n squared because the exponential term is the most significant part.

Exponential growth is still quite bad, but it is far better than the factorial growth of the brute-force algorithm.

It is also important to notice that the algorithm requires memory to store the intermediate results, which also goes up approximately exponentially. The brute force algorithm doesn't have any significant memory requirements. However, that is usually an acceptable trade-off for a much better time performance.

The stages above describe how the algorithm works at a high level. We haven't gone into great detail about exactly how the algorithm keeps track of the various stages. Over the years since its discovery, a lot of work has been put into optimising the implementation. Optimising the implementation won't change the time complexity, which will still be roughly exponential. However, it might make the algorithm run several times faster than a poor implementation.

We won't cover this in detail, but if you ever need to use this algorithm for a serious purpose, it is worth considering using an existing, well-optimised implementation rather than trying to write it yourself. Unless you are just doing it for fun!

Other algorithms

Even the Bellman–Held–Karp algorithm has poor performance for modestly large numbers of towns. 100 towns, for example, would be well beyond the capabilities of a modern PC.

There are various heuristic algorithms that are capable of finding a good solution, but not necessarily the best possible solution, in a reasonable amount of time. I hope to cover these in a future article.

• Adjacency matrices
• The seven bridges of Königsberg
• Permutation matrices and graphs
• Dijkstra's algorithm

Join the GraphicMaths Newletter

Sign up using this form to receive an email when new content is added:

Popular tags

adder adjacency matrix alu and gate angle area argand diagram binary maths cartesian equation chain rule chord circle cofactor combinations complex modulus complex polygon complex power complex root cosh cosine cosine rule cpu cube decagon demorgans law derivative determinant diagonal directrix dodecagon eigenvalue eigenvector ellipse equilateral triangle eulers formula exponent exponential exterior angle first principles flip-flop focus gabriels horn gradient graph hendecagon heptagon hexagon horizontal hyperbola hyperbolic function hyperbolic functions infinity integration by parts integration by substitution interior angle inverse hyperbolic function inverse matrix irregular polygon isosceles trapezium isosceles triangle kite koch curve l system line integral locus maclaurin series major axis matrix matrix algebra mean minor axis nand gate newton raphson method nonagon nor gate normal normal distribution not gate octagon or gate parabola parallelogram parametric equation pentagon perimeter permutations polar coordinates polynomial power probability probability distribution product rule pythagoras proof quadrilateral radians radius rectangle regular polygon rhombus root set set-reset flip-flop sine sine rule sinh sloping lines solving equations solving triangles square standard curves standard deviation star polygon statistics straight line graphs surface of revolution symmetry tangent tanh transformation transformations trapezium triangle turtle graphics variance vertical volume of revolution xnor gate xor gate

• Graph theory
• 7 bridges of Königsberg
• Binary numbers

Key Products

• Route Optimization API

Optimize routing, task allocation and dispatch

• Directions and Distance Matrix API

Calculate accurate ETAs, distances and directions

• Navigation API & SDKs

Provide turn-by-turn navigation instructions

• Live Tracking API & SDKs

Track and manage assets in real time

• All Products

Product Demos

See NextBillion.ai APIs & SDKs In action

• Integrations

Easily integrate our products with your tools

Platform Overview

Learn about how Nextbillion.ai's platform is designed

Routing Customizations

Learn about NextBillion.ai's routing & map customizations capabilities

Supply Chain & Logistics

Get regulation-compliant truck routes

• Fleet Management

Solve fleet tracking, routing and navigation

• Last-Mile Delivery

Maximize fleet utilization with optimal routes

• On-Demand Delivery

Real-time ETA calculation

• Middle Mile Delivery

Real-time ETA Calculation

• Ride Hailing

Optimized routes for cab services

• Non-Emergency Medical Transport

Optimize routing and dispatch

Field Workforce

• Field Services

Automate field service scheduling

• Waste Collection

Efficient route planning with road restrictions

BY BUSINESS TYPE

Logistics technology providers

Fleet owners

BY LOGISTICS TYPE

Long haul trucking

Middle-mile logistics

Last-mile delivery

Urban mobility

Field services

Non-emergency transportation

See NextBillion.ai APIs & SDKs in Action

• Case Studies

Discover what customers are building in real time with NextBillion.ai

Get in-depth and detailed insights

• Product Updates

Latest product releases and enhancements

Navigate the spatial world with engaging and informative content

NextBillion.ai vs. Google Cloud Fleet Routing

Experience a more powerful optimization and scheduling platform, better optimized routes, advanced integration capabilities and flexible pricing with NextBillion.ai.

• API Documentation

Comprehensive API guides and references

Interactive API examples

Integrate tools you use to run your business

• Technical Blogs

Deep-dive into the technical details

Get quick answers to common queries

FEATURED TECHNICAL BLOG

How to Implement Route Optimization API using Python

Learn how to implement route optimization for vehicle fleet management using python in this comprehensive tutorial.

ROUTE OPTIMIZATION API

API Reference

DISTANCE MATRIX API

Navigation api & sdk.

Android SDK

Flutter SDK

Documentation

Integration

NEXTBILLION.AI

Partner with us

Our story, vision and mission

Meet our tribe

Latest scoop on product updates, partnerships and more

Come join us - see open positions

Reach out to us for any product- or media-related queries

For support queries, write to us at

To partner with us, contact us at

For all media-related queries, reach out to us at

For all career-related queries, reach out to us at

• Request a Demo

Table of Contents

Best Algorithms for the Traveling Salesman Problem

• March 15, 2024

What is a Traveling Salesman Problem?

In the field of combinatorial optimization, the Traveling Salesman Problem (TSP) is a well-known puzzle with applications ranging from manufacturing and circuit design to logistics and transportation. The goal of cost-effectiveness and efficiency has made it necessary for businesses and industries to identify the best TSP solutions. It’s not just an academic issue, either. Using route optimization algorithms to find more profitable routes for delivery companies also lowers greenhouse gas emissions since fewer miles are traveled.

In this technical blog, we’ll examine some top algorithms for solving the Traveling Salesman Problem and describe their advantages, disadvantages, and practical uses.

Explore NextBillion.ai’s Route Optimization API , which uses advanced algorithms to solve TSP in real-world scenarios.

Brute Force Algorithm

The simplest method for solving the TSP is the brute force algorithm. It includes looking at every way the cities could be scheduled and figuring out how far away each approach is overall. Since it ensures that the best solution will be found, it is not useful for large-scale situations due to its time complexity, which increases equally with the number of cities.

This is a detailed explanation of how the TSP is solved by the brute force algorithm:

Create Every Permutation: Make every combination of the cities that is possible. There are a total of n! permutations to think about for n cities. Every combination shows a possible sequence where the salesman could visit the cities.

Determine the Total Distance for Every Combination: Add up the distances between each city in the permutation to find the overall distance traveled for each one. To finish the trip, consider the time from the final city to the starting point.

Determine the Best Option: Observe which permutation produces the smallest total distance and record it. This permutation represents the ideal tour. Return the most effective permutation to the TSP as the solution after examining every option.

Give back the best answer possible: Return the most effective permutation to the TSP as the solution after all possible combinations have been examined.

Even though this implementation gives an exact solution for the TSP, it becomes costly to compute for larger instances due to its time complexity, which increases factorially with the number of cities. 

The Branch-and-Bound Method

The Branch-and-Bound method can be used to solve the Traveling Salesman Problem (TSP) and other combinatorial optimization problems. To effectively find a suitable space and the best answer, divide-and-conquer strategies are combined with eliminating less-than-ideal solutions.

This is how the Branch and Bound method for the Traveling Salesman Problem works:

Start : First, give a simple answer. You could find this by starting with an empty tour or using a heuristic method.

Limit Calculation : Find the lowest total cost of the current partial solution. This limit shows the least amount of money needed to finish the tour.

Divide : Select a variable that is associated with the subsequent stage of the tour. This could mean picking out the next city to visit.

When making branches, think about the possible values for the variable you’ve chosen. Each branch stands for a different choice or option.

Cutting down : If a branch’s lower bound is higher than the best-known solution right now, cut it because you know that it can’t lead to the best solution.

Exploration : Keep using the branch-and-bound method to look into the other branches. Keep cutting and branching until all of your options have been thought through.

New Ideal Solution : Save the best solution you found while doing research. You should change the known one if a new, cheaper solution comes along.

Termination : Continue investigating until all possible paths have been considered and no more choices exist that could lead to a better solution. End the algorithm when all possible outcomes have been studied.

Selecting the order in which to visit the cities is one of the decision variables for the Traveling Salesman Problem. Usually, methods like the Held-Karp lower bound are used to calculate the lower bound. The technique identifies and cuts branches that are likely to result in less-than-ideal solutions as it carefully investigates various combinations of cities.

The Nearest Neighbor Method

A heuristic algorithm called the Nearest Neighbor method estimates solutions to the Traveling Salesman Problem (TSP). In contrast to exact methods like brute force or dynamic programming, which always get the best results, the Nearest Neighbor method finds a quick and reasonable solution by making local, greedy choices.

Here is a detailed explanation of how the nearest-neighbor method solves the TSP problem:

Starting Point : Pick a city randomly to be the tour’s starting point.

Picking Something Greedy: Select the next city on the tour to visit at each stage based on how close the current city is to the not-explored city. Usually, a selected measurement is used to calculate the distance between cities (e.g., Euclidean distance).

Go and Mark: Visit the closest city you picked, add it to your tour, and mark it as observed.

Additionally: Continue this manner until every city has been visited at least once.

Go Back to the Beginning City: After visiting all the other cities, return to the starting city to finish the tour. 

The nearest-neighbor method’s foundation is making locally optimal choices at each stage and hoping that the sum of these choices will produce a reasonable overall solution. Compared to exact algorithms, this greedy approach drastically lowers the level of computation required, which makes it appropriate for relatively large cases of the TSP.

Ant Colony Optimization

ACO, or Ant Colony Optimization, is a metaheuristic algorithm that draws inspiration from ants’ seeking habits. It works very well for resolving a combination of optimization issues, such as the TSP (Traveling Salesman Problem). The idea behind ACO is to imitate ant colonies’ chemical trail communication to determine the best routes.

Ant Colony Optimization provides the following solution for the Traveling Salesman Problem:

Starting Point: A population of synthetic ants should be planted in a random starting city. Every ant is a possible solution for the TSP.

Initialization of The scents: Give each edge in the problem space (connections between cities) an initial amount of synthetic pheromone. The artificial ants communicate with one another via the fragrance. 

Ant Motion: Each ant creates a tour by constantly selecting the next city to visit using a combination of fragrance levels and a heuristic function.

The quantity of fragrance on the edge that links the candidate city to the current city, as well as a heuristic measure that could be based on factors like distance between cities, impact the chances of selecting a specific city.

Ants mimic how real ants use chemical trails for communication by following paths with higher fragrance levels.

Update on Pheromones: The pheromone concentration on every edge is updated once every ant has finished traveling.

The update involves placing fragrances on the borders of the best tours and evaporating existing fragrances to copy the natural breakdown of chemical paths, which is intended to encourage the search for successful paths.

Repetition: For the fixed number of cycles or until a shift standard is satisfied, repeat the steps of ant movement, fragrance update, and tour construction.

Building Solution : After a few iterations, the artificial ants develop an answer, which is considered the algorithm’s outcome. This solution approximates the most efficient TSP tour.

Enhancement: To improve progress and solution quality, the process can be optimized by adjusting parameters like the influence of the heuristic function and the rate at which fragrances evaporate.

Ant Colony Optimization is excellent at solving TSP cases by using the ant population’s group ability. By striking a balance between exploration and exploitation, the algorithm can find potential paths and take advantage of success. It is a well-liked option in the heuristics field since it has been effectively used to solve various optimization issues.

Genetic Algorithm

Genetic Algorithms (GAs) are optimization algorithms derived from the concepts of genetics and natural selection. These algorithms imitate evolution to find predictions for complex problems, such as the Traveling Salesman Problem (TSP). 

Here is how genetic algorithms resolve the TSP:

Starting Point: select a starting group of possible TSP solutions. Every possible tour that visits every city exactly once is represented by each solution.

Assessment: Examine each solution’s fitness within the population. Fitness is commonly defined in the TSP environment as the opposite of the total distance traveled. Tour length is a determining factor in fitness scores.

Choice: Choose people from the population to be the parents of the following generation. Each person’s fitness level determines the likelihood of selection. More fit solutions have a higher chance of being selected.

Transformation (Recombination): To produce offspring, perform crossover, or recombination, on pairs of chosen parents. To create new solutions, crossover entails sharing information between parent solutions.

Crossover can be applied in various ways for TSP, such as order crossover (OX) or partially mapped crossover (PMX), to guarantee that the resulting tours preserve the authenticity of city visits.

Change: Change some of the offspring solutions to introduce arbitrary changes. A mutation can involve flipping two cities or changing the order of a subset of cities.

Mutations add diversity to the population when discovering new regions of the solution space. 

Substitute: Parents and children together make up the new generation of solutions that will replace the old ones. A portion of the top-performing solutions from the previous generation may be retained in the new generation as part of a privileged replacement process.

Finalization: For a predetermined number of generations or until a convergence criterion is satisfied, repeat the selection, crossover, mutation, and replacement processes. 

Enhancement: Modify variables like population size, crossover rate, and mutation rate to maximize the algorithm’s capacity to identify excellent TSP solutions.

When it comes to optimizing combinations, genetic algorithms are exceptional at sifting through big solution spaces and identifying superior answers. Because of their capacity to duplicate natural evolution, they can adjust to the TSP’s structure and find almost ideal tours. GAs are an effective tool in the field of evolutionary computation because they have been successfully applied to a wide range of optimization problems.

NextBillion.ai offers advanced Route Optimization API that solves real-life TSP and VRP problems, which can be easily integrated with your applications. 

Book a demo Today!

In this Article

About author.

Rishabh is a freelance technical writer based in India. He is a technology enthusiast who loves working in the B2B tech space.

It is not possible to solve the Traveling Salesman Problem with Dijkstra’s algorithm. Dijkstra’s algorithm, a single-source shortest path algorithm, finds the shortest possible route from a given source node to every other node in a weighted graph. In comparison, the Traveling Salesman Problem looks for the quickest route that stops in every city exactly once before returning to the starting point.

The term “traveling salesman” refers to a scenario where a salesperson visits different cities to sell goods or services. The goal of this problem is to find the shortest route that goes to each city once and returns to the starting point. It is a fundamental problem in algorithmic optimization to determine the best order of city trips and minimize travel time or distance.

“Route salesman” or just “sales representative” are other terms for a traveling salesman. These people go to various places to sell goods and services to customers. The traveling salesman, who determines the shortest route to visit multiple cities, is often referred to as a “touring agent” or simply as the “salesman” in the context of mathematical optimization.

The minimum distance a salesman needs to visit each city exactly once and then return to the starting city is known as the shortest distance in the Traveling Salesman Problem (TSP). It stands for the ideal tour duration that reduces the total travel distance. The goal of solving the TSP, an essential issue in combinatorial optimization, is finding the shortest distance.

Try RoadWarrior free for 7 days

Solving the Traveling Salesman Problem

Get home early with RoadWarrior.

Enter your stops, optimize your routes, manage your team – quickly and efficiently.

Imagine a salesman who needs to visit multiple cities, but he wants to minimize the distance traveled and return to the starting point. This classic problem, known as the Traveling Salesman Problem (TSP), has been a subject of study for over a century. The applications of TSP are widespread, from logistics and agriculture to astronomy and computer-generated art. In this blog post, we will delve into the world of the Traveling Salesman Problem, exploring its history, algorithms, and real-world applications.

Short Summary

• The Traveling Salesman Problem is a complex problem of finding an optimal route for a round trip.
• Solutions to the TSP include NP-hard classification, brute force approach, dynamic programming and Christofides’ Algorithm.
• Route planning software such as OptimoRoute provide businesses with efficient tools for tackling the TSP, thereby improving their operations and saving resources.

Understanding the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a problem of determining the most efficient route for a round trip, with the objective of maintaining the minimum cost and distance traveled. It serves as a foundational problem to test the limits of efficient computation in theoretical computer science.

The salesman’s objective in the TSP is to find a minimum weight Hamiltonian cycle, which maintains both the travel costs and the distance traveled at a minimum.

Theoretical Background

The TSP is classified as an NP-hard problem. This shows that the number of solution sequences grows rapidly with the number of cities. The brute force approach to resolving the TSP involves examining each round-trip route to ascertain the shortest one. However, as the number of cities increases, the number of round-trips to check can quickly surpass the capability of the most powerful computers. This limitation has led to the development of more sophisticated algorithms to tackle the TSP, such as dynamic programming and approximation algorithms.

The Hamiltonian Cycle Problem, also known as the Hamiltonian cycle problem, inquires whether there exists a closed walk in a graph that visits each vertex precisely once and is closely related to the TSP. Both problems have been studied extensively by computer scientists due to their implications in complexity theory and the P versus NP problem.

Optimal vs. Approximate Solutions

In solving the TSP, there is a distinction between optimal solutions and approximate solutions. Optimal solutions are the most advantageous route, while approximate solutions are round-trip routes whose lengths approach that of the most advantageous route. The brute force approach involves determining every potential solution and subsequently selecting the most advantageous one. However, this method is computationally intractable for large TSP instances.

One notable approximate solution is Christofides’ algorithm, which begins by determining the shortest spanning tree and subsequently converting it into a round-trip route. This algorithm guarantees a response that is, at most, 1.5 times the optimal solution. While not always yielding the optimal solution, approximate algorithms like Christofides’ algorithm provide a more feasible approach to solving the TSP.

Evolution of TSP Algorithms

TSP algorithms have been in existence since the 1950s, when the initial brute force approach was formulated. Subsequently, more sophisticated techniques such as dynamic programming and Christofides’ algorithm have been developed. These advanced algorithms have enabled researchers and practitioners to find near-optimal solutions to the TSP more quickly and efficiently.

By leveraging these algorithms, it is possible to solve the TSP in a fraction of the time.

Brute Force Approach

The brute force approach to TSP involves attempting all potential solutions, making it the most time-consuming and expensive method. As the number of destinations increases, the number of roundtrips likewise increases exponentially, rendering it computationally intractable even for the most powerful computers. Therefore, the brute force approach is not considered to be a viable solution for large TSP instances.

Despite its limitations, the brute force approach serves an important role in the history of TSP algorithms. It represents the initial attempt to solve the TSP and laid the groundwork for the development of more advanced and efficient algorithms.

Dynamic Programming

Dynamic programming is a technique employed to address intricate issues by segmenting them into more manageable subproblems and resolving them one at a time. It is regularly utilized to resolve the Traveling Salesman Problem due to its ability to avoid redundant calculations and identify the shortest route that visits all cities exactly once. The dynamic programming approach is more scalable than the brute force approach, as it can be employed to solve problems of any size.

However, dynamic programming is not without its limitations. It can be computationally expensive and time-consuming, as it necessitates solving a substantial number of subproblems. Despite these drawbacks, dynamic programming remains a popular and effective method for solving the TSP.

Christofides’ Algorithm

Christofides’ algorithm is an algorithm for obtaining approximate solutions to the Traveling Salesman Problem. It involves constructing a minimum spanning tree and then discovering a minimum-weight perfect matching on the odd-degree vertices of the tree. This algorithm, developed in the 1970s, utilizes a combination of graph theory and heuristics to address the TSP.

The significance of Christofides’ algorithm lies in its ability to yield routes that are guaranteed to be no more than 50 percent longer than the shortest route. While it may not always provide the optimal solution, its development marked a substantial improvement in the pursuit of efficient TSP algorithms.

Recent Advances in TSP Algorithms

In recent years, computer scientists have made significant advancements in TSP algorithms. These breakthroughs include:

• Approximation algorithms
• Metaheuristic approaches
• Local search operators
• Anytime Automatic Algorithm Selection

These cutting-edge algorithms have enabled researchers to find even more efficient solutions to the TSP, further demonstrating the importance of continued research and development in this area.

Geometry of Polynomials

Oveis Gharan and Nathan Klein used the geometry of polynomials approach to solve the TSP by representing the problem as a polynomial with variables corresponding to the edges between all the cities. This approach permits the utilization of geometric techniques and algorithms to discover an optimal or approximate solution to the problem, including determining the starting and ending point of the route.

This innovative method showcases the potential for leveraging mathematical techniques and geometrical properties in solving the TSP. As research progresses, it is expected that even more efficient algorithms and approaches will be developed, further pushing the boundaries of our understanding of the TSP.

Fractional Solutions and Rounding Techniques

Amin Saberi and Arash Asadpour developed a general rounding technique that employs randomness in an attempt to select a whole-number solution that preserves as many characteristics of the fractional solution as possible. The use of fractional solutions and rounding techniques can be utilized to construct effective approximation algorithms for the TSP.

Saberi, Gharan, and Singh implemented this general rounding technique to formulate a new approximation algorithm for the TSP. As computer scientists continue to explore new approaches and techniques, it is likely that even more powerful and efficient algorithms will be developed to tackle the complex TSP.

Practical Applications of TSP Solutions

TSP solutions are employed in a variety of industries, including logistics, astronomy, agriculture, and vehicle routing. Its applications range from planning efficient delivery routes and optimizing telescope trajectories to designing microchips and creating computer-generated art.

The widespread use of TSP solutions underscores the importance of continued research and development in this area, as advancements in TSP algorithms have the potential to positively impact numerous sectors.

Route Optimization

Route optimization is the process of determining the most efficient routes for various applications. In logistics, for example, TSP solutions can assist in enhancing efficiency in the last mile. By employing optimization techniques, businesses can reduce the number of stops, minimize total distance traveled, and ultimately save on fuel and labor costs.

The Vehicle Routing Problem (VRP), a generalized form of the TSP, focuses on discovering the most efficient set of routes or paths for multiple vehicles and hundreds of delivery locations. By utilizing TSP solutions and optimization techniques, companies can greatly improve their overall efficiency and productivity, leading to significant cost savings and improved customer service.

Last-Mile Delivery Challenges

The last-mile delivery problem refers to the final stage of a supply chain. It involves transporting goods from a transportation hub, such as a depot or warehouse, to the ultimate recipient. TSP solutions play a crucial role in addressing this challenge by optimizing delivery routes, reducing the number of stops, and minimizing total distance traveled.

For example, the Traveling Salesman Problem with Time Windows (TSPTW) approach considers specific time constraints for each delivery location, ensuring that deliveries are made within a specified time frame. By employing TSP algorithms and optimization techniques, businesses can:

• Overcome last-mile delivery challenges
• Improve overall efficiency
• Achieve cost savings
• Enhance customer satisfaction

TSP Solvers for Real-World Problems

Modern TSP solvers use advanced algorithms to provide near-optimal solutions quickly. These solvers include the routingpy library, real-life TSP and VRP solvers, and state-of-the-art TSP solvers based on local search.

By leveraging these powerful algorithms, businesses and researchers can tackle real-world TSP problems with greater efficiency and accuracy.

Branch and Bound Method

The branch and bound method is an algorithm utilized to address optimization problems, such as the TSP. It functions by exhaustively examining all potential solutions and identifying the most advantageous one. By dividing the problem into smaller subproblems and determining the optimal solution for each subproblem, the branch and bound method permits a more efficient and precise resolution to the problem.

Although the branch and bound method is computationally expensive, it has several advantages, such as being relatively straightforward to implement and capable of addressing large-scale problems. Its application in solving real-life TSP instances showcases its potential in effectively optimizing routes and minimizing costs.

Nearest Neighbor Method

The Nearest Neighbor algorithm is a greedy algorithm that finds the closest unvisited node and adds it to the sequencing until all nodes are included in the tour. While it rarely yields the optimal solution, particularly for large and intricate instances, it can be utilized effectively as a means to generate an initial feasible solution quickly.

This initial solution can then be supplied into a more sophisticated local search algorithm for further optimization. The Nearest Neighbor algorithm demonstrates that even relatively simple algorithms can play a valuable role in providing quick and feasible solutions to real-world TSP problems.

Route Planning Software for TSP

Utilizing route planning software to solve TSP problems in various industries offers numerous benefits. These software solutions, such as Route4Me, leverage advanced algorithms like Dijkstra’s Algorithm to quickly identify the most efficient route for a team.

By implementing route planning software, businesses can improve efficiency, reduce costs, and enhance customer satisfaction.

Advantages of Route Planning Software

Route planning software can help businesses in the following ways:

• Optimize routes
• Decrease the number of stops
• Minimize the total distance traveled
• Increase efficiency and productivity
• Reduce fuel and labor costs by optimizing routes and minimizing the time spent on route planning and decision-making.

Improved customer service is another benefit of route planning software. By optimizing routes and ensuring timely deliveries, businesses can enhance their reputation and build customer loyalty. In an increasingly competitive market, utilizing route planning software can give businesses a critical edge in delivering exceptional service and maintaining customer satisfaction.

Examples of Route Planning Solutions

There are numerous route planning solutions available for addressing the TSP, including vehicle routing software, optimization algorithms, and Excel sheets with order details and addresses. These solutions offer businesses a variety of options to choose from, depending on their specific needs and requirements.

Some examples of popular route planning software include OptimoRoute and Straightaway. These software solutions can help businesses tackle TSP problems efficiently, saving time and resources while improving overall operations. By leveraging advanced algorithms and powerful tools, route planning software provides a valuable solution for businesses looking to optimize their logistics and delivery processes.

Throughout this blog post, we have explored the fascinating world of the Traveling Salesman Problem, delving into its history, algorithms, and practical applications. From the early brute force approach to modern approximation algorithms and route planning software, the TSP continues to challenge and inspire researchers, computer scientists, and businesses alike. As we continue to push the boundaries of our understanding of the TSP, the potential for new and innovative solutions to real-world problems remains vast and exciting.

Frequently Asked Questions

Has anyone solved the traveling salesman problem.

No one has successfully come up with an algorithm to efficiently solve every traveling salesman problem, despite notable progress being made over the years.

What is the Traveling Salesman Problem (TSP)?

The Traveling Salesman Problem is an optimization problem that seeks to determine the most efficient route for a round trip, with the aim of minimizing cost and distance traveled.

What are some examples of industries that benefit from TSP solutions?

TSP solutions are widely used in industries such as logistics, astronomy, agriculture, and vehicle routing, providing a range of benefits.

What is the difference between optimal and approximate solutions in TSP?

Optimal solutions in TSP provide the most advantageous route, while approximate solutions offer a similar route whose length is close to that of the optimal solution.

These solutions can be used to solve a variety of problems, such as finding the shortest route between two cities or the most efficient way to deliver goods. They can also be used to optimize the use of resources, such as time and money.

What is an example of a modern TSP solver?

Routingpy is an example of a modern TSP solver, providing comprehensive tools to address the Traveling Salesman Problem and Vehicle Routing Problem.

It offers a range of features, including an intuitive user interface, fast computation times, and a wide range of optimization algorithms. It also provides a comprehensive set of tools for analyzing and visualizing the results of the optimization process.

Related Articles

Walmart spark delivery: a lucrative opportunity for independent contractors.

11 minute read

Android Route Planning Simplified: The Best Apps on the Market

7 minute read

Best Route Planners for iPhone: Navigating the App Choices

The Enlightened Mindset

Exploring the World of Knowledge and Understanding

Welcome to the world's first fully AI generated website!

Exploring the Travelling Salesman Problem: Benefits, Challenges, and Solutions

By Happy Sharer

Introduction

The Travelling Salesman Problem (TSP) is an optimization problem in which a salesperson needs to visit a set of locations in the most efficient way possible. This problem has been studied for centuries, with numerous applications in fields such as mathematics, computer science, operations research, and artificial intelligence. In this article, we will explore the definition of the Travelling Salesman Problem, its components and challenges, and how it can be solved using different algorithms and approaches.

Exploring the Basics of the Travelling Salesman Problem

The Travelling Salesman Problem is defined as “the problem of finding the shortest route that visits each location exactly once and returns to the starting point” ( The Concise Encyclopedia of Mathematics , 2004). In other words, the goal of the problem is to find the most efficient or cost-effective route for a salesperson to take while visiting a given set of locations.

When attempting to solve the Travelling Salesman Problem, there are several components to consider. First, the number of locations to be visited must be determined. Additionally, the exact distances between each location must be known in order to accurately calculate the total distance of the route. Finally, the starting and ending points must be established so that the route can be completed in a loop.

Solving the Travelling Salesman Problem can be quite challenging due to its complexity and the sheer number of possible routes that need to be evaluated. As the number of locations increases, the number of possible routes grows exponentially, making it difficult to find the optimal solution in a reasonable amount of time. Thus, it is important to use efficient algorithms and approaches when attempting to solve the problem.

Solving the Travelling Salesman Problem: Algorithms and Approaches

There are several algorithms and approaches that can be used to solve the Travelling Salesman Problem. The most common algorithms include brute force, dynamic programming, branch and bound, and heuristics. Each of these algorithms has its own pros and cons, and they can be used in combination to obtain the best results.

The brute force algorithm is one of the simplest solutions for the Travelling Salesman Problem. This approach involves systematically evaluating every possible route until the optimal solution is found. While this method is effective, it can be extremely time consuming and computationally expensive, especially for large datasets.

Dynamic programming is another popular algorithm for solving the Travelling Salesman Problem. This approach involves breaking down the problem into smaller, subproblems that can be more easily solved. By solving each of the subproblems individually, the overall problem can be solved more quickly and efficiently. However, dynamic programming can also be computationally expensive and may not always yield the optimal solution.

The branch and bound algorithm is another approach that can be used to solve the Travelling Salesman Problem. This algorithm works by building a search tree and gradually reducing the number of possible solutions until the optimal solution is found. This approach is generally more efficient than brute force, but it can still be computationally intensive.

Finally, heuristics can be used to solve the Travelling Salesman Problem. Heuristics involve using approximate methods to quickly obtain a good solution without necessarily finding the optimal solution. These techniques are often faster and more efficient than other algorithms, but they may not always yield the best results.

How to Tackle the Travelling Salesman Problem with Artificial Intelligence

Artificial intelligence (AI) can also be used to solve the Travelling Salesman Problem. AI-based solutions typically involve using machine learning algorithms to analyze large datasets and identify patterns that can be used to generate efficient routes. AI-based solutions are often more accurate and faster than traditional algorithms, making them ideal for solving complex optimization problems like the Travelling Salesman Problem.

One example of an AI-based solution for the Travelling Salesman Problem is Google Maps’ “Optimized Route” feature. This feature uses AI algorithms to analyze data from millions of users and identify the quickest route between multiple destinations. It then provides users with an optimized route that is tailored to their specific needs.

The Impact of the Travelling Salesman Problem on Businesses and Industries

The Travelling Salesman Problem has become increasingly important for businesses and industries around the world. Solving the problem can help companies save time and money by providing them with the most efficient routes for their employees. Additionally, businesses can use AI-based solutions to automate the process of route optimization and ensure that their teams are taking the most efficient routes.

For example, UPS has implemented AI-based solutions to optimize its package delivery routes. By using AI algorithms to analyze data from millions of packages, UPS was able to reduce the amount of time it takes to deliver packages by up to 30%. Similarly, Amazon has used AI to optimize its warehouse operations, resulting in improved efficiency and reduced costs.

Examining the Benefits and Drawbacks of the Travelling Salesman Problem

Solving the Travelling Salesman Problem can have both advantages and disadvantages. On the plus side, finding the most efficient route can save businesses time and money, and AI-based solutions can make the process even more efficient. Additionally, the use of AI can help businesses automate the process of route optimization and provide more accurate results.

On the downside, solving the Travelling Salesman Problem can be computationally expensive, especially for large datasets. Additionally, AI-based solutions can be costly and require significant upfront investments. Finally, the results of the problem may not always be perfect, as there may be other factors to consider when determining the best route.

The Travelling Salesman Problem is an optimization problem in which a salesperson needs to visit a set of locations in the most efficient way possible. The problem can be solved using various algorithms and approaches, including brute force, dynamic programming, branch and bound, and heuristics. AI-based solutions are also becoming increasingly popular, as they can provide more accurate and efficient results. Ultimately, businesses and industries around the world have benefited from solving the Travelling Salesman Problem, but it is important to consider the benefits and drawbacks before investing in a solution.

The Travelling Salesman Problem is an interesting and complex problem with numerous applications in fields such as mathematics, computer science, and operations research. With the right strategies and tools, businesses can benefit from the problem by achieving greater efficiency and savings.

(Note: Is this article not meeting your expectations? Do you have knowledge or insights to share? Unlock new opportunities and expand your reach by joining our authors team. Click Registration to join us and share your expertise with our readers.)

Hi, I'm Happy Sharer and I love sharing interesting and useful knowledge with others. I have a passion for learning and enjoy explaining complex concepts in a simple way.

Related Post

Exploring japan: a comprehensive guide for your memorable journey, your ultimate guide to packing for a perfect trip to hawaii, the ultimate packing checklist: essentials for a week-long work trip, leave a reply cancel reply.

Your email address will not be published. Required fields are marked *

Expert Guide: Removing Gel Nail Polish at Home Safely

Trading crypto in bull and bear markets: a comprehensive examination of the differences, making croatia travel arrangements, make their day extra special: celebrate with a customized cake.

Solution of a Large-Scale Traveling-Salesman Problem

• First Online: 01 January 2009

Cite this chapter

• Vašek Chvátal 9 ,
• William Cook 10 ,
• George B. Dantzig ,
• Delbert R. Fulkerson &
• Selmer M. Johnson  

9023 Accesses

7 Citations

The RAND Corporation in the early 1950s contained “what may have been the most remarkable group of mathematicians working on optimization ever assembled” [6]: Arrow, Bellman, Dantzig, Flood, Ford, Fulkerson, Gale, Johnson, Nash, Orchard-Hays, Robinson, Shapley, Simon, Wagner, and other household names. Groups like this need their challenges. One of them appears to have been the traveling salesman problem (TSP) and particularly its instance of finding a shortest route through Washington, DC, and the 48 states [4, 7].

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
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview.  Download preview PDF.

G.B. Dantzig, Application of the simplex method to a transportation problem , Activity Analysis of Production and Allocation (T.C. Koopmans, ed.), Cowles Commission Monograph No. 13. JohnWiley & Sons, Inc., New York, N. Y.; Chapman & Hall, Ltd., London, 1951, pp. 359–373.

Google Scholar  

G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson, Solution of a large scale traveling salesman problem , Technical Report P-510, RAND Corporation, Santa Monica, California, USA, 1954.

G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson, On a linear-programming, combinatorial approach to the traveling-salesman problem , Operations Research 7 (1959) 58–66.

Article   MathSciNet   Google Scholar  

M.M. Flood, Merrill Flood (with Albert Tucker) , Interview of Merrill Flood in San Francisco on 14 May 1984, The Princeton Mathematics Community in the 1930s, Transcript Number 11 (PMC11), Princeton University, 1984.

R.E. Gomory, Outline of an algorithm for integer solutions to linear programs , Bulletin of the American Mathematical Society 64 (1958) 275–278.

M. Gröotschel and G.L. Nemhauser, George Dantzig’s contributions to integer programming , Discrete Optimization 5 (2008) 168–173.

J. Robinson, On the Hamiltonian game (a traveling salesman problem) , RAND ResearchMemorandum RM-303, RAND Corporation, Santa Monica, California, USA, 1949. The following article originally appeared as:

Download references

Author information

Authors and affiliations.

Canada Research Chair in Combinatorial Optimization, Department of Computer Science and Software Engineering, Concordia University, Please Provide City, Canada

Vašek Chvátal

School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA

William Cook

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Vašek Chvátal .

Editor information

Editors and affiliations.

Inst. Informatik, Universität Köln, Pohligstr. 1, Köln, 50969, Germany

Michael Jünger

Fac. Sciences de Base (FSB), Ecole Polytechnique Fédérale de Lausanne, Lausanne, 1015, Switzerland

Thomas M. Liebling

Ensimag, Institut Polytechnique de Grenoble, avenue Félix Viallet 46, Grenoble CX 1, 38031, France

Denis Naddef

School of Industrial &, Georgia Institute of Technology, Ferst Drive NW., 765, Atlanta, 30332-0205, USA

George L. Nemhauser

IBM Corporation, Route 100 294, Somers, 10589, USA

William R. Pulleyblank

Inst. Informatik, Universität Heidelberg, Im Neuenheimer Feld 326, Heidelberg, 69120, Germany

Gerhard Reinelt

ed Informatica, CNR - Ist. Analisi dei Sistemi, Viale Manzoni 30, Roma, 00185, Italy

Giovanni Rinaldi

Center for Operations Reserach &, Université Catholique de Louvain, voie du Roman Pays 34, Leuven, 1348, Belgium

Laurence A. Wolsey

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this chapter

Chvátal, V., Cook, W., Dantzig, G.B., Fulkerson, D.R., Johnson, S.M. (2010). Solution of a Large-Scale Traveling-Salesman Problem. In: Jünger, M., et al. 50 Years of Integer Programming 1958-2008. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68279-0_1

Download citation

DOI : https://doi.org/10.1007/978-3-540-68279-0_1

Published : 06 November 2009

Publisher Name : Springer, Berlin, Heidelberg

Print ISBN : 978-3-540-68274-5

Online ISBN : 978-3-540-68279-0

eBook Packages : Mathematics and Statistics Mathematics and Statistics (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.

Click through the PLOS taxonomy to find articles in your field.

For more information about PLOS Subject Areas, click here .

Loading metrics

Open Access

Peer-reviewed

Research Article

Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic

Roles Conceptualization, Methodology, Software

Affiliation Engineering Academic Area, Autonomous University of Hidalgo, Pachuca, Hidalgo, Mexico

Roles Conceptualization, Data curation, Formal analysis, Investigation, Methodology, Validation, Writing – original draft, Writing – review & editing

* E-mail: [email protected]

Roles Conceptualization, Resources, Software, Validation, Writing – review & editing

Roles Software, Supervision

• Gustavo Erick Anaya Fuentes, 
• Eva Selene Hernández Gress, 
• Juan Carlos Seck Tuoh Mora, 
• Joselito Medina Marín

• Published: August 22, 2018
• https://doi.org/10.1371/journal.pone.0201868
• Reader Comments

This article finds feasible solutions to the travelling salesman problem, obtaining the route with the shortest distance to visit n cities just once, returning to the starting city. The problem addressed is clustering the cities, then using the NEH heuristic, which provides an initial solution that is refined using a modification of the metaheuristic Multi-Restart Iterated Local Search MRSILS ; finally, clusters are joined to end the route with the minimum distance to the travelling salesman problem. The contribution of this research is the use of the metaheuristic MRSILS , that in our knowledge had not been used to solve the travelling salesman problem using clusters. The main objective of this article is to demonstrate that the proposed algorithm is more efficient than Genetic Algorithms when clusters are used. To demonstrate the above, both algorithms are compared with some cases taken from the literature, also a comparison with the best-known results is done. In addition, statistical studies are made in the same conditions to demonstrate this fact. Our method obtains better results in all the 10 cases compared.

Citation: Anaya Fuentes GE, Hernández Gress ES, Seck Tuoh Mora JC, Medina Marín J (2018) Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic. PLoS ONE 13(8): e0201868. https://doi.org/10.1371/journal.pone.0201868

Editor: Lidia Adriana Braunstein, Universidad Nacional de Mar del Plata, ARGENTINA

Received: January 26, 2017; Accepted: July 24, 2018; Published: August 22, 2018

Copyright: © 2018 Fuentes et al. This is an open access article distributed under the terms of the Creative Commons Attribution License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Data Availability: The results and code program for the present study are available in the public repository figshare.com ( https://figshare.com/s/211103efe101fac7ddae ). Figshare repository data include the results in cost and computational time of 10 instances solved through CTSPMRSILS and GA with clusters summary in Table 24 in the Manuscript. A sheet of excel for every instance, 30, 50 and 100 runs were used in both methods and included in this repository ( https://figshare.com/s/211103efe101fac7ddae#/articles/6484118 ). Also, in this repository there are two codes in Matlab, one with Genetic Algorithms and clusters, the main function is Genclusters.m ( https://figshare.com/s/211103efe101fac7ddae#/articles/6459401 ); and the other is with CTSPMRSILS and clusters, the main function is Genclustersv3.m ( https://figshare.com/s/211103efe101fac7ddae#/articles/6459404 ). Both programs are with the distance matrix of eil76, but can be adapted for any of the instances of TSP founded in TSLIB.

Funding: This work was supported by National Council for Science and Technology (CONACYT) with project number CB-2014-237323, and the financial support for publication costs was provided by PRODEP publishing support program.

Competing interests: The authors have declared that no competing interest exist.

1 Introduction

Travelling Salesman Problem TSP is well known in the literature and is considered one of the most difficult problems to solve, besides being very useful to solve various problems in manufacturing. The first time who someone tried to solve this problem was addressed by Dantzig, Fulkerson and Johnson [ 1 ] algorithm on an IBM 7090 computer, the method used was Branch and Bound, through this method it was found that the average computational time was too high to be feasible to solve. Since then, TSP has been solved by various Metaheuristics such as Ant Colony ACO , Simulated Annealing RS , Genetic Algorithms GA , among others, but new algorithms continue to emerge, and it is interesting proven them in classic problems.

All the methods used to solve TSP have found a limit on their computational runtime, we attemting to solve problems with many cities or nodes [ 2 ], because this problem is NP Hard [ 3 ]. For this reason, the TSP remains a subject of current research to try new and different heuristic strategies. There are different applications in problems with a lot of nodes. For example, the Family Travel Salesman Problem, that is motivated by the order picking problem in warehouses where products of the same type are stored in different warehouses or in separate places in the same warehouse [ 4 ]. Other application of the TSP is in the technical approach to solve the fuel optimization problem in separated spacecraft interferometry missions [ 5 ]. Also, different problems can be converted to TSP with a lot of nodes, one of them is the Vehicle Routing Problem [ 6 ], and other is the Job Shop Scheduling Problem [ 7 ]; in the the last case a problem with 30 jobs and 10 machines is a TSP with 300 cities. Other applications are in Tas, Gendreau, Jabali and Laporte [ 8 ] and in Veenstra, Roodbergen, Vis and Coelho [ 9 ]. In a different topic, different clustering techniques have been used to solve problems with many nodes, such as clusters based in prototypes, centers, graphs and densities [ 10 ]. Some authors have already solved the TSP by clusters, see for example the work of Phienthrakul [ 11 ], what hence forth we will named as CTSP (Clustering the Traveling Salesman Problem). In this research, he solved the problem with Ant Colony, Simulated Annealing and Genetic Algorithms., but the best results that he obtained were with Genetic Algorithms.

Our proposal is the solution of CTSP applying a combination of heuristics as the NEH and a modification of the metaheuristic Multi Restart Iterated Local Search MRSILS [ 12 ], all these terms together will be named as CTSPMRILS (The Travelling Salesman Problem with Clusters, NE H and Multi Restart Iteration Local Search). Until today, no one who has solved it in this way has been found, and this is the innovative part. The approach in this paper is tested in 10 instances of Phienthrakul [ 11 ]. The CTSPMRILS finds satisfactory results in all the instances proved. The aim of this article is to demonstrate that the proposed algorithm CTSPMRILS is more efficient than Genetic Algorithms when clusters are used.

This article is structured as follows: section 2 shows the TSP background, the clustering techniques and their application in the TSP, and also some basic aspects related to the NEH heuristic and MRSILS ; section 3 presents the description and problem statement, where defines the problem solving in mathematical terms; section 4 describes the development of the proposed algorithm in this article; later in section 5 the results are presented; in section 6 a discussion of the results is provided. Finally, section 7 presents the conclusions of this research.

2 Background

2.1 the travelling salesman problem.

The TSP can be formally defined as follows (Buthainah, 2008). Let a network G = [ N , A , C ], that is N the set nodes, A the set of arcs, and C = [ c ij ] the cost matrix. That is, the cost of the trip since node i to node j . The TSP requires a Halmiltonian cycle in G of minimum cost, being a Hamiltonian cycle, one that passes to through each node i exactly once. TSP is a problem of permutation that aims to find the path of shorter length or minimum cost in an unguided graph than represents the cities or nodes to be visited. The TSP starts in a node, visiting all the nodes one by one to finally return to the initial node, in such a way must form routes and no sub-paths. The TSP can be modeled through Integer Programming [ 13 ] and in the symmetric case, Branch and Cut algorithms have been developed. Although the search for optimal solutions of large instances of the symmetric TSP via Branch and Cut have been reached, this effort is two-fold; one must invest in a relevant algorithmic and implementation effort. The implementation effort is unfortunately now far too high for a newcomer [ 14 ]. TSP is considered NP-complete and is one of the biggest challenges faced by analysts, even through various techniques that are available [ 15 ].

To deal with the complexity of the problem, TSP has been studied extensively with meta heuristics, see for example, the works of Dorigo [ 16 ] with colony of ants, Cerny [ 17 ] with the Monte Carlo Method; Jog et al. [ 18 ], Chattarjee et al. [ 19 ], Larrañaga et al.[ 20 ], Moon et al. [ 21 ], Fogel [ 22 ], Also, different versions of GA have been presented in Kurian, Mathew and Kumar [ 15 ] intended to improve efficiency in solving the TSP , so far without finding a method or technique that ensures finding the optimum in polynomial time. Current trends to solve TSP problems includes the Clustering Technique or solve the TSP separately generating smaller problems as described in the next section.

2.2 Clustering techniques

Arising from the difficulties in finding solutions for the TSP in feasible time, works such as Dutta and Bhattacharya [ 23 ] discusses various techniques of clustering based on policies and methods of clusters, they show the steps for the clustering process and discuss some important concepts related to class data and the characteristics of selection and evolution of the cluster, which is a term that has its beginnings in Amdahl's Law [ 24 ]. In addition, the results found by Dutta and Bhattacharya [ 23 ] indicate that clustering techniques can be classified into 7 groups: based on distances, densities, models, on pictures, in seeds, spectra and hierarchies used in data mining. Clustering has been used to solve different problems applied in different fields, for example Nizam [ 25 ], proposed clustering as a powerful control system voltage stability and presents a new technique for clustering called neural Kohonen network. The formation of these clusters can simplify the control voltage. Vijayalakshmi, Jayanavithraa, Ramya [ 26 ] observed in the field of genetics that are measured levels of thousands of genes simultaneously, using microarray technology. In this technology, genetic clusters approach is used to find genes with similar functions. Under this approach, several clustering algorithms are used in clusters; as proposed by Vijayalakshmi et al. [ 26 ], which is an automatic algorithm that provides the ability to find a strong global convergence towards an optimal solution.

Weiya, Guohui and Dan [ 27 ], proposed a novel method called cluster graph consistent approach, the solution obtained by this method is close to the optimal with a discrete solution. The different techniques of clustering are also analyzed for data mining by authors such as Saroj and Chaudhary [ 28 ]. Clusters group is a subject of active research in many fields such as statistics, identifying patterns and learning machines. Cluster analysis is an excellent tool to work with a lot of data.

Moreover, Kaur and Kaur [ 29 ] uses clustering in Data Mining by k- means clustering to divide the data into k clusters; Besides, Nadana and Shriram [ 30 ] proposed a methodology called Megadata based on a model of clustering for large data sets. The experimental results showed that it is possible to find a better quality of clusters without improving the computational time.

Kaur and Singh [ 31 ] proposed an advanced clustering algorithm to direct large data sets. This advanced method for clustering allows to measure the distance of each object, also requires a simple data structure for each iteration. Their experimental results proved that the advanced method of clustering algorithm can improve the effectiveness of the speed and accuracy of the algorithm by reducing the computational complexity.

Tavse and Khandelwal [ 32 ] classified data internet clusters for application in data transmission, achieving better efficiency, longer life and stability of the network, optimizing data classification. Refianti et al [ 33 ] compared two algorithms called: affinity propagation and k -means, both grouped data clusters. The data are regarding the timing of completion of the thesis students. The results show that the k -means algorithm provides more accurate results with cluster data and more effectively than affinity propagation , while this provides different values for the centroids after five tests. In the next section, clustering to find better solutions to the TSP is presented.

2.3 Clusters applied to the travelling salesman problem

Different methods and techniques have been used to solve the TSP clustered, as Lin-Kernighan proposed by Karapetyan and Gutin [ 34 ]. Also, the GA with clusters CA G presented recently at work Sivaraj, Ravichandran and Devipriya [ 35 ], who notes that using CAG manages to find the optimal solution in less time that standard GA named SGA , this was observed in three cases shown in Sivaraj et al. [ 35 ]. The latter author developed an unsupervised learning mechanism, used to group similar objects in clusters, ensuring that despite the different techniques for clustering that are available, there is a general strategy that works in the same way on different problems. However, the conclusion is that it is better to use simple mechanisms.

In the origins of the clusters Tsai and Chiu [ 36 ] proposed a very similar to CTSP method called hierarchical clustering, which adopts an ambitious strategy to gradually mix objects and build a classification structure called dendrogram. Nevertheless, the quality of its clusters is unreliable. To overcome the problem, a global optimum strategy for the construction of the dendrogram is to find the optimal circular route that minimizes the total distance to visit all objects along the arms of the dendrogram, which is modeled as a TSP and is solved using a method of search variable in the neighborhood. When the cluster dendrogram is modeled, it is based on information provided by the order. Through these experiments, the quality of this clustering method is superior to traditional methods.

Nagy and Negru [ 37 ] discussed methods to cluster which can be used to treat spatial and temporal patterns in a large amount of data. They use 55 cities to apply the methods of detection. His approach allows us to observe the existence of different spatial and temporal clusters.

Vishnupriya and Sagayaraj [ 38 ] implemented clustering algorithms for techniques used in data mining, making possible the analysis of data sets, using the algorithm k- means to calculate the value of the cost based on the Euclidean distance like TSP .

Nidhi [ 39 ] proposes the k- means algorithm for the problem of increasing data with several clusters generated dynamically and without repetition, which reduces the computational time, providing more accurate results. Therefore, the initial grouping is done with statistical data, using k -means. Then the next points, the largest distance between the centroid and the farthest point is used to define the next point that is in the cluster, repeating the process to cover the total data.

Derived from the works mentioned above, it becomes necessary to define a heuristic that may help to solve the TSP with feasible results, hence, in this article the use of NEH and MRSILS algorithms is proposed as a feasible alternative.

2.4 NEH y multi-restart iterated local search

Nawas, Enscore and Ham [ 40 ] proposed a heuristic called NEH which intends to solve the Job Shop Scheduling Problem, Liu Song and Wu [ 41 ] improved this algorithm with two techniques. First, to reduce the computational time per block properties are developed and introduced in the NEH algorithm to obtain a shorter the computational time. Second, tiebreaker rules are applied to obtain good solutions. The simulation results show that these two techniques improve the results obtained in the NEH Algorithm.

Mestría [ 42 ] also proposed a heuristic method to solve the CTSP , which it is a generalization of TSP where a set of nodes is divided into disjointed clusters with the aim of finding the minimum cost of the Hamiltonian cycle. Mestría, [ 42 ] developed two random descendants in the neighborhood, with iterated local search called ILS algorithm to solve the CTSP . The computational time obtained shows that the heuristic methods are competitive using software in parallel.

Grasas, Juan and Lorenzo [ 43 ] found that ILS is one of the most popular solutions using simple heuristics. ILS is recognized by many authors as relatively simple as well as having a structure capable of dealing with combinatorial optimization problems COPs . The ILS has been successfully applied to provide near optimal solutions for different problems of logistics, transportation, production etc. However, it has been designed to solve problems in deterministic scenarios, therefore, it does not reflect the actual stochastic nature of the systems.

Dong, Chen, Huang and Nowak [ 44 ] proposed the MRSILS to solved Flow Shop Scheduling Problem, MRSILS generates an initial solution as well as constructs in negligible time and the corresponding ILS performs. This is repeated until a termination criterion, it can be set as the maximum number of iterations for the local search procedure or the maximum allowable computational time.

Seck et al. [ 12 ] modifies the MRSILS algorithm with an uncomplicated process which generates minor changes by means of permutations for improving the initial solution before using MRSILS , then a minor variation is made in the MRSILS to obtain better performance. The experiments show that the new algorithms produce slightly better results than the original one.

Thus, it is proposed to try MRSILS and NEH heuristic to apply on clusters of the problem described below.

3 Description and problem statement

The TSP can be defined as follows: Find the shortest route for a sales person starting from a city, visiting each in a specific group of cities just once and returning to the starting point [ 45 ].

Anil, Bramel and Hertz [ 47 ] defines the CTSP considering ordering the clusters for TSP , where a traveling salesman starts and ends its journey in a specific city must visit a set of n points divided into k clusters not connected, the k points of that cluster are visited before the points of the cluster k+ 1 for k = 1,2,…, k–1 seeking the minimum total travel distance.

Given a complete undirected graph G = ( V , E ) where k+ 1 clusters denoted by C i ⊆ V , for each i = 0,1,2,…, k , preestablished. It is assumed that C i ∩ C j = 0 for all 1≤ i , j≤k , i≠j , and C 0 is denoted as a single node 0 ϵ V and may be a deposit C 0 = 0. The CTSP seeks to determine the minimum distance of commuter travel agent starting and ending in the same city and visiting each of them, which are referred to as V and are in one way. To solve this problem, Phienthrakul [ 11 ] proposed a technique called k -means, to group in clusters with the steps described below:

• Choose an integer value for k .
• Select k objects arbitrarily (use these as initial set of k centroids).
• Assign each of the objects to a cluster, which is closest to the centroid.
• Recalculate the centroid of k clusters.
• Repeat steps 3 and 4 until the centroids do not change more.

Another technique proposed by the author is called Gaussian Mixed Model applied by the normal distribution forming clusters. The model uses the Maximization Algorithm Hope EM [ 48 ], to adjust the Gaussian distribution of the data. The algorithm starts by defining the number of clusters k and selecting the settings k of Gaussian distributions

This article proposes to use k -means algorithm and recalculate the centroids by deducting the arithmetic mean of the coordinates X and Y , to obtain a new centroid and iterate until the centroids no change more, allowing the algorithm to be more efficient by using the arithmetic mean instead of a fit test that requires more steps.

4 Development

This article seeks to solve the TSP in combination with clusters, NEH and MRSILS , such combination henceforth it is called as CTSPMRSILS , which consist in grouping nodes in clusters to find the minimum distance in each of them, but unlike the proposed by Phienthrakul [ 11 ] it is modified to work with a proposed heuristic that provides solutions for each cluster with a combination of the NEH [ 49 ] and MR SILS algorithms, which is explained by applying it to the instance burma 14 instance of TSPLIB [ 50 ], as shown in the following steps:

• PPT PowerPoint slide
• PNG larger image
• TIFF original image

https://doi.org/10.1371/journal.pone.0201868.t001

• Centroid 1 = (22, 98);
• Centroid 2 = (18, 97);
• Centroid 3 = (23, 9).
• 3. Subsequently, n nodes are grouped by assigning each of them to the nearest centroid, such that no node remains without assigned centroid; as it is shown in Table 2 for this example.

https://doi.org/10.1371/journal.pone.0201868.t002

The assignment of the nodes to the clusters is as follows, cluster 1 = 5 , 6 , 7 , 12 ; cluster 2 = 1 , 2 , 8 , 9 , 10 , 11 , 13 , 14 and cluster 3 = 3 , 4 .

• Centroid 1 = (22.31,96.48);
• Centroid 2 = (17.07, 96.42);
• Centroid 3 = (21.24,92.96).

Table 3 shows the coordinates of clusters 1,2 and 3; C1 , C2 , C3 respectively in the X and Y axes, also from it the average of the coordinates of each cluster and in both axis are obtained to recalculate the centroids, therefore, such averages are: for C 1 , μx = 22.31 and μγ = 96.48; for C 2 , μx = 17.07 and μγ = 96.42; for C 3 , μx = 21.24 and μγ = 92.96.

https://doi.org/10.1371/journal.pone.0201868.t003

Repeating steps 3 and 4, Table 4 is obtained; in which there is only one modification compared to Table 3 . The clusters are remapped as shown in Table 4 .

https://doi.org/10.1371/journal.pone.0201868.t004

Now new centroids are:

• Centroid 1 = (22.31, 96.48);
• Centroid 2 = (16.63, 96.69);
• Centroid 3 = (20.85, 93.48);

For the next iteration, there is no reassignment of nodes to a different cluster, allocations are equal to those of Table 4 , so the step 4 in this iteration found the following clusters:

• Cluster 1 = 5-6-7-12;5
• Cluster 2 = 1-2-8-9-10-11-13;
• 5. In this step the NEH algorithm is applied to each of the k clusters, hereinafter the algorithm only be explained with the cluster 2, which is the largest for this example, calculating the cost or distance of each of the nodes to the other nodes belonging to the cluster in Table 5 .

https://doi.org/10.1371/journal.pone.0201868.t005

• 6. Nodes are sorted in ascending order relative to the travel expense, thereby Table 6 for Cluster 2 is obtained. Chosen as initial cluster nodes in question in the order obtained in the previous step with what you have for each cluster route.

https://doi.org/10.1371/journal.pone.0201868.t006

This order of the nodes is:

• 7. In this step the first two nodes of the list are chosen to exchange them and the permutation that provides the minimum cost is chosen, this is shown in Table 7 for cluster 2.

https://doi.org/10.1371/journal.pone.0201868.t007

This permutation is joined by the third node 9, moving its position in the list, Table 8 is obtained.

https://doi.org/10.1371/journal.pone.0201868.t008

The best result obtained in Table 9 can be considered as 9-11-8-1; and it is incorporated to node 2, for Table 10 .

https://doi.org/10.1371/journal.pone.0201868.t009

https://doi.org/10.1371/journal.pone.0201868.t010

The best result is that follows the path 9-11-8-1-2, to which node 13 is incorporated as shown in Table 11 . The smaller travel distance in Table 11 , is the path 13-9-11-8-1-2, so that the end node 10 of this cluster permuting as shown in Table 12 .

https://doi.org/10.1371/journal.pone.0201868.t011

https://doi.org/10.1371/journal.pone.0201868.t012

The results in each cluster by NEH algorithm are: cluster1, π ´ = 7 − 12 − 6–5 with cost of 5.8812; cluster2, π = 13−8−9−11−1−2−10 with cost of 11.3536 and cluster3, π ´ = 4−3−14 with cost of 4.4552.

• 8. The next step is to apply the MRSILS algorithm to each of the clusters starting from the initial solution generated by the NEH and arbitrarily define the number of iterations of the procedure that are performed, as well as a provisional store π with a default capacity number nπ , which stores the value of π at the end of each iteration. In this initial solution, π , each of the nodes are moved, respecting the order in which they appear, changing their position and choosing the one with the lowest cost or maintaining the one already stored, if it has a lower cost. To see the example of the 13th node, refer to the Table 13 . The initial solution provided by NEH for Cluster 2 was 13-8-9-11-1-2-10 and then node 8 is showed in Table 14 . In which the value of π with π ´ = 13−8−9−11−1−2−10 and we observe that π ´ = π , such that it does not change its value.

https://doi.org/10.1371/journal.pone.0201868.t013

https://doi.org/10.1371/journal.pone.0201868.t014

https://doi.org/10.1371/journal.pone.0201868.t015

The procedure is repeated in each cluster to a predetermined number of iterations. The value of π in each cluster is stored in the stack named π with capacity nπ in each cluster. When the number of iterations exceeds the value of nπ , the worst of the values in π will be eliminated from the iteration nπ +1. In addition, when a new iteration is initiated a perturbation is made on the best value of π by generating two random positions to make a shift. These are called Aleat and Aleat 2 using this new individual generated as π for start the next iteration of MRSILS. For example, if the best element of π is 13-8-11-9-1-2-10, Aleat 1 = 3 and Aleat 2 = 6. The perturbed solution is 13-8-10-11-9-1-2. In this example, only one iteration is perfomed, and the metaheuristic MRSILS is concluded. Now the clusters are: Cluster1 , π = 7−12−6−5 with cost of 5.8812; Cluster2, π = 13−8−11−9−1−2−10 with cost of 11.2294 and Cluster3, π = 4−3−14 with cost of 4.4552.

https://doi.org/10.1371/journal.pone.0201868.t016

• 10. The distance between centroid 1 and each of the nodes in C c are calculated, and the closest node to centroid 1 is chosen; it is named as node C2 . The distances between centroid 2 and each of the nodes or cluster 1 are calculated, also the nearest node to centroid 2 is chosen and named as node C1 . Subsequently, Cluster 1 is joined with C c , through the node C1 and node C2 . The distances between Centroid1 and each of the nodes C c ., where the centroid 1 coordinates are X = 22.31 and Y = 96.48, are shown in Table 17 .

https://doi.org/10.1371/journal.pone.0201868.t017

Table 17 shows the closed node to centroid 1 is 14, so node C2 = 14. The distance of C c with coordinates X = 20.85 and Y = 93.48 is calculated for each node of cluster 1, as shown in Table 18 . That can find the node of cluster 1 and it is closer to the centroid 2, in this case corresponds to node 12 so node C1 = 12.

https://doi.org/10.1371/journal.pone.0201868.t018

https://doi.org/10.1371/journal.pone.0201868.t019

• 11. Now, it is checked which of the nodes attached to node C2 of C c , is located closer to it, thereby choosing the direction of travel within the cluster. The last node of the path in C c , is called ClusterEnd 2, remaining free according to the algorithm until joining the last cluster with it. Similarly, the last node in cluster 1 is called ClusterEnd1. For the example, the distance of nodeC 2 = 14, to respect node 3 and node 4, is calculated. Table 19 shows such distances. So, node 3 is the closest, the direction the C c route must follow as 14-3-4; in addition, ClusterEnd 2 = 4

To end the direction of travel for cluster 1, it is necessary to end the nearest node to node node C1 = 12 between 6 and 7; which are the only possible consecutive as obtained in for its respective Cluster, as shown in Table 20 .

https://doi.org/10.1371/journal.pone.0201868.t020

Thus, node 6 is closest to node 12, the direction of the Cluster1 path is 12-6-5-7 and ClusterEnd1 = 7, and then the nodes near the centroids are joined so that node 12 joins node 14 as shown in ( Fig 1 ). The ClusterEnd1 and ClusterEnd2 nodes remain free until they join the rest of the clusters; In case they were the only clusters, these nodes join to obtain a final route. In case of a greater number of clusters, it is necessary to continue with next step.

https://doi.org/10.1371/journal.pone.0201868.g001

• 12. The next cluster to join is defined by finding the minimum distance between ClusterEnd2 and each of the remaining centroids. For this case, only one cluster is yet to be joined, in such a way that the distance of each node of this final cluster corresponding to cluster 3, with respect to ClusterEnd2, it is calculated, as shown in Table 21 .

https://doi.org/10.1371/journal.pone.0201868.t021

Table 21 identifies that the cluster 2closest to ClusterEnd2 is 13; and it is named as nodeC3. Subsequently, the node nearest to nodeC3, which is 8 and 10, is identified, to assign the direction to the route, these calculations are in Table 22 .

https://doi.org/10.1371/journal.pone.0201868.t022

The closest to the nodeC3 is the node 8, so the sequence of cluster 2 is 13-8-11-9-1-2-10, in addition the last node is called ClusterEnd3, in this case it corresponds to 10.

• 13. The previous step is repeated until k clusters. Finally, the last node of cluster k is joined to ClusterEnd1 to have the final path of the algorithm as shown in ( Fig 2 ).

https://doi.org/10.1371/journal.pone.0201868.g002

The final route is obtained: 7-5-6-12-14-3-4-13-8-11-9-1-2-10-7 at a cost of 37.6361. In the next section the results obtained in various instances reported in TSPLIB [ 50 ], are compared in both methods Genetic Algorithms and the proposed method described in this section.

As already mentioned, the objective of this article is to demonstrate that CTSPMRSILS , is more efficient than GA when clusters are used in TSP. For comparing them, a GA was programmed with the same parameters of [ 11 ], a) Selection Method: Tournament, b) Crossover Rate = 0.9, c) Mutation rate = 0.8, d) Number of generations = 5 n and e) Number of individuals = 3 n and n is the number of nodes. The 10 instances suggested by the same author were compared in cost and computational time, the last numbers in the name of the instance represent the number of nodes, for example, rat783 has 783 cities, the distance between the nodes were taken of TSPLIB [ 50 ]. Additionally, 30, 50 and 100 runs were used in both methods. The results are shown in Table 23 for the cost and in Table 24 for the time, in both cases, CTSPMRSILS obtains better results. It is important to mention that for the case pcb442 it was not possible to run the GA with 100 runs and for rat783 it was not feasible 30, 50 or 100 runs. Due to the complexity of the calculations a program was developed in the specialized software MatlabR2015a, and all the examples were solved in a computer with Core Intel Xeon Processor 3.2 GHz—Quad—Memory 8 GB.

https://doi.org/10.1371/journal.pone.0201868.t023

https://doi.org/10.1371/journal.pone.0201868.t024

In addition, 95% confidence intervals and means were carried out to guarantee the certainty of the result, in both indicators minimum cost in Table 25 and computational time in Table 26 , t -student was used for the mean test, in every case, a test for variances was did before, due to the amount of data the tests of variances and means are based on a normal distribution. CTSPMRSILS , represents μ 1 and the GA represents μ 2 . In both cases, there is statistical evidence to affirm that the μ 1 is less than μ 2 , which means that the minimum cost and time are obtained with CTSPMRSILS .

https://doi.org/10.1371/journal.pone.0201868.t025

https://doi.org/10.1371/journal.pone.0201868.t026

Also, the best results of the CTSPMRSILS were compared with the best-known result reported in the TSLIB [ 50 ], the same was done with the results of Piehtrankul [ 11 ], see Table 27 ; in [ 11 ] clusters with the k -means method and Genetic Algorithms are used. The comparison method was the percentage relative error, being 10.99% in CTSPMRSILS against 22.28% obtained with [ 11 ]. Which means that the proposed method is better than GA in clusters.

https://doi.org/10.1371/journal.pone.0201868.t027

6 Discussion

This article seeks to improve the efficiency of algorithms to solve problems with a larger number of nodes, to achive this goalclustering is used. In this research, computational experiments on 10 different instances of TSPLIB [ 50 ] are solved with the intention for comparing two methods: CTSPMRSILS and GA when are used in clusters. In this research, computational experiments on 10 different instances of TSPLIB [ 50 ] are solved with the intention for comparing two methods: CTSPMRSILS and GA when are used in clusters. For made that comparison, a GA was programmed and evaluate in cost and time with CTSPMRSILS . Also, some instances found in the literature with clusters and GA [ 11 ] are compared.

As can be seen in the previous section, the CTSPMRSILS improves the results of the GA when clusters are applied to the TSP. This can be seen in the confidence intervals of both cost and time, since they make inference of the difference that will exist with some confidence between the difference in the results of the compared algorithms, favoring the proposed method. Additionally, when comparing the results obtained by Piethrankul [ 11 ] and the proposed method with the best-known found, better results were obtained with the CTSPMRSILS in all instances. Even in the case of berlyn52 the best-know of TSLIB [ 50 ] was improved. Moreover, it can be seen in Table 24 , that the best results in 9 of the 10 instances were obtained at 50 runs, so it is suggested in a future work to analyze if the number of runs could be a halt criterion.

7 Conclusions

There are a lot of methods to solve the TSP, exact algorithms like branch and cut that are difficult to programming and implement. In the other hand, there are a lot of metaheuristics to deal with the complexity of the problem but any of them do not ensures finding the optimum in polynomial time. For this reason, we presented in our proposal a new algorithm.

Our proposal is a combination of NEH and a modification of the metaheuristic Multi Restart Iterated Local Search MRSILS that are used to solve the TSP with clusters, in the literature there is no one who has used this algorithm to solve the TSP when it is divided into clusters. Phietrankul made a comparison between different algorithms, and GA with cluster was the algorithm that would find the best results (minimum cost). The aim of this article is to demonstrate that the proposed algorithm CTSPMRILS is more efficient than Genetic Algorithms when clusters are used.

We compare CTSPMRSILS with GA with the same parameters of [ 11 ] and we get better results with the proposed method. Also, we did the comparison with the results published by Piehthrankul and we obtained better results in all the instances tested. We conclude that method proposed in this article is a viable candidate to solve problems as required by manufacturing companies and obtain better results in cost and time compare with GA.

In addition, the following recommendations are proposed for future research:

• The clustering is perfectible so that different methods could be for optimizing the allocation of the nodes to the different clusters.
• It is feasible to consider the combination of the MRSILS with some Metaheuristic different from the NEH in the search of better results.
• It could also be applied as a halt criterion for predetermined runs in the MRSILS.
• One more recommendation may focus on proposing a different method for joining clusters, after metaheuristics give a result.

Acknowledgments

This work was supported by National Council for Science and Technology (CONACYT) with project number CB-2014-237323, and the financial support for publication costs was provided by PRODEP publishing support program.

• View Article
• Google Scholar
• 5. Bailey C. and Mc. Lain T. Fuel Saving Strategies for Separated Space Craft Interferometry. Proceedings of the 2000 AIAA Guidance,Navigation,& Control Conference, United States of America, 2014.
• 10. Tan P, Steinbach M and Kumar V. Introduction to data mining. 1 st ed. Boston, EUA: Pearson Addison Wesley; 2011.
• 13. Wagner H. Principles of Operations Research. 2ª ed. Englewood Cliffs,N.J. Estados Unidos de América: Prentice Hall; 1975.
• 14. Gutin G. & Punnen A. The traveling salesman problem and its variations. Springer Science & Business Media; 2002.
• 16. Dorigo M. Ant colonies for the traveling salesman problem. Universidad Libre de Bruselas, Bélgica. 1997
• 17. Cerny, V.Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm. Lecture note in computer science Proceedings of the 9th Intenational Conference on ComputationalScience, 5544, 631–640. 1985.
• 46. Apostol T. Calculus: One-Variable Calculus, with an Introduction to Linear Algebra. 2nd ed. Waltham, MA: Blaisdell; 1967.
• 50. Reinelt G. TSPLIB; 2016. [Citado mayo 2018]. Base de datos: figshare [Internet]. Available from: http://comopt.i.uni-heidelberg.de/software/TSPLIB95/tsp/
• 51. Franklin D. Introductory University Mathematics with mymathlab leveler. 2nd ed. (Original in Spanish: Matemáticas Universitarias Introductorias con nivelador mymathlab) Pearson; 2014

Fast approximation of the traveling salesman problem shortest route by rectangular cell clustering pattern to parallelize solving

• Vadim Romanuke Polish Naval Academy
• Endnote/Zotero/Mendeley (RIS)
• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a  Creative Commons Attribution License  that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See  The Effect of Open Access ).

Most read articles by the same author(s)

• Vadim Romanuke, Infinity Substitute in Finding Exact Minimum of Total Weighted Tardiness in Tight-Tardy Progressive 1-machine Scheduling by Idling-free Preemptions , Statistics, Optimization & Information Computing: Vol 9 No 4 (2021)
• Vadim Romanuke, Equilibrium stacks for a non-cooperative game defined on a product of staircase-function continuous and finite strategy spaces , Statistics, Optimization & Information Computing: Vol 12 No 1 (2024)
• For Readers
• For Authors
• For Librarians

• Computer Vision
• Federated Learning
• Reinforcement Learning
• Natural Language Processing
• New Releases
• Advisory Board Members
• 🐝 Partnership and Promotion

Dhanshree Shripad Shenwai

Dhanshree Shenwai is a Computer Science Engineer and has a good experience in FinTech companies covering Financial, Cards & Payments and Banking domain with keen interest in applications of AI. She is enthusiastic about exploring new technologies and advancements in today’s evolving world making everyone's life easy.

SaySelf: A Machine Learning Training Framework That Teaches LLMs To Express More Accurate Fine-Grained Confidence Estimates

• 12 Most Popular Databases in 2024
• 18 Data Profiling Tools Every Developer Must Know
• CoSy (Concept Synthesis): A Novel Architecture-Agnostic Machine Learning Framework to Evaluate the Quality of Textual Explanations for Latent Neurons

RELATED ARTICLES MORE FROM AUTHOR

Demonstration iterated task optimization (ditto): a novel ai method that aligns language model outputs directly with user’s demonstrated behaviors, meet qwen2-72b: an advanced ai model with 72b parameters, 128k token support, multilingual mastery, and sota performance, modeling cultural accumulation in artificial reinforcement learning agents, this ai research discusses achieving efficient large language models (llms) by eliminating matrix multiplication for scalable performance, 10 gpts for software developers, demonstration iterated task optimization (ditto): a novel ai method that aligns language model outputs..., meet qwen2-72b: an advanced ai model with 72b parameters, 128k token support, multilingual mastery,..., sayself: a machine learning training framework that teaches llms to express more accurate fine-grained..., this ai research discusses achieving efficient large language models (llms) by eliminating matrix multiplication....

• AI Magazine
• Privacy & TC
• Cookie Policy

🐝 🐝 Join the Fastest Growing AI Research Newsletter Read by Researchers from Google + NVIDIA + Meta + Stanford + MIT + Microsoft and many others...

Thank You 🙌

Privacy Overview

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

What is a Travelling Salesman Problem (TSP)? Explained!

• Author: Diksha Bhandari
• Read Time: 9 min
• Published: September 14, 2023
• Last Update: November 8th, 2023

Table of Contents

• Route Planning
• Driver Behaviour
• Last Mile Delivery
• Asset Tracking
• Dispatch Management
• Fuel Management
• Route Optimisation
• Electric Vehicle
• Roster Management
• Vehicle Tracking
• TrackoMile Industries
• TrackoBit Industries
• Sensor Integration
• GPS Trackers and Hardware
• Tech and Beyond
• TrackoField
• What's New
• Employee Management
• Field Sales And Service
• Task and Workflow
• GPS Software
• Lead Management
• Fleet Management
• Leave And Attendance
• Video telematics
• TrackoField Industries

Want to know what a travelling salesman problem (TSP) is? Need solutions to real-life TSP challenges. Learn here. 

Do you also look for the shortest route on Google Maps before embarking on a trip?

I am sure, you know multiple routes to reach the office, the mall, or your desired location, but checking on the internet before leaving home has become a ritual. It becomes all the more important to refer to maps when you have to pick up friends or colleagues along the way.

‘ADD STOPS’

Yes, you are right! 💯

That’s what solving the TSP challenge using software means!

What is a Travelling Salesman Problem (TSP)?

The traveling salesman problem is the popular combinatorial optimisation challenge in mathematics and computer science. The prime objective of the problem is to determine the shortest possible route a salesperson must take to cover a set of locations in one go and then return to the starting point.

Addressing travelling salesman challenges and their optimisation are more relevant in this time and age, especially in the supply chain, logistics and delivery space.

TSP may result in delayed deliveries and slimming profits as it’s not easy for delivery agents to choose the most viable and cost-effective route in real-time.

What are Traveling Salesman Problem Challenges to Solve?

When a salesperson is in the field hopping from one client site to another, finding out the best and the shortest route is an added pressure on the agent. In today’s day and age, distance isn’t the only factor that defines efficiency. There are several factors, such as time, fuel consumption, capacity, etc. that together define efficiency.

However, addressing the travelling salesman challenges involves mitigating a few unavoidable challenges along the way that field agents face themselves.

1. Time Constraints

Sales agents often have a tight schedule with multiple deliveries to make with a short TAT. Similarly, in TSP, optimising routes to minimise travel time is a fundamental challenge.

2. Last-minute Changes

Eleventh-hour changes are not a new concept for salespeople. They encounter urgent visits and last-minute cancellations a lot. Similarly, TSP solutions must be adaptable to handle dynamic scenarios and route modifications.

3. Resource Efficiency

Just as salespersons aim at reducing fuel costs and ensuring on-time deliveries, TSP solutions such as TrackoMile must strive for resource optimisation by reducing travel distances and delivery TAT.

4. Objective Diversification

While solving the travelling salesman problem (TSP) , optimising multiple objectives such as cost, time, and environmental factors adds complexity as solutions need to balance conflicting goals.

5. Combinatorial Complexity

TSP is a combinatorial optimisation problem, which means it involves complicated mathematical calculations with numerous variables. Sometimes, complex scenarios get further intricate as multiple variables are involved.

6. Adaptability and Scalability

Similarly, how sales agents adjust to the routes on the fly, the route algorithm must be flexible and responsive to real-time changes such as spiking volumes, vehicle breakdown or traffic slow down. A TSP solution must have a good appetite to handle large datasets and complex networks.

Also Read 4 Key Solutions for Fuel Management System 2023

Top 5 Solutions to The Travelling Salesman Problem

The traveling salesman problem solutions offer various trade-offs between computational intricacies and the quality of the resolution, allowing practitioners to choose the best-suited approach based on their needs and problems.

Here are the Top 5 solutions to the Traveling Salesman Problem (TSP) :

1. Brute Force Algorithm

The Brute Force algorithm is a straight approach to solving the Traveling Salesman Problem (TSP). It systematically explores all possible routes to identify the shortest one among them all. While it guarantees an optimal solution, its downside lies in its major time complexity, making it practical only for small TSP challenges.

2. Nearest Neighbour Algorithm

The Nearest Neighbour method is the simplest heuristic for the TSP. It starts from the first location and repeatedly selects the closest unvisited location to form a tour. Although it is quick to implement this method, it may always yield the optimal solution for it prioritises proximity over other factors.

3. Genetic Algorithm

This technique or method draws inspiration from nature itself. They evolve TSP solutions through selection, crossovers and mutation. They pick the best routes and mix them up. This creates new routes that might be even better. Then, they keep the best ones and repeat the mixing and picking process. Survival of the fittest in the true sense.

4. Ant Colony Optimisation (ACO)

Ants have a tendency to leave pheromones on the shorter routes they find, calling fellow ants on the same route. They keep leaving more pheromones on the shorter routes they find. Over time, the collective behaviour of the ants causes them to converge on the shortest route. Inspired by the nature of ants, ACO finds the shortest route by analysing the trails of data left by artificial ants based on the strength of these data trails.

5. Dynamic Programming

Dynamic Programming is like solving a puzzle, step-by-step, by breaking it into smaller pieces. In TSP challenges, it finds the best route to visit all locations. It begins with figuring out the shortest route between two locations; then it builds on that to find ways to more locations. It’s a smart TSP solution for small scenarios but may require significant memory resources for larger and more complex problems.

What Are Real-world Travelling Salesman Problem Applications?

The Traveling Salesman Problem (TSP) has a wide array of applications across various domains due to its relevance in optimising routes and sequences. Here are several crucial real-word TSP applications and implementations in the real world.

1. TSP implementation in Logistics and Delivery Services

The logistics and supply chain sectors have the widest TSP applications.

• Courier, Express & Parcel : Companies like FedEx, UPS, and DHL rely on TSP algorithms to optimise delivery routes for their fleet of delivery trucks. By finding the most efficient sequence of stops, they minimise fuel consumption , reduce delivery TAT, and save on operational overheads too.
• On-demand Delivery : Food delivery companies, instant grocery delivery apps and at-home appointment platforms like Swiggy, BlinkIt and UrbanCompany, respectively, leverage TSP solutions to ensure timely delivery. Enhancing the customer experience and increasing the number of deliveries each rider can make.

2. TSP Applications in Transportation and Urban Planning Waste collection routes, Traffic light synchronisation, optic cable installation, etc. are some areas where TSP Solutions works like a knight in shining armour. Other real-world TSP applications include

• Public Transport : City planners and public transport agencies use TSP principles to design bus, tram and train routes that reduce travel for passengers.
• Emergency Service Dispatch : Ambulance services, Police PCR vans employ TSP algorithms to dispatch vehicles quickly and efficiently in response to emergency calls. Finding the shortest route to reach the incident location can save lives.
• Urban Mobility Solution : In the era of ride-sharing and on-demand mobility apps like Uber, Ola, Lyft, etc., real-world TSP applications become prominent. TSP solutions optimise the route to destinations, ensuring quick and cost-effective transportation.

Other significant real-life applications of the Travelling Salesman Problem are

• TSP in Healthcare and Medical Research – for DNA sequencing and understanding genetic patterns and diseases.
• TSP in Manufacturing and Production – In circuit board manufacturing and job scheduling of technicians.
• TSP in Robotics and Autonomous Vehicles -Self-driving cars and drones use TSP-like algorithms for efficient navigation.

Solving the Travelling Salesman Problem – Last Mile Delivery Route Optimisation

Route optimisation is the key to efficient last-mile delivery . In order to attain flawless route optimisation, the software must solve the traveling salesman problem every step of the way.

Why it’s essential to solve TSP for Last Mile Delivery?

In simple and minimal words, solving TSP problems helps in many ways:

• Saves Time : It makes deliveries faster, so your customers get orders sooner.
• Customer Satisfaction : Fast deliveries give you an edge over the competition and enhance customer experience too.
• Saves Money : It reduces fuel wastage and vehicle wear, making deliveries cheaper.
• Environment Friendly : It lowers pollution by using fewer vehicles and shorter routes.
• Happy Staff: Drivers and dispatchers have less stress and can finish their work faster.

How do we solve the travelling salesman problem for last-mile delivery?

Solving TSP challenges for Last-mile delivery is like solving a big jigsaw puzzle. There are a hundred thousand addresses to visit daily. The software must find the shortest and most optimised route to them and come back to the starting point at the end.

• Our route optimisation software , TrackoMile, leverages capacity management , routing algorithms and robust rule engines to present the most optimal combination of delivery addresses. Thereby giving the most optimally planned routes or trips.
• All delivery managers have to do is upload the CSV file of the addresses or integrate TrackoMile to their CRM to fetch the delivery addresses. Now trip allocation, route optimisation, dispatch and everything else happen in a few clicks.
• ETA when the delivery is en route, POD when the order is delivered successfully, and trip analysis, are added features to simplify overall operations.

The Vehicle Routing Problem is very similar to TSP, with wide applications in logistics, delivery services and transportation. While TSP focuses on finding the shortest route for a single traveller visiting various locations, VRP deals with multiple vehicles serving multiple customers, considering added constraints like vehicle capacity, TATs and more.

How Can AI Help in Solving Traveling Salesman Problem (TSP)?

AI or Artificial Intelligence are becoming the driving force for business growth across various industrial sectors. AI particularly aids in solving the Traveling Salesman Problem(TSP) in the logistics and delivery sector by employing advanced algorithms and techniques. What are a few tricks up AI’s sleeves that help in automating TSP resolution? Let’s find out!

1. Advanced Algorithms

AI algorithms such as Genetic Algorithms, ACO, simulated annealing and a few others mentioned above, tackle complex Travelling Salesman Problem scenarios.

2. Machine Learning

Gathering information from historical data and optimising routes based on real-time insights is what AI is best for. Machine learning models are trained to adapt to changing conditions, like traffic, weather and delivery constraints, to provide a more accurate plan of action.

3. Parallel Computing

AIi enables the use of a parallel computing process, which means solving multiple segments of TSP simultaneously. This accelerates the problem-solving process for large-scale challenges.

4. Heuristic Improvement

TSP Heuristics powered by AI can groom initial solutions, gradually improving their results over time. These heuristics can be applied iteratively by AI to reach better results.

5. Hybrid Approaches

Applying hybrid algorithms is not a new technique to refine techniques and produce more accurate results. AI on top of it singles out data-oriented combinations that work the best in varied use cases.

Wrapping Up!

The travelling salesman problem’s importance lies in its real-world applications. Whether optimising delivery routes, planning manufacturing processes or organising circuit board drilling, finding the most efficient way to cover multiple locations is crucial to minimise costs and save time.

The TSP problems have evolved over the years, and so have TSP algorithms, heuristics and solutions. With the advent of advanced technologies such as GPS and machine learning, TSP continues to adapt and find new applications in emerging fields, cementing its status as a fundamental problem in optimization theory and a valuable tool for various industries. Mobility automation software like Trackobit, TrackoMile and TrackoField resort to TSP heuristics to solve challenges along the way.

Read Blog – Best Delivery Route Planner Apps for 2023

Traveling Salesman Problem FAQs

What is tsp.

TSP is an abbreviation for Traveling Salesman Problem. It’s the routing problem that deals with finding the shortest route to travel to a combination of locations in the most optimal manner.

Is Travelling Salesman Problem Solvable?

Yes, the Traveling Salesman Problem (TSP) is solvable, but the time to find the solution can grow proportionately with an increase in the number of locations. With the evolution of travelling salesman problem applications, various TSP algorithms and heuristics, their hybrids have also emerged.

Wh at is the objective of TSP?

The objective of the Traveling Salesman Problem (TSP) is to find the shortest possible route that covers all given locations or waypoints and comes back to the starting point with the least resource utilisation.

Diksha Bhandari

Currently creating SaaSy content strategies for TrackoBit and TrackoField, this content professional has dedicated a decade of her life to enriching her portfolio and continues to do so. In addition to playing with words and spilling SaaS, she has a passion for traveling to the mountains and sipping on adrak wali chai.

• Author Showcase
• All Blog Post

Never Miss a Beat

Related Blog

Top 12 Google Map Alternatives – Offering Precise Navigation

Explore our best picks for 12 free Google map alternatives that offer accurate and secure location and navigational solutions. 

Food Delivery Trends to Watch in 2024 & Beyond

Food and technology are both revolving along with consumer demands. Here are some of the food delivery trends to watch in 2024.

Biofuel – An Alternative to Fossil Fuels in Transportation | G20

Transportation industries are moving towards a greener future through the sustainable use of biofuels like Ethanol — discussed in the G20 2023 summit.

Top 10 Navigation Apps for Android and iOS | 2024

Discover the 10 best navigation apps in 2024 that offer personalised navigation just like Sherpas (experienced guides of Himalayan terrain) do.

Thank you for reaching out! We'll speak to you soon.

In the meantime, why not find out more about us, explore our products, or visit our blog?

Stay Updated on tech, telematics and mobility. Don't miss out on the latest in the industry.

Cookie Consent

We use cookies to enhance and personalize your browsing experience. By continuing to use our website, you agree to our Privacy Policy.

A three-phase algorithm for the pollution traveling Salesman problem

Affiliations.

• 1 School of Industrial Engineering, Universidad del Bío-Bío, Concepción, 4030000, Chile.
• 2 Department of Industrial Engineering, Universidad del Bío-Bío, Concepción, 4030000, Chile.
• 3 Department of Accounting and Finance, Universidad del Valle, Cali, 760001, Colombia.
• PMID: 38694131
• PMCID: PMC11058884
• DOI: 10.1016/j.heliyon.2024.e29958

This paper studies a variant of the Pollution Traveling Salesman Problem (PTSP) focused on fuel consumption and pollution emissions (PTSPC). The PTSPC generalizes the well-known Traveling Salesman Problem (TSP), classified as NP-Hard. In the PTSPC, a vehicle must deliver a load to each customer through a Hamiltonian cycle, minimizing an objective function that considers the speed of each edge, the mass of the truck, the mass of the load pending delivery, and the distance traveled. We have proposed a three-phase algorithm for the PTSPC. The first phase solves the Traveling Salesman Problem (TSP) exactly with a time limit and heuristically using a Nearest Neighborhood Search approach. This phase considers the constraints associated with the PTSPC by using commercial software. In the second phase, both the obtained solutions and their inverse sequences from the initial phase undergo enhancement utilizing metaheuristic algorithms tailored for the PTSPC. These algorithms include Variable Neighborhood Search (VNS), Tabu Search (TS), and Simulated Annealing (SA). Subsequently, for the third phase, the best solution identified in the second phase-determined by having the minimum value by the PTSPC objective function-is subjected to resolution by a mathematical model designed for the PTSPC, considering the heuristic emphasis of commercial software. The efficiency of the former algorithm has been validated through experimentation involving the adaptation of instances from the Pollution Routing Problem (PRP) to the PTSPC. This approach demonstrates the capacity to yield high-quality solutions within acceptable computing times.

Keywords: Heuristic; Matheheuristic algorithm; Pollution Traveling Salesman; Simulated annealing; Tabu search; VNS.

© 2024 The Authors.