3月2日(現地時間)、GoogleはGoogleマップ上で使用する公共機関などを用いた移動方法検索技術の最適化方法を公式ブログで解説した。Googleは各大学の研究機関と連携し、次世代のルート計画を研究していたが、それらの成果から移動パターンを見直し、「A地点からC地点へ電車で移動して、次にC地点からB地点へバスで移動する」よりも、「A地点からB地点へバスで直接移動して、たまに早足で歩く」など、合理的な移動パターンの提示を可能にしている。

世界70カ国2万以上の都市に対応したGoogleマップの乗り換え案内機能

これらの移動パターンは事前に計算して保持しているが、問題は対応する国々の拡大に伴って、計算量が増えてしまう点だ。例えば1万の停留所に対しては1億の移動パターンが必要になるため、拡張性がある移動パターンアルゴリズムを導入することで改善している。下図は公式ブログに掲載されたドイツのバス路線図をクラスター化し、境界駅(異なるエリア間の境界となるバスの停留所)をハイライトしたものだ。

ドイツの公共輸送ネットワーク。25万1,763の停留所のうち、1万886カ所(4.32パーセント)が境界駅となる

まずは各クラスター内の最適な接続の移動パターンを計算し、次に任意のクラスターペアの移動パターンを計算。そして本当に必要な境界駅へのアクセスを導き出している。これらの結果を保存し、クエリに応じて我々ユーザーに移動方法を提示するのがGoogleマップの乗り換え案内機能だ。

こちらはベルリンの境界駅(青色)と最適化した境界駅(赤色および黒色の線)で示したもの。592の移動パターンに対して重要なのは111の移動パターンであることが確認できる

Googleマップの乗り換え案内機能は、2005年12月の開始時点でオレゴン州ポートランドに留まっていたが、2010年の検索速度向上を経て、現在では日本を含めた世界70カ国2万以上の都市に対応している。

阿久津良和(Cactus)