プローブ情報を用いた渋滞予測に基づく最適経路の視覚化
2002MT048 三宅 真悟
指導教員

1 はじめに自動車を利用して時間内に目的地に到着する為に，交通渋滞を避けたいと考えることは明白な事実である．現在では，都市過密化により都市交通ネットワークは成長し，より複雑になっている．これに伴い，複雑な渋滞パターンをもたらし，容易に渋滞を避けることは困難である．その中で，自動車での効率的な移動において，適切なルート選択と正確な渋滞予測が必要不可欠である．
現在，交通渋滞は多くの都市で問題となっている．大きな問題点としては，タクシーや自動車を用いた移動で時間内に目的地に到着できないことである．渋滞を引き起こす要素には，都市エリアでの急速な人口と事業の成長や自動車の普及による徹底的な使用，新しい道路を開通しないこと，さらに，公共交通機関を利用しないことなどが挙げられる．交通渋滞の特徴として，交通渋滞パターンは複雑で，いたる箇所で発生することが挙げられる．また，交通渋滞はある位置で発生した後，時間が経過するにつれて広がっていく．他にも交通渋滞には時間に伴うラッシュに加え，不確定要素である工事，交通事故，天気などによって発生する場合もある．
そこで，本研究では，ある出発点から目的地 (以下，O-D 間) までスムーズな移動ができるように渋滞を考慮した最適経路を視覚化することを目的とする．渋滞を予測するために，GPS を搭載したインターネットタクシーのプローブデータを使用し，交通渋滞の視覚化を行い，その渋滞地点を考慮した上で，ある O-D 間の最適経路の視覚化を行う．渋滞判別プログラムによって渋滞地点を認識するが，速度から渋滞と判断するために適切な閾値が必要とされる．また，パーキングブレーキのフラグを見ることによって停車と渋滞を区別する．渋滞判別プ
ログラムによって渋滞と判断された地点を実際の地図上にマーキングすることにより渋滞の視覚化を行う．その結果を用いて，大規模渋滞地点と小規模渋滞地点の経路のノード間距離にそれぞれ異なった重みを加え，最短経路プログラム (Dijkstra プログラム)[1] を使用することによって最適経路を視覚化する．

2002MT060 奈良 浩和

河野 浩之
るので，センサーが設置されていない箇所の交通データの取得は困難である．また，悪天候により電波妨害が生じ，正確なデータを取得できないという問題点がある．
2.2 解決方法の提案
本研究では，GPS を搭載したタクシーから取得されたプローブデータを使用し，[2] と同様に交通渋滞の視覚化を行う．この動的データを使用することによって，静的データでは認識できなかった地点の渋滞認識が可能となる．また，電波妨害による影響を受けにくいので，正確なデータ処理をすることができる．さらに，このプ
ローブデータを用いて表示した渋滞地点を考慮し，あるO-D 間での自動車の移動における最適経路を提案することができる．

3 最適経路表示までの過程とプローブデータ
3.1 渋滞を考慮した最適経路表示までの過程
図 1 は，本研究において渋滞を考慮した最適経路表示までの流れを示したシステム図である．始めにプロー
ブデータを PostgreSQL8.0.4+PostGIS*1 に格納していき，条件付出力によって本研究で使用する必要なデータのみを抽出する．抽出されたデータを渋滞判別プログラ
ムに代入し，速度から渋滞と判断することにより，渋滞地点の発見を行う．渋滞と判断された地点をプロアトラ
ス SV 全国版の地図上にマーキングすることにより，渋滞地点の視覚化を行う．次に，最短経路を求めるダイクストラプログラムを用いて経路探索を行う．渋滞判別プ
ログラムによって渋滞と判断された地点の経路のノード間距離に重みを加えるが，渋滞表示の結果から把握できた大規模渋滞地点と小規模渋滞地点にそれぞれ違った重みを加える．重みを加えた経路をダイクストラプログラ
ムに代入することによって渋滞を考慮した最適経路の視覚化が可能となる．

2 交通渋滞に関する関連研究
2.1 センサーによる静的データから交通渋滞を視覚化する研究[2] は，ミネソタ大学交通管理センターの高速道路操作グループによる交通渋滞を視覚化する研究である．道路に設置された複数のセンサーにより交通データを取得し，そのデータを基に交通渋滞のパターン発見や視覚化を行う．しかし，取得した交通データは静的データであ

図 1 渋滞を考慮した最適経路表示までの過程

3.2 プローブデータ
本研究で使用するプローブデータは，過去の愛知県下における 1 年間の期間に，GPS を搭載した約 1500 台の*1 http://www.postgresql.jp/

タクシーから取得されたデータであり，合計 10GB 程度の大容量サイズである．プローブデータは，およそ 30秒〜1 分毎の間隔に受信されており，その時間における瞬間的なデータである．データの中身は，タクシー ID，時刻，速度，加速度，緯度，経度など 40 項目程のさまざまな情報が記載されている．このプローブデータをPostgreSQL に格納する．実際に格納した結果の一部を図 2 に示す．尚，50 台分のタクシーデータを格納するとおよそ 5 万行程になる．

