地点から経路探索してみる。

遅ればせながら、ヴァル研究所 Advent Calendar 2017 25日目の記事です(遅くなってすみません)。

今回は緯度経度と地点を用いた経路探索について紹介してみようと思います。

緯度経度からの探索

駅すぱあとWebサービスでは、駅名を指定した探索だけでなく、出発地・目的地に座標情報(緯度経度)を指定して探索を行うこともできます。

最適な経路は人それぞれ

経路探索では駅すぱあとが最適と判断した経路が返されるのですが、その時々の状況で「最適な経路」は利用者によって異なります。例えば、とにかく早く目的地に着きたい場合や、ゆっくりでも良いのでお値段の安い経路にしたい等です。

緯度経度からの探索では距離的に最も近い駅が最寄駅として選択されますが、以下の図のように近い最寄駅が選択されることで、目的地への到着に時間がかかってしまうパターンも発生する可能性があります。

これはどちらかが正解ということではなく、先の例と同じく利用者によって最適な経路は異なります。結果的に遠回りでも良いので近い駅から交通機関を利用したい・早く目的地に辿りつけるなら、少し歩いて駅に向かうのでも良い等々です。

「地点」の形で最寄駅を指定する

経路探索で緯度経度を指定する方法の他に、地点生成APIを使用することで、「地点」の形で最寄駅を複数指定し、地点から経路探索を行う方法もあります。イメージ的には複数の最寄駅候補を利用者側でピックアップしておくことで、経路探索時の選択肢を増やせるようにする感じです。

地点生成の例

実際に地点を生成してみます。地点生成では駅コード(または駅名)、時間(地点から最寄駅までの時間)が必須パラメータなので、まずはその値を集めます。

駅コードと時間は緯度経度からの周辺駅検索から集めてみます。時間そのものはレスポンスに含まれないので、距離から時間を算出(80mで1分として換算)します。また、取得できる距離は道なりではなく、緯度経度からの直線距離になります。

$ export ACCESS_KEY=アクセスキーを入力してください
$
$ # 緯度経度からの周辺駅検索(/geo/station)で最寄駅までの距離(直線距離)を取得します。
$ # この例では、「末広町」駅の距離を取得します。
$ curl -s "http://api.ekispert.jp/v1/xml/geo/station?key=${ACCESS_KEY}&geoPoint=35.701176841793846,139.7721991683132,wgs84,500" | xmllint --format - > geo_station.xml 

今回は取得したレスポンスから、最寄駅を5件取得します。これは地点生成に指定可能な最寄駅の数が最大5件までであるためです。また、緯度経度からの周辺駅検索では半径を指定しないと最寄駅が1件しか返されない点にご注意ください。

$ # 指定した緯度経度から、最寄駅を5件取得する。
$ # まずは駅コード、駅名、(緯度経度からの)距離を1行にまとめた形にする。
$ curl -s "http://api.ekispert.jp/v1/xml/geo/station?key=${ACCESS_KEY}&type=train&geoPoint=35.68942931789852,139.727520419778,wgs84,1500" \
      | xmllint --format - \
      | egrep -A1 '(<Station |<Distance)' \
      | egrep '(<Station|<Name|<Distance)' \
      | paste -d ' ' - - - \
      | sed -e "s/ //g" \
      | sed -e "s/<Stationcode=\"//g" \
      | sed -e "s/\"><Name>/,/g" \
      | sed -e "s/<\/Name><Distance>/,/g" \
      | sed -e "s/<\/Distance>//g" \
      | head -n5 \
      | tee tmp01.txt
23041,四ツ谷,474
22493,曙橋,550
23042,四谷三丁目,731
22520,市ケ谷,751
22673,麹町,1036

<駅コード>,<駅名>,<距離> がカンマ区切りで取得できました。これに距離から算出した時間を追加します。

