Tags

, , , ,

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)

tsp225_2-opt

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)")

dotchart_tsp225

 

 #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.)

tsp3000_2-opt 3000 locations

Some useful stuff:

Order Theory

TPS – Infrastructure for the Traveling Salesperson Problem

 

Advertisements