修 士 論 文 概 要 書
提出
2008 年 2 月 学籍番号
3606U018–6
CD専門分野 情報・ネットワーク専攻 研究指導 情報システム設計研究
氏 名
大高 宏介
指 導
教 員
戸川 望 印
研 究
題 目
進路方向ごとに異なる混雑度を考慮した旅行時間算出手法 1 まえがき
現在，車両から取得した走行履歴の情報を元に旅行時間 を算出するサービスが，VICSや各自動車メーカによって提 供されている．しかしこれらのサービスによって提供され る旅行時間の算出精度は十分高いとは言えない．この原因 の１つとして，交差点において進路方向によって通過する までの時間が異なる場合があったとしも，リンク旅行時間 に反映されていない点が挙げられると考えた．そこで我々 は，次の特徴を持つ旅行時間算出手法を提案し，これによ り，各交差点において進路方向ごとに混雑度が異なること を考慮した旅行時間の算出を，わずかなデータサイズの増 加で実現可能とした．(1)同一リンクでもその先の進路方向 ごとに個別にリンク旅行時間を作成する．(2)(1)の対象と なるリンクを，進路方向によって混雑度に大きく差が生じ るリンクに限定する．
交通流シミュレータNETSIMを用いた実験では，10％以 上の旅行時間の算出精度の向上が得られた．また，データサ イズと算出精度とのトレードオフについても，データサイ ズを極端に重視した場合の評価を除いた概ねの評価で，提 案手法が従来手法を上回る結果が得られた．
2 既存の手法の問題点
既存手法では，リンクを通過後にどの方向へ進んだかに 関係なく単一のリンク旅行時間が作成される．従って，例 えば「直進する場合はすいているが右折する場合は混雑し ている」といった状況を考慮できないことが問題である．
一方で，テレマティクスのうちインターナビでは，高速 道路の分岐点において車線ごとの混雑度を考慮した旅行時 間が提供されている．ただしこれは，高速道路の特性から
「分岐点では進路方向によって混雑度に差が生じる可能性が 高い」と経験則として判断した結果対象としているにすぎ ないため，一般道には適応できないことが問題である．
3 提案手法の基本概念
提案手法は，既存手法の持つインフラ，すなわち移動体 通信により車両から走行履歴情報を取得できる環境を利用 した手法として位置付ける．その上で，走行履歴情報を元 に進路方向によって生じる混雑度の差が大きなリンクを特 定し，そのリンクではリンク旅行時間を進路方向によって 個別に作成する点に特徴を持つ．
3.1 リンク旅行時間の特徴
図1は，提案手法におけるリンク旅行時間の例であり，図 中の矢印と数字は，進路方向およびその時にリンクを通過 するのに要する時間を表す．このように，同一のリンクで もその先の進路方向によって個別にリンク旅行時間を作成 することを1つ目の特徴とする．
一方で，リンク旅行時間の細分化によりデータベースの データサイズが大きくなると，必ずしも優れた費用対効果 が得られるとは限らない．そこで，進路方向ごとに生じる 混雑度の差が小さいリンクではリンク旅行時間を進路方向
45 40 180
75 20 20 220
140 60
70
P1 P3
P6
P7 P4
P5
P2
図1: 提案手法におけるリンク旅行時間の例
道路地図
ノード情報 Step Step Step StepD1D1D1D1
リンク旅行時間格納領域 Step
Step Step StepD2D2D2D2
ノード・リンク情報抽出
データ構造決定
データベ データベ データベ データベースースースース
StepStep
StepStepD3D3D3D3 リンク旅行時間格納
StepStepStepStepD5D5D5D5CDF決定 StepStepStepStepD4D4D4D4リンク追加
図 2: データベース作成フロー
ごとに区別しないことを2つ目の特徴とする．これにより，
算出精度とデータサイズのトレードオフの向上を目指す．
3.2 ノードの種類
1つのリンクに対して次のように3種類のノードを定義 する．リンク元ノードであるノードをSN，リンク先ノー ドであるノードをP N，リンク先となるノードを通過した その次に通過するノードであるノードをDNと定義する．
提案手法における進路方向とは，「右左折」や「直進」などの 単語ではなく，「リンク先のノードを通過後，一番最初に通 過するノード」と定義する．すなわち，進路方向とはDN のことである．
4 提案手法のためのデータベース作成手 順と旅行時間算出手法
前章で提案した概念を実現するためのデータベース作成 手順の提案，およびそのデータベースを用いた旅行時間算 出手法の提案をする．
4.1 データベース作成手法
図2は，提案手法において旅行時間を算出するために用 いるデータベースの作成フローである．ここで，「対象とす るリンクで進路方向を考慮するか否か」を決定する項目と して「CDF(Course Direction Flag)」を定義する．CDF
61 62 51 52
46 79 88
30 46 79
LTT table
SN PN
DN
…
…
…
LTT table
LTT table
LTT table 28 44
…
53 …
(b) CDF=0のリンク (a) CDF=1のリンク (リンク30→51)
(リンク28→61)
150 152 155 156 156
… …
… …
(c) LTTtableの構造
LTT 30,51,46 ( t100) リンク旅行時間[sec ]
時間帯 No.
100 101 102 103 104
図3: データ構造
は，各リンクごとに与えられ，進路方向を考慮するリンク
では1，そうでないリンクでは0のいずれかの値を持つ．
StepD1.ノード・リンク情報抽出
実際の道路地図からノードとリンクの配置に関する情報 を抽出し，それらをリスト化した「ノード情報」を作成する．
StepD2.データ構造決定
StepD1で作成されたノード情報を元に，データベースの
データ構造を決定する．各リンクごとに用意するリンク旅 行時間の格納領域をオブジェクトとして扱い，これを以下
「LTTtable」と呼ぶ．データ構造の例を図3に示す．
StepD3.リンク旅行時間格納
データ構造が決定した領域に対してリンク旅行時間を格 納することで，データベースを作成する．
StepD4.リンク追加
このステップは，リンク旅行時間の格納の際に，SN，PN，
DNの全てが一致する格納場所が存在しない場合に処理す る．この時には，StepD1のノード情報作成時に新たなリン クを追加し，再びStepD3を処理することで対応する．す なわち，既知でないリンクが発生した時でも単純な処理で 対応でき，この点が，本論文で右左折や直進などの単語で はなくノードを進路方向として定義することの利点である．
StepD5.CDF 決定
このステップは，進路方向ごとに生じる混雑度の差が小 さいノードでは進路方向を考慮しないことで，旅行時間の 算出精度とデータベースのデータサイズのトレードオフの 向上を目的としている．そこで，リンク旅行時間の進路方 向ごとのばらつきの度合いを「分散度」として定式化し，こ の分散度の小さいリンクではCDF = 0としてStepD2を 再処理することでデータ構造を変更する．
4.2 旅行時間算出手法
入力する経路をR=p1→p2→ · · · →pNとして，旅行 時間を算出する．図1の例を用いると，経路P1 →P2 → P3→P4→P5の旅行時間の旅行時間の算出時のリンク旅 行時間はそれぞれ75，180，220，70が選択され，その合計 である545が算出結果として出力される．
5 評価実験
交通流シミュレータ「NETSIM」を用いて提案手法を評 価する．評価項目は，旅行時間の算出精度および，算出精 度とデータサイズのトレードオフである．
0.00 0.50 1.00 1.50 2.00 2.50 3.00 3.50 4.00
0 0.2 0.4 0.6 0.8 1 1.2
p = 1.0 p = 0.5 p = 1.5
CDF率
PED
p = 2.0
図4: CDF 率 とP EDの関係
5.1 旅行時間の算出精度
NETSIM上で発生させた交通流のデータから，既存手法
および提案手法のそれぞれに基づいてデータベースを作成 し，それを元に算出した旅行時間の算出精度を比較する．
15個の入力経路に対して検証した結果，旅行時間の算出 精度はいずれのCDF率でも既存手法から向上し，最低でも 10%以上(CDF 率= 0.1の時)，最大で13.2%(CDF 率= 1.0の時)の向上が得られた．
5.2 算出精度とデータサイズとのトレードオフ
旅行時間の算出精度と，各CDF 率 におけるデータベー スのデータサイズを元にトレードオフを評価する．評価指標 P EDを以下のように定義する．ERRは算出誤差，SIZE はデータサイズである．
P ED(x) =ERRtrad ERR(x) ·
(SIZEtrad SIZE(x)
)p
(1) 図4は，前節の結果を元に算出したP EDとの関係であ る．p= 2.0かつCDF 率≥0.9の時を例外として，それ 以外では全てP ED>1となり，概ねトレードオフに対する 評価でも既存手法に対する優位性を示せた．また，算出精 度とデータサイズのトレードオフはCDF 率= 0.2程度の 時に最良となることが分かった．
6 むすび
本論文では，テレマティクスをベースとした旅行時間の 算出手法を提案した．提案手法では，進路方向別ごとに個 別にリンク旅行時間を格納することで，同じリンクでも進 路方向によって混雑度が異なる状況を考慮し，その結果よ り高精度な旅行時間の算出を可能とする．さらに，各リンク ごとに進路方向による混雑度の差を求め，この値を元に進 路方向を考慮するリンクを自動的に決定することで，算出 精度とデータサイズのトレードオフの向上を実現する．評 価実験では，旅行時間の算出精度および，データサイズと のトレードオフの両方の評価項目において，既存手法と比 べ提案手法が有効であることを示した．また，旅行時間の 算出精度に影響するリンクは全体の２割程度であり，この リンクを対象として進路方向を考慮することで算出精度と データサイズのトレードオフが最良になることが分かった．
提案手法を応用することで旅行時間の短縮を目的とした 経路探索が可能になると考えられ，この点が今後の課題と して挙げられる．
研究業績 ITS研究会(2006.9.28) ITS研究会(2007.9.18)
電子情報通信学会論文誌（投稿中）
