運転者にとって好ましい経路を選択して表示する方法、装置及びコンピュータプログラム
【課題】運転中の頻繁な経路変更を抑制し、効率的に最適な経路を選択することができ、運転者にとって好ましい経路を選択して表示する方法、装置及びコンピュータプログラムを提供する。
【解決手段】出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出しておく。算出した動的戦略に基づいて、交差点ごとの所要時間に関する確率分布、及び所要時間に依存して選択するべき進行方向を算出する。所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する。交差点ごとに、進行方向ごとの所要時間の確率を加算して、加算して合計した確率が一番高い進行方向を順次選択しても良い。
【解決手段】出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出しておく。算出した動的戦略に基づいて、交差点ごとの所要時間に関する確率分布、及び所要時間に依存して選択するべき進行方向を算出する。所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する。交差点ごとに、進行方向ごとの所要時間の確率を加算して、加算して合計した確率が一番高い進行方向を順次選択しても良い。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路の変更頻度を減少させつつ、運転者にとって好ましい経路を選択して表示する方法、装置及びコンピュータプログラムに関する。
【背景技術】
【０００２】
昨今のカーナビゲーションシステムは、経路選択アルゴリズムに様々な工夫が施され、運転者にとって最適な経路を選択して表示することができるようになっている。例えば特許文献１乃至４には、静的な情報に基づいて運転者にとって最適な経路を選択するカーナビゲーションシステムが開示されている。また、システムによっては、静的な情報に基づく複数の経路候補を表示して、表示された経路候補の中から運転者に選択させて最適な経路を表示するシステムも開示されている。
【０００３】
また、静的な情報だけではなく、将来起こり得る事象の確率分布を用いて経路選択する技術も開発されている。例えば非特許文献１及び２では、プローブカーデータ、定点観測データ等を取得し、移動（走行）時間の不確実性（確率分布）、あるいは将来の渋滞予測等の動的な情報を用いて、より最適な経路を選択するシステムが開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−１９００９１号公報
【特許文献２】特開２００２−２８６４８０号公報
【特許文献３】特開２００３−３３７０３６号公報
【特許文献４】特開２００５−０３７２４６号公報
【特許文献５】特開２００７−２５５９１９号公報
【特許文献６】特開２００８−０７７６３６号公報
【特許文献７】特開２０１０−０７２９８６号公報
【特許文献８】特許第３０１２０９６号公報
【特許文献９】特許第３１９３４７９号公報
【非特許文献】
【０００５】
【非特許文献１】キュー・ウー、ジェイ・ハートレイ、ディー・アル−ダバス：タイム−ディペンデント ストカスティック ショーテスト パス、アイ・ジェイ オブ シミュレーション、第６巻、７−８番、２００５年（Ｑ．Ｗｕ，Ｊ．Ｈａｒｔｌｅｙ，Ｄ．Ａｌ−Ｄａｂａｓｓ：Ｔｉｍｅ−Ｄｅｐｅｎｄｅｎｔ Ｓｔｏｃｈａｓｔｉｃ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ（ｓ）．Ｉ．Ｊ． ｏｆ Ｓｉｍｕｌａｔｉｏｎ，ｖｏｌ．６，Ｎｏ．７−８ ２００５）
【非特許文献２】イー・ディー・ミラー、エイチ・エス・マーマッサーニ、エイ・ジリアスコパラス：パス サーチ テクニックス フォー トランスポーテイション ネットワークス ウィズ タイム−ディペンデント、ストカスティック アーク コスト 、アイイーイーイー インターナショナル カンファレンス オン システムズ、マン アンド サイバネチックス：ヒューマンス、インフォメーション アンド テクノロジー、１９９４年（Ｅ．Ｄ．Ｍｉｌｌｅｒ、Ｈ．Ｓ．Ｍａｈｍａｓｓａｎｉ，Ａ．Ｚｉｌｉａｓｋｏｐｏｕｌｏｓ：Ｐａｔｈ ｓｅａｒｃｈ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ｔｉｍｅ−ｄｅｐｅｎｄｅｎｔ， ｓｔｏｃｈａｓｔｉｃ ａｒｃ ｃｏｓｔｓ． ＩＥＥＥ Ｉｎｔ． Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｙｓｔｅｍｓ，Ｍａｎ， ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ：‘Ｈｕｍａｎｓ，Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ’ １９９４）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、特許文献１乃至４のように、静的な情報に基づいて選択した経路を表示する場合、出発時には交通渋滞がなかった道路において、通過時に交通渋滞が発生しやすい時間帯に入り、あるいは実際に交通渋滞が発生した場合、経路を再探索することにより経路の変更が頻繁に生じるおそれがあった。経路の変更は運転者にとってはストレスであり、経路の変更が頻繁に生じることで、結果として非効率的な経路選択になってしまう可能性も否定することができない。
【０００７】
また、動的な情報に基づいて選択した経路を表示する場合であっても、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示して運転者に理解させることは困難であるので、結局は静的な情報に基づく経路候補の中から最適な経路を選択している。したがって、経路の変更が頻繁に生じる場合、非効率的な経路選択になっている場合等も生じうる。
【０００８】
本発明は斯かる事情に鑑みてなされたものであり、運転中の頻繁な経路変更を抑制し、効率的な経路を選択することができ、運転者にとって好ましい経路を選択して表示する方法、装置及びコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために第１発明に係る方法は、運転者に経路を選択して表示する装置で実行することが可能な方法であって、出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する工程と、算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する工程と、前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する工程とを含む。
【００１０】
また、第２発明に係る方法は、第１発明において、前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する工程を含み、加算して合計した確率が一番高い進行方向を順次選択する。
【００１１】
次に、上記目的を達成するために第３発明に係る装置は、運転者に経路を選択して表示する装置であって、出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する動的戦略算出部と、算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する進行方向算出部と、前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する交差点決定部とを備える。
【００１２】
また、第４発明に係る装置は、第３発明において、前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する確率加算部を備え、前記交差点決定部は、加算して合計した確率が一番高い進行方向を順次選択する。
【００１３】
次に、上記目的を達成するために第５発明に係るコンピュータプログラムは、運転者に経路を選択して表示する装置で実行することが可能なコンピュータプログラムであって、前記装置を、出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する動的戦略算出手段、算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する進行方向算出手段、及び前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する交差点決定手段として機能させる。
【００１４】
また、第６発明に係るコンピュータプログラムは、第５発明において、前記装置を、前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する確率加算手段として機能させ、前記交差点決定手段を、加算して合計した確率が一番高い進行方向を順次選択する手段として機能させる。
【発明の効果】
【００１５】
本発明によれば、出発地から到着地までに通過する可能性のある交差点間を移動する所要時間の確率分布を、交差点での進行方向ごと、すなわち次に移動することが可能な、隣接する交差点ごとに取得するので、運転中に交通渋滞が発生する時間帯に入る場合であっても、確率計算時に既に想定している事象であることから経路を再探索する必要がなく、突然の経路変更が生じる可能性は低い。また、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示することなく、動的な情報に基づいて効率的な経路を確実に選択することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態１に係る経路選択装置の構成を示すブロック図である。
【図２】本発明の実施の形態１に係る経路選択装置の機能ブロック図である。
【図３】簡単な道路モデルに基づく確率モデルを示す例示図である。
【図４】本発明の実施の形態１に係る経路選択装置の各径路を選択した場合の期待所要時間を例示した表である。
【図５】本発明の実施の形態１に係る経路選択装置の最適な動的戦略に従う場合における「中町」で選択される道路を例示した表である。
【図６】本発明の実施の形態１に係る経路選択装置の経路の変更確率を例示した表である。
【図７】本発明の実施の形態１に係る経路選択装置のＣＰＵの処理手順を示すフローチャートである。
【図８】本発明の実施の形態２に係る経路選択装置の機能ブロック図である。
【図９】本発明の実施の形態２に係る経路選択装置のＣＰＵの処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態に係る、経路の変更頻度を減少させつつ、運転者にとって好ましい経路を選択して表示することができる装置について、図面に基づいて具体的に説明する。以下の実施の形態は、特許請求の範囲に記載された発明を限定するものではなく、実施の形態の中で説明されている特徴的事項の組み合わせの全てが解決手段の必須事項であるとは限らないことは言うまでもない。
【００１８】
また、本発明は多くの異なる態様にて実施することが可能であり、実施の形態の記載内容に限定して解釈されるべきものではない。実施の形態を通じて同じ要素には同一の符号を付している。
【００１９】
以下の実施の形態では、コンピュータシステムにコンピュータプログラムを導入した装置について説明するが、当業者であれば明らかな通り、本発明はその一部をコンピュータで実行することが可能なコンピュータプログラムとして実施することができる。したがって、本発明は、経路の変更頻度を減少させつつ、運転者にとって好ましい経路を選択して表示することができる装置というハードウェアとしての実施の形態、ソフトウェアとしての実施の形態、又はソトウェアとハードウェアとの組み合わせの実施の形態をとることができる。コンピュータプログラムは、ハードディスク、ＤＶＤ、ＣＤ、光記憶装置、磁気記憶装置等の任意のコンピュータで読み取ることが可能な記録媒体に記録することができる。
【００２０】
本発明の実施の形態によれば、出発地から到着地までに通過する可能性のある交差点間を移動する所要時間の確率分布を、交差点での進行方向ごと、すなわち次に移動することが可能な、隣接する交差点ごとに取得するので、運転中に交通渋滞が発生する時間帯に入る場合であっても、確率計算時に既に想定している事象であることから経路を再探索する必要がなく、突然の経路変更が生じる可能性は低い。また、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示することなく、動的な情報に基づいて効率的な経路を確実に選択することが可能となる。
【００２１】
（実施の形態１）
図１は、本発明の実施の形態１に係る経路選択装置の構成を示すブロック図である。本発明の実施の形態１に係る経路選択装置１は、少なくともＣＰＵ（中央演算装置）１１、メモリ１２、記憶装置１３、Ｉ／Ｏインタフェース１４、ビデオインタフェース１５、可搬型ディスクドライブ１６、通信インタフェース１７及び上述したハードウェアを接続する内部バス１８で構成されている。
【００２２】
ＣＰＵ１１は、内部バス１８を介して経路選択装置１の上述したようなハードウェア各部と接続されており、上述したハードウェア各部の動作を制御するとともに、記憶装置１３に記憶されたコンピュータプログラム１００に従って、種々のソフトウェア的機能を実行する。メモリ１２は、ＳＲＡＭ、ＳＤＲＡＭ等の揮発性メモリで構成され、コンピュータプログラム１００の実行時にロードモジュールが展開され、コンピュータプログラム１００の実行時に発生する一時的なデータ等を記憶する。
【００２３】
記憶装置１３は、内蔵される固定型記憶装置（ハードディスク）、ＲＯＭ等で構成されている。記憶装置１３に記憶されたコンピュータプログラム１００は、プログラム及びデータ等の情報を記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体９０から、可搬型ディスクドライブ１６によりダウンロードされ、実行時には記憶装置１３からメモリ１２へ展開して実行される。もちろん、通信インタフェース１７を介して接続されている外部コンピュータからダウンロードされたコンピュータプログラムであっても良い。
【００２４】
通信インタフェース１７は内部バス１８に接続されており、インターネット、ＬＡＮ、ＷＡＮ等の外部のネットワークに接続されることにより、外部コンピュータ等とデータ送受信を行うことが可能となっている。
【００２５】
Ｉ／Ｏインタフェース１４及びビデオインタフェース１５は、液晶ディスプレイ等で構成されたタッチパネル２１と接続され、所定の画像を表示しつつ、情報の入力を受け付ける。もちろん、別個にキーボード、マウス等の入力装置を接続して入力を受け付けても良い。
【００２６】
図２は、本発明の実施の形態１に係る経路選択装置１の機能ブロック図である。図２（ａ）において、経路選択装置１の動的戦略算出部２０１は、各交差点において、各交差点への所要時間に依存した動的戦略を算出する。ここで、「動的戦略」とは、各交差点において、その交差点への到着時間に応じて最適な次の交差点を進行方向として定めることを意味する。例えば出発点（出発地）ｖ0 の次の交差点ｖ1 において、交差点ｖ1 に到着する時刻に応じて、次に到着するべき交差点を進行方向として定める。
【００２７】
時間依存最適進行方向算出部（進行方向算出部）２０２は、動的戦略算出部２０１で算出された動的戦略に基づいて、各交差点への到着時間がｔとなる確率ｐと、各交差点への到着時間がｔである場合に選択するべき次の交差点を進行方向として算出する。例えば図２（ｂ）に示すように、交差点ｘごとに、交差点ｘへの到着時間がｔとなる確率ｐに、次に選択するべき交差点ｙを対応付けた表として算出結果を記憶しても良い。
【００２８】
確率加算部２０３は、次の交差点ごとに、進行方向ごとの所要時間の算出した確率を加算する。これにより、交差点ごとの次の交差点ごと、すなわち進行方向ごとの確率を求めることができる。交差点決定部２０４は、確率加算部２０３で加算して合計した所要時間の確率が一番高い進行方向を順次選択して、次の交差点を決定する。
【００２９】
もちろん、所要時間の確率分布は時系列に変動する。図３は、簡単な道路モデルに基づく確率モデルを示す例示図である。図３では、出発点を「西町」とし、運転者は朝７時に出発点「西町」を出発して「東町」に向かう場合を想定している。そして、「西町」から「中町」への所要時間の期待値Ｅは３０分、１時間以上要する確率は０．２５、３時間以上要する確率は０となっている。山道を選択した場合、中町から東町への所要時間は１．２５時間であり、高速道路を選択した場合、中町から東町への所要時間は１．０時間である。また、８時から１０時の間に中町から高速道路を選択した場合、交通渋滞により２時間余分に時間がかかる。
【００３０】
運転者に対して表示する経路の選択肢は３つある。図４は、本発明の実施の形態１に係る経路選択装置１の各径路を選択した場合の期待所要時間を例示した表である。図４からは、期待所要時間が１．７０時間と最短である経路‘３’を表示するべきと判断される。しかし、本願発明では、期待所要時間が２．００時間と最長である経路‘２’が表示される。なお、経路‘２’の期待所要時間は、「中町」経由であるので、図３に基づいて、０．５時間＋（０．７５×１．０時間＋０．２５×（１．０時間＋２．０時間））で算出することができる。
【００３１】
まず、最適な動的戦略を算出しておく。最適な動的戦略は、周知の手法により算出することができるが、交差点、道路等の数が少数である場合には、動的戦略を全て列挙して、最適な動的戦略を選択しても良い。
【００３２】
図５は、本発明の実施の形態１に係る経路選択装置１の最適な動的戦略に従う場合における、「中町」で選択される道路を例示した表である。なお、この最適な動的戦略に従って「西町」を７時に出発する場合には、まず「中町」へ高速道路を使っていくものとする。図５の例では、「中町」に到着する時間が８時より前の確率は０．７５であり、これは図３から明らかである。この場合、高速道路を選択して「中町」から「東町」への所要時間は１時間となる。
【００３３】
「中町」に到着する時間が８時から１０時の間である確率は０．２５である。この場合、山道を選択して「中町」から「東町」への所要時間は１．２５時間となる。そして、「中町」に到着する時間が１０時以降である確率は０である。この場合、高速道路を選択して「中町」から「東町」への所要時間は１時間となる。
【００３４】
図５に示す動的戦略に基づくと、最適な動的戦略は、「西町」から「中町」へは高速道路を選択し、「中町」から「東町」へは、「中町」への到着時間に応じて経路を動的に選択する。斯かる動的戦略に従って運転した場合、期待所要時間は、０．５時間＋（０．７５×１時間＋０．２５×１．２５時間）で１．５６２５時間と算出することができる。これは、図４の経路‘３’の期待所要時間よりも短い。
【００３５】
ただし、最適な動的戦略は経路を示すものではないので、運転者に提示する情報には工夫が必要となる。本実施の形態１では、運転者に最適な動的戦略に従って運転させるよう、出発時点において表示するべく経路を決定する。
【００３６】
まず、動的戦略によると、「西町」からの最適な経路は「中町」へ向かう高速道路であるので、「西町」から「中町」へ向かう高速道路を経路の一部として表示することを決定する。そして、決定された経路に従う場合の「中町」へ到着する時刻の確率分布Ｐを算出する。図３では、８時以前に到着する確率は０．７５、８時から１０時の間に到着する確率は０．２５である。
【００３７】
次に、最適な動的戦略に従って運転する場合に、確率分布Ｐに基づいて、進行方向として「中町」から山道を選択する確率Ｑｍと「中町」から高速道路を選択する確率Ｑｈを算出する。例えば、「中町」へ８時以前に到着する確率は０．７５であり、最適な動的戦略に従って高速道路を選択する。また、「中町」に１０時以降に到着する確率は０であるので、高速道路を選択する確率は０．７５（＝０．７５＋０）となる。同様に、山道を選択する確率は０．２５となる。
【００３８】
次に、最適な動的戦略に従って運転して「中町」に到着した時点で、「中町」からも最適な動的戦略に従う場合に、進行方向として選択する確率が最も高い道を特定する。図３の例では、「中町」から山道を選択する確率Ｑｍと「中町」から高速道路を選択する確率Ｑｈとで、「中町」から高速道路を選択する確率Ｑｈの方が大きいので、進行方向として選択する確率が最も高いのが高速道路であると特定する。
【００３９】
この時点で、「中町」からの高速道路を表示される経路の一部として追加表示する。したがって、表示される経路は、「西町」→高速道路→「中町」→高速道路→「東町」となり、すなわち図４に示す経路‘２’が表示される。
【００４０】
運転者は、表示されている経路‘２’に従って「西町」を出発する。「中町」に到着する直前において、「中町」への到着時刻が８時から１０時の間であるか否かを判断する。８時から１０時の間は、高速道路で渋滞が発生し、山道が最適な選択となる時間帯だからである。
【００４１】
「中町」への到着時刻が８時から１０時の間であると判断した場合、表示する経路を山道に変更することで、渋滞を回避することができる。「中町」への到着時刻が８時以前又は１０時以降であると判断した場合、表示する経路は変更されない。
【００４２】
すなわち、運転者が「西町」を出発する時点で、経路‘２’を表示することにより、表示される経路が変更される確率、すなわち「中町」への到着時刻が８時から１０時の間である確率は０．２５と小さいことから、表示される経路が頻繁に変更されることがない。
【００４３】
図６は、本発明の実施の形態１に係る経路選択装置１の経路の変更確率を例示した表である。図６に示すように、経路‘２’の変更確率は、上述したように０．２５となる。同様に、経路‘１’の変更確率は、０．７５（＝１−０．２５）となる。経路‘３’を表示した場合には、最適な動的戦略では「西町」からは「中町」に向かうので、表示されている経路が即座に変更されることになり、すなわち変更確率は‘１’となる。したがって、最小の変更確率は、表示経路が経路‘２’の場合であることが分かる。
【００４４】
図７は、本発明の実施の形態１に係る経路選択装置１のＣＰＵ１１の処理手順を示すフローチャートである。図７において、経路選択装置１のＣＰＵ１１は、初期値を設定する（ステップＳ７０１）。具体的には、交差点ｖ0 を出発点に設定し、確率テーブルＴ0 を（０、１．０）に、引数ｉを‘０’に、それぞれ設定する。ここで、確率テーブルＴi は、出発点を出発してからの時間ｔで区分けされる時間区分Ｓk と、時間区分Ｓk における確率ｐk とで表すテーブルであり（Ｓk 、ｐk）の集合で表す。
【００４５】
ＣＰＵ１１は、交差点ｖi に隣接する交差点ｕj を進行方向として抽出し、抽出した交差点ｕj へ向かう時間区分Ｓk の集合を算出する（ステップＳ７０２）。ここで、時間区分とは、図３の例でいう「朝８時より前」、「８時から１０時の間」等の動的戦略から求まる所要時間の区分を意味する。
【００４６】
ＣＰＵ１１は、確率テーブルＴi の確率ｐkをカウンタｊごとに加算し、確率ｐkの和Ｐj を算出する（ステップＳ７０３）。ｊごとに加算するということは、交差点ｖi に隣接する交差点ｕj ごとに確率ｐkの和Ｐj を算出することを意味する。このように算出されたＰj は、動的戦略に基づいて運転する場合における、交差点ｖi を経由したときに次の交差点が交差点ｕj となる確率を示している。
【００４７】
ＣＰＵ１１は、算出した確率ｐkの和Ｐj のうち、最大値である総和Ｐm を選択する（ステップＳ７０４）。
【００４８】
ＣＰＵ１１は、算出した最大値である総和Ｐm に対応する交差点ｕm を次の交差点ｖi+1 として（ステップＳ７０５）、交差点ｖi+1 での確率テーブルＴi+1 を算出する（ステップＳ７０６）。ＣＰＵ１１は、引数ｉを‘１’インクリメントして（ステップＳ７０７）、交差点ｖi が到着点であるか否かを判断する（ステップＳ７０８）。
【００４９】
ＣＰＵ１１が、交差点ｖi が到着点ではないと判断した場合（ステップＳ７０８：ＮＯ）、ＣＰＵ１１は、処理をステップＳ７０２へ戻して上述した処理を繰り返す。ＣＰＵ１１が、交差点ｖi が到着点であると判断した場合（ステップＳ７０８：ＹＥＳ）、ＣＰＵ１１は、処理を終了し、ｖ0 、ｖ1 、・・・、ｖi を探索した経路としてタッチパネル２１に表示する。
【００５０】
以上のように本実施の形態１によれば、最適な動的戦略に基づいて運転させるために、それまでの所要時間等の動的な情報に基づいて表示させる経路を変更しながら、運転者を最適な動的戦略に従って運転するように誘導することができる。表示させる経路は、最適な動的戦略に従って運転した場合に、あるいは運転中に交通渋滞が発生する時間帯に入る可能性等を考慮した場合に、最も選択する可能性が高い交差点列で構成される。このため、運転中に交通渋滞が発生する時間帯に入る場合であっても、表示させる経路を決定する時点で既に想定している事象であることから、突然の経路変更が生じて表示される経路の変更が必要となる可能性は低い。また、常に一本の経路のみを表示して運転者を誘導するので、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示することなく、動的な情報に基づいて効率的な経路を確実に選択することが可能となる。
【００５１】
（実施の形態２）
本発明の実施の形態２に係る経路選択装置１の構成は実施の形態１と同様であることから、同一の符号を付することにより詳細な説明は省略する。本実施の形態２では、最も確率の高い所要時間に対応する交差点を選択する点で実施の形態１とは相違する。
【００５２】
また、図８は、本発明の実施の形態２に係る経路選択装置１の機能ブロック図である。図８において、経路選択装置１の動的戦略算出部２０１は、各交差点において、各交差点への所要時間に依存した動的戦略を算出する。例えば出発点（出発地）ｖ0 の次の交差点ｖ1 において、交差点ｖ1 に到着する時刻に応じて、次に到着するべき交差点を進行方向として定める。
【００５３】
時間依存最適進行方向算出部（進行方向算出部）２０２は、動的戦略算出部２０１で算出された動的戦略に基づいて、各交差点への到着時間がｔとなる確率ｐと、各交差点への到着時間がｔである場合に選択するべき次の交差点を算出する。
【００５４】
最大確率抽出部６０１は、交差点ごとに、進行方向ごとの最も確率の高い所要時間を抽出する。これにより、交差点ごとにどれだけ時間がかかるか最も高い確率を有する進行方向を求めることができる。交差点決定部２０４は、最も高い確率を有する進行方向を順次選択して、次の交差点を決定する。
【００５５】
図９は、本発明の実施の形態２に係る経路選択装置１のＣＰＵ１１の処理手順を示すフローチャートである。図９において、経路選択装置１のＣＰＵ１１は、初期値を設定する（ステップＳ９０１）。具体的には、交差点ｖ0 を出発点に設定し、出発点を出発してから経過した時間τ0 を‘０’に、引数ｉを‘０’に、それぞれ設定する。
【００５６】
ＣＰＵ１１は、交差点ｖi に隣接する交差点ｖi+1 を進行方向として抽出し、抽出した交差点ｖi+1 の中から次の進行方向となる交差点ｖi+1 を周知の動的戦略に基づいて特定する（ステップＳ９０２）。ここで、図９のステップＳ９０２におけるψ（ｖi 、τi ）は、事前に算出してある動的戦略により定まる次に移動することが可能な交差点を、τi は出発点を出発してから経過した時間を、それぞれ意味する。
【００５７】
ＣＰＵ１１は、特定された交差点ｖi+1 への経路を移動する所要時間のうち、最も確率の高い所要時間Ｘi
を算出する（ステップＳ９０３）。そして、ＣＰＵ１１は、経過時間τi に所要時間Ｘi を加算して経過時間τi+1 を算出する（ステップＳ９０４）。
【００５８】
ＣＰＵ１１は、引数ｉを‘１’インクリメントして（ステップＳ９０５）、交差点ｖi が到着点であるか否かを判断する（ステップＳ９０６）。ＣＰＵ１１が、交差点ｖi が到着点ではないと判断した場合（ステップＳ９０６：ＮＯ）、ＣＰＵ１１は、処理をステップＳ９０２へ戻して上述した処理を繰り返す。ＣＰＵ１１が、交差点ｖi が到着点であると判断した場合（ステップＳ９０６：ＹＥＳ）、ＣＰＵ１１は、処理を終了し、ｖ0 、ｖ1 、・・・、ｖi を探索した経路としてタッチパネル２１に表示する。
【００５９】
以上のように本実施の形態２によれば、最適な動的戦略に基づいて運転させるために、それまでの所要時間等の動的な情報に基づいて表示させる経路を変更しながら、運転者を最適な動的戦略に従って運転するように誘導することができる。表示させる経路は、最適な動的戦略に従って運転した場合に、あるいは運転中に交通渋滞が発生する時間帯に入る可能性等を考慮した場合に、最も選択する可能性が高い交差点列で構成される。このため、運転中に交通渋滞が発生する時間帯に入る場合であっても、表示させる経路を決定する時点で既に想定している事象であることから、突然の経路変更が生じて表示される経路の変更が必要となる可能性は低い。また、常に一本の経路のみを表示して運転者を誘導するので、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示することなく、動的な情報に基づいて効率的な経路を確実に選択することが可能となる。
【００６０】
なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨の範囲内であれば多種の変更、改良等が可能である。
【符号の説明】
【００６１】
１ 経路選択装置
１１ ＣＰＵ
１２ メモリ
１３ 記憶装置
１４ Ｉ／Ｏインタフェース
１５ ビデオインタフェース
１６ 可搬型ディスクドライブ
１７ 通信インタフェース
１８ 内部バス
９０ 可搬型記録媒体
１００ コンピュータプログラム
【技術分野】
【０００１】
本発明は、経路の変更頻度を減少させつつ、運転者にとって好ましい経路を選択して表示する方法、装置及びコンピュータプログラムに関する。
【背景技術】
【０００２】
昨今のカーナビゲーションシステムは、経路選択アルゴリズムに様々な工夫が施され、運転者にとって最適な経路を選択して表示することができるようになっている。例えば特許文献１乃至４には、静的な情報に基づいて運転者にとって最適な経路を選択するカーナビゲーションシステムが開示されている。また、システムによっては、静的な情報に基づく複数の経路候補を表示して、表示された経路候補の中から運転者に選択させて最適な経路を表示するシステムも開示されている。
【０００３】
また、静的な情報だけではなく、将来起こり得る事象の確率分布を用いて経路選択する技術も開発されている。例えば非特許文献１及び２では、プローブカーデータ、定点観測データ等を取得し、移動（走行）時間の不確実性（確率分布）、あるいは将来の渋滞予測等の動的な情報を用いて、より最適な経路を選択するシステムが開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−１９００９１号公報
【特許文献２】特開２００２−２８６４８０号公報
【特許文献３】特開２００３−３３７０３６号公報
【特許文献４】特開２００５−０３７２４６号公報
【特許文献５】特開２００７−２５５９１９号公報
【特許文献６】特開２００８−０７７６３６号公報
【特許文献７】特開２０１０−０７２９８６号公報
【特許文献８】特許第３０１２０９６号公報
【特許文献９】特許第３１９３４７９号公報
【非特許文献】
【０００５】
【非特許文献１】キュー・ウー、ジェイ・ハートレイ、ディー・アル−ダバス：タイム−ディペンデント ストカスティック ショーテスト パス、アイ・ジェイ オブ シミュレーション、第６巻、７−８番、２００５年（Ｑ．Ｗｕ，Ｊ．Ｈａｒｔｌｅｙ，Ｄ．Ａｌ−Ｄａｂａｓｓ：Ｔｉｍｅ−Ｄｅｐｅｎｄｅｎｔ Ｓｔｏｃｈａｓｔｉｃ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ（ｓ）．Ｉ．Ｊ． ｏｆ Ｓｉｍｕｌａｔｉｏｎ，ｖｏｌ．６，Ｎｏ．７−８ ２００５）
【非特許文献２】イー・ディー・ミラー、エイチ・エス・マーマッサーニ、エイ・ジリアスコパラス：パス サーチ テクニックス フォー トランスポーテイション ネットワークス ウィズ タイム−ディペンデント、ストカスティック アーク コスト 、アイイーイーイー インターナショナル カンファレンス オン システムズ、マン アンド サイバネチックス：ヒューマンス、インフォメーション アンド テクノロジー、１９９４年（Ｅ．Ｄ．Ｍｉｌｌｅｒ、Ｈ．Ｓ．Ｍａｈｍａｓｓａｎｉ，Ａ．Ｚｉｌｉａｓｋｏｐｏｕｌｏｓ：Ｐａｔｈ ｓｅａｒｃｈ ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ｔｉｍｅ−ｄｅｐｅｎｄｅｎｔ， ｓｔｏｃｈａｓｔｉｃ ａｒｃ ｃｏｓｔｓ． ＩＥＥＥ Ｉｎｔ． Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｙｓｔｅｍｓ，Ｍａｎ， ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ：‘Ｈｕｍａｎｓ，Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ’ １９９４）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、特許文献１乃至４のように、静的な情報に基づいて選択した経路を表示する場合、出発時には交通渋滞がなかった道路において、通過時に交通渋滞が発生しやすい時間帯に入り、あるいは実際に交通渋滞が発生した場合、経路を再探索することにより経路の変更が頻繁に生じるおそれがあった。経路の変更は運転者にとってはストレスであり、経路の変更が頻繁に生じることで、結果として非効率的な経路選択になってしまう可能性も否定することができない。
【０００７】
また、動的な情報に基づいて選択した経路を表示する場合であっても、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示して運転者に理解させることは困難であるので、結局は静的な情報に基づく経路候補の中から最適な経路を選択している。したがって、経路の変更が頻繁に生じる場合、非効率的な経路選択になっている場合等も生じうる。
【０００８】
本発明は斯かる事情に鑑みてなされたものであり、運転中の頻繁な経路変更を抑制し、効率的な経路を選択することができ、運転者にとって好ましい経路を選択して表示する方法、装置及びコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために第１発明に係る方法は、運転者に経路を選択して表示する装置で実行することが可能な方法であって、出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する工程と、算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する工程と、前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する工程とを含む。
【００１０】
また、第２発明に係る方法は、第１発明において、前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する工程を含み、加算して合計した確率が一番高い進行方向を順次選択する。
【００１１】
次に、上記目的を達成するために第３発明に係る装置は、運転者に経路を選択して表示する装置であって、出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する動的戦略算出部と、算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する進行方向算出部と、前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する交差点決定部とを備える。
【００１２】
また、第４発明に係る装置は、第３発明において、前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する確率加算部を備え、前記交差点決定部は、加算して合計した確率が一番高い進行方向を順次選択する。
【００１３】
次に、上記目的を達成するために第５発明に係るコンピュータプログラムは、運転者に経路を選択して表示する装置で実行することが可能なコンピュータプログラムであって、前記装置を、出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する動的戦略算出手段、算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する進行方向算出手段、及び前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する交差点決定手段として機能させる。
【００１４】
また、第６発明に係るコンピュータプログラムは、第５発明において、前記装置を、前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する確率加算手段として機能させ、前記交差点決定手段を、加算して合計した確率が一番高い進行方向を順次選択する手段として機能させる。
【発明の効果】
【００１５】
本発明によれば、出発地から到着地までに通過する可能性のある交差点間を移動する所要時間の確率分布を、交差点での進行方向ごと、すなわち次に移動することが可能な、隣接する交差点ごとに取得するので、運転中に交通渋滞が発生する時間帯に入る場合であっても、確率計算時に既に想定している事象であることから経路を再探索する必要がなく、突然の経路変更が生じる可能性は低い。また、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示することなく、動的な情報に基づいて効率的な経路を確実に選択することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態１に係る経路選択装置の構成を示すブロック図である。
【図２】本発明の実施の形態１に係る経路選択装置の機能ブロック図である。
【図３】簡単な道路モデルに基づく確率モデルを示す例示図である。
【図４】本発明の実施の形態１に係る経路選択装置の各径路を選択した場合の期待所要時間を例示した表である。
【図５】本発明の実施の形態１に係る経路選択装置の最適な動的戦略に従う場合における「中町」で選択される道路を例示した表である。
【図６】本発明の実施の形態１に係る経路選択装置の経路の変更確率を例示した表である。
【図７】本発明の実施の形態１に係る経路選択装置のＣＰＵの処理手順を示すフローチャートである。
【図８】本発明の実施の形態２に係る経路選択装置の機能ブロック図である。
【図９】本発明の実施の形態２に係る経路選択装置のＣＰＵの処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態に係る、経路の変更頻度を減少させつつ、運転者にとって好ましい経路を選択して表示することができる装置について、図面に基づいて具体的に説明する。以下の実施の形態は、特許請求の範囲に記載された発明を限定するものではなく、実施の形態の中で説明されている特徴的事項の組み合わせの全てが解決手段の必須事項であるとは限らないことは言うまでもない。
【００１８】
また、本発明は多くの異なる態様にて実施することが可能であり、実施の形態の記載内容に限定して解釈されるべきものではない。実施の形態を通じて同じ要素には同一の符号を付している。
【００１９】
以下の実施の形態では、コンピュータシステムにコンピュータプログラムを導入した装置について説明するが、当業者であれば明らかな通り、本発明はその一部をコンピュータで実行することが可能なコンピュータプログラムとして実施することができる。したがって、本発明は、経路の変更頻度を減少させつつ、運転者にとって好ましい経路を選択して表示することができる装置というハードウェアとしての実施の形態、ソフトウェアとしての実施の形態、又はソトウェアとハードウェアとの組み合わせの実施の形態をとることができる。コンピュータプログラムは、ハードディスク、ＤＶＤ、ＣＤ、光記憶装置、磁気記憶装置等の任意のコンピュータで読み取ることが可能な記録媒体に記録することができる。
【００２０】
本発明の実施の形態によれば、出発地から到着地までに通過する可能性のある交差点間を移動する所要時間の確率分布を、交差点での進行方向ごと、すなわち次に移動することが可能な、隣接する交差点ごとに取得するので、運転中に交通渋滞が発生する時間帯に入る場合であっても、確率計算時に既に想定している事象であることから経路を再探索する必要がなく、突然の経路変更が生じる可能性は低い。また、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示することなく、動的な情報に基づいて効率的な経路を確実に選択することが可能となる。
【００２１】
（実施の形態１）
図１は、本発明の実施の形態１に係る経路選択装置の構成を示すブロック図である。本発明の実施の形態１に係る経路選択装置１は、少なくともＣＰＵ（中央演算装置）１１、メモリ１２、記憶装置１３、Ｉ／Ｏインタフェース１４、ビデオインタフェース１５、可搬型ディスクドライブ１６、通信インタフェース１７及び上述したハードウェアを接続する内部バス１８で構成されている。
【００２２】
ＣＰＵ１１は、内部バス１８を介して経路選択装置１の上述したようなハードウェア各部と接続されており、上述したハードウェア各部の動作を制御するとともに、記憶装置１３に記憶されたコンピュータプログラム１００に従って、種々のソフトウェア的機能を実行する。メモリ１２は、ＳＲＡＭ、ＳＤＲＡＭ等の揮発性メモリで構成され、コンピュータプログラム１００の実行時にロードモジュールが展開され、コンピュータプログラム１００の実行時に発生する一時的なデータ等を記憶する。
【００２３】
記憶装置１３は、内蔵される固定型記憶装置（ハードディスク）、ＲＯＭ等で構成されている。記憶装置１３に記憶されたコンピュータプログラム１００は、プログラム及びデータ等の情報を記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体９０から、可搬型ディスクドライブ１６によりダウンロードされ、実行時には記憶装置１３からメモリ１２へ展開して実行される。もちろん、通信インタフェース１７を介して接続されている外部コンピュータからダウンロードされたコンピュータプログラムであっても良い。
【００２４】
通信インタフェース１７は内部バス１８に接続されており、インターネット、ＬＡＮ、ＷＡＮ等の外部のネットワークに接続されることにより、外部コンピュータ等とデータ送受信を行うことが可能となっている。
【００２５】
Ｉ／Ｏインタフェース１４及びビデオインタフェース１５は、液晶ディスプレイ等で構成されたタッチパネル２１と接続され、所定の画像を表示しつつ、情報の入力を受け付ける。もちろん、別個にキーボード、マウス等の入力装置を接続して入力を受け付けても良い。
【００２６】
図２は、本発明の実施の形態１に係る経路選択装置１の機能ブロック図である。図２（ａ）において、経路選択装置１の動的戦略算出部２０１は、各交差点において、各交差点への所要時間に依存した動的戦略を算出する。ここで、「動的戦略」とは、各交差点において、その交差点への到着時間に応じて最適な次の交差点を進行方向として定めることを意味する。例えば出発点（出発地）ｖ0 の次の交差点ｖ1 において、交差点ｖ1 に到着する時刻に応じて、次に到着するべき交差点を進行方向として定める。
【００２７】
時間依存最適進行方向算出部（進行方向算出部）２０２は、動的戦略算出部２０１で算出された動的戦略に基づいて、各交差点への到着時間がｔとなる確率ｐと、各交差点への到着時間がｔである場合に選択するべき次の交差点を進行方向として算出する。例えば図２（ｂ）に示すように、交差点ｘごとに、交差点ｘへの到着時間がｔとなる確率ｐに、次に選択するべき交差点ｙを対応付けた表として算出結果を記憶しても良い。
【００２８】
確率加算部２０３は、次の交差点ごとに、進行方向ごとの所要時間の算出した確率を加算する。これにより、交差点ごとの次の交差点ごと、すなわち進行方向ごとの確率を求めることができる。交差点決定部２０４は、確率加算部２０３で加算して合計した所要時間の確率が一番高い進行方向を順次選択して、次の交差点を決定する。
【００２９】
もちろん、所要時間の確率分布は時系列に変動する。図３は、簡単な道路モデルに基づく確率モデルを示す例示図である。図３では、出発点を「西町」とし、運転者は朝７時に出発点「西町」を出発して「東町」に向かう場合を想定している。そして、「西町」から「中町」への所要時間の期待値Ｅは３０分、１時間以上要する確率は０．２５、３時間以上要する確率は０となっている。山道を選択した場合、中町から東町への所要時間は１．２５時間であり、高速道路を選択した場合、中町から東町への所要時間は１．０時間である。また、８時から１０時の間に中町から高速道路を選択した場合、交通渋滞により２時間余分に時間がかかる。
【００３０】
運転者に対して表示する経路の選択肢は３つある。図４は、本発明の実施の形態１に係る経路選択装置１の各径路を選択した場合の期待所要時間を例示した表である。図４からは、期待所要時間が１．７０時間と最短である経路‘３’を表示するべきと判断される。しかし、本願発明では、期待所要時間が２．００時間と最長である経路‘２’が表示される。なお、経路‘２’の期待所要時間は、「中町」経由であるので、図３に基づいて、０．５時間＋（０．７５×１．０時間＋０．２５×（１．０時間＋２．０時間））で算出することができる。
【００３１】
まず、最適な動的戦略を算出しておく。最適な動的戦略は、周知の手法により算出することができるが、交差点、道路等の数が少数である場合には、動的戦略を全て列挙して、最適な動的戦略を選択しても良い。
【００３２】
図５は、本発明の実施の形態１に係る経路選択装置１の最適な動的戦略に従う場合における、「中町」で選択される道路を例示した表である。なお、この最適な動的戦略に従って「西町」を７時に出発する場合には、まず「中町」へ高速道路を使っていくものとする。図５の例では、「中町」に到着する時間が８時より前の確率は０．７５であり、これは図３から明らかである。この場合、高速道路を選択して「中町」から「東町」への所要時間は１時間となる。
【００３３】
「中町」に到着する時間が８時から１０時の間である確率は０．２５である。この場合、山道を選択して「中町」から「東町」への所要時間は１．２５時間となる。そして、「中町」に到着する時間が１０時以降である確率は０である。この場合、高速道路を選択して「中町」から「東町」への所要時間は１時間となる。
【００３４】
図５に示す動的戦略に基づくと、最適な動的戦略は、「西町」から「中町」へは高速道路を選択し、「中町」から「東町」へは、「中町」への到着時間に応じて経路を動的に選択する。斯かる動的戦略に従って運転した場合、期待所要時間は、０．５時間＋（０．７５×１時間＋０．２５×１．２５時間）で１．５６２５時間と算出することができる。これは、図４の経路‘３’の期待所要時間よりも短い。
【００３５】
ただし、最適な動的戦略は経路を示すものではないので、運転者に提示する情報には工夫が必要となる。本実施の形態１では、運転者に最適な動的戦略に従って運転させるよう、出発時点において表示するべく経路を決定する。
【００３６】
まず、動的戦略によると、「西町」からの最適な経路は「中町」へ向かう高速道路であるので、「西町」から「中町」へ向かう高速道路を経路の一部として表示することを決定する。そして、決定された経路に従う場合の「中町」へ到着する時刻の確率分布Ｐを算出する。図３では、８時以前に到着する確率は０．７５、８時から１０時の間に到着する確率は０．２５である。
【００３７】
次に、最適な動的戦略に従って運転する場合に、確率分布Ｐに基づいて、進行方向として「中町」から山道を選択する確率Ｑｍと「中町」から高速道路を選択する確率Ｑｈを算出する。例えば、「中町」へ８時以前に到着する確率は０．７５であり、最適な動的戦略に従って高速道路を選択する。また、「中町」に１０時以降に到着する確率は０であるので、高速道路を選択する確率は０．７５（＝０．７５＋０）となる。同様に、山道を選択する確率は０．２５となる。
【００３８】
次に、最適な動的戦略に従って運転して「中町」に到着した時点で、「中町」からも最適な動的戦略に従う場合に、進行方向として選択する確率が最も高い道を特定する。図３の例では、「中町」から山道を選択する確率Ｑｍと「中町」から高速道路を選択する確率Ｑｈとで、「中町」から高速道路を選択する確率Ｑｈの方が大きいので、進行方向として選択する確率が最も高いのが高速道路であると特定する。
【００３９】
この時点で、「中町」からの高速道路を表示される経路の一部として追加表示する。したがって、表示される経路は、「西町」→高速道路→「中町」→高速道路→「東町」となり、すなわち図４に示す経路‘２’が表示される。
【００４０】
運転者は、表示されている経路‘２’に従って「西町」を出発する。「中町」に到着する直前において、「中町」への到着時刻が８時から１０時の間であるか否かを判断する。８時から１０時の間は、高速道路で渋滞が発生し、山道が最適な選択となる時間帯だからである。
【００４１】
「中町」への到着時刻が８時から１０時の間であると判断した場合、表示する経路を山道に変更することで、渋滞を回避することができる。「中町」への到着時刻が８時以前又は１０時以降であると判断した場合、表示する経路は変更されない。
【００４２】
すなわち、運転者が「西町」を出発する時点で、経路‘２’を表示することにより、表示される経路が変更される確率、すなわち「中町」への到着時刻が８時から１０時の間である確率は０．２５と小さいことから、表示される経路が頻繁に変更されることがない。
【００４３】
図６は、本発明の実施の形態１に係る経路選択装置１の経路の変更確率を例示した表である。図６に示すように、経路‘２’の変更確率は、上述したように０．２５となる。同様に、経路‘１’の変更確率は、０．７５（＝１−０．２５）となる。経路‘３’を表示した場合には、最適な動的戦略では「西町」からは「中町」に向かうので、表示されている経路が即座に変更されることになり、すなわち変更確率は‘１’となる。したがって、最小の変更確率は、表示経路が経路‘２’の場合であることが分かる。
【００４４】
図７は、本発明の実施の形態１に係る経路選択装置１のＣＰＵ１１の処理手順を示すフローチャートである。図７において、経路選択装置１のＣＰＵ１１は、初期値を設定する（ステップＳ７０１）。具体的には、交差点ｖ0 を出発点に設定し、確率テーブルＴ0 を（０、１．０）に、引数ｉを‘０’に、それぞれ設定する。ここで、確率テーブルＴi は、出発点を出発してからの時間ｔで区分けされる時間区分Ｓk と、時間区分Ｓk における確率ｐk とで表すテーブルであり（Ｓk 、ｐk）の集合で表す。
【００４５】
ＣＰＵ１１は、交差点ｖi に隣接する交差点ｕj を進行方向として抽出し、抽出した交差点ｕj へ向かう時間区分Ｓk の集合を算出する（ステップＳ７０２）。ここで、時間区分とは、図３の例でいう「朝８時より前」、「８時から１０時の間」等の動的戦略から求まる所要時間の区分を意味する。
【００４６】
ＣＰＵ１１は、確率テーブルＴi の確率ｐkをカウンタｊごとに加算し、確率ｐkの和Ｐj を算出する（ステップＳ７０３）。ｊごとに加算するということは、交差点ｖi に隣接する交差点ｕj ごとに確率ｐkの和Ｐj を算出することを意味する。このように算出されたＰj は、動的戦略に基づいて運転する場合における、交差点ｖi を経由したときに次の交差点が交差点ｕj となる確率を示している。
【００４７】
ＣＰＵ１１は、算出した確率ｐkの和Ｐj のうち、最大値である総和Ｐm を選択する（ステップＳ７０４）。
【００４８】
ＣＰＵ１１は、算出した最大値である総和Ｐm に対応する交差点ｕm を次の交差点ｖi+1 として（ステップＳ７０５）、交差点ｖi+1 での確率テーブルＴi+1 を算出する（ステップＳ７０６）。ＣＰＵ１１は、引数ｉを‘１’インクリメントして（ステップＳ７０７）、交差点ｖi が到着点であるか否かを判断する（ステップＳ７０８）。
【００４９】
ＣＰＵ１１が、交差点ｖi が到着点ではないと判断した場合（ステップＳ７０８：ＮＯ）、ＣＰＵ１１は、処理をステップＳ７０２へ戻して上述した処理を繰り返す。ＣＰＵ１１が、交差点ｖi が到着点であると判断した場合（ステップＳ７０８：ＹＥＳ）、ＣＰＵ１１は、処理を終了し、ｖ0 、ｖ1 、・・・、ｖi を探索した経路としてタッチパネル２１に表示する。
【００５０】
以上のように本実施の形態１によれば、最適な動的戦略に基づいて運転させるために、それまでの所要時間等の動的な情報に基づいて表示させる経路を変更しながら、運転者を最適な動的戦略に従って運転するように誘導することができる。表示させる経路は、最適な動的戦略に従って運転した場合に、あるいは運転中に交通渋滞が発生する時間帯に入る可能性等を考慮した場合に、最も選択する可能性が高い交差点列で構成される。このため、運転中に交通渋滞が発生する時間帯に入る場合であっても、表示させる経路を決定する時点で既に想定している事象であることから、突然の経路変更が生じて表示される経路の変更が必要となる可能性は低い。また、常に一本の経路のみを表示して運転者を誘導するので、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示することなく、動的な情報に基づいて効率的な経路を確実に選択することが可能となる。
【００５１】
（実施の形態２）
本発明の実施の形態２に係る経路選択装置１の構成は実施の形態１と同様であることから、同一の符号を付することにより詳細な説明は省略する。本実施の形態２では、最も確率の高い所要時間に対応する交差点を選択する点で実施の形態１とは相違する。
【００５２】
また、図８は、本発明の実施の形態２に係る経路選択装置１の機能ブロック図である。図８において、経路選択装置１の動的戦略算出部２０１は、各交差点において、各交差点への所要時間に依存した動的戦略を算出する。例えば出発点（出発地）ｖ0 の次の交差点ｖ1 において、交差点ｖ1 に到着する時刻に応じて、次に到着するべき交差点を進行方向として定める。
【００５３】
時間依存最適進行方向算出部（進行方向算出部）２０２は、動的戦略算出部２０１で算出された動的戦略に基づいて、各交差点への到着時間がｔとなる確率ｐと、各交差点への到着時間がｔである場合に選択するべき次の交差点を算出する。
【００５４】
最大確率抽出部６０１は、交差点ごとに、進行方向ごとの最も確率の高い所要時間を抽出する。これにより、交差点ごとにどれだけ時間がかかるか最も高い確率を有する進行方向を求めることができる。交差点決定部２０４は、最も高い確率を有する進行方向を順次選択して、次の交差点を決定する。
【００５５】
図９は、本発明の実施の形態２に係る経路選択装置１のＣＰＵ１１の処理手順を示すフローチャートである。図９において、経路選択装置１のＣＰＵ１１は、初期値を設定する（ステップＳ９０１）。具体的には、交差点ｖ0 を出発点に設定し、出発点を出発してから経過した時間τ0 を‘０’に、引数ｉを‘０’に、それぞれ設定する。
【００５６】
ＣＰＵ１１は、交差点ｖi に隣接する交差点ｖi+1 を進行方向として抽出し、抽出した交差点ｖi+1 の中から次の進行方向となる交差点ｖi+1 を周知の動的戦略に基づいて特定する（ステップＳ９０２）。ここで、図９のステップＳ９０２におけるψ（ｖi 、τi ）は、事前に算出してある動的戦略により定まる次に移動することが可能な交差点を、τi は出発点を出発してから経過した時間を、それぞれ意味する。
【００５７】
ＣＰＵ１１は、特定された交差点ｖi+1 への経路を移動する所要時間のうち、最も確率の高い所要時間Ｘi
を算出する（ステップＳ９０３）。そして、ＣＰＵ１１は、経過時間τi に所要時間Ｘi を加算して経過時間τi+1 を算出する（ステップＳ９０４）。
【００５８】
ＣＰＵ１１は、引数ｉを‘１’インクリメントして（ステップＳ９０５）、交差点ｖi が到着点であるか否かを判断する（ステップＳ９０６）。ＣＰＵ１１が、交差点ｖi が到着点ではないと判断した場合（ステップＳ９０６：ＮＯ）、ＣＰＵ１１は、処理をステップＳ９０２へ戻して上述した処理を繰り返す。ＣＰＵ１１が、交差点ｖi が到着点であると判断した場合（ステップＳ９０６：ＹＥＳ）、ＣＰＵ１１は、処理を終了し、ｖ0 、ｖ1 、・・・、ｖi を探索した経路としてタッチパネル２１に表示する。
【００５９】
以上のように本実施の形態２によれば、最適な動的戦略に基づいて運転させるために、それまでの所要時間等の動的な情報に基づいて表示させる経路を変更しながら、運転者を最適な動的戦略に従って運転するように誘導することができる。表示させる経路は、最適な動的戦略に従って運転した場合に、あるいは運転中に交通渋滞が発生する時間帯に入る可能性等を考慮した場合に、最も選択する可能性が高い交差点列で構成される。このため、運転中に交通渋滞が発生する時間帯に入る場合であっても、表示させる経路を決定する時点で既に想定している事象であることから、突然の経路変更が生じて表示される経路の変更が必要となる可能性は低い。また、常に一本の経路のみを表示して運転者を誘導するので、「○時より前に到着したら道路Ａ、それ以降なら道路Ｂ」などという運転者が即時に判断することができない情報を表示することなく、動的な情報に基づいて効率的な経路を確実に選択することが可能となる。
【００６０】
なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨の範囲内であれば多種の変更、改良等が可能である。
【符号の説明】
【００６１】
１ 経路選択装置
１１ ＣＰＵ
１２ メモリ
１３ 記憶装置
１４ Ｉ／Ｏインタフェース
１５ ビデオインタフェース
１６ 可搬型ディスクドライブ
１７ 通信インタフェース
１８ 内部バス
９０ 可搬型記録媒体
１００ コンピュータプログラム
【特許請求の範囲】
【請求項１】
運転者に経路を選択して表示する装置で実行することが可能な方法であって、
出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する工程と、
算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する工程と、
前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する工程と
を含む方法。
【請求項２】
前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する工程を含み、加算して合計した確率が一番高い進行方向を順次選択する請求項１に記載の方法。
【請求項３】
運転者に経路を選択して表示する装置であって、
出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する動的戦略算出部と、
算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する進行方向算出部と、
前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する交差点決定部と
を備える装置。
【請求項４】
前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する確率加算部を備え、前記交差点決定部は、加算して合計した確率が一番高い進行方向を順次選択する請求項３に記載の装置。
【請求項５】
運転者に経路を選択して表示する装置で実行することが可能なコンピュータプログラムであって、
前記装置を、
出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する動的戦略算出手段、
算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する進行方向算出手段、及び
前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する交差点決定手段
として機能させるコンピュータプログラム。
【請求項６】
前記装置を、
前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する確率加算手段として機能させ、前記交差点決定手段を、加算して合計した確率が一番高い進行方向を順次選択する手段として機能させる請求項５に記載のコンピュータプログラム。
【請求項１】
運転者に経路を選択して表示する装置で実行することが可能な方法であって、
出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する工程と、
算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する工程と、
前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する工程と
を含む方法。
【請求項２】
前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する工程を含み、加算して合計した確率が一番高い進行方向を順次選択する請求項１に記載の方法。
【請求項３】
運転者に経路を選択して表示する装置であって、
出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する動的戦略算出部と、
算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する進行方向算出部と、
前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する交差点決定部と
を備える装置。
【請求項４】
前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する確率加算部を備え、前記交差点決定部は、加算して合計した確率が一番高い進行方向を順次選択する請求項３に記載の装置。
【請求項５】
運転者に経路を選択して表示する装置で実行することが可能なコンピュータプログラムであって、
前記装置を、
出発地から到着地までに通過する可能性のある各交差点において、各交差点への所要時間に依存した動的戦略を算出する動的戦略算出手段、
算出した動的戦略に基づいて、交差点ごとの前記所要時間に関する確率分布、及び前記所要時間に依存して選択するべき進行方向を算出する進行方向算出手段、及び
前記所要時間の確率が一番高い進行方向を順次選択して、到着地までに通過する交差点を決定する交差点決定手段
として機能させるコンピュータプログラム。
【請求項６】
前記装置を、
前記交差点ごとに、前記進行方向ごとの前記所要時間の確率を加算する確率加算手段として機能させ、前記交差点決定手段を、加算して合計した確率が一番高い進行方向を順次選択する手段として機能させる請求項５に記載のコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１３−５３９８７（Ｐ２０１３−５３９８７Ａ）
【公開日】平成２５年３月２１日（２０１３．３．２１）
【国際特許分類】
【出願番号】特願２０１１−１９３６０９（Ｐ２０１１−１９３６０９）
【出願日】平成２３年９月６日（２０１１．９．６）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度、総務省、「自動車二酸化炭素排出量削減のための大規模モビリティ社会シミュレータの研究開発」委託事業、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【復代理人】
【識別番号】１００１１７２６０
【弁理士】
【氏名又は名称】福永 正也
【Ｆターム（参考）】
【公開日】平成２５年３月２１日（２０１３．３．２１）
【国際特許分類】
【出願日】平成２３年９月６日（２０１１．９．６）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２１年度、総務省、「自動車二酸化炭素排出量削減のための大規模モビリティ社会シミュレータの研究開発」委託事業、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【復代理人】
【識別番号】１００１１７２６０
【弁理士】
【氏名又は名称】福永 正也
【Ｆターム（参考）】
[ Back to top ]