ハードウェア・シミュレータを用いた最適径路計算システム

(1)

特集l 自動車径路誘導システム

ハードウェア・シミュレータを用いた

最適径路計算システム

古村文伸

1 .

はじめに径路誘導システムでは各車を誘導する径路として，刻々変化する道路網内の混雑状況，通行規制状況に従って目的地までの最適径路すなわち最短時間径路をリアルタイムに計算することが必要となる.この最短径路問題は従来ラベリング法等のアルゴリズムを用いた計算機プログラムで解かれていたが，ネットワークのノード数すなわち道路網の地点数が多くなると処理時聞が急速に大きくなるという難点があった. そこでこれを解決するためわれわれは道路網を模擬したディジタル回路網を作り，その中を伝播する電気信号で車の走行を模擬することによって，最短径路を高速に探索するハードウエア・シミュレータを開発した. 本文ではこのハードウエア・シミュレータの原理と構成について述べる.さらに通産省工業技術院の大型プロジェクト「自動車総合管制技術の研究開発J {自総管)で実施した径路誘導パイロット実験への適用結果を示す.

2 .

最短径路問題とその従来解法

2 .

1

最短径路問題最短径路問題は道路交通制御のほか，輸送計画，日程計画等こむらふみのぷ側目立製作所 19唱O 年 4 月号 3 C(1,2) 2 の数理計画問題にしばしば現われる重要な問題である [1 ].この問題はつぎのように定式化できる. 図 l に示すような N 個のノード {i}

(i=

1

, …,

N) とノードを結ぶ有向アークから成るネットワークを考える.アーク (i， j) には距離あるいは時間等に相当する正のアークコスト c{i， j) が与えられているとする.このとき問題は与えられた出発ノード s と目的ノード e に対し，径路に沿ってのアークコストの和明 -1

J

=

L

:

