放送大学

メタヒューリスティクス2

放送大学の全国の学習センターとサテライトスペースの最短巡回経路の近似解を求めます。

(RのTSPパッケージを使います。)

（準備）
センター名、住所、緯度、経度からなるcsvデータsc.csvを作成

  1. 学習センター・サテライトスペース所在地一覧から住所を入手。
    XMLのreadHTMLTableパッケージを使い、エディタにコピペ。あとはエディタ等を使って加工。
  2. Geocoding - 住所から緯度経度を検索で検索し、コピー＆ペースト

シェイプファイルを Global Administrative Areas からダウンロード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
library(maptools)
library(rgdal)
library(sp)
library(TSP)
#shapeファイル、sa.csvのフォルダ名ファイル名は環境によって違います。
jpn<-readShapeSpatial("/home/user/R/work/JPN/JPN_adm0.shp")
sc <- read.table("/home/user/R/work/sc.csv", header=TRUE, sep=",", na.strings="NA", dec=".", strip.white=TRUE)
names(sc)<-c("name","address","lat","lon")
#spDistsN1で距離を計算。距離行列を作成。
nr<-nrow(sc)
distance = matrix(0, nr, nr)
 for(i in 1:(nr-1)){
   sc_i = sc[i,]
   loc_i = cbind(sc_i$lon, sc_i$lat)
   for(j in (i+1):nr){
     sc_j = sc[j,]
     loc_j = cbind(sc_j$lon,sc_j$lat)
     route_ij = spDistsN1(loc_i, loc_j,longlat=TRUE)
    distance[i,j] = distance[j,i] = route_ij
   }
 }
rownames(distance)<-sc$name
colnames(distance)<-sc$name
#solve_TSP関数のすべてのmethodを使って最短経路を計算。パラメータはdefault
methods <- c("nearest_insertion", "cheapest_insertion", "farthest_insertion", "arbitrary_insertion", "nn", "repetitive_nn", "2-opt")
tours <- lapply(methods, FUN = function(m) solve_TSP(TSP(ATSP(distance)), method = m))
names(tours) <- methods
tour_lengths <- c(sapply(tours, FUN = attr, "tour_length"))
#最短のmethodを確認
tour_lengths

nearest_insertion cheapest_insertion farthest_insertion arbitrary_insertion nn repetitive_nn 2-opt
6383.965 6351.786 6234.314 6269.559 7841.229 6950.645 6190.954

経路が最短のmethodを選んでshortestに入れる
最短のmethodは毎回異なる
以下はmethodに2-optを選択した場合 

1
2
3
4
5
6
7
8
shortest<-tours$'2-opt'
shortest
#経路1番から6番までを表示
shortest[1:6]
order<-as.integer(shortest)
#データscを経路順に並べ替え
sctsp <- sc[ order,]
head(sctsp)

佐賀学習センター 熊本学習センター 長崎学習センター 沖縄学習センター 鹿児島学習センター 宮崎学習センター
51 53 52 57 56 55

name address lat lon
51 佐賀学習センター 佐賀県佐賀市天神3-2-11 33.26010 130.2920
53 熊本学習センター 熊本県熊本市中央区黒髪2-40-1 32.81635 130.7270
52 長崎学習センター 長崎県長崎市文教町1-14 32.78613 129.8647
57 沖縄学習センター 沖縄県中頭郡西原町字千原1 26.24759 127.7653
56 鹿児島学習センター 鹿児島県鹿児島市山下町14-50 31.59957 130.5578
55 宮崎学習センター 宮崎県日向市本町11-11 32.42350 131.6241

地図を描いて経路をプロット

1
2
3
4
5
6
7
8
9
10
11
proj4string(jpn)="+proj=longlat"
plot(jpn, xlim=c(127.5, 149), ylim=c(26, 45.5),xlab="", ylab="",col="#d0e0ff",axes=F,border="grey")
points(sctsp$lon, sctsp$lat,col="blue",pch=16,cex=0.8) 
#nr<-nrow(sc)
 for(i in 1:(nr-1)){
   sc_i = sctsp[i,]
     sc_j = sctsp[(i+1),]
     segments(sc_i$lon,sc_i$lat,sc_j$lon,sc_j$lat,lwd = 1, col = "red")
 }
segments(sctsp[nr,]$lon,sctsp[nr,]$lat,sctsp[1,]$lon,sctsp[1,]$lat,lwd=1,col="red")
title(main="学習センター最短直線経路(RのTSPパッケージで得た近似解の一例)")