第 20 回交通工学研究発表会講演論文集(2000 年 10 月)

１９

車両走行軌跡の取得を目的とした光学式ビーコンの効率的な配置を求める手法と車載機高度化による効果
東京大学生産技術研究所 正会員
東京大学生産技術研究所 正会員
千葉工業大学 正会員

○堀口良太
桑原雅夫
赤羽弘和

１．はじめにVICS で利用されている光学式ビーコン(以下ビーコン)

2には情報提供メディアとしてだけでなく，情報収集メディ

終点
16↑ ↓73

アとしての役割も持っている．現仕様では，車載機からビmrs k : k 番目経路に含まれるリンク数ビーコンの位置と時刻などが含まれるが，これらを収集し図 1 では，次の 4 つの経路 R1 〜R2 が定義される(起終点ペアの添え字は省略)．
R1 = {1, 2, 4, 8},

ここでは，アップリンク情報から車両の走行軌跡を特定できるビーコンの効率的な配置を求める手法を提案する．
走行軌跡は，集計することでリンク旅行速度や OD 交通

特定にはビーコンをネットワーク上に密に配置しなければR3 = {1, 2, 7, 5, 8},同時に，これらの経路をリンク番号をインデックスとする2値ベクトル Qrs k として表記する．

ならないことが容易に想像される．整備費用の制約からも，より少ないビーコンで，より多くの走行軌跡を捕捉できるよQrs k = { qrs kj | qrs kj =δj, j = 1, 2, …, N}(2)

δj = 1 (aj ∈ R k), orrs

= 0 (aj ∉ Rrs k).

うな効率的な配置を求める手法へのニーズは大きい．

aj : リンクj

以下では効率的な配置を求める手法を組み合わせ最N : リンク数

適化問題として定式化し，実際のネットワークを用いたケ

よって経路 R1 〜R2 も次のようにベクトル表記される．

ーススタディを行う．また現在検討されている車載機の高Q1 = (1, 1, 0, 1, 0, 0, 0, 1),

度化，すなわちビーコンを通過する直前数リンクの走行

Q2 = (1, 0, 1, 0, 1, 0, 0, 1),

履歴をアップリンクに含めることにより，より少ないビーコン

Q3 = (1, 1, 0, 0, 1, 0, 1, 1),で同様の情報が取得できると期待されるが，その効果にQ4 = (1, 0, 1, 1, 0, 1, 0, 1).

ついてもケーススタディで評価する．

経路がループを形成しなければ，Rrs k とQrs k は 1 対 1 で対応する．よってqrs kj が 1 のときに，リンク番号を意味する

２．組み合わせ最適化問題としての定式化
ここでは図 1 に示す 1OD の簡単なネットワークを例として用いながら，走行軌跡を特定するビーコン配置を求め

添え字 j から，Rrs k の対応する要素 ars ki の添え字 i への 1対 1 写像 f rs k が定義される．
∀ qrs kj∈ Qrs k ∩ qrs kj =1,る手法を説明する．

∃ frs k : j→i | ars ki ∈ Rrs k ∩ ars ki = j.

(1) 現行のアップリンク情報の場合
まず，起終点ペア rs を結ぶ k 番目の経路 Rrs k を，次のようにリンク番号の順序付き集合として表記する．
Rrs k = {ars ki | i = 1, 2, …, mrs k}.

R2 = {1, 3, 5, 8},
R4 = {1, 3, 6, 4, 8}.

量などが求められるだけでなく，経路選択モデルの導出に利用できるなど，利用価値の高い情報であるが，その5

図１：1OD4 経路の単純なネットワーク

最初に通過したビーコンの位置と時刻，直前に通過した効率的な道路利用を可能にすることが期待されている．

8

数字はリンク番号ーコンへ渡される(アップリンク)情報には，トリップ開始後て得た情報を交通計画・運用にフィードバックすることで，4

起点

(3)

さらに，あるビーコンの配置パターン Bp についても，次のように 2 値ベクトルで表記する．
Bp = {bpl | bpl =δl , l = 1, 2, …, N}

