1.1.1. Research Background of TSP
TSP (traveling salesman problem) is a well-known classical problem in the field of combinatorial optimization, which has not been completely solved so far. It has been classified as NP complete problem (Zhuo et al., 2020). The number of possible paths and the number of cities increase exponentially, so it is difficult to find the optimal solution accurately. The general formulation is: a traveling salesman wants to sell goods to n cities. He starts from city 1, passes through other cities at least once, then returns to city 1, and asks what kind of walking route he should choose to make the total journey the shortest (the distance between cities dij is known).
TSP problem has been proved to be NP complete. This means:
- 1.
Any NP complete problem cannot be solved by any known polynomial algorithm. With the expansion of the scale, such problems will encounter the problem of combination explosion;
- 2.
If any NP complete problem has a polynomial algorithm, then all NP complete problems have a polynomial algorithm.
Although the computing speed of the computer has been greatly improved, and some exponential algorithms have been available to solve the traveling salesman problem accurately, but with their failure (combination explosion) in large-scale problems, people have retreated to seek the second, and turned to look for approximate algorithm or heuristic algorithm. After decades of efforts, some progress has been made. At present, generally speaking, for the traveling salesman problem under 10000 cities, the approximate algorithm can be used to obtain the acceptable error less than 1% approximate solution or optimal solution in a reasonable time(Elias et al., 2019).
1.1.2. Significance of TSP Research
TSP is an ideal problem. Most of the researches on TSP are not for direct practical application, but these researches can be used in many practical combinatorial optimization problems after transformation. It is natural to think that the results of TSP can be applied to transportation and logistics problems. The earliest application of TSP is in the 1940s of last century, which is applied to the optimization of school bus routes. Now, TSP has been applied in more and more aspects:
- 1.
Arrangement of drilling schedule of circuit board. In this application, holes in the circuit board represent the city in the TSP problem, and the drill moves from one hole to another (Li et al., n.d.). Finding the shortest path becomes finding the most time-saving bit moving time. Although the development of drilling technology is very large, the moving time of drill is still a headache;
- 2.
Gene sequencing. Concorde is a program for solving TSP problems. Researchers at the National Institutes of health use the program to sequence genes. In this application, the local gene map is regarded as the city, and the distance between the city and the city represents the possibility of a map connecting with other maps (Chao & Xuan, 2001). Researchers are trying to find the most likely way to connect these local maps into a whole genetic map;
- 3.
Circuit design of semiconductor. A semiconductor manufacturer uses the Concorde program to optimize the circuit design of semiconductors, which can save the time of making semiconductors and reduce the energy consumption of semiconductor circuits;
- 4.
Line design of optical cable. Bell telephone company uses Concorde program to design the laying line of optical cable, and the same method is also applied to the laying of telephone and power lines;
- 5.
In other aspects, such as robot control, TSP is also applied.
Compared with practical value, the theoretical significance of TSP is more significant. In fact, this problem exists as an example of all combinatorial optimization problems. Many problems can be attributed to a TSP or treated as a sub problem. It has become and will continue to be a standard problem for testing new algorithms. This is because TSP problems show all aspects of combinatorial optimization. It is very simple in concept, but its solution is very difficult. If an algorithm proposed for TSP can achieve better results, then it can be modified to apply to other types of combinatorial optimization problems and achieve good results. For these reasons, the problem has attracted many researchers in different fields, including mathematics, operations research, physics, biology and artificial intelligence.