進路方向ごとに異なる混雑度を考慮した旅行時間算出手法

(1)

2007 年度修士論文

進路方向ごとに異なる混雑度を考慮した旅行時間算出手法

指導教員戸川望准教授

早稲田大学大学院理工学研究科情報・ネットワーク専攻

3606U018–6 大高宏介

2008 年 2 月 8 日

(2)

第 1 _章

序論

(5)

第1章序論

1.1 本論文の背景と意義

近年のITSの進歩により，多くの人が交通情報サービスを受けられるようになった．交通情報の中でも特に重要とされるのが，車両が走行する経路の出発から到着までの所要時間(以下，「旅行時間」と言う)である．旅行時間を求める一般的な方法は，ノードから隣のノードまでの所要時間(以下，「リンク旅行時間」と言う)の和を求めることであり，このリンク旅行時間を取得する手段としては主に，VICS[1]や自動車メーカが提供するテレマティクス¹が挙げられる．

VICSは，1996年に(財)道路交通情報通信システムセンタによって開始された交通情報提供サービスである．リンク旅行時間は，光ビーコン²を用いて車両のIDを取得し，2つの地点で同一のIDが取得された時に2点間の通過時刻の差を求めることで作成される．テレマティクスは，各自動車メーカが自社ユーザ向けに，交通情報の提供を目的として独自に展開しているサービスであり，トヨタのG-BOOK[2]，日産のカーウィングス[3]，ホンダのインターナビ[4]などがある．テレマティクスの特徴としては，携帯電話や車両に搭載された DCM³などの通信機器を媒体にして，車両が情報の送受信をしている点にある．リンク旅行時間は，走行中の車両から通信機器を用いて送信された走行記録(通過地点および通過時刻) を元に作成される．

これらのリンク旅行時間の実測値との誤差は，VICSでは5〜51%，特に光ビーコン設置間隔が500mであるリンクでの平均で21%[5]，会員数最多のインターナビで2〜43%生じた検証結果がある[4]ように，いずれもいかに精度を高めるかが課題となっている．我々はこの原因の1つとして，「進路方向ごとに混雑度が異なる場合を無視している」点が挙げられると考えた．

VICSやテレマティクスにおけるリンク旅行時間は，交差点を通過後に直進したのか，あるいは右左折したのかに関係なく，対象となるリンクを通過した全ての車両の通過時間の平均値を求めることで作成されている．従って，「直進する場合にはすぐ通過できるが，右折する場合には時間がかかる」ような交差点でも直前の交差点からの所要時間は一律の値となるため，実際の混雑状況が旅行時間の算出に正しく反映されない可能性がある．

例外としてインターナビでは，高速道路の分岐点において車線ごとの混雑度を考慮した旅行時間が提供されている．ただしこれは，高速道路の特性から「分岐点では進路方向によって混雑度に差が生じる可能性が高い」と経験則として判断できるため対象としているにすぎない．交差点数が膨大な一般道においては，全ての交差点で進路方向によって異なる混雑度

1テレマティクスとは，Telecommunication(通信)とInformatics(情報処理)をつなげた造語である．

2光ビーコンとは，指向性が非常に高い近赤外線技術を応用した，走行車両の車載装置との双方向通信機能と車両感知機能を併せ持つ装置である．小型で低価格であることを特長とし，主に一般道の路上に設置され，

120km/hで走行する車両に対して1Mbpsでデータの送受信が可能である．

3DCMとは，Data Communication Moduleの略であり，G-BOOKにおける専用無線通信端末を指す．

(6)

第1章序論

を考慮する(以下，「進路方向を考慮する」と言う)にはデータサイズの観点から現実的でない可能性が高く，一方で高速道路のように経験則から進路方向によって混雑度に差が生じる交差点を特定することも困難である．

以上より，正確な旅行時間の算出のためにリンク旅行時間が満たすべき条件は以下の2点であると考えた．

条件1 1つのリンクに対して進路方向ごとに個別にリンク旅行時間を格納する．

条件2 進路方向を考慮するリンクの対象を，進路方向によって混雑度に大きな差が生じるリンクのみに限定する．

そこで本論文では，この2つの条件を共に満たした旅行時間の算出手法を提案する．既存のインフラを利用することを前提として，データベース作成時に同一のリンクでも進路方向によって個別にリンク旅行時間を格納することで条件1を満たし，旅行時間の算出精度の向上を目指す．次に「分散度」を導入し，リンクごとに進路方向による混雑度の差の大きさを比較する．この分散度の値が大きいリンクのみで進路方向を考慮することで条件2を満たし，算出精度とデータベースのデータサイズとのトレードオフの向上を目指す．最後に，交通流シミュレータを用いた評価実験により，旅行時間の算出精度および，データサイズとのトレードオフの観点から提案手法の有効性を検証する．

(7)

第1章序論

1.2 本論文の概要

本論文の概要は以下の通りである．

第2章「既存の旅行時間算出手法におけるリンク旅行時間」では，本論文で扱う単語を明確化した上で，既存手法の問題点を列挙する．まず本論文で扱うノード，リンク，道路グラフおよびリンク旅行時間を定義する．次に，既存の旅行時間算出手法であるVICSおよびテレマティクス(以下，これらを「既存手法」とする)におけるリンク旅行時間の概要を説明する．最後に，既存手法におけるリンク旅行時間の特徴と問題点を挙げ，その問題点から旅行時間算出手法が満たすべき条件について考える．

第3章「進路方向を考慮した旅行時間算出の基本概念」では，進路方向を考慮した旅行時間算出のための基本概念を説明する．まず始めに，提案手法はテレマティクスをベースとした手法として位置づけているため，この理由について述べる．次に，同一のリンクでも進路方向によって区別して扱うことを，提案手法におけるリンク旅行時間の特徴として提案する．

