(57)【要約】本発明はナビゲーションシステムのルート計画の方法を開示し、前記方法は、実際の地理的空間に対して格子化処理を行い、前記格子はセルラーネットワークのセルであり、移動局のセル切り替え記録を取得し、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立することと、実際の地理的空間における出発地と目的地を、格子化処理された出発格子と目的格子にそれぞれ対応させ、前記隣接関係モデルに基づいて、出発格子から目的格子までの格子レベル径路を決定することと、前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換することと、を含む。同時に、本発明の実施形態はナビゲーションシステムのルート計画の装置を開示する。【選択図】図１
2017524902.tif 000002
【特許請求の範囲】
【請求項１】
ナビゲーションシステムのルート計画の方法であって、
実際の地理的空間に対して格子化処理を行い、前記格子はセルラーネットワークのセルであり、移動局のセル切り替え記録を取得し、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立することと、
実際の地理的空間における出発地と目的地を、格子化処理された出発格子と目的格子にそれぞれ対応させ、前記隣接関係モデルに基づいて、出発格子から目的格子までの格子レベル径路を決定することと、
前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換することと、を含む、方法。
【請求項２】
前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立する前に、前記方法は、
予め設定された選別案により、前記移動局のセル切り替え記録に対して選別を行うことを更に含む
請求項１に記載の方法。
【請求項３】
前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立することは、
前記移動局のセル切り替え記録に基づいて、移動局の移動軌跡を抽出することと、
一定時間内の全ての前記移動軌跡の集合をスナップショットとすることと、
スナップショットに基づいて、前記一定時間内のセルの隣接関係モデルを確立することと、を含む
請求項１に記載の方法。
【請求項４】
前記スナップショットに基づいて、前記一定時間内のセルの隣接関係モデルを確立することは、
前記スナップショットに基づいて、全てのセル基地局を頂点にして、セル間の隣接関係をエッジにして、セル間の隣接値をエッジのウェイトにするウェイト付き有向グラフを確立することを含み、
セル間の隣接値は、２つのセルの間に移動する確率であり、又は、２つのセルの間に移動する時間である
請求項３に記載の方法。
【請求項５】
前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換することは、
前記格子レベル径路を地理情報システム（ＧＩＳ）地図における出発地から目的地までの実際ルートに変換し、及び／又は前記格子レベル径路を衛星地図における出発地から目的地までの実際ルートに変換することを含む
請求項１に記載の方法。
【請求項６】
ナビゲーションシステムのルート計画の装置であって、格子モデル確立モジュールと、格子径路探索モジュールと、径路変換モジュールと、を備え、
格子モデル確立モジュールは、実際の地理的空間に対して格子化処理を行い、前記格子はセルラーネットワークのセルであり、移動局のセル切り替え記録を取得し、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立するように構成され、
格子径路探索モジュールは、実際の地理的空間における出発地と目的地を、格子化処理された出発格子と目的格子にそれぞれ対応させ、前記隣接関係モデルに基づいて、出発格子から目的格子までの格子レベル径路を決定するように構成され、
径路変換モジュールは、前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換するように構成される、装置。
【請求項７】
前記格子モデル確立モジュールは、予め設定された選別案により、前記移動局のセル切り替え記録に対して選別を行うように構成される
請求項６に記載の装置。
【請求項８】
前記格子モデル確立モジュールは、
前記移動局のセル切り替え記録に基づいて、移動局の移動軌跡を抽出するための軌跡抽出サブモジュールと、
一定時間内の全ての前記移動軌跡の集合をスナップショットとするためのスナップショット管理サブモジュールと、
スナップショットに基づいて、前記一定時間内のセルの隣接関係モデルを確立するための確立サブモジュールと、を備える
請求項６に記載の装置。
【請求項９】
前記確立サブモジュールは、
前記スナップショットに基づいて、全てのセル基地局を頂点にして、セル間の隣接関係をエッジにして、セル間の隣接値をエッジのウェイトにするウェイト付き有向グラフを確立するように更に構成され、
セル間の隣接値は、２つのセルの間に移動する確率であり、又は、２つのセルの間に移動する時間である
請求項８に記載の装置。
【請求項１０】
前記径路変換モジュールは、
前記格子レベル径路をＧＩＳ地図における出発地から目的地までの実際ルートに変換するためのＧＩＳ地図マッチングサブモジュール、及び／又は
前記格子レベル径路を衛星地図における出発地から目的地までの実際ルートに変換するための衛星地図マッチングサブモジュールを含む
請求項６に記載の装置。
【請求項１１】
コンピューター記憶媒体であって、
請求項１乃至５のいずれか１項に記載の方法を実行するためのコンピューター実行可能な命令が記憶されている、コンピューター記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はインテリジェント交通、車ネットワーク、位置情報サービス（ＬＢＳ）及び移動通信にまたがる分野に関し、特にナビゲーションシステムのルート計画の方法、装置とコンピューター記憶媒体に関する。
【背景技術】
【０００２】
車ネットワークと移動通信技術の発展に伴い、都市の管理する需要が日々増加し、ナビゲーション技術も発展している。初期のルート計画の方法は主に静的地理情報システム（Ｇｅｏｇｒａｐｈｉｃ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍ：ＧＩＳ）地図に基づいて、動的計画などの方法を使用してルートを計算し、地図への依存度が高い。地図の測量、製図、及び公開は一定周期を必要とするので、地図の情報が常に実際の状況より遅延され、それに、実際の交通状況がいろいろな突発事件によって影響を受けるので、ナビゲーションルートの正確性及び有効性に影響を与える。ＧＩＳ地図と実際の道路状況を組み合わせすることは徐々にナビゲーション技術の発展方向になっている。
【０００３】
現在、道路状況のデータが下記のような２つのデータから取得される。１つは無料の交通情報チャネル（Ｔｒａｆｆｉｃ  Ｍｅｓｓａｇｅ  Ｃｈａｎｎｅｌ：ＴＭＣ）の道路状況データであり、もう１つは商業用の道路状況データである。ここで、ＴＭＣ道路状況データが交通管理部から発表されて、リアルタイムデータが主に道路のモニタリング、警察の出動記録から取得され、リアルタイム性がよいが、ある区域にＴＭＣシステムが設定されないので、カバーの領域と情報量は限りがある。商業用の道路状況データは主にフローティングカーデータ（Ｆｌｏａｔ  Ｃａｒ  Ｄａｔａ：ＦＣＤ）から取得され、一般的に、タクシー会社がタクシーに設定した装置を介して道路状況の情報を収集するが、商業、技術と歴史に制約されるので、現在、少ない都市の道路状況情報しか提供できなく、且つ時間の遅延が大きく、リアルタイム性がよくない。
【０００４】
上述したように、現在のナビゲーション技術において、道路状況のデータのカバー範囲が小さく、リアルタイム性がよくないので、厳しいナビゲーション要求を満たすことができないという問題がある。完全にＧＩＳ地図に基づいたルート計画の方法は、地図の情報に誤りがある又は更新が適時的でない場合、計算されたナビゲーションルートの正確性と有効性を保証しにくいので、所望のルートより大きな誤差がある場合があり、更に間違ったルートを提供することもある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
既存の技術問題を解決するために、本発明の実施形態はナビゲーションシステムのルート計画の方法、装置およびコンピューター記憶媒体を提供し、関連エリア内の実際の交通状況を自動的に感知して、リアルタイムにルート計画を行い、且つ運転中にリアルタイムの道路状況の変化に応じてインタラクティブのナビゲーションを正確に、有効に行う。
【課題を解決するための手段】
【０００６】
本発明の実施形態に係る技術案は下記のように実現される。
【０００７】
本発明の実施形態はナビゲーションシステムのルート計画の方法を提供し、該方法は
実際の地理的空間に対して格子化処理を行い、前記格子はセルラーネットワークのセルであり、移動局のセル切り替え記録を取得し、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立することと、
実際の地理的空間における出発地と目的地を格子化処理された出発格子と目的格子にそれぞれ対応させ、前記隣接関係モデルに基づいて、出発格子から目的格子までの格子レベル径路を決定することと、
前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換することと、を含む。
【０００８】
上述の技術案において、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立する前に、前記方法は、
予め設定された選別案により、前記移動局のセル切り替え記録に対して選別を行うことを更に含む。
【０００９】
上述の技術案において、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立することは、
前記移動局のセル切り替え記録に基づいて、移動局の移動軌跡を抽出することと、
一定時間内の全ての前記移動軌跡の集合をスナップショットとすることと、
スナップショットに基づいて、前記一定時間内のセルの隣接関係モデルを確立することと、を含む。
【００１０】
上述の技術案において、前記スナップショットに基づいて、前記一定時間内のセルの隣接関係モデルを確立することは、
前記スナップショットに基づいて、全てのセル基地局を頂点にして、セル間の隣接関係をエッジにして、セル間の隣接値をエッジのウェイトにするウェイト付き有向グラフを確立することを含み、
セル間の隣接値は、２つのセルの間に移動する確率であり、又は、２つのセルの間に移動する時間である。
【００１１】
上述の技術案において、前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換することは、
前記格子レベル径路をＧＩＳ地図における出発地から目的地までの実際ルートに変換し、及び／又は前記格子レベル径路を衛星地図における出発地から目的地までの実際ルートに変換することを含む。
【００１２】
本発明の実施形態はナビゲーションシステムのルート計画の装置を提供し、該装置は、格子モデル確立モジュールと、格子径路探索モジュールと、径路変換モジュールと、を備え、
格子モデル確立モジュールは、実際の地理的空間に対して格子化処理を行い、前記格子はセルラーネットワークのセルであり、移動局のセル切り替え記録を取得し、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立するように構成され、
格子径路探索モジュールは、実際の地理的空間における出発地と目的地を格子化処理された出発格子と目的格子にそれぞれ対応させ、前記隣接関係モデルに基づいて、出発格子から目的格子までの格子レベル径路を決定するように構成され、
径路変換モジュールは、前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換するように構成される。
【００１３】
上述の技術案において、前記格子モデル確立モジュールは、予め設定された選別案により、前記移動局のセル切り替え記録に対して選別を行うように構成される。
【００１４】
上述の技術案において、前記格子モデル確立モジュールは、
前記移動局のセル切り替え記録に基づいて、移動局の移動軌跡を抽出するための軌跡抽出サブモジュールと、
一定時間内の全ての前記移動軌跡の集合をスナップショットとするためのスナップショット管理サブモジュールと、
スナップショットに基づいて、前記一定時間内のセルの隣接関係モデルを確立するための確立サブモジュールと、を備える。
【００１５】
上述の技術案において、前記確立サブモジュールは、
前記スナップショットに基づいて、全てのセル基地局を頂点にして、セルの隣接関係をエッジにして、セル間の隣接値をエッジのウェイトにするウェイト付き有向グラフを確立するように更に構成され、
セル間の隣接値は、２つのセルの間に移動する確率であり、又は、２つのセルの間に移動する時間である。
【００１６】
上述の技術案において、前記径路変換モジュールは、
前記格子レベル径路をＧＩＳ地図における出発地から目的地までの実際ルートに変換するためのＧＩＳ地図マッチングサブモジュール、及び／又は
前記格子レベル径路を衛星地図における出発地から目的地までの実際ルートに変換するための衛星地図マッチングサブモジュールを含む。
【００１７】
本発明の実施形態はコンピューター記憶媒体を提供し、前記コンピューター記憶媒体は、前記のナビゲーションシステムのルート計画の方法を実行するためのコンピューター実行可能な命令を記憶している。
【００１８】
本発明の実施形態はナビゲーションシステムのルート計画の方法、装置及びとコンピューター記憶媒体を提供し、前記方法は、実際の地理的空間に対して格子化処理を行い、前記格子はセルラーネットワークのセルであり、移動局のセル切り替え記録を取得し、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立することと、実際の地理的空間における出発地と目的地を格子化処理された出発格子と目的格子にそれぞれ対応させ、前記隣接関係モデルに基づいて、出発格子から目的格子までの格子レベル径路を決定することと、前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換することと、を含む。本発明の実施形態を利用して、関連エリア内の実際の交通状況を自動的に感知して、リアルタイムにルートの計画を行い、且つ運転中にリアルタイムの道路状況の変化に応じてインタラクティブのナビゲーションを正確に、有効に行うことが可能である。
【図面の簡単な説明】
【００１９】
【図１】本発明実施形態によるナビゲーションシステムのルート計画の方法を実現するフローチャートである。
【図２】本発明実施形態の一つの実施形態による基地局間の移動確率有向グラフの模式図である。
【図３】本発明実施形態のもう一つの実施形態による基地局間の移動時間有向グラフの模式図である。
【図４】本発明実施形態によるナビゲーションシステムのルート計画の装置の構造模式図である。
【発明を実施するための形態】
【００２０】
本発明の実施形態と技術案を明確に説明するために、以下、図面及び実施形態を参照して本発明の技術案について詳しく説明する。明らかに、下記の実施形態は本発明の実施形態の一部であり、全部ではない。本発明の実施形態に基づき、当業者が工夫をしなくて獲得した全てのほかの実施形態は、本発明の保護範囲に含まれる。
【００２１】
図１は本発明実施形態によるナビゲーションシステムのルート計画の方法を実現するフローチャートであり、図１に示すように、該方法は、以下のステップを含む。
【００２２】
ステップ１０１：実際の地理的空間に対して格子化処理を行い、前記格子はセルラーネットワークのセルであり、移動局のセル切り替え記録を取得し、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立する。
【００２３】
具体的に、ナビゲーションシステムが実際の地理的空間に対して格子化処理を行うことは、実際の地理的空間を複数のエリアに区分し、１つのエリアを１つの格子とする。その後、各格子の間の隣接関係モデルを確立する。
【００２４】
１つの実施形態において、ナビゲーションシステムは、セルラーネットワークのセルを格子にし、実際の地理的空間に対して区分を行い、セルの隣接関係モデルを確立する。ここで、セルは基地局のアンテナがカバーする空間である。
【００２５】
セルラーネットワークにおいて、移動性管理信号は、セルラーネットワークのユーザ位置を管理する信号であり、移動性管理信号から様々な移動局の移動軌跡情報を取得することができ、基地局側で移動局のセルの位置変化を観測したことにより、移動局のセル切り替え記録が取得されることができ、更に移動局に属している移動物体が格子の間に移動する軌跡情報を取得することができる。
【００２６】
具体的に、移動通信事業者の信号収集プラットフォームは、基地局コントローラからＡｂｉｓ／Ｉｕｂインターフェースを介して移動局のセル切り替え記録を収集し、各記録が「移動局番号、セル識別子、セルへの進入タイムスタンプ」に記録され、一定時間の間隔内の全ての移動局のセル切り替え記録を、ファイルの形で特定の記憶空間に格納する。ここで、一般的に信号収集プラットフォームの処理能力に応じて一定時間の間隔の長さを１５分に設定する。特定の記憶空間は専用ファイル伝送プロトコル（ＦＴＰ）サーバにおける記憶空間であってよい。
【００２７】
それ以外、移動スマート端末と移動インターネット応用の普及に従って、特にタクシーを呼ぶソフトウェアがタクシー業界において広く普及されることと共に、移動通信事業者は、移動局のネットアクセス記録から特定の移動局、特にタクシーの移動局におけるセル切り替え記録を取得することができる。具体的に、移動通信事業者の信号収集プラットフォームはパッケージスイッチ（Ｐａｃｋａｇｅ  Ｓｗｉｔｃｈ：ＰＳ）ドメインの信号記録、例えば、ディープパッケージ解析（Ｄｅｅｐ  Ｐａｃｋａｇｅ  Ｉｎｓｐｅｃｔｉｏｎ：ＤＰＩ）によって生成された通話記録において、「移動局番号、セル識別子、セルへの進入タイムスタンプ」の形に基づいて、移動局のセル切り替え記録を抽出し、且つ一定時間の間隔内の全ての移動局のセル切り替え記録を、ファイルの形で特定の記憶空間に格納する。ここで、一般的に信号収集プラットフォームの処理能力に応じて一定時間の間隔の長さを１５分に設定する。特定の記憶空間は専用のＦＴＰサーバにおける記憶空間であってもよい。
【００２８】
本発明の実施形態において、移動通信事業者の信号収集プラットフォームは、ナビゲーションシステムが、移動局のセル切り替え記録に基づいてセル間の隣接関係モデルを確立するために、データ基礎を提供する。
【００２９】
１つの実施形態において、ナビゲーションシステムが格子を確立する、即ち上記のセル間の隣接関係モデルを確立することは、以下のステップを含む。
【００３０】
ステップＡ：移動局のセル切り替え記録を定時に取得する。
【００３１】
具体的に、ナビゲーションシステムは、移動通信事業者の信号収集プラットフォームにより専用のＦＴＰサーバに格納された移動局の切り替え記録ファイルを定時に読み取り、読み取られた移動局のセル切り替え記録ファイルから移動局のセル切り替え記録を取得する。
【００３２】
セルの隣接関係を有効に正確に確立するために、ナビゲーションシステムは、予め設定された選別案により、前記移動局のセル切り替え記録に対して選別を行うことができる。ここで、選別案は以下のとおりである。
【００３３】
選別案一：ナビゲーションシステムは移動局番号に基づいて選別することができる。
【００３４】
移動性がない移動局番号の関連記録を削除することができる。実際に応用する場合、一部の移動局は移動性がなく、例えば、ユーザ身元識別モジュールＳＩＭカードを装着する交差点カメラであって、その位置が変化しない。しかし、基地局は依然として該交差点カメラの位置情報を定時に受信し、相応に、移動通信事業者の信号収集プラットフォームも該交差点カメラの記録を収集して保存する。このような移動局に対して、その移動局番号を事前に取得して、該移動局番号の関連記録を全部削除することができる。
【００３５】
また、特定の移動局番号の関連記録だけを保存してよい。例えば、タクシーの移動局番号の関連記録だけを保存する。周知のように、タクシーの移動局は普通のユーザの移動局より移動性がよく、且つカバー範囲が広いので、タクシーの移動局番号を事前に取得して、タクシーの移動局番号に関する情報だけを保存する。
【００３６】
選別案二：ナビゲーションシステムはセル識別子に基づいて選別を行う。
【００３７】
ある場合、現在取得された移動局のセル切り替え記録が少なく、セル間の隣接関係を表すことができないので、前に取得された移動局のセル切り替え記録を参照する必要がある。例えば、昨日取得された移動局のセル切り替え記録である。しかし、今日移動通信事業者が新しい基地局を新築すれば、該新築の基地局のセル識別子の関連記録は昨日の記録と結合できないので、該セル識別子の関連記録を削除する必要がある。この場合、ナビゲーションシステムは履歴記録に基づいてメモリに元のセル識別子をロードしたから、１つの移動局のセル切り替え記録におけるセル識別子がメモリにロードされたセル識別子に存在しない場合、ナビゲーションシステムは該移動局のセル切り替え記録を削除する。
【００３８】
選別案三：ナビゲーションシステムはセルの震動により生じられた記録を無視する。
【００３９】
ある場合、移動局の位置が変化しないが、セルの切り替えを行うことはセル震動と呼ばれる。該移動局が実際に移動しないから、セル震動により生じられた移動局の切り替え記録はセル間の実際の隣接関係を表すことができないので、このような記録を無視すべきである。
【００４０】
具体的に、ナビゲーションシステムは、新しい記録Ｒを取得した後、該記録における移動局番号Ｍと同じである前回の記録Ｏをサーチし、２つの記録の時間間隔Ｔが３０分を超えるかどうかを判断する。時間間隔Ｔが３０分より小さい場合、記録Ｒにおけるセル識別子がナビゲーションシステムに格納された移動局番号Ｍが最近にキャンプした２つのセル識別子のいずれか１つに該当するかどうかを判断し、記録Ｒにおけるセル識別子がナビゲーションシステムに格納された移動局番号Ｍが最近にキャンプした２つのセル識別子のいずれか１つに該当する場合、記録Ｒがセル震動により生じられた記録と認められるので、ナビゲーションシステムは該記録Ｒを無視する。
【００４１】
実際に応用する場合、上記の選別案に対して、そのうちの１つを選択する或いは組み合わせて使用することができる。
【００４２】
ステップＢ：前記移動局のセル切り替え記録に基づいて、セルの隣接関係を確立する。
【００４３】
具体的に、ナビゲーションシステムは定時に取得された移動局のセル切り替え記録に基づいて、一定時間内の移動局の移動軌跡を抽出する。この移動軌跡に基づいてこの時間帯内のセルの隣接関係を確立する。ナビゲーションシステムに上記の選別案の１つ又は複数が予め設定された場合、ナビゲーションシステムが移動局のセル切り替え記録から移動局の軌跡を抽出する効率を高めることができる。
【００４４】
１つの実施形態において、ナビゲーションシステムは移動局のセル切り替え記録に基づいて移動局の移動軌跡を抽出する方法は、具体的に以下を含む。
【００４５】
ナビゲーションシステムにおいて、セル移動ペアを利用して移動局の移動軌跡を表してよく、セル移動ペアが「元セル識別子、目的セル識別子、キャンプ時間」に表記され、ナビゲーションシステムは、各移動局が最近にキャンプした２つのセル識別子とこの２つのセルへ進入するタイムスタンプを格納する。例えば、ナビゲーションシステムにおいて、移動局Ｍに対して格納された最近にキャンプした２つのセル識別子はＸ１とＸ２であり、Ｘ１に対応するタイムスタンプはｔｔ１であり、ここで、セル識別子Ｘ２に対応するタイムスタンプはｔｔ２であり、且つｔｔ２がｔｔ１より大きい、即ち、移動局の前回の切り替え記録は「Ｍ、Ｘ２、ｔｔ２」である。ナビゲーションシステムは移動局Ｍのセル切り替え記録Ｒを読み取り、Ｒ＝＜Ｍ、ｎ１、ｔ１＞である。
【００４６】
ナビゲーションシステムは、記録Ｒと移動局Ｍの前回の切り替え記録との間の時間間隔Ｔを計算し、即ち、Ｔ＝ｔ１−ｔｔ２である。
【００４７】
Ｔ≧３０分である場合、記録Ｒが記録した軌跡と時間間隔Ｔの前の移動軌跡が２つの独立した移動軌跡に分けられると認められるので、ナビゲーションシステムは、格納された移動局Ｍが最近にキャンプした２つのセル識別子をクリアし、即ち、セル識別子Ｘ１とセル識別子Ｘ２に対応する記録を削除し、そして記録Ｒにおけるセル識別子ｎ１とタイムスタンプｔ１を格納する。
【００４８】
Ｔ＜３０分である場合、ナビゲーションシステムは、セル移動ペア＜Ｘ２、ｎ１、ｔ１−ｔｔ２＞を移動局Ｍの１つの移動軌跡とし、且つ移動局Ｍが最近にキャンプした２つのセル識別子をＸ２とｎ１に更新し、ここで、セル識別子Ｘ２に対応するタイムスタンプはｔｔ２であり、セル識別子ｎ１に対応するタイムスタンプはｔ１である。
【００４９】
上記の方法に基づいて、移動局Ｍに関する全ての記録を処理して、移動局Ｍの全ての移動軌跡を取得することができ、更に全ての移動局の移動軌跡を取得する。
【００５０】
特に、一定時間内の全ての移動軌跡（即ちセル移動ペア）の集合をスナップショットと呼ばれ、前記一定時間が該スナップショットに対応するスナップショット時間であり、例えば、スナップショット時間が１５分であるスナップショットは１５分内に取得された全ての移動局の移動軌跡の集合を表す。ナビゲーションシステムは複数の履歴スナップショットと１つの現在スナップショットをメンテナンスすることができる。より強いナビゲーションシステムのリアルタイムの感知特性を実現し、同時に収集されたデータ量がモデル精度の要求を満たすことを保証するために、スナップショット時間を１５分から１時間まで設定することが好ましい。スナップショットがファイル又はメモリデータベースのような形で格納され、履歴スナップショットがファイルシステムに永続され、現在スナップショット及び当日の履歴スナップショットがメモリデータベースに保存される。メモリデータベースに１つのスナップショットのインデックスが含まれてよく、スナップショットのインデックスに各スナップショットの時間属性、休、祝日属性及び天気属性が記録される。ここで、時間属性は、年、四半期、月、週、日、時間帯を含む。休、祝日属性は、出勤日、週末、祝日、休日を含む。天気属性は、非劣悪天気、大雨、大雪、凍霜を含む。
【００５１】
ナビゲーションシステムは上記のスナップショットショットに基づいて、一定時間内のセル隣接関係モデルを確立してよく、下記を含む。
【００５２】
上記のスナップショットショットに基づいて、全てのセルを頂点にして、セル間の隣接関係をエッジにして、セル間の隣接値をエッジのウェイトにするウェイト付き有向グラフを確立する。ここで、セル間の隣接値は、２つのセルの間に移動する確率であり、又は、２つのセルの間に移動する時間である。
【００５３】
具体的に、案Ｉにおいて、スナップショットに＜セル１、セル２、キャンプ時間＞のようなセル移動ペア記録がある場合、セル１からセル２までの間にエッジが相互接続されることを表す。セル１からセル２への移動確率は、元セル１から目的セル２に移動する記録数を、全ての元セル１から移動した記録数で割った値である。セル１からセル２に移動する確率を、セル１からセル２までのエッジのウェイトとし、図２は１つの実施形態において、セル間の移動確率有向グラフである。
【００５４】
案ＩＩにおいて、スナップショットに＜セル１、セル２、キャンプ時間＞のようなセル移動ペア記録がある場合、セル１からセル２までの間にエッジが相互接続されることを表す。セル１からセル２までの移動時間は、全ての＜セル１、セル２、キャンプ時間＞である記録における「キャンプ時間」の平均値である。セル１からセル２に移動する時間をセル１からセル２までのエッジのウェイトとし、図３は１つの実施形態において、セル間の移動時間有向グラフである。
【００５５】
上記の案ＩＩに対して、高次のコンテキストの関連モデルを使用して改善し、例えば二次モデルであり、この場合、＜前の前の（ｓｅｃｏｎｄ  ｌａｓｔ）セルＩＤ、前のセルＩＤ、現在セルＩＤ、キャンプ時間＞ペアを抽出及び記録する必要があり、且つ二次モデルを使用してモデリングし及び解を求める。もっと高次モデルを実行するような方法を使ってよく、このように類推する。
【００５６】
現在スナップショットにおける移動軌跡の数量が少なくて、確立されたセル間の隣接関係モデルの精度が高くない場合、履歴スナップショットと現在スナップショットを使って有向グラフを構成してよいが、このような方法を採用するとき、履歴スナップショットのコンテキスト状態と現在状態が一致することを保証する必要があり、従って、履歴スナップショットを選択するとき、最近の履歴スナップショットを使用すること、及びインデックス特徴と現在時刻インデックス特徴が類似する履歴スナップショットを使用する必要がある。
【００５７】
ステップ１０２：実際の地理的空間における出発地と目的地を、空間に対して格子化処理後の出発格子と目的格子にそれぞれ対応させ、前記格子間の隣接関係モデルに基づいて、出発格子から目的格子までの格子レベル径路を決定する、
具体的に、ナビゲーションシステムはユーザから入力された出発地と目的地を受信し、位置対応関係に基づいて、出発地を出発格子に対応させ、目的地を目的格子に対応させ、ステップ１０１において確立された格子間の隣接関係モデルに基づいて、出発格子から目的格子までの格子レベル径路を決定する。
【００５８】
特に、セルラーネットワークのセルを格子とする場合、出発地と目的地の経緯度及びセルの経緯度に基づいて、出発地／目的地で最も近い基地局のセルを選び取って、出発基地局／目的セルとする。
【００５９】
１つの実施形態において、上記の案Ｉにより、セル間の移動確率有向グラフを確立する場合、出発セルから目的セルまでの最適な径路は、全ての開始ノードが出発セルノードであり、終点ノードが目的セルノードである径路において、確率が最も大きい径路である。図２に示すように、出発セル１から目的セル７までの最適な径路は、セル１−＞セル２−＞セル４−＞セル７であり、該径路の生成確率は０．７＊０．３＊０．９＝０．１８９であり、該確率はほかのいずれかの径路の確率より大きい。例えば、セル１−＞セル２−＞セル５−＞セル６−＞セル７の径路の生成確率が０．７＊０．２＊０．４＊０．１＝０．００５６である場合、移動確率有向グラフにおけるエッジのウェイトを-ｌｏｇ（元のエッジのウェイト）に変更し、対応的に、最適な径路の計算を標準的な最短径路のサーチ問題に変換して解を求めることができる。
【００６０】
１つの実施形態において、図３に示すように、上記の案ＩＩにより、セル間の移動時間有向グラフを確立する場合、出発セルから目的セルまでの最適な径路に対する解を求めることを、該有向グラフにおいて最短径路をサーチすることに変換してよい。図３に示すように、出発セル１から目的セル７までの最適な径路は、セル１−＞セル３−＞セル６−＞セル７であり、該径路の移動時間は３０＋６０＋２０＝１１０であり、該径路の移動時間はほかのいずれかの径路の移動時間より短い、例えば、セル１−＞セル２−＞セル５−＞セル７の径路の移動時間は５０＋２５＋３６＝１１１である。
【００６１】
ステップ１０３：前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換する。
【００６２】
具体的に、ナビゲーションシステムはステップ１０２に基づいて算出された格子レベル径路をＧＩＳ地図に対応させ、及び／又は衛星地図に対応させ、出発地から目的地までの実際ルートを取得する。
【００６３】
１つの実施形態において、セルラーネットワークのセルを格子とし、セルレベル径路をＧＩＳ地図に対応させて実際ルートに変換する方法は、セルレベル径路における各セルの基地局の経緯度に基づいて、該径路を二次元空間における１つのポリラインに変換し、該ポリラインに対して最小二乗法を用いて平滑化処理を行って１つの平滑化曲線を得て、５００ｍの距離で曲線に対してバッファ（Ｂｕｆｆｅｒ）処理して１つのエリアを得、ＧＩＳ地図から該エリアを貫通する又は該得エリアに含まれる全ての道路を選択し、該地図の部分集合を使って動的計画演算法に基づいて出発地から目的地までのルートを計算することを含む。
【００６４】
もう１つの実施形態において、セルラーネットワークのセルを格子とし、セルレベル径路を衛星地図に対応させ、実際ルートに変換する方法は、ユーザに衛星地図を伝送し、かつセルレベル径路を衛星地図に表示し、ユーザは、径路指示と衛星地図が表した実際の道路状況に応じて、ルートを選択することを含む。この方法を採用すれば、ユーザのためにＧＩＳ地図に表示されない道路を提供して、ＧＩＳ地図の情報が道路の実際状況より遅れている問題を解決する。一般的に、新しいつくった道路が早くても３ヶ月をかかってＧＩＳ地図に更新されるので、更にＧＩＳ地図に表示されることができない。
【００６５】
上記の実施形態により提供されたナビゲーションシステムのルート計画の方法において、二段階のルート計画の方法を採用する。まず、実際の地理的空間に対してセルラーネットワークのセルを利用して格子化を行い、次に、移動通信事業者から取得された移動局のセル切り替え記録から移動局の移動軌跡を抽出することで、複数の実際の移動局の移動軌跡情報をリアルタイムで感知することができる。セルラーネットワークのセル空間に対して径路の計画を行い、そして、ＧＩＳ地図又は衛星地図に基づいて径路のマッチングを行うことにより、ＧＩＳ地図の正確性と有効性に対して依頼することを減少し、径路の計画を行う結果のリアルタイム性、正確性、及び有効性を向上させることができる。且つ、ＧＩＳ地図のエラーを見付けることを補助することもでき、同時に、これに基づいて、地図に対してエラーを許容する範囲内に最適な径路を提供する。本発明の実施形態に記載の技術案は移動通信ネットワークに基づいたので、配置のコストが低く、適用の範囲が広い。
【００６６】
本発明の実施形態はコンピューター記憶媒体を提供し、前記コンピューター記憶媒体はコンピューター実行可能な命令を格納し、前記コンピューター実行可能な命令は前記ナビゲーションシステムのルート計画の方法を実行することに用いられる。
【００６７】
図４は本発明実施形態によるナビゲーションシステムのルート計画の装置の構造模式図であり、図４に示すように、該ルート計画の装置は、格子モデル確立モジュール４１と、格子径路探索モジュール４２と、径路変換モジュール４３と、を備える。
【００６８】
格子モデル確立モジュール４１は、実際の地理的空間に対して格子化処理を行い、前記格子はセルラーネットワークのセルであり、移動局のセル切り替え記録を取得し、前記移動局のセル切り替え記録に基づいて、セルの隣接関係モデルを確立するように構成される。
【００６９】
格子径路探索モジュール４２は、実際の地理的空間における出発地と目的地を格子化処理された出発格子と目的格子にそれぞれ対応させ、前記隣接関係モデルに基づいて、出発格子から目的格子までの格子レベル径路を決定するように構成される。
【００７０】
径路変換モジュール４３は、前記格子レベル径路を実際の地理的空間における出発地から目的地までの実際ルートに変換するように構成される。
【００７１】
ここで、上記の格子はセルラーネットワークのセルであり、対応的に、上記のルート計画の装置における格子モデル確立モジュール４１は、予め設定された選別案により、前記移動局のセル切り替え記録に対して選別を行うように構成される。
【００７２】
１つの実施形態において、前記格子モデル確立モジュール４１は、
前記移動局のセル切り替え記録に基づいて、移動局の移動軌跡を抽出するための軌跡抽出サブモジュールと、
一定時間内のすべての前記移動軌跡の集合をスナップショットとするためのスナップショット管理サブモジュールと、
スナップショットに基づいて、前記一定時間内のセルの隣接関係モデルを確立するための確立サブモジュールと、を備える。
【００７３】
前記確立サブモジュールは、
前記スナップショットに基づいて、全てのセル基地局を頂点にして、セルの隣接関係をエッジにして、セル間の隣接値をエッジのウェイトにするウェイト付き有向グラフを確立するように更に構成され、
セル間の隣接値は、２つのセルの間に移動する確率であり、又は、２つのセルの間に移動する時間である。
【００７４】
また、上記のルート計画の装置において、前記径路変換モジュール４３は、
前記格子レベル径路をＧＩＳ地図における出発地から目的地までの実際ルートに変換するためのＧＩＳ地図マッチングサブモジュール、及び／又は
前記格子レベル径路を衛星地図における出発地から目的地までの実際ルートに変換するための衛星地図マッチングサブモジュールを含む。
【００７５】
実際の応用において、上記の各モジュール及び各ユニットはいずれもナビゲーションシステムにおける中央処理装置（ＣＰＵ）、マイクロプロセッサー（ＭＰＵ）、デジタル信号処理装置（ＤＳＰ）、又はフィールドプログラマブルゲートアレイ（ＦＰＧＲ）により実現される。
【００７６】
図４に示すような装置の原理は方法と相似であるので、本発明の実施形態で提供されるナビゲーションシステムのルート計画の装置の実行過程及び実行原理は、前述の方法の実行過程及び実行原理を参照することができ、ここでは詳細な説明を省略する。
【００７７】
本分野の当業者であれば、本発明の実施形態が方法、システム、或いはコンピュータプログラム製品として提供されることができると理解すべきである。従って、本発明は、ハードウェア実施形態、ソフトウェア実施形態、或いはソフトウェア実施形態とハードウェア実施形態を組み合わせた形態を使用することができる。しかも、本発明はコンピュータ使用可能プログラムコードを含む１つ以上のコンピュータで使用可能な記憶媒体（磁気ディスク記憶装置と光メモリなどを含むがこれらに限られない）により実施されるコンピュータプログラム製品の形態を使用することができる。
【００７８】
本発明は、本発明の実施形態による方法、装置（システム）、及びコンピュータプログラム製品のフローチャート及び／又はブロック図を参照して説明される。コンピュータプログラム命令によってフローチャートの各プロセスおよび／ブロック、およびフローチャートおよび／ブロックのプロセスおよび／またはブロックの組み合わせを実現することができると理解すべきである。これらのコンピュータプログラム命令を汎用コンピュータ、専用コンピュータ、組み込みプロセッサまたは他のプログラム可能データ処理装置のプロセッサに与えて１つのマシンを生成することができ、それによってコンピュータまたは他のプログラム可能データ処理装置のプロセッサで実行された命令によりフローチャートの１つのプロセスまたは複数のプロセスおよび／ブロック図における指定された機能を実現するための装置を生成する。
【００７９】
これらのコンピュータプログラム命令がコンピュータまたは他のプログラム可能データ処理装置が特定のモードで動作することをガイドすることができるコンピュータ可読メモリに記憶されることもでき、それによって、当該コンピュータ可読メモリに記憶された命令により命令装置が含まれる製造品を生成し、当該命令装置がフローチャートの１つ以上のプロセスおよび／またはブロック図の１つ以上のブロックにおける指定された機能を実現する。
【００８０】
これらのコンピュータプログラム命令がコンピュータまたは他のプログラム可能データ処理装置にロードされることができ、それによってコンピュータまたは他のプログラム可能データ処理装置で実行された命令によりフローチャートの１つ以上のプロセスおよび／またはブロック図の１つ以上のブロックにおける指定された機能を実現するためのステップを提供する。
【００８１】
以上は、本発明の最適的な実施例に過ぎなく、本発明の保護範囲を限定することに用いられるものではない。
【産業上の利用可能性】
【００８２】
本発明の実施形態により提供されるナビゲーションシステムのルート計画の方法、装置及び記憶媒体において、二段階のルート計画の方法を採用し、まず、実際の地理的空間に対してセルラーネットワークのセルを利用して格子化を行い、次に、移動通信事業者から取得された移動局のセル切り替え記録から移動局の移動軌跡を抽出することで、複数の実際の移動局の移動軌跡情報をリアルタイムで感知することができる。セルラーネットワークのセル空間に対して径路の計画を行い、そして、ＧＩＳ地図又は衛星地図に基づいて径路のマッチングを行うことにより、ＧＩＳ地図の正確性と有効性に対して依頼することを減少し、径路の計画を行う結果のリアルタイム性、正確性、及び有効性を向上させることができる。且つ、ＧＩＳ地図のエラーを見付けることを補助することもでき、同時に、これに基づいて、地図に対してエラーを許容する範囲内に最適な径路を提供する。本発明の実施形態に記載の技術案は移動通信ネットワークに基づいたので、配置のコストが低く、適用の範囲が広い。
【図１】
2017524902.tif 000003
【図２】
2017524902.tif 000004
【図３】
2017524902.tif 000005
【図４】
2017524902.tif 000006
【国際調査報告】
2017524902.tif 000007
2017524902.tif 000008
2017524902.tif 000009
2017524902.tif 000010