(57)【要約】車線レベル車両ルート指定およびナビゲーション装置は、交通流内の個々の車両のマイクロシミュレーションを行う、シミュレーションモジュールと、シミュレーションモジュールによって判定される、起点から目的地までの候補経路に沿った状況を評価し、候補経路に沿った推奨される車線レベル操縦を判定する、車線レベルオプティマイザとを含む。リンクレベルオプティマイザは、シミュレーションモジュールによって判定されるリンク走行時間に基づいて、候補経路を判定してもよい。シミュレーションは、リアルタイム交通状況データに基づいてもよい。推奨される候補経路は、配達またはサービスまたは緊急対応車両に提供される、あるいは避難計画のために、もしくはゴミ収集車または郵便配達車または除雪車等の車両のルートを指定するために使用されてもよい。
2016513805.tif 000002
【特許請求の範囲】
【請求項１】
車線レベル車両ルート指定およびナビゲーション装置であって、
交通流内の個々の車両のマイクロシミュレーションを行う、シミュレーションモジュールと、
前記シミュレーションモジュールによって判定される、起点から目的地までの候補経路に沿って予測される状況を評価し、前記候補経路に沿って使用が推奨される車線および関連付けられた車線レベル操縦を判定する、車線レベルルートオプティマイザと
を備える、車線レベル車両ルート指定およびナビゲーション装置。
【請求項２】
前記シミュレーションモジュールによって判定されるリンク走行時間に基づいて、前記候補経路を判定する、リンクレベルオプティマイザをさらに備える、請求項１に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項３】
前記シミュレーションモジュールは、前記候補経路のうちの少なくともいくつかのための複数回のシミュレーション実行を行い、
前記リンクレベルオプティマイザは、時間効率的かつ確実なルートおよびルート案内を識別するために使用される、請求項２に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項４】
前記使用が推奨される車線および前記関連付けられた車線レベル操縦は、運転者ルート選好を考慮する、請求項１に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項５】
前記運転者ルート選好は、車線選好を備える、請求項４に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項６】
前記車線レベルオプティマイザは、前記候補経路に沿った交通制御操作を考慮する、請求項１に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項７】
前記交通制御操作は、前記シミュレーションモジュールによってシミュレートされる、請求項６に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項８】
前記交通制御操作は、リアルタイム交通制御データに基づいて評価される、請求項６に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項９】
リアルタイム交通状況データのための入力をさらに備え、
前記シミュレーションモジュールは、少なくとも部分的に、前記リアルタイム交通状況データに基づいて、前記マイクロシミュレーションを行う、請求項１に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項１０】
前記車線レベルオプティマイザは、今後の下流車線状況を考慮する、請求項１に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項１１】
前記マイクロシミュレーションにおいて使用されるモデルおよび前記車線レベルオプティマイザは、交通流に対する障害物の影響を考慮する、請求項１に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項１２】
前記交通流に対する障害物は、（ａ）工事区域または（ｂ）交通事故のうちの１つ以上を含む、請求項１１に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項１３】
異なるルート指定は、前記起点から前記目的地まで走行する異なる車両に提供される、請求項１に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項１４】
前記シミュレーションモジュールは、（ａ）マルチスレッド型または（ｂ）分散型のうちの少なくとも１つである、請求項１に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項１５】
車線レベル車両ルート指定およびナビゲーション装置であって、
交通流内の個々の車両のマイクロシミュレーションを行うことにより、車線レベルにおいて候補経路を推奨するシミュレーションモジュールと、
リアルタイム交通状況データのための入力と
を備え、
前記シミュレーションモジュールは、少なくとも部分的に、前記リアルタイム交通状況データに基づいて、前記マイクロシミュレーションを行う、車線レベル車両ルート指定およびナビゲーション装置。
【請求項１６】
前記リアルタイム交通状況データは、（ａ）１つ以上の車両または（ｂ）１つ以上の道路区画のうちの少なくとも１つに対して利用可能である、請求項１５に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項１７】
前記リアルタイム交通状況データは、車線レベルにおいて利用可能である、請求項１５に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項１８】
前記推奨される候補経路は、緊急対応車両に提供される、請求項１５に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項１９】
前記推奨される候補経路は、避難計画のために使用される、請求項１５に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項２０】
前記推奨される候補経路は、あるエリア内の道路区画群を横断し、前記エリア内の全住所にサービス提供しようとする車両のルート指定を行うために提供される、請求項１５に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項２１】
前記推奨される候補経路は、除雪車に提供される、請求項２０に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項２２】
前記推奨される候補経路は、ゴミ収集車に提供される、請求項２０に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項２３】
前記推奨される候補経路は、郵便配達車に提供される、請求項２０に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項２４】
前記推奨される候補経路は、緊急対応車両に提供される、請求項１５に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項２５】
前記推奨される候補経路は、サービス車両に提供される、請求項１５に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項２６】
前記推奨される候補経路は、配達車両に提供される、請求項１５に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項２７】
前記シミュレーションモジュールは、（ａ）マルチスレッド型または（ｂ）分散型のうちの少なくとも１つである、請求項１５に記載の車線レベル車両ルート指定およびナビゲーション装置。
【請求項２８】
車線レベル車両ルート指定およびナビゲーション方法であって、
シミュレーションエンジンにおいて、交通流内の個々の車両のマイクロシミュレーションを行うことと、
車線最適化エンジンにおいて、前記行うことによって判定される、起点から目的地までの候補経路に沿って予測される状況を評価し、前記候補経路に沿った推奨される車線レベル操縦を判定することと
を含む、車線レベル車両ルート指定およびナビゲーション方法。
【請求項２９】
リンク最適化エンジンにおいて、前記行うことによって判定されるリンク走行時間に基づいて、前記起点から前記目的地までの候補経路を判定することをさらに含む、請求項２８に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３０】
前記行うことは、前記候補経路のうちの少なくともいくつかのための複数回のシミュレーション実行を行うことを含み、
前記判定することは、時間効率的かつ確実なルートおよびルート案内を識別することを含む、請求項２９に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３１】
前記判定することは、運転者ルート選好を考慮する、請求項１に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３２】
前記判定することは、前記候補経路に沿った交通制御操作を考慮する、請求項２８に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３３】
前記行うことは、前記交通制御操作をシミュレートすることを含む、請求項３２に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３４】
前記交通制御操作をシミュレートすることは、リアルタイム交通制御データに基づく、請求項３２に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３５】
リアルタイム交通状況データを入力することをさらに含み、
前記行うことは、少なくとも部分的に、前記リアルタイム交通状況データに基づいて、前記マイクロシミュレーションを行う、請求項２８に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３６】
前記判定することは、今後の下流車線状況を考慮する、請求項２８に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３７】
前記行うことにおいて使用されるモデルおよび前記判定することは、交通流に対する障害物の影響を考慮する、請求項２８に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３８】
前記交通流に対する障害物は、（ａ）工事区域または（ｂ）交通事故のうちの１つ以上を含む、請求項３７に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項３９】
異なるルート指定は、前記起点から前記目的地までの異なる車両に提供される、請求項２８に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項４０】
車線レベル車両ルート指定およびナビゲーション方法であって、
シミュレーションエンジンにおいて、交通流内の個々の車両のマイクロシミュレーションを行うことにより、車線レベルにおいて候補経路を推奨することと、
リアルタイム交通状況データを入力することと
を含み、
前記行うことは、少なくとも部分的に、前記リアルタイム交通状況データに基づいて、前記マイクロシミュレーションを行う、車線レベル車両ルート指定およびナビゲーション方法。
【請求項４１】
前記リアルタイム交通状況データは、（ａ）１つ以上の車両または（ｂ）１つ以上の道路区画のうちの少なくとも１つに対して利用可能である、請求項４０に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項４２】
前記リアルタイム交通状況データは、車線レベルにおいて利用可能である、請求項４０に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項４３】
推奨される候補経路を緊急対応車両に提供することをさらに含む、請求項４０に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項４４】
避難計画のための候補経路を推奨することをさらに含む、請求項４０に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項４５】
ルート道路区画全体を横断しようとする車両のルートを指定するために推奨される候補経路を提供することをさらに含む、請求項４０に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項４６】
推奨される候補経路を除雪車に提供することをさらに含む、請求項４５に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項４７】
推奨される候補経路をゴミ収集車に提供することをさらに含む、請求項４５に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項４８】
推奨される候補経路を郵便配達車に提供することをさらに含む、請求項４５に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項４９】
推奨される候補経路を緊急対応車両に提供することをさらに含む、請求項４０に記載の車線レベル車両ルート指定およびナビゲーション方法。
【請求項５０】
前記推奨される候補経路は、サービス車両に提供される、請求項４０に記載の車両ルート指定およびナビゲーション装置。
【請求項５１】
前記推奨される候補経路は、配達車両に提供される、請求項４０に記載の車両ルート指定およびナビゲーション装置。
【請求項５２】
交通計画方法であって、
シミュレーションエンジンにおいて、交通流内の個々の車両のマイクロシミュレーションを行うことと、
前記マイクロシミュレーションに基づいて、（ａ）改変される道路幾何学形状、（ｂ）改変される交通信号設定、または（ｃ）道路課金のうちの少なくとも１つを判定することと
を含む、交通計画方法。
【請求項５３】
前記判定することは、交通信号タイミングを判定することを含む、請求項５２に記載の交通計画方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願への相互参照）
本出願は、２０１３年３月１５日に出願された、同時係属の同一出願人による米国仮特許出願第６１／７８９，０１９号の利益を主張する。上記文献は、その全体として本明細書において参照することによって援用される。
【０００２】
本発明は、広く分離された出発点と目的地との間を進路するための交通ネットワークを通して種々のタイプの個々の車両のための車線レベルルート案内を提供するためのプロセスおよび装置と、１台、数台、および／または非常に多くの台数の多様な自動車のための効果的ルート指定戦略を識別するための測定、シミュレーション、および最適化を通して、車線レベルで地域および地帯交通を管理するための方法とを提供する。本発明はまた、交通計画および管理ならびに交通シミュレーションおよび予測のための改良された方法および装置を提供する。
【背景技術】
【０００３】
（発明の背景）
個々の運転者によるルートおよび車線の不良な選択肢から生じる道路ネットワークの使用には、大いなる非効率性が存在し、個々の運転者および他の車両内で走行中の多数の個人の両方にとって、渋滞および遅延につながる。緊急車両は、その目的地に辿り着くために苦戦し、多くの場合、その指名のためにとるべき最良ルートまたは最速となるであろう走行車線を確信していない。潜在的に、渋滞緩和案内を識別および実装し得る、公知のナビゲーションおよび交通管理システムは、原始的であり、同一の情報が全運転者に与えられるときでさえ、逆効果となり得る。
【発明の概要】
【課題を解決するための手段】
【０００４】
（発明の要約）
本発明の実施形態による、レーンレベル車両ルート指定およびナビゲーション装置は、交通流内の個々の車両のマイクロシミュレーションを行う、シミュレーションモジュールと、シミュレーションモジュールによって判定される、起点から目的地までの候補経路に沿って予測される状況を評価し、候補経路に沿って使用が推奨される車線および関連付けられた車線レベル操縦を判定する、車線レベルルートオプティマイザとを含む。リンクレベルオプティマイザは、シミュレーションモジュールによって判定されるリンク走行時間に基づいて、候補経路を判定するために使用されてもよく、次いで、車線レベルオプティマイザを用いてさらに精緻化されてもよい。シミュレーションは、リアルタイム交通状況データに基づいてもよい。
【０００５】
車線レベルオプティマイザは、交通制御のシミュレーションまたはリアルタイム交通制御データを含む、候補経路に沿った交通制御操作を考慮してもよい。シミュレーションは、よりタイムリーなナビゲーション案内を提供する、または複数の代替を同時に評価するために、より高速な計算のためのマルチスレッド型および／または分散型であってもよい。
【０００６】
本発明の別の実施形態によると、車線レベル車両ルート指定およびナビゲーション装置は、交通流内の個々の車両のマイクロシミュレーションを行い、車線レベルにおいて候補経路を推奨するためのシミュレーションモジュールと、リアルタイム交通状況データのための入力とを含み、マイクロシミュレーションは、少なくとも部分的に、該リアルタイム交通状況データに基づく。
【０００７】
候補車線レベル経路は、緊急対応車両に提供される、あるいは避難計画のために、もしくはゴミ収集車または郵便配達車または除雪車等、道路区画の全群を横断しようとする車両のルートを指定するために使用されてもよい。
【０００８】
本発明による方法もまた、提供される。本方法はまた、マイクロシミュレーションに基づいて、（ａ）道路幾何学形状の改良または（ｂ）交通信号設定および交通信号タイミングの改良のうちの少なくとも１つを判定することを含む、交通計画または管理のために使用されてもよい。
【０００９】
本発明は、運転者によって行われるより現実的車線レベル軌道選択を考慮することによる、交通マイクロシミュレーション方法の改良を含む。単回シミュレーション実行の状況では、先読み機構が、より良好な車線レベル案内を識別するために使用され、案内が、後の時間間隔における他の交通に照らして実行可能であることを確実にする。先読み機構はまた、交通マイクロシミュレーションの他の側面も改善する。
【００１０】
これらの方法は、他の交通に照らして適切な車線レベル案内を要求し、さらに、その走行車線別に車両を測位する能力を通して、車線レベルナビゲーションを可能にする、将来の自律的車両システムにおいて、特に効果的であり得る。
【００１１】
前述および他の目的ならびに利点は、付随の図面と関連して検討される、以下の発明を行うための形態の考察に応じて明白となるであろう（同様の参照文字は、全体を通して同様の部品を指す）。
【図面の簡単な説明】
【００１２】
【図１】図１は、Ｐｈｏｅｎｉｘ（Ａｒｉｚｏｎａ）における交通のマイクロシミュレーションの視覚的表現である。
【図２】図２は、本発明の実施形態が動作し得る、交通環境を示す。
【図３】図３は、２つの地点間の２つの候補経路を示す。
【図４】図４は、図３の一部のさらなる詳細を示す。
【図５】図５は、図４の一部のさらなる詳細を示す。
【図６】図６は、予想車線変更につながる、交通状況の実施例を示す。
【図７】図７は、本発明の実施形態による、ナビゲーションエンジンの流れ図である。
【図８】図８は、道路区画の実施例である。
【図９】図９は、図８の道路区画を表す、車線グラフである。
【図１０】図１０は、シミュレーションのマルチスレッド化を図示する、略図である。
【図１１】図１１は、シミュレーションを行うコンピュータのクラスタ化を図示する、略図である。
【発明を実施するための形態】
【００１３】
（発明の詳細な説明）
既存のナビゲーションシステムは、主に、予期されるリンク走行時間および方向転換ペナルティと、あるタイプまたはクラスの道路の使用のための時期的選好とに基づいて、ルートを選定することによって、ルート案内を提供する。これらのシステムは、必須車線変更が特定の推奨または選定される経路を横断するために要求される場所を容易に識別することができるが、種々の交通状況および異なる場所において使用するための最良車線には敏感ではない。それらはまた、車線使用および車線変更に関する障壁および制限を明示的に表すことができない。車線レベルにおける交通渋滞を明示的に検討するもの、または車線、またはさらに、ある車線が、渋滞している、またはアクセス不可能であるときの代替経路を選定するための運転者挙動における差異を認識するものはない。車線レベルデータを用いることによって、より効果的ルートおよび車線選択肢が、判定されることができる。ルート案内ナビゲーションにおいて車線レベル詳細を利用するプロセスは、適切な交通シミュレーションを通してさらに評価され、また、精緻化されることができる。
【００１４】
微視的シミュレーションモデルは、十分に大きい地理的スケールにおいて未だ構築されておらず、構築および有効化が非常に高価である、または有用となるためには、計算上、非常に要求が厳しいであろうため、車線レベルモデル化詳細を欠いている、中間視的交通シミュレーションが、リアルタイムルート案内を提供する唯一の実行可能方法であるというのが通説となっている。地域全体の交通マイクロシミュレーションに対する障害物として、従来、時刻別の進路パターンに関する詳細データと道路区画およびその中の車線別のネットワーク性能の欠如、運転者ルート選択肢をモデル化することの困難点、特に、非常に渋滞した交通状況下における、多数の車両の正確なシミュレーションにおける問題、ならびに有用であるために、結果のための十分に短い時間内でシミュレーションを行う計算負荷が挙げられる。しかしながら、地域スケールにおけるマイクロシミュレーションは、本発明の譲受人に譲渡された米国特許第７，１５５，３７６号（参照することによって、全体として本明細書に組み込まれる）に説明される方法を使用して実装されることができる。
【００１５】
交通シミュレーション、特に、車両が車線レベル詳細を用いてシミュレートされる、微視的交通シミュレーションでは、ルート案内は、車両に提供される一方、同時に、ネットワーク上の他の交通も検討することができる。しかし、既存のシミュレーションベースのシステムは、起点から目的地までの車線使用またはルートの一部のための規範的戦略に関係なく、実際の運転者挙動および自由裁量の車線変更のモデル化を試みる。その結果、これらのシステムは、履歴、測定、シミュレート、または予測される車線レベル密度および可能性として考えられる速度に基づいて、進路全体または進路の一部のために使用すべき最良車線、あるいは車線変更を試みる、または行うべき、道路リンク内の場所を適切に判定することができない。
【００１６】
インターネットソースによって提供される、現在の市販のナビゲーションシステムおよびナビゲーション案内は、多くの場合、発生するにつれて渋滞を識別し、代替ルートを提供することができる。本案内は、３つの基本限界を有する。第１に、同一の２つの場所間の全走行車は、同一の案内が与えられ、これ自体が、逆効果であり得る。第２に、より深刻なこととして、現在の状況が、ルート案内が妥当であるために十分に長く存続し続けるであろうと仮定される。これは、渋滞が、任意の時点で悪化または軽減し得るため、当てはまることはほとんどあり得ない。第３に、他の車線より良好な予期される走行時間を提供するであろう、具体的場所における車線に関する具体的案内が存在しない。
【００１７】
車線レベルにおける履歴データ、または車線レベル精査データ、または両方に依拠するシステムが提案されているが、履歴または現在のデータのいずれも、ある時点において被られるであろう走行状況に全く適用されない場合がある。天候または催事または事故等の実世界状況における変化は、そのような以前のデータを誤ったものにするであろう。また、典型的には、履歴データまたは精査データは、全車線区画および交差点を通る移動に利用可能であるわけではないであろう。提案されている自己回帰モデル等の統計的方法は、見逃した観察を補填するために使用される場合があるが、それらの方法は、依然として、過去の体験および状況に依拠する同一の限界を有する。
【００１８】
交通信号または遮断された交差点、二重駐車車両、および歩行者の影響を捕捉することができないこと、ならびに走行環境の多様性を検討することができないこと（平均的状況に基づく案内を非常に準最適なものにし得る）等の他の限界も同様に存在し得る。
【００１９】
適応交通信号システムおよびランプメータリングのような他の手段は、異なる渋滞レベルにおける交通システムの異なる性能につながり得る。これらの機構の挙動および影響を表すことができないことは、欠陥または準最適ルート案内につながり得る。
【００２０】
他の車両および他の車両交通の混合の明示的検討は、ルート指定および交通管理において有利となり得る。１台または数台の低速車両の存在さえ、著しくかつ確率的に、全体的交通流に影響を及ぼし、渋滞を生じさせ得ることは良く理解されている。また、トラック、特に、大型トラックの割合は、ネットワーク性能に有意な影響を及ぼすことが知られている。車両レベルモデル化がなければ、低速車両の存在は、考慮され得ない。
【００２１】
クラウドソーシング、携帯電話、航空画像、ＬＩＤＡＲ、より精密な全地球測位システムデバイス、道路センサ、車載センサ、および道路カメラからの新しい形態のデータ収集は、徐々に、地域全体のシミュレーションのためのデータ障壁を徐々に低下させつつある。新しいデータソースの全てが、車線レベル地理的分解能および精度を有するわけではないが、ルート指定、交通シミュレーション、および交通管理目的のために利用可能な車線レベル情報の供給が、増加することが予期されるはずである。
【００２２】
現在のナビゲーションシステムは、ルート案内を提供するとき、全くではないにしろ、時間をおろそかにする。ピーク周期および他の時刻に対応する、予期されるリンク走行時間または使用される速度が存在し得る、あるいは単に、ポストされた速度および／またはリアルタイムで観察された速度に基づく、いくつかの複合走行時間を使用し得る。典型的には、これらの速度は、道路の機能クラス別に変動するが、地域内またはそれを越えて、単一道路リンク毎に収集または観察されない。いくつかのシステムは、渋滞に関するリアルタイムデータを利用することができるが、これらのデータは、典型的には、主要高速道路に制限され、根幹道路に関する状況または１５〜３０分を超えて存続するであろう状況を将来的に考慮することができない。これらのシステムのいずれも、可能性として、ルートを辿るときに方向転換毎に提供される車線の数を示す以外、ルート指定のために、車線レベル情報を明示的に使用しない。
【００２３】
既存の交通管理システムは、ほとんどの高度なリアルタイム交通管理および制御システムでさえ、予測のために簡略化されたモデルを使用する。走行需要および走行時間は、履歴データまたは限定されたリアルタイム測定のいずれかに基づく。車線レベル走行需要の推定およびそのような需要に基づく交通流の最適化の文献証拠は、存在しない。
【００２４】
中間視的シミュレーション方法を使用する、ある公知のシステムでは、供給面重視の交通性能は、リンクレベルで取り扱われ、車線レベルではない。概して、研究文献は、マイクロシミュレーションが、地域全体には実行不可能であり、ナビゲーション案内を提供するために十分に高速で計算されることができないことを教示している。
【００２５】
しかしながら、前述の組み込まれた米国特許第７，１５５，３７６号は、ルート指定および交通マイクロシミュレーションのために好適な車線レベルＧＩＳデータベースを説明する。そのシステムに基づいて、Ｐｈｏｅｎｉｘ（Ａｒｉｚｏｎａ）の５００平方マイルエリア内の交通流の全ての作業マイクロシミュレーションモデルが、開発されており、ラップトップコンピュータ上でも、本シミュレーションは、リアルタイムより高速で実行される。付加的拡張を伴って、さらなる速度改良が、ナビゲーションのためのシステムを実用化するために達成されることができる。本明細書に提供される方法および装置は、１台の車両（１人乗り自動車）、カープール車両（相乗り車両（ＨＯＶ）車線等の付加的利用可能な車線使用代替を有し得る）、トラック、バス、オートバイ、または自転車）のためのより詳細かつより効率的ルート案内を生成し、また、大規模都市圏地域内の広く分離された起点から目的地までの経路を横断する複数の車両から生じる、交通渋滞の管理および改善を提供する。異なる車両タイプのための車線使用許可および制限（前述のカープール例等）もまた、車線レベルルート指定に考慮されてもよい。
【００２６】
これらの改良されたプロセスは、高速道路上ならびに街路上の交差点間および内の交通および幾何学状況に関する時間依存車線レベル情報を記憶、管理、および利用する能力に基づく。交差点間では、道路は、交通特性（例えば、カーブ、坂道、車線数）に基づく、区画に分割されてもよく、各区画は、車線に分割されてもよい。隣接する区画および交差点における上流車線と下流車線との間の配列は、車線コネクタによって説明される。走行需要は、エンティティ別の個々の進路または総進路数のいずかとして、起点、目的地、および所望の出発または到着時間を使用して、地理的および時間的に、ネットワークに関連付けられる。車両場所および軌道、車線区画特異的車両車線占有率／密度、車両間隙分布率、ならびに速度が、短時間間隔の間、観察および測定と、また、詳細マイクロシミュレーションとから、記録されることができる。これらのデータは、起点から目的地までの車線レベルにおいて、可能性の高い走行時間および潜在的車両軌道の他の特性を分析するために使用されることができる。同様に、これらのデータ項目は、交差点の内側で生じる、軌道の構成要素のために回収されることができる（遅延は、多くの場合、車両の対立する移動およびさらに歩行者のため被られる）。必要データの全てが、現場で観察または測定されることができない場合、詳細シミュレーションは、必要とされる場所および／または時間間隔のために利用可能な測定を補完するために使用されることができる。
【００２７】
図１は、Ｐｈｏｅｎｉｘ（Ａｒｉｚｏｎａ）における交通の前述のマイクロシミュレーションを描写し、ボックス１は、ボックス２に示されるように、近地上現実レベルの詳細を伴う、車両および車線レベル幾何学形状を含む、交差点を表す。モデルはまた、ボックス３に示されるように、詳細交通信号タイミングおよび他の交通管理データを含み、信号動作およびそれらに対する運転者の挙動応答の正確なシミュレーションを可能にする。例えば、ボックス４は、任意の時間ｔにおける、交通信号コントローラの動作状態を図示し、ボックス５は、時間ｔ＋１０秒における、そのコントローラの動作状態を表す。これは、需要（すなわち、車両）と、ナビゲーションシステムが動作する環境の供給（すなわち、車線レベル幾何学形状および交通信号動作）要素の両方の高忠実性シミュレーションを可能にする。
【００２８】
車線レベルナビゲーション問題はその複雑な性質と、運転者および／または交通管理システムならびにスタッフに利用可能な情報の欠如と、不十分な分析および予測方法とのため、都市圏道路ネットワークの小区分内でさえ多く存在する。以下の実施例は、例証であり得る。
【００２９】
（実施例１）
最初に、両道路が渋滞する時刻における、２つの主要高速道路間の合流点を検討する。高速道路のうちの一方では、交通は、ある高速道路から他の高速道路に出るために指定された車線上において、２マイルを超えて停滞している。３つの他の車線は、低速ではあるが、移動しており、せかせかした運転者によって多数回の車線変更が行なわれている。ある運転者は、抜け出る必要がある。運転者は、長い行列の終了時に出口車線の中に移動すべきか、または最右から２番目の車線を走行し、次いで、出口車線に割り込むべきか？後者の場合、車線変更が試みられるべき場所は？
【００３０】
（実施例２）
２車線環状交差路では、運転者は、ある地点から進入し、第３の出口点から抜け出る必要がある。どの車線が使用され、その範囲は？
【００３１】
（実施例３）
工事区域が、道路の右車線を遮断している。作業エリアのどれくらい前方に標識が置かれるべきであり、ある車線内の運転者は、どれくらい近くで空いている車線へと操縦し始めるべきか？
【００３２】
（実施例４）
車線減少が存在する。いつおよびどこで、運転者は、終了する車線から出ようと試みるべきか？これは、数分間の間に予測されるものを含む、現存状況に依存するであろう。その道路に詳しい運転者は、車線減少が存在することを把握している一方、観光客等の他の運転者は、そうではない。システムは、どのように既知および無知運転者の両方を考慮すべきか？
【００３３】
（実施例５）
前方の高速道路が、遮断されているが、高速道路からの遮断されていない出口ランプが存在する。渋滞するエリアの周囲に、出口ランプからのより長い代替ルートが存在する。高速道路から出る方が、そこに留まるよりも時間を節約することになるか？交通遮断が解消するのにどれくらいの時間がかかるかは不明であり、どれだけの人が代替ルートをとり、その性能を劣化させるのかも不明である。
【００３４】
概して、自由裁量の車線変更は、標的車線における改良された運転体験の予想を伴う。渋滞する交通における車線変更は、遅延を伴い、他者に遅延を生じさせ、個々の遅延および全体的システム遅延の最小限化を予測困難にする。
【００３５】
例えば、今後１５分における交通信号または料金所の状態を把握することは困難である。その日の同じ時間であっても、前日または前の週の同日と同一であると考えることは、合理的ではないであろう。しかしながら、図２に描写されるもののような交通環境の要素および複雑性を表す可能な包括的交通シミュレーションシステムは、履歴情報および現場から利用可能なリアルタイム交通情報を融合し、次いで、その情報を有用な短期予測、したがって、有意義な車線レベルルート案内に関連させることができる。
【００３６】
図２は、本発明の実施形態によるシステムが動作し得る、状況を図示する。現場に一般に見られるハードウェア、例えば、舗道および交通カメラ２０２内に埋め込まれた磁気ループ検出器２０１は、リアルタイム交通データを提供することができ、これは、電気または光学ケーブルを経由して、あるいはワイヤレスで、中央コンピューティング環境２０３に伝送されることができ、そこに、履歴交通データもまた、記憶される。交通信号コントローラ２０４はまた、遠隔性能監視のために、リアルタイム状態情報を提供する。衛星および地上ワイヤレス通信デバイス２０５は、コンピューティング環境２０３への交通データの伝送をサポートし、そこで、シミュレーションが、実行され、ルート指定戦略が、案内がそれらの同一の通信デバイスを通して走行車に返信される前に、試験される。未だ逸脱しておらず、ルート上にいる運転者は、自宅または職場のパーソナルコンピュータ２０６上、または車載システム２０７上、またはモバイルデバイス２０８（ハンドヘルドナビゲーションデバイスならびに携帯電話を含む）上で案内を受信してもよい。命令２０９もまた、交通をより良好に管理するために、交通信号制御デバイス２０４に返されることができる。その結果、システムの種々のユーザ（例えば、商業用車両、乗用車等の運転者）は、その特定のニーズまたは目的に合わせた車線レベルルート案内２１０を受信し得る。
【００３７】
より緻密なネットワークグラフとともに車線レベル情報を使用する、ナビゲーションエンジンは、推奨される車線レベルルートを生成することを可能にする。案内は、変更車線において費やされる時間および努力と、車線内ならびに交差点でおよびそれを通して予期される操作速度（信号機付きかどうかにかかわらず）、または高速道路上の合流および割り込み区分ならびに車線内において予期される速度を考慮する。これらは、種々のタイプの観察から測定され、Ｈｉｇｈｗａｙ  Ｃａｐａｃｉｔｙ  Ｍａｎｕａｌ法またはより詳細なシミュレーションの適用を通して、検証または有効化されることができる。マイクロシミュレーションは、データが、他のソースから利用可能ではない、または費用効果的に回収されることができない場合、データを生成または補完するために使用されることができる。
【００３８】
０．１秒〜１秒の範囲の非常に短い時間間隔で地域交通流をシミュレートする、ナビゲーションエンジンが、代替車線レベルルートを評価するために使用されることができる。一実施形態では、シミュレートされる精査車両は、特定の車線レベル軌道の性能を計算するために使用される。複数回のシミュレーション実行は、任意の所与の軌道と関連付けられた走行時間の相違を推定し、相違、したがって、車線レベルルートの信頼性を検討することを可能にする。任意の車線レベルルート選択肢は、交通信号および交通流の本質的可変性質から生じる、多数の確率的影響を被るであろう。ナビゲーションシステムは、ルートを走行車に推奨する際、予期される走行時間に加え、信頼性を考慮し得る。
【００３９】
ナビゲーションのためのルート選択は、従来、最良経路の正確かつ迅速な計算のために、周知かつ深く研究されたアルゴリズムを使用して、ある形態の最短経路計算を使用していた。これらの方法は、ノード／ノードまたはリンク／リンク最短経路法を使用して、リンクレベルで適用される。好適なデータが得られることができる場合、全く同一の方法が、車線レベルに適用されることができるが、ネットワークのサイズは、都市圏地域では、非常に大きく、経路上の一対の車線間の遷移が、車線に沿った特定の地点のみにおいてではなく、経路に沿った任意の場所で生じ得るため、結果を記録することは、より複雑である。また、車線レベル詳細を検討するために拡張され得る、離散選択肢公式を使用したルート選択肢モデルも存在する。
【００４０】
種々の目的機能を伴う、リンクレベルおよび車線レベル最短経路は、車線レベルナビゲーションのための推奨を提供する、またはより精緻化された車線レベルナビゲーションのための候補を生成するために使用されることができる。最短経路計算のパラダイムは、リンクまたはリンク区画の分解能限界を有し、リンク内の連続車線変更の可能性に対して有用ではない。本限界は、より多数のより短いリンクの作成を通して有益に解決されることができず、それ自体、データニーズおよびデータ有効性の観点から、他の問題をもたらすであろう。
【００４１】
マイクロシミュレーションを通して、候補車線レベル最短経路軌道が、代替的かつ知的に摂動させる車線変更場所およびタイミングを用いて評価されることができる。したがって、シミュレーションは、車線レベル案内代替間で精緻化および選択するために使用されることができる。
【００４２】
地理的に正確な車線レベルネットワークデータベースならびにリアルタイム測定およびコンピュータ合成交通情報が、シミュレーション内で使用される。データの量は、実質的であり得る、ナビゲーションネットワークおよび使用される詳細レベルは、計算および通信負荷を低減させるために、慎重に選択されなければならない。
【００４３】
予想的かつルート戦略的に計画された車線変更は、有意な方法において、走行車走行時間およびルートを改良することができる。図３は、場所３１１から場所３１３までの候補経路のうちの２つ３０１、３０２を示す。この場合、運転者は、斜線経路を選定しており、場所３１２に接近しつつある。運転者が差し迫った車線変更決定を計画しなければならない、選定される経路上の下流の距離またはリンク（すなわち、道路区画）の数は、先読み範囲と呼ばれる。次の２つの交差点を接続する、すぐ下流の道路区画は、３０３にハイライトされ、図４により詳細に示される。
【００４４】
車線レベルにおける車線接続および交通状況は、良好なナビゲーションシステムのために重要な情報である。我々の実施例では、車両４０１の運転者は、交差点４０３で左折することを意図し、２つの左車線は、左折を行うことが許可されている。車線接続が懸念される場合、運転者は、経路に留まるために、現在の場所において最左車線へと移動すべきである。しかしながら、運転者は、多数の車両４１１が、交差点４０２において左折を行なっており、その方向転換移動のために停滞している行列が存在する場合、第１の交差点４０２を通過するまで、車線変更を遅延させ得る。車線レベルナビゲーションシステムおよびそのサポートデータベース、適切な車線レベル状況において、本渋滞のパターンを認識し、ある運転者挙動を認知し、車線レベルにおいて経路を最適化し、運転者を適宜案内することが可能である。
【００４５】
道路タイプ、車線数、道路の地理、ならびに交通信号および標識の存在に基づいて、本発明の実施形態は、自動的に、典型的都市交差点およびフリーウェイ中継地点構成における車線接続を生成することができる。自動的に生成された車線接続の結果は、有効化され、さらに必要に応じて、測量データ、航空画像、および車両軌道データを使用して、改訂されることができる。実施例として、図５は、交差点４０３における車線接続をより詳細に図示する。交差点の内側の矢印ヘッドを伴う湾曲線は、車線コネクタと呼ばれる。車線コネクタは、幾何学配列および車線間の許可された移動を示す。説明される車線レベルデータベース内の特徴として、車線コネクタは、特定のコネクタを使用する運転者の傾向または確率を示すデータの記憶をサポートする。示されるように、実線車線コネクタ５０１は、破線車線コネクタ５０２より一般に使用される。
【００４６】
図６は、予想車線変更の別の実施例６００を示す。本実施例は、アクセス制限高速道路６０１を伴う。東行出口ランプ６０２は、下流交差点６０３の容量を超える交通量のため、停滞する車両の行列６１２を有する。次の出口ランプ６０４を辿ることを意図する運転者（そうでなければ、出口ランプ６０２の前に右に移動したであろう）は、特に、出口ランプ６０４が、さらに下流にある、または出口ランプ６０４への複数の車線コネクタが存在する場合、出口ランプ６０２に形成されている行列６１２に加わるのではなく、中央および左車線６０５、６０６を使用するように助言され、それによって、不必要な行列を回避し、より短い走行時間を享受するであろう。一方、最適かつ意図されるルートを逃す確率がより高い（例えば、出口ランプ６０４が、出口ランプ６０２に非常に近いため）、または代替ルートの使用のコストが過剰である場合、より早期の車線変更が、行列６１２に加わることをもたらす場合でも、最良行動方針を構成し得、運転者に推奨されるであろう。
【００４７】
車線レベルナビゲーションシステムの要素の１つは、車線レベルルートオプティマイザの含有であり、これは、リンクレベルオプティマイザに加え、またはその代わりに、使用されることができる。起点、目的地、ならびに車両タイプおよび選好（例えば、相乗り車両（ＨＯＶ）、車対トラック、時間の価値等）を前提として、リンクレベルオプティマイザは、起点および目的地を接続するリンクシーケンスのサブネットワークまたは事実上の「ハンモック」によって表される、候補経路を計算する。ハンモックは、起点または車両の現在の位置における単一リンクから発生し、目的地における単一リンクで収束する、リンクおよびノードのネットワークであると考えられ得る。所定の先読み閾値（選好）に従って、車線レベルオプティマイザは、車線レベル交通密度および速度の履歴測定またはマイクロシミュレーションのいずれかを使用して、経路候補上の走行時間、遅延、および運転体験を評価する。本評価の結果は、次いで、車線レベルルート案内を導出するために使用され、ある（例えば、車線変更操縦のいずれも、可能ではない、または望ましくない）場合にはまた、リンクレベルオプティマイザを起動し、改訂された基準に従って、経路候補を再計算してもよい。車線レベルオプティマイザによって採用されるマイクロシミュレーションでは、交差点の内側の車両軌道および対立同様に、下流交差点における交通信号（適応交通信号であってもよい）（および、例えば、メッセージ標識および他の運転者情報システムを含む、他の交通制御）が、交差点遅延を現実的に判定するためにシミュレートされる。いくつかの実施形態では、起点、目的地、ならびに車両タイプおよび選好、ならびに任意の他の入力が、リンクレベルオプティマイザを全く使用せずに、直接、車線レベルオプティマイザに打ち込まれることができることに留意されたい。
【００４８】
ナビゲーションエンジン７００は、図７における略図に図示されることができる。ナビゲーションエンジン７００では、履歴速度データ７０１が、地域全体のネットワーク（４）を表す、地理的データベースおよびモデル７０２を取り込むために使用される。データベース内の記録は、説明されるような道路区画、車線、および車線コネクタを表す。履歴速度データ７０１とともに、ネットワークは、交通流および渋滞の時間ならびに空間的パターンを確立するために使用される。既知の交通信号タイミングおよび管理データ７０３と、履歴データ（例えば、交通数）を使用して測定または較正のいずれかが行われる、走行需要７０４の推定もまた、ネットワークモデルとともに記憶され、シミュレーションを実行するために使用される。加えて、携帯電話、検出器、およびカメラからの速度測定を含む、リアルタイムデータ７０５と、例えば、交通管理センターからの事故報告およびタイミングデータ７０６も、現在の情報をネットワークにフィードするために使用される。
【００４９】
履歴およびリアルタイム情報を使用した地域全体のネットワークの車線レベルモデル７０２を用いて、正確な動的交通割当およびシミュレーションが、７０７において実行され、走行時間および方向転換移動遅延７０８の予測を産生し、これは、順に、リンクレベルルートオプティマイザ７０９を駆動する。走行車の起点をその目的地に接続するハンモック７１０によって表される、一式の代替リンク経路が、オプティマイザ７０９によって産生される。一実施形態では、一式の車線グラフ７１１が、走行車のために展開される。理想的には、車線グラフは、最適リンクルートの全体を包含するが、計算リソースが十分ではない場合、車線グラフは、示されるように、先読み範囲に限定されてもよい。
【００５０】
車線グラフに基づいて、最適車線経路は、車線レベルオプティマイザ７１２において産生され、車線変更および方向転換移動ルート案内命令７１３の形態において、走行車に伝送される。走行車が、７１４において、車線を変更する場合、エンジン７００は、７１５において、車両が、依然として、車線グラフによって最適車線経路に接続されると見なされる一式の車線内にあるかどうかを判定する。走行車が、依然として、「接続された」車線内にある場合、車線レベルオプティマイザ７１２は、現在の車線に基づいて、命令を走行車にアップデートする。そうでなければ、エンジン７００は、リンクレベルオプティマイザ７０９に戻る。
【００５１】
７１６において、走行車が新しい道路区画に移動したことが検出されると、エンジン７００は、７１７において、走行車が現在の助言されているリンク経路上の道路区画上にあるかどうかを判定し、そうである場合、車線グラフ７１１は、ネットワーク内の新しい位置を反映させるようにアップデートされる。そうでなければ、エンジンは、リンクレベルオプティマイザ７０９に戻る。このように、地域全体のネットワークに関連した走行車の場所は、エンジン７００によって継続的に追跡され、リンクレベルオプティマイザ７０９および車線レベルオプティマイザ７１２と結合されるシミュレーションを使用して、走行車を案内する。
【００５２】
リンクレベルオプティマイザ７０９が省略される、ある実施形態では、全てのリンクレベルおよび車線レベル計算は、車線レベルオプティマイザにおいて行われる。これは、車線または区画変更に基づいて要求される任意の再計算を含む。
【００５３】
ナビゲーションエンジン７００では、可能性として考えられる車線レベル軌道が、所定の先読み範囲内のルートの一部のみのための可変サイズの車線レベルネットワークまたはグラフを構築することによって、代替ルート上の下流の車線内の交通を先読みすることにより評価されるが、また、潜在的に、利用可能な計算および／または通信容量が可能である場合、ある場所から車両の目的地までの全車線レベル経路を検討することができる。
【００５４】
車線レベルネットワーク（別様に、車線グラフとして知られる）は、道路ネットワーク内の車線使用規制、車線変更、および車線配列に関する詳細情報を表すためのモデルである。具体的には、車両移動の車線レベルナビゲーションおよびマイクロシミュレーションをサポートするために設計される。車線グラフの設計は、図８に示されるように、簡略化された実施例によって最も良く示されることができる。
【００５５】
図８は、１０の道路区画を含む、ある範囲の東行フリーウェイ８００を示す（長さは、正確な縮尺ではない）。本実施例では、区画８０１−８０７は、フリーウェイであり、区画８０８および８０９は、出口ランプであり、区画８１０は、入口ランプである。２つの最左車線は、相乗り（ＨＯＴ）専用に制限されるように指定され、ＨＯＴと一般（ＧＰ）車線との間の車線変更は、区画８０１内では可能であるが（破線によって示される）、区画８０２−８０７では、禁止される（第２および第３の車線８１１、８１２間の実線によって示される）。ＨＯＴ運転者は、全車線を使用してもよいが、運転者が使用すべき車線は、その目的地および選定されるルートに依存し得る。一方、障壁および／または車線変更規制の存在のため、運転者がとるべきルートもまた、現在いる車線に依存する。最適車線レベル経路はさらに、ＨＯＴおよびＧＰ車線上の交通状況に依存する。本発明の車線グラフモデルは、車線レベルオプティマイザの動作を効率化するために設計される。
【００５６】
実施例として、図９は、区画１の上流を走行中の運転者のための車線グラフ９００の一部である。グラフは、頂点（車線を表す）および縁（車線間の関係を表す）を含有する。運転者が、本線を通して、出口１（８０８）、出口２（８０９）、またはさらに下流に進行しているかどうかに応じて、車線を表す頂点のいくつかは、トリミングされる（例えば、運転者の意図されるルートから除去される）ことができる、またはより多くの頂点が、追加されることができる。
【００５７】
図９の車線グラフ９００では、各頂点（円形）は、具体的道路区画内の車線を表す。黒色頂点９０１は、ＨＯＴ車両に対して制限された車線である一方、他の頂点９０２は、車線使用制限がない車線を表す。
【００５８】
対の頂点間に二重矢印を伴う垂直線９０３は、近隣車線間の車線変更操縦を表す。車線変更が、一方向のみ（例えば、右／左ではなく、左／右、またはその逆）に許可される場合、単一矢印が、一対の隣接する車線間に描かれるであろう。
【００５９】
車線グラフ９００内の各水平または対角線９０４は、ネットワーク内の車線コネクタを表す。車線コネクタは、上流車線と下流車線との間の配列を説明する。２つ以上のそのような線９０４が、複数の上流車線頂点を下流車線頂点に接続する場合、合流を表す。２つ以上のそのような線９０４が、上流車線頂点を複数の下流車線頂点に接続する場合、車線分割（すなわち、分岐）９１４を表す。
【００６０】
各線９０４上の番号（１または０）は、車線変更操縦に割り当てられるコストを表す。これらのコストが割り当てられることによって、運転者の現在の位置から任意の下流リンクまでの車線レベル経路の計算は、非常に確立された最短経路アルゴリズムによって行われることができる。経路の最小コストは、その現在の経路上にとどまるために、運転者に要求される最小数の車線変更を与える。最短経路に沿った各頂点の先行点を追跡することによって、車線変更が生じるべき場所および現在の位置からのその距離が判定されることができる。車線グラフ９００上に深度優先または幅優先の探索法等の技法を適用することによって、現在の位置（すなわち、起点）から選定される下流目的地までの代替車線経路が、列挙されることができる。
【００６１】
同様に、グラフ内の車線のための走行速度、遅延、交通密度、および車両間の間隙が、グラフ内の車線頂点のための属性として記録されることができる。車線変更操縦の可能性および困難点は、グラフ内の近隣車線を接続する、縁の属性によって表されることができる。検索技法は、したがって、候補車線経路に沿ったコストおよび運転体験を評価し、要求される車線変更を開始するために最適場所を選択するために、車線グラフ上で行われることができる。
【００６２】
本フレームワークでは、現在の位置までの車両の走行記録を表すもの、または前述の技法から導出された車線レベル案内を表すもののいずれかである、車線経路は、地理的座標および事象によって、またはデータトリプレットのシーケンスによって表されることができる。各データトリプレットは、（１）一意の道路区画識別子（すなわち、車線グラフ内の頂点の行）と、（２）区画内の車線位置指数（すなわち、車線グラフ内の頂点の列）と、（３）車線のいずれかの端点からの相対的距離の観点から表される、車線変更の位置とを含有し得る。運転者への推奨のための車線経路を策定するとき、距離は、車線変更が助言される場所を反映し、車線変更が完了されるべき前の快適な間隔を可能にする。助言車線変更位置は、所与の位置における車線変更の難度を特徴付けるために使用される、現在または履歴速度データから導出されることができる。案内を提供するとき、データトリプレットは、地理的座標および事象通知に変換され、車両の現在の場所に関するリアルタイムＧＰＳ情報と協調されることができる。
【００６３】
車線変更（または、車線変更が行なわれるべきではないとき、現在の車線内に留まる作用）は、義務的なものと、自由裁量のものの２つのタイプであると考えられ得る。義務的車線変更は、リンクレベルで定義される所与のルート上に残るために要求される方向転換を行うために、車線変更が行なわれなければならない場合を指す一方、自由裁量の車線変更は、速度を加速する、または重量車両を通過させる等、運転体験を改良するための車線変更操縦を指す。複数の車線接続が存在するとき、義務的車線変更は、自由裁量の車線変更の選択肢セット（すなわち、代替軌道経路）を減少させ得る。
【００６４】
さらに、２つのタイプの自由裁量の車線変更を区別することができる。これらのうちの第１のものは、リンクまたはリンク区画およびその中の車線の即時の状況あるいはすぐ下流におけるものに基づく。これは、車両をリンクシーケンスによって定義されるそのルート上に保ちながら、車線を選択する、短先読みプロセスを有する、公知のシミュレータに対応する。本タイプの自由裁量の車線変更では、決定は、本質的に、短絡的であり、各ルート区画内またはおそらくいくつかの下流リンク上で利用可能な代替車線に基づく。
【００６５】
第２のタイプの自由裁量の車線変更は、ルート戦略的であり、車線選択および車線変更のための場所の戦略的選択肢に焦点を当てることによって、ルートの残りまたは他の有意な部分のための走行時間または他の性能指数を改良する目標を有する。本プロセスは、車線グラフ内の車線頂点および縁を追加および除去することによって行われる。また、システムが、どの挙動シナリオが車線レベル軌道の観点から優れているかを学習するにつれて、複数回のシミュレーション実行の過程にわたって調節されることができる。
【００６６】
異なる車線変更場所と関連付けられた遅延の減少および速度の加速はさらに、車両ナビゲーションシステムおよび最短経路アルゴリズムの当業者に周知の方法を使用して、最良車線レベル経路を計算する際に検討されることができる。これらは、リンクまたはリンク区画内の場所に特定化され、確率的予期される走行時間および車線変更確率を検討することができる。
【００６７】
履歴測定およびリアルタイム測定からのデータの組み合わせに基づいて、多数回のシミュレーション実行が、車線レベルにおいて、代替経路に沿って可能性の高い走行時間および交通密度を合成および予測するために使用されることができる。これらのシミュレーション実行の結果は、次いで、処理され、異なる車線レベルルート指定および推奨される車線変更場所のための可能性の高い走行時間を評価するために使用される。車線変更は、具体的場所において保証されることができないため、ナビゲーション推奨は、推奨される車線変更を試みるべき第１の場所を含むことができる。ナビゲーション命令はまた、事前に、車両のために推奨される、一式の車線操縦を説明することができる。
【００６８】
推奨されるルートは、車両の時間および場所に基づいて、動的に判定され、したがって、車両の進路の持続時間の間に存在し、体験されるであろう、交通状況のために最適化されることができる。したがって、事故および工事区域も、ナビゲーション案内に考慮されることができる。
【００６９】
予測機能およびシミュレーションは、車両がその進路の今後の部分において見出すであろう状況をより正確に表すため、履歴またはさらにリアルタイム状況の使用より優れた、かつそれを上回る能力を提供する。
【００７０】
リンクレベルオプティマイザ７０９および車線レベルオプティマイザ７１２によって使用されるシミュレーションエンジンは、最大速度、車線選好、ルートの単純性、時間の価値、望ましい到着時間枠、ならびに、該当する場合、車線使用制限および通行料に関連付けられた車両分類のためのものを含む、運転者選好を反映するようにカスタマイズされることができる。シミュレーションエンジンはまた、存在する場合、適応交通信号最適化を考慮することができる。
【００７１】
リンクレベルオプティマイザ７０９は、リンクレベル代替ルートを生成する。これは、運転者の現在の位置から所望の目的地までの複数の代替ルートを提供することができる。これらの代替ルートは、リンクの指向性シーケンスのサブネットワークまたは「ハンモック」として策定されることができる。選定されるルートのために、案内される車両が、ある道路区画から次の道路区画に移動する、または車線を変更するにつれて、先読み範囲内のルートに沿ったリンクの下流部分は、次いで、前述のように、車線レベルネットワークまたはグラフ７１１に拡張される。車線レベルオプティマイザ７１２は、可能性として考えられる車線レベル軌道を生成するために使用される。これらの車線レベル代替経路は、次いで、評価され、事前設定ルールおよび基準に基づいて、最適なものを判定する。
【００７２】
代替ルートが最初に判定されることによって、車載ナビゲーションデバイスと遠隔サーバとの間の通信は、最小限に保たれることができる。これは、ナビゲーションエンジン７００が、車線状況および行列に関するリアルタイムデータフィードと相互作用し、適応ルート案内を与えることを可能にする。
【００７３】
複数回のシミュレーション実行はさらに、任意のルート推奨のロバスト性を精緻化または確立するために利用されることができる。これらのシミュレーション実行は、所与のルートが予期される最小時間内に横断可能な尤度の概念を与えることができる。単一車両進路のための最良ルートを選定するために、シミュレーションは、現在の状況下における可能性の高いシナリオを評価し、効果的代替の範囲を提供することができる。動的交通割当（ＤＴＡ）およびシミュレーションが、サーバ側または遠隔分散型コンピューティング環境内で行われ、ネットワーク状態を推定し、信頼性ならびに予期される走行時間を検討することができる。履歴速度プロファイル、速度および走行時間のリアルタイム測定、交通管理および制御に関する情報、および走行需要推定および交通事故は全て、ネットワーク状態推定器および予測器にフィードされ、地域全体のネットワーク内の現在および今後の速度、走行時間、ならびにリンクおよび方向転換移動に関する遅延を判定するために使用される。
【００７４】
概して、動的ユーザ平衡交通割当モデルが、交通をモデル化するために使用されてもよい。本公式化では、反復毎に、車両が、ネットワーク上の時間周期別の以前の反復予測走行時間に最も良く基づく、その最良経路を選定するように、反復解が計算されてもよい。計算された近似平衡解において、時間間隔別のネットワーク上の走行時間は、変更を停止し、ルート選択肢は、したがって、安定化するであろう。好ましい実施形態では、マイクロシミュレーションベースのＤＴＡが、ルートおよび車線レベルナビゲーション案内を提供するために使用されるであろう。これは、所与の出発時間において、具体的起点と具体的目的地との間を進行する単一車両のための最良軌道の識別から導出されるであろう。また、種々の事象が、事故あるいは道路建設または保守のための道路修正等の最良車線レベル軌道のシミュレーションおよび計算に計上されることができる。シミュレーションは、同時に測定されることができない、または履歴から把握されることができない、今後の影響を組み込むことを可能にする。
【００７５】
車線減少ならびに予期しない事故および工事区域は、渋滞の増加につながる。説明されるシステムは、交通シミュレーションを使用して、事象（事故および工事区域）の上流の交通状況および遅延量を推定する。個人の運転体験を最適化するだけではなく、これらのボトルネックにおける処理量を増加させるために利用可能な容量をより良好に利用する、車線変更の最適位置を判定するために、運転者を案内する。車線レベル交通管理は、事故を減少し、かつ車両交通と関連付けられた遅延およびエネルギー消費を減少させることによって、公共の安全性を改良する潜在性を有する。
【００７６】
車線レベル案内は、リンクレベル最短経路からの差異につながり得る。これは、障壁が車線間に存在する、または要求される車線変更の数が多すぎて、利用可能な距離内の一般的速度で安全に操縦できない、前述の実施例において明確に明らかであるが、寄与要因が、交通パターンおよび車線を横断する交通状況の差異であるときは、あまり明白ではない。リンクレベルでは、経路計算は、ある種類の走行時間の平均または一般化コストに関して行われる必要がある。しかしながら、交通流内の車両は、多くの場合、異なる目的地に走行しており、道路区画を横断する交通密度および車線利用は、必ずしも、均一または均衡化されない。さらに、運転者の時間の価値および遅延の知覚は、異なり得る。したがって、「平均」運転者にとっての平均走行時間、方向転換遅延、および／または一般化コストに基づく最短経路は、必ずしも、具体的運転者にとって最適経路ではない場合がある。説明されるシステムでは、運転者のナビゲーションの個性のニーズが、車両の場所および車線を横断した可変交通状況を考慮することによって、明示的に検討される。
【００７７】
すでに利用可能な多くのルート案内システムと同様に、説明されるシステムは、リンクレベルルート計算を含んでもよい。しかしながら、ここでは、その計算は、広域内のルート候補をスクリーニングするための最初のステップにすぎない。計算はまた、データ縮小ステップとしての役割を果たし得、したがって、より詳細な車線レベル経路評価が、計算および通信要件が最小限にされるように、はるかに小さいデータセットのためだけに必要とされる。
【００７８】
ある特定の実施形態では、予期される走行時間が、使用および最小限にされるが、進路の他の側面も、最適化される対象に含まれ得る。このようなものとして、限定ではないが、ある道路または車線の使用あるいは制限エリアへの進入のために被られる料金、車線変更が行われなければならない要求される車線変更数および残りの距離、制御される回数（例えば、信号機、一時停止標識制御）交差点、駐車車両の存在、横道および車道から進入してくる、およびそこへと出て行く車両、ならびに歩行者交通の分布率が挙げられる。
【００７９】
ＧＰＳシステム、レーザおよびレーダ測距装置、マイクロ波、画像処理、および物体認識の正確度の改良は、車線内および交差点内の場所において、車両を確実に測位する能力を提供し得、説明されるようなナビゲーションエンジンをフィードするために使用され得る。より低いコストを伴うワイヤレス通信の容量の拡張は、説明されるシステムが、ナビゲーションのための場所特異的交通データおよび要求を中央サーバに送信し、シミュレーションを使用して、交通予測を実行し、個々ベースで最適化された車線レベル経路およびナビゲーション命令を生成することを可能にし得る。
【００８０】
シミュレーションおよび車両ルート指定は、車線レベルであるため、交通コントローラが、遅延、処理量、停止回数、および青信号に到着する車両の割合等の予測される性能測定値に基づいて、信号タイミング、位相化、および協調の最適化を行うことを可能にすることができる。そのような最適化は、説明される方法を利用するソフトウェアを使用してオフラインで、または接近車両とのリアルタイム通信を介したオンライン信号最適化および車両到着パターンの推定を行う、コントローラ内の構成要素によってのいずれかで、行われてもよい。
【００８１】
説明される車線レベルルート指定方法はまた、自己運転自動化車両が、適切な車線変更決定を行うのを補助してもよい。所定の経路を使用するのではなく、自動化された車両は、継続的に、その代替車線経路を評価し、最適ルートを選定し、規定された経路上に留まるために必要車線変更を行うことができる。
【００８２】
ナビゲーションエンジンは、インターネットを経由して結果をサーブするコンピュータのクラスタ上、車載コンピュータ上、専用ナビゲーションデバイス上、スマートフォン上、または開発され得る他の類似対応コンピューティングデバイス上で様々に実行されてもよい。複数のインスタンスの同時実行は、より高速かつより良好な予測をもたらし得る。
【００８３】
微視的シミュレーションが、車線レベル性能およびルート指定を提供するために使用されるが、ネットワークのいくつかの部分は、より粗い巨視的または中間視的または微視的手段とのハイブリッド組み合わせによってシミュレートされ得る。関わる計算負荷のため、シミュレーションは、典型的には、マルチスレッド型およびまた分散型であろう。車両移動のシミュレーションおよびネットワーク状態アップデートのマルチスレッド化は、全アクティブスレッドが、相互に隣接しない処理ノードであり、最大数のスレッドが、機能されるように、ノード隣接マトリクスを使用して、タスクを各スレッドに割り当てることによって、改良されることができる。本方法は、共有データ項目の書込アクセスのために必要とされるスレッドのあるロックを回避する。図１０における略図に示されるように、白色ノード１００１が、８つのスレッドによってアクティブに処理されているものである場合、これらのスレッドによって管理される車両移動は、場所特異的変数のアップデートをロックせずに、安全に行われることができる。本方法はまた、任意のフリースレッドがすぐに機能されるため（ネットワークが、利用可能なスレッドの数と比較して小さすぎない、および処理のために準備ができた非隣接ノードが存在しない限り）、スレッド間で作業負荷を均衡化するのに役立つ。
【００８４】
シミュレーションはまた、ネットワーク分解に基づいて、複数のコンピュータのクラスタに分散されることができ、これは、サブネットワーク間の境界リンクの数を最小限にし、クラスタ内のコンピュータ間の負荷を均衡化する。サブネットワークに関与する各コンピュータ上のスレッドロックを最小限にし、かつ地域全体のシミュレーションを共同して行うコンピュータ間の要求される通信の量を制限することによって、ネットワーク状態推定および予測のオンタイム計算性能が、達成されることができる。交通測定およびネットワーク事象が、リアルタイムで生じるため、本システムは、ローリングホライズン方式で動作する。５、１０、１５、または３０分毎に、新しい測定および事象データが利用可能となるにつれて、コンピュータの新しいクラスタが、次の時間周期のためのネットワーク状態推定および交通予測を行うためにアクティブ化される。図１１における略図は、コンピュータの３つのクラスタ１１０１、１１０２、１１０３が、どのように順番に交替し、異なる時間周期のための分散型走行時間推定および交通予測を行うかを図示する。クラス内の各コンピュータは、ネットワーク分解に基づいて、ネットワークの一部をシミュレートする。
【００８５】
いったん新しい一式のネットワーク状態推定および交通予測が、利用可能となると、リンクレベルルートオプティマイザは、加入運転者のために機能される。リンクレベルルートオプティマイザは、各運転者の現在の位置からその所望の目的地までの現在の時間における代替ルートを計算する。前述のように、代替ルートは、指向性リンクのシーケンスのサブネットワークとして、またはハンモックとして説明されることができる。個々の運転者の具体的選好に基づいて、これらの代替ルートは、性能測定値を計算し、現在の状況に基づいて、ルート案内を提供するために評価される。
【００８６】
所望のルートまたは一式の代替ルートを前提として、車線グラフが、先読み範囲内のルートの一部のために構築されてもよい。これは、より詳細なマイクロシミュレーションが行われ、データが、ネットワークのはるかに小さく、かつ選択されたエリアのためだけに組み立てられることを可能にする。車線レベル経路オプティマイザのタスクは、したがって、代替軌道または車線経路を評価し、走行時間および遅延を推定し、運転体験の指数を計算することである。最良代替が、次いで、ナビゲーション案内として推奨される。
【００８７】
車線変更は、最適な所望の場所において、常時、可能であるわけではない。車線変更は、走行の速度および運転者の積極性に適切な標的車線内の好適な間隙の存在を要求する。説明されるシステムは、車線変更の困難点を査定し、測定または予測される車線占有率に基づいて、早期または後の車線変更を推奨することができる。車線変更が、早期または後に推奨されるべきかどうかは、ユーザ定義されることができる。具体的ユーザの運転習慣からの自動化された学習が、ナビゲーション案内が運転挙動および期待に合わせられるであろうように、システム内に含まれる。
【００８８】
ルート案内およびシミュレートされる交通内の一貫性は、拡張または修正を伴わずに、利用可能な技法によって容易に達成可能でない場合がある。動的（時間依存）最良経路計算では、今後の時間間隔におけるリンクまたは車線走行時間の推定が、要求される。しかし、これらは、以前にシミュレートされる交通状況から得られる場合であっても、それらの推定は、不備がある、またはルート案内が最初に産生され、後にアップデートされる状況および時間と一貫しない場合がある。
【００８９】
車線レベル案内の検証は、マイクロシミュレーションを行い、結果を査定することによって検証されることができる。
【００９０】
本発明の実施形態の特定の用途は、緊急対応車両のルート指定におけるものである。緊急対応の状況では、交通流内の車両の通常運転挙動は、緊急対応車両のサイレンおよび視覚的検出に対するその応答によって改変される。これらの応答および挙動順応性は、随時、観察されることができるが、具体的結果は、道路幾何学形状および交通レベルに依存し、これらは、マイクロシミュレーションを用いてシミュレートされることができる。同様に、緊急車両自体のための交通シミュレーションにおける挙動モデルは、可能な限り迅速にその目的地に到達するためのその標的速度と、反対方向に車線を使用し、交通信号を敢えて無視する能力とを反映することができる。ここでも、車線レベルルート指定戦略は、最短リンクレベルルートの運転者の従来の知識を優に上回り、さらなる時間利点につながり得る。同様に、これらのシステムおよび方法は、緊急の場合の避難ルートを判定するために使用されることができる。運転者挙動のためのモデルは、運転者が、避難状況下、公共に提供される案内に応答して、どのように挙動するか、または挙動し得るかを反映するように修正されることができる。
【００９１】
車線レベルルート指定の別の用途は、商業サービスまたは配達車両、また、除雪車およびゴミ収集車のためのものである。これらの車両は、異なるサイズおよび性能特性を有し、多くの場合、合法的および違法に駐車させた車両を有する道路区画をナビゲートする必要があり、これは、必然的に、その車線および停止場所の選択肢に影響を及ぼすであろう。
【００９２】
２地点間配達動作とは対照的に、街路区画群全体が横断されなければならない、郵便配達およびゴミ収集のために適切なもの等の円弧ルート指定が既知の場合、ある車線選択肢が、要求され、自由裁量ではないであろう。これは、停止挙動および具体的配達または収集活動のシミュレーションを含む、交通マイクロシミュレーションにおいて対応されることができ、これは、最終的には、各車両に対するより良好かつより現実的作業負荷の配分および割り当てられたタスクを行うために要求されるより良好かつより現実的時間の推定につながり得る。
【００９３】
除雪の場合、車線レベルルート指定は、決定が主要道路上の少なくとも１つの車線を開放するように行われ得るため、さらに効果的となり得、車両毎の車線レベルの全体的ルート計画および軌道の選択肢は、より専門的に計画、シミュレート、および行われることができる。同様に、除雪ルートは、より小さい道路を完全に見逃すことを回避するように設計されることができる。
【００９４】
商業および公共車両のこれらのルート指定の全ての場合において、他の交通および駐車車両の存在は、車線レベルおよび車両レベル詳細を欠いている従来のルート指定システムより適切に表されることができる。
【００９５】
説明されるタイプの微視的交通シミュレーションは、個々の車両のための車線レベルナビゲーション案内を提供することができるが、また、交通管理のための改良された能力をもたらす。交通管理では、戦略は、交通流を平滑化するために実装される。これらの戦略は、種々の状況のために与えられる、またはリアルタイムおよび起こりつつある状況に応答することができる。
【００９６】
交通管理戦略に関して、単一車両のための性能を改良することに焦点を当てることは不十分である。メッセージ標識および他の通信を通して交通管理情報を複数の車両に提供することは、容易に行われることができるが、効果的戦略の査定は、運転者が、起こりつつある交通状況およびそれらの状況に関する新しく提供される情報に合わせるにつれて、より複雑な分析を要求する。ネットワーク上のある形態の平衡状況を判定する、地域全体の動的交通割当は、必要とされる予測を提供し、通行料徴収および動的道路課金等のより高度な手段を含む、交通管理戦略における変動を評価するために使用されることができる。
【００９７】
説明されるシステムは、無料公共システムによって、または交通情報およびルート案内を加入者に販売するプライベートサービス提供者によって、予想走行時間を推定するためのエンジンとして使用されることができる。ユーザが、走行時間情報およびルート案内にどのように応答するかを収集することによって、本システムは、システムが、よりデータを蓄積し、ユーザの応答から経時的に学習するにつれて、ルート案内がより正確となるであろうように、そのパラメータを調節するための自己調整構成要素を含むことができる。
【００９８】
本システムはまた、全体的交通環境に応答する、バスのための車線レベルルート指定戦略を選択することによって、バスシステムの性能を改良するために使用されることができる。多くの場合、設計または意図上、車線レベルである、バス優先および／または信号専有戦略もまた、容易に組み込まれることができる。他の走行モードもまた、組み込まれ、車線レベル案内をそれらのために計算させることができる。
【００９９】
したがって、車線レベル車両ルート指定およびナビゲーション装置ならびに対応する方法が、提供される。当業者は、本発明は、説明される実施形態以外によっても実践されることができ、例証目的のために提示され、限定ではなく、本発明は、以下の請求項によってのみ限定されることを理解するであろう。
【図１】
2016513805.tif 000003
【図２】
2016513805.tif 000004
【図３】
2016513805.tif 000005
【図４】
2016513805.tif 000006
【図６】
2016513805.tif 000007
【図９】
2016513805.tif 000008
【図１０】
2016513805.tif 000009
【図５】
2016513805.tif 000010
【図７】
2016513805.tif 000011
【図８】
2016513805.tif 000012
【図１１】
2016513805.tif 000013
【国際調査報告】
2016513805.tif 000014
2016513805.tif 000015