最適集合駅探索 Web サービスの構築

平成○年○月○日
最適集合駅探索 Web サービスの構築
学籍番号：0010000
氏名：○○○○
1. はじめに
総務省の調査によれば，PC からのインターネット利用者の 38.9%が過去 1 年以内に路線探索
などの地図情報提供サービスを利用している[1]。
路線探索サービスは便利であるが，複数地点にいる人間が集合地点を決めるような場合には，
意外にも不便である。例えば，千葉駅と横浜駅と大宮駅にいる 3 人が集合すべき場所を探そうとす
ると，東京駅など適当な候補駅をいくつか思い浮かべた後，候補駅と 3 つの駅の間の路線探索を
行って，適切かどうかを確認する作業を繰り返す必要がある。複数の駅を出発地点として，適切な
集合駅を探索したいといった需要は，少なからずあるはずだが，そのような需要に応えるサービス
は，現在のところ，Web 上に提供されていない。
本研究では，Web 上で適切な集合駅を探索するサービスを構築することを目的とし，東京近辺
に地域を限定したプログラムを試作した。本稿では，最適集合地点を探索する手法と，試作した最
適集合駅探索 Web サービスについて報告する。
2. システムの構築
2.1. データの整備
本研究では，駅データ[2]から東京都，千葉県，埼玉県，神奈川県を通る主要な 125 路線から
2031 駅を抽出した。抽出した駅のうち，徒歩で乗換可能な駅同士をグループ化し，1492 の駅グル
ープを定義した。また，時刻表[3]および路線探索サービスなどを参考に，隣接駅間に，代表的な
所要時間（分）を設定した。さらに，駅グループ内のすべての 2 駅の組み合わせに対して，乗換の
所要時間として 5 分を設定した。
2.2. 実装方法
本システムは，図 1 に示すように，「駅間所要時間算出」，「駅グループ間所要時間算出」，「最
適駅探索」の 3 つの部分から構成される。
2.2.1. 駅間所要時間算出
テーブル「駅」，「隣接駅」を用いて，任意の 2 駅の間の最短所要時間を算出した。最短所要時
間の算出には Floyd アルゴリズム[4]を利用した。駅数を n としたとき，本処理の計算量は O(n3)であ
る。算出結果はテーブル「駅間所要時間」に格納した。
《中略》
1
[1]
駅データ
駅グループ
データ
駅間所要時間
算出
隣接駅
データ
[2]
駅グループ間
所要時間算出
駅間
所要時間
クライアントPC
[3]
最適集合駅探索
駅ｸﾞﾙｰﾌﾟ間
所要時間
Web
ブラウザ
Webサーバー
駅データ
駅グループ
データ
図 1 システムの概要
3. 実行結果
本システムの実行例を示す。
《中略》
4. おわりに
本研究では，出発駅を複数与え，最適な集合駅を探索する Web サービスを構築した。東京，
千葉，埼玉，神奈川限定ではあるが，概ね妥当な結果を得られることが確認できた。
今後の課題として，探索対象地域の拡大と評価基準の見直しが挙げられる。本手法では駅数
の 2 乗に比例した記憶領域が必要なため，探索対象地域の拡大には，対象地域の分割を行うなど
の工夫が必要である。また，現在の評価基準では，お互いに近接した複数の出発駅と遠く離れた
出発駅が 1 つあるような状況では，実感に合わない最適駅が結果として出力されることがある。今
後，ユーザーの目的に応じて，距離の総和など別の評価基準を選択できるよう検討を行っていき
たい。
参考文献
[1] 総務省，『平成 21 年度通信利用動向調査報告書』，p.62，
http://www.soumu.go.jp/johotsusintokei/statistics/pdf/HR200900_001.pdf，2010 年 9 月 16 日.
[2] 株式会社コードプラス, 『駅コード.jp』, http://www.ekidata.jp/, 2010 年 5 月 21 日.
[3] JTB パブリッシング交通図書編集部編, 『JTB 時刻表』, JTB パブリッシング, 2010.
[4] R. W. Floyd, “Algorithm 97: shortest path”, Comm. ACM, 5(6), p.345, 1967.
2