c{k!

,

ki+1) が最小となるノード列 {kd

(i=

1, 2 ，… ， m) を求めることである.ただしん =s， km=e とする.このとき解として得られたノード列が最短径路を，また J が径路のコストを与える.

2 .

2

ソフトウェアによる解法最短径路問題は従来 LP ， DP ，ラベリング法等のアルゴリズムを用いて，計算機ソフトウエアにより解く方法が多数開発されている.このうち N

0 :

i: ノートーーー :アーク C(i, j) : e アークコスト一ー一 S， e 聞の最短径路図 1 ネットワークと最短径路 (31)

2

3

5

(2)

最も一般的なものはラベリング法で，中でも基本 10' 形はつぎの古典的ラベリング法 [2J である. すべてのノード i にラベル (di， Ti) を与える. また i に入るアークの始ノードの集合を Pi とする.このときつぎのステップにより 5 から他の全ノードへ到る最短径路が求まる. ステップ各ノード i のラベルの初期値を

iM

件 S のとき

(s

,

0 )

i=s のときとする. ステップ 2 すべてのノード i について

min

{Tj十 c (j，

i

)

}

JePi なる j を求め，ラベルを(j，

T

j

+

c

(j, i)) でおきかえる. ステップ 3 すべてのノードについて第 2 ラベルの値が変化しなくなるまでステップ 2 を繰り返す. こうして得た各ノード i の第 l ラベルムは最短径路上で z の直前にあるノードを，また第 2 ラベル Ti は s から i までの最短径路のコストを与える. このアルゴリズムの計算量を見積ってみる.各ノードに入るアークの数を平均λf とすれば，ステッブ 2 で各ノード当り加算と比較の演算はそれぞれ M 回行なわれる.ノード数 N のとき l 回のステップ 2 でNxM 回となる.またステップ 2 全体の反復回数は高々，出発ノート》冶らの最短径路上に含まれるノード数の最大値に等しい.ネットワーク内のノード分布が一様であればこの最大値は NO_•5 _{のオーダーとなる.} _{したがって} _{l 出発} ノート‘から他の全ノードへの最短径路を探索するに要する計算量は NxMxNO_・_5=MxN1_・5 _に比例する. 最短径路計算は対象ネットワーク形状，プログラム作成方法により同←A_{アルゴリズムでも処理時} 聞が変化する.ここでは l つの白安として上記アルゴリズムを FORTRAN プログラム化し，自総管パイロット実験の対象である東京の道路網 10 74SE 営紙おな(-引 L I 10-' \隊司円

片/イ

/

10-2 ハ U S 唱_i n u l 10事 103 10

‘

ノード数図 2 最短径路計算時間の比較

(N=

1465) およびその一部を用いて，汎用計算機 HITAC一M160II でラ γ した結果を図 2 に示す. 一方径路誘導システムで許容される処理時聞を考えてみる.上記パイロァト実験システムでは，

272

の出発ノートーから全目的ノードへの最短径路を，通行規制の異なる 8 つのケース (4 車種×高速道路利用可・杏の 2 ケース)について日分以内に求める必要がある.すなわち l 出発ノードから 1 回当りの許容処理時聞は O. 14秒であり，これは上記ラベリング法による処理時間の1/40程度に相当する.古典的ラベリング法の改良としてダイクストラ法[2 J がある.これはノード当りのアーク数 M が N に近い密なネットワークでは処理時間短縮に有効である.しかし道路網では λf は平均 3-4 で N に比べはるかに小さく，ラベルのソートに要する処理のためかえって処理時聞が増える.

3 .

ハードウェア・シミュレータ

3 .

1

ハードウェア・シミュレータの原理ノード数 N が増えるにつれラベリング法の処

(3)

理時聞が急速に長くなる原因は，上記ステップ 2 で本来独立した各ノードについての第 2 ラベルの加算と比較の演算をノードごとに逐次実行することにある.そこでわれわれは発想を転換し，対象ネットワークに相似な(ノードの接続関係が相等しい)回路網を作り，その中で電気信号で交通流を模擬することにより最短径路を高速に求めるアプローチをとった. この考え方にもとづいて新しく開発されたものが，ハードウエア・シミュレータ[3 J である. ハードウエア・シミュレータは図 3 に示すように，ネットワークのノードに対応したノードモジュールと，アークに対応した信号線から成る.ノードモジュールは，ゲートとアークごとのカウンタをもっディジタル回路でつの LSI

(Large

S

c

a

l

e

Integrated

circuit) に封入される. このハードウエア・シミュレータを用いてつぎのようにして最短径路が求められる. 各カウンタには対応するアーグのアーグコストの値が初期設定されている. 1 つの出発ノードに対応するノードモジュールのゲートからパルス信号(旅行信号とよぶ)を発する.パルス信号がカ

~

Ufl:'H'H ト

出Jljj[

つ

11

2

3

7

(4)

ウンタに伝わると，モジュールの外部から与えられるクロック信号によってカウンタの内容が l ずつ減少させられる.そしてカウンタの内容が O になった時点で旅行信号が，下流に接続されたモジュールへ信号線を通して伝えられる.信号を受けとったモジュールは，上と同様に各アークのカウンタの内容の減算を開始する.それと同時にゲートを閉め，その後他の上流側モジュールからの旅行信号を受け付けないようにする.そしてカウンタの内容が O になると旅行信号がさらに下流側のモジュールに伝えられる. こうしてすべてのモジュールに共通のクロック信号を用いて旅行信号の遅延と伝播を進めれば，各モジュールへは可能な全径路のうち最もコストの小さい径路をとった旅行信号だけが受け付けられる.こうしてすべてのモジュールに旅行信号が到着したならば動作を停止する.このとき各モジュールに記憶された先着アーク番号をたどれば，出発ノードから他の全ノードへの最短径路が得られる.またモジュールにクロック信号を計数するカウンタを別途設け，旅行信号がそのそジュールに到着した時点、の値を保持させれば，これは最短径路のコストを与える.このハードウエアシミュレータの演算過程は，旅行信号を車の l つの集団とみなせば，出発ノードからいっせいに走り始めた車群が，途中の各ノードで各アークに分岐し，可能なすべての径路を走行して各ノードへの先着を競うレースを模擬している.

3 .

2

計算の速度、ードウエア・シミュレータにより l 出発ノードから他の全ノードへの最短径路を求めるに要する時聞は，出発ノードから最も遠いノードへ旅行信号が到達するまでの時聞に等しい.ノード数が N のとき，ノードの分布，アーグコストが一様であればこれは NO・ 5 のオーダーに比例する.したがって処理時聞がほぼ N 1. 5 に比例するラベリング法によるソフトウエア解法に比べ， N が大きくなるほど有効になる.前述の東京の道路網にハードウエア・シミュレータを適用した時の処理時間の推定結果を図 2 に示す.ラベリング法に比べ 10 倍ないし 100 倍程度高速である.パイロット実験 (N=1465) の l 出発ノード当りの処理時聞は要求条件を十分満足している. ハードウエア・シミュレータによる解法をラベリング法と比較すると，ラベリ γ グ法のステップ 2 の演算のうち，第 2 ラベルの加算をハードウエア・シミュレータではカウンタによる旅行信号の遅延で，また第 2 ラベルの比較による最小値の検出をハードウエア・シミュレータではゲートを閉じる操作で実現している.しかもこれらの動作は出発ノードから波紋のように伝播する旅行信号の前線に当るノードで同時並列に行なわれる.このようにハードウエア・シミュレータ f'Ìアークコストを所要時間とみなし，電気信号を利用して物理的シミュレーションを行なうことにより，ラベリング法のステップ 2 の逐次処理による処理時間増加の難点を解決したものである.

3 .

3

専用計算機としての位置づけ道路網交通流を模擬するハードウエアとして従来，ダイオード回路を用いたアナログ・シミュレータ([

4

]など)，専用ハードウエアとディジタル計算機を組合せたシミュレータ[

5

]等がある. 前者は道路網内の最適交通流分布をネットワークフロー問題[ 1 ]として解くものである.後者は個々の車の動きを再現でき，信号制御効果の事前評価等に利用されている.これに対し本ハードウエア・シミュレータは交通流の再現を目的とするものではなく，最短径路を求めるために車の流れを模擬している.したがって道路網以外のネットワーグの最短径路問題にも適用できる. 本ハードウエア・シミュレータの特徴として， 1000 個以上のノードモジュール LSI から構成されている点がある. LSI 化された演算ユニットとして最近高速フーリエ変換や浮動小数点演算を行なうものが出現している.これらは主にマイコンと組合せ数値計算の高速化のために用いることを

(5)

図 4 専用シミュレータシステム目的としている.ハードウエア・シミュレータのように単一の専用 LSI モジュールを多数組合せて特定の問題を解く，大規模な専用計算機は従来なかった.

4 .

径路誘導システムへの適用

4 .

1

専用シミュレータシステム自総管パイロット実験の径路誘導システム用の最適径路計算装置として「専用シミュレータシステム J

[6

]を開発した.これは図 4 に示すように約 1200個のそジュール LSI を用いたハードウエア・シミュレータ，その制御装置，制御用計算機とから構成される. ハードウェア・シミュレータはパイロット実験エリア内の各地点を出発ノードとして，都内の道路網について最短時間径路を探索する.この径路計算の入力として必要な各アークの60分先までの予測アークコストすなわちアークの旅行時間の予測値，および通行規制データは制御装置からセットされる.予測アークコストは 15分ごとの未来値が用意され，ハードウエア・シミュレータで l 出発ノードから径路計算を開始後 15 分， 30分， 45 分 1980 年 4 月号モジュール LSI I!O :入出力コントローラ BM ノ〈ッファメモリハードウェア・シミュレータに相当する時間だけクロックが進んだ時点で計算をいったん停止し，各アークのカウンタの内容を該当する時点、のアークコストに書きかえたのち計算を再開続行する.こうすることにより未来の旅行時間および通行規制の変化に適応した最短径路が得られる. ハードウエア・シミュレータからは計算結果として，各目的ノードへの最短径路について出発ノードからの進路(左折，直進，右折等)が出力される.制御用計算機は，パイロット実験エリア内 86個の各交差点についてこの進路データを編集してガイドテープ、ルを作る.これが各交差点の路上機に送られ車の誘導に使われる.

4 .

2

ネ'"}トワークの縮退モデルノード数の多い広域道路網を対象としてハードウエア・シミュレ{タを作ると，ハードウエアの規模が大きくなり，入出力データの量および処理時聞が増大する.そこで元のネットワークからノード数を減らした等価ネットワークモデルを作り，このモデルを用いて最短径路計算を行なうハードウエア・シミュレータを作る必要が生ずる. このようなモデルとしてつぎの透視画法的縮退ネ (35)

2

3

9

(6)

(a) 元ネットワーク (b) 縮退ネットワーク -ノードーーアクゾーン境界一一地区境界図制御エリア -非縮退ノード。仮想ノード図 5 ネットワークの縮退ットワーグモデル[7]がある. 対象道路網を誘導制御の対象となるエリアと，その周辺の径路誘導の目的地となるエリアに分ける.自総管パイロット実験では前者はパイロット実験エリアであり，後者は残りの都内の道路網である.図 5 に示すように制御対象エリアを中心として，周辺エリアの遠くのノードについては，隣接する複数ノードを l つの仮想ノードに縮退させる.このとき中心からの距離が大きくなるにつれ，より多くのノードを同ーの仮想ノードに縮退させることにより，透視画法的に粗いネットワーグが得られる. このときどれだけのノードを 1 仮想ノードに縮退させるべきかは，元のネットワークで求めた最短径路と縮退ネットワークで求めた最短径路との誤差評価により判断できる.たとえば，ある出発ノードから周辺エリアのゾーン Z 内のノード i

(i=

1 ， 2 ，… ， N) へ到る最短径路の進路を li，また径路のコストを Ti とし，縮退ネットワークでゾーン Zへ到る最短径路の進路およびコストを 1 ， T とする.このときある闘値 fh ， θz に対し， ~

ITi-TI

ヤ一一一

<fh

N

品 T

7b(凶なる t の個数 )

<02

が成り立っときのみゾーン Z を縮退させればよい.このような計算をあらかじめオフライン的に行なうことによってネットワークモデルを作ることができる.パイロット実験に適用した結果， 1465 ノードの元ネットワークから 599 ノードの縮退ネットワークが得られた.

4 .

3

処理速度の評価パイロット実験の結果，ハードウエア・シミュレータによる最短径路計算処理時聞は，データの入出力処理を含め l 出発ノード当り l 回平均 0.046 秒であった. 272 出発ノード 8 車種の全ケースでは 100 秒となる.これとアークコストの予測，ガイドテープル編集の処理を加えた，専用シミュレータシステムの処理時聞は 8.5 分であり， 15分周期のガイドテーブル更新には充分余裕があることが確認できた. 5. おわりにネットワークの最短径路問題を高速に解くためのハードウエア・シミュレータを開発し，交通流の径路誘導システムに適用した.ハードウエア・シミュレータは専用のモジュール LSI を 1000個以上用いた専用計算機で，汎用ディジタル計算機に比べ 10ないし 100倍の処理速度をもっ. 今回開発したハードウエア・シミュレータは東京の主要道路網を模擬するもので，制御用ミニコンと同程度の大きさである.パイロット実験と同様の径路誘導システムを都内全域に適用するためにはこの規模のシミュレータを数箇所の地区管制センターに 1 つずつ設置すればよい.将来超 LSI 技術の発達により集積度の増した回路素子を使えば，シミュレータを小型化し各交差点の路上機あ

(7)

るいは各車の車載装置に組込むことも可能となろう.こうすれば最適径路計算処理を各交差点，各車に分散でき，より迅速できめ細かな道案内，交通流制御の道が聞かれよう. また最短径路計算をサフールーチンとして用いることにより解ける問題(たとえば配分問題[

8

J) , あるいは類似のネットワーク問題(たとえばネットワークフロー問題)向きの計算機へハードウエア・シミュレータを拡張することも可能である. 本文に述べた最短径路計算用ハードウエア・シミュレータのみならず今後他の分野においても，ますます発達する半導体技術を利用した専用計算機で，大規模な問題を解くアプローチが有効になると思われる. 参芳文献 [ 1 J 関根泰次:数理計画法，岩波書店， 1978. [ 2

J

S. E. Dreyfus : An Appraisal of Some Shorｭ

test-Path Algorithms

,

J

.

of Operations Resｭ

earch, 17, 395-412, 1969.

[3 J 奈良，萩原:ディジタルモジューノレによる相同相似形計算機，電気学会誌論文集， 96巻 8 号， 1976. [4

J

1 .

H. Lewer

,

J

.

M. Bullingham: Electronic

Simulator Mark II for Quickest Routes in Road Network

,

Traffic Engineering and Conｭ

trol, 15, 558-559, 1974. [5 J 谷口忠勝，高羽禎雄:交通流、ンミュレーション・システム TRN *SIMII を用いた車両走行のシミュレーション，昭和51 年電気学会全国大会 1260. [6J 古村，坪井，萩原，石崎，久保:径路誘導制御用道路網交通流専用シミュレータシステムの開発，第 16回 SICE 学術講演会 1402， 1977. [7]古村，井原:交通流制御l のための道路ネットワーグモデルの構成，昭和53年電気学会全国大会 1161. [8J オベレーションズリサーチ 1977 年 12 月号:特集 IA 法. 1980 年 4 月号 © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず. (37)

2

4

1