時に注意しなければならないことは，プローブデータに記載されている速度は，ある時間における瞬間的な速度なので，信号待ち，右左折による減速時の速度も含まれているということである．そのため，およそ 3 分〜5 分における速度の平均を計算することによって，この問題点を解決することができる．この平均速度を用いて渋滞判別を行う．さらに，異なったデータ型の緯度・経度もプログラム内で元のデータ型に戻す．以下，渋滞判別プ
ログラムの全体の流れのフローチャート (図 3) とフローチャートの説明を示す．

図 3 渋滞判別プログラムのフローチャート

図 2 PostgreSQL に格納したプローブデータの一部

プローブデータの緯度・経度は，例えば，東経 136 度
40 分 40 秒⇒ (136*3600+40*60+40)*256=125962240のようにデータ型が違って記載されている．これは，渋滞地点の視覚化時に使用するため，後の渋滞判別プログ
ラム内で正式な緯度・経度のデータ型に戻して表示させる必要がある．

4 渋滞を考慮した最適経路の視覚化
4.1 実験に使用するデータの抽出
プローブデータには，本研究で使用しないデータも含まれているので，PostgreSQL から渋滞判別プログラムで使用するデータのみを条件付出力コマンドを用いて抽出する．条件指定により，ある時間内のみのデータの抽出，さらに，緯度・経度を指定することによって，指定範囲のデータの抽出が可能となる．この抽出結果を渋滞判別プログラムに代入し，渋滞判別を行う．
4.2 渋滞判別プログラム
プローブデータの速度から渋滞と判断するために，渋滞判別プログラムを使用する．また，停車を渋滞と判断しないように，パーキングブレーキのフラグを見ることによって区別する必要がある．このプログラムに，条件付出力によって抽出したデータを代入する．データ代入

1．停車・通常・渋滞状態の判別を開始する 2．PostgreSQL から抽出したデータを読み込む 3．抽出したデータは，ある時間における瞬間的なデータなので，3分〜5 分程度の平均速度を計算する．また，緯度・経度も計算し，度分秒で表した形式に戻す 4．3 で計算した平均速度が 10km/h 以下の場合，停車・渋滞の状態を区別するためにパーキングブレーキのフラグを見る 5．
パーキングブレーキを確認する 6．パーキングブレーキ
が ON の場合は，停車と判断する 7．パーキングブレー
キが OFF の場合は，渋滞と判断する 8．4 で平均速度が 10km/h を超える場合は，閾値である 20km/h と比較する 9．平均速度が 20km/h 以下の場合は，渋滞と判断する 10．平均速度が 20km/h を超える場合は，通常と判断する 11．全てのデータを判断し終えた結果をファイルに出力する 12．停車・通常・渋滞状態の判別を終了する．
渋滞判別プログラムの結果，各時間毎に停車・通常・渋滞状態が区別して表示される．この結果を用いて，渋滞と判断された緯度・経度をプロアトラス SV の地図上の緯度・経度に照らし合わせてマーキングを行う．
4.3 渋滞判別のための閾値
渋滞判別プログラムの中で，速度から渋滞と判断するために閾値が必要とされる．現在，一般道路で渋滞とされている定義は，警視庁交通部では 20km/h 以下，国土交通省道路局では 10km/h 以下とされている．本研究では，一般道路のデータを使用する．そこで，速度から渋滞と判断するための閾値は，警視庁交通部で使用している 20km/h 以下とする．
4.4 渋滞地点の視覚化
図 4 は，2002 年 10 月 1 日，愛知県名古屋市千種区付近において 50 台分のタクシーデータによる AM8 時〜AM9 時までの渋滞地点をマーキングした結果である．
結果から，点の密度が高い地点は大規模渋滞，点の密度が低い地点は小規模渋滞と読み取ることができる．さらに，AM7 時〜AM8 時で同じ 50 台分のタクシーデータを用いて視覚化を行い，AM8 時〜AM9 時の視覚化結果と比較すると，AM8 時〜AM9 時の方が渋滞地点の範囲が広がっており，AM7 時〜AM8 時で小規模渋滞であった地点が通常状態になっているという結果を得ることができた．つまり，小規模渋滞は時間が経過するにつれて通常状態に戻り，大規模渋滞は時間が経過するにつれて広範囲に広がっていくと言えるのである．また，2002 年
10 月 1 日は平日であり，AM8 時〜AM9 時は朝のラッシュ時刻であることから，交通量が増えたことにより渋滞の範囲が広がったとも考えることができる．

4.6 最適経路の視覚化
今まで述べてきたことを考慮した上で，最適経路の視覚化を行う．実験では，図 4 の渋滞情報を使用し，上社IC 付近の範囲で経路探索を行う．経路探索において必
要なノード番号，ノード数，リンク数，ノード間距離は
図 5 のように定め，ノード番号 0 を出発点，ノード番号16 を目的地とする．また，渋滞を迂回するためには通らないような道幅の狭い道路は含まず，図 5 の太線，つまり道幅の広い道路のみを用いて経路探索を行う．

図 5 経路探索するためのリンク，ノード，ノード間距離情報

