"identity", "random" return a tour representing the order in the data
(identity order) or a random order. [TSP, ATSP]
"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). [TSP, ATSP]
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:
"nn", "repetitive_nn" Nearest neighbor and repetitive
nearest neighbor algorithms for symmetric and asymmetric TSPs (Rosenkrantz
et al. 1977). [TSP, ATSP]
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:
"sa" Simulated Annealing for TSPs (Kirkpatrick et al, 1983) [TSP, ATSP]
A tour refinement method that uses simulated annealing with subtour
reversal as local move. The used optimizer is
stats::optim() with method "SANN". This method is
typically a lot slower than "two_opt" and requires parameter tuning for the
cooling schedule.
Additional control options:
"tour" an existing tour which should be improved.
If no tour is given, a random tour is used.
"local_move" a function that creates a local move with the current
tour as the first and the TSP as the second parameter. Defaults to
randomized subtour reversal.
"temp" initial temperature. Defaults to the length of the current tour divided
by the number of cities.
"tmax" number of evaluations per temperature step. Default is 10.
"maxit" number of evaluations. Default is 10000 for speed, but larger values
will result in more competitive results.
"trace" set to 1 to print progress.
See stats::optim() for more details on the parameters.
"two_opt" Two edge exchange improvement procedure (Croes 1958). [TSP, ATSP]
This is a tour refinement procedure which 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.
This method can be applied to tours created by other methods or used as its
own method. In this case 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.
"two_opt_repetitions" number of times to try two_opt with a
different initial random tour (default: 1).
"concorde" Concorde algorithm (Applegate et al. 2001). [TSP, ETSP]
Concorde is an advanced exact TSP solver for symmetric TSPs
based on branch-and-cut.
ATSPs can be solved using reformulate_ATSP_as_TSP() done automatically
with as_TSP = TRUE.
The program is not included in this package and
has to be obtained and installed separately.
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). The interface to Concorde uses
write_TSPLIB().
"verbose" logical; FALSE suppresses the output printed to the terminal.
"linkern" Concorde's Chained Lin-Kernighan heuristic (Applegate et al. 2003). [TSP, ETSP]
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.