(1)

(4)

ars ki : ｋ番目経路の i 番目リンク番号

δl = 1 (リンクl にビーコン設置), or- 73 -第 20 回交通工学研究発表会講演論文集(2000 年 10 月)= 0 (リンクl にビーコン未設置).

はすべての走行軌跡が同定できるが，現実には S22 のス

ここで Qrs k とBp に関する次の二項演算子#を定義する． キーマを持つ軌跡のアップリンク情報は収集されないこと# : (Qrs k, Bp ) →Srs kpに留意されたい．

(5)

Srs kp = {srs kpl | srs kpl=ϕl , l = 1, 2, …, N}

さて，以上のようなスキーマの概念を取り入れたとき，ビϕl= 1 (q kl=1 ∩ bpl =1),ーコンの最適配置を求める問題は，次の評価関数 E を最= 0 (qrs kl=0 ∩ bpl =1), or大化するような組み合わせ最適化問題となる．

rs

Find Bp such as E(Hp , Cp )→maximum,= * (bpl =0).
すなわち「srs kpl =1」は車両軌跡がリンクl を通過している

where

Hp = -Σrs Σkxrs kplog(xrs kp)ことを意味し，「srs kpl =0」は車両軌跡がリンクl を通過してxrs kp = ||Srs kp|| / Krs

いないことを意味している．「*」は未定義を意味するシン

Cp = ||Bp || / Nrs(6)ボルである．ここでは慣例的に S kp をビーコン配置 Bp でHp : スキーマのエントロピー

分類される経路 Qrs k のスキーマと呼ぶ．

Cp : ビーコン設置リンク率

このとき，ある車両の走行軌跡τを経路と同様にベクトル

