"identity", "random"return a tour representing the order
in the data (identity order) or a random order.
"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:
startindex 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:
startindex of the first city (default: random city).
"two_opt"Two edge exchange improvement procedure (Croes 1958).
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:
touran existing tour which should be improved.
If no tour is given, a random tour is used.
two_opt_repetitionsnumber of times to try
two_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:
exea character string containing the path to the executable
(see Concorde).
cloa 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.
precisionan 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 (see there for more
information).
%\item{\code{"grasp"}}{
% Greedy Randomized Adaptive Search Procedure (L.S. Pitsoulis
% and M.G.C. Resende 2001).
%
% GRASP is a metaheuristic for combinatorial optimization. It is
% implemented as a multistart procedure, in which in each iteration a
% random route is constructed (construction phase). To find an
% optimum the route is improved by a local search algorithm
% (implemented as k-opt neighborhood search). This is
% repeatedly done until a stopping criterium is reached (i.e., a number of
% iterations).
%
% Additional control options:
% \describe{
% \item{\code{start}}{index of the first city (default: random
% city).}
% \item{\code{iterations}}{an integer containing the number of
% iterations after the algorithm stops (default: 100 iterations).}
% \item{\code{max_i}}{an integer representing the max. steps to find
% a better solution in local search (default: 100 steps).}
% \item{\code{k}}{an integer needed to change k edges of the tour in
% local search (default: 3 cities).}
% }
% }