solve_TSP {TSP} | R Documentation |
Common interface to all TSP solvers in this package.
solve_TSP(x, method, control)
x |
the TSP given as an object of class |
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 |
Currently the following methods are available:
"nearest_insertion"
,
"farthest_insertion"
,
"cheapest_insertion"
,
"arbitrary_insertion"
Nearest, farthest, cheapest and arbitrary insertion algorithms for a symmetric and asymmetric TSP (Rosenkrantz et al. 1977).
The distances between cities are stored in a distance matrix D with elements d(i,j). All insertion algorithms start with a tour consisting of an arbitrary city and choose in each step a city k not yet on the tour. This city is inserted into the existing tour between two consecutive cities i and j, such that
d(i,k) + d(k,j) - d(i,j)
is minimized. The algorithms stops when all cities are on the tour.
The nearest insertion algorithm chooses city k in each step as the city which is nearest to a city on the tour.
For farthest insertion, the city k is chosen in each step as the city which is farthest to any city on the tour.
Cheapest insertion chooses the city k such that the cost of inserting the new city (i.e., the increase in the tour's length) is minimal.
Arbitrary insertion chooses the city k randomly from all cities not yet on the tour.
Nearest and cheapest insertion tries to build the tour using cities which fit well into the partial tour constructed so far. The idea behind behind farthest insertion is to link cities far away into the tour fist to establish an outline of the whole tour early.
Additional control options:
start
index of the first city (default: random city).
"nn", "repetitive_nn"
Nearest neighbor and repetitive nearest neighbor algorithms for symmetric and asymmetric TSPs (Rosenkrantz et al. 1977).
The algorithm starts with a tour containing a random city. Then the algorithm always adds to the last city on the tour the nearest not yet visited city. The algorithm stops when all cities are on the tour.
Repetitive nearest neighbor constructs a nearest neighbor tour for each city as the starting point and returns the shortest tour found.
Additional control options:
start
index of the first city (default: random city).
"2-opt"
Two edge exchange improvement procedure (Croes 1958).
This procedure systematically exchanges two edges in the graph represented by the distance matrix till no improvements are possible. Exchanging two edges is equal to reversing part of the tour. The resulting tour is called 2-optimal.
By default, improvement starts with a random tour.
Additional control options:
tour
an existing tour which should be improved. If no tour is given, a random tour is used.
rep
number of times to try 2-opt with a different initial random tour (default: 1).
"concorde"
Concorde algorithm (Applegate et al. 2001).
Concorde is an advanced exact TSP solver for only symmetric TSPs
based on branch-and-cut. The program is not included in this package and
has to be obtained and installed separately (see
Concorde
).
Additional control options:
exe
a character string containing the path to the executable
(see Concorde
).
clo
a character string containing command line options for
Concorde, e.g., control = list(clo = "-B -v")
. See
concorde_help
on how to obtain a complete list of available
command line options.
precision
an integer which controls the number of
decimal places used for the internal representation of distances in
Concorde. The values given in x
are multiplied by
10^{precision} before being passed on to Concorde. Note that
therefore the results produced by Concorde (especially lower and upper
bounds) need to be divided by 10^{precision} (i.e., the decimal point
has to be shifted precision
placed to the left). Note also, that
Concorde cannot handle Inf
which is therefore replaced by 2 times
the maximum value in x
(ignoring the infinity entries). The
interface to Concorde uses write_TSPLIB
(see there for more
information).
"linkern"
Concorde's Chained Lin-Kernighan heuristic (Applegate et al. 2003).
The Lin-Kernighan (Lin and Kernighan 1973)
heuristic uses variable k edge exchanges to
improve an initial tour. The program is not included in this package and
has to be obtained and installed separately (see
Concorde
).
Additional control options: see Concorde above.
An object of class TOUR
.
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.
TOUR
,
TSP
,
ATSP
,
write_TSPLIB
,
Concorde
.
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 ## Not run: tours$concorde <- solve_TSP(tsp, method = "concorde") tours$linkern <- solve_TSP(tsp, method = "linkern") ## End(Not run) ## 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")