1万の停留所には1億の移動パターン!Google、乗換案内の最適化方法を解説

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

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

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