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

 

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)

<お知らせ>
ITソリューション検討Information

マイナビニュースのIT Search+では、ITソリューションの検討に役立つ情報を掲載しています。
ここでは、IT Search+の人気記事ベスト3をご紹介。ぜひ、ビジネスにお役立てください。



人気記事

一覧

イチオシ記事

新着記事

【特別企画】カシオ「EXILIM」とリプレックス「Scene」の連携に見る - ハードウェアとサービスの幸せな関係
[07:00 9/28] スマホとデジタル家電
お金の神様 第20回 ボーナスが実力主義
[07:00 9/28] マネー
ココリコ、ガムを噛みながら打席に入る"メジャー級"の中学同級生が登場
[07:00 9/28] エンタメ
平井理央、"優良物件"のような同級生登場 - グループ交際でディズニーにも
[07:00 9/28] エンタメ
ランドセル選びってどうだった? ママ・パパ300人に直撃--35%が後悔した事は
[07:00 9/28] ライフスタイル