Interestingly, exact solution to the ordering problem, or the traveling salesman problem (TSP) in common terminology, is one of the most complex problems, classified under combinatorial optimization. Traveling to n cities (vertices) requires checking (n-1)! possibilities. In my endeavor, 3,000 locations had 4*10^9131 possible solutions. This number is larger than the number of sands in any beach I know of!
This post investigates the performance of R packages: TSP and tspmeta. The results were significantly satisfactory for my use. Particularly, the ability to manipulate data in R is glorious.
TSP-R package does not provide a built-in exact solver but provides following 7 heuristic solutions:
- 2-opt
- Nearest Neighbor
- Repetitive Nearest Neighbor
- Insertion algorithms (nearest, farthest, cheapest and arbitrary)
#1 TPS225.tsp: 225 vertices in 2D
The following code input your TSP225.csv file and outputs your solution and the visualization. The ‘tour’ object generated is a class of TOUR and integer; it contains your solution.
library(tspmeta)
TSP225 <- read.csv("TSP225.csv")
coords.df <- data.frame(long=TSP225$Long, lat=TSP225$Lat)
coords.mx <- as.matrix(coords.df)
# Compute distance matrix
dist.mx <- dist(coords.mx)
# Construct a TSP object
tsp.ins <- tsp_instance(coords.mx, dist.mx )
#
tour <- run_solver(tsp.ins, method="2-opt")
#Plot
autoplot(tsp.ins, tour)
Comparing solutions: Plot below shows the optimal tour length for the 7 heuristic solutions and the exact solution by Concorde. For Concorde solution, I used NEOS-Server hosted at UW-Madison.
methods <- c("nearest_insertion", "farthest_insertion",
"cheapest_insertion", "arbitrary_insertion", "nn", "repetitive_nn",
"2-opt")
tours <- sapply(methods, FUN = function(m) run_solver(tsp.ins, method = m), simplify = FALSE)
dotchart(c(sapply(tours, FUN = attr, "tour_length"), "Concorde, NEOS)" = 3916),
xlab = "Tour length (n=225)", main="Heuristic Solutions vs. Exact (concorde)")
#2 3000 random vertices in 2D
Apparently, as the number of vertices grow, difference between the exact solution and other heuristic solutions grow significantly. 2-opt solutions is closest to the optimal. Repeating 2-opt solution and picking the smallest value got me really close to the exact solution (its not shown below.)
Some useful stuff:
Order Theory
TPS – Infrastructure for the Traveling Salesperson Problem