道路網を効率的に分割して最短経路探索を高速化(2/2)

１．道路網を効率的に分割して最短経路探索を高速化(2/2)まとめ

・最初に緊密に接続されたノード同士をグループ化してグラフを小さくする
・これを実現するためにランダムウォークを使用して閉じた領域を捜している
・閉じた領域群をグループ化してシンプルな地図にして最短経路を捜している

２．ランダムウォークを使ってパーティショニング

以下、ai.googleblog.comより「Efficient Partitioning of Road Networks」の意訳です。元記事の投稿は2021年9月30日、Ali Kemal SinopさんとMahmuda Ahmedさんによる投稿です。

アイキャッチ画像のクレジットはPhoto by Alexander Schimmeck on Unsplash

私達のパーティショニングアルゴリズム

2つのコンポーネント間の各接続は潜在的なビーコンであるため、ビーコンが多すぎないようにするためのアプローチは、コンポーネント間の接続数を最小限に抑えるように道路ネットワークを分割することです。

これを行うには、ネットワークを2つのバランスの取れた（つまり、同じサイズの)コンポーネントに分割すると同時に、これら2つのコンポーネントを接続する道路の数を最小限に抑えることから始めます。これにより、各コンポーネントの道路に対するビーコンの比率が効果的に小さくなります。次に、アルゴリズムは、すべてのコンポーネントが内部の道路の数に関して目的のサイズに達するまで、ネットワークを一度に2つに分割し続けます。これにより、有用なマルチコンポーネントパーティションが生成されます。

ここには注意すべきバランスがあります。サイズが小さすぎると、ビーコンが多くなりすぎます。一方、サイズを大きくするには、長距離経路探索時のみ有用です。したがって、サイズは入力パラメーターとして残され、実験によって決定され、アルゴリズムが完成します。

METIS(一般的なネットワーク用)、PUNCHと慣性フロー(どちらも道路ネットワークのようなものに最適化されています)など、多数の分割手法があります。

私たちのソリューションは慣性フローアルゴリズム(inertial-flow algorithm)に基づいており、都市の中と同じように大陸全体を対象にしてもで効率的に実行できるように拡張されています。

道路網をバランスを取ってパーティショニング

前述のように、グラフとして表される道路網を2つのバランスの取れた部品に分割するにはどのようにすれば良いでしょうか？

最初のステップは、緊密に接続されたノード同士をグループ化してグラフを小さくすることです。これにより、次の双方向パーティショニングフェーズを高速化できます。これはランダムウォークが役立つところです。

ランダムウォークは、多くの有用な理論的特性を持っています。そのため、森の中の蚊の動きから熱拡散まで、さまざまなトピックを研究するために使用されてきました。

今回のアプリケーションに最も関連するのはランダムウォークが「内部では十分に接続されているが外部では不十分に接続されている領域で「閉じ込められる」」傾向があることです。

スタテンアイランドの街路を一定のステップ数でランダムウォークすることを検討してください。島を出る道路は比較的少ないため、ほとんどのステップは島の内部で発生し、島の外に出る可能性は低くなります。

ランダムウォークのイラスト
青いグラフがスタテンアイランドに対応する架空の道路網であるとします。50回のランダムウォークが実行され、すべて中間点から開始されます。各ランダムウォークは、10ステップ、または島から出るまで続きます。各ノードの数字は、ランダムウォークが訪れた回数を表しています。最終的に、島内のノードは、外部のノードよりもはるかに頻繁にアクセスされます。

緊密に接続されたノード群(上記の例のスタテンアイランドなど)を見付けてグループ化した後、アルゴリズムは各グループを新しい単一ノードとみなして地図を縮小します。

ノードのグループ(中央)を見つけ、各グループを単一の「スーパー」ノード(右)に合体させることにより、元のグラフ(左)のサイズを縮小します。ここでの例は、アルゴリズムの残りの部分をわかりやすく説明するために意図的にで選択したものです。

アルゴリズムの最後のステップは、このはるかに小さいグラフを2つに分割してから、この小さなグラフの分割を元の道路網のグラフの1つに調整することです。次に、慣性フローアルゴリズムを使用して、ノードに対するビーコンの比率(つまり、エッジがカットされる比率)を最小化するような切断面を見つけます。

元のアルゴリズムはさまざまな方向から評価をします。各方向について、ノードの最初と最後の10%の間でカットされるエッジ(ビーコンなど)の数を最小化する分割を見つけます。

小さなグラフでカットを見つけたら、アルゴリズムは精練ステップを実行して、カットを道路網の元のグラフに投影します。

結論

この作品は、古典的なアルゴリズムが大規模な問題を解決するための多くの有用なツールとしてどのように用いられているかを示しています。グラフの分割を使用すると、大規模なグラフの問題を小さなサブ問題に分割して、独立して並行して解決できます。これは、この分割アルゴリズムを使用してルートを効率的に計算するGoogleマップに特に関係があります。

謝辞

Google Researchの協力者であるLisa Fawcett, Sreenivas Gollapudi, Kostas Kollias, Ravi Kumar, Andrew Tomkins, Ameya VelingkerとGoogleMapsの協力者であるPablo Beltran, Geoff Hulten, Steve Jackson, Du Nguyenに感謝します。