Jump to a key chapter

## Understanding the Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is a classical combinatorial optimization problem that has applications in a wide range of fields, from logistics to computer science. The problem involves a salesman who needs to visit a number of cities, starting and ending at the same city, while minimizing the total distance travelled. In this article, we'll take a closer look at the problem and the components of its mathematical formulation.

### Decision Mathematics: Introduction to the Travelling Salesman Problem

The Travelling Salesman Problem belongs to the realm of decision mathematics, a branch of mathematics dealing with decision-making in various contexts including optimization and operations research. The TSP is an example of an NP-hard problem, meaning that no efficient algorithm exists to find an exact solution in polynomial time.

**The Travelling Salesman Problem (TSP):** Given a list of cities and the distances between them, find the shortest possible route that visits each city exactly once and returns to the origin city.

The TSP has several real-life applications, such as:

- Route optimization for transport and logistics
- Microchip design and routing
- DNA sequencing
- Machine scheduling

**Example:** Suppose a salesman needs to visit 4 cities: A, B, C, and D. The distances between the cities are as follows:

A | B | C | D | |

A | 0 | 10 | 15 | 20 |

B | 10 | 0 | 35 | 25 |

C | 15 | 35 | 0 | 30 |

D | 20 | 25 | 30 | 0 |

The shortest possible route for the salesman in this example is A → B → D → C → A, with a total distance of 80 units.

## Components of the Travelling Salesman Problem Formula

Now let's dive into the mathematical components of the TSP. The problem can be modelled as a graph, where cities are represented by nodes and the paths between cities are represented by edges weighted with their distances. The task is to find the smallest total weight of a cycle that connects all nodes and returns to the starting node.

**Graph:** A mathematical object consisting of vertices (nodes) and edges, which represent pairwise connections between the vertices. In the context of the TSP, these vertices are cities and the edges represent paths between them with associated distances.

Mathematically, the TSP can be described with the following components:

**Set of nodes:**\(N = \{1, 2, \ldots, n\}\) - a set of cities the salesman needs to visit.**Distance matrix:**\(D = [d_{ij}]_{n\times n}\) - an \(n\times n\) matrix, where \(d_{ij}\) represents the distance between city \(i\) and city \(j\). We have \(d_{ij} = d_{ji}\) for symmetric TSP instances, while for asymmetric TSP instances \(d_{ij} \neq d_{ji}\) can occur.**Decision variables:**\(x_{ij}\) - binary variables equal to 1 if the path between cities \(i\) and \(j\) is included in the solution, and 0 otherwise.

The objective function for the TSP is to minimize the total distance travelled, which can be represented as:

\[ \min \sum_{i=1}^{n}\sum_{j=1}^{n} d_{ij}x_{ij} \]Subject to constraints that ensure:

- Each city is visited exactly once
- The salesman returns to the starting city
- There are no subtours (trips that don't include all cities)

Although finding an exact solution to the TSP remains a challenge, several heuristic algorithms have been developed to find near-optimal solutions in a reasonable amount of time, such as

- Nearest Neighbour Algorithm
- Simulated Annealing
- Genetic Algorithms

While understanding the Travelling Salesman Problem may seem complex, its wide applicability in optimization and real-life scenarios is undeniably valuable.

## Solving the Travelling Salesman Problem

Finding solutions to the Travelling Salesman Problem remains a complex task due to its NP-hard nature. Nonetheless, several approaches and algorithms have been developed to tackle the problem, allowing for effective solutions in various applications.

### Travelling Salesman Problem Complexity and Challenges

Understanding the complexity and challenges behind solving the TSP is an essential step in finding effective methods to address it. Given that the Travelling Salesman Problem is considered to be NP-hard, finding an exact solution in polynomial time is highly unlikely. Instead, researchers have been focusing on developing approximation algorithms and heuristic methods to find near-optimal solutions in reasonable timeframes.

**NP-hard problems:** These problems belong to a class of decision problems for which no known polynomial-time algorithm exists. NP-hard problems are considered to be at least as hard as the hardest problems in NP, a class of problems to which a solution can be verified in polynomial time.

There are essentially two main challenges when solving the TSP:

**Computational complexity:**The number of potential solutions for the problem increases rapidly as the number of cities grows. For \(n\) cities, there are \((n-1)!\) possible routes, leading to an exponential growth in the problem's complexity.**Finding optimal solutions:**In many problem instances, an exact optimal solution is not required, hence near-optimal solutions are often sought. Developing approximation algorithms and heuristics that offer near-optimal solutions and perform well on large problem instances are major focus points in TSP research.

### Using Branch and Bound to Solve the Travelling Salesman Problem

Branch and Bound is a general algorithm for solving combinatorial optimization problems, including the TSP. The method allows finding an optimal or near-optimal solution while avoiding the exhaustive search of all possible routes. The algorithm operates by exploring a tree-like structure of potential solutions, branching off to create subproblems based on decisions made. It then calculates bounds (upper and lower) for these subproblems to determine whether they're worth further exploration or can be discarded, effectively pruning the search space.

**Branch and Bound:** A tree-search-based method for solving combinatorial optimization problems. It involves dividing a problem into smaller subproblems, evaluating the bounds of each subproblem and discarding those that do not contribute to an optimal solution.

The basic steps in the Branch and Bound algorithm for solving the TSP are:

- Construct an initial solution, either randomly or using a greedy approach.
- Create subproblems by branching off based on decisions on edges included in or excluded from the tour.
- Calculate lower and upper bounds for each subproblem. Lower bounds can be obtained using solutions to relaxed versions of the problem (e.g., not requiring to visit each city exactly once), whereas upper bounds can be derived from the current best solution or using heuristics.
- Eliminate subproblems with bounds that do not hold the potential for better solutions than the current best one.
- Continue branching and bounding until no promising subproblems remain, and return the best solution found.

Applying Branch and Bound to solve the TSP effectively identifies optimal or near-optimal solutions while reducing the search space by excluding subproblems that cannot contribute to improved solutions. This technique can provide high-quality results for small to medium-sized problems; however, its computational complexity remains high and can be prohibitive for larger instances. In such cases, heuristic methods such as Nearest Neighbour, Simulated Annealing, or Genetic Algorithms are often prefered for their ability to find near-optimal solutions in significantly reduced time.

## Advanced Travelling Salesman Problem Concepts

In addition to the classic Travelling Salesman Problem, several advanced TSP concepts and variations exist that incorporate additional constraints or consider specific objectives beyond minimising the overall tour distance. In this section, we will explore the Bottleneck Travelling Salesman Problem and the Bitonic Euclidean Travelling Salesman Problem, including their problem formulations and potential applications.

### Bottleneck Travelling Salesman Problem Explained

The Bottleneck Travelling Salesman Problem (BTSP) is a variation of the standard TSP that focuses on minimising the longest edge used in the tour. This problem type arises in situations where the most critical factor is the worst-case travel time or distance rather than the overall tour length. The objective function for the BTSP is to determine the shortest possible route that visits each city exactly once, returns to the starting city, and involves the smallest possible longest edge.

**Bottleneck Travelling Salesman Problem (BTSP):** A variation of the TSP, where the objective is to minimise the length of the longest edge used in the tour.

Mathematically, the BTSP can be formulated as follows:

\[ \min \ \max_{(i, j) \in T} d_{ij} \]Subject to constraints enforcing:

- Each city is visited exactly once
- The salesman returns to the starting city
- No subtours (trips that don't include all cities)

Several algorithms have been proposed for solving the BTSP, ranging from exact methods such as Branch and Bound, Integer Linear Programming, to heuristic approaches, including Genetic Algorithms, Ant Colony Optimization and Tabu Search.

Applications of the Bottleneck Travelling Salesman Problem can be found in a variety of areas:

- Telecommunications network design, focusing on the maximum latency of data transmission
- Emergency service route planning to minimise response time
- Transportation hub connection optimization, where ensuring shortest transit time is critical

### Bitonic Euclidean Travelling Salesman Problem and Its Applications

The Bitonic Euclidean Travelling Salesman Problem (BETSP) is a specific variant of the TSP that imposes additional structural restrictions on the resulting tour. The problem requires finding a shortest bitonic tour on a set of points in the Euclidean plane, where a tour is considered bitonic if it consists of two monotonic chains in terms of the \(x\)-coordinates of the points (cities).

**Bitonic Euclidean Travelling Salesman Problem (BETSP):** A variation of the TSP, where the objective is to find the shortest possible bitonic tour in the Euclidean plane.

A simpler version of the BETSP, called the Bitonic Euclidean Salesman Path Problem, focuses on constructing a shortest bitonic path instead of a closed cycle. Due to the bitonic nature of the tours, the BETSP provides an opportunity for more efficient algorithms compared to the general TSP.

Dynamic Programming approaches have been demonstrated to be effective in solving the BETSP. The algorithm considers diagonal strips of points in the plane and, by calculating partial bitonic tours, incrementally constructs the optimal bitonic tour. The complexity of this algorithm is \(O(n^2 \log n)\), making it computationally more tractable than the classic TSP.

The Bitonic Euclidean Travelling Salesman Problem has applications in:

- Computer graphics for blending curves and surfaces
- Routing problems on grids, such as wire routing in printed circuit boards
- Geometric optimization in computational geometry

In summary, both the Bottleneck Travelling Salesman Problem and the Bitonic Euclidean Travelling Salesman Problem extend the classic TSP concept by introducing new objectives or constraints. These variations provide insights into efficient algorithms and offer practical applications in various industries and scenarios, enhancing our understanding of the broader challenges in combinatorial optimization, decision-making, and operations research.

## The Travelling Salesman Problem - Key takeaways

The Travelling Salesman Problem (TSP): given a list of cities and the distances between them, find the shortest possible route that visits each city exactly once and returns to the origin city.

TSP belongs to decision mathematics and is an NP-hard problem, meaning no efficient algorithm exists to find an exact solution in polynomial time.

Several heuristic algorithms, such as Nearest Neighbour Algorithm, Simulated Annealing, and Genetic Algorithms, have been developed to find near-optimal TSP solutions in a reasonable amount of time.

Branch and Bound is a tree-search-based method for solving the TSP, allowing for optimal or near-optimal solutions without exhaustive search of all possible routes.

Advanced TSP concepts include the Bottleneck Travelling Salesman Problem, which focuses on minimising the longest edge used in the tour, and the Bitonic Euclidean Travelling Salesman Problem, where the objective is to find the shortest possible bitonic tour in the Euclidean plane.

###### Learn with 12 The Travelling Salesman Problem flashcards in the free StudySmarter app

We have **14,000 flashcards** about Dynamic Landscapes.

Already have an account? Log in

##### Frequently Asked Questions about The Travelling Salesman Problem

What is Travelling salesman problem and how is it modeled as a graph problem?

The Travelling Salesman Problem (TSP) is an optimisation problem that aims to find the shortest possible route for a salesman to visit a given set of cities and return to the starting city, visiting each city only once. It is modelled as a graph problem by representing cities as vertices and the distances between them as weighted edges, with the objective being to find the minimum-weight Hamiltonian cycle within the graph.

What is the formula for the traveling salesperson problem?

There isn't a specific formula for the travelling salesperson problem. Instead, it is an optimisation problem, aiming to find the shortest route connecting a set of cities, visiting each city once and returning to the starting point. Solutions can be found using various algorithms and techniques, such as the Nearest Neighbour or Branch-and-Bound methods.

What is travelling salesman problem?

The travelling salesman problem is an optimisation problem in further mathematics, which aims to find the shortest possible route for a salesman to visit a given set of cities and return to the starting city, ensuring that each city is visited only once.

How to solve travelling salesman problem?

To solve the Travelling Salesman Problem, you can use exact algorithms like the Held-Karp algorithm, branch and bound method, or integer linear programming. Alternatively, you can apply heuristic methods like the nearest neighbour rule, the genetic algorithm, or simulated annealing for approximate solutions.

Has the travelling salesman problem been solved?

No, the travelling salesman problem (TSP) has not been fully solved yet. It remains an open problem in the field of mathematics and computer science. Currently, there are various approximation algorithms available, but no efficient algorithm exists for finding the optimal solution to the TSP for all cases.

##### About StudySmarter

StudySmarter is a globally recognized educational technology company, offering a holistic learning platform designed for students of all ages and educational levels. Our platform provides learning support for a wide range of subjects, including STEM, Social Sciences, and Languages and also helps students to successfully master various tests and exams worldwide, such as GCSE, A Level, SAT, ACT, Abitur, and more. We offer an extensive library of learning materials, including interactive flashcards, comprehensive textbook solutions, and detailed explanations. The cutting-edge technology and tools we provide help students create their own learning materials. StudySmarter’s content is not only expert-verified but also regularly updated to ensure accuracy and relevance.

Learn more