Krs : 起終点ペア rs 間の経路総数で表記すると，そこに含まれる唯一のスキーマが存在する||Srs kp|| : スキーマ Srs kp に属する経路数(ただしすべて未定義値のスキーマをのぞく）．したがって，||Bp || : ビーコン設置リンク数

このスキーマに分類される経路がただ一つの場合，そのスキーマのエントロピーはその定義より，一つのスキーマ経路を走行する車両軌跡を同定でき，複数の経路がある に属する経路数が少ないほど大きくなる．具体的な E の場合，そのうちのいずれかを走行した車両経路を分離で 記述は問題ごとに与える．
きることになる．

当然ながら，この問題は NP 完全であり，多数の局所解もう一度例に戻り，リンク4 と5 にビーコンを配置した場合 を持つので，遺伝的アルゴリズムや模擬徐冷法，TABUを考える．ビーコン配置パターンB1 は，探索などの効率的に準最適解を求める手法を利用するこ

B1 = (0, 0, 0, 1, 1, 0, 0, 0)とになる．また，この手法でははじめに経路を列挙していと表記され，経路 R1 〜R2 はそれぞれるが，これについては既存の研究成果を利用することに

Q1 #B1 = S11 = (*, *, *, 1, 0, *, *, *),なる．本稿のケーススタディでは Dial の配分アルゴリズム

Q2 #B1 = S21 = (*, *, *, 0, 1, *, *, *),[1]

Q3 #B1 = S31 = (*, *, *, 0, 1, *, *, *) = S21 ,経路を列挙している．

における efficient path の概念を採用し，ループのない

Q4 #B1 = S41 = (*, *, *, 1, 0, *, *, *) = S11 .の 2 種類のスキーマに分類される．ネットワーク形状から， (2) 車載機の高度化が実現された場合車両の走行軌跡は必ずこの 2 つのスキーマのどちらか一

現在，ビーコンが設置されていないリンクの交通状況を方を持っているのだが，い ずれのスキーマにも複数の経 把握するために，車載機側でリンク走行履歴を保存して路が属しており，経路を同定できないとわかる．

おき，アップリンク情報にその履歴を付加して通信する，

また，リンク2 と4 に配置した場合，パターンB 2 は，いわゆる車載機の高度化が検討されている．履歴が保存

B2 = (0, 1, 0, 1, 0, 0, 0, 0)

されるリンクの数が多いほど，同じ質の情報を収集するのと表記され，経路 R1 〜R2 はそれぞれに必要なビーコンは少なくなることは，直感で理解できる

Q1 #B2 = S12 = (*, 1, *, 1, *, *, *, *),が，前節と同様の方式で，最適なビーコン配置を求める

Q2 #B2 = S22 = (*, 0, *, 0, *, *, *, *),問題を次のように定式化できる．

Q3 #B2 = S32 = (*, 1, *, 0, *, *, *, *),経路やビーコンの配置についての表記は前節の通りと

Q4 #B2 = S42 = (*, 0, *, 1, *, *, *, *).

する．ビーコンと通信する直前 n リンクの履歴を車載機側のように，各経路独自のスキーマに分類される．この場合 で保存しているとき，Qrs k と Bp に関する二項演算子#を次- 74 -

第 20 回交通工学研究発表会講演論文集(2000 年 10 月)
nのように# と拡張して定義する．
# n : (Qrs k, Bp ) →Srs kp
rsrs

今，目的関数 E 1 を(7)ゾーンセントロイドrsS kp = {s kpl | s kpl=ϕl , l = 1, 2, …, N}
ϕl= 1 (∪(qrs ky=1 ∩ bpy =1

信号交差点|(x=i-n,…, i), f rs k(l) = i, f rs k(y) = x)),ゾーン境界

= 0 (qrs kl=0 ∩ bpl =1), or= * (otherwise).

対象リンク

ネットワーク端点
セントロイドすなわち，経路上のあるリンクl の走行履歴が，n 本先までのリンクのいずれかに設置されたビーコンでアップリンク

図 2：浜松中心市街地のネットワーク情報として収集された場合は，対応するスキーマの要素
E 1 = Hp + δ(1 - Cp )を 1 とし，リンクl にビーコンが設置されていてもアップリン(8)δ = 1 (すべての経路が同定された), or

ク情報が収集されなかった場合は 0 とする．スキーマの要= 0 (それ以外)

素がこのいずれにも当てはまらない場合は，未定義を意と設定し，リンクの走行履歴を保存しない場合(E 1 , n=0)，味する「*」のままとする．
以上のような演算子の拡張定義を導入することで，前節と同様のスキーマのエントロピーを目的関数の説明変数

およびビーコン通過直前の3 リンクまで履歴を保存する場
合(E 1 , n=3)と5 リンクまで保存する場合(E 1 , n=5)の 3 ケースについて，最適組み合わせを探索した．とした組み合わせ最適化問題に定式化ができる．
車載機が高度化された場合の手順を，再び例題のネッ

さらに別の目的関数 E 2

トワークで説明する．いま車載機は直前 1 リンクの履歴をE 2 = Hp * (1 - Cp )保持しているとし，車載機が高度化されていない場合は経路を同定できなかった，リンク4 と5 にビーコンを配置し(9)についても，5 リンクまで履歴を保存する場合(E 2 , n=5)の最適配置を探索した．
各ケースの探索結果を表 1 に示す．

たパターンB1 ，すなわち，B1 = (0, 0, 0, 1, 1, 0, 0, 0)

ケース
E1, n=0E1, n=3E1, n=5E2, n=5を考えると，この場合は経路 R1 〜R2 はそれぞれ
Q1 #1 B1 = S11 = (*, 1, *, 1, 0, *, *, *),Q2 #1 B1 = S21 = (*, *, 1, 0, 1, *, *, *),Q3 #1 B1 = S31 = (*, *, *, 0, 1, *, 1, *),Q4 #1 B1 = S41 = (*, *, *, 1, 0, 1, *, *).

表 1：最適組み合わせ探索の結果同定された経路数
ビーコン設置リンク数
729 (100%)50 (64%)729 (100%)
37 (47%)729 (100%)
33 (42%)501 (69%)
18 (23%)図 3 に各ケースにおけるビーコン設置リンクの配置を示の 4 種類の独立のスキーマに分類されることがわかる．

す．評価関数が E 1 の場合，すべての経路が同定されており，かつビーコンの数が少ないほど高い評価値となるの

３．実ネットワークを用いたケーススタディ

で，得られたビーコン配置で全経路が同定されている．まケーススタディとして，図 2 に示す浜松中心市街地ネット た評価関数が E 2 の場合，車載機の高度化により18 個のワークにおけるビーコン最適配置を考える．ネットワークはビーコンで 69%の経路を同定しているが，目的地となるセ

東西南北それぞれが約 1.5km の長さにわたり，13 の端点 ントロイドにもっとも近いリンクに設置される傾向が見て取
セントロイドと 3 つのゾーンセントロイドを含む．起終点ペ れる．なお，探索戦略はランダム探索と山登り法を組み合
ア数は 240 となる．またリンクは細街路を省いた道路で構 わせた手法を初期値を変えて十数回繰り返すという簡便成され，その数は往復別に 78 本である．このネットワーク なもので，結果は準最適解であることに留意されたい．に Dial の配分アルゴリズムを適用すると，efficient path を729 本列挙できる．
- 75 -

第 20 回交通工学研究発表会講演論文集(2000 年 10 月)#Beacon = 50

#Beacon = 37

Counts of Links on Paths (Total 729 paths, E=6.82)

120
Beacon100%

Beacon10080%

8060%

6040%

4020%

20
E 1 , n =00

E 1, n=3#Beacon = 33

#Beacon = 18, # Identified Path = 501
Beacon0%123456789 10 11 12 13 14 15 16

図 4：経路上のリンク数頻度分布(曲線は累積)

Beaconと予想され，このような空間的な指標と n の一般的な関係についても考察をすすめていく必要がある．
今回は最適配置を求めるに当たり，単純な評価関数を定義してケーススタディを行った．より現実的な評価のE 1 , n =5

ためには，たとえば計画経路交通量で重み付けした評E 2, n=5

図 3：ビーコン設置リンクの最適配置

価関数や，ビーコン数の上限を制約条件とした最適化，あるいは既存ビーコンにくわえて新規にビーコンを設置する場合の最適化など，さまざまな手法を検討するとと

４．考察と今後の課題

直感的には n 本直前のリンク走行履歴をアップリンクに もに，最適化の手法についても，より効率的な手法を探含めれば，全経路を同定するために必要なビーコン数は る必要がある．
n=0 の時と比べて 1/n 程度になるように思われるが，ケーススタディからはそれほどの効果は確認されない．これは【参考文献】

ネットワークの範囲内にセントロイドが比較的均一に分布 [1] Dial, R.B.: A probabilistic multipath traffic assignment
していると，あるセントロイドへの直近アクセスリンクに配置

algorithm which obviates path enumulation, Transportation

されたビーコンが，別のはなれば場所にあるセントロイド

Research 5, pp.83-111, 1971へ向かう経路を同定する場合に，必ずしもその役目を兼ねないため，車載機の高度化によって期待するほどの効果が得られなかったものと考えられる．
また，ネットワーク形状とセントロイドの分布パターンによって，列挙される経路を構成しているリンク数の分布が変わってくる．仮に全セントロイドへの直近アクセスリ
ンクにビーコンが設置された場合，n 本直前のリンク走行履歴をアップリンクに含めると，そこを目的地とする経路のうちリンク数が n 本以下のものは，当然ながらすべて同定可能となる．図 4 は今回のケーススタディで列挙された経路のリンク数頻度分布であるが，n=10 程度までは同定できる経路数も順調に増加するが，それ以上は余り増加しない．したがってネットワーク形状とセントロイド分布によって，ある効率的な履歴保存数 n が決まるように思われる．逆に言えば n の大小により，経路が同定可能なセントロイド分布の空間的詳細度が変わってくる- 76 -