放送大学

巡回セールスマン問題ggmap

巡回セールスマン問題ggmap

センターの間を直線でなく経路で結ぶ

（準備）
ggmapパッケージを使って経路の距離行列を作成し、保存する。
制約があるので一回では作成できないし、時間がかかる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
library(ggmap)
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")
nr<-nrow(sc)
#距離・時間行列の作成
travelmode="driving"
distance=matrix(0,nr,nr)
for(i in 1:nr){
	x_i=sc[i,]
	loc_i=c(x_i$lon,x_i$lat)
	for(j in (i+1):nr){
		x_j=sc[j,]
		loc_j=c(x_j$lon,x_j$lat)
route.ij=route(loc_i,loc_j,mode=travelmode,structure="route")
		distance[i,j]=distance[j,i]<-sum(route.ij$km,na.rm=T)
	}
}
save(distance, file="distance.dat")
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
library(ggmap)
library(TSP)
concorde_path("/home/user")
#フォルダ名ファイル名は環境によって違います。
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")
nr<-nrow(sc)
load("/home/user/R/work/JPN/distance.dat")
rownames(distance)<-sc$name
colnames(distance)<-sc$name
shortest<-solve_TSP(TSP(ATSP(distance)), method ='concorde')
lat=sc$lat
lon=sc$lon
map <- get_googlemap(center=c(139,35),zoom=5)
map<-ggmap(map)+geom_point(data=sc,mapping=aes(x=lon,y=lat),size=2,colour="red")
#巡回経路の図示
travelmode="driving"
for(i in 1:(nr-1)){
	h1=shortest[i]
	h2=shortest[i+1]
route1=na.omit(route(c(lon[h1],lat[h1]),c(lon[h2],lat[h2]),mode=travelmode,structure="route"))
	print(route1)
map=map+geom_path(data=route1,aes(x=lon,y=lat),size=0.75,colour="blue",alpha=0.75)
}
	h1=shortest[nr];h2=shortest[1]
route1=na.omit(route(c(lon[h1],lat[h1]),c(lon[h2],lat[h2]),mode=travelmode,structure="route"))
	print(route1)
map=map+geom_path(data=route1,aes(x=lon,y=lat),size=0.75,colour="blue",alpha=0.75)
map