次に，提案手法内で用いる3種類のノードについて定義した上で，本論文における「進路方向」を定義する．次に，進路方向によって異なる混雑度を考慮するリンクとそうでないリンクを区別する理由を述べた上で，進路方向によって異なる混雑度を考慮するリンクを決定する概念を提案する．最後に，こららの概念を元にして作成したリンク旅行時間を用いて，出発地から目的地までの旅行時間を算出する手法を提案する．

第4章「進路方向を考慮した旅行時間算出のためのデータベース作成手順と旅行時間算出手法」では，前章で提案した概念を実現するためのデータベース作成手順を提案する．まずデータベース作成フローのStepD1からStepD5までを簡単に説明した後に，各ステップごとに処理の詳細を提案する．大まかな流れとしては，抽出した道路地図に関する情報を元にリンク旅行時間格納領域のデータ構造決定した後，リンク旅行時間を格納することで暫定的なデータベースが作成される．さらに，この暫定的なデータベースに対して補正を加えることで，最終的なデータベースが完成する．最後に，これらのステップを完了後に作成されるリンク旅行時間のデータベースを用いて，出発地から目的地までの旅行時間を算出する手法を提案する．

第5章「評価実験」では，交通流シミュレータ「NETSIM」を用いて提案手法を評価する．

評価項目は，旅行時間の算出精度および，算出精度とデータサイズのトレードオフの2項目である．1つ目の評価項目では，まず旅行時間の算出精度の評価方法を提案した後，シミュレーションによって得られた既存手法と提案手法の旅行時間の算出精度を示す．さらにその結果から分かることを述べる．次に2つ目の評価項目では，算出精度とデータサイズのトレードオフの評価指標となるP EDを定式化した後，1つ目の評価項目のシミュレーション結果を元に各CDF 率の時のP EDを算出する．さらにその結果から分かることを述べ，算

(8)

第1章序論

出精度とデータサイズとのトレードオフを考慮した時の最適なCDF 率の導出方法について考察する．

第6章「今後の課題」では，今後本論文をさらに発展させるための課題について検討する．

本論文の目的は旅行時間の算出であるため，今後の課題としては，この旅行時間算出手法を応用した経路探索が挙げられる．経路探索は，「距離の短縮」や「迷いにくさの向上」などの目的に応じて探索手法が異なるが，ここで対象とする経路探索は「時間の短縮」であり，この経路探索手法に関する概要を説明する．

第7章「結論」では，本論文の内容を統括する．

(9)

第 2 _章

既存の旅行時間算出手法におけるリンク旅

行時間

(10)

第2章既存の旅行時間算出手法におけるリンク旅行時間

2.1 本章の概要

本章では，既存手法について説明する．まず，本論文で扱うノード，リンク，道路グラフおよびリンク旅行時間を定義する．次に，既存の旅行時間算出手法であるVICSおよびテレマティクスの概要を説明する．最後に，VICSおよびテレマティクスにおいて旅行時間の算出に用いられるリンク旅行時間の特徴と問題点を挙げる．

以下，第2節では，ノード，リンク，道路グラフおよびリンク旅行時間を定義する．第3 節では，VICSおよびテレマティクスの概要を説明する．第4節では，ある測定結果を元にして旅行時間の精度が低下する原因について考た上で，その例を用いてリンク旅行時間の特徴と問題点を述べる．さらにその問題点を踏まえた上で，旅行時間の算出手法が満たすべき条件について考える．

(11)

2.2 ノード，リンク，道路グラフおよびリンク旅行時間の定義

本節では，ノード，リンク，道路グラフおよびリンク旅行時間を定義する．

ノード

「車両から道路上の地点および通過時刻を取得できる場所」をノードと定義する．VICS では，道路上に固定された光ビーコンを媒体として，車両を識別するための情報(以下，「車

両ID」と言う)をセンタへ送信することで，各地点ごとの通過時刻を得る．テレマティクス

では，車載通信機器を媒体として，車両IDに加えてGPS測位を元にした位置情報をセンタへ送信することで，各地点ごとの通過時刻を得る．本論文では，ノードを識別するための情

報(以下，「ノードID」と言う)がαであるノードを「ノードα」と表記する．

リンク

「ノードαからノードβまで，他のノードを通過せずにたどり着くことができる状態」を，

「ノードαとノードβがリンクされている」と定義し，以降はこのリンクを「リンクα→β」

と表記する．

道路グラフ

上述のノードとリンクから構成されるグラフを，「道路グラフ」と定義する．

リンク旅行時間

リンク旅行時間とは，1つのリンク上を走行するのに要する時間である．すなわち，リンク元であるノードαの通過時刻と，リンク先であるノードβの通過時刻との時間差を，リンクα→βのリンク旅行時間と定義する．

2.3 VICS およびテレマティクスの概要

本節では，既存の旅行時間算出手法であるVICSおよびテレマティクスの概要を説明する．

本論文では，これらの2つの手法を既存手法として定義する．

図2.1は，既存手法のシステム構成であり，図2.1中の「CERVISE CENTER」はVICSおよびテレマティクスのセンターを示す．図2.1(a)では，走行中の車両から何らかの無線通信により，以下に挙げる走行履歴に関する情報を取得する．

• 車両ID．

• 通過した地点に関する情報(交差点IDや位置情報等)．

• 上記の地点の通過時刻．

(12)

(b)Link Travel Time (d)Data Base

(c)Store (e)Calculate

(a)Uplink

User

(g)Course Information (f)Travel Time

S E R V IC E C E N T E R

Access Load

図 2.1: 既存手法のシステム構成

図2.1(b)では，図2.1(a)によって得られた情報を元にリンク旅行時間を作成する．図2.1(c) では，作成したリンク旅行時間を適当な場所に格納することで，図2.1(d)のデータベースが作成される．図2.1(e)では，図2.1(f)で示す車両から要求された経路に対して，旅行時間を算出し，その結果を図2.1(g)で示すように送信することで提供する．

