(57)【特許請求の範囲】
【請求項１】
複数のノードをリンクした道路ネットワークデータと、各ノードのＯＤ交通量データとに基づいて、該ＯＤ交通量データで指定される起点及び終点の組み合わせ毎に、起点から終点までの最適経路を探索する最適経路探索手段と、
前記最適経路探索手段により探索された最適経路が交差するノード又は最適経路が分岐するノードを、分岐ノードとして抽出する分岐ノード抽出手段と、
前記分岐ノード抽出手段により抽出された各分岐ノードを連結して簡略ネットワークを作成する作成手段と、
前記作成手段により作成された簡略ネットワークの各分岐ノードを用いて、前記各最適経路の分岐ノード間のパスを抽出するパス抽出手段と、
前記パス抽出手段により抽出された複数のパスを組み合わせて、前記各最適経路の候補経路を作成する候補経路作成手段と、
を備えた候補経路作成装置。
【請求項２】
前記パス抽出手段は、前記簡略ネットワークにおいて、既に抽出されたパスに重複しないようにパスを抽出する
請求項１に記載の候補経路作成装置。
【請求項３】
前記パス抽出手段は、分岐ノード間の各パスの走行負担を表すコストと閾値とを比較し、前記閾値より低いコストのパスのみを抽出する
請求項１または請求項２に記載の候補経路作成装置。
【請求項４】
前記最適経路探索手段は、前記起点及び前記終点の少なくとも１つに対して前記道路ネットワークデータの代表的な地点を用いて、前記最適経路を探索する
請求項１から請求項３のいずれか１項に記載の候補経路作成装置。
【請求項５】
最適経路探索手段と、分岐ノード抽出手段と、作成手段と、パス抽出手段と、候補経路作成手段と、を備えた候補経路作成装置において実行される候補経路作成方法であって、
前記最適経路探索手段が、複数のノードをリンクした道路ネットワークデータと、各ノードのＯＤ交通量データとに基づいて、該ＯＤ交通量データで指定される起点及び終点の組み合わせ毎に、起点から終点までの最適経路を探索し、
前記分岐ノード抽出手段が、前記最適経路探索手段により探索された最適経路が交差するノード又は最適経路が分岐するノードを、分岐ノードとして抽出し、
前記作成手段が、前記分岐ノード抽出手段により抽出された各分岐ノードを連結して簡略ネットワークを作成し、
前記パス抽出手段が、前記作成手段により作成された簡略ネットワークの各分岐ノードを用いて、前記各最適経路の分岐ノード間のパスを抽出し、
前記候補経路作成手段が、前記パス抽出手段により抽出された複数のパスを組み合わせて、前記各最適経路の候補経路を作成する
候補経路作成方法。
【請求項６】
コンピュータを、
複数のノードをリンクした道路ネットワークデータと、各ノードのＯＤ交通量データとに基づいて、該ＯＤ交通量データで指定される起点及び終点の組み合わせ毎に、起点から終点までの最適経路を探索する最適経路探索手段、
前記最適経路探索手段により探索された最適経路が交差するノード又は最適経路が分岐するノードを、分岐ノードとして抽出する分岐ノード抽出手段、
前記分岐ノード抽出手段により抽出された各分岐ノードを連結して簡略ネットワークを作成する作成手段、
前記作成手段により作成された簡略ネットワークの各分岐ノードを用いて、前記各最適経路の分岐ノード間のパスを抽出するパス抽出手段、及び
前記パス抽出手段により抽出された複数のパスを組み合わせて、前記各最適経路の候補経路を作成する候補経路作成手段
として機能させるための候補経路作成プログラム。
【請求項７】
請求項１から請求項４のいずれか１項に記載の候補経路作成装置と、
単位時間あたり所定数の車両を発生させる車両発生手段と、
前記最適経路探索手段で探索された最適経路の走行負担を表すコストと、前記候補経路作成手段で作成された候補経路の走行負担を表すコストとを用いて、前記最適経路及びその候補経路の中から確率的に経路を選択する経路選択手段と、
前記車両発生手段により発生された各車両を、前記経路選択手段により選択された経路の起点から終点に移動させる車両移動手段と、
を備えた交通シミュレーション装置。
【請求項８】
前記経路選択手段は、経路間の推測された又は実測された旅行時間を用いて各経路のコストを演算する
請求項７に記載の交通シミュレーション装置。
【請求項９】
前記経路選択手段は、経路間の旅行時間を所定値に設定して、前記最適経路及び前記候補経路の各コストを演算する
請求項７に記載の交通シミュレーション装置。
【請求項１０】
前記経路選択手段は、車両が分岐ノードに達するまでに、前記分岐ノードから終点までのすべての部分経路のコストを用いて、前記各部分経路の中から確率的に経路を選択する
請求項７から請求項９のいずれか１項に記載の交通シミュレーション装置。
【請求項１１】
前記経路選択手段は、車両が分岐ノードに達するまでに、前記分岐ノードから最適経路上の最も手前の分岐ノードまでの部分経路のコストを用いて、前記各部分経路の中から確率的に経路を選択する
請求項７から請求項９のいずれか１項に記載の交通シミュレーション装置。
【請求項１２】
前記経路選択手段は、車両の旅行時間の有無に応じて、経路間の推測された又は実測された旅行時間を用いて各経路のコストを演算する第１のモード、経路間の旅行時間を所定値に設定して前記最適経路及び前記候補経路の各コストを演算する第２のモードのいずれかに切り替える
請求項７に記載の交通シミュレーション装置。
【請求項１３】
前記経路選択手段は、ドライバの走行経験の有無に応じて、車両が分岐ノードに達するまでに前記分岐ノードから終点までのすべての部分経路のコストを用いて前記各部分経路の中から確率的に経路を選択する第３のモード、車両が分岐ノードに達するまでに前記分岐ノードから最適経路上の最も手前の分岐ノードまでの部分経路のコストを用いて前記各部分経路の中から確率的に経路を選択する第４のモードのいずれか１つに切り替える
請求項７または請求項１２に記載の交通シミュレーション装置。
【請求項１４】
前記経路選択手段は、交通情報受信手段の有無に応じて、車両が分岐ノードに達するまでに前記分岐ノードから終点までのすべての部分経路のコストを用いて前記各部分経路の中から確率的に経路を選択する第３のモード、車両が分岐ノードに達するまでに前記分岐ノードから最適経路上の最も手前の分岐ノードまでの部分経路のコストを用いて前記各部分経路の中から確率的に経路を選択する第４のモードのいずれかに切り替える
請求項７または請求項１２に記載の交通シミュレーション装置。
【請求項１５】
請求項１から請求項４のいずれか１項に記載の候補経路作成装置と、車両発生手段と、経路選択手段と、車両移動手段と、を備えた交通シミュレーション装置において実行される交通シミュレーション方法であって、
前記候補経路作成装置が、請求項５に記載の候補経路作成方法を実行し、
前記車両発生手段が、単位時間あたり所定数の車両を発生し、
前記経路選択手段が、前記最適経路探索手段で探索された最適経路の走行負担を表すコストと、前記候補経路作成手段で作成された候補経路の走行負担を表すコストとを用いて、前記最適経路及びその候補経路の中から確率的に経路を選択し、
前記車両移動手段が、前記車両発生手段により発生された各車両を前記経路選択手段により選択された経路の起点から終点に移動させる
交通シミュレーション方法。
【請求項１６】
コンピュータを、請求項１から請求項４のいずれか１項に記載の候補経路作成装置を構成する各手段、車両発生手段、経路選択手段、及び車両移動手段として機能させるための交通シミュレーションプログラムであって、
前記車両発生手段は、単位時間あたり所定数の車両を発生させ、
前記経路選択手段は、前記最適経路探索手段で探索された最適経路の走行負担を表すコストと、前記候補経路作成手段で作成された候補経路の走行負担を表すコストとを用いて、前記最適経路及びその候補経路の中から確率的に経路を選択し、
前記車両移動手段は、前記車両発生手段により発生された各車両を前記経路選択手段により選択された経路の起点から終点に移動させる
交通シミュレーションプログラム。
【請求項１７】
現在位置を前記起点とし、目的地を前記終点として、前記現在位置から前記目的地までの最適経路を探索すると共に前記最適経路の候補経路を作成する請求項１から請求項４のいずれか１項に記載の候補経路作成装置と、
前記最適経路探索手段で探索された最適経路の走行負担を表すコストと、前記候補経路作成手段で作成された候補経路の走行負担を表すコストとに基づいて、最もコストの小さい経路を探索する経路探索手段と、
を備えた経路探索装置。
【請求項１８】
現在位置を前記起点とし、目的地を前記終点として、前記現在位置から前記目的地までの最適経路を探索すると共に前記最適経路の候補経路を作成する請求項１から請求項４のいずれか１項に記載の候補経路作成装置と、経路探索手段と、を備えた経路探索装置において実行される経路探索方法であって、
前記候補経路作成装置が、請求項５に記載の候補経路作成方法を実行し、
前記経路探索手段が、前記最適経路探索手段で探索された最適経路の走行負担を表すコストと、前記候補経路作成手段で作成された候補経路の走行負担を表すコストとに基づいて、最もコストの小さい経路を探索する
経路探索方法。
【請求項１９】
コンピュータを、現在位置を前記起点とし、目的地を前記終点として、前記現在位置から前記目的地までの最適経路を探索すると共に前記最適経路の候補経路を作成する請求項１から請求項４のいずれか１項に記載の候補経路作成装置を構成する各手段、及び経路探索手段として機能させるための経路探索プログラムであって、
前記経路探索手段は、前記最適経路探索手段で探索された最適経路の走行負担を表すコストと、前記候補経路作成手段で作成された候補経路の走行負担を表すコストとに基づいて、最もコストの小さい経路を探索させる
経路探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、候補経路作成装置、方法、プログラム、交通シミュレーション装置、方法及びプログラム、経路探索装置、方法、及びプログラムに係り、特に、演算負荷を低減して高速に処理可能な候補経路作成装置、方法、プログラム、交通シミュレーション装置、方法及びプログラム、経路探索装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
現在の交通ネットワークにおいては、交通渋滞の解消や交通の円滑化を目的とした道路・交通施設の改変や新設に際して、施策の導入効果を定量的に評価でき、計画立案を支援できる交通流シミュレータによる交通流シミュレーションが求められている。交通流シミュレーションとは、交通規制や車両の経路等を交通流に反映させて交通全体に及ぼす影響を再現するシミュレーションをいう。
【０００３】
従来、ネットワークが大規模化した場合でも、個々の車両における経路決定処理時間及びトータルの計算時間を短縮することができる交通流シミュレーションにおける経路選択方式が開示されている（例えば、特許文献１を参照。）。
【０００４】
特許文献１に記載された交通流シミュレーションにおける経路選択方式は、各出発地及び各分岐点から目的地迄の最短経路における所要コストを事前に準備して記憶しておき、現在地から目的地迄の経路を順次、選択・決定していくことにより、個々の車両における経路決定処理時間を短縮するものである。
【０００５】
このような交通流シミュレーションでは、逐次経路を探索する手法（手法Ａ）、予め作成した候補経路から最適経路を選択する手法（手法Ｂ）のいずれかが用いられる。
【０００６】
手法Ａでは、車両発生時点にダイキストラ法などによって最適な経路を探索する。また、交通状況に応じて、走行途中で逐次経路探索することもある。手法Ｂでは、車両発生時点にその時点の道路状況を考慮して、ｄｉａｌの配分法などを用いて複数の候補経路の中から確率的に走行する経路を選択する。また、途中で経路を変更する場合は、手法Ａのように、走行途中の時点で経路を探索し、経路を変更する場合もある。
【特許文献１】特開２００２−１５７６７２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
手法Ａは、非常に計算量が多く、評価対象が広域のネットワークで多くの車両が走行する場合では、各車両の経路探索処理の計算時間が非常にかかってしまう問題がある。また、探索される経路が交通状況によって異なってしまい、個々の車両の経路が現実的であるかを確認することも困難である。更に、刻々と交通状況が変わる場合、ある地点を周回したり、非常に遠回りしたりするなど、現実的ではない経路が選択されることもある。
【０００８】
手法Ｂでは、コストの合計値が小さいものから順に複数の複数の候補経路が選択され、その場合、探索された経路の一部が他の経路に重複することがある。このような経路は、大部分のリンクが他の経路のリンクと重複しているため、候補経路として適さない。
【０００９】
また、リンクコストとして旅行時間が含まれているリンクが最小となる経路を探索する手法もある。この手法では、主要幹線の混雑を避けた細街路主体の経路となる場合が多く、現実の道路では運転者があまり選択しない経路が探索される。このような経路は、現実的ではなく、車両の候補経路に適さない問題があった。
【００１０】
本発明は、上述した課題を解決するために提案されたものであり、高速でかつ適切な経路を作成できる候補経路作成装置、方法、プログラムを提供することを目的とする。さらに、上記発明を用いて交通シミュレーションを行う交通シミュレーション装置、方法及びプログラム、上記発明を用いて経路を探索する経路探索装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明に係る候補経路作成装置は、複数のノードをリンクした道路ネットワークデータと、各ノードのＯＤ交通量データとに基づいて、該ＯＤ交通量データで指定される起点及び終点の組み合わせ毎に、起点から終点までの最適経路を探索する最適経路探索手段と、前記最適経路探索手段により探索された最適経路が交差するノード又は最適経路が分岐するノードを、分岐ノードとして抽出する分岐ノード抽出手段と、前記分岐ノード抽出手段により抽出された各分岐ノードを連結して簡略ネットワークを作成する作成手段と、前記作成手段により作成された簡略ネットワークの各分岐ノードを用いて、前記各最適経路の分岐ノード間のパスを抽出するパス抽出手段と、前記パス抽出手段により抽出された複数のパスを組み合わせて、前記各最適経路の候補経路を作成する候補経路作成手段と、を備えている。
【００１２】
最適経路探索手段によって探索される最適経路は、起点及び終点の組み合わせに対して１つである。よって、演算負荷の大きい最適経路探索は、起点及び終点の組み合わせに対して１回だけ行われる。
【００１３】
最適経路探索手段により探索された各最適経路が重なっている分岐ノードは、一般のドライバが比較的よく通過する場所と考えられる。そこで、分岐ノード抽出手段は、探索された各最適経路の重なり具合に基づいて、前記各最適経路の各ノードの中から分岐ノードを抽出する。
【００１４】
作成手段は、抽出された各分岐ノードを連結して簡略ネットワークを作成する。この簡略ネットワークは、一般のドライバがよく通過する場所を連結したときの最適経路を表している。
【００１５】
パス抽出手段は、簡略ネットワークの各分岐ノードを用いて、前記各最適経路の分岐ノード間のパスを抽出する。このパスは、最適経路やその他のパスと重複しないように、また、最適経路から大きく遠回りしないようにして抽出される。
【００１６】
候補経路作成手段は、抽出された複数のパスを組み合わせて、各最適経路の候補経路を作成する。これにより、最適経路と起点及び終点が同じであるが経路の異なる候補経路が作成される。
【００１７】
よって、本発明に係る候補経路作成装置は、起点から終点までの最適経路を探索し、各最適経路の重なり具合に基づいて各最適経路の各ノードの中から分岐ノードを抽出し、各分岐ノードを用いて各最適経路の分岐ノード間のパスを抽出し、抽出された複数のパスを組み合わせて各最適経路の候補経路を作成することにより、適切な候補経路を高速に作成することができる。
【００１８】
なお、本発明は、候補経路作成方法及びプログラムによっても実現可能である。
【００１９】
本発明に係る交通シミュレーション装置は、上記候補経路作成装置と、単位時間あたり所定数の車両を発生させる車両発生手段と、前記候補経路作成装置で探索された最適経路の走行負担を表すコストと、前記候補経路作成装置で作成された候補経路の走行負担を表すコストとを用いて、前記最適経路及びその候補経路の中から確率的に経路を選択する経路選択手段と、前記車両発生手段により発生された各車両を、前記経路選択手段により選択された経路の起点から終点に移動させる車両移動手段と、を備えている。
【００２０】
車両発生手段は、単位時間あたり所定数の車両を発生させる。車両は交通シミュレーション上のものである。経路選択手段は、候補経路作成装置で得られた最適経路及びその候補経路の中から確率的に経路を選択する。
【００２１】
確率的に経路を選択するために、候補経路作成装置で探索された最適経路の走行負担を表すコストと、候補経路作成装置で作成された候補経路の走行負担を表すコストとが用いられる。通常、コストが大きくなるに従ってドライバはそのコストに対応する経路を選ばなくなり、コストが小さくなるに従ってドライバはそのコストに対応する経路を選ぶようになる。よって、上述した各コストが用いられて、最適経路及びその候補経路の中から確率的に１つの経路が選択される。
【００２２】
車両移動手段は、車両発生手段により発生された各車両を、経路選択手段により選択された経路の起点から終点に移動させる。
【００２３】
よって、本発明に係る交通シミュレーション装置は、最適経路の走行負担を表すコストと、候補経路作成装置で作成された候補経路の走行負担を表すコストとを用いて、最適経路及びその候補経路の中から確率的に経路を選択し、単位時間あたり所定数発生された各車両を選択された経路の起点から終点に移動させることにより、高速に交通シミュレーションを行うことができる。なお、本発明は、交通シミュレーション方法及びプログラムによっても実現可能である。
【００２４】
本発明に係る経路探索装置は、現在位置を前記起点とし、目的地を前記終点として、前記現在位置から前記目的地までの最適経路を探索すると共に前記最適経路の候補経路を作成する上記候補経路作成装置と、前記候補経路作成装置で探索された最適経路の走行負担を表すコストと、前記候補経路作成装置で作成された候補経路の走行負担を表すコストとに基づいて、最もコストの小さい経路を探索する経路探索手段と、を備えている。
【００２５】
候補経路作成装置は、現在位置から目的までの１つの最適経路を探索すると共に、その最適経路とは異なる候補経路を作成する。経路探索手段は、探索された最適経路の走行負担を表すコストと、作成された候補経路の走行負担を表すコストとに基づいて、最もコストの小さい経路を探索する。
【００２６】
よって、本発明に係る経路探索装置は、現在位置から目的地までの経路を高速に探索することができる。なお、本発明は、経路探索方法及びプログラムによっても実現可能である。
【発明の効果】
【００２７】
本発明に係る候補経路作成装置、方法及びプログラムは、最適経路及びその候補経路を高速に作成することができる。
【００２８】
本発明に係る交通シミュレーション装置、方法及びプログラムは、複数の経路を走行する車両の交通シミュレーションを高速に行うことができる。
【００２９】
本発明に係る経路探索装置、方法及びプログラムは、高速に経路を探索することができる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の好ましい実施の形態について図面を参照しながら詳細に説明する。
【００３１】
［第１の実施形態］
図１は、本発明の第１の実施形態に係る交通シミュレーション装置の構成を示すブロック図である。
【００３２】
（全体構成）
交通シミュレーション装置は、道路ネットワークデータ等が入力される入力部１０と、最適経路を探索する経路探索処理部２０と、複数の候補経路を作成する候補経路作成処理部３０と、候補経路リストや分岐ノードリストを記憶するデータベース４０と、交通流を計算する交通流計算部５０と、交通流計算部５０による交通流シミュレーション結果を表示する表示部６０と、を備えている。
【００３３】
入力部１０には、外部から道路ネットワークデータ、ＯＤ交通量データが入力される。入力部１０は、これらのデータを経路探索処理部２０や交通流計算部５０に供給する。なお、入力部１０は、入力されたデータを経路探索処理部２０や交通流計算部５０に供給できれば特に限定されない。例えば、入力部１０は、キーボード、外部ネットーワークからデータを受信する入出力ポート、交通情報を受信するセンサ、光ディスクや磁気ディスク等の記録媒体から道路ネットワークデータ等を読み出す読出装置のいずれであってもよい。
【００３４】
（経路探索処理部２０の構成）
経路探索処理部２０は、入力部１０から供給された道路ネットワークデータと、ＯＤ交通量の起点及び終点とに基づいて、リンクコストの合計値が最小となる最適経路を探索する。なお、ＯＤ交通量とは、ある出発地（起点）から目的地（終点）までの起終点間の交通量をいい、例えば、交通需要の発生地点、集中地点における発生交通量や発生時間などがある。なお、経路の起点及び終点は、施設、工場、住宅地、商業地などがある地域の代表的な地点としてもよい。
【００３５】
図２は、道路ネットワークデータで表される道路ネットワークを示す図である。道路ネットワークは、交差点を表すノードを連結したリンクによって道路を簡略化したものである。同図において、ＯＤ交通量で入力された車両の起点及び終点となるノードは黒丸印で表され、それ以外のノードは白丸印で表されている。また、ノード間のリンクは１本の線で表されているが、実際は上り方向と下り方向とでリンクを別々にする。太いリンクは主要幹線道路、細いリンクは細街路を示している。
【００３６】
経路探索処理部２０は、次のようにして起点Ｎ１から終点Ｎ２まで走行する車両の最適経路を探索する。経路探索処理部２０は、例えばダイキストラ法を用いて、経路上のリンクコストの合計が最小となる経路を得る。リンクコストは、車両が該当リンクを走行するときの負担を表し、例えば式（１）によって計算される。
【００３７】
【数１】
0004736590.tif 000002
【００３８】
式（１）において、
Ｃ：リンクコスト
Ｔ：（方向別）リンク旅行時間
Ｌ：リンク長
Ｒｋ：道路種別
Ｒｗ：車線数
Ｄ：右左折の有無
Ｆ：通行料金
ｗ１〜ｗ６：重み係数
である。
【００３９】
重み係数ｗは、実際の道路でドライバが選択する経路に近いものが算出されるように調整される。重み係数ｗは、普通車、大型車などの車種別に設定されてもよい。リンク旅行時間Ｔは、直進、右折、左折などの方向別に求めてもよい。
【００４０】
リンク旅行時間Ｔは、交通状況に応じて変化するため、リンクコストＣに対する動的な（可変）パラメータである。リンク旅行時間Ｔ以外のパラメータは、交通状況にかかわらず一定であり、静的な（固定）パラメータである。
【００４１】
リンク旅行時間Ｔは、候補経路作成時やシミュレーション開始前の時点では、リンク長を制限速度で割った値を用いる。シミュレーション中では、前時間のシミュレーション結果によるリンク旅行時間Ｔの計算値を用いる。その値は、一定間隔（例えば５分間）のうちに、該当リンクを車両が走行した旅行時間などにより算出される。また、速度や旅行時間は、実際の道路で計測された値を用いてもよい。
【００４２】
図３は、シミュレーション開始前に経路探索処理部２０によって探索された最適経路Ｒ１N1-N2を示す図である。この経路Ｒ１N1-N2は、国道などの主要幹線を主に通って、距離が短くなるように算出されたものである。つまり、この経路Ｒ１N1-N2は、ドライバが閑散時間帯に走行する経路、地図を見て決定する経路、ナビゲーションシステムによる推奨経路と類似する経路となる。
【００４３】
図３では起点Ｎ１から終点Ｎ２までの経路を例に挙げたが、これに限定されるものではない。ＯＤ交通量で入力される交通需要は、対象地域の外から外、外から中、中から中などの様々な方向が表現される。
【００４４】
図４は、図３の対象地域内のその他の交通需要を示す図である。ここでは、起点Ｎ３から終点Ｎ４、起点Ｎ５から終点Ｎ６などの交通需要もある。経路探索処理部２０は、これらの交通需要についても最適経路Ｒ１N3-N4、Ｒ１N5-N6を探索する。そして、経路探索処理部２０は、ＯＤ交通量のすべての起点・終点の組に対して上述のように最適経路を探索し、探索した経路をデータベース４０の「候補経路リスト」に追加する。
【００４５】
（候補経路作成処理部３０）
候補経路作成処理部３０は、ＯＤ交通量の起点・終点の組毎に、最適経路と異なる複数の候補経路を作成する。候補経路を作成するために、（１）分岐ノードの抽出、（２）交通ネットワークの簡略化、（３）分岐ノード間のパスの抽出、（４）パスの組み合わせが行われる。
【００４６】
（分岐ノードの抽出）
ＯＤ交通量のすべての起点・終点の組毎の最適経路を重ねていくと、経路が交差するノードが存在する。例えば図４に示すように、ノードＮ９では、経路Ｒ１N1-N2と経路Ｒ１N3-N4が交差する。多くの経路が交差するノードは多くの車が通過するので、そのノードに対応する実際の交差点は交通量が多い主要交差点となる。このように経路が交差するノードを以下では「分岐ノード」という。分岐ノードの重ね具合は、単に経路が重なっていれば十分ではなく、一定の条件を満たす必要がある。
【００４７】
図５は、ノードｅにおいて経路が重なっている場合にノードｅが分岐ノードとして抽出される条件を説明する図である。同図（Ａ）の場合、車がノードａからノードｅに移動すると、次の移動先ノードの選択肢としてノードｂしかない（ノードｅからノードａに戻るのは意味がないので除外。）。よって、ノードｅは単なる通過点に過ぎないので、分岐ノードとはならない。
【００４８】
同図（Ｂ）の場合、車がノードａからノードｅに移動すると、次の移動先ノードの選択肢としてノードｂとノードｃがある。したがって、ノードｅは分岐ノードとして抽出される。同図（Ｃ）の場合、２つの経路がノードｅで交差しているので、ノードｅは分岐ノードとして抽出される。なお、本実施形態では、ノードから２通り以上の分岐が存在する場合にそのノードを分岐ノードとするが、これに限定されるものではない。例えば、分岐ノードの数を減らす必要がある場合、ノードから３通り以上の分岐が存在するノードのみを分岐ノードとしてもよい。
【００４９】
そして、候補経路作成処理部３０は、上述のように、対象地域においてすべての経路を重ね、上記の条件で順次分岐ノードを抽出し、分岐ノードを分岐ノードリストに追加していく。
【００５０】
（交通ネットワークの簡略化）
次に、候補経路作成処理部３０は、分岐ノード間が最適経路上で結ばれているものを、分岐ノード間を接続する部分（以下「パス」という。）として、そのノード列を記録する。
【００５１】
図６は、ノードＮ７、Ｎ８、Ｎ９をそれぞれ分岐ノードＰ２、Ｐ３、Ｐ４と定義したときのパスを説明する図である。分岐ノードＰ２とＰ３は経路Ｒ１N1-N2が通過しており、分岐ノードＰ２とＰ３間はノードＮ７、Ｎ８、Ｎ９を結ぶパスで接続されている。そこで、候補経路作成処理部３０は、このような分岐ノード間Ｐ２−Ｐ３、その分岐ノード間のパスを構成するノード列Ｎ７、Ｎ８、Ｎ９、その分岐ノード間を接続する接続リンク（以下「分岐ノード接続リンク」という。）ＬP2-P3を次のように記録する。
【００５２】
図７は、候補経路作成処理部３０によって記録される分岐ノード間、ノード列、分岐ノード接続リンクの対応関係表を示す図である。候補経路作成処理部３０は、例えば分岐ノード間Ｐ３−Ｐ４については、上記対応関係表に、分岐ノード間Ｐ３−Ｐ４、ノード列Ｎ９、Ｎ１０、分岐ノード接続リンクＬP3-P4を記録する。そして、候補経路作成処理部３０は、分岐ノードと分岐ノード接続リンクとに基づいて、図２に示した交通ネットワークを簡略化したもの（以下「簡略ネットワーク」という。）を作成する。
【００５３】
図８は、候補経路作成処理部３０によって作成された簡略ネットワークを示す図である。簡略ネットワークは、複数の分岐ノードと、分岐ノード間を接続する複数の分岐ノード接続リンクと、で構成されている。
【００５４】
以上の説明では、候補経路作成処理部３０が実際の道路状況に即した分岐地点を自動的に抽出する例を挙げたが、これに限定されるものではない。例えば、分岐ノードとして抽出されたノードが実際の道路状況と比較して分岐地点としてふさわしくない、とユーザが判断した場合、ユーザは分岐ノードの候補からそのノードを削除してもよい。また、ユーザは、分岐ノードとして候補経路作成処理部３０に抽出されなかったノードを、新たに分岐ノードとして登録してもよい。
【００５５】
ユーザによって分岐ノードが編集された場合、候補経路作成処理部３０は、再度、簡略ネットワークを作成する。また、分岐ノードがリストから追加、削除され、分岐ノード間のパスが存在しなくなった場合、経路探索処理部２０がダイキストラ法などを用いて分岐ノード間の最適経路を探索して、パスを見つければよい。なお、分岐ノードの追加、削除、編集等の情報は、入力部１０から入力される。
【００５６】
また、ユーザは、すべての分岐ノードを手動で登録してもよい。この場合、経路探索処理部２０は、分岐ノード間、起点ノード−分岐ノード間、分岐ノード−終点ノード間について最適経路を探索して、パスを求めればよい。そして、候補経路作成処理部３０は、分岐ノードによる簡略ネットワークを作成すればよい。
【００５７】
（分岐ノード間のパスの抽出）
次に、候補経路作成処理部３０は、簡略ネットワークに基づき、各起点−終点間について複数の候補経路を作成する。ここでは、起点Ｎ１から終点Ｎ２までの経路Ｒ１N1-N2の複数の候補経路を作成する例について説明する。
【００５８】
図９は、簡略ネットワークにおける起点Ｎ１から終点Ｎ２までの経路Ｒ１N1-N2を示す図である。経路Ｒ１N1-N2は、起点ノード、分岐ノード、終点ノード（Ｎ１→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６→Ｐ７→Ｎ２）で表現される。この経路Ｒ１N1-N2を分割して、分岐ノード間のパスを検討する。例えば、Ｐ２からＰ６までのパスは分岐ノード列Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６で構成されている。そこで、候補経路作成処理部３０は、この分岐ノード列をＰ２からＰ６までの第１のパスとして抽出して登録する。
【００５９】
図１０は、候補経路作成処理部３０によって登録された分岐ノード列及びそのコストを示す図である。候補経路作成処理部３０は、分岐ノード列Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６のコストを演算し、その分岐ノード列を第１のノード（番号１）として登録すると共に、そのコストも登録する。なお、コストの演算は式(１)を用いてもよいし、その他の式を用いてもよい。
【００６０】
図１１は、起点Ｎ１から終点Ｎ２までの別の経路Ｒ１’N1-N2を示す図である。Ｒ１’N1-N2におけるＰ２からＰ６までのパスは、分岐ノード列Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ６で構成されている。これは、第１のパスと異なるパスである。そこで、候補経路作成処理部３０は、分岐ノード列Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ６のコストを演算し、その分岐ノード列を第２のノード（番号２）として登録すると共に、そのコストも登録する。
【００６１】
候補経路作成処理部３０は、このようにすべての経路の各分岐ノード間において複数のパスを順次登録する。しかし、パスが一定の条件を満たさない場合、そのパスは登録されない。
【００６２】
図１２は、２つ目以降のパスが登録されない例を示す図である。例えば、Ｐ１からＰ３までの２つ目のパスを探索するとき、以下の条件が付加されて、起点をＰ１、終点をＰ３として最適経路の探索が実施される。
【００６３】
条件１：途中で経路Ｒ１N1-N2上の別の（Ｐ１、Ｐ３以外の）分岐ノードを通らない。
【００６４】
条件２：新たなパスのコストは第１のパスのコストの１．５倍以内である。
【００６５】
条件１は、新たなパスの全部又は一部は既に登録されている簡略ネットワーク上の経路（又はパス）を通ってはいけない、ことを意味する。これにより、Ｐ１−Ｐ３間では、パスＰ１→Ｐ２→Ｐ３を除くと、図１２に示すように、パスＰ１→Ｐ１１→Ｐ１２→Ｐ９→Ｐ１４→Ｐ１３→Ｐ３がパスの候補となる。なお、最適経路探索が実行されてもパスの候補が見つけられなかった場合、パスはないものとする。
【００６６】
しかし、別の候補となるパスのコストが第１のパスのコストと比較して非常に大きくなる場合、そのパスは非常に遠回りするパスと考えられ、パスとしては不適切である。そのようなパスを排除するため、条件２が用いられる。
【００６７】
図１２の場合、パスＰ１→Ｐ１１→Ｐ１２→Ｐ９→Ｐ１４→Ｐ１３→Ｐ３のコストは、パスＰ１→Ｐ２→Ｐ３のコストの１．５倍以上になる。そのため、パスＰ１→Ｐ１１→Ｐ１２→Ｐ９→Ｐ１４→Ｐ１３→Ｐ３は、適切なパスではないため、除外される。
【００６８】
候補経路作成処理部３０は、以上のように最適経路（本実施形態では経路Ｒ１N1-N2）上の各分岐ノード間の複数のパスを探索して、次のような複数のパスを抽出する。
【００６９】
図１３は、経路Ｒ１N1-N2の複数のパスを示す図である。図１４は、候補経路作成処理部３０によって登録された最終的な分岐ノード列及びそのコストを示す図である。図１４によると、最適経路Ｒ１N1-N2の各分岐ノードのうちＰ１、Ｐ２、Ｐ３、Ｐ４において分岐できるパスが存在する。
【００７０】
（パスの組み合わせ）
候補経路作成処理部３０は、分岐ノード間のパスを組み合わせることによって、起点Ｎ１から終点Ｎ２について、最適経路Ｒ１N1-N2以外に、次の４通りの候補経路Ｒ２、Ｒ３、Ｒ４、Ｒ５を新たに作成できる。
【００７１】
Ｒ２N1-N2：Ｎ１→Ｐ１→Ｐ１１→Ｐ１２→Ｐ９→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ３N1-N2：Ｎ１→Ｐ１→Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ４N1-N2：Ｎ１→Ｐ１→Ｐ２→Ｐ３→Ｐ１３→Ｐ１４→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ５N1-N2：Ｎ１→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ１５→Ｐ１６→Ｐ１７→Ｐ７→Ｎ２
なお、下線部は、経路Ｒ１N1-N2から分岐した分岐ノードを示す。そして、候補経路作成処理部３０は、このように作成した経路Ｒ２、Ｒ３、Ｒ４、Ｒ５を、データベース４０の候補経路リストに追加する。
【００７２】
したがって、経路探索処理部２０が道路ネットワークデータ及びＯＤ交通量データに基づいて最適経路を探索し、候補経路作成処理部３０がその最適経路の分岐ノードから複数の候補経路を作成する。これにより、計算量の多い最適経路の探索が１回だけですむので、起点から終点までの複数の経路を高速に作成することができる。
【００７３】
また、候補経路作成処理部３０は、起点及び終点の異なる最適経路の重なり具合に基づいて分岐ノードを抽出し、分岐ノード間をリンクして複数の経路を作成するので、実際の車両がよく通行しそうな経路を作成することができる。換言すると、一般のドライバがほとんど使用しない経路が作成されるのを回避することができる。
【００７４】
（交通流計算部５０）
交通流計算部５０は、車両を発生する車両発生処理部５１と、各車両について確率的に経路を選択する経路選択処理部５２と、選択された経路上に車両を移動させる車両移動処理部５３と、を備えている。
【００７５】
車両発生処理部５１は、単位時間当たり所定数の交通シミュレーション上の車両を発生する。発生した車両は、経路選択処理部５２によって選択される経路の起点に配置される。
【００７６】
経路選択処理部５２は、車両発生処理部５１で発生した車両毎に、経路探索処理部２０で探索された最適経路と候補経路作成処理部３０で作成された候補経路の中から確率的に経路を選択する。
【００７７】
（経路選択行動の要因）
交通シミュレーションで車両の経路選択行動を表現するためには、ドライバの経路選択の要因を分類する必要がある。ドライバの経路選択行動の要因として以下のものが挙げられる。
【００７８】
（１）通常の交通状況を把握しているか、全く知らないか
通勤、通学をしているドライバは、既にその地域を何度も走行しており、おおよその渋滞発生地帯や渋滞状況を把握している。このようなドライバは、「早朝なら主要幹線中心の経路を選択し、通勤時間帯なら主要幹線の渋滞を避けた他の経路を選択する。」のように、選択する経路を交通状況に応じて決定する。それに対して、その地域を初めて走行する土地勘のないドライバは、地図やナビゲーションシステムを参考にして経路を決定する。この場合、ドライバは、交通状況が分からず、静的な要因で経路を決定するため、経路として主に主要幹線を選択する。
【００７９】
（２）交通情報の受信手段があるか、無いか
ＶＩＣＳ（Vehicle Information and Communication System）付きナビゲーションシステムや携帯電話を使った交通情報サービスの受信手段がある車両のドライバは、現在地よりも遠方の交通状況を知ることができる。よって、そのようなドライバは、現在地より遠方の経路上の地点の渋滞情報を受信した場合、現在地付近が渋滞していなくても、遠方の渋滞地点を迂回するように、経路変更を検討する。一方、交通情報を受信する手段がない車両のドライバは、周辺の交通状況しか認識できず、目前の渋滞に遭遇した場合にのみ経路変更を検討する。
【００８０】
（３）経路変更を好むか、好まないか
渋滞に遭遇した場合、すぐに別の経路に変更するドライバや、あまり経路変更をしたらがないドライバなどがいる。これは、経路変更を検討するドリガーとなる条件が異なると考えられる。
【００８１】
以上のような経路選択行動に関するドライバ・車両の要因を考慮して、経路選択が行われる。
【００８２】
（経路選択処理部５２の処理）
経路選択処理部５２は、車両発生処理部５１で発生された車両が経路を選択する際に、各経路を選択する確率を式(２)に示すロジットモデルにより決定する。
【００８３】
【数２】
0004736590.tif 000003
【００８４】
ここで、
ｎ：この起点、終点に対する全経路数
Ｐk：経路ｋを選択する確率
Ｃk：経路ｋのリンクコスト合計
θ：コストに対する経路選択確率の敏感さを表す感度パラメータ
である。
【００８５】
θについては後述する。また、経路ｋの各リンクのリンクコストは式（１）で求められる。リンクコストを求めるためのリンク旅行時間Ｔは、ドライバの要因別に、以下の２つの方式のいずれかが用いられる。
【００８６】
方式１−Ａ：前時間（例えば、所定サンプリング時間毎にシミュレーション計算が行われる場合では１サンプリング前の時間）のシミュレーション計算で得られたリンク旅行時間Ｔ、又は、実測のリンク旅行時間Ｔ
方式１−Ｂ：最高速度でリンクを走行したときのリンク旅行時間Ｔ、又は、リンク旅行時間Ｔ＝０（係数ｗ１＝０としても可）
渋滞が発生している状況では、リンク旅行時間Ｔが変化する。ドライバが走行地域の交通状況に関する知識がある場合は方式１−Ａ、その知識がない場合は方式１−Ｂに従ってリンク旅行時間Ｔが求められ、そして、経路ｋのリンクコストの合計が計算される。なお、方式１−Ｂでは、リンク旅行時間Ｔを所定値（最高速度でリンクを走行したときの旅行時間、又はゼロ）に設定することによって、リンク旅行時間Ｔを無視している。したがって、旅行時間Ｔの情報があるときは方式１−Ａ、旅行時間Ｔの情報がないときは方式１−Ｂに切り替えるとよい。
【００８７】
例えば、起点Ｎ１から終点Ｎ２までを走行する車両の場合、経路選択処理部５２は、図１２に示す各経路
Ｒ１N1-N2：Ｎ１→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６→Ｐ７→Ｎ２
Ｒ２N1-N2：Ｎ１→Ｐ１→Ｐ１１→Ｐ１２→Ｐ９→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ３N1-N2：Ｎ１→Ｐ１→Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ４N1-N2：Ｎ１→Ｐ１→Ｐ２→Ｐ３→Ｐ１３→Ｐ１４→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ５N1-N2：Ｎ１→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ１５→Ｐ１６→Ｐ１７→Ｐ７→Ｎ２
について、各々リンクコストの合計を計算した後に式(２)を計算し、確率的にＲ１〜Ｒ５のいずれかの経路を選択する。
【００８８】
図１５は、確率的に経路を選択することを説明する図である。なお、Ｐ1〜Ｐ5は、式（２）によって求められたＲ１N1-N2〜Ｒ５N1-N2の確率である。経路選択処理部５２は、Ｐ1〜Ｐ5を計算し、図５に示すように、これらを累積する。
【００８９】
例えば、Ｐ1＝０．４０、Ｐ2＝０．２６、Ｐ3＝０．１７、Ｐ4＝０．１０、Ｐ5＝０．０７とすると、累積された確率Ｐ1〜5の範囲は次のようになる。
【００９０】
累積された確率Ｐ1の範囲：０．００以上０．４０未満
累積された確率Ｐ2の範囲：０．４０以上０．６６未満
累積された確率Ｐ3の範囲：０．６６以上０．８３未満
累積された確率Ｐ4の範囲：０．８３以上０．９３未満
累積された確率Ｐ5の範囲：０．８９以上１．００未満
次に、経路選択処理部５２は、乱数（０〜１．０）を発生し、発生した乱数が累積確率Ｐ1〜Ｐ5のいずれの範囲に対応するかに基づいて経路を選択する。例えば、乱数が０．５の場合は累積確率Ｐ2に対応する経路Ｒ２が選択され、乱数が０．８０の場合は累積確率Ｐ3に対応する経路Ｒ３が選択される。
【００９１】
そして、車両移動処理部５３は、車両発生処理部５１で発生された車両を、経路選択処理部５２で選択された経路の起点から終点に向かって移動させる処理を行う。車両が経路上を移動して次の分岐ノードに達する前に、経路選択処理部５２はその分岐ノードにおいて経路を変更するか否かを判断する。
【００９２】
（経路変更の条件）
図１６は、経路Ｒ１N1-N2の分岐ノードにおいて経路を変更するか否かの判断を説明する図である。ここでは、分岐ノードＰ２からＰ３にかけて渋滞Ａが発生したものとする。
【００９３】
車両発生処理部５１で発生された車両が経路ＲN1-N2を選択した場合、その経路ＲN1-N2には分岐ノードＰ１、Ｐ２、Ｐ３、Ｐ４からそれぞれ分岐するパスが存在する。このため、車両は、分岐ノードの手前で別のパスを選択（経路を変更）することが可能である。しかし、経路変更が可能な地点で必ずしも経路は変更されない。例えば、渋滞が無く順調に走行できる場合は、ドライバは経路を変更する必要がない。また、現在の選択した経路上で渋滞が発生している場合、ドライバは経路を変更するか否かを検討する。
【００９４】
ここで、渋滞に遭遇しても、経路変更を検討するか否かの判断はドライバによって異なる。そこで、経路選択処理部５２は、ドライバの経路選択の嗜好性を予め設定することができる。
【００９５】
図１７は、ドライバの経路選択の嗜好性を示す図である。図１７によると、経路変更の嗜好性が大きいドライバは、旅行時間が閑散時の２倍以上になったときに、経路を変更する。経路変更の嗜好性が小さいドライバは、旅行時間が閑散時の４倍以上になったときに、経路を変更する。経路変更の嗜好性が中程度のドライバは、旅行時間が閑散時の３倍以上になったときに、経路を変更する。
【００９６】
経路変更の嗜好性を有するドライバの分布の度合いは、ドライバの経路選択の統計に沿って設定されてもよい。
【００９７】
また、交通情報を受信する手段がない車両のドライバは、周辺の交通状況しか認識できないため、経路変更が可能な分岐ノードの手前で、進行中の直前のリンクが渋滞した場合のみ経路変更を検討する。交通情報を受信する手段がある車両のドライバは、遠方の交通情報も知ることができるため、経路上のリンクに渋滞が発生した場合は、経路変更が可能な分岐ノードの手前ならばどこでも経路変更を検討できる。
【００９８】
（経路変更時の経路選択方法）
走行途中での経路変更する時の経路選択においては、途中の地点（分岐ノード）から終点までの部分的な経路（以下「部分経路」という。）が選択される。例えば、図１５の分岐ノードＰ２の手前で経路選択が行われる場合、分岐ノードＰ２から終点Ｎ２までの経路としては、経路上の分岐ノード間のパスの組み合わせによって、次のような部分経路が存在する。
Ｒ１P1-N2：Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６→Ｐ７→Ｎ２
Ｒ２P1-N2：Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ３P1-N2：Ｐ２→Ｐ３→Ｐ１３→Ｐ１４→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ４P1-N2：Ｐ２→Ｐ３→Ｐ４→Ｐ１５→Ｐ１６→Ｐ１７→Ｐ７→Ｎ２
各部分経路を選択する確率は、式（３）のロジットモデルにより決定される。
【００９９】
【数３】
0004736590.tif 000004
【０１００】
ここで、
ｎ：この分岐ノードａに対する部分経路数
Ｐａk：分岐ノードａに対する経路ｋを選択する確率
Ｃａk：分岐ノードａに対する経路ｋのリンクコスト合計
θ：コストに対する経路選択確率の敏感さを表す感度パラメータ
である。
【０１０１】
対象となる部分経路の各リンクのリンクコストは式（１）で求められる。対象とする部分経路は、ドライバの要因別に、以下の２つの方式のいずれかによって選択される。
方式２−Ａ：経路変更する分岐ノードから終点までのすべての部分経路を対象に、部分経路のリンクコストの合計値を求め、式（３）で確率的に部分経路を選択する方式
方式２−Ｂ：経路変更する分岐ノードからパスが存在する経路上の最も手前の分岐ノードまでの部分経路を対象に、部分経路のリンクコストの合計値を求め、式（３）で確率的に部分経路を選択する方式
図１６の分岐ノードＰ２で経路を変更する場合、方式２−Ａ又は方式２−Ｂによって次のような部分経路が選択される。
【０１０２】
方式２−Ａによって選択される部分経路は
Ｒ１P1-N2：Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６→Ｐ７→Ｎ２
Ｒ２P1-N2：Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ３P1-N2：Ｐ２→Ｐ３→Ｐ１３→Ｐ１４→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
Ｒ４P1-N2：Ｐ２→Ｐ３→Ｐ４→Ｐ１５→Ｐ１６→Ｐ１７→Ｐ７→Ｎ２
の４つである。
【０１０３】
方式２−Ｂによって選択される部分経路は
Ｒ１P2-P6：Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６
Ｒ２P2-P6：Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ６
Ｒ３P2-P6：Ｐ２→Ｐ３→Ｐ１３→Ｐ１４→Ｐ１０→Ｐ６
の３つである。
【０１０４】
方式２−Ｂにおいて、上記の部分経路が選択されたのは、経路上で分岐ノードＰ２からのパスが存在する分岐ノードであって、分岐ノードＰ２から最も手前の（近い）分岐ノードはＰ６であるためである。その理由として、分岐ノードＰ３は、Ｐ２からパス（Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ１４→Ｐ１３→Ｐ３）が存在する分岐ノードであって、Ｐ２から最も手前の分岐ノードである。しかし、このパスのコストはパスＰ２→Ｐ３のコストの１．５倍以上になるため、このパスは不適切とみなされて、分岐ノードＰ３は方式２−Ｂで対象となる分岐ノードから除外される。また、分岐ノードＰ４、Ｐ５は、分岐ノードＰ２からのパスが存在しない。分岐ノードＰ６は、分岐ノードＰ２からのパス（Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ６）が存在する。よって、方式２−Ｂによって、分岐ノードＰ２からＰ６までの各パスＲ１〜３P2-P6が選択可能な部分経路となる。
【０１０５】
そして、部分経路として例えばＲ３P2-P6が選択された場合、分岐ノードＰ２から終点Ｎ２までの部分経路は
Ｒ３P2-N2：Ｐ２→Ｐ３→Ｐ１３→Ｐ１４→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
となる。
【０１０６】
このように、経路選択処理部５２は、車両が経路上の次の分岐ノードに達する前に、方式２−Ａ又は方式２−Ｂに従って複数の部分経路を選択し、各部分経路のリンクコストの合計を計算した後に式(３)を計算し、確率的にいずれか１つの部分経路を選択する。
【０１０７】
なお、方式２−Ａの対象となる車両は交通情報の受信手段がある車両であるので、その車両のドライバは車両周辺及び遠方の交通状況（渋滞Ａ及びＢ）を分かっている。よって、図１６に示す渋滞Ａ及び渋滞Ｂが考慮されて各部分経路のコストが計算され、最もコストの小さい部分経路が選択される。
【０１０８】
一方、方式２−Ｂの対象となる車両は交通情報の受信手段がない車両であるので、その車両のドライバは車両周辺の交通状況（渋滞Ａ）しか分かっていない。この場合、ドライバは、渋滞Ａのみを避ける経路を考える。よって、車両位置に近い範囲における部分経路のコストが計算され、最もコストの小さい部分経路が選択される。
【０１０９】
図１８は、ドライバの経路選択行動の要因と経路選択方式の関係を示す図である。同図によると、交通情報の入手（受信）手段がある車両のドライバの場合、その地域の交通状況に関する知識の有無にかかわらず、経路選択処理部５２は、車両発生時に方式１−Ａによって経路を選択し、途中から経路を変更する時は方式２−Ａによって経路を変更する。経路変更を判断する地点は、すべての経路変更可能な分岐ノードの手前である。
【０１１０】
交通情報の入手手段がない車両のドライバであって、その地域の交通状況に関する知識のないドライバの場合、経路選択処理部５２は、車両発生時に方式１−Ｂによって経路を選択し、途中から経路を変更する時は方式２−Ｂによって経路を変更する。交通情報の入手手段がない車両のドライバであって、その地域の交通状況に関する知識のあるドライバの場合、経路選択処理部５２は、車両発生時に方式１−Ａによって経路を選択し、途中から経路を変更する時は方式２−Ｂによって経路を変更する。経路変更を判断する地点は、渋滞が発生している直前の分岐ノードの手前である。
【０１１１】
経路選択処理部５２は、このようなドライバの経路選択行動の要因と経路選択方式を、車両発生処理部５１で発生された車両毎にランダムに決定してもよいし、統計データ（単位台数あたりの交通情報受信手段を有する車両の台数、ドライバの経路選択パターン等）を考慮して決定してもよい。
【０１１２】
以上のように、第１の実施形態に係る交通シミュレーション装置は、道路ネットワークデータ及びＯＤ交通量データに基づいて最適経路を探索し、その最適経路の分岐ノードから複数の候補経路を作成する。これにより、演算負荷の大きい最適経路の探索を１回だけですませて複数の経路を作成するので、交通シミュレーションの計算を高速に行うことができる。
【０１１３】
また、交通シミュレーション装置は、起点及び終点の異なる最適経路の重なり具合に基づいて分岐ノードを抽出し、分岐ノード間をリンクして複数の経路を作成するので、車両が実際によく通行しそうな経路を使って交通シミュレーションを行うことができる。
【０１１４】
さらに、上記交通シミュレーション装置は、ドライバの経路選択の特徴、車両の交通情報受信手段の有無を考慮して、分岐ノードにおいてどのような経路が選択されるかをシミュレーションすることができる。すなわち、実際のドライバの経路選択行動に近い状況で交通シミュレーションを実行できるので、シミュレーションの精度を向上させることができる。また、交通シミュレーション装置は、経路探索処理を行うことなく走行途中の経路を変更できるので、演算負荷が小さく済み、高速で交通シミュレーションを行うことができる。なお、交通シミュレーション装置は、経路変更後に再び経路変更を行うことも可能である。
【０１１５】
図１９は、経路変更後に再び経路変更を行うことを説明する図である。車両発生時に経路ＲN1-N2以外の経路が選択された場合や途中で経路が変更された場合でも、再度経路変更可能である。ここでは、経路
Ｒ３N1-N2：Ｎ１→Ｐ１→Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ６→Ｐ７→Ｎ２
の途中から別の経路に変更することを説明する。
【０１１６】
上述した図１４によると、分岐ノード間Ｐ１０→Ｐ７では、上記の分岐ノードＰ６を通るパスのほかに、分岐ノードＰ１８を通るパスも存在する。そこで、経路選択処理部５２は、
Ｒ７N1-N2：Ｎ１→Ｐ１→Ｐ２→Ｐ８→Ｐ９→Ｐ１０→Ｐ１８→Ｐ１９→Ｐ７→Ｎ２
の経路に変更することも可能である。
【０１１７】
ただし、経路変更が繰り返されると、必要以上に遠回りする経路が選択される可能性がある。そこで、経路選択処理部５２は、「選択しようとする経路のコストが車両発生時に選択した経路のコストの２倍以内になる」条件を付加してもよい。
【０１１８】
［第２の実施形態］
つぎに、本発明の第２の実施形態について説明する。なお、第１の実施形態と同一の部位には同一の符号を付し、その詳細な説明は省略する。
【０１１９】
図２０は、第２の実施形態に係る経路探索装置の構成を示すブロック図である。経路探索装置は、車載型であってもよいし、ネットワークに接続されたコンピュータであってもよい。
【０１２０】
経路探索装置は、道路ネットワークデータ等が入力される入力部１０と、最適経路を探索する経路探索処理部２０と、複数の候補経路を作成する候補経路作成処理部３０と、候補経路データや分岐ノードデータを記憶するデータベース４０と、経路を選択する経路選択部５５と、選択された経路を表示する表示部６０とを備えている。
【０１２１】
入力部１０は、外部から道路ネットワークデータ、ＯＤ交通量データを入力し、これらのデータを経路探索処理部２０や経路選択部５５に供給する。なお、入力部１０は、入力されたデータを経路探索処理部２０や経路選択部５５に供給できれば特に限定されない。例えば、入力部１０は、外部ネットーワークからデータを受信する入出力ポート、交通情報を受信するセンサ、光ディスクや磁気ディスク等の記録媒体から道路ネットワークデータ等を読み出す読出装置、車両の現在位置情報を受信するＧＰＳセンサ等のいずれであってもよい。
【０１２２】
経路探索処理部２０は、現在位置を前記起点とし、目的地を前記終点として、現在位置から目的地までの最適経路を探索する。なお、現在位置は、ＧＰＳセンサで受信された情報が表す位置であってもよいし、ドライバ又はオペレータによって設定された位置であってもよい。候補経路作成処理部３０は、経路探索処理部２０で探索された最適経路の候補経路を作成する。
【０１２３】
経路選択部５５は、経路探索処理部２０で探索された最適経路のリンクコストの合計値、候補経路作成処理部３０で作成された候補経路のリンクコストの合計値を計算する。リンクコストは、式（１）により求められる。そして、経路選択部５５は、最もリンクコストの合計値が大きい経路を選択し、その選択結果を表示部６０に供給する。これにより、表示部６０には、現在位置から目的地までの経路が表示される。
【０１２４】
以上のように、第２の実施形態に係る経路探索装置は、道路ネットワークデータ及びＯＤ交通量データに基づいて最適経路を探索し、最適経路の分岐ノードから複数の候補経路を作成する。これにより、計算量の多い最適経路の探索が１回だけですむので、現在位置から目的までの候補経路を高速に作成できる。よって、現在位置から目的までの経路探索を高速に行うことができる。
【０１２５】
また、経路探索装置は、起点及び終点の異なる最適経路の重なり具合に基づいて分岐ノードを抽出し、分岐ノード間をリンクして複数の経路を作成するので、実際の車両がよく通行しそうな候補経路の中から、走行負担の小さい経路を探索することができる。
【０１２６】
なお、本発明は、上述した実施の形態に限定されるものではなく、特許請求の範囲に記載された範囲内で設計上の変更をされたものにも適用可能であるのは勿論である。
【０１２７】
上述した実施形態において、「条件２：新たなパスのコストは第１のパスのコストの１．５倍以内である。」、「選択しようとする経路のコストが車両発生時に選択した経路のコストの２倍以内になる」という条件を用いたが、１．５倍、２倍という数値は特に限定されるものではない。また、経路探索処理部２０、候補経路作成処理部３０、交通流計算部５０（又は経路選択部５５）は、それぞれ異なるコンピュータで構成されてもよいし、同一のコンピュータで構成されてもよい。
【図面の簡単な説明】
【０１２８】
【図１】本発明の第１の実施形態に係る交通シミュレーション装置の構成を示すブロック図である。
【図２】道路ネットワークデータで表される道路ネットワークを示す図である。
【図３】シミュレーション開始前に経路探索処理部によって探索された最適経路Ｒ１N1-N2を示す図である。
【図４】図３に示した対象地域内のその他の交通需要を示す図である。
【図５】ノードｅにおいて経路が重なっている場合にノードｅが分岐ノードとして抽出される条件を説明する図である。
【図６】ノードＮ７、Ｎ８、Ｎ９をそれぞれ分岐ノードＰ２、Ｐ３、Ｐ４と定義したときのパスを説明する図である。
【図７】候補経路作成処理部によって記録される分岐ノード間、ノード列、分岐ノード接続リンクの対応関係表を示す図である。
【図８】候補経路作成処理部によって作成された簡略ネットワークを示す図である。
【図９】簡略ネットワークにおける起点Ｎ１から終点Ｎ２までの経路Ｒ１N1-N2を示す図である。
【図１０】候補経路作成処理部によって登録された分岐ノード列及びそのコストを示す図である。
【図１１】起点Ｎ１から終点Ｎ２までの別の経路Ｒ１’N1-N2を示す図である。
【図１２】２つ目以降のパスが登録されない例を示す図である。
【図１３】経路Ｒ１N1-N2の複数のパスを示す図である。
【図１４】候補経路作成処理部によって登録された最終的な分岐ノード列及びそのコストを示す図である。
【図１５】確率的に経路を選択することを説明する図である。
【図１６】経路Ｒ１N1-N2の分岐ノードにおいて経路を変更するか否かの判断を説明する図である。
【図１７】ドライバの経路選択の嗜好性を示す図である。
【図１８】ドライバの経路選択行動の要因と経路選択方式の関係を示す図である。
【図１９】経路変更後に再び経路変更を行うことを説明する図である。
【図２０】第２の実施形態に係る経路探索装置の構成を示すブロック図である。
【符号の説明】
【０１２９】
１０  入力部
２０  経路探索処理部
３０  候補経路作成処理部
４０  データベース
５０  交通流計算部
５１  車両発生処理部
５２  経路選択処理部
５３  車両移動処理部
５５  経路選択部
６０  表示部
【図１】
0004736590.tif 000005
【図２】
0004736590.tif 000006
【図３】
0004736590.tif 000007
【図４】
0004736590.tif 000008
【図５】
0004736590.tif 000009
【図６】
0004736590.tif 000010
【図７】
0004736590.tif 000011
【図８】
0004736590.tif 000012
【図９】
0004736590.tif 000013
【図１０】
0004736590.tif 000014
【図１１】
0004736590.tif 000015
【図１２】
0004736590.tif 000016
【図１３】
0004736590.tif 000017
【図１４】
0004736590.tif 000018
【図１５】
0004736590.tif 000019
【図１６】
0004736590.tif 000020
【図１７】
0004736590.tif 000021
【図１８】
0004736590.tif 000022
【図１９】
0004736590.tif 000023
【図２０】
0004736590.tif 000024