ＣＡ法による広域道路交通シミュレータを用いた経路案内方式の評価

全文

(1)高度交通システム 10−６（２００２．９．３）. ＣＡ法による広域道路交通シミュレータを用いた経路案内方式の評価狩野均. 小塚英城. 筑波大学電子情報工学系 [email protected] 本稿では、セルオートマトン（ＣＡ）により自然渋滞を時系列的に発生させ､これを用いて動的経路探索アルゴリズムを評価するシステムの開発事例を示す。本システムは、実際のカーナビで用いられているナビ研Ｓ規格地図を対象としており、国内の任意の地域で交通シミュレーションを行うことができる。Nagel 等の提案した多速度モデルを広域道路網に適用するため、交差点モデルと車線変更モデルを提案した。首都圏を対象とした交通シミュレーションを実施し、非平衡環境におけるダイクストラ法と遺伝的アルゴリズムの探索性能を比較検討した。. Evaluation of Route Guidance Methods Using CA-Based Wide Area Traffic Flow Simulator Hitoshi Kanoh. Hideki. Kozuka. University of Tsukuba To evaluate dynamic route selection methods, we developed a traffic flow simulator that uses cellular automata in a non-equilibrium environment where traffic congestion occurs frequently. The simulator uses the S standard map of the Navigation System Researchers’ Association, which is the map used in actual car navigation devices, and produces environments where spontaneous traffic congestion occurs. The traffic flow model we propose is based on Nagel’s multiple-velocities model. Additionally, we propose an intersection model and a lane change model. We confirmed that our simulator works effectively for real road maps.. 1. はじめに. 境において､運転手の快適性を考慮した実用的な. 自動車用ナビゲーション装置（カーナビ）は､高度道路交通システムの車載情報端末として広. 経路をリアルタイムに計算する手法の開発､ならびにその評価方法の研究を行っている[3～6]｡. く利用されている[1, 2]｡最近では､ＶＩＣＳなど. 本稿では､後者について述べる。すなわち、実. の渋滞情報提供サービスの普及にともない､運転. 際のカーナビで用いられているナビ研Ｓ規格地. 中に交通渋滞が発生した場合に迂回路を自動的. 図[7]を用いて道路交通シミュレーションを行い､. に計算するカーナビも市販されている｡しかし､. 自然渋滞を時系列的に発生させ､これを用いて. 現状のカーナビは計算時間が長く､実際に迂回路. 動的経路探索アルゴリズムを評価するシステム. が表示されたときは､曲がるべき交差点を通過し. の開発事例を示す。. てしまっている場合もある｡また､実際の運転に適さない迂回路が表示されることもある｡. 道路交通モデル[8～11]としては､流体モデル､車追従モデル､セルオートマトン（ＣＡ）モデル. 著者らは､交通渋滞が多発するような非平衡環. が提案されているが､本研究では､Nagel等が提. −37−.

(2) 案したＣＡによる多速度モデルを用いる[12]｡こ. や空腹など. れは､道路を多数のセルをつないだ帯として表. ③. し､道路の状態を各セルに車が存在するか否か. 目的情報. 旅行の目的、目的地の設備、目的地の天候、. で表現するものである｡. 立ち寄り地など. 以下では､まずNagel等の多速度モデルを広域道路網に適用するための交差点モデルと車線変. これらの情報が変化した場合カーナビが新た. 更モデル、ならびに、ナビ研Ｓ規格地図を利用. な経路を探索するためには次の情報が必要とな. した交通シミュレータの構成方法を示す。つぎ. る。. に、遺伝的アルゴリズム（ＧＡ）[3]を用いた実. (a) 車の現在位置. 用的な渋滞迂回路の生成手順を示す。最後に、. (b) 目的地. このシミュレータをもちいて、非平衡環境にお. (c) 交通状況. けるダイクストラ法[13]とＧＡの探索性能を比. ここで、①～③と(a)～(c)は、表２のような関係. 較検討する。. にある。表２は、例えば環境情報が変化すると、経路探索において現在地と交通状況が変化する. 2. 研究分野の概要. という意味である。. 2.1 非平衡環境における経路案内. 表１経路探索に必要な情報（○：変化あり）. 運転手がカーナビを用いて経路探索を行うと. 環境情報. 移動体情報. 目的情報. きは、まず運転手がカーナビに目的地を入力す. 現在地. ○. ○. ○. る。つぎに、カーナビが現在地から目的地まで. 目的地. ×. ×. ○. の最適経路を探索し表示する。そして運転中は、. 交通状況. ○. ×. ×. 運転手の意志決定をサポートするため、交通状況やレストランのメニュー、駐車場の空き状況、. 2.2 ＣＡを用いた交通シミュレーション. 目的地の設備などをリアルタイムに表示する。. 本節では Nagel らの方法[11,12]を示す｡道路. さらに、交通状況の変化に対応した渋滞迂回路. は多数のセルが１次元につながっているとし､. 等を再探索する。このように、カーナビは、車. 各セルの長さは車の最小車間距離とする｡１つ. のおかれている環境変化に応じてリアルタイム. のセルには速度 v を持つ車が１台入ることが. に運転手に情報を提供する。本稿では、上記の. できるとする｡速度は整数化し､実際の速度と. ような意志決定支援を含む経路探索を経路案内. 対応させる｡車は前方向に障害物がなければ､. と呼ぶ。経路案内においては、運転手とカーナ. １ステップで v 個前方のセルまで進む｡. ビの関係が重要な要素になってくる。. 速度の上限を v max ､先行車との車間距離を. 運転手が経路を選択するときに必要な情報は次の３つに分類できる。本稿では、これらの情. gap とすると､車は各時間ステップごとに次の規則で決まる新しい速度で進む｡. 報が時々刻々変化する状況を非平衡環境と呼ぶ。 ①. 環境情報. 減速： v > gap なら v → gap. 交通渋滞、事故、規制、天候、近景など ②. 加速： v < gap & v < v max なら v → v + 1. 揺らぎ：確率 p で v → v − 1. 移動体情報. 自動車の位置、燃料、故障、旅行者の疲労. −38−.