VICSおよびテレマティクスによって特徴が異なるのは，図2.1(a)および図2.1(g)である．

以下では，VICSとテレマティクスの詳細を説明する．

2.3.1 VICS

VICSは，1996年に(財)道路交通情報通信システムセンタによって開始された交通情報提供サービスである．

図2.1(a)に関しては，光ビーコン[6][7]を用いて車両からの情報がアップリンクされる．車

両のIDを取得し，2つの地点で同一のIDが取得された時に2点間の通過時刻の差を求める

(13)

表 2.1: 進路方向によって混雑度が大きく異なる交差点の例場所時間帯進路方向所要時間 (1)県道13号線，浅間下 16:30 右折・直進 14’30”

交差点，横浜駅方面頃左折 2’00”

(2)国道1号線，保土ヶ谷 17:30 右折 9’15”

橋交差点，戸塚方面頃左折 0’45”

(3)環状2号線，駅入口交 9:00 右折 5’45”

差点，新横浜駅方面頃左折・直進 1’00”

ことで作成される．

図2.1(f)に関しては，車両からのアップリンクの際に用いる光ビーコンの他に，電波ビー

コン[1],[8]，FM多重放送[1],[9]の3種類を媒体として，VICSセンターから各車両へ交通情報を送信している．

前節の定義により，VICSでは「光ビーコンの設置場所」をノードと定義する．

2.3.2 _{テレマティクス}

テレマティクスとは，移動体に携帯電話などの移動体通信システムを利用してサービスを提供することの総称である．図2.1(a)の車両からのアップリンク，および図2.1(f)の車両への情報の送信は，車両と接続された携帯電話もしくはDCM等の専用端末などの移動体通信システムを経由して行われる．

前節の定義により，テレマティクスでは「各テレマティクスサービスが定めた，各車両が GPS測位と通過時刻の記録を行うべき場所」をノードと定義する．

2.4 リンク旅行時間の特徴と問題点

表2.1は，ある交差点において，渋滞の最後尾に到着してから交差点を通過するまの所要時間を，通過後の各進路方向ごとに測定した結果である．この結果から，同じリンクでも進路方向によっては所要時間に数倍の差が生じることが分かる．このような交差点が存在する以上，進路方向によって異なる混雑度を考慮しないことが，旅行時間の算出精度の低下につながり得ると言える．

では，このような旅行時間の差が生じる原因について考える．図2.2は，道路グラフと交通量の例であり，図2.2(a)は道路グラフの例で，図中のP₁,· · ·,P₅ はノードIDである．図 2.2(b)は，リンクP1→P2について，ノードP2を通過時の進路方向ごとの単位時間あたりの

(14)

P

⁴

(a) 道路グラフ

P

²

P

³

P

⁵

P

¹

(b) 進路方向ごとの平均所要時間および通過台数

進路方向

平均所要時間 [sec]

単位時間あたり通過台数

左折

T

^l

N

^l

直進

T

^s

N

^s

右折

T

^r

N

^r

図 2.2: 道路グラフと交通量の例

通過台数およびそれらの車両がリンクを通過するのに実際に要する平均時間の例である．

既存手法では，車両から取得されるノードIDおよび通過時刻には進路方向に関する情報は含まれない．従って，リンクを通過後にどの方向へ進んだかに関係なく，通過した全ての車両の1台あたりの所要時間の平均値がリンク旅行時間となる．すなわち図2.2の例では，リンクP₁→P₂のリンク旅行時間LT T(Link Travel Time)は，

LT T = T_l·N_l+T_s·N_s+T_r·N_r

N_l+N_s+N_r (2.1)

となる．

このリンク旅行時間を用いることの問題点は，実際の道路状況が旅行時間の算出に正しく反映されない可能性が生じることであり，この点が表2.1のような差の原因として考えられる．例として，図2.2(a)の道路グラフに表2.1(3)の混雑度をあてはめて考える．ある一定時間の左折の通過台数N_lが25台，直進の通過台数N_sが30台，右折の通過台数N_rが45台であったため，リンクP₁ →P₂のリンク旅行時間LT T は式(1)より，(60×28 + 60×33 + 345×39)÷(28 + 33 + 39) = 171[sec]となる．これは，ある1台の車両が実際に要した時間

が表2.1(3)と同じ時間であったと仮定すると，その車両に提供されるリンク旅行時間には左

折および直進の場合で64.9%，右折の場合で101.8%の誤差が生じることになる．すなわち，

進路方向によって混雑度に差が生じているような状況では，既存手法ではリンク旅行時間に大きな誤差が生じ，結果として旅行時間の算出精度の低下につながると言える．

(15)

例外として，テレマティクスのうちインターナビでは，高速道路の分岐点において車線ごとの混雑度を考慮した旅行時間が提供されている．ただしこれは，高速道路の特性から「分岐点では進路方向によって混雑度に差が生じる可能性が高い」と経験則として判断した結果対象としているにすぎず，分岐点の数が膨大な一般道においても同じように適用することはできない．また，全ての交差点で進路方向を考慮するにはデータサイズが膨大となるため，

いずれにしても対象が高速道路のみであることが問題として挙げられる．

以上に挙げる問題点により，旅行時間の算出手法が満たすべき条件として以下の2点が挙げられる．

(16)

2.5 本章のまとめ

本章では，本論文で扱う用語を明確化した上で，既存手法の問題点を列挙した．

第2節では，ノードを「車両から道路上の地点および通過時刻を取得できる場所」と定義し，リンクを「ノードαからノードβまで，他のノードを通過せずにたどり着くことができる状態」と定義し，道路グラフを「ノードとリンクから構成されるグラフ」と定義した．その上で，リンク旅行時間を「1つのリンク上を走行するのに要する時間」，すなわち，「リンク元であるノードαの通過時刻と，リンク先であるノードβの通過時刻との時間差」と定義した．

第3節では，既存手法におけるリンク旅行時間の特徴と問題点として以下の2点を挙げた．

1つ目は，リンクを通過後にどの方向へ進んだかに関係なく，通過した全ての車両の1台あたりの所要時間の平均値がリンク旅行時間となるため，実際の道路状況が旅行時間の算出に正しく反映されない可能性が生じることである．インターナビが例外として高速道路の分岐点において車線ごとの混雑度を考慮した旅行時間を提供しているが，これは高速道路の特性から「分岐点では進路方向によって混雑度に差が生じる可能性が高い」と経験則として判断した結果対象としているにすぎない．従って，分岐点の数が膨大な一般道においても同じように適用することはできず，これが2つ目の問題点である．以上に挙げる問題点により，旅行時間の算出手法が満たすべき条件として以下の2点が挙げられる．

(17)

第 3 _章

進路方向を考慮した旅行時間算出の基本

概念

(18)

第3章進路方向を考慮した旅行時間算出の基本概念

3.1 本章の概要

本章では，進路方向を考慮した旅行時間算出のための基本概念を提案する．第2節では，

提案手法の位置づけを，既存手法，その中でも特にテレマティクスをベースとした手法とする理由について述べる．第3節では，同一のリンクでも進路方向によって区別して扱う点を，

提案手法におけるリンク旅行時間の特徴として提案する．第4節では，議論の簡潔化の目的で提案手法内で用いる，3種類のノードについて定義した上で，本論文における「進路方向」

を定義する．第5節では，進路方向によって異なる混雑度を考慮するリンクとそうでないリンクを区別する理由を述べた上で，進路方向によって異なる混雑度を考慮するリンクを決定する概念を提案する．最後に第6節では，こららの概念を元にして作成したリンク旅行時間を用いて，出発地から目的地までの旅行時間を算出する概念を提案する．

提案手法は，既存手法におけるリンク旅行時間の問題点を踏まえ，1つのリンクに対して進路方向によって個別にリンク旅行時間を作成し，かつリンク旅行時間を進路方向ごとに個別に作成するリンクの対象を進路方向によって混雑度に大きな差が生じるリンクのみに自動的に限定することで，旅行時間の算出精度の向上とデータサイズとのトレードオフの向上の双方を目指す．

(19)

3.2 提案手法の位置付け

提案手法は，既存手法の持つインフラを利用した手法として位置付ける．すなわち，車両から情報を取得できることを前提とした上で，その情報を元に進路方向によって生じる混雑度の差が大きなリンクを特定し，そのリンクではリンク旅行時間を進路方向によって個別に作成する．

ここで，全交差点数に対するノード数について考える．2006年4月時点で全国の光ビーコンの設置箇所¹は約3万箇所[11]であり，リンク旅行時間を取得できる範囲はリンク数にして約8万個，距離にして約7万kmである[10]．一方，テレマティクスのうち会員数が最多のインターナビでは，2007年4月の時点でこの距離は約36万kmである[4]．従って，ノード数についてもインターナビはVICSと比較してはるかに多いと予想できる．これは光ビーコンの設置箇所でのみ車両の通過時刻を取得できるVICSに対して，GPS測位が可能な地点であればどこでもノードに設定することができるテレマティクスの特性に起因していると言える．

このような背景から，テレマティクスが旅行時間を提供する手法としてより優れると考えられるため，提案手法はテレマティクスのシステム内で実現することを前提とする．

3.3 進路方向によって異なる混雑度を考慮したリンク旅行時間

進路方向によって混雑度が異なる状況を考慮すべきリンクでは，リンクを通過後に進んだ方向によって車両を区別して考え，各進路方向ごとに個別に平均値を算出したものをリンク旅行時間として扱う．すなわち，1つのリンクに対して，進路方向の数だけリンク旅行時間を作成する．

図2.2の例では，リンクP1→P2のリンク旅行時間は，左折する車両にとってはT T Ll，直進する車両にとってはT T L_s，右折する車両にとってはT T L_rが作成される．表2.1(3)の例を用いて算出した場合，T T Ll=T_l = 60[sec]，T T Ls =T_s= 60[sec]，T T Lr=T_r = 345[sec]

となる．

3.4 ノードの種類

ここで，以降の論述の簡素化のため，1つのリンクに対して次のように3種類のノードを定義する．図2.2のリンクP1→P2を用いて，リンク元ノードであるノードP1を「起点ノード(Starting Node，以下「SN」と言う)」，リンク先ノードであるノードP₂を「通過ノー

11つの設置箇所につきビーコン発信機は車線毎に設置されるため，「設置箇所」の数と「設置台数」は同一ではない．

(20)

GPS測位と通過時刻の記録を行う交差点

SN PN DN

I^f

S P D

D

D P

S

P^a

(a) 道路地図 (b) 道路グラフ

I^b

I^a I^c

I^e

I^g

I^j

I^k I^d

P^b

P^c P^e

P^f

P^g

P^j I^h

Iⁱ

図 3.1: ノードの種類

ド(Passing Node，以下「P N」と言う)」，リンク先となるノードを通過したその次に通過

するノードであるノードP₃，ノードP₄，ノードP₅)を「方向ノード(Direction Node，以下

「DN」と言う)」と定義する．

ここまでは右左折および直進を進路方向として表記したが，提案手法における進路方向とは，「リンク先のノードを通過後，一番最初に通過するノード」と定義する．すなわち，進路方向とはDN のことである．

