(57)【特許請求の範囲】
【請求項１】
検索予定ルート取得モジュールが、検索起点と検索終点とを含む検索しようとするルートを取得するステップと、
第１選択モジュールが、既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとするステップと、
第２選択モジュールが、既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとするステップと、
利用可能ルート共通部分モジュールが、前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを候補ルートとするステップと、
第１選別モジュールが、迂回距離に基づいて前記候補ルートを選別するステップと、を含み、
前記第１選別モジュールが、迂回距離に基づいて前記候補ルートを選別するステップは、
ルート計画サブモジュールが、前記候補ルートの最初の起点と最初の終点、及び前記検索起点と前記検索終点に基づいて、ルートを新たに計画するステップと、を備え、
ここで、前記迂回距離は、再計画ルートのルート距離と前記候補ルートの最初のルート距離との距離差の値であり、
既存のルートのデータベースは逆索引データベースであり、ここで、各既存のルートの記録は前記逆索引データベースに記憶されるとともに、記録のうちの少なくとも１つの属性項の数値の順序に基づいて順序付けられ、前記属性項は少なくとも起点ハッシュコードと終点ハッシュコードとを含み、
マップはグリッドの形で区分され、前記ハッシュコードは各グリッドに対応付けられるとともに、ハッシュリンクリストの形で記憶され、隣接するグリッドのハッシュコードはハッシュリンクリストにおいて互いに関連付けられ、
このようにして、前記第１選択モジュールが、既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとするステップにおいては、
前記検索起点のハッシュコードを決定し、前記検索起点のハッシュコードに対して既存のルートのデータベースにおいてマッチングを行うステップと、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、起点範囲のグリッドとするステップと、
前記起点範囲のグリッドを経由する既存のルートを起点利用可能なルートとするステップと、を含み、
前記第２選択モジュールが、既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとするステップにおいては、
前記検索終点のハッシュコードを決定し、前記検索終点のハッシュコードに対して既存のルートのデータベースにおいてマッチングを行うステップと、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、終点範囲のグリッドとするステップと、
前記終点範囲のグリッドを経由する既存のルートを終点利用可能なルートとするステップと、を含む
ことを特徴とする走行ルートマッチング方法。
【請求項２】
前記第１選別モジュールが、迂回距離に基づいて前記候補ルートを選別するステップは、
迂回距離計算サブモジュールが、再計画ルートの迂回距離を計算するステップと、
ルート決定サブモジュールが、前記迂回距離が所定閾値範囲内にある前記再計画ルートを、選別して得られたルートとするステップと、をさらに含む
ことを特徴とする請求項１に記載の走行ルートマッチング方法。
【請求項３】
迂回距離に基づいて前記候補ルートを選別した後に、前記方法は、
第２選別モジュールが、車両所有者の運転歴または車両モデルを含むユーザのルート補助デマンドに基づいて、候補ルートを選別するステップ、をさらに含む
ことを特徴とする請求項１または請求項２に記載の走行ルートマッチング方法。
【請求項４】
迂回距離に基づいて前記候補ルートを選別した後に、前記方法は、
順序付けモジュールが、既存のルートに対応する車両所有者の発車時間に基づいて、選別したルートを順序付けるステップ、をさらに含む
ことを特徴とする請求項１または請求項２に記載の走行ルートマッチング方法。
【請求項５】
検索起点と検索終点を含む検索しようとするルートを取得するための検索予定ルート取得モジュールと、
既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとする第１選択モジュールと、
既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとする第２選択モジュールと、
前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを候補ルートとする利用可能ルート共通部分モジュールと、
迂回距離に基づいて前記候補ルートを選別する第１選別モジュールと、を備え、
前記第１選別モジュールは、前記候補ルートの最初の起点と最初の終点、及び前記検索起点と前記検索終点に基づいて、ルートを新たに計画するルート計画サブモジュールと、を備え、
ここで、前記迂回距離は、再計画ルートのルート距離と前記候補ルートの最初のルート距離との距離差の値であり、
既存のルートのデータベースは逆索引データベースであり、ここで、各既存のルートの記録は前記逆索引データベースに記憶されるとともに、記録のうちの少なくとも１つの属性項の数値の順序に基づいて順序付けられ、前記属性項は少なくとも起点ハッシュコードと終点ハッシュコードとを含み、
マップはグリッドの形で区分され、前記ハッシュコードは各グリッドに対応付けられるとともに、ハッシュリンクリストの形で記憶され、隣接するグリッドのハッシュコードはハッシュリンクリストにおいて互いに関連付けられ、
このようにして、前記第１選択モジュールは、具体的に、
前記検索起点のハッシュコードを決定し、前記検索起点のハッシュコードを既存のルートのデータベースにおいてマッチングを行い、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、起点範囲のグリッドとし、
前記起点範囲のグリッドを経由する既存のルートを起点利用可能なルートとすることに用いられており、
前記第２選択モジュールは、具体的に、
前記検索終点のハッシュコードを決定し、前記検索終点のハッシュコードを既存のルートのデータベースにおいてマッチングを行い、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、終点範囲のグリッドとし、
前記終点範囲のグリッドを経由する既存のルートを終点利用可能なルートとすることに用いられる
ことを特徴とする走行ルートマッチング装置。
【請求項６】
前記第１選別モジュールは、
再計画ルートの迂回距離を計算する迂回距離計算サブモジュールと、
前記迂回距離が所定閾値範囲内にある前記再計画ルートを、選別して得られたルートとするルート決定サブモジュールと、をさらに備える
ことを特徴とする請求項５に記載の走行ルートマッチング装置。
【請求項７】
迂回距離に基づいて前記候補ルートを選別した後に、車両所有者の運転歴または車両モデルを含むユーザのルート補助デマンドに基づいて、候補ルートを選別する第２選別モジュールをさらに備える
ことを特徴とする請求項５または請求項６に記載の走行ルートマッチング装置。
【請求項８】
迂回距離に基づいて前記候補ルートを選別した後に、既存のルートに対応する車両所有者の発車時間に基づいて、選別したルートを順序付ける順序付けモジュールをさらに備える
ことを特徴とする請求項５または請求項６に記載の走行ルートマッチング装置。
【請求項９】
１つ以上のコンピュータ実行可能な命令を含む記録媒体であって、前記コンピュータ実行可能な命令は、コンピュータのプロセッサにより実行される時に、走行ルートマッチング方法を実行することに用いられており、前記方法は、
検索起点と検索終点とを含む検索しようとするルートを取得するステップと、
既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとするステップと、
既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとするステップと、
前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを候補ルートとするステップと、
迂回距離に基づいて前記候補ルートを選別するステップと、を含み、
前記迂回距離に基づいて前記候補ルートを選別するステップは、
前記候補ルートの最初の起点と最初の終点、及び前記検索起点と前記検索終点に基づいて、ルートを新たに計画するステップ、を備え、
ここで、前記迂回距離は、再計画ルートのルート距離と前記候補ルートの最初のルート距離との距離差の値であり、
既存のルートのデータベースは逆索引データベースであり、ここで、各既存のルートの記録は前記逆索引データベースに記憶されるとともに、記録のうちの少なくとも１つの属性項の数値の順序に基づいて順序付けられ、前記属性項は少なくとも起点ハッシュコードと終点ハッシュコードとを含み、
マップはグリッドの形で区分され、前記ハッシュコードは各グリッドに対応付けられるとともに、ハッシュリンクリストの形で記憶され、隣接するグリッドのハッシュコードはハッシュリンクリストにおいて互いに関連付けられ、
このようにして、前記第１選択モジュールが、既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとするステップは、
前記検索起点のハッシュコードを決定し、前記検索起点のハッシュコードに対して既存のルートのデータベースにおいてマッチングを行うステップと、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、起点範囲のグリッドとするステップと、
前記起点範囲のグリッドを経由する既存のルートを起点利用可能なルートとするステップと、を含み、
前記第２選択モジュールが、既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとするステップは、
前記検索終点のハッシュコードを決定し、前記検索終点のハッシュコードに対して既存のルートのデータベースにおいてマッチングを行うステップと、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、終点範囲のグリッドとするステップと、
前記終点範囲のグリッドを経由する既存のルートを終点利用可能なルートとするステップと、を含む
ことを特徴とする記録媒体。
【発明の詳細な説明】
【優先権主張】
【０００１】
本願は、出願日が２０１５年０６月３０日に提出された、出願番号が２０１５１０３７７０１９．２で、申請人が百度在線網絡技術（北京）有限公司で、発明の名称が「走行ルートマッチング方法、装置及び記録媒体」である中国特許出願に基づく優先権を主張し、当該特許出願の全文を引用により本願に組み込む。
【技術分野】
【０００２】
本発明の実施例は、ロケーションに基づくサービス技術分野に関し、特に走行ルートマッチング方法、装置及び記録媒体に関する。
【背景技術】
【０００３】
乗合のコンセプトが中国に入ったところに、インターネットは既に国内に着実に発展してきたので、大部分の人はその最初に乗合のウェブサイトにより、同乗者を探すことができる。インターネットの発展に伴い、中国国内に多様な乗合文化が次第に形成され、より多くの乗合は乗合のウェブサイトに依存する。現在北京、上海、広州など大都会のサラリーマンは乗合ウェブサイトにより同乗者を探して乗り合うことが好きである。
【０００４】
乗合のプロセスにおいて、乗合利用者は自分の路線ニーズに応じて、自分に適する車両所有者を探す。従って、ある走行ルートのマッチング問題が存在する。既存の乗合プラットフォームの走行ルートマッチング問題を解決する方法は、迂回距離を計算し、当該迂回距離に基づいて車両所有者のルートをマッチングすることである。この方法の欠点は、マッチングを行う度にデータベースにおける全部の車両所有者のルートをトラバースする必要があり、マッチング効率は極めて低いことである。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の実施例は、走行ルートマッチング方法、装置及び記録媒体を提供して、走行ルートマッチングの計算効率を向上させる。
【課題を解決するための手段】
【０００６】
第１態様において、本発明の実施例は走行ルートマッチング方法を提供し、この方法は、
検索起点と検索終点とを含む検索しようとするルートを取得するステップと、
既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとするステップと、
既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとするステップと、
前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを候補ルートとするステップと、
迂回距離に基づいて前記候補ルートを選別するステップと、を含む。
【０００７】
第２態様において、本発明の実施例は走行ルートマッチング装置をさらに提供し、この装置は、
検索起点と検索終点を含む検索しようとするルートを取得するための検索予定ルート取得モジュールと、
既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとする第１選択モジュールと、
既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとする第２選択モジュールと、
前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを候補ルートとする利用可能ルート共通部分モジュールと、
迂回距離に基づいて前記候補ルートを選別する第１選別モジュールと、を備える。
【０００８】
第３態様において、本発明の実施例はコンピュータ実行可能な命令を含む１つ以上の記録媒体をさらに提供し、前記コンピュータ実行可能な命令は、コンピュータのプロセッサにより実行される時に、走行ルートマッチング方法を実行することに用いられており、前記方法は、
検索起点と検索終点とを含む検索しようとするルートを取得するステップと、
既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとするステップと、
既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとするステップと、
前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを候補ルートとするステップと、
迂回距離に基づいて前記候補ルートを選別するステップと、を含む。
【０００９】
本発明の実施例が提供した走行ルートマッチング方法、装置及び記録媒体は、既存のルートのデータベースから検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとし、前記既存のルートのデータベースから検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとし、前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを、求めた候補ルートとし、迂回距離に基づいて前記候補ルートを選別することにより、走行ルートマッチングの効率を大きく向上させることを実現できる。
【図面の簡単な説明】
【００１０】
以下、本発明に係る実施例をより詳しく説明するために、実施例に用いられる図面を簡単に説明し、勿論、以下の図面は本発明に係る一部の実施形態に過ぎず、当業者にとって、創造的労働をすることなく、これらの図面に対する修正や置き換えは可能である。
【００１１】
【図１】本発明の実施例１に係る走行ルートマッチング方法のフローチャートである。
【図２】本発明の実施例１に係る走行ルートマッチング方法において選別のフローチャートである。
【図３】本発明の実施例２に係る走行ルートマッチング方法のフローチャートである。
【図４】本発明の実施例２に係る走行ルートマッチング方法の概略図である。
【図５】本発明の実施例３に係る走行ルートマッチング装置の構成概略図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照しながら本発明に係る実施例をより明確、かつ完全的に説明する。勿論、後述する実施例は本発明に係る実施形態一部であり、全部の実施例ではなく、本発明の原理を説明するためのものに過ぎず、本発明を制限するものではない。本発明の実施例に基づいて、当業者が創造的な労働をすることなく取得するほかの実施例はいずれも本発明の保護範囲に属する。
【００１３】
実施例１
図１は本発明の実施例１に係る走行ルートマッチング方法を示すフローチャートである。当該方法は、走行ルートをマッチングすることに適用される。当該方法は、走行ルートマッチング装置により実行されてもよく、前記装置は、ソフトウェア及び／またはハードウエアにより実現されてもよく、図１に示すように、本実施例に係る走行ルートマッチング方法における操作は以下のステップを含む。
【００１４】
Ｓ１１０：検索起点と検索終点とを含む検索しようとするルートを取得する。
【００１５】
前述操作は、具体的に、サーバが前記検索しようとするルートの主な情報を取得し、即ち、検索起点と検索終点とを取得する。具体的に、検索起点と検索終点は、それぞれ乗り合う車両をサーチするユーザの入力する乗車の起点ロケーションと目的地ロケーションであってもよい。
【００１６】
Ｓ１２０：既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとする。
【００１７】
本実施例に係る前記グリッドは、ＧｅｏＨａｓｈ（ジオハッシュ）アルゴリズムを用いて、マップをグリッド形で区分することにより形成された矩形格子である。前記ハッシュコードは各グリッドに対応し、ハッシュリンクリストの形で記憶され、隣接するグリッドのハッシュコードはハッシュリンクリストにおいて互いに関連付けられる。
【００１８】
このようにして、上記操作は、具体的に、
サーバが、取得した検索起点に基づいて前記検索起点が位置するグリッドのハッシュコードを決定し、前記検索起点のハッシュコードに対して既存のルートのデータベースにおいてマッチングを行うステップと、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、起点範囲のグリッドとするステップと、
前記起点範囲のグリッドを経由する既存のルートを起点利用可能なルートとするステップと、を含み、
ここで、前記検索起点のハッシュコードに対して既存のルートのデータベースにおいてマッチングを行う時に、検索起点のハッシュコードが既存のルートのデータベースにおけるハッシュコードと同一または対応するハッシュコードであればマッチングが成功し、対応するハッシュコードとは、検索起点のハッシュコードのプレフィックスと同じプレフィックスを有するハッシュコードであってもよい。
【００１９】
隣接するグリッドのハッシュコードはハッシュリンクリストにおいて互いに関連付けられるので、ハッシュリンクリストから所定数量の関連付けられるハッシュコードを取得することができ、その対応するグリッドは隣接するグリッドである。
【００２０】
Ｓ１３０：既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとする。
【００２１】
起点利用可能なルートの確認方法と同様で、前述操作は、具体的に、
まず、前記検索終点のハッシュコードを決定し、前記終点のハッシュコードに対して既存のルートのデータベースにおいてマッチングを行うステップと、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、終点範囲のグリッドとするステップと、
前記終点範囲のグリッドを経由する既存のルートを終点利用可能なルートとするステップと、を含む。
【００２２】
ここで、本実施例における前記既存のルートのデータベースは逆索引データベースであって、各既存のルートの記録は前記逆索引データベースに記憶されるとともに、記録のうちの少なくとも１つの属性項の数値の順序に基づいて順序付けられ、前記属性項は少なくとも起点ハッシュコードと、終点ハッシュコードと、及び／または経由点のハッシュコードを含む。
【００２３】
Ｓ１４０：前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを候補ルートとする。
【００２４】
さらに、前記起点利用可能なルートと前記終点利用可能なルートのうちの、前記検索起点を経由するとともに前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを候補ルートとしてもよく、即ち、起点利用可能なルートでもあり、終点利用可能なルートでもあるルートを候補ルートとしてもよい。
【００２５】
Ｓ１５０：迂回距離に基づいて前記候補ルートを選別する。
【００２６】
図２に示すように、前述操作は具体的に以下のステップを含む。
【００２７】
Ｓ１５１：前記候補ルートの最初の起点と最初の終点、及び前記検索起点と前記検索終点に基づいて、ルートを新たに計画する。
【００２８】
前記最初の起点、最初の終点、検索起点及び検索終点の順番が異なるため、迂回距離の差が大きくなり、新たに候補ルートを最適化すべきである。
【００２９】
Ｓ１５２：再計画ルートの迂回距離を計算し、ここで、前記迂回距離は、前記再計画ルートのルート距離と前記候補ルートの最初のルート距離との距離差の値である。
【００３０】
ここで、前記最初のルート距離は、最初の起点から最初の終点までの最適なルート距離である。前記最適なルートは、所要時間が最も短く、道路状況良好、高速優先、渋滞回避及び／または距離最短のルートであってもよく、これらのルートの属性は、既存のルートの属性項としてデータベースに記憶されておいてもよく、リアルタイムに更新されてもよい。
【００３１】
Ｓ１５３：前記迂回距離が所定閾値範囲内にある前記再計画ルートを、選別して得られたルートとする。
【００３２】
さらに、前記迂回距離の所定閾値は、車両所有者により決定されてもよく、具体的な距離値を設定してもよく、再計画ルートからより良いルートを選択してもよい。ルートを選別する時に、迂回距離を考慮する他に、前記再計画ルートのかかる時間、道路状況及び高速道路の料金情報なども合わせて考慮してもよい。
【００３３】
本発明の実施例に係る走行ルートマッチング方法は、既存のルートのデータベースにおいて、既存のルートを逆索引の形態で記憶し、既存のルートの記録の起点ハッシュコード、終点ハッシュコード及び／または経由点のハッシュコードなどの属性項の数値の順番に基づいて、既存のルートを順序付けることにより、乗車したいユーザのルートに対する検索効率を向上させるほか、ある程度に車両所有者の迂回距離を減らし、時間を節約するため、マッチング効率及びユーザと車両所有者の体験を向上させる。
【００３４】
好ましくは、迂回距離に基づいて前記候補ルートを選別した後に、本発明の実施例に係る発明は、既存のルートに対応する車両所有者の発車時間に基づいて、選別したルートを順序付けるステップをさらに含んでもよい。
【００３５】
即ち、選別したルートに、ルートのそれぞれの最初の起点の発車時間に基づいて順序付けを行い、発車が早いのを前に、発車が遅いのを後に表示してもよく、好ましくは、前記検索起点に到着予定時間に基づいて順序付けてもよく、予定到着時間が早いのを前に、予定到着時間が遅いのを後にするように順序付けてもよい。２つの異なる順序付け方により、ユーザが発車時間または予定到着時間の情報に基づいて、自分に適する時間を選択し、自分の時間を合理的に利用する。
【００３６】
好ましく、本実施例の前記走行ルートマッチング方法は、さらに、
車両所有者の運転歴または車両モデルを含むユーザのルート補助デマンドに基づいて、候補ルートを選別するステップを含む。
【００３７】
前記ルート補助デマンドは前述二項に限定されず、車両所有者が登録した時に得られた車両所有者ＩＤ（ｉｄｅｎｔｉｆｉｃａｔｉｏｎ、身分認識コード）、車両所有者の性別なども含んでもよい。本発明において、ルート補助デマンドは、既存のルートの記録の属性項としてもよく、既存のルートのデータベースに記憶され、好ましくは、前記記憶されたルート補助デマンドをリアルタイムに更新してもよい。
【００３８】
本発明は、先ず、前記ルート補助デマンドにおける少なくとも一項に基づいて候補ルートを選別し、そして、検索しようとするルートの検索起点と検索終点に基づいて選別してもよく、このように、検索プロセスにおいて、異なる選別結果を取得し、ユーザの体験を向上させることができる。
【００３９】
例示的に、車両所有者の運転歴が少なくとも３年であることをルート補助デマンドとして検索を行い、既存のルートデータベースにおいて、当該条件に合致する車両所有者及び車両所有者の関連情報を統計することができ、前記関連情報は、条件に合致する車両所有者の走行ルート、車両所有者の性別及び車両所有者ＩＤなどを含む。
【００４０】
実施例２
図３は本発明の実施例２に係る走行ルートマッチング方法を示すフローチャートである。図４は本発明の実施例２に係る走行ルートを例示的に説明する。図４に示すように、ユーザはＣポイントでしたく、目的地はＤポイントである。このように、当該走行ルートマッチング方法は図３に示すように、操作のステップは以下のステップを含む。
【００４１】
Ｓ３０１：ユーザの検索しようとするルートの検索起点Ｃと検索終点Ｄを取得する。
【００４２】
Ｓ３０２：既存のルートのデータベースにおいてサーチを行い、前記検索起点Ｃ周囲の所定範囲内のグリッドを経由する既存のルートＡ−Ｂ、Ａ−Ｍ及びＰ−Ｑを選択し、起点利用可能なルートとする。
【００４３】
ここで、マップにおける位置は前述グリッドの形で区分され、前記ハッシュコードは各グリッドに対応付けられるとともに、ハッシュリンクリストの形で記憶され、隣接するグリッドのハッシュコードはハッシュリンクリストにおいて互いに関連付けられ、容易に一定数量の隣接するグリッドを見つけることができる。
【００４４】
図４に示すように、前述の操作は、具体的に、前記検索起点のハッシュコードはＷＸ４Ｇ０８であることを決定し、ＷＸ４Ｇ０８を既存のデータベースにおいてマッチングを行い、ハッシュリンクリストにおいて、マッチングされたハッシュコードＷＸ４Ｇ０８と隣接する所定数量のハッシュコードＷＸ４Ｇ０９、ＷＸ４Ｇ０Ｂ、ＷＸ４ＦＢＷ及びＷＸ４ＦＢＺを取得し、起点範囲グリッドとし、前記起点範囲グリッドを経由する既存のルートＡ−Ｂ、Ａ−Ｍ及びＰ−Ｑを起点利用可能なルートとする。
【００４５】
Ｓ３０３：既存のルートのデータベースにおいてサーチを行い、前記検索終点Ｄ周囲の所定範囲内のグリッドを経由する既存のルートＡ−Ｂ、Ｂ−Ｎ及びＰ−Ｑを選択して、終点利用可能なルートとするステップである。
【００４６】
具体的に、先ず、前記検索終点のハッシュコードはＷＸ４ＦＣＰであることを決定し、ハッシュコードＷＸ４ＦＣＰを既存のルートのデータベースにおいてマッチングを行い、そして、ハッシュリンクリストにおいてマッチングされたハッシュコードＷＸ４ＦＣＰと隣接する所定数量のハッシュコードＷＸ４Ｇ１０、ＷＸ４ＦＢＺ、ＷＸ４ＦＣＮ及びＷＸ４ＦＣＳを取得し、終点範囲グリッドとし、前記終点範囲グリッドを経由する既存のルートＡ−Ｂ、Ｂ−Ｎ及びＰ−Ｑを終点利用可能なルートとする。
【００４７】
Ｓ３０４：前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、結果はＡ−Ｂ及びＰ−Ｑであり、共通部分におけるＡ−Ｂ及びＰ−Ｑを候補ルートとする。
【００４８】
Ｓ３０５：前記候補ルートＡ−Ｂの最初の起点Ａと最初の終点Ｂ、Ｐ−Ｑの最初の起点Ｐと最初の終点Ｑ、及び前記検索起点Ｃと前記検索終点Ｄに基づいてルートを新たに計画する。
【００４９】
Ｓ３０６：再計画ルートＡ−Ｃ−Ｄ−Ｂと最初のルートＡ−Ｂとの間の距離差の値を計算し（結果は３ｋｍ）、再計画ルートＰ−Ｃ−Ｄ−Ｑと最初のルートＰ−Ｑとの間の距離差値を計算する（結果は８ｋｍ）。
【００５０】
Ｓ３０７：実際の迂回距離が１０ｋｍ内にある再計画ルートＡ−Ｃ−Ｄ−ＢとルートＰ−Ｃ−Ｄ−Ｑを、選別して後得られたルートとする。
【００５１】
本実施例に係る発明は、既知ルートの起点及び主な経由点などの情報を属性項として記憶し、既知ルートの途中に乗り合う乗客のルートに対する検索を容易にし、実際の迂回距離の計算及び比較することにより、乗客にさらに適するルートの選択を提供することができる。
【００５２】
実施例３
図５は、本発明の実施例３に係る走行ルートマッチング方法の構成概略図である。図５に示すように、当該走行ルートマッチング装置は、検索予定ルート取得モジュール５１０と、第１選択モジュール５２０と、第２選択モジュール５３０と、利用可能ルート共通部分モジュール５４０と、第１選別モジュール５５０と、を備える。
【００５３】
前記検索予定ルート取得モジュール５１０は、検索起点と検索終点を含む検索しようとするルートを取得する。
【００５４】
前記第１選択モジュール５２０は、既存のルートのデータベースにおいてサーチを行い、前記検索起点の周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとする。
【００５５】
前記第２選択モジュール５３０は、既存のルートのデータベースにおいてサーチを行い、前記検索終点の周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとする。
【００５６】
前記利用可能ルート共通部分モジュール５４０は、前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを候補ルートとする。
【００５７】
前記第１選別モジュール５５０は、迂回距離に基づいて前記候補ルートを選別する。
【００５８】
前述装置において、既存のデータベースは逆索引データベースであって、ここで、各既存のルートの記録は前記逆索引データベースに記憶されるとともに、記録のうちの少なくとも一つの属性項の数値の順序に基づいて順序付けられ、前記属性項は少なくとも起点ハッシュコードと終点ハッシュコードとを含む。
【００５９】
好ましく、マップはグリッドの形で区分され、前記ハッシュコードは各グリッドに対応付けられるとともに、ハッシュリンクリストの形で記憶され、隣接するグリッドのハッシュコードはハッシュリンクリストにおいて互いに関連付けられる。
【００６０】
また、具体的に、前記第１選択モジュール５２０は、
前記検索起点のハッシュコードを決定し、前記検索起点のハッシュコードを既存のルートのデータベースにおいてマッチングを行い、
ハッシュリンクリストにおいてマッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、起点範囲のグリッドとし、
前記起点範囲のグリッドを経由する既存のルートを起点利用可能なルートとすることに用いられる。
【００６１】
具体的に、前記第２選択モジュール５３０は、
前記検索終点のハッシュコードを決定し、前記検索終点のハッシュコードを既存のルートのデータベースにおいてマッチングを行い、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、終点範囲のグリッドとし、
前記終点範囲のグリッドを経由する既存のルートを終点利用可能なルートとすることに用いられる。
【００６２】
さらに、前記第１選別モジュール５５０は、ルート計画サブモジュールと、迂回距離計算サブモジュールと、ルート決定サブモジュールと、を備える。
【００６３】
前記ルート計画サブモジュールは、前記候補ルートの最初の起点と最初の終点、及び前記検索起点と前記検索終点に基づいて、ルートを新たに計画する。
【００６４】
前記迂回距離計算サブモジュールは、再計画ルートの迂回距離を計算し、前記迂回距離は、前記再計画ルートのルート距離と前記候補ルートの最初のルート距離との距離差の値である。
【００６５】
前記ルート決定サブモジュールは、前記迂回距離が所定閾値範囲内にある前記再計画ルートを、選別して得られたルートとする。
【００６６】
本実施例に係る前記装置は、第２選別モジュール５６０をさらに備える。
【００６７】
前記第２選別モジュール５６０は、車両所有者の運転歴または車両モデルを含むユーザのルート補助デマンドに基づいて、候補ルートを選別する。
【００６８】
本実施例における前記装置は、順序付けモジュール５７０をさらに備える。
【００６９】
前記順序付けモジュール５７０は、迂回距離に基づいて前記候補ルートを選別した後に、既存のルートに対応する車両所有者の発車時間に基づいて、選別したルートを順序付ける。
【００７０】
前述走行ルートマッチング装置は、本発明の任意の実施例に係る走行ルートマッチング方法を実行でき、実行する方法に対応する機能モジュールと有益効果を有する。
【００７１】
実行例４
１つ以上のコンピュータ実行可能な命令を含む記録媒体であって、前記コンピュータ実行可能な命令は、コンピュータのプロセッサにより実行される時に、走行ルートマッチング方法を実行することに用いられており、前記方法は、
検索起点と検索終点とを含む検索しようとするルートを取得するステップと、
既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとするステップと、
既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとするステップと、
前記起点利用可能なルートと前記終点利用可能なルートとの共通部分を求め、共通部分におけるルートを候補ルートとするステップと、
迂回距離に基づいて前記候補ルートを選別するステップと、を含む
ことを特徴とする記録媒体。
【００７２】
前述記録媒体は前記方法を実行する時に、さらに、
既存のルートのデータベースは逆索引データベースであり、ここで、各既存のルートの記録は前記逆索引データベースに記憶されるとともに、記録のうちの少なくとも１つの属性項の数値の順序に基づいて順序付けられ、前記属性項は少なくとも起点ハッシュコードと終点ハッシュコードとを含んでもよい。
【００７３】
前述記録媒体は前記方法を実行する時に、さらに、
マップはグリッドの形で区分され、前記ハッシュコードは各グリッドに対応付けられるとともに、ハッシュリンクリストの形で記憶され、隣接するグリッドのハッシュコードはハッシュリンクリストにおいて互いに関連付けられ、
このようにして、既存のルートのデータベースにおいてサーチを行い、前記検索起点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、起点利用可能なルートとするステップにおいては、
前記検索起点のハッシュコードを決定し、前記検索起点のハッシュコードに対して既存のルートのデータベースにおいてマッチングを行うステップと、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、起点範囲のグリッドとするステップと、
前記起点範囲のグリッドを経由する既存のルートを起点利用可能なルートとするステップと、を含み、
既存のルートのデータベースにおいてサーチを行い、前記検索終点周囲の所定範囲内のグリッドを経由する既存のルートを選択して、終点利用可能なルートとするステップにおいては、
前記検索終点のハッシュコードを決定し、前記検索終点のハッシュコードに対して既存のルートのデータベースにおいてマッチングを行うステップと、
ハッシュリンクリストにおいて、マッチングされたハッシュコードと隣接する所定数量のハッシュコードを取得し、終点範囲のグリッドとするステップと、
前記終点範囲のグリッドを経由する既存のルートを終点利用可能なルートとするステップと、を含んでもよい。
【００７４】
前述記録媒体は前記方法を実行する時に、迂回距離に基づいて前記候補ルートを選別するステップにおいては、具体的に、
前記候補ルートの最初の起点と最初の終点、及び前記検索起点と前記検索終点に基づいて、ルートを新たに計画するステップと、
再計画ルートの迂回距離を計算するステップと、
前記迂回距離が所定閾値範囲内にある前記再計画ルートを、選別して得られたルートとするステップと、を含んでもよく、
ここで、前記迂回距離は、前記再計画ルートのルート距離と前記候補ルートの最初のルート距離との距離差の値である。
【００７５】
前述記録媒体は前記方法を実行する時に、迂回距離に基づいて前記候補ルートを選別した後に、
車両所有者の運転歴または車両モデルを含むユーザのルート補助デマンドに基づいて、候補ルートを選別するステップ、をさらに含んでもよい。
【００７６】
前述記録媒体は前記方法を実行する時に、迂回距離に基づいて、記候補ルートを選別した後に、
既存のルートに対応する車両所有者の発車時間に基づいて、選別したルートを順序付けるステップ、をさらに含んでもよい。
【００７７】
当業者は以上の実施形態についての説明により次のことを明確に理解することができる。本発明がソフトウェア及び必要な汎用ハードウェアにより実現することができ、勿論、ハードウェアにより実現することもできるが、多くの場合に、前者の実施形態がより好適である。このような理解を踏まえて、本発明の解決手段が実質的に又は従来技術に対して貢献している部分がソフトウェア製品の態様で実現することができる。該コンピュータソフトウェア製品は、コンピュータ読み取り可能な記録媒体、例えばフロッピーディスク、光ディスク、読み出し専用メモリ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ、ＲＯＭ）、ランダムアクセスメモリ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ、ＲＡＭ）等に格納することができる。該コンピュータソフトウェア製品には、コンピュータ関連機器（パソコン、サーバ、又はネットワーク機器等が挙げられる）に本発明の各実施例に係る方法を実行させる複数の命令を含む。
【００７８】
注意されたいのは、上記走行ルートマッチング装置に係る実施例において、各ユニット及びモジュールが機能ロジックによって分割されたものであるに過ぎず、前記の分割を制限するものではなく、対応する機能を実現することができれば足り、また、各機能ユニットの具体の名称は、互いに区別するためのものに過ぎず、本発明の保護範囲を制限するものではない。
【００７９】
以上に述べたものは、本発明の具体的な実施形態に過ぎず、本発明の技術的範囲を制限するものではなく、本発明が公開した技術範囲内に当業者が容易に変更または置換えるものについては、本発明の技術的範囲内に含まれることを理解されるべきである。よって、本発明の技術的範囲は、特許の請求の範囲に記載された内容を基準とする。
【図１】
0006476284.tif 000002
【図２】
0006476284.tif 000003
【図３】
0006476284.tif 000004
【図４】
0006476284.tif 000005
【図５】
0006476284.tif 000006