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