図3.1は，ノードの種類の例である．図3.1(a)は実際の道路地図で，Ia，· · ·，Ikは交差点名を表し，黒丸が付してある交差点I_a，Ib，Ic，Ie，If，Ig，Ij，IkはGPS測位と通過時刻の記録を行う交差点，すなわちノードと定義される交差点ある．図3.1(b)はノードとリンクの定義を元に決定される道路グラフで，Pa，Pb，Pc，Pe，Pf，Pg，Pjは交差点I_a，Ib，Ic， I_e，If，Ig，Ijに対応するノードIDである．Ibに対応するノード，すなわちP_bからは，Ia， I_c，Ie，If，Ig，Ijに対応するノード，すなわちP_a，Pc，Pe，Pf，Pg，Pjの計6個のノードに対してリンクが作成される．従って，SNがノードP_aかつP N がノードP_bとなるリンク P_a→P_bに対しては，P_c，Pd，Pe，Pf，PgがDNとなり，計5種類の進路方向が定義される．

3.5 進路方向によって異なる混雑度を考慮するリンクの決定

進路方向によって異なる混雑度を考慮するリンクが多くなると，データベースのデータサイズは大きくなる．従って，単純に全てのリンクで進路方向を区別することは，より高精度な旅行時間の算出が期待でき実装も容易であるが，必ずしもデータサイズを考慮した時の

「費用対効果」が優れるとは限らない．従って，進路方向ごとに生じる混雑度の差の大きさ

(21)

に応じて，進路方向を考慮するか否かを決定することが望ましい．

そこで，進路方向による混雑度の差に着目し，これを以下「分散度」として定義する．その上で，分散度が小さいリンクではリンク旅行時間を進路方向ごとに区別しないことで，算出精度とデータサイズのトレードオフの向上を目指す．

3.6 旅行時間算出

以上の理論により作成したリンク旅行時間を元に，入力経路に対する出発地から目的地までの旅行時間を算出する．入力経路は通過するノードを通過順に並べたものとし，この入力経路をリンクごとに分解した後，各リンクのリンク旅行時間をデータベースより検索し，それらの和を旅行時間として出力する．

(22)

3.7 本章のまとめ

本章では，進路方向を考慮した旅行時間算出のための基本概念を提案した．

第2節では，提案手法を既存手法の持つインフラを利用した手法として位置付けた．さらに，対象とするノード数がVICSと比較してはるかに多いと予想できるという理由から，既存手法の中でもテレマティクスをベースとすることとした．

第3節では，同一のリンクでも進路方向によって区別して扱うことを，提案手法におけるリンク旅行時間の特徴として提案した．

第4節では，本手法を提案する上での議論の簡潔化の目的から，同一のリンクに対して3 種類のノードを定義した．すなわち，あるリンクに対して，リンク元となるノードSN，リンク先となるノードP N，および進路方向を表すノードDN の3種類のノードを定義した．

また，本論文においては，「右左折」や「直進」といった単語ではなく，DNを「進路方向」

とすることとした．

第5節では，単純に全てのリンクで進路方向を区別することは必ずしもデータサイズを考慮した時の「費用対効果」が優れるとは限らないと考えたことから，進路方向ごとに生じる混雑度の差が大きいリンクのみで進路方向を考慮することとした．ここで「分散度」を「進路方向ごとに生じる混雑度の差」の大きさと定義し，この分散度が大きいリンクのみで進路方向を考慮する．

第6節では，こららの概念を元にして作成したリンク旅行時間を用いて，出発地から目的地までの旅行時間を算出する概念を提案した．

(23)

第 4 _章

進路方向を考慮した旅行時間算出のための

データベース作成手順と旅行時間算出手法

(24)

第4章進路方向を考慮した旅行時間算出のためのデータベース作成手順と旅行時間算出手法

4.1 本章の概要

本章では，前章で提案した概念を実現するためのデータベース作成手順を提案する．

まず第2節では，データベース作成フローのStepD1からStepD5までを簡単に説明する．

その上で，4.3から4.7では各ステップごとに処理の詳細を提案する．

第3節はStepD1で，対象とする道路地図を元に，ノードとリンクの定義に従って道路グラ

フを決定した後，各ノードに対して以下の情報をリスト化する．第4節はStepD2で，StepD1 で作成されたノード情報を元に，データベースのデータ構造を決定する．第5節はStepD3 で，データ構造が決定した領域に対してリンク旅行時間を格納することで，データベースを作成する．第6節はStepD4で，StepD3において格納場所が存在しない場合に，リンクを追加するために「ノード情報」を編集する．第7節はStepD5で，混雑度の差が小さいリンクを判定し，そのリンクではリンク旅行時間を進路方向によって区別しないよう，データ構造を再決定する．このための判定方法を提案する．

最後に第8節では，これらのステップを完了後に作成されるリンク旅行時間のデータベースを用いて，出発地から目的地までの旅行時間を算出する手法を提案する．

(25)

4.2 データベース作成フロー

図4.1は，提案手法において旅行時間を算出するために用いるデータベースの作成フローである．

StepD1 実際の道路地図からノードとリンクの配置に関する情報を抽出し，それらの関係

をリスト化した「ノード情報」を作成する．

StepD2 「ノード情報」を元に「リンク旅行時間格納領域」のデータ構造を決定する．

StepD3 車両から取得した情報を元に算出したリンク旅行時間を「リンク旅行時間格納領

域」へ格納することで，データベースを作成する．

StepD4 リンク旅行時間の格納の際に，必要があればリンクを追加するために「ノード情

報」を編集する．

StepD5 一旦作成されたデータベースを元にCDF(後述)を決定する．このステップは，混

雑度の差が小さいリンクではリンク旅行時間を進路方向によって区別しないよう，データ構造を再決定するためのものである．

