The previous chapter introduced the graph data structure. A generic implementation was shown. Several classic graph algorithms were implemented and discussed.
This chapter is the first of several chapters that examine solutions to the classic Travelling Salesperson Problem. An exact solution to this problem is computationally intractable. In this chapter, we present and implement an algorithm for obtaining an exact solution to this problem.
In the next section, we introduce this classic problem.
17.1 Travelling Salesperson Problem and Its History
The Travelling Salesperson Problem (TSP) is a classic problem with a rich history. Given a set of cities and the distance between every pair of cities, the problem is to find the shortest tour that visits every city exactly once and returns to the starting city. The problem was first formulated in 1930. It has become one of the most intensively studied problems in optimization.
Some history:
See
- 1.
An exact solution for 15,112 German towns from TSPLIB was found in 2001 using the cutting-plane method proposed by George Dantzig, Ray Fulkerson, and Selmer M. Johnson in 1954, based on linear programming.
- 2.
In May 2004, the Travelling Salesman Problem of visiting all 24,978 towns in Sweden was solved: a tour of length approximately 72,500 kilometers was computed, and it was proven that no shorter tour exists.
- 3.
In March 2005, the Travelling Salesman Problem of visiting all 33,810 points in a circuit board was solved using Concorde TSP Solver. The computation took approximately 15.7 CPU-years.
TSP is a member of a group of problems that are NP-hard (nondeterministic polynomial time hard). If a polynomial-time-based solution could be found for any problem in this group, it can be proven that a polynomial-time solution for all the problems in this group could be found. To date, no such polynomial-time solutions have been found for any NP-hard problem.
In the next section, we present a brute-force solution to this problem that produces an exact solution.
17.2 An Exact Brute-Force Solution
Cities will be represented by vertices in a graph and numbered 0, 1, 2, …, n. The distance between cities will be specified as either integer or floating-point numbers and shown as the edges in the graph.
The brute-force solution requires that we obtain all permutations of tours that start with city 0 and end with city 0. For each tour in the permutation, we compute its cost. We return the tour with the lowest cost.
For each tour permutation, we compute the length of the tour. The tour permutation with the smallest length is an optimum solution to the problem. There may be ties.
Finding Permutations
The first task is to compute all the permutations of a slice containing consecutive integers starting at 0.
Permutations of slice
We leave it to the reader to walk through the code for a small problem and verify that it produces the desired permutation.
The second parameter in the Permutations function is an operation that must be performed on each slice. In the example presented in Listing 17-1, the operation is to output the slice. This is shown in main in boldface.
Brute-Force Computation for TSP
Brute-force solution to TSP
Discussion of Code
We focus on the invocation of Permutations inside of function TSP. In particular, we look at the function defined as the second parameter, shown in boldface.
For each tour in the permutation, we compute the cost of the tour.
The first cost computed is the cost of going from city 0 to the first city in the tour permutation. Following that, in a loop, we compute and add the costs for the sequence of cities in the tour permutation. The final cost computed is the cost from the last city in the tour permutation back to city 0.
A programming subtlety requires that we make a copy of the tour that we save in the global minimumTourCost. This is needed because assigning one slice to another makes a shallow copy. We are interested here in copying the information, not the address of the slice.
This block of code also adds the tour link from the starting city 0 and the tour link of getting back to city 0.
The computational cost of this brute-force solution is (n – 1)! That is why the brute-force method is intractable.
To illustrate this, we solve a 14-city problem with random integer distances between cities. We embed a low-cost path from city 0 to 1, 1 to 2, …, 13 to 0, each a distance 1 apart, for a total cost of 14. This does not affect computation time but gives us a test of correctness of the TSP algorithm.
As you can see from the output, we pass this test. The computation time for a 14-city problem is over two minutes.
If we were to increase the size of the problem by one city, the computation time would increase by a factor of 14. The computational complexity, O(n!), clearly makes this brute-force algorithm intractable.
Other Solutions
There are many algorithms, all intractable, that produce exact solutions to TSP. These algorithms employ dynamic programming, branch and bound, linear programming, and other techniques. They work well for small-sized problems but are impractical when the number of cities exceeds several dozen.
Before we examine heuristic algorithms for solving TSP that produce solutions close to the exact solution in reasonable time and storage space for large-sized problems, the next section presents code for displaying a TSP tour.
17.3 Displaying a TSP Tour
Displaying a TSP tour
Discussion of Code
The helper function, definePoints, returns a plotter.XYs. It uses the input slice, cities, to obtain the X and Y coordinates of each city that are assigned to pts. It assigns the sequence of points based on the input slice, tour.
The DrawTour function invokes definePoints and assigns the result to data. The remaining code follows the protocol in the plot package that is imported. A new plot, p, is defined. The lines and points variables are obtained from plotter.NewLinePoints.
After adding these to the plot, p, a png file is saved, which contains the points and lines that graphically display the tour.
17.4 Summary
The famed Travelling Salesperson Problem is introduced. A brute-force solution is presented. This solution, like all known exact solutions, is computationally intractable with a big O of O(n!).
Code for displaying a tour with specified coordinate locations is presented and illustrated with a simple example.
In the next chapter, we present another algorithm for obtaining an exact solution solving TSP. This algorithm uses a powerful technique called branch and bound. Like all known exact solutions to TSP, this branch-and-bound algorithm is computationally intractable.