This vignette introduces how to solve TSP problems using the R package TSP (Hahsler and Hornik 2007). The traveling salesperson problem asks for the shortest round trip that visits each city exactly once. The TSP package provides classes for representing traveling salesperson problems, several construction and improvement heuristics, and interfaces to the external Concorde solver.
This vignette covers the typical workflow:
- Create a problem from coordinates or a distance matrix.
- Find a tour with
solve_TSP(). - Inspect, and visualize a solution.
Basic Usage
Create a TSP problem from coordinates
The standard representation of a symmetric TSP is a distance matrix. For locations described by coordinates you can calculate distances before creating the TSP object. Here we create a Euclidean traveling salesperson problem fro ma dataframe with coordinates. Row names are used as city labels.
cities <- data.frame(
x = c(0.15, 0.38, 0.62, 0.82, 0.78, 0.55, 0.28, 0.08),
y = c(0.20, 0.08, 0.18, 0.42, 0.78, 0.92, 0.80, 0.52),
row.names = LETTERS[1:8]
)
problem <- TSP(dist(cities))
problem
#> object of class 'TSP'
#> 8 cities (distance 'euclidean')
n_of_cities(problem)
#> [1] 8
labels(problem)
#> [1] "A" "B" "C" "D" "E" "F" "G" "H"Note, that there are other representations for Euclidean TSPs
ETSP() and asymmetric TSPs ATSP() available.
Most algorithms will convert them into a distance-based representation
first.
Solve the problem
solve_TSP() returns a TOUR, an integer
permutation giving the order in which the cities are visited. The
default combines arbitrary insertion with 2-opt improvement.
set.seed(123)
tour <- solve_TSP(problem)
tour
#> object of class 'TOUR'
#> result of method 'arbitrary_insertion+two_opt' for 8 cities
#> tour length: 2.430432
as.integer(tour)
#> [1] 7 6 5 4 3 2 1 8
labels(tour)
#> [1] "G" "F" "E" "D" "C" "B" "A" "H"
tour_length(tour)
#> [1] 2.430432The stored tour length includes the final edge from the last city back to the first. A TSP solution is therefore a cycle, not an open path.
Plot the coordinates and the resulting tour with
plot():

Where to go next
Read about the available TSP solvers.
The most useful help pages are:
-
?solve_TSPfor all solvers and their control parameters; -
?TSP,?ETSP, and?ATSPfor problem representations; -
?TOURand?tour_lengthfor working with solutions; -
?read_TSPLIBand?write_TSPLIBfor TSPLIB files; and -
?insert_dummyand?cut_tourfor turning a cycle into one or more paths. ## References