CDF(Course Direction Flag)とは，「対象とするリンクで進路方向を考慮するか否か」を決定する項目として定義したものである．CDF は，各リンクごとに与えられ，進路方向を考慮するリンクでは1，進路方向を考慮しないリンクでは0のいずれかの値を持つ．

道路地図

ノード情報 StepStep StepStepD1D1D1D1

リンク旅行時間格納領域 Step

Step Step StepD2D2D2D2

ノード・リンク情報抽出

データ構造決定

データベデータベデータベデータベースースースース

Step Step Step

StepD3D3D3D3 リンク旅行時間格納

StepStepStepStepD5D5D5D5CDF決定 StepStepStepStepD4D4D4D4リンク追加

図 4.1: データベース作成フロー

(26)

4.3 ノード・リンク情報抽出 (StepD1)

ノード情報とは，各ノードに対して，そのノードからリンクされている(以下，「隣接する」

と言う)ノードに関する情報をリスト化したものである．

ノード・リンク情報抽出の手順を図4.2に示す．対象とする道路地図(図4.2(a))を元に，

ノードとリンクの定義に従って道路グラフ(図4.2(b))を決定した後，各ノードに対して以下の情報をリスト化した，「ノード情報(図4.2(c))」を作成する．

• 隣接するノードのノードID．

• リンクのCDF．

図4.2(b)では，2つのノード間の双方向のリンク¹を「↔」で表している．さらに，リンク上

の数字はそのリンクのCDF²を，それ以外の数字はノードIDを表す．図4.2(c)中のCDF は1と0の両方が混在しているが，このステップでは全てのリンクでCDF = 1としてノード情報を作成する．

4.4 データ構造決定 (StepD2)

StepD1で作成されたノード情報を元に，データベースのデータ構造を決定する．各リンクご

とに用意するリンク旅行時間の格納領域をオブジェクトとして扱い，これを以下「LTTtable」

と呼ぶ．

図4.3は作成するデータ構造の例であり，図4.3中の太線は連結リストを，直線矢印は連結リストの各要素から次の連結リストへのリンクを，曲線矢印はLTTtableへのリンクを表す．データ構造の決定手順は以下の通りである．

( i ) 要素数が全ノード数と同一の配列を作成する．この配列がP Nに対応し，n番目の要

素は，ノードIDがn+ 1であるP N のリンク先を保持する．

( ii ) 各P Nからのリンク先に連結リストを作成する．この連結リストの各要素がSNに対

応し，それぞれノードIDとDNへのリンク先を保持する．

この次の手順は，SNとP Nによって決定されるリンクのCDF の値によって異なる．CDF の値は，前のステップ，すなわちStepD1，StepD4，StepD5のいずれかを終了時点のノード情報を参照することで得る．

1双方向のリンクとは，ノードαとノードβに関して，リンクα→βおよびリンクβ→αの両方が存在することであり，一方通行の道路では双方向ではなく片方向のリンクとなる．

2ここでのCDF は，表示の簡素化のため双方向で同じ値としているが，実際には双方向の場合は個別に決定され，必ずしも同一とは限らない．

(27)

(a) 道路地図

(b) 道路グラフ

・・・

N o d e N o .

CDF

N o d e N o .

CDF

N o d N o .

CDF

_{・・・}

：：：：：：：

_{・・・}

5 0 4 6 0 4 9 1 5 6 1

_{・・・}

5 1 3 0 1 4 6 0 7 9 1

_{・・・}

5 2 2 8 1 5 8 1 5 5 1

_{・・・}

5 3 5 5 1 6 1 0 6 2 0

_{・・・}

：：：：：：：

_{・・・}

N o d e N o .

リンク 3 リンク 2

リンク 1

(c) ノード情報

79 51 46 50 49

56 33 40

59 1 0 1

1 0

0 1 1

1 0

0 1

0

図 4.2: ノード・リンク情報抽出

CDF = 1の場合

(iii) 各SNからのリンク先に連結リストを作成する．この連結リストの各要素がDN に対

応し，それぞれノードIDとLTTtableへのリンク先を保持する．

(iv) 各DNからのリンク先にLTTtableを作成する．

この時のデータ構造は図4.3(a)のようになる．

CDF = 0の場合

(iii) 各SN からのリンク先にLTTtableを作成する．

この時のデータ構造は図4.3(b)のようになる．

(28)

LTTtableの構造

図4.3(c)はLTTtableの構造である．LTTtableは，要素数を「1日のうちに存在する時間帯数」とした一次元配列構造とする．リンク旅行時間をさらに曜日，イベント発生の有無，

天気等の複数の次元で扱う手法[15],[16]があるが，これらはLTTtable内の構造に関する問題である．本論文が問題としているのはLTTtableの配置方法であるため，ここでは簡単のためリンク旅行時間を時間軸のみで扱う．1つの時間帯の長さは一律でT_d，時間帯数は1日の長さである24×60=1440[min]をT_dで割った値とする．

各時間帯をt_n(n = 1,2,· · ·1440/T_d)と表記し，このnを「時間帯番号」と呼ぶ．さらに，

ノードpiがSN，ノードpj がP N，ノードpkがDN であるリンク旅行時間のうち，P N の通過時刻がn番目の時間帯に属するものをLT T_p_i_,p_j_,p_k(t_n)と表記し，LT Tpi,pj,pk(t_n)が格納されるLTTtableをLT T table_p_i_,p_j_,p_kと表記する．

図4.3(c)は，リンク30→51に対して，ノード46がDN であるリンク旅行時間のための LT T table_30,51,46であり，100番目の時間帯のリンク旅行時間LT T_30,51,46(t₁₀₀)が150[sec]であることを示している．

4.5 _{リンク旅行時間格納} (StepD3)

データ構造が決定した領域に対してリンク旅行時間を格納することで，データベースを作成する．各車両は，ノードを通過する度に以下の情報を1組にして，後にテレマティクスのセンタへアップリンクする．