(3) 3 提案する方法. step2:その差の絶対値が１６に最も近いものを選択. 3.1 広域道路交通シミュレーション. step3:その２本をひとつの組とし、残りの１本. ここでは､実際のカーナビで使用されている. をもうひとつの組とする. ナビ研 S 規格地図を対象として道路交通シミュレーションを行う方法を述べる｡. step4:同じ組の道路は同じ信号の状態で動作するものとする。. Ｓ規格地図では､道路の特性として､制限速度､. (ⅱ) ４叉路. 距離､道路種別､車線数､方位､信号の有無などの. step1:道路の方位を小さい順にソート. データが格納してある｡道路種別には国道や都. step2:１番目と３番目をひとつの組とする. 道府県道､高速道などの 8 段階で区別されてい. step3:２番目と４番目をひとつの組とする. る。また、方位はその道路の進行方位を示して. step4:同じ組の道路は同じ信号の状態で動作. おり､32 段階で区別されている｡本稿では国道、. するものとする。. 都道府県道､地方主要道をまとめて主要道と呼ぶことにする｡. 交叉する道路の数が奇数の場合は、３叉路のアルゴリズムを拡張したアルゴリズムを用いて信号を制御する。また、偶数の場合は４叉路の. (1). 交差点モデル. アルゴリズムを拡張する。. 交差点での車の振る舞いを決定するアルゴリズ. また、信号のない交叉点を通過するときには、. ムを図１に示す。図１において gapfacing は信号. 自分のいる道路が優先的に進行できる道路なの. に向かってきている車と信号との距離、vfacing は. かを判断する必要がある。そこではじめに道路. 向かってくる車の速度である｡. 種別を用いて優先度を判定する｡もし道路種別が同じで優先道路かどうか判定できなければ､. if(信号あり) 信号の状態により進行か停止. 車線数を用いて優先道路かどうかを判定する｡. if(信号なし) (2) 進行方向の決定. if(優先道路＆（左折 || 直進)). 交差点内の道路のうち、主要道である道路の. そのまま進行 else if((優先道路＆右折) || 非優先道路). 行する。進行しなかった場合、もしくは主要道. if(一時停止していた車) if(gapfacing-vfacing >0) else else. 本数を数え、それらの道路には 30%の確率で進が存在しない場合はランダムに進行方向を決定. 進行. する。これにより主要道を走る車が多くなり、. そのまま停止. 実際の交通に近づけることができる。. 一時停止. 図１交差点での車の振る舞いを決定する手順ナビ研 S 規格地図には各交差点の信号の有無. (3) 車線変更ルール •. 走る｡. が登録されている。ここでは、交叉点の信号の組合せを決定するアルゴリズムを 3 叉路と４叉. 次の信号で左折する車は一番左のレーンを. •. 次の信号で右折する車は一番右のレーンを走る｡. 路の場合に分けてアルゴリズムを示す。 (ⅰ) ３叉路 step1:２本の道路の方位の差をそれぞれ計算. −39−. •. 直進する車はどのレーンを走ってもよい｡. •. 前の車の速度が遅いときは 20%の確率で車.

(4) 線変更をする｡ただし曲がる車は信号の手. 3.3 動的経路案内方式. 前では車線変更できない｡ •. 提案する手法のアルゴリズムを図３に示す。. 車線変更する際には移る先のレーンにいる. 以下では、集団の再生成手順について述べる。. 車との距離と速度を確認し､追いつかれそ. 図４は、車が走行中に渋滞が発生した場合に、. うなら車線変更はしない｡また移る先のレ. ＧＡ集団中の別の個体を用いて迂回路を生成す. ーンの前方にいる車が遅いときも車線変更. る方法を示している。Rk は集団中の k 番目の個. をしない｡. 体、Re は車が出発前にカーナビが探索した推奨経路（集団中のエリート個体）である。また、 Vt は、あらかじめ知識として登録しておいた走. 3.2 動的経路探索手法の評価システム. システムの構成を図２に示す｡また､受け渡されるデータ(D1～D5)の概要を表２に表す｡. procedure main ( ){. 本システムでは､まずスタートとゴールを設. 地図データの読み込み;. 定し､ダイクストラ法で推奨経路を求め､スター. 出発地と目的地を入力;. トからゴールまで仮想の車を進めていく｡５分. 走りやすい経路を地図から抽出;. おきに交通情報を更新し､渋滞が発生した場合. 初期集団の生成;. にダイクストラ法とＧＡで渋滞回避を行うもの. genetic operation ( );. である｡. 目的地に到着するまでループ { 経路探索部ＧＡ. 表示部 D3. if ( 環境情報が変化 ) {. 渋滞発生部ＣＡ. 集団の再生成;. ダイクストラ法. genetic operation ( ); } if ( 移動体情報が変化 ) {. D1 D1 ナビ研Ｓ規格地図. D5. 現在地を出発地とする; D4. genetic operation ( ) ;}. D3 D2. if ( 目的情報が変化 ) { 新しい目的地を入力;. システム制御部. 現在地を出発地とする; 図２システムの構成. 集団を初期化; genetic operation ( ); }}. 表２システムで受け渡されるデータ. } procedure genetic operation ( ){. D１. ノード番号・隣接ノ－ド番号・距離道路種別・車線数・方位・信号・座標. D２. 距離・道路種別・車線数・座標. D３. ノード番号列・座標. D４. 渋滞数ノード数・渋滞ノード番号・座標. D５. 現在地・渋滞の位置・現在時間. 制限時間までループ { 経路の適応度の評価; 選択と交叉; 走りやすい道路の適用; }} }. 図３本手法のアルゴリズム. −40−.

(5) りやすい道路を示している[3]。図４で車が現在. 250. 地点にさしかかったとき、推奨経路上の破線部. 200 Traffic. で渋滞が発生したと仮定する。このとき渋滞回避経路を次のように求める。. 150 100 50 0. [step1] k=1,…, kmax まで step2 と step3 を繰り返す. 0. 。（kmax は集団サイズ） [step2] Rk と Re が渋滞の手前で交叉していると. 0.5 Density. 1. 図５密度と交通量の関係（つくば市）. きは、現在地から Rk を経由して目的地に至る経路を迂回路の候補として登録する。 [step3] Vt が渋滞の手前で Re と Rk の両方と交叉しているときは、現在地から Vt と Rk を経由して目的地に至る経路を迂回路の候補として登録する。 [step4] 登録された経路を新たなＧＡ集団とする。 Rk. 現在地. 目的地. 目的地. Vt. Rk Re. Re 出発地. 出発地. 現在地. 図６シミュレーション開始前の図４渋滞回避経路の生成. 地図（つくば市）. 4 評価実験 4.1 交通量本手法を評価するため、ナビ研Ｓ規格地図を用いて、つくば市と東京都で道路交通シミュレーションを行った。1 つのセルは 5.5m､1 タイムステップは 2 秒とし､速度の上限はそれぞれの道路の制限速度とした｡つくば市の地図を対象として、特定の道路を t=0～1000 に通過した車の台数（交通量）を計測した。t=0 のときの基本道の密度を 0.1 に固定し､主要道の密度を0 から1 まで変化させたときの交通量を図５に示す｡ここで密度とは、その道路の全セルに対する車の存在するセルの割合で. 図７５分後の渋滞状況ある。主要道の密度が 0.2 以上のとき、渋滞が発生していることがわかる。. −41−.