今回は，以下の 3 つの実験を行い，各実験によって導かれた経路をそれぞれ経路 1，経路 2，経路 3 とする．

• 実験 1• 実験 2

渋滞を考慮しない最短経路を表示
大規模渋滞地点と小規模渋滞地点にそれぞれ異なった重みを加え，最適経路を表示• 実験 3 大規模渋滞地点と小規模渋滞地点に同じ重みを加え，最適経路を表示
実験 1 の結果を図 6 に示す．経路 1 は，目的地までの最短経路である．
図 4 AM8 時〜AM9 時における 50 台分のタクシーデータを用いた渋滞地点の視覚化

図 4 のように渋滞地点を視覚化した結果を基にして，渋滞地点の経路のノード間距離に重みを加える．その経路をダイクストラプログラムに代入し，渋滞を考慮した最適な経路探索を行う．
4.5 重みの重要性
本研究では，渋滞地点を考慮した経路探索をしなければならない．そのためには，渋滞による移動損失時間を考慮した重みを加える必要がある．そこで，大規模渋滞によって隣接ノードまでの移動時間が，渋滞地点の平均速度との比較により本来の 3 倍に増えると予想し，大規模渋滞地点の経路のノード間距離を 3 倍するという重みを加える．また，小規模渋滞では，移動時間が本来の 2倍に増えると予想し，小規模渋滞地点の経路のノード間距離を 2 倍するという重みを加える．

図 6 経路 1：渋滞を考慮しない目的地までの最短経路

次に，実験 2 を行うが，渋滞地点を視覚化した結果から図 7 のように渋滞地点が既に把握できている．渋滞情報から，リンク 0〜1，0〜4，4〜6，5〜6，5〜7，6〜8，6〜12，12〜13 は大規模渋滞地点，リンク 3〜10 は小規模渋滞地点と読み取ることができる．

5 実験のまとめ
実験の結果，経路 2 では迂回している渋滞地点を経路3 では通っている．つまり，重みを減らすことによって，

図 7 実験範囲の AM8 時〜AM9 時における渋滞地点

大規模渋滞地点の経路のノード間距離に，大規模渋滞による移動の損失時間を予想した重みである 3 倍を加え，小規模渋滞地点の経路のノード間距離に，小規模渋滞による移動の損失時間を予想した重みである 2 倍を加えて実験 2 を行う．結果を図 8 に示す．

渋滞地点を通った方が移動時間が短いと判断されたということである．また，渋滞を考慮した経路と，渋滞を考慮しないで渋滞地点を通った最短経路のガソリン代，移動時間，目的地への到着時間の面から考察すると，渋滞を考慮した経路では，迂回する分だけ移動距離が長くなりガソリン代が増えてしまうが，渋滞地点を通る最短経路より早く目的地に到着することができる．一方，渋滞地点を通る最短経路では，渋滞による継続した速度低下により，燃費が悪化 [3] してしまうので，渋滞を迂回した分のガソリン代と同じ程度かかってしまう．さらに，渋滞により到着時間の遅れも生じてしまう．つまり，渋滞を考慮した最適経路を通ることにより，最短経路と同じガソリン代で目的地に早く到着できるのである．

6 おわりに渋滞を考慮した目的地までの最適経路を視覚化することができたが，必ずしもユーザーの最適条件を満たす経路とは限らない．数百台のタクシーの渋滞情報を使用した広範囲での実験や，渋滞による統計的な移動損失時間を考慮した重み，さらには，道幅，右左折の数などを考慮した適切な重みの提案が今後の課題となっている．
私たちが交通データを有効に活用することでスムーズな交通ネットワークを作りあげることができるが，誰もが同じ交通データを活用すると逆効果となってしまい，別の場所で交通渋滞が発生してしまうという問題がある．現在では，このような交通データを有効に活用する為のさらなる研究も行われている．

図 8 経路 2：渋滞を考慮した目的地までの最適経路

最後に実験 3 を行う．実験 3 では，大規模渋滞と小規模渋滞の重みを同じ 2 倍にして実験を行う．実験 2 の結果を図 9 に示す．

謝辞
本研究を進めるにあたり，最後までご指導して頂いた
河野浩之教授，共にそれぞれの研究を進め，さまざまな助言をして頂いた河野研究室の仲間に深く感謝しています．

参考文献

図 9 経路 3：重みを変えた場合の目的地までの最適経路[1] 浅野，増澤，和田著， IT TEXT アルゴリズム論,
pp.119-121，オーム社，2003．
[2] Shashi Shekhar，Chang-tien Lu，Sanjay Chawla，Pusheng Zhang， Data Mining and Visualizationof Twin-Cities Traffic Data, Technical Report TR
01-015，University of Minnesota，2001.8．
http://www.cs.umn.edu/tech_reports_upload/tr2001/01-015.pdf (accessed 2005.9)[3] 交通エコロジー・モビリティ財団， エコ交通に関する調査研究報告書, 日本財団図書館，1999．
http://nippon.zaidan.info/seikabutsu/1999/00075/contents/029.htm (accessed 2006.1)