(57)【要約】【課題】渋滞の発生を予め予測して、渋滞の解消に寄与するような実用的な経路を複数探索することができる経路探索装置を提供する。【解決手段】ＯＤ交通量分割部１４Ａは、ＯＤ交通量Ｄ２をＯＤ1〜ＯＤnのｎ個に分割し、ＯＤ交通量が徐々に増加するようにｎ回に分けて出力する。経路探索部１４Ｂは、記憶装置１０から入力される道路ネットワークデータＤ１、ＯＤ交通量分割部１４Ａから入力される分割されたＯＤ交通量データＤ３、及び交通流シミュレータ１４Ｃから出力された旅行時間Ｄ４を入力として、候補経路を選定し、候補径路データＤ５を出力する。交通流シミュレータ１４Ｃは、道路ネットワークデータＤ１、ＯＤ交通量データＤ３、及び経路探索部１４Ｂで選択された経路を含む複数の候補経路を示す候補径路データＤ５を入力として、シミュレーションを行い、道路ネットワーク上の各リンクに対する時間帯別の旅行時間を算出する。【選択図】図２
2004198165.tif 000002
【特許請求の範囲】
【請求項１】
道路ネットワーク上を複数の車両が走行する場合に、所定の出発地点から所定の目的地点に至るのに最適な経路を探索する経路探索装置において、
出発地点と目的地点との間の全ＯＤ交通量を複数に分割すると共に、出力されるＯＤ交通量が徐々に増加するように、分割されたＯＤ交通量を適宜組み合せて順次出力するＯＤ交通量分割手段と、
道路ネットワーク上の各リンクの旅行時間を設定した場合に、道路ネットワークを表す道路ネットワークデータと前記ＯＤ交通量分割手段から入力されたＯＤ交通量とに基づいて、設定された前記旅行時間の下でコストの合計が最小となる候補経路を選定する候補経路選定手段と、
前記候補経路選定手段で選定された候補経路に、複数の車両を走行させてシミュレーションを実施するシミュレーション手段と、
を含む経路探索装置。
【請求項２】
前記シミュレーション手段は、得られたシミュレーション結果に基づいて道路ネットワーク上の各リンクの最大旅行時間を算出し、前記候補経路選定手段は、算出した前記最大旅行時間を旅行時間と仮定して候補経路を選定する請求項１に記載の経路探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路探索装置に係り、特に、道路ネットワーク上の所望の出発地から目的地までの経路を探索する経路探索装置に関する。
【０００２】
【従来の技術】
交通情報システムは、ドライバーに動的な交通情報を提供することによって、個々の車両の旅行時間を短縮するだけでなく、車両が特定の道路に集中するのを防ぎ、交通渋滞を緩和する方策として期待されている。
【０００３】
ドライバーに動的な交通情報を提供する技術として、予め設定された各リンクのコストの初期値を用いて最適経路を検出し、この最適経路に基づいてシミュレーションを行い、その際の遅延率が所定の値以上であった場合には、所定のルールにしたがってコストを修正し、再度最適経路を検索し、シミュレーションを行う経路探索方法が提案されている（特許文献１参照）。
【０００４】
この経路探索方法では、経路探索、シミュレーション、コスト修正の操作を繰り返すことによって、移動体の行動を反映したコストが設定され、そのコストに従って経路が探索されることによって、移動体の集中が抑えられ、渋滞の発生を回避できる。
【０００５】
【特許文献１】
特開２００１−１９３４７０号公報（段落００４０、００５７等）
【０００６】
【発明が解決しようとする課題】
しかしながら、上記の経路探索方法では、全移動体がコストが最小になる経路を選択した場合、渋滞が酷過ぎてシミュレーションの実行が不可能になる場合がある。特に、詳細な道路ネットワークを用いた場合には、デッドロックが起き易くなり、適正な渋滞状況を知ることができない。
【０００７】
特許文献１には、１つの経路への移動体の集中を防止するために、最適な経路を１つだけ検出するのではなく、検索した複数の経路の中で、コストの合計が最小のものから順に、予め決めた数の経路を選択し、各移動体に確率的にこれらの経路を割り振ることが提案されているが、コスト合計が最小のものから順に選択したのでは、似通った経路が複数選択され、渋滞の解消に寄与するような実用的な経路は選択されない、という問題がある。
【０００８】
本発明は、上記問題を解決すべく成されたものであり、本発明の目的は、渋滞の発生を予め予測して、渋滞の解消に寄与するような実用的な経路を複数探索することができる経路探索装置を提供することにある。
【０００９】
【課題を解決するための手段】
上記目的を達成するために本発明は、道路ネットワーク上を複数の車両が走行する場合に、所定の出発地点から所定の目的地点に至るのに最適な経路を探索する経路探索装置において、出発地点と目的地点との間の全ＯＤ交通量を複数に分割すると共に、出力されるＯＤ交通量が徐々に増加するように、分割されたＯＤ交通量を適宜組み合せて順次出力するＯＤ交通量分割手段と、道路ネットワーク上の各リンクの旅行時間を設定した場合に、道路ネットワークを表す道路ネットワークデータと前記ＯＤ交通量分割手段から入力されたＯＤ交通量とに基づいて、設定された前記旅行時間の下でコストの合計が最小となる候補経路を選定する候補経路選定手段と、前記候補経路選定手段で選定された候補経路に、複数の車両を走行させてシミュレーションを実施するシミュレーション手段と、を含んで構成したことを特徴とする。
【００１０】
本発明の経路探索装置では、ＯＤ交通量分割手段が、出発地点と目的地点との間の全ＯＤ交通量を複数に分割すると共に、出力されるＯＤ交通量が徐々に増加するように、分割されたＯＤ交通量を適宜組み合せて順次出力する。候補経路選定手段は、道路ネットワーク上の各リンクの旅行時間を設定した場合に、道路ネットワークを表す道路ネットワークデータと前記ＯＤ交通量分割手段から入力されたＯＤ交通量とに基づいて、設定された前記旅行時間の下でコストの合計が最小となる候補経路を選定する。シミュレーション手段は、候補経路選定手段で選定された候補経路に複数の車両を走行させてシミュレーションを実施する。
【００１１】
以上の通りＯＤ交通量を分割し、段階的にＯＤ交通量を増加させながらシミュレーションを実施することで、非渋滞時から渋滞時まで複数の交通状況での旅行時間を演算することができる。これらの旅行時間を用いて経路探索を行うことにより、各交通状況下での実用的な選択経路を求めることができる。
【００１２】
また、車両の選択経路は、道路の混み具合、即ち、各リンクの旅行時間が変化することにより変化するので、前記シミュレーション手段は、得られたシミュレーション結果に基づいて道路ネットワーク上の各リンクの最大旅行時間を算出し、前記候補経路選定手段は、算出した前記最大旅行時間を旅行時間と仮定して候補経路を選定することが好ましい。
【００１３】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１４】
図１に示すように、本実施の形態の経路探索装置は、道路ネットワークを表す道路ネットワークデータを記憶した記憶装置１０、出発地（Ｏ）の位置、目的地（Ｄ）の位置、及び出発地から目的地までの交通量（ＯＤ交通量）を表すＯＤ交通量データ等を入力するためのキーボード等で構成された入力装置１２、入力装置１２から入力された入力データ及び記憶装置１０に記憶された道路ネットワークデータに基づいて経路及び旅行時間の演算を行なうコンピュータ等で構成された演算装置１４、及び演算装置１４で演算された経路及び旅行時間を表示するＣＲＴやＬＣＤ等で構成された表示装置１６から構成されている。
【００１５】
図２に、図１の演算装置１４を機能ブロックで表す。図２に示すように、演算装置１４は、ＯＤ交通量分割部１４Ａ、経路探索部１４Ｂ、及び交通流シミュレータ１４Ｃを含んで構成される。ＯＤ交通量分割部１４Ａは、ＯＤ交通量Ｄ２をＯＤ1〜ＯＤnのｎ個に分割し、ＯＤ交通量が徐々に増加するように、ＯＤ1、ＯＤ1＋ＯＤ2、．．．、ＯＤ1＋ＯＤ2＋…＋ＯＤnの順にｎ回に分けて出力する。経路探索部１４Ｂは、記憶装置１０から入力される道路ネットワークデータＤ１、ＯＤ交通量分割部１４Ａから入力される分割されたＯＤ交通量データＤ３、及び交通流シミュレータ１４Ｃから出力された旅行時間Ｄ４を入力として、道路ネットワークデータ、ＯＤ交通量データ及び旅行時間に基づいて、道路ネットワークを走行する車両が選択する可能性がある複数の候補経路を選定し、候補径路データＤ５を出力する。また、交通流シミュレータ１４Ｃは、道路ネットワークデータＤ１、ＯＤ交通量データＤ３、及び経路探索部１４Ｂで選択された複数の候補経路を示す候補径路データＤ５を入力として、シミュレーションを行い、道路ネットワーク上の各リンクに対する時間帯別の旅行時間を算出する。
【００１６】
図３は、記憶装置１０に記憶されている道路ネットワークデータの例を示すものである。この道路ネットワークデータは、豊田市南部を対象としたノード（交差点等）数３６７６、リンク（道路）数９５９７、信号設置交差点数６０３のデータである。
【００１７】
以下、図４を参照して、本実施の形態の経路探索装置における経路探索の手順について説明する。なお、図５は、演算装置１４の処理ルーチンを説明するためのフローチャートである。以下では、各ＯＤ（出発地／目的地）についてＯＤ交通量を６分割する場合について説明するが、ＯＤ交通量の分割数は６には限定されない。なお、Ｏ及びＤに対応するゾーンが広いほど、或いは、ＯＤに対する交通量が多いほど、分割数を大きくする必要がある。
【００１８】
ステップ１００で、記憶装置１０に記憶された道路ネットワークデータが読み出され、入力装置１２からＯＤ交通量データ等が入力されると、ステップ１０２で、演算装置１４のＯＤ交通量分割部１４Ａは、各ＯＤについてＯＤ1〜ＯＤ6が５０％、１０％、１０％、１０％、１０％、１０％となるように、全ＯＤ交通量を６分割する。ＯＤ交通量は整数であるため、分割は乱数を用いて確率的に行う。例えば、所定の時間帯にノードＡからノードＢに向かう車両が１３台である場合には、６台、１台、１台、１台、１台、１台に分割した後に、残りの２台を０．５、０．３、０．３、０．３、０．３、０．３の確率で１台ずつ割り当てる。
【００１９】
ＯＤ交通量の分割方法は、特に制限は無いが、実用的な観点から、第１回目の経路探索に使用するＯＤ交通量が４０％以上とするのが好ましい。全ＯＤ交通量の半分程度、即ち４０〜６０％とするのがより好ましい。また、第２回目以降の経路探索に使用するＯＤ交通量の増加分は、第１回目のＯＤ交通量以外のＯＤ交通量を均等に分割するか、或いは、徐々に減少するように分割することが好ましい。ＯＤ交通量の増加分が徐々に減少するように分割する場合、減少量（前回との差分）は後半ほど減少するように設定するのが好ましい。
【００２０】
以下に全ＯＤ交通量の他の分割例を示す。
【００２１】
５０％、３０％、１０％、１０％   （４分割）
５０％、３０％、１０％、５％、５％  （５分割）
５０％、２５％、１５％、１０％   （４分割）
４０％、２０％、１０％、１０％、１０％、１０％  （６分割）
次に、ステップ１０４で、経路探索部１４Ｂは、図示したＯＤを対象として、ダイキストラ（Dijkstra）法等の既存のアルゴリズムを用いて、出発地から目的地に至るまでの経路のコストの合計が最小となる経路の探索を行ない、候補経路を選定する。本実施の形態では、図４（Ａ）に示すように、経路１が選定される。ステップ１０６で、この経路１を最適経路データとして出力し、表示装置１６に表示する。
【００２２】
経路のコストは、所要時間、走行距離、右左折回数、平均車線数、又はそれらの組合せ等により予め定めた評価基準に基づいて計算することができる。本実施の形態では、特開平６−３３１３７０号公報に記載されたコスト計算式に従って、所要時間、走行距離、右左折回数、及び平均車線数から経路のコストを算出する。第１回目の経路探索では、所要時間として、道路ネットワークＤ１の各リンクごとに予め設定された速度で走行したときの所要時間、即ち、自由走行時の旅行時間を使用する。
【００２３】
次に、ステップ１０８で、交通流シミュレータ１４Ｃは、図４（Ｂ）に示すように、選定された経路１について、５０％のＯＤ交通量（ＯＤ1）を仮定してシミュレーションを行い、ステップ１１０で、道路ネットワーク上の各リンクに対する時間帯別の旅行時間の平均値を算出する。算出した時間の最大値が、５０％のＯＤ交通量の下での道路ネットワーク上の各リンクに対する旅行時間１である。
【００２４】
本実施の形態では、シミュレータとして、広域交通流を対象とするマクロモデルの交通流シミュレータである「NETSTREAM(NETwork Simulator for Traffic Efficiency And Mobility)」を用いた。「NETSTREAM」は、道路ネットワークデータ、信号データ、ＯＤ交通量データ、及び経路データを入力として交通流計算を行い、各リンクの交通量、旅行時間、渋滞長などを出力する。なお、「NETSTREAM」の詳細については、技術報告「豊田中央研究所Ｒ＆Ｄレビュー」第３７巻、Ｎｏ２に記載されている。
【００２５】
次に、ステップ１１２で、経路探索部１４Ｂは、交通流シミュレータ１４Ｃから出力された旅行時間１を用いて、第２回目の経路探索を行ない、候補経路を選定する。本実施の形態では、図４（Ｃ）に示すように、経路１に加えて経路２が新たに選定される。ステップ１１４で、この経路１及び経路２を候補経路データとして出力し、表示装置１６に表示する。
【００２６】
次に、ステップ１１６で、ＯＤ交通量が１００％に達したか否かを判断し、１００％に達していない場合は、ステップ１１８で次のＯＤ交通量を用意し、ステップ１０８に戻って、ステップ１０８〜１１８でシミュレーションと経路探索とを繰り返す。
【００２７】
即ち、交通流シミュレータ１４Ｃは、図４（Ｄ）に示すように、選定された経路１及び経路２について、６０％のＯＤ交通量（ＯＤ1＋ＯＤ2）を仮定してシミュレーションを行い、道路ネットワーク上の各リンクに対する時間帯別の旅行時間の平均値を算出する。算出した時間の最大値が、６０％のＯＤ交通量の下での道路ネットワーク上の各リンクに対する旅行時間２である。
【００２８】
次に、経路探索部１４Ｂは、交通流シミュレータ１４Ｃから出力された旅行時間２を用いて、第３回目の経路探索を行ない、候補経路を選定する。本実施の形態では、経路１及び経路２に加えて経路３が新たに選定される。この経路１〜経路３を候補経路データとして出力し、表示装置１６に表示する。
【００２９】
引き続き、ＯＤ交通量が１００％に達するまで、ＯＤ交通量を７０％、８０％、９０％と順次増加して、シミュレーションと経路探索とを繰り返し実施する。本実施の形態では、第６回目の経路探索を行なった時点で、ＯＤ交通量が１００％に達し、図４（Ｅ）に示すように、６本の候補経路が選定される。同様にして、各ＯＤについて最大６本の混雑状況別の選択経路を得ることができる。
【００３０】
最後に、ステップ１２０で、交通流シミュレータ１４Ｃは、図４（Ｆ）に示すように、選定された経路１〜経路６について、１００％のＯＤ交通量（ＯＤ1＋ＯＤ2＋ＯＤ3＋ＯＤ4＋ＯＤ5＋ＯＤ6）を仮定してシミュレーションを実施する。ステップ１２２で、シミュレーション結果を出力して、処理ルーチンが終了する。
【００３１】
図３に示す道路ネットワークデータを用いて、上記の方法で各ＯＤについて得られた６経路について交通流シミュレーションを実施した。ＯＤ交通量データとしては、例えば、１９９１年パーソントリップ調査の基本ゾーン単位のＯＤ交通量データ及び個人別トリップ調査データを元に、対象時間を午前６時〜午前１０時として３０分単位で作成したデータを使用した。各時間帯別の車両発生状況を表１に示す。
【００３２】
【表１】
2004198165.tif 000003
【００３３】
比較のために、各ＯＤについて１経路のみを用いて、１５分毎に最小コスト経路を探索することにより交通状況に応じた経路を増加させる手法でシミュレーションを実施した。各時間帯別の車両発生状況を表２に示す。
【００３４】
【表２】
2004198165.tif 000004
【００３５】
表２から分かるように、時間の経過と共に車両の発生割合が減少し、午前７時〜午前９時の朝のピーク時間を過ぎても道路ネットワーク上に存在する車両数が増加していることから、解消不能で且つ深刻な渋滞が発生していることが分かる。
【００３６】
これに対し、表１に示したシミュレーション結果では、同じＯＤ交通量データを用いても、道路ネットワーク上に存在する車両数がピーク時間を過ぎると減少し、渋滞が解消されていることが分かる。即ち、本実施の形態では、交通流シミュレーションで使用するのに有効な経路が得られていることが分かる。
【００３７】
車両の選択経路は、渋滞がないとき、少し混んできたとき、渋滞のとき、激しい渋滞のとき、というように道路の混み具合、即ち、各リンクの旅行時間が変化することにより異なる。以上、説明した通り、ＯＤ交通量を分割し、段階的にＯＤ交通量を増加させながらシミュレーションを実施することで、非渋滞時から渋滞時まで複数の交通状況での旅行時間を演算することができる。これらの旅行時間を用いて経路探索を行うことにより、各交通状況下での実用的な選択経路を求めることができる。
【００３８】
【発明の効果】
本発明の経路探索装置によれば、渋滞の発生を予め予測して、渋滞の解消に寄与するような実用的な経路を複数探索することができる、という効果がある。
【図面の簡単な説明】
【図１】本発明の実施の形態のブロック図である。
【図２】図１の演算装置を表す機能ブロックとデータとの関係を示すブロック図である。
【図３】道路ネットワークの例を示す線図である。
【図４】（Ａ）〜（Ｆ）は、経路探索の手順を説明するための説明図である。
【図５】図１の演算装置の処理ルーチンを表すフローチャートである。
【符号の説明】
Ｄ１  道路ネットワークデータ
Ｄ２  ＯＤ交通量データ
Ｄ３  分割されたＯＤ交通量データ
Ｄ４  旅行時間
Ｄ５  候補径路データ
１０    記憶装置
１２    入力装置
１４    演算装置
１４Ａ  ＯＤ交通量分割部
１４Ｂ  経路探索部
１４Ｃ  交通流シミュレータ
１６    表示装置ＯＤ交通量を分割
【図１】
2004198165.tif 000005
【図２】
2004198165.tif 000006
【図３】
2004198165.tif 000007
【図４】
2004198165.tif 000008
【図５】
2004198165.tif 000009