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!
TSP-R package does not provide a built-in exact solver but provides following 7 heuristic solutions:
- 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: