Dakin Branch-and-Bound TSP Algorith

1. A simple insertion algorithm

The branch-and-bound algorithm is based on an insertion algorithm which we will need to look at first. This algorithm is based on a process that derives an r-city tour from an (r-1)-city tour. Starting with a two city problem (or a three city problem if it is symmetric), the process is applied recursively to build up to a complete n-city solution. To get a true true optimum tour it is necessary to modify the insertion algorithm so that more than one r-city tour is investigated for each (r-1)-city tour; a branch-and-bound strategy is used to limit the extent of this search.

To understand the motivation of the approach we will first look at a way to do a backward recursion; that is, a procedure that goes from an r-city tour to an (r-1)-city tour.

n-city tour Suppose you are a travelling salesman and you are following a "good" tour route, not necessarily optimal, for visiting r cities; let us call this tour T(r). If you now decide that you no longer want to visit one of these cities - call it B - then how would you adjust your route?

(n-1)-city tour 1 I imagine you would simply drop B, leaving the rest of the tour intact. That is, if A is the city you go to before B and C is the one after, you would simply leave out the A-B and B-C links and take the shortest route from A to C, leaving the rest of the tour unchanged. For future reference we will give this tour a name - T(r-1) - and call the procedure for deriving T(r-1) from T(r) the Removal Algorithm. Common sense tells us that if T(r) is a "good" tour - that is, close to optimal - then T(r-1) is also "good". This is pretty vague however, and it is worth asking ourselves just how good the Removal Algorith is. Why not be an optimist and go for broke! So we state:

Proposition P: If T(r) is an optimal tour then T(r-1) is also optimal.

P is just a proposition; we have not proved whether it is true or not. If P were true then we would have a very nice way to solve the TSP. If we had the optimal T(r-1) then we would know that the optimal T(r) can be formed by inserting B in T(r-1). So all you would need to do is try inserting B into each of the r-1 links in T(r-1) and pick the one that gives the shortest r-tour. Applying this procedure recursively we could build an n-city tour starting with the trivial 2 city case in solution time that varies as n^2. We will call this the Insertion Algorithm.

(n-1)-city tour 2 This is fine if P is true. But is it? Unfortunately you can sometimes improve on the the Removal Algorithm. Because the Removal Algorithm is not necessarily optimal, the Insertion Algorithm is not necessarily optimal either. However both algorithms give near optimal result in many cases.

Some open questions

TSP's can be symmetric or asymetric - and there are other criteria that my be useful for classifying TSP's. If there were a class of TSP for which P is true then the Insertion Algorithm would be a very fast optimal algorithm for that class of TSP.
Open Question 1: Is there a class of TSP for which P is true?

In practice the Insertion Algorithm tends to give you a different tour depending on the order in which you add the cities - so the sorting of cities is possibly a useful line to pursue. I have tried a lot of sorting ideas with only modest results - but this does not necessarily mean that there is nothing in it. Sorting is a subject we will return to in the branch-and-bound context.
Open Question 2: Is there, in general, an insertion order for which P is true?
Open Question 3: If not, how much can the performance of the Insertion Algorithm be improved by sorting? In the following sections we will use the Insertion Algorithm as the basis for a branch-and-bound algorithm which can produce either an optimal tour or a tour whose length is within a known margin of the optimum.

In the absence of good answers to the open questions we can say that the Insertion Algorithm is a highly efficient way to get "good" solutions to the TSP. The great weakness of this algorithm, in common with other heuristic approaches, is that you have no precise idea how far from optimal your solution is. Also you should note that my Dynamic Programming Search algorithm is nearly as efficient as the Insertion Algorithm and produces better results in practice.

2. The branch-and-bound insertion algorithm

The Insertion Algorithm is based on the following recursion, which we will call Insert(r,T(r-1)), that operates on a subtour T(r-1) of the first (r-1) cities.

