© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022
R. WienerGeneric Data Structures and Algorithms in Gohttps://doi.org/10.1007/978-1-4842-8191-8_17

17. Travelling Salesperson Problem

Richard Wiener1  
(1)
Colorado Springs, CO, USA
 

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

https://en.wikipedia.org/wiki/Travelling_salesman_problem#Exact_algorithms.
  1. 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. 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. 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.

Consider the graph shown in Figure 17-1. This graph represents a four-city problem. The edge values represent the distance between cities.

An illustration of a graph, of four city T S P, with the help of Brute Force solution. Cities are labeled 0, 1, 3, and 4. Distance between cities are edges, depicted in the format: City, distance. 0 to 1, 5. 0 to 2, 3. 0 to 3, 9. 1 to 2, 2. 1 to 3, 1. 2 to 3, 6.

Figure 17-1

Graph of a four-city TSP

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.

The tour permutations that we consider are shown in Figure 17-2.

An illustration of tour permutations of T S P, with the help of Brute Force solution. There are 6 sets of tour permutations presented. First set: 0 1 2 3. Second set: 1 3 2. Third set: 0 2 1 3. Fourth set: 0 2 3 1. Fifth set: 0 3 2 1. Sixth set: 0 3 1 2.

Figure 17-2

Tour permutations

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.

Listing 17-1 performs this task.
package main
import (
    "fmt"
)
func Permutations(data []int, operation func([]int)) {
    permute(data, operation, 0)
}
func permute(data []int, operation func([]int), step
            int) {
    if step > len(data) {
        operation(data)
        return
    }
    permute(data, operation, step + 1)
    for k := step + 1; k < len(data); k++ {
        data[step], data[k] = data[k], data[step]
        permute(data, operation, step + 1)
        data[step], data[k] = data[k], data[step]
    }
}
func main() {
    data := []int{0, 1, 2, 3}
    Permutations(data, func(a []int) {
        fmt.Println(a)
    })
}
/* Output
[0 1 2 3]
[0 1 3 2]
[0 2 1 3]
[0 2 3 1]
[0 3 2 1]
[0 3 1 2]
[1 0 2 3]
[1 0 3 2]
[1 2 0 3]
[1 2 3 0]
[1 3 2 0]
[1 3 0 2]
[2 1 0 3]
[2 1 3 0]
[2 0 1 3]
[2 0 3 1]
[2 3 0 1]
[2 3 1 0]
[3 1 2 0]
[3 1 0 2]
[3 2 1 0]
[3 2 0 1]
[3 0 2 1]
[3 0 1 2]
*/
Listing 17-1

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

Listing 17-2 presents a brute-force computation for the TSP. It uses the permutation logic presented in Listing 17-1. It finds all the permutations of tours that start at 0 and end at 0. For each tour, it computes the cost of the tour and saves the best tour along with its cost.
package main
import (
    "fmt"
    "math/rand"
    "time"
)
type Graph [][]int
type TourCost struct {
    cost int
    tour []int
}
var minimumTourCost TourCost
var graph Graph
func Permutations(data []int, operation func([]int)) {
    permute(data, operation, 0)
}
func permute(data []int, operation func([]int), step
             int) {
    if step > len(data) {
        operation(data)
        return
    }
    permute(data, operation, step+1)
    for k := step + 1; k < len(data); k++ {
        data[step], data[k] = data[k], data[step]
        permute(data, operation, step+1)
        data[step], data[k] = data[k], data[step]
    }
}
func TSP(graph Graph, numCities int) {
    tour := []int{}
    for i := 1; i < numCities; i++ {
        tour = append(tour, i)
    }
    minimumTourCost = TourCost{32767, []int{}}
    Permutations(tour, func(tour []int) {
        // Compute cost of tour
        cost := graph[0][tour[0]]
        for i := 0; i < len(tour)-1; i++ {
            cost += graph[tour[i]][tour[i+1]]
        }
        cost += graph[tour[len(tour)-1]][0]
        if cost < minimumTourCost.cost {
            minimumTourCost.cost = cost
            var tourCopy []int
            tourCopy = append(tourCopy, 0)
            tourCopy = append(tourCopy, tour...)
            tourCopy = append(tourCopy, 0)
            minimumTourCost.tour = tourCopy
        }
    })
}
func main() {
    graph = Graph{{0, 5, 3, 9}, {5, 0, 2, 1}, {3, 2, 0, 6},
                  {9, 1, 6, 0}}
    TSP(graph, 4)
    fmt.Printf(" Optimum tour cost: %d  An Optimum
             Tour %v", minimumTourCost.cost,
             minimumTourCost.tour)
    numCities := 14
    graph2 := make([][]int, numCities)
    for i := 0; i < numCities; i++ {
        graph2[i] = make([]int, numCities)
    }
    for row := 0; row < numCities; row++ {
        for col := 0; col < numCities; col++ {
            graph2[row][col] = rand.Intn(9) + 2
        }
    }
    // Create a short path for test purposes
    for i := 0; i < numCities-1; i++ {
        graph2[i][i+1] = 1
    }
    graph2[numCities-1][0] = 1
    start := time.Now()
    TSP(graph2, numCities)
    elapsed := time.Since(start)
    fmt.Printf(" Optimum tour cost: %d  An Optimum
              Tour %v", minimumTourCost.cost,
               minimumTourCost.tour)
    fmt.Println(" Computation time: ", elapsed)
}
/* Output
Optimum tour cost: 15  An Optimum Tour [0 1 3 2 0]
Optimum tour cost: 14  An Optimum Tour [0 1 2 3 4 5 6 7 8 9 10 11 12 13 0]
Computation time:  2m15.918717943s
*/
Listing 17-2

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.

We compare the cost of the tour permutation with the lowest cost thus far. This is held as a global variable of type TourCost.
type TourCost struct {
    cost int
    tour []int
}

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.

We accomplish this with the append function as follows:
var tourCopy []int
tourCopy = append(tourCopy, 0)
tourCopy = append(tourCopy, tour...)
tourCopy = append(tourCopy, 0)

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

Listing 17-3 uses a third-party package to graphically display a tour given a slice of points that define the cities in the tour.
package main
import (
    "image/color"
    "gonum.org/v1/plot"
    "gonum.org/v1/plot/plotter"
    "gonum.org/v1/plot/vg"
    "gonum.org/v1/plot/vg/draw"
)
type Point struct {
    X float64
    Y float64
}
func definePoints(cities []Point, tour []int)
                  plotter.XYs {
    pts := make(plotter.XYs, len(cities) + 1)
    pts[0].X = cities[0].X
    pts[0].Y = cities[0].Y
    for i := 1; i < len(cities); i++ {
        pts[i].X = cities[tour[i]].X
        pts[i].Y = cities[tour[i]].Y
    }
    pts[len(cities)].X = cities[0].X
    pts[len(cities)].Y = cities[0].Y
    return pts
}
func DrawTour(cities []Point, tour []int) {
    data := definePoints(cities, tour) // plotter.XYs
    p := plot.New()
    p.Title.Text = "TSP Tour"
    lines, points, err := plotter.NewLinePoints(data)
    if err != nil {
        panic(err)
    }
    lines.Color = color.RGBA{R: 255, A: 255}
    points.Shape = draw.PyramidGlyph{}
    points.Color = color.RGBA{B: 255, A: 255}
    p.Add(lines, points)
    // Save the plot to a PNG file.
    if err := p.Save(4*vg.Inch, 4*vg.Inch,
            "tour.png"); err != nil {
        panic(err)
    }
}
func main() {
    numCities := 4
    cities := make([]Point, numCities)
    cities[0] = Point{0.0, 0.0}
    cities[1] = Point{3.0, 0.0}
    cities[2] = Point{3.0, 4.0}
    cities[3] = Point{1.0, 11.0}
    tour := []int{0, 3, 1, 2}
    DrawTour(cities, tour)
}
Listing 17-3

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.

The output of this program is shown in Figure 17-3.

A graph depicts the output of T S P. X-axis ranges from 0 to 3, in unit increments. Y-axis ranges from 0 to 10, in increments of 5. Three points (0, 0), (3, 4), (3, 0), and (1, 11) are connected by lines in the same order mentioned.

Figure 17-3

Output from Listing 17-3

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.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.145.119.199