ある地点から別の地点へのルーティングは、たとえそれらがナビゲーターとして使用されていなくても、電子地図にとって必須になっています。 この記事では、MAPS.MEプロジェクトでのルーティングの作成のストーリー、つまり、どの段階を経たのか、この間に学んだことを説明します。
ルーティングMAPS.MEの履歴
最初の試み
ルーティングは元々、すでに完成したアプリケーションへの追加機能として開発されました。 ルートの開発が開始された時点で、マップは既に発行されており、最初のユーザーが旅行でアプリを持ち歩いていました。 プロジェクトチームは、OSMデータの描画、保存、処理の経験を積みました。 そのため、主題領域を調査した後、チームは地図を描くためのデータに古典的なアルゴリズムを実装しました。 最初の試みでは、 ダイクストラのアルゴリズムが選択されました。 これは、非負のrib骨がある道路グラフで最短ルートを見つけることができる有名なアルゴリズムです。 ただし、最初のテストでは、開発コンピューターでもアルゴリズムの動作が遅いことが既に示されています。 電話に転送することに疑問はありませんでした。 ルート検索を高速化するために、ダイクストラのアルゴリズムはA *アルゴリズムに置き換えられました 。 プログラムはかなり速く動作し始めましたが、それでも遅すぎます。
それでも、実装されたアルゴリズムの経験により、遭遇した主な問題を定式化することができました。
- リソース制限。 私たちは携帯電話でルーティングを実行しているため、高速のプロセッサ、大量のRAM、ディスクからの高速読み取りに依存することはできません。
- OSMのグラフィックの性質。 道路グラフはありませんが、描画用に作成されたマップがあります。 また、車線、コーナリング制限、制限速度、およびその他の道路標識は地図上に描かれていないため、道路よりもはるかに悪く埋められています。
- 交通ルール。 これらは、画面に描かれたフラットグラフと比較して、道路グラフを非常に複雑にします。 このプログラムでは、追加の制限を考慮する必要があります：ターンの禁止、マルチレベルの交換、その場で方向転換できないこと。
実用的なソリューション
書籍や科学記事を期待して、モバイルデバイスのルーティングパフォーマンスの問題を解決するアルゴリズムを探し始めました。 そしてこの時点で、 収縮階層アルゴリズムが見つかりました（以降、単にCHと呼びます）。 ダイクストラの古典的なアルゴリズムと比較して、CHは信じられないほどのパフォーマンスの向上を提供しますが、特別に作成された道路グラフが必要です。 このアルゴリズムは、グラフのエッジの事前計算に基づいており、ルート構築を高速化します。 CHについては、別の記事で詳しく説明する予定です。
アルゴリズムを選択した後、描画に適したデータとルーティングに適したデータは同じものではないという事実に直面しました。 さらに、OSMの機能により、適切な道路グラフを取得することは非常に困難であるため、オープンソースプロジェクトOSRM （オープンソースルーティングマシン）を使用することにしました。 データ準備の段階でのOSRMは、OSMマップを処理し、ルートをプロットできる道路グラフを作成します。 したがって、車、自転車、歩行者、およびその他のルーティングの道路グラフを取得できます。 ただし、OSRMには1つの重大な欠点があります。サーバーで使用するために設計されており、その大きな中間ファイルで使用されるすべての情報を保存します。 ただし、これらのファイルの情報のほとんどは、すでに電話でマップファイルに保存されており、重複を避けるために、それらを再パックする必要があります。 さらに、OSRM自体はマルチスレッドhttpデーモンであり、モバイルデバイスでの実行を目的としていません。
しかし、よく考えられたアーキテクチャにより、OSRMにはCHアルゴリズムを個別に使用し、シンプルなインターフェイスを介して再パッケージ化されたデータを提供する機能があります。 そのため、MAPS.MEはOSRMバックログを使用して、ルートを取得するためにダウンロードする必要がある最初のルーティングファイルと.routingファイルを取得しました。
国際線
電話にダウンロードして保存するデータの量を減らすために、世界地図を別々の領域にカットしました。 さらに、地形のマッピングが適切であればあるほど、道路のグラフが占める面積が大きくなり、マップをカットする必要がある部分が少なくなります。 その結果、たとえば、ドイツの地図は州に分割されました。 CHアルゴリズムは、そのような各エリア内にルートを描画します。 複数のマップ間にルートを敷設する可能性は、OSMに新しく追加されるたびに増加し、マップ間のルーティングを開発するときが来ました。 複数のカードにルーティングするソリューションを選択する際、大量の追加データを必要としないものを選択しました。 その結果、そのようなアーキテクチャが得られました。各マップのグラフには、入力と出力であるN本の道路があります。 それらの間の距離を計算して、マップ間のルートの検索を高速化することもできます。 その結果、マップファイル間の移動オーバーグラフが発生します。 このような旅では、すべての世界地図のファイルは必要ありませんが、隣接するものだけで十分です。 さらに、これらのファイルの異なるバージョンを持つことができます。 一方のカードが更新されても、もう一方のカードが更新されない場合、プログラムは引き続き方向を取得します。 春に、このバージョンのルート計画をリリースしました。
ハイキングコース
しかし、あなたはいつももっと欲しい！ そして、新しいタイプのルーティングを追加したいと考えました。 歩くことから始めました。 歩行者の経路がどのようになるかを決定したら、施設から次の手順に進みました。
- 歩行者のナビゲーションは、車のグラフに匹敵する追加のスペースを占有するべきではありませんが、既存のデータを最大限に活用する必要があります。
- 歩行者は、自動車ルートが必要とする距離を必要としません。
- 歩行者グラフは、論理的には簡単です。禁止された操作や一方通行の道路はありません。
その結果、A *アルゴリズムの古い実装を開始した場所に戻り、道路データのグラフィック表示で機能することにしました。 そして、ハッカソンウィーク中に、4人のチームがこの問題に専念しました。 その結果、新しいMAPS.MEアップデートで提示された歩行者ルーティングアルゴリズムを作成することができました。 さらに、双方向のA *アルゴリズムを最適化およびデバッグしたことで、カード間のルーティングで使用できるようになり、長距離ルートの構築が加速されました。
オプション1.単純な単方向ダイクストラアルゴリズム。 ドットは、ルートを検索するときに表示されるリブの10個ごとに表示されます。
オプション2.双方向アルゴリズムA *。 ドットは、ルートを検索するときに表示されるリブの10個ごとに表示されます。
歩行者ナビゲーションがほぼ完了し、まもなくスマートフォンで表示できるようになります。
結論
アプリケーションのルーティング開発の歴史は、何を教えてくれましたか？ 最初に注意したいのは、コードを投げないことです 。 以前のバージョンのルーティングアルゴリズムがgitaに含まれていたことは非常に役立ちました。 リポジトリが移動したとき、彼らは生き残りました。それはかつてエネルギーを浪費しました。 それらは歴史上行き詰まり、masterブランチに遅れをとっていましたが、すぐに復元され、既存のインターフェイスに適応し、問題の解決に使用されました。 関連資料を検索して読む。 最新のルーティングアルゴリズムははるかに進歩しており、作業の最適化に関する学術研究が毎月発行されています。 CHレベルアルゴリズムの再発明は非常に困難です。 可能な場合は外部ライブラリを使用し 、その品質に自信があります。 OSRMを使用すると、OSMカードを最初から解析することなく、複雑なCHアルゴリズムの既にデバッグされたコードを使用できません。
参照資料
興味のある方のために、最新のルーティングアルゴリズムの理解に役立つ興味深い作品をいくつか紹介します。
- 輸送ネットワークにおける経路計画MSR-TR-2014-4 最新のルーティングアルゴリズムのMSによる比較レビュー。
- 道路ネットワークのルート計画。 ドミニク・シュルテス 。 ルーティングアルゴリズムに関する論文。 最新のアルゴリズムの原理の詳細な説明
- 収縮階層：道路ネットワークにおけるより高速で単純な階層ルーティング。 ロバートガイスバーガー 。 完全に収縮階層アルゴリズム専用の卒業作品。
