TSP (version 1.0-4)

solve_TSP: TSP solver interface

Description

Common interface to all TSP solvers in this package.

Usage

solve_TSP(x, method, control)

Arguments

x

the TSP given as an object of class TSP or ATSP.

method

method to solve the TSP (default: nearest insertion algorithm; see details).

control

a list of arguments passed on to the TSP solver selected by method.

Value

• An object of class TOUR.

Details

Currently the following methods are available: [object Object],[object Object],[object Object],[object Object],[object Object]

References

Concorde home page, http://www.tsp.gatech.edu/concorde/

David Appletgate, Robert Bixby, Vasek Chvatal, William Cook (2001): TSP cuts which do not conform to the template paradigm, Computational Combinatorial Optimization, M. Junger and D. Naddef (editors), Springer.

D. Applegate, W. Cook and A. Rohe (2003): Chained Lin-Kernighan for Large Traveling Salesman Problems. INFORMS Journal on Computing, 15(1):82--92.

G.A. Croes (1958): A method for solving traveling-salesman problems. Operations Research, 6(6):791--812.

S. Lin and B. Kernighan (1973): An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2): 498--516.

L.S. Pitsoulis and M.G.C. Resende (2001): Greedy randomized adaptive search procedures. In P.M. Pardalos and M.G.C. Resende, editors, Handbook of Applied Optimization, pp. 168--181.

D.J. Rosenkrantz, R. E. Stearns, and Philip M. Lewis II (1977): An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563--581.

See Also

TOUR, TSP, ATSP, write_TSPLIB, Concorde.

Examples

data("USCA50")

## create TSP
tsp <- USCA50

## methods
methods <- c("nearest_insertion", "cheapest_insertion", "farthest_insertion", 
    "arbitrary_insertion", "nn", "repetitive_nn", "2-opt")


## calculate tours
tours <- lapply(methods, FUN = function(m) solve_TSP(tsp, method = m))
names(tours) <- methods

## use the external solver which has to be installed separately
tours$concorde  <- solve_TSP(tsp, method = "concorde")
tours$linkern  <- solve_TSP(tsp, method = "linkern")

## show first tour
tours[[1]]

## compare tour lengths
opt <- 14497 # optained by concorde
tour_lengths <- c(sapply(tours, FUN = attr, "tour_length"), optimal = opt) 
dotchart(tour_lengths/opt*100-100, xlab = "percent excess over optimum")