(a) 通過したノードID(P_aとする)．

(b) 前回通過したノードID(Pbとする)．

(c) 前々回通過したノードID(Pcとする)．

(d) (b)の通過時刻が含まれる時間帯(tpとする)．

(e) (c)を通過後に(b)を通過するまでに要した時間．

もしリンクP_c→P_bがCDF = 1であった場合には，LT T table_P_c_,P_b_,P_aに(e)が振り分けられる．CDF = 0であった場合には，LT T tablePc,Pbに(e)が振り分けられる．(d)は，LLTtable 内で時間帯によって分類するための項目であり，振り分けられた先のLTTtable内で，tpが同一である全ての(e)の平均値が，リンク旅行時間LT TPc,P_b,Pa(tp)となる．

(29)

61 62 51 52

46 79 88

30 46 79

LTT table

SN PN

DN

…

LTT table

28 44

…

53 ^…

(b) CCD=0のリンク (a) CCD=1のリンク　(リンク30→51)

(リンク28→61)

150 152 155 156 156

… …

(c) LTTtableの構造

LTT

^30,51,46

( t

¹⁰⁰

)

リンク旅行時間[sec ] 時間帯

No.

100 101 102 103 104

図 4.3: データ構造

4.6 リンク追加 (StepD4)

このステップは，リンク旅行時間の格納の際に，StepD3における(a)，(b)，(c)の全てが一致する格納場所が存在しない場合に処理する．この現象は，ある車両が2つのノード間を，

リンクと定義されていない経路を走行して到達した時³に発生する．

この時には，StepD1のノード情報作成時に新たなリンクを追加し，再びStepD3を処理することで対応する．すなわち，既知でないリンクが発生した時でも単純な処理で対応でき，

この点が，本論文で右左折や直進などの単語ではなくノードを進路方向と定義する利点である．

3道路工事によって追加された経路や，いわゆる「裏道」と呼ばれるような経路を用いた場合が挙げられる．

(30)

4.7 CDF 決定 (StepD5)

このステップは，進路方向ごとに生じる混雑度の差が小さいノードでは進路方向を考慮しないことで，旅行時間の算出精度とデータベースのデータサイズのトレードオフの向上を目的としている．

ここで，進路方向ごとの混雑度の差の大きさを表す「分散度」を定式化する．分散度は，

各リンクごとに数値化される．リンクα→βに対して，ノードβと隣接するノードα以外のノードをn₁，n₂，· · ·，n_m(mはノードα以外の隣接するノードの数)とすると，分散度D(α, β) を以下の式で定義する．

D(α, β) = Xm

k=1

¯¯ave(α, β)−LT T_α,β,n_k¯¯

m (4.1)

ここで，ave(α, β)はリンクα→βに存在する全ての進路方向別のリンク旅行時間の平均値

であり，

ave(α, β) = Xm

k=1

LT T_α,β,n_k

m (4.2)

と定義する．さらに式(2)で，LT Tα,β,nkは，LT Tα,β,nk(t₁),· · ·,LT T_α,β,n_k(t_1440/t_d)までの平均値とする．すなわち，ここではD(α, β)は時間帯には依存しないものとする．

この分散度を用いて，各リンクのCDF を以下の手順で決定する．ここで，「CDF 率」を

「全リンク数⁴に対してCDF = 1とするノードの割合」と定義する．

( i ) 各リンクの分散度を算出する．

( ii ) 全リンクを分散度によって降順にソートする．

(iii) 上位からCDF 率に応じたの数のリンクのみCDF = 1のままとし，残りのリンクを

CDF = 0に変更する．

CDF 率は，旅行時間の算出精度とデータサイズのトレードオフを考慮した上でサービス提供者が決定するべき値である⁵．

4リンク数は，双方向の場合は個別にカウントする．

5CDF 率の最適値については，後述の実験で検証する．

(31)

StepC1i←1，n←0，T T ←0．

StepC2j←i+ 1．

リンクpi→pjがCDF = 1であればStepC3へ，

CDF = 0であればStepC4へ．

StepC3k←i+ 2．

データベースよりLT Tp_i,p_j,p_k(tα+n)を参照．

T T ←T T+LT Tp_i,p_j,p_k(tα+n)としてStepC5へ．

StepC4データベースよりLT Tp_i,p_j(tα+n)を参照．

T T ←T T+LT Tp_i,p_j(tα+n)としてStepC5へ．

StepC5n←[T T /T_d]．

i≤N−2であればi←i+ 1としてStepC2へ．

i=N−1であればT T ←T T+LT T_p_N−1_,p_N(t_α+n) とし，T Tを出力して終了．

図 4.4: 旅行時間算出手順

この処理により，StepD2で用いるノード情報が更新される．再びStepD2およびStepD3 を処理した後にデータベースが完成される．

4.8 旅行時間算出手法

上述で作成したデータベースを元に，進路方向によって混雑度が異なることを考慮した旅行時間算出手法を提案する．

入力する経路をR =p1 →p2 → · · · →pN(piはノードID，Nは入力経路中に存在するノード数，N≥3とする)，走行開始時刻が含まれる時間帯を4.5の表記に従ってt_αとし，出発地から目的地までの旅行時間T T(Travel Time)の算出手順を図4.4に示す．以下，各ステップの詳細を提案する．

StepC1 ノードIDを表すための変数i，時間帯番号を表すための変数nおよび旅行時間T T

を用意し，それぞれ初期値として0を代入する．

StepC2 変数jにi+ 1を代入する．ここで図4.2中のノード情報より，リンクp_i→p_jのCDF を参照する．このCDF が1であればStepC3へ，0であればStepC4へ．

