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)

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