Insert(r,T(r-1)): If r = n then terminate; otherwise find the best r-tour, T(r), that can be constructed by inserting city r into the (r-1) tour; then perform Insert(r+1,T)(r)

The branch-and-bound insertion algorithm (BABIA) varies this recursion to perform a truncated search of the complete solution space to yield a true optimum tour. The truncation is what gives efficiency, allowing you to give up on large parts of the solution space without excluding the optimal tour. The truncation works by maintaining an upper bound on optimal tour length - the length of the best tour found so far - and discarding subtours that exceed the bound.

The BABIA algorithm is based on the Search(r,T(r-1)) recursion that operates on a particular (r-1) tour, T(r-1), as follows:

Search(r,T(r-1)): If r = n then record the tour details and reset the bound B to the tour length. Otherwise:
- sort the r-tours formed by inserting city r in T(r-1) in ascending order of length,
- scan these tours in sorted order and, for each r-tour T(r) whose length is less than B, apply Search(r+1,T(r)). Note that this may result in new tours being found, changing the value of B in the course of the scan.

The bounding strategy assumes that T(r) is always at least as long as T(r-1). To see what this assumption means, consider the effect of inserting city j between cities i and k; this adds an "insertion cost" that we will denote by IC(i,j,k). It has a simple relationship to the distance matrix D:

IC(i,j,k) = D[i,j] + D[j,k] - D[i,k]

The bounding strategy works if all insertion (IC's) are non negative. This must be so if the distance matrix is made up of straight line distances between cities, since D[i,k] represents the straight line distance between i and k, which must be at least as short as the less direct route represented by D[i,j] + D[j,k]. See Section 3. below for how to handle other cases.

You can think of the search as traversing a tree comprised of "nodes" (sub-tours) and "branches" (insertions). There are up to r-1 insertions, depending on the effect of the bound, following from each (r-1)-tour, each leading to an r-tour node from which up to r branches may emanate. What bounding does is to 'lop off' many of the branches, reducing the size of the tree that has to be searched.

Finding "good" solutions of known goodness

You can sharpen up the bounding criterion if you are prepared to make do with a solution whose length is within some percentage p of the true optimum. Then you can truncate the search from any branch whose tour length exceeds (1 - p/100)*B. This reduces the solution time at the expense of getting a solution that is not necessarily optimal but is within a known margin of the optimum. The demo program allows you to experiment using different values of p.

3. Preconditioning the distance matrix

Because the demo program generates straight line distances, insertion costs are automatically positive and no links are missing. If either of these conditions is not satisfied then you would need to precondition the distance matrix as follows:

Set the length of any missing link to some large value that ensures that no optimal tour can include that link. The sum of the lengths of the n longest real links is a safe value to use - you can probably get away with a smaller value.
Adding the same constant value to each element in a row (or column) of a distance matrix has no effect on the relative length of all tours (since each tour involves going to and from each node just once) - but it does add that constant to each insertion cost for that node. So...

For each node i find its smallest insertion cost and, if it is negative, add the modulus of that value to each element in the i'th row of the distance matrix. Repeat for all i. Keep a tally of the sum of these constants and subtract it from the length you get for the optimal tour to get its true length.

4. Sorting city order for BABIA

We have also considered sorting the order in which cities are inserted as a way of improving results from the Insertion Algorithm. Here our motivation for sorting is rather different - to improve the speed of BABIA. The idea is to make subtours as long as possible as the n-tour is bulit up with the idea of increasing the number of tree nodes that exceed the current bound, reducing the amount of tree that has to be searched. Sorting algorithms that have been tried include:

doing a pass through the Insertion Algorithm, at each stage picking, as the city to insert next, the one that gives the highest minimum insertion cost
as above, but picking the city that gives the highest second smallest insertion cost
pick, as the first three cities, those that form the longest triangle of any three cities - and don't bother about the order of the remaining cities.

All of these offer significant improvement over random order, but there is not a lot to pick between them

Please Email me if you have any comments

Back to my home page

Robert Dakin - dakin@pcug.org.au