find_tour_BB {gor}

Branch-and-Bound algorithm for the TSP

Description

This routine performs a version of the Branch-and-Bound algorithm for the Traveling Salesperson Problem (TSP). It is an exact algorithm with exponential worst-case running time; therefore, it can be run only with a very small number of cities.

Usage

find_tour_BB(
  d,
  n,
  verb = FALSE,
  plot = TRUE,
  z = NA,
  tour = rep(0, n),
  distance = 0,
  upper = Inf,
  col = c(1, rep(0, n - 1)),
  last = 1,
  partial = c(1, rep(NA, n - 1)),
  covered = 0,
  call = 0,
  save.best.result = FALSE,
  filename.best.result = "best_result_find_tour_BB.Rdata",
  order = NA
)

Arguments

d

Distance matrix of the TSP instance

n

Number of vertices of the TSP complete graph

verb

If detailed operation of the algorithm should be echoed to the console. It defaults to FALSE

plot

If tours found by the algorithm should be plotted using plot_tour. It defaults to TRUE

z

Points to plot the tours found by the algorithm. It defaults to NA; it should be set if plot is TRUE or else plot_tour will not plot the tours

tour

Best tour found by the algorithm. If the algorithm has ended its complete run, this is the optimum of the TSP instance. This variable is used to store the internal state of the algorithm and it should not be set by the user

distance

Distance covered by the best tour found. This variable is used to store the internal state of the algorithm and it should not be set by the user

upper

Upper bound on the distance covered by the optimum tour. It can be provided by the user or the routine will use the result found by the heuristic build_tour_nn_best

col

Vectors of "colors" of vertices. This variable is used to store the internal state of the algorithm and it should not be set by the user

last

Last vertex added to the tour being built by the algorithm. This variable is used to store the internal state of the algorithm and it should not be set by the user

partial

Partial tour built by the algorithm. This variable is used to store the internal state of the algorithm and it should not be set by the user

covered

Partial distance covered by the partial tour built by the algorithm. This variable is used to store the internal state of the algorithm and it should not be set by the user

call

Number of calls that the algorithm performs on itself. This variable is used to store the internal state of the algorithm and it should not be set by the user

save.best.result

The time needed for a complete run of this algorithm may be exponentially large. Since it only will return its results if it ends properly, we can save to a file the best result found by the routine at a given time when save.best.result = TRUE (default is FALSE). Then, the user will be allowed to stop the run of the algorithm without losing the (possibly suboptimal) result.

filename.best.result

The name of the file used to store the best result found so far when save.best.result = TRUE. It defaults to "best_result_find_tour_BB.Rdata". When loaded, this file will define the best tour in variable "Cbest".

order

Numeric vector giving the order in which vertices will be search by the algorithm. It defaults to NA, in which case the algorithm will take the order of the tour found by the heuristic build_tour_nn_best. If the user knows in advance some good tour and he/she wishes to use the order of its vertices, it should be taken into account that the third vertex used by the algorithm is the last vertex of the tour!

Details

The algorithm starts at city 1 (to avoid the cyclic permutation tour equivalence) and the "branch" phase consists on the decision of which city follows next. In order to avoid the equivalence between a tour and its reverse, it only considers those tours for which the second city has a smaller vertex id that the last. With n cities, the total number of tours explored in this way is (n-1)!/2, which clearly is infeasible unless n is small. Hence the "bound" phase estimates a lower bound on the distance covered by the tours which already are partially constructed. When this lower bound grows larger than an upper bound on the optimum supplied by the user or computed on the fly, the search stops in this branch and the algorithm proceeds to the next. This complexity reduction does not help in the worst case, though.

This routine represents the tree search by iterating over the sucessors of the present tree vertex and calling itself when descending one level. The leaves of the three are the actual tours, and the algorithm only reaches those tours whose cost is less than the upper bound provided. By default, the algorithm will plot the tour found if the coordinates of the cities are supplied in the "z" input argument.

When the routine takes too much time to complete, interrupting the run would result in losing the best tour found. To prevent this, the routine can store the best tour found so far so that the user can stop the run afterwards.

Value

A list with nine components: $tour contains a permutation of the 1:n sequence representing the best tour constructed by the algorithm, $distance contains the value of the distance covered by the tour, which if the algorithm has ended properly will be the optimum distance. Component $call is the number of calls the algorithm did on itself. The remaining components are used to transfer the state of the algorithm in the search three from one call to the next; they are $upper for the current upper bound on the distance covered by the optimum tour, $col for the "vertex colors" used to mark the vertices added to the partially constructed tour, which is stored in $partial. The distance covered by this partial tour is stored in $covered, the last vertex added to the partial tour is stored in $last, and the "save.best.result" and "filename.best.result" input arguments are stored in $save.best.result and $filename.best.result.

Author(s)

Cesar Asensio

Examples

## Random points
set.seed(1)
n <- 10
z <- cbind(runif(n, min=1, max=10), runif(n, min=1, max=10))
d <- compute_distance_matrix(z)
bb <- find_tour_BB(d, n)
bb$distance                        # Optimum 26.05881
plot_tour(z,bb)
## Saving tour to a file (useful when the run takes too long):
## Can be stopped after tour is found
## File is stored in tempdir(), variable is called "Cbest"
find_tour_BB(d, n, save.best.result = TRUE, z = z)