(57)【要約】  【課題】  交通シミュレーション技法において、シミュレーションの妥当なタイムステップの値を自動的に決定すること。  【解決手段】  道路の充填率を計算するために、シミュレーションの対象とする領域における交差点のうち、充填率に関して上位K個(Kは例えば1000と選ばれる）を同期タイミング毎に選択する。充填率は、例えば、交差点に直接つながる道路における車両の充填率によって計算される。充填率は、より具体的には、交差点に直接つながる道路毎に、その道路を走る車両の数を道路の長さで割った値を合計した値として計算される。そして、シミュレーションのタイムステップが、充填率に対する単調減少関数、好適には、充填率の二乗に逆比例する値として決定される。【選択図】  図３
2014191580.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータの処理によって、道路に沿って移動する複数の車両の位置を順次、時間間隔に従い計算するシミュレーション・システムにおいて、
道路の交差点における車両の充填率を計算するステップと、
前記車両の充填率に関して、上位Ｎ個（Ｎは所定の自然数）の交差点を選ぶステップと、
前記選ばれた交差点に関して、前記車両の充填率を加算するステップと、
前記加算した充填率の値の単調減少関数として、前記シミュレーションの時間間隔を計算するステップと、
前記計算された時間間隔でシミュレーションを進めるステップを有する、
交通シミュレーション方法。
【請求項２】
前記単調減少関数が、逆二乗に比例する関数である、請求項１に記載の方法。
【請求項３】
前記車両の充填率が、道路に沿った車両の数を、道路の長さで割った値により計算される、請求項２に記載の方法。
【請求項４】
前記シミュレーションの時間間隔が、測定対象とする交差点の数×ノード数の総数×シミュレーション全体の車両数を、前記加算した値の二乗で割ることによって計算される、請求項２に記載の方法。
【請求項５】
前記シミュレーションの時間間隔が、測定対象とする交差点の数×ノード数の総数×シミュレーション全体の車両数を、前記加算した値の二乗×シミュレーション全体のステップ数で割ることによって計算される、請求項２に記載の方法。
【請求項６】
前記シミュレーションの時間間隔を計算するステップが、過去の所定時間ウインドウの範囲の時間間隔の平均値を求めることで、時間間隔を計算するステップを含む、請求項１に記載の方法。
【請求項７】
前記シミュレーションの時間間隔を計算するステップが、前記加算した充填率の値が所定の閾値より小さいことに応答して、前記加算した充填率の代わりに該閾値を用いて時間間隔を計算するステップを含む、請求項１に記載の方法。
【請求項８】
コンピュータの処理によって、道路に沿って移動する複数の車両の位置を順次、時間間隔に従い計算するシミュレーション・システムにおいて、
前記シミュレーション・システムに、
道路の交差点における車両の充填率を計算するステップと、
前記車両の充填率に関して、上位Ｎ個（Ｎは所定の自然数）の交差点を選ぶステップと、
前記選ばれた交差点に関して、前記車両の充填率を加算するステップと、
前記加算した充填率の値の単調減少関数として、前記シミュレーションの時間間隔を計算するステップと、
前記計算された時間間隔でシミュレーションを進めるステップを実行させる、
交通シミュレーション・プログラム。
【請求項９】
前記単調減少関数が、逆二乗に比例する関数である、請求項８に記載のプログラム。
【請求項１０】
前記車両の充填率が、道路に沿った車両の数を、道路の長さで割った値により計算される、請求項９に記載のプログラム。
【請求項１１】
前記シミュレーションの時間間隔が、測定対象とする交差点の数×ノード数の総数×シミュレーション全体の車両数を、前記加算した値の二乗で割ることによって計算される、請求項９に記載のプログラム。
【請求項１２】
前記シミュレーションの時間間隔が、測定対象とする交差点の数×ノード数の総数×シミュレーション全体の車両数を、前記加算した値の二乗×シミュレーション全体のステップ数で割ることによって計算される、請求項９に記載のプログラム。
【請求項１３】
前記シミュレーションの時間間隔を計算するステップが、過去の所定時間ウインドウの範囲の時間間隔の平均値を求めることで、時間間隔を計算するステップを含む、請求項８に記載のプログラム。
【請求項１４】
前記シミュレーションの時間間隔を計算するステップが、前記加算した充填率の値が所定の閾値より小さいことに応答して、前記加算した充填率の代わりに該閾値を用いて時間間隔を計算するステップを含む、請求項８に記載のプログラム。
【請求項１５】
コンピュータの処理によって、道路に沿って移動する複数の車両の位置を順次、時間間隔に従い計算するシミュレーション・システムにおいて、
道路の交差点における車両の充填率を計算する手段と、
前記車両の充填率に関して、上位Ｎ個（Ｎは所定の自然数）の交差点を選ぶ手段と、
前記選ばれた交差点に関して、前記車両の充填率を加算する手段と、
前記加算した充填率の値の単調減少関数として、前記シミュレーションの時間間隔を計算する手段と、
前記計算された時間間隔でシミュレーションを進める手段を有する、
交通シミュレーション・システム。
【請求項１６】
前記単調減少関数が、逆二乗に比例する関数である、請求項１５に記載のシステム。
【請求項１７】
前記車両の充填率が、道路に沿った車両の数を、道路の長さで割った値により計算される、請求項１６に記載のシステム。
【請求項１８】
前記シミュレーションの時間間隔が、測定対象とする交差点の数×ノード数の総数×シミュレーション全体の車両数を、前記加算した値の二乗で割ることによって計算される、請求項１６に記載のシステム。
【請求項１９】
前記シミュレーションの時間間隔が、測定対象とする交差点の数×ノード数の総数×シミュレーション全体の車両数を、前記加算した値の二乗×シミュレーション全体のステップ数で割ることによって計算される、請求項１６に記載のシステム。
【請求項２０】
前記シミュレーションの時間間隔を計算する手段が、過去の所定時間ウインドウの範囲の時間間隔の平均値を求めることで、時間間隔を計算する処理を実行する、請求項１５に記載のシステム。
【請求項２１】
前記シミュレーションの時間間隔を計算する手段が、前記加算した充填率の値が所定の閾値より小さいことに応答して、前記加算した充填率の代わりに該閾値を用いて時間間隔を計算する処理を実行する、請求項１５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータによって、道路上の車両の走行をシミュレーションするための、交通シミュレーション技法に関するものである。
【背景技術】
【０００２】
従来より、コンピュータに基づく交通シミュレーション・システムは周知である。このようなシステムでは、道路に沿った一台毎の車両の動きを、タイムステップ毎にコンピュータにより計算し、進めていく。この際、各車両の動きは、例えば特開２００４−２５８８８９号公報によれば、車両の停車時および走行時における加速度の方向と大きさが、前記車両の走行に影響を与える時間的に一定な外的要因の影響度の大きさで定義される静的ポテンシャル場と、前記車両の走行に影響を与える時間的に変動する外的要因の影響度の大きさで定義される動的ポテンシャル場とに基づいて決定される。
【０００３】
その際問題となるのは、タイムステップの幅である。すなわち、シミュレーションの精度を上げようとすると、タイムステップの幅は小さくする必要があるが、すると、シミュレーション・システムの動作速度が低下してしまう。そこで特開２００９−９３４２５号公報は、交通流シミュレーションにおいて、必要な精度を確保しつつ、処理効率を向上させるために、シミュレーション対象となる領域を複数の領域に分割し、領域ごとに前記タイムステップの値が異ならせるようにすることを開示する。その際、タイムステップ後に移動体がタイムステップの異なる領域に進入する場合には、進入した領域のタイムステップに合致する時刻およびその時の位置を算出して、シミュレーションを続けるようにする。
【０００４】
しかし、特開２００９−９３４２５号公報の技法では、シミュレーション対象となる領域を予め分割しておき、その分割された領域毎に妥当なタイムステップの値を与えておく必要があるが、任意の対象領域に対して妥当なタイムステップの値を設定しておくことは困難である。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００４−２５８８８９号公報
【特許文献２】特開２００９−９３４２５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従って、この発明の目的は、交通シミュレーション技法において、シミュレーションの妥当なタイムステップの値を自動的に決定することにある。
【課題を解決するための手段】
【０００７】
本発明は上記課題を解決するためになされたものであり、交通シミュレーションにおける道路の混雑度に応じて、シミュレーションを動的に変えることによって、上記課題を解決する。
【０００８】
本発明のシステムは先ず、道路の混雑度、すなわち充填率を計算するために、シミュレーションの対象とする領域における交差点のうち、充填率に関して上位K個(Kは例えば1000と選ばれる）を同期タイミング毎に選択する。充填率は、例えば、交差点に直接つながる道路における車両の充填率によって計算される。充填率は、より具体的には、交差点に直接つながる道路毎に、その道路を走る車両の数を道路の長さで割った値を合計した値として計算される。
【０００９】
そして本発明によれば、シミュレーションのタイムステップが、充填率に対する単調減少関数、好適には、充填率の二乗に逆比例する値として決定される。
【発明の効果】
【００１０】
この発明によれば、車両の充填率に応じて自動的にタイムステップを決定することにより、シミュレーションの動作速度と動作精度に関して最適化がはかられる。
【図面の簡単な説明】
【００１１】
【図１】本発明を実施するためのハードウェアのブロック図である。
【図２】本発明を実施するための機能構成のブロック図である。
【図３】本発明の処理のフローチャートを示す図である。
【図４】地図を複数の場所に分割することを示す図である。
【図５】交差点における充填率の計算を説明するための図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して、本発明の一実施例の構成及び処理を説明する。以下の記述では、特に断わらない限り、図面に亘って、同一の要素は同一の符号で参照されるものとする。なお、ここで説明する構成と処理は、一実施例として説明するものであり、本発明の技術的範囲をこの実施例に限定して解釈する意図はないことを理解されたい。
【００１３】
先ず、図１を参照して、本発明を実施するために使用されるコンピュータのハードウェアについて説明する。図１において、ホスト・バス１０２には、複数のＣＰＵ１  １０４ａ、ＣＰＵ２  １０４ｂ、ＣＰＵ３  １０４ｃ、・・・ＣＰＵｎ  １０４ｎが接続されている。ホスト・バス１０２にはさらに、ＣＰＵ１  １０４ａ、ＣＰＵ２  １０４ｂ、ＣＰＵ３  １０４ｃ、・・・ＣＰＵｎ  １０４ｎの演算処理のためのメイン・メモリ１０６が接続されている。
【００１４】
一方、Ｉ／Ｏバス１０８には、キーボード１１０、マウス１１２、ディスプレイ１１４及びハードティスク・ドライブ１１６が接続されている。Ｉ／Ｏバス１０８は、Ｉ／Ｏブリッジ１１８を介して、ホスト・バス１０２に接続されている。キーボード１１０及びマウス１１２は、オペレータが、コマンドを打ち込んだり、メニューをクリックするなどして、操作するために使用される。ディスプレイ１１４は、必要に応じて、後述する本発明に係るプログラムをＧＵＩなどのインターフェースで操作するためのメニューを表示するために使用される。
【００１５】
この目的のために使用される好適なコンピュータ・システムのハードウェアとして、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｘがある。その際、ＣＰＵ１  １０４ａ、ＣＰＵ２  １０４ｂ、ＣＰＵ３  １０４ｃ、・・・ＣＰＵｎ  １０４ｎは、例えば、インテル（Ｒ）Ｘｅｏｎ（Ｒ）であり、オペレーティング・システムは、Ｗｉｎｄｏｗｓ（商標）Ｓｅｒｖｅｒ  ２００８である。オペレーティング・システムは、ハードティスク・ドライブ１１６に格納され、コンピュータ・システムの起動時に、ハードティスク・ドライブ１１６からメイン・メモリ１０６に読み込まれる。
【００１６】
本発明を実施するためには、マルチプロセッサ・システムを用いることが望ましい。ここでマルチプロセッサ・システムとは、一般に、独立に演算処理し得るプロセッサ機能を複数もつシステムを意図しており、従って、マルチコア・シングルプロセッサ・システム、シングルコア・マルチプロセッサ・システム、及びマルチコア・マルチプロセッサ・システムのどれかでよいことを理解されたい。
【００１７】
マルチコア・プロセッサとしては、好適には、インテル社のＣｏｒｅ（商標）  ｉ３、Ｃｏｒｅ（商標）  ｉ５、Ｃｏｒｅ（商標）  ｉ７、Ｘｅｏｎ（Ｒ）、ＡＭＤ社のＡｔｈｌｏｎ（商標）、Ｐｈｅｎｏｍ（商標）、Ｓｅｍｐｒｏｎ（商標）などを使用することができる。
【００１８】
なお、本発明を実施するために使用可能なコンピュータ・システムのハードウェアは、ＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｘに限定されず、本発明のシミュレーション・プログラムを走らせることができるものであれば、パーソナル・コンピュータを含む任意のコンピュータ・システムを使用することができる。オペレーティング・システムも、Ｗｉｎｄｏｗｓ（Ｒ）に限定されず、Ｌｉｎｕｘ（Ｒ）、Ｍａｃ  ＯＳ  Ｘ（Ｒ）など、任意のオペレーティング・システムを使用することができる。さらに、シミュレーション・プログラムを高速で動作させるために、ＰＯＷＥＲ（商標）６ベースで、オペレーティング・システムがＡＩＸ（商標）のＩＢＭ（Ｒ）Ｓｙｓｔｅｍ  Ｐなどのコンピュータ・システムを使用することもできる。
【００１９】
さらに、コンピュータ・システムのハードウェアは、ＬＡＮ、ＷＡＮなどで相互接続された分散システムを使用することも可能である。
【００２０】
ハードティスク・ドライブ１１６にはさらに、図２に関連して後述するメイン・プログラム２０２、地図データ２０４、交通シミュレーション・プログラム２０６、充填率計算ルーチン２０８、ソート・ルーチン２１０、ステップ数計算ルーチン２１２などが格納されており、オペレータのキーボード１１０やマウス１１２などの操作に応答して、メイン・メモリ１０６にロードされて実行される。これらのファイルやルーチンに関しては、図２に関連して後述する。メイン・プログラム２０２、交通シミュレーション・プログラム２０６、充填率計算ルーチン２０８、ソート・ルーチン２１０、ステップ数計算ルーチン２１２等は、Java(R)、C、C++、C#などの既存のコンピュータ・プログラミングのコードとして書かれ、所定のコンパイラでコンパイルすることにより作成することができる。
【００２１】
次に、図２を参照して、本発明の機能構成を説明する。メイン・プログラム２０２は、オペレータのキーボード１１０やマウス１１２などの操作を受け付けて、交通シミュレーション・プログラム２０６の起動、停止など、処理全体の制御を担う。
【００２２】
地図データ２０４は、これには限定されないが、この実施例では、Open Street Map(http://www.openstreetmap.org/)から入手されたものを使用する。特にこの実施例では、交差点を点の集合として管理する。ただ、実際の交差点だけに着目していると、高速道路のように延々と続く道路の場合、点が疎らになってしまう。そこで、長い道路の場合、数百メートルのオーダーで区切って、その区切りも、拡張された交差点とみなすようにしている。以下の記述では基本的に、実際の交差点と拡張された交差点とを同様に扱う。
【００２３】
さらにこの実施例によれば、地図データ２０４は、交差点の集合が複数の部分集合に分割され、その部分集合の各々が、別個の処理単位であるノードにより処理される。ここでいうノードとは、論理的に分離可能な処理単位であり、図１で示す構成では、典型的には、個々のＣＰＵ１０４ａ、１０４ｂ、・・・、１０４ｎの各々である。あるいは、分散処理環境の場合、ネットワーク接続された個々のコンピュータの各々をノードとみなしてもよい。ともかく、交通シミュレーション・プログラム２０６をこのようなマルチノードで構成すると、車両が道路に沿って移動するにつれて、異なるノードの間に通信が生じるので、通信の量をなるべく減らすように、交差点に対するノードの割り当てがなされる。
【００２４】
図４に、地図データ２０４の一部と、その交差点データのノードの割り当てが図示されている。領域Ｐ1はあるノードに割り当てられ、領域Ｐ2は別のノードに割り当てられ、領域Ｐ3はさらに別のノードに割り当てられ、領域Ｐ4はさらに別のノードに割り当てられている。この実施例では、このような、交差点の部分集合に対応し、個別のノードに割り当てられている領域を、場所(Place)とも呼ぶ。一つの実施例では、１つのＣＰＵが、ほぼ１００個の交差点を含む１つの場所を担当するようにする。
【００２５】
次に、図５を参照して、この発明で使用される、充填率という指標について説明する。図５において、c1、c2、c3、c4、及びc5が交差点であり、v1、v2、v3、v4、v5、v6、v7、v8、v9、及びv10が車両であり、l1、l2、l3、及びl4が、交差点で区切られた線分としての道路の長さであるとする。すると、交差点c1の充填率は、交差点c1に接続された道路毎の車両の台数を道路の長さで割ったものの和として、N1/l1+N2/l2+N3/l3+N4/l4としてあらわされる。
【００２６】
図２に戻って、交通シミュレーション・プログラム２０６は、次のような疑似コードで記述されるような処理を行う。
for (t = 0; t < N;  t=+Δt) {
1. すべての交差点に対して、各交差点に流入する車両を処理する(車の位置決定・移動など) 
2. すべての交差点に対して、各交差点から流出する車両を処理する 
(次の道路オブジェクトに車両を渡す、他のノードに道路が存在する場合にはマイグレーション、必要によっては経路決定、など）
3. すべての交差点の処理が終了するのを待ち、同期する (全のードに存在する交差点のグローバルな同期）
} 
(t はシミュレーションステップ、N は総シミュレーションステップ数、Δtはステップを進める値) 
【００２７】
このとき、一つの実施例では、車両は前方に車がない場合には、その道路の制限速度とほぼ同程度の速度で走り、道路上を移動していくようにする。そして、前方に車両が存在する場合は、適切な車両を保つように速度を落として、ステップ毎に、車両の位置を更新していく。これに限らず、これ以外の任意の車両移動シミュレーション・アルゴリズムを用いることができる。
【００２８】
充填率計算ルーチン２０８は、地図データ２０４のデータと、交通シミュレーション・プログラム２０６の出力を基に、地図データ２０４上の各交差点での充填率を計算する。ここでの、充填率の定義は、上述のとおりである。なお、地図データ２０４上の全交差点の充填率を計算することが計算量的に重過ぎるなら、グラフ理論における中心性に基づき、予め交差点を重み付けして、ある閾値以上の交差点の充填率のみ計算するようにしてもよい。この場合の中心性として、その頂点を通過しないと到達できない経路の数である媒介性(betweenness)を利用することができる。
【００２９】
ソート・ルーチン２１０は、地図データ２０４上の各交差点を、充填率計算ルーチン２０８によって計算された充填率で降順ソートし、その上位Ｎ個（Ｎは、１つの実施例では1000個）を選んで、その交差点が所属する場所の情報とともに、ステップ数計算ルーチン２１２に供給する。
【００３０】
ステップ数計算ルーチン２１２は、ソート・ルーチン２１０から受け取った充填率が上位Ｎ個の交差点について、下記の式により、合計された充填率dを計算する。
【数１】
2014191580.tif 000003
ここで、
Nr : 各道路の車両の数
lr : 各道路の長さ
P : 場所の集合
C : 各場所Pにおいて対象とする交差点につながる道路の集合
【００３１】
こうしてdが求まると、ステップ数計算ルーチン２１２は、下記の式により、交通シミュレーション・プログラム２０６のステップ数Δtを計算する。
【数２】
2014191580.tif 000004
ここで、
P : 場所の数
T : シミュレーションの全体のステップ数
NC : シミュレーションの全体の対象とする交差点の数
Nv : シミュレーションで走行する車両の数
【００３２】
なお、このようにして計算した結果のステップ数Δtがある閾値より大きい場合は、例えば、過去のn回（例えば、２０回）で計算したステップ数Δtを保存しておいて、それを平均した値を出力するようにしてもよい。これにより、ステップ数Δtが突然急増するこを緩和することができる。
【００３３】
さらに、このようにして計算した結果のステップ数Δtがある閾値より小さい場合は、予め決めておいた所定の定数を代わりに、ステップ数Δtとして出力するようにしてもよい。これにより、ステップ数Δtが突然急減するこを緩和することができる。
【００３４】
このようにして決定されたステップ数Δtは、交通シミュレーション・プログラム２０６に提供されて、シミュレーションのステップを進めるのに使用される。
【００３５】
次に、図３のフローチャートを参照して、本発明に係る交通シミュレーションの動作を説明する。
【００３６】
図３のステップ３０２では、メイン・プログラム２０２は、交通シミュレーション・プログラム２０６を、シミュレーション開始ステップi = 0に初期化する。この処理には、地図データ２０４の交差点情報を場所として好適には各々がＣＰＵである各ノードに割り当てたり、車両の台数や初期位置、初期速度を与えたりすることも含まれる。
【００３７】
ステップ３０４では、与えられた設定に従い、交通シミュレーション・プログラム２０６がステップを実行する。好適には各ノードは、個別のスレッドとして実行されるので、ノードは、スレッド・ノードとも称する。
【００３８】
ステップ３０６では、充填率計算ルーチン２０８が、交通シミュレーション・プログラム２０６がステップを実行した状態での測定対象の交差点をモニタリングし、ソート・ルーチン２１０でソートすることにより、充填率に関して上位Ｎ個の交差点を選ぶ。このような上位Ｎ個の交差点の情報を用いて、ステップ数計算ルーチン２１２が、前述の式(1)を用いて、充填率の合計値dを計算する。
【００３９】
続いてステップ３０８で、ステップ数計算ルーチン２１２が、前述の式(2)を用いて、ステップ数Δtを計算し、すなわち、i ← i + Δｔで、このΔｔだけ交通シミュレーション・プログラム２０６のステップが進められる。
【００４０】
続いてステップ３０８で、メイン・プログラム２０２は、全スレッド・ノードで同期が全体シミュレーション・ステップ数Tに到達したかどうか判断し、もしそうなら、処理を終了し、そうでないなら、ステップ３０４に戻る。
【００４１】
以上、この発明を特定の実施例に基づき説明してきたが、この発明は、この特定の実施例に限定されず、当業者が自明に思いつく様々な変形、置換などの構成、技法適用可能であることを理解されたい。例えば、特定のプロセッサのアーキテクチャ、オペレーティング・システムなどに限定されない。
【００４２】
例えば、上記実施例は、シミュレーションのステップ数を、充填率dの二乗に逆比例するものとして計算したが、適用例に応じて、充填率dの単調減少関数である別の関数を使用してもよい。
【００４３】
また、上記実施例では、シミュレーションで使用する地図の領域を複数の場所に分割し、各々の場所を、個別のノードに割り当てたが、このような構成は必須ではなく、シミュレーションで使用する地図の領域の大きさにより、単一ＣＰＵで全体の処理をカバーすることも可能であることを理解されたい。
【符号の説明】
【００４４】
１０２  ホスト・バス
１０４ａ、１０４ｂ、・・・１０４ｎ  ＣＰＵ
１０６  メイン・メモリ
１１６  ハードティスク・ドライブ
２０３  地図データ
２０６  交通シミュレーション・プログラム
２０８  充填率計算ルーチン
２１２  ステップ数計算ルーチン
【図１】
2014191580.tif 000005
【図２】
2014191580.tif 000006
【図３】
2014191580.tif 000007
【図４】
2014191580.tif 000008
【図５】
2014191580.tif 000009