Open access

# Introductory Chapter: Traveling Salesman Problem - An Overview

Written By

Donald Davendra and Magdalena Bialic-Davendra

Submitted: 20 August 2020 Published: 09 December 2020

DOI: 10.5772/intechopen.94435

From the Edited Volume

## Novel Trends in the Traveling Salesman Problem

Edited by Donald Davendra and Magdalena Bialic-Davendra

Chapter metrics overview

View Full Metrics

## 1. Introduction

The traveling salesman problem (TSP) is considered one of the seminal problems in computational mathematics. Considered as part of the Clay Mathematics Institute Millennium Problem with its assertion of P = N P [1], the TSP problem has been well researched during the past five decades.

The TSP problem can be described as the following: consider a number of cities which must be visited by a traveling salesman, only once, arriving once and departing once and starting and ending at the same city. Given the pairwise distances between cities, what is the best order in which to visit them, so as to minimize the overall distance traveled?

Mathematically, the equation for the TSP can be given as in Eq. (1):

x ij = 1 the path goes from city i to city j 0 otherwise E1

where x ij = 1 if city i is connected with city j, and x ij = 0 otherwise. For i = 0 , , n , let u i be an artificial variable and finally take c ij to be the distance from city i to city j. The objective function can be then formulated as Eq. (2):

min i = 0 n j i , j = 0 n c ij x ij 0 x ij 1 i , j = 0 , , n u i Z i = 0 , , n i = 0 , i j n x ij = 1 j = 0 , , n j = 0 , j i n x ij = 1 i = 0 , , n u i u j + nx ij n 1 1 i j n E2

## 2. Complexity

The complexity of the TSP is still unknown. Using a brute force approach to test each and every tour, for a tour of n cities, it will be (n-1)! possibilities and it will have a time complexity of O n ! . However, using the dynamic programming approach, the complexity can be derived of a tour of n cities, which can be divided into n-2 subsets each of size n-1, with the constraint that all such subsets don’t have the n th city in them. Therefore, there are a maximum of O n 2 n such subproblems, which can be solved in linear time. The time complexity is therefore O n 2 2 n . Both space and time complexity of the TSP problem can be considered as exponential.

## 3. History

The genesis of the TSP problem is difficult to pinpoint. Some literature point to widespread usage since the 1950’s [2], after the 48 state problem posed by Hassler Whitney in the 1930’s induced a lot of interest. The subsequent second world war really ingrained the use of operations research into this domain. An excellent detailed history is given in [3], where TSP is considered as a part of the history of Combinatorial Optimization.

The TSP problem over time has evolved into many different branches, each with different constraints:

Symmetric TSP (STSP) - the basic TSP problem, where the distance between city i and city j is the same as from city j and city i.

Asymmetric TSP (ATSP) - modified TSP, where the distance between city i and city j is not the same as from city j and city i.

Hamiltonian Cycle Problem (HCP) - is a problem where finding if a path in an undirected or directed graph G that visits each vertex V exactly once exists.

Sequential Ordering Problem (SOP) - Given a set of n cities and distances for each pair of cities, find a Hamiltonian path from city 1 to city n of minimal length, which takes given precedence constraints (such as requiring some nodes to be visited prior) into account.

Capacitated Vehicle Routing Problem (CVRP) - Given n-1 nodes, 1 depot (with resources) and distances between the nodes, the objective is to satisfy demand at each node using vehicles with identical capacity with the shortest tour.

Case Enough TSP (CETSP) - a problem developed for radio frequency identification (RFID), where close proximity is enough to a node. The objective is to trace the shortest path interlinking the different nodes.

TSP with Neighborhoods (TSPN) - where a collection of L regions in the plane, called neighborhoods is given and the objective is to seek the shortest tour to visit all these neighborhoods.

## 4. Current literature

Linear programming and deterministic methods have been seen as the early solvers, however, intractability of this problem has led to a general decline in these mathematical formulations. Within the past few decades with the rise of computational power, a new branch of algorithms called meta-heuristics generally based on evolutionary dynamics have become more synonymous with solving combinatorial optimization problems. Based around naturally occurring phenomena, these algorithms treat each problem as a black box with the aim of finding feasibly good solutions within acceptable space and time constraints. A vast repository of literature exists for the TSP problem, and the TSP Library is an excellent starting off resource point [4].

### 4.1 Deterministic approaches

Some of the latest literature on the TSP problem is divided into three components. The first is the exact and approximation algorithms, which try and produced efficient and reasonably good quality solutions. Some of the latest approaches are given below.

1. 2-Opt Algorithm [5]

2. Branch and Cut Algorithm [6]

3. Approximate and Exact Algorithms [7]

4. Branch and Bound [8]

### 4.2 Evolutionary approaches

The second aspect is evolutionary algorithms. A vast number of these algorithms are now in existence and have been applied to the TSP problem from the seminal work on the Ant Colony Optimization by Dorigo and Gambardella [9] to the following current research.

1. Artificial Bee Colony [10]

2. Differential Evolution [11]

3. Genetic Algorithm [12]

4. Tree Seed Algorithm [13]

5. Spider Monkey [14]

6. Ant Colony Optimization [15]

7. Harmony Search Algorithm [16]

8. Pigeon Inspired Optimization [17]

### 4.3 High performance computing

The third aspect is application based, specifically high-performance computing. With the wider dissemination of parallel computing, especially multi-core and graphic processor unit based approaches, many algorithms have been parrallized. Some of the latest approaches from literature is given as:

