Rでポケモンスタンプラリー(2/3) {tidygraph}で最短経路検索
estrellita.hatenablog.com の続き。今回は{tidygraph}を利用してスタンプ設置駅間の最短経路を取得する。
- データ準備
- 路線ネットワークに必要なノードとエッジのデータを作成
{tidygraph}でスタンプ設置駅間の最短経路探索（ ← イマココ）- 路線ネットワークデータからスタンプ設置駅の最短距離を探索
{TSP}で巡回セールスマン問題を解く- 各スタンプ設置駅間の距離行列から移動距離が最短となるような巡回順を探索
目次
グラフオブジェクトの作成
前回作成したグラフの辺情報edgeからtidygraph::as_tbl_graph()でグラフオブジェクトを作成し、ノード情報nodeと結合することで駅名や緯度・経度などの情報を追加する。
g <- edge %>% tidygraph::as_tbl_graph(directed = FALSE) %>% dplyr::inner_join(node, by = c("name" = "station_g_cd")) > g # A tbl_graph: 1780 nodes and 2186 edges # # An undirected multigraph with 1 component # # Node Data: 1,780 x 5 (active) name station_name line_cd lon lat <chr> <chr> <chr> <chr> <chr> 1 1122934 内郷 11229 140.855005 37.035895 2 1122933 湯本 11229 140.849884 37.006922 3 1122932 泉 11229 140.854125 36.955602 4 1122931 植田 11229 140.796468 36.920649 5 1122930 勿来 11229 140.786506 36.883883 6 1122929 大津港 11229 140.778001 36.846085 # … with 1,774 more rows # # Edge Data: 2,186 x 4 from to line_cd dist <int> <int> <chr> <dbl> 1 1 1726 11229 4140. 2 1 2 11229 3248. 3 2 3 11229 5708. # … with 2,183 more rows
ネットワークグラフの可視化
{ggraph}で可視化してみる。駅の座標は手動で設定したいため、layout = "manual"とし必要な座標情報を作成する。
coord <- g %>% tidygraph::activate(nodes) %>% dplyr::rename(x = lon, y = lat) %>% dplyr::select(x, y) %>% dplyr::as_tibble() %>% dplyr::mutate_if(is.character, list(as.numeric)) coord %>% head() %>% knitr::kable()
| x | y |
|---|---|
| 140.8550 | 37.03589 |
| 140.8499 | 37.00692 |
| 140.8541 | 36.95560 |
| 140.7965 | 36.92065 |
| 140.7865 | 36.88388 |
| 140.7780 | 36.84609 |
ノードの座標を手動で設定するにはggraph::ggraph()でlayout = "manual"、node.positionに座標情報を指定する。
g %>% ggraph::ggraph(layout = "manual", node.position = coord) + ggraph::geom_node_point(color = "gray") + ggraph::geom_edge_link(ggplot2::aes(color = line_cd), alpha = 0.8)
ヘアボール化して駅名が読み取れないが正しく路線ネットワークを再現できている。
最短経路の取得
tidygraph::node_distance_to()で各駅に対してスタンプ設置駅への最短経路の距離を計算する。距離を計算するにあたり、weightに駅間の距離であるdistを指定する。
station <- g %>% tidygraph::activate(nodes) %>% tidygraph::pull(station_name) for(i in seq_along(stamp$name_j)) { varname <- paste0("dist_", stamp$name_e[i]) target <- which(station == stamp$name_j[i]) g <- g %>% tidygraph::activate(nodes) %>% dplyr::mutate(!!varname := tidygraph::node_distance_to(target, weights = dist)) } g # A tbl_graph: 1780 nodes and 2186 edges # # An undirected multigraph with 1 component # # Node Data: 1,780 x 48 (active) name station_name line_cd lon lat dist_Ageo dist_Ikebukuro dist_Itabashi dist_Omiya <chr> <chr> <chr> <chr> <chr> <dbl> <dbl> <dbl> <dbl> 1 1122… 内郷 11229 140.… 37.0… 206314. 201008. 202856. 198189. 2 1122… 湯本 11229 140.… 37.0… 203067. 197760. 199608. 194941. 3 1122… 泉 11229 140.… 36.9… 197359. 192052. 193901. 189233. 4 1122… 植田 11229 140.… 36.9… 190923. 185616. 187464. 182797. 5 1122… 勿来 11229 140.… 36.8… 186747. 181440. 183289. 178621. 6 1122… 大津港 11229 140.… 36.8… 182485. 177178. 179026. 174359. # … with 1,774 more rows, and 39 more variables: dist_Kawasaki <dbl>, dist_Kichijoji <dbl>, # dist_Sakuragicho <dbl>, dist_Shibuya <dbl>, dist_Shinjuku <dbl>, dist_Tachikawa <dbl>, # dist_Nakano <dbl>, dist_Hasuda <dbl>, dist_Hachioji <dbl>, `dist_Higashi-Totsuka` <dbl>, # `dist_Musashi-Urawa` <dbl>, dist_Meguro <dbl>, dist_Yokohama <dbl>, dist_Akihabara <dbl>, # dist_Ushiku <dbl>, dist_Kashiwa <dbl>, dist_Kanda <dbl>, `dist_Kita-Senju` <dbl>, # dist_Kinshicho <dbl>, `dist_Koshigaya-Laketown` <dbl>, `dist_Shin-Urayasu` <dbl>, # dist_Sugamo <dbl>, dist_Tamachi <dbl>, dist_Tsudanuma <dbl>, dist_Tokyo <dbl>, # dist_Toride <dbl>, dist_Nippori <dbl>, `dist_Haneda-Airport-International-Terminal` <dbl>, # dist_Hamatsucho <dbl>, dist_Ryogoku <dbl>, dist_Akabane <dbl>, dist_Ichigaya <dbl>, # dist_Ueno <dbl>, dist_Ofuna <dbl>, dist_Kamata <dbl>, dist_Shinagawa <dbl>, dist_Chiba <dbl>, # `dist_Nishi-Ogikubo` <dbl>, dist_Matsudo <dbl> # # Edge Data: 2,186 x 4 from to line_cd dist <int> <int> <chr> <dbl> 1 1 1726 11229 4140. 2 1 2 11229 3248. 3 2 3 11229 5708. # … with 2,183 more rows
内郷から上尾には約206km、湯本から池袋には約197km電車に乗るということになる。
各駅からスタンプ設置駅までの最短距離が求まったので、最後にスタンプ設置駅間の距離行列を作成し、{TSP}パッケージで巡回セールスマン問題を解く。