(6) ては、車の所要時間の他に、信号数、曲がる回数、道路の広さ、車線数、道路種別等が含まれている [3]。比較のため、ダイクストラ法のコスト関数は、車の所要時間のみとした。また、ダイクストラ法の計算範囲は、出発地と目的地を含む長方形の内部に限定した。所要時間の見積もりは、探索を開始した時刻に各道路を通過している車の速度を用いた。探索結果を図１０と表３に示す。ダイクストラ法は厳密解法であるため、所要時間最小の経路を選定している。これに対して本手法は、所要時間は 2.6 分長くなっているものの、走りやすい経路. 図８１０分後の渋滞状況. （曲がる回数と信号が少ない）を選定している。特に計算時間はダイクストラ法の７０倍以上高速であり、リアルタイム性に優れているといえる。ダイクストラ法において、本手法と同じコスト関数を用いることも可能であるが、計算時間が大幅に増加することになる。. 表３経路探索結果. 図９１５分後の渋滞状況. 評価項目. 本手法. ダイクストラ法. 所要時間（分）. 31.6. 29. 曲がる回数. 2. 6. 信号数. 23. 29. 計算時間（秒）. 0.06. 4.34. 図６から８は、t=0 において全道路密度を 0.1 としたときの５分ごとのシミュレーション結果. 出発地. を示している。t=0 のときは、地図上の車の台数は 11980 台であった。また、図中の太線は、車の速度が制限速度の 1/3 以下になった道路を表している。交通流が時々刻々と変化している様子がわかる。目的地ダイクストラ. 4.2 経路案内東京都の地図を用いて、本手法とダイクストラ. 本手法. 図１０経路案内の例（東京都）. 法で経路探索を行った。本手法のコスト関数とし. −42−.

(7) 5. おわりに. [4] ブイ,柏崎,高橋,狩野:集団の再利用に基づくＧＡによるカーナビゲーションのための動的経路探索,計測自動制御学会論文集, Vol.36, NO.9,. 本稿では、ナビ研Ｓ規格地図を用いた広域道路. pp.789-796(2000).. 交通シミュレータの開発事例を紹介した。また、このシミュレータを用いた実験により、遺伝的ア. [5] H. Kanoh, H. Kozuka: Evaluation of GA-Based. ルゴリズムは、ダイクストラ法に比べてほぼ同程. Dynamic Route Guidance for Car Navigation. 度の経路をリアルタイムに計算できることを確認. Using Cellular Automata, IEEE Intelligent. した。都市部における経路探索においては、渋滞. Vehicle Symposium , (2002).. 情報を加味することが必須と考えられるので、本. [6] H. Kozuka, Y. Matsui, H. Kanoh: Traffic Flow. Simulation. シミュレータの有用性は高いと考えている。. using. Non-equilibrium. 今後､本シミュレーションと実際の交通との比較. Cell. Automata. Environment,. under IEEE. 検討が必要である。またここでは車の進行方向をラ. International Conference on Systems, Man, and. ンダムに決定しているが､何割かの車に目的地を持. Cybernetics, pp.1341-1345 (2001). [7] ナビゲーションシステム研究会:Format Guide. たせた場合の検討も重要であると考える｡. Book S 規格(Version2.2),(1997).. 現在、規制緩和により、（財）日本道路交通センターが提供する道路交通情報を利用して民間企業が交通情報サービスを提供できるようになることも決定している。都市部の交通量は、社会生活と密接な関係にあり、今後、交通量予測がいろいろな面で重要な課題となってくることが予想される。. 謝辞. [8] 土木学会：交通ネットワークの均衡分析，丸善， (2000)． [9] 森津：国内外の交通シミュレーションモデル，第３７回土木計画学シンポジウム論文集， pp.99-106，(2001)． [10] 久井：交通流のモデリングと信号制御，計測と制御，Vol.41, No.3, pp.193-198 (2002). [11] 加藤:セルオートマトン法による道路交通シミュレーション,人工知能学会誌,１５巻２号,pp.242-250 (2000).. ナビ研 S 規格地図の CD-ROM フォーマットに関する資料をご提供いただいた IT ナビゲーショ. [12] Kai Nagel and steel Rasmussen: Traffic at the edge of chaos, ARTIFICIAL LIFE. ンシステム研究会殿に感謝の意を表します｡. , pp.222-235. (1994).. 参考文献 [1] 山崎敏夫：ナビゲーションシステム体系と今後の展開,人工知能学会誌,Vol.15,No.2,pp.226-231 (2000).. [13] 上川,梅津：車載ナビゲーションシステムの経路探索技術, 計測と制御, 第３６巻第１１号,pp.790-792(1997).. [2] 狩野：高度道路交通システムとＡＩ, 人工知能学会誌､ Vol.15, No.2, pp.222-225 (2000). [3] 狩野,中村信昭,中村友洋: 知識の集団を用いた GA による不特定な立ち寄り地を含む経路探索, 人工知能学会論文誌, Vol.17, No.2 D, pp.145-152 (2002).. −43−.

(8)