att480 and a280 instances of TSP

jmsallan · May 27, 2018 · 78aa450 · 78aa450
1 parent 2350f20
commit 78aa450
Show file tree

Hide file tree

Showing 4 changed files with 74 additions and 4 deletions.
diff --git a/TSP/code/functionsTSP2.R b/TSP/code/functionsTSP2.R
@@ -372,7 +372,7 @@ GRASP <- function(D, rcl.size, start=1){
 
 }
 
-GRASP2opt <- function(D, rcl.size, tries, start=1, ls="TS"){
+GRASP2opt <- function(D, rcl.size, tries, start=1, iter=50, ls="TS"){
 
   n <- dim(D)[1]
 
@@ -386,9 +386,9 @@ GRASP2opt <- function(D, rcl.size, tries, start=1, ls="TS"){
     initial.solution <- GRASP(D, rcl.size)
 
     if(ls=="TS")
-        refined.solution <- TSTSP2opt(D, initial.solution$sol, iter=10*n)
+        refined.solution <- TSTSP2opt(D, initial.solution$sol, iter=iter)
       else
-        refined.solution <- SATSP2opt(D, initial.solution$sol, Tmax=n*100)
+        refined.solution <- SATSP2opt(D, initial.solution$sol, Tmax=n*(n-3)*50)
 
     if(refined.solution$fit <= bestfit){
       bestfit <- refined.solution$fit

diff --git a/TSP/countriesDemo.R b/TSP/countriesDemo.R
@@ -0,0 +1,66 @@
+#set wd!
+
+source("code/functionsTSP2.R")
+
+load("results/TSPcities.Rdata")
+
+#----loading country instances-----
+
+library(netgen)
+
+#att48. optimal tour has length 10628
+
+att48 <- importFromTSPlibFormat("instances/att48.tsp")
+Datt48 <- att48$distance.matrix
+
+#nearest neighbour
+NNatt48 <- NearestNeighbour(Datt48)
+
+#tabu search
+TS01att48 <- TSTSP2opt(Datt48, NNatt48$sol, iter=40, tabu.size = 5, eval = TRUE)
+plot(1:40, TS01att48$evalbest, type="l", xlab="", ylab="")
+
+#simulated annealing
+set.seed(1111)
+SA01att48 <- SATSP2opt(Datt48, NNatt48$sol, Tmax=10000, mu=1, eval = TRUE)
+plot(1:10000, SA01att48$evalbest, type="l", xlab="", ylab="")
+
+#ILS
+set.seed(1313)
+ILS01att48 <- ILSTSTSP2opt(Datt48, NNatt48$sol, rounds=50, iter=50)
+ILS02att48 <- ILSTSTSP2opt(Datt48, 1:48, rounds=50, iter=50)
+
+#comparing ILS
+plot(1:50, ILS02att48$evalbest, type = "l", col="red", xlab="", ylab="")
+lines(1:50, ILS01att48$evalbest, col="blue")
+
+#GRASP
+set.seed(2222)
+GRASP01att48 <- GRASP2opt(Datt48, rcl.size = 2, tries=50, iter=50)
+
+#a280. optimum 2579
+
+a280 <- importFromTSPlibFormat("instances/a280.tsp")
+Da280 <- a280$distance.matrix
+
+#nearest neighbour
+NNa280 <- NearestNeighbour(Da280)
+
+#tabu search
+TS01a280 <- TSTSP2opt(Da280, NNa280$sol, iter=40, tabu.size = 5, eval = TRUE)
+plot(1:40, TS01att48$evalbest, type="l", xlab="", ylab="")
+
+set.seed(1313)
+SA01a280 <- SATSP2opt(Da280, NNa280$sol, Tmax=310000, mu=1, eval = FALSE)
+
+#ILS
+set.seed(1313)
+ILS01a280 <- ILSTSTSP2opt(Da280, NNa280$sol, rounds=30, iter=40)
+ILS02a280 <- ILSTSTSP2opt(Da280, 1:280, rounds=30, iter=40)
+
+set.seed(1111)
+GRASP01a280 <- GRASP2opt(Da280, rcl.size = 2, tries=30, iter=40)
+
+
+
+save.image("results/TSPcities.Rdata")
diff --git a/TSP/instances/00readingTSPcities.R b/TSP/instances/00readingTSPcities.R
@@ -1,7 +1,8 @@
 # http://www.math.uwaterloo.ca/tsp/world/countries.html
 # http://www.math.uwaterloo.ca/tsp/world/
 
-setwd("~/Dropbox (UPC)/001-Docencia/COL1617q2/Sallan/data")
+#setwd on data folder!
+
 
 download.TSP <- function(sample){
   url.base <- "http://www.math.uwaterloo.ca/tsp/world/"
@@ -35,3 +36,6 @@ download.TSP("ch71009")
 download.TSP("ei8246")
 download.TSP("it16862")
 download.TSP("kz9976")
+
+#http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/
+
diff --git a/TSP/results/TSPcities.Rdata b/TSP/results/TSPcities.Rdata