1. Multi-Core approach [18]

2. OpenMP [19]

3. CUDA [20]

## 5. Future direction

Even though a number of problems, especially in the combinatorial and scheduling domain have increased over the past decade, the TSP problem have remained a vital area of research. This is primarily for it being generally equated to the intractably quandary of P = N P , with its far reaching consequences in other fields such as encryption etc. It is the belief that a combination of smart heuristics employed on super-computers with parallel programming paradigms will be the future direction of tacking large-scale TSP problems.

## References

1. 1. Clay Mathematics Institute https://www.claymath.org/millennium-problems/p-vs-np-problem [Accessed: 10 October 2020]
2. 2. Applegate DL, Bixby RE, Chvatal V, Cook WJ. The Traveling Salesman Problem: A Computational Study. Princeton. Oxford: Princeton University Press; 2006
3. 3. Alexander S. On the History of Combinatorial Optimization (Till 1960), Editor(s): K. Aardal, G.L., Nemhauser, R., Weismantel, Handbooks in Operations Research and Management Science, Elsevier, Vol 12, Pages 1-68, 2005
4. 4. TSP Library. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ [Accessed: 10 October 2020]
5. 5. Hougardy S, Zaiser F, Zhong X. The approximation ratio of the 2-Opt Heuristic for the metric Traveling Salesman Problem. Operations Research Letters. 2020;48(4):401-404
6. 6. Yuan Y, Cattaruzza D, Ogier M, Semet F. A branch-and-cut algorithm for the generalized traveling salesman problem with time windows. European Journal of Operational Research. 2020;286(3):849-866, ISSN 0377-2217. DOI: 10.1016/j.ejor.2020.04.024
7. 7. Wang S, Liu M, Chu F. Approximate and exact algorithms for an energy minimization traveling salesman problem. Journal of Cleaner Production. 2020;249:119433, ISSN 0959-6526. DOI: 10.1016/j.jclepro.2019.119433
8. 8. Salman R, Ekstedt F, Damaschke P. Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem. Operations Research Letters. 2020;48(2):163-166, ISSN 0167-6377. DOI: 10.1016/j.orl.2020.01.009
9. 9. Dorigo M, Gambardella L. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. April 1997;1(1):53-66. DOI: 10.1109/4235.585892
10. 10. Pandiri V, Singh A. An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman problem. Applied Soft Computing. 2019;78:481-495, ISSN 1568-4946. DOI: 10.1016/j.asoc.2019.03.001
11. 11. Ali I, Essam D, Kasmarik K. A novel design of differential evolution for solving discrete traveling salesman problems. Swarm and Evolutionary Computation. 2020;52:100607, ISSN 2210-6502. DOI: 10.1016/j.swevo.2019.100607
12. 12. Dong X, Cai Y. A novel genetic algorithm for large scale colored balanced traveling salesman problem. Future Generation Computer Systems. 2019;95:727-742, ISSN 0167-739X. DOI: 10.1016/j.future.2018.12.065
13. 13. Cinar A, Korkmaz S, Kiran M. A discrete tree-seed algorithm for solving symmetric traveling salesman problem. Engineering Science and Technology, an International Journal. 2020;23(4):879-890, ISSN 2215-0986. DOI: 10.1016/j.jestch.2019.11.005
14. 14. Akhand MAH, Ayon I, Shahriyar SA, Siddique N, Adeli H. Discrete Spider Monkey Optimization for Travelling Salesman Problem. Applied Soft Computing. 2020;86:105887, ISSN 1568-4946. DOI: 10.1016/j.asoc.2019.105887
15. 15. Tuani A, Keedwell E, Collett M. Heterogenous Adaptive Ant Colony Optimization with 3-opt local search for the Travelling Salesman Problem. Applied Soft Computing. 2020;106720, ISSN 1568-4946. DOI: 10.1016/j.asoc.2020.106720
16. 16. Boryczka U, Szwarc K. The Harmony Search algorithm with additional improvement of harmony memory for Asymmetric Traveling Salesman Problem. Expert Systems with Applications. 2019;122:43-53, ISSN 0957-4174. DOI: 10.1016/j.eswa.2018.12.044
17. 17. Zhong Y, Wang L, Lin M, Zhang H. Discrete pigeon-inspired optimization algorithm with Metropolis acceptance criterion for large-scale traveling salesman problem. Swarm and Evolutionary Computation. 2019;48:134-144, ISSN 2210-6502. DOI: 10.1016/j.swevo.2019.04.002
18. 18. Wei X, Ma L, Zhang H, Liu Y. Multi-core-, multi-thread-based optimization algorithm for large-scale traveling salesman problem. Alexandria Engineering Journal. 2020. DOI: 10.1016/j.aej.2020.06.055
19. 19. Burkhovetskiy V, Steinberg B. Parallelizing an exact algorithm for the traveling salesman problem. Procedia Computer Science. 2017;119:97-102, ISSN 1877-0509. DOI: 10.1016/j.procs.2017.11.165
20. 20. Ermis G, Catay B. Accelerating local search algorithms for the travelling salesman problem through the effective use of GPU. Transportation Research Procedia. 2017;22:409-418, ISSN 2352-1465. DOI: 10.1016/j.trpro.2017.03.012

Written By

Donald Davendra and Magdalena Bialic-Davendra

Submitted: 20 August 2020 Published: 09 December 2020