StepC3 変数kにi+ 2を代入する．SNがp_i，P Nがp_j，DN がp_kで，かつ時間帯番号が α+nであるリンク旅行時間LT T_p_i_,p_j_,p_k(t_α+n)をデータベースより参照する．その値を旅行時間T T に加算し，StepC5へ．

StepC4 SNがp_i，P Nがp_jで，かつ時間帯番号がα+nであるリンク旅行時間LT T_p_i_,p_j(t_α+n) をデータベースより参照する．その値を旅行時間T T に加算し，StepC5へ．

(32)

StepC5 StepC3またはStepC4終了時点のT T によってインクリメントされる時間帯番号の数，すなわち[T T /T_d]をnに代入する．この処理により，リンク旅行時間を加算する度に時間帯が更新され，そのリンクを通過している時間帯のリンク旅行時間を取得できるようになる．その後，i≤N−2であればStepC2へループする．i=N−1であればT T にLT T_p_N−1_,p_N(t_α+n)を加算して終了する．ただし，この時のリンクp_N−1 →p_N のCDF が1であった場合には，DN となるノードが経路中に存在しないため，例外として全ての進路方向の平均値をLT T_p_N−1_,p_N(t_α+n)とする．

なお，文献[15],[16]で提案されているように，曜日，イベント発生の有無，天気等をLTT-

tableの構造に取り入れたとしても，本アルゴリズムを簡単に拡張し対応できると思われる．

(33)

4.9 本章のまとめ

本章では，前章で提案した概念を実現するためのデータベース作成手順を提案した．

第2節では，データベース作成フローのStepD1からStepD5までを簡単に説明した．ここで，「対象とするリンクで進路方向を考慮するか否か」を決定する項目を「CDF」と呼ぶフラグで定義した．以降，4.3から4.7では各ステップごとに処理の詳細を提案した．

第3節章はStepD1で，このステップでは対象とする道路地図を元に，ノードとリンクの

定義に従って道路グラフを決定した後，各ノードに対して以下の情報をリスト化する．これにより作成される情報を「ノード情報」と呼ぶ．

第4節はStepD2で，このステップではStepD1で作成されたノード情報を元に，データ

ベースのデータ構造を決定する．リンク旅行時間を格納する場所をオブジェクト化し，これ

をLTTtableと呼ぶ．旅行時間算出の際には時間帯の他にも曜日や天候，イベントの有無な

どの要素を考慮する必要があると思われるが，これらは全てLTTtableの内部構造に関する問題である．本論文で問題としているのはLTTtableの配置であり，内部構造は問題としていないため，ここでのLTTtableの構造は時間軸のみの一次元配列とした．

第5節はStepD3で，このステップではデータ構造が決定した領域に対してリンク旅行時

間を格納することで，データベースを作成する．各車両から送信された情報を元に，ノードが一致するLTTtableへその車両のリンク旅行時間が振り分けられ，最終的には同一時間帯内のリンク旅行時間の平均値が，算出に用いられるリンク旅行時間となる．

第6節はStepD4で，このステップではStepD3において格納場所が存在しない場合に，リ

ンクを追加するために「ノード情報」を編集する．これは，新たに作成された道路や裏道と呼ばれる道路を走行した時に発生するが，この時にはStepD1のノード情報作成時に新たなリンクを追加し，再びStepD3を処理することで対応できる．すなわち，既知でないリンクが発生した時でも単純な処理で対応でき，この点が，本論文で右左折や直進などの単語ではなくノードを進路方向と定義する利点である．

第7節はStepD5で，このステップでは混雑度の差が小さいリンクを判定し，そのリンク

ではリンク旅行時間を進路方向によって区別しないよう，データ構造を再決定する．このための判定方法として，「分散度」の算出方法を提案した．一度作成されたデータベースを元に各リンクごとに分散度を算出し，この値が小さいリンクではCDF = 0として，再びStepD3 を処理することで最終的にデータベースが完成となる．

最後に第8節では，これらのステップを完了後に作成されるリンク旅行時間のデータベースを用いて，出発地から目的地までの旅行時間を算出する手法を提案した．本手法では，曜日，イベント発生の有無，天気等をLTTtableの構造に取り入れたとしても，本アルゴリズムを簡単に拡張し対応できると思われる．

(34)

第 5 _章

評価実験

(35)

第5章評価実験

5.1 本章の概要

本章では，交通流シミュレータ「NETSIM[12],[13],[14]」を用いて提案手法を評価する．評価項目は，旅行時間の算出精度および，算出精度とデータサイズのトレードオフの2項目である．第2節では，旅行時間の算出精度について評価方法を説明した後，シミュレーション結果と，その結果から分かることを述べる．第3節では，算出精度とデータサイズのトレードオフについて評価方法を説明した後，シミュレーション結果と，その結果から分かることを述べる．さらに，このトレードオフを考慮した時の最適なCDF 率の導出方法について考察する．

(36)

第5章評価実験

5.2 旅行時間の算出精度

図 5.1: シミュレーションに用いた道路モデル

図5.1は今回のシミュレーションに用いた道路モデルである．都市部で，方向別車線があり，かつある程度混雑している地域という条件から，横浜駅周辺の東西約7km×南北約5km の範囲を対象とした．ノード数は160個，リンク数は483本である．

旅行時間の算出精度に関して，既存のテレマティクスと提案手法のそれぞれの誤差を比較する．本論文では，誤差を「シミュレータ上で測定した旅行時間からの差」と定義し，データサイズを「データベース中に存在するLTTtableの数」と定義する．

5.2.1 _評価方法

評価の手順は以下の通りである．

( i ) 図5.1の道路モデルに対して，図4.1中のStepD1およびStepD2を処理する．この時の StepD2は，全てのノードでCDF = 1，すなわちCDF 率 = 1.0として処理する．

進路方向ごとに異なる混雑度を考慮した 旅行時間算出手法

2007 年度 修士論文