$ # 移動時間(80m:1分)を追加して地点生成のパラメータを作成する。
$ station_code_list=''
$ distance_time_list=''
$ distance_list=''
$ traffic_list=''
$ for line in `cat tmp01.txt`
  do
      station_code=`echo $line | cut -d, -f1`
      distance=`echo $line | cut -d, -f3`
      distance_time=$((distance/80))
      # 駅コードのリスト(地点生成パラメータ)
      if [ ! -z "${station_code_list}" ]; then
          station_code_list="${station_code_list}:${station_code}"
      else
          station_code_list=${station_code}
      fi
      # 駅までの所要時間リスト(地点生成パラメータ)
      if [ ! -z "${distance_time_list}" ]; then
          distance_time_list="${distance_time_list}:${distance_time}"
      else
          distance_time_list=${distance_time}
      fi
      # 距離リスト(地点生成パラメータ)
      if [ ! -z "${distance_list}" ]; then
          distance_list="${distance_list}:${distance}"
      else
          distance_list=${distance}
      fi
      # 移動手段リスト(地点生成パラメータ)
      if [ ! -z "${traffic_list}" ]; then
          traffic_list="${traffic_list}:徒歩"
      else
          traffic_list="徒歩"
      fi
  done

必要なパラメータが集められたので、これで地点生成を行います。

$ curl -s "http://api.ekispert.jp/v1/xml/toolbox/course/point?key=${ACCESS_KEY}&name=landmark&stationCode=${station_code_list}&time=${distance_time_list}&distance=${distance_list}&traffic=${traffic_list}" | xmllint --format - > toolbox_course_point.xml
$ point_data=`grep '<SerializeData' toolbox_course_point.xml | sed -e "s/<\/SerializeData>.*$//" -e "s/^.*<SerializeData>//" `
$ echo ${point_data}
P-landmark-23041,22493,23042,22520,22673-5,6,9,9,12--%E5%BE%92%E6%AD%A9,%E5%BE%92%E6%AD%A9,%E5%BE%92%E6%AD%A9,%E5%BE%92%E6%AD%A9,%E5%BE%92%E6%AD%A9-474,550,731,751,1036-0----

最終的に以下のような地点データが取得できました。

P-landmark-23041,22493,23042,22520,22673-5,6,9,9,12--%E5%BE%92%E6%AD%A9,%E5%BE%92%E6%AD%A9,%E5%BE%92%E6%AD%A9,%E5%BE%92%E6%AD%A9,%E5%BE%92%E6%AD%A9-474,550,731,751,1036-0----

あとは地点を指定して経路探索を実行するだけです。

$ curl -s "http://api.ekispert.jp/v1/xml/search/course/plain?key=${ACCESS_KEY}&from=${point_data}&to=築地" \
  | xmllint --format - \
  | egrep -A2 '(<Point|<Line|distance)' \
  | egrep '(<Name|distance)' \
  | grep -v '<Route' \
  | sed -e "s/          <Name>/* /g" \
    -e "s/        <Name>/| /g" \
    -e "s/<\/Name>//" \
    -e "s/^.*distance=\"/|   距離：/" \
    -e "s/\" .*$/m/" \
    -e "s/\">/m/" \
    -e "s/| landmark/* landmark/"

以下のような経路探索結果が得られます。今回は距離をそのまま時間に換算して地点を生成していますが、利用者側で最寄駅までの時間を指定できるため、利用目的に応じて最寄駅を柔軟に設定できます。

* landmark
|   距離：474m
| 徒歩
* 四ツ谷
|   距離：39m
| 東京メトロ丸ノ内線(池袋－荻窪)
* 銀座
|   距離：10m
| 東京メトロ日比谷線
* 築地

まとめ

地点生成を使用して利用者側で最寄駅を柔軟に指定して経路探索を行う方法を紹介しました。地点を用いることで、出発地・目的地の指定がより実際に即した形で行えるようになります。

ヴァル研究所Advent Calendar 2017を振り返って

ヴァル研究所Advent Calendar 2017、最終日の投稿もこれで無事完了できそうです(投稿が遅くなってすみません)。

参加してくださった@aosho235さん、@valitohさん、@nakano348さん、@mist_devさん、@RyujiKawazoeさん、@hmaruyamaさん、@t_ryusukeさん、@ieryさん、@ssusanさん、ありがとうございました。
(お名前は掲載日順です)

ちょっと気が早いですが、2018年のAdvent Calendarに向けて、少しずつ準備(というかネタ集め)できれば良いなと思います。
来年もぜひヴァル研究所Advent Calendarをよろしくお願いいたします。