経路探索の仕組み
「駅すぱあと」(ヴァル研究所)など

 仕事先の訪問からちょっとした旅行まで,電車を使ったお出かけに便利なのが路線の探索ソフト/サービスです。出張や旅行で初めて訪ねる町でも,どうすれば希望の時刻に着けるかを分単位で教えてくれます。パソコン用のソフトとしてはもちろん,今ではインターネット上にも携帯電話やブラウザで利用できるサービスがあります。

 路線探索の定番ソフト「駅すぱあと」(図3)の開発本部長を務めているヴァル研究所の宮本雅臣取締役に,どうやって作っているのか,そして難しいのはどこか,尋ねてみました。意外にも,「最短経路を求めるアルゴリズムは,教科書通りといってしまえばその通りなんです」(宮本氏)と言います。

図3●路線探索ソフト「駅すぱあと」。一番早く着ける経路のほか,いくつかの候補を示してくれる
図3●路線探索ソフト「駅すぱあと」。一番早く着ける経路のほか,いくつかの候補を示してくれる

 公共交通の路線は,駅と駅をノード(節)として,ノード間を枝でつないだ「グラフ」というデータ構造で表すことができます。ノード間を結ぶ枝には所要時間に相当する重みを付けます(図4(1))。

図4●最短距離を見つけるDijkstraのアルゴリズム
図4●最短距離を見つけるDijkstraのアルゴリズム

 グラフの「最短経路の探索」にも効率の良い方法が考えられています。例えば,一つのノードからほかのすべてのノードへの最短距離を求める有名なアルゴリズムに,「Dijkstra(ダイクストラ)のアルゴリズム」があります。Dijkstraのアルゴリズムは,最短距離が確定しているノードから直接移動できるノードへの距離を求めて,その中で一番短いものを確定済みのグループに入れる,という作業を未確定のノードがなくなるまで繰り返します(2)~(4)。このとき確定済みのどのノードからの距離かを記録すれば,最短経路もわかります。

 これで,データさえ正しければ,一番早く着く経路は間違いなく見つかります。ただし,検索するたびに日本全国のすべてのデータを計算している時間はないので,不要な計算はなるべく省くようにデータの持ち方などを工夫しているそうです。いずれにしても最短経路を求めるのはさほど難しくないようです。では何が難しいのでしょうか?

 「2番目以降に表示する経路です。これは“早い,安い”ではダメなんです」(宮本氏)。例えば,2番目に短い時間で着く経路を計算で探すと,“最短経路で使う特急を一駅手前で降りて,残りを各駅停車で行く”といった答えが出てしまうそうです。「それは確かに2番目に早く着く方法かもしれません。しかし,ユーザーが2番目の選択肢として求めているのはおそらくそういう答えではないと考えています」(宮本氏)。

 より自然な2番目,3番目の答えを求めるには,計算で出てくる不自然な答えを取り除くロジックを組み込む地道な作業が必要になります。すなわち,「頭脳よりは体力の勝負」(宮本氏)というわけです。これからも,単に“早い,安い”ではなく,例えば乗り換えに掛かる時間を若い人とお年寄りで切り替えるなど,ユーザー一人ひとりに合った答えを出せるような仕組みを取り入れていく予定だそうです。


ここからは会員の登録が必要です。