−∴・・￣−：‥・こl十、二十
天冒 健二…‖‖‖‖＝‖＝‖＝‖‖州＝＝川州l…‖‖‖川＝＝1川‖‖‖＝‖‖‖＝＝‖‖州‖＝＝‖川削‖削‖‖州＝＝州＝…11‖‖＝川…＝‖‖＝＝＝＝‖‖＝＝‖＝＝＝‖‖‖‖＝＝＝‖＝＝‖‖＝＝‖＝＝‖‖＝‖‖‖＝‖‖＝＝‖‖‖＝＝‖‖‖＝＝＝＝‖‖‖‖‖＝＝‖‖＝‖‖＝＝州＝、すると考えれば理解しやすい。

．、・∴、

道路網を表すグラフの特徴としては，各点の次数が電子地図を利用したマップマッチング型のナビゲー

定数オ山ダーの比較的粗な構造であることが挙げられションシステムが，初めて実用化されて10年以∬二がる亜 また，lノンクの踵離あるいは旅行時間をリンクコ経ち，この間，GPSとの併用により位置検出精度がストと呼ぶが，それに交差点での右折や左折にペナル飛躍的に向上し，種々の機能が充実してきたの これにティ的なコストを付加することも多い。ナビゲーショ

より予 車両の現在位置から目的地までの経路を探索しフンシステムで用いられる最ご短絡問題のアルゴリズムに交差点ごとに音声で困的地への方向を案内する経路誘は9 表二Lに示すような種々のバリエーションがある凸最短路問題のアルゴリズムで最も有名なものはダイ

導システムが【誼般化したひ

経路探索は当初，リンク（道路単位）の距離をベMクストラ法（Dijkstra method）である白 木手法は，スとした静的（固定）な探索であったが91996年に9出発地から探索を開始して，各探索では走査されたリ通信によりリアルタイムで交通情報を提供するⅤICS

ンクの申で摘発地からのコストが最小のリンクを選ん（VehicleImformatiomamdCommunicatiomSystem： で9 そのリンクに接続するリンクを走査し，出発地か遠路交通情報通信システム）が実用化されて以来，リらのコストを求めていくものである静 ダイクストラ法

ンクの旅行時間（リンクを通過するのに必要な時間）

では，各リンクはユ度しか探索されることはない。アをベースとした垂加勺経路探索へと変化してきており，ルゴリズムは以下の通りである。

道路の渋滞緩和の山勘となっている。

ダイクストラ法

以下て、は，経路探索の基本的アルゴリズムをいくっ① 0以外の点（Ⅴについて0からの仮の距離か紹介すると共に，経路誘導の形態や効果評価についdist（Ⅴ）＝＝∞，d五st（（））＝0，すべてのⅤについてて報告する￠

仮の親p（Ⅴ）＝mull，走査対象点の集合U＝（0）とする。

、：丁−ニー‥圭紅・一三ー．・、∴・・、い．
2。且 経路探索の種類

表1経路探索アルゴリズム

ナビグー・ションシステムにおける経路探索は，組み合わせ最適化における最短路問題の直接的な応用のiつである。最短路閑題とは，点の集合Ⅴと向きと良さを持った枝の集合Eで構成される有向グラフにお種 類

ダイクストラ法
バケット法

いて，2点0，dが与えられたとき9 0からdまでの巌短絡，すなわち，枝の長さの和が最小の経路を求める問題である。点Ⅴは交差一捌こ，枝（Ⅴ，W）は隣接する

2交差点Ⅴ，Wを結ぶリンクに，枝の良さiem離hは枝（ⅤブW）に対応するリンクの距離あるいは旅行時間にヲ。㌃．笠0，dはそれぞれ車輌の出発地および目的地に相当特徴探索した仮ラベルの中から最小値を選び，ラベルを確定する

ラベル確定法を選定し易くする
仮ラベルを親子の階層構造で管理し，ヒ｝プ法】

両方向探索法】
A☆法

ラベル修正法

最小値を選定し易くする
出発地と目的地の両方向から探索する
目的地までの最短値を考慮し，その下限値を用いる探索した仮ラベルに対してラベルを確定する方法をとらない

ポテンシャル法 仮ラベルをFIFO等の方法で取り出す

バケット法 仮ラベルをバケットで管理し，最小値
てんもく けんじ
住友電気．t業㈱Å法〒554−0024大阪市此花区島屋ト1−3
馴帽（12）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.に近いものを取り出す
目的地までの最短値を考慮するが，下限値を用いない
オペレーションズ。リサーチ

表2 探索回数削減アルゴリズム② Uからdist（Ⅴ）が最小である点Ⅴを1つ選んで取り出す．もしⅤ＝dならば終了．

特種 類③ dist（Ⅴ）十1ength（Ⅴ，W）＜dist（w）となる枝（Ⅴ，w）に対し，dist（w）＝dist（Ⅴ）十1ength（v，W），
p（w）＝Ⅴとし，WをUに格納する．②へ戻る．
ラベル修正法は出発地から探索を開始し，各探索では幅優先探索等の位相的順序に従ってリンクを選び，そのリンクに接続するリンクを走査し，出発地からの徴階層化法 出発地，目的地から離れている道路を階層的に縮退して計算に用いる

長方形法 出発地，目的地を含む適当な長方形内の道路のみを計算の対象とする
楕円法 出発］軋 目的地を焦点とする楕円内の道路のみを計算の対象とする
遠方縮退法 出発地から離れている道路を縮退する
分割攻略法 出発地から目的地までの経路を複数回に分割して計算するコストを求めていく手法である．ラベル修正法では各探索においてリンクを選ぶ際にダイクストラ法のよう的地周辺以外では国道や高速道路等の幹線道路を利用にコスト最小のものを選ぶ手間は不要であるが，各リすることが多いと考えられるため，グラフを全道路綱ンクは2度以上探索される可能性がある．ラベル修正を表現した層，幹線道路だけを表現した層のように複法は道路網のように各点の次数が定数オーダーである数の階層に分割して持ち，出発地，目的地の周辺は詳ような粗なグラフでは1回の探索当たりの処理時間と細な層，中間部分は幹線道路のみの層を用いることに探索回数のバランスが良く有効であると考えられる．

よって中間部分のグラフのリンク数を削減する手法

これらの方法は，基本的に出発地から他の全リンク（階層化法）や，探索を出発地，目的地を含む長方形へのコスト最小の経路を求めるものであるため，目的や楕円形の領域に限定する手法（長方形法，楕円法），地とは異なる方向のリンクにも同じように探索を広げ出発地から遠方にある道路のみを縮退させる手法（遠ていく．

方縮退法）等が，一般的に用いられている．

そこで探索するリンクをなるべく出発地と目的地の2．2 経路探索の具体例

間に限定し，探索回数を減らすため，出発地，目的地

次に，ナビゲーションシステムにおける経路探索のの両方からダイクストラ法による探索を行う両方向探

具体例について，通常の経路探索とは異なった例を2索法も用いられる．

つ紹介する．

また，ダイクストラ法に，目的地に近いリンクほど2．2．1合理的な複数経路の探索小さくなるヒューリスティックなコストを付け加えた利用者の多様なニーズを満たすため，ナビゲーショアプローチであるA＊法も用いられる．A＊法では各ンシステムに対し複数の推奨経路の提供を望む意見も点Ⅴからdまでの最短路の長さの下限値h（Ⅴ）を用い多い．現在のシステムでは，所要時間最小化，走行距ており，h（Ⅴ）の例としてⅤからdまでのユークリッ

離最小化，右折回数最小化等，異なるコストを用いてド距離がある．アルゴリズムは以下の通りである．

経路探索を行うことによって評価観点の異なる複数のA＊法

経路を求めている．ここで紹介する方式はこのような（彰 0以外の点Ⅴについて0からの仮の距離手法ではなく，同一のコスト，同一の評価観点から異dist（v）＝∞，dist（0）＝0，すべてのⅤについてなる複数の経路を求める手法である．k番目に最短の仮の親p（Ⅴ）＝null，走査対象点の集合U＝（0）

経路を求めるk一最短路問題のアルゴリズムを道路網とする。のグラフに通用した場合，最短経路から1ブロック分② Uからdist（v）十h（Ⅴ）が最小である点Ⅴを1つ選んで取り出す．もしⅤ＝dならば終了．
③ dist（Ⅴ）＋1ength（Ⅴ，W）＜dist（w）となる枝（Ⅴ，w）に対し，dist（w）＝dist（Ⅴ）＋1ength（Ⅴ，W），

迂回した経路等，最短経路とほとんど変わらない経路が求まってしまう．そこで，新たにナビゲーションシ
ステムにおける複数経路にふさわしい，「代替経路」の探索について紹介する．

p（w）＝Ⅴとし，WをUに格納する．②へ戻る．

ナビゲーションシステムにおいて，ユーザーの選択

また，出発地から目的地までの経路は人間にとってのために最適経路とともに提供する代替経路に必要な直感的に理解しやすいため，ナビゲーションシステム

条件として，の経路探索では探索回数を減らすために，表2で示す（i）最適経路とのコストの差が小さい

ような多くのヒューリスティックな工夫がなされてい（ii）最適経路とはなるべく異なるリンクを通るる．例えば，一般に車両で走行する際には出発地，目が挙げられる．そこで，出発地から目的地までの代替

2000年7月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（13）313経路を以下のように定義してみるp

利用者が最適経路と比較，選択する対象として妥当と［定義1］最適経路と重複するリンクのコストの和が思われる代替経路が求まった。表3は定数△を変化最適経路のコストの1／2未満の経路の中で，コストがさせた場令の探索によって得られた代替経路と最適経最小の経路を代替経路と定義する。

路の亜複部分の最適経路に対するコストの割合（単この定義に従って代替経路を求めた場合，途中で最位：％）を示したものである。また，図1は△＝100

適経路との分岐，合流を何度も繰り返すような経路がおよびユ20の場合の代替経路を示しているむ 図＝こお、求まることがある。このような経路は利踊者が最適経いて経路を示す太線の軋 太い方は最適経路を，細い路と比較，選択する対象とするのにふさわしいとは言方は代椿経路を示す恥い難いものである。そこで，代替経路の定義を最適経2。2，2 遠方縮退経路探索

路との重複だけでなく，分岐，合流の回数も考慮して出発地と目的地との距離が長い場合，目的地の位置以下のように変更してみる巾

が多少変わったとしても，出発地付近の経路はほとん［定義2］代替経絡を，最適経路とのコストの差が・fブ

ど影響を受けない〃 例えば，現在地が東京駅前の場合えられた定数△以下かつ，最適経路との分岐ッ 企灘は9 那勺地が大阪であろうと名古屋であろうと，少なが1垣1のみの経路の中で，最適経路と亜複するリンク

くとも高速道路までの経路は同じである。このことをのコストの和が最小の経路と意義する血 但し9 そのよ

利用して，指摘地をエリア別にグループ化して予 交差

うな経路が複数存在する場合は，その中でコスト最小

蔦ごとに終グル佃プへの進行方向を設定することによのものとする伊り，記憶容巌を削減することができる咄 出発地から離このようにして定義した代替経路は恥pste皇nのk一
叢短絡アルゴリズムを拡張することによって効率的にれるにつれてタ グルービングを粗くすれば，さらに効果的である叩求めることが可能である。実験の結果，多くの場合でこの考え方は，1973〜1978年に自動車結合管制システムでガイドテーブルとして実験され，ある程度，泰3 △と最適経路との重複部分の割合の関係△20一耶

60蛋∃ljIl

重複部分 島耶 5応。4 5応．4 5毎．4 陀 宥虫

最適性に関して有効であると実証されている。しかし，
l二0

この井式では，動的な交通情報を考慮した経路を提供することができない，常に1つの経路しか提供することができな畑 等の欠点があった〃 そこで筆者らは，以下のような2点を改良したアルゴリズムを開発した中
まず最初は，巨摘勺地から出発地への距離と方角によってグルー州ビングしタ 図2のように，テーブルを目的地から才圭一ち発地方向に検索し，さらに経路計算と併用する点である也 これにより，出発地付近の動的な交通情報を考慮して経路を求めることが可能となった。出発地から遠方では，リアルタイム情事鋸まあまり重要でないので，テーブル検索で得られる経路でもあまり問題（1）△＝100はない付 さらに，車輌の移動に伴い，車両付近の経路を将計算することにより，常に動的な交通情報を考慮（2）△＝120

図1得られた代替経路の例
劉憫（14）

図2 テーブル検索と経路計算の併用© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズd⊃リサーチ大差ないエリアには両方設定

北からの方が早いエリア

西からの方早いエリア

二二 三 軍 」→
図3 複数経路のイメージ

図5 複数経路の例

た経路の例を図4および図5に示す．図4は，出発地を奈良県五傾市役所前に，目的地を和歌山市役所前と徳島市役所前に設定した例である．わかりやすいように両方の経路を一度に図示している．出発地からそれぞれの目的地への方角はほぼ同じであるが，徳島への経路は淡路島を経由する必要がある．本アルゴリズム
では，目的地から出発地への方角だけではなく，距離も考慮した上でグルーピングし，テーブルを作成しているので，このような場合でも妥当な経路を得ることができる．

図4 距離と方角によってグルーピングされたテーブルによって求められた経路

図5は，出発地が大阪駅前，目的地が山梨児の大月市役所前の例である．この場合，中央自動車道を通る経路と，名神・東名高速道路を通る経路にほとんど差がないため，大月ジャンクションにおける経路テーブした経路を得ることができる．

次に改良した点は，図3のように，出発地と目的地

ルには，長野方面と静岡方面の2つの接続情報が設定との間に複数の妥当な経路が存在する場合には，それされている．その結果，2通りの経路を提供することらを全てテーブルに設定することである．これは，以ができる．

下のような手順で行われる．
（彰 まず出発地グループの各リンクと目的地リンク

3．経路誘導システムの具体例
3．1中央決定型経路誘導と自立型経路誘導との間で代表的な経路を求める．

② 代表的な経路が1つしかなければ，それを唯一の経路としてテーブルに登録しておく．
③ 代表的な経路が複数ある場合は，それぞれの一DRGS（Dynamic Route Guidance System：動的経路誘導システム）には，中央決定型動的経路誘導システム（C−DRGS：Centrally determined Dynamic

致度を調べる．一致度が低い，すなわち大きくRouteGuidanceSystem）と，自立型動的経路誘導シ異なる経路がある場合には，これらを第2候補，ステム（L−DRGS：Locally determined Dynamic

第3候補として順次テーブルに登録していく．

RouteGuidanceSystem）の2通りがある。それぞれ一致度が高い，すなわち，重複部分が多い経路の概念図を図6と図7に示す．

しかない場合には，経路として不適当なので，前者では，誘導車両はビーコンを通過した際に，目的地，前回通過ビーコンID，実績リンク旅行時間等登録はしない．

これにより，ドライバーの好みの経路を案内したり，の情報をビーコンに送信し，逆にビーコンから目的地天候や突発事象等による通行止めによる迂回に対応しまでの経路や目的地までの所要時間を受信する．交通たりすることができる．

管制センターは，一定のタイミングごとに各ビーコン実際にテーブル検索と経路計算との併用で求められ2000年7月号から収集される実績リンク旅行時間を用いて，全ての© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（15）315

OD，旅行時間収集

最適経路探索経絡テーブル送信：‥‥‥‥‥／

図6 C−ⅢRGSの概念図

図8 シミュレーション対象ネットワーク

へU

0︵Un︶

八u∩︶

︵UQ lO 20 30 40 50 60 7￠ 80 90 用の5コンに送信する也 なお通信手段として，ビーコンの替︹U﹇0むS﹈阪蟹濫濃密計の最適経路を求め，整理された検索テーブルを各ビー

5
ク叫・1−
1Om（OrigimandⅢestimation：出発地中日的地）ペア

0O

図7：虹個別菜の概念図

誘導率［％］

図9 誘導車両に最適経路のみを走行させた場合

わりに携帯電話等を用いることも考えられるのまた後者では，ⅤICSに代表されるように，路上の卜■のシミュレー「ションで用いた出発地を黒い太線で，車両感知器等から収集された旅行時間や渋滞長，渋滞H的地を灰色の太線で示す。それぞれ6リンクずつあ度が，ビーコンや『M多重放送等の通信手段を通しり，東京の西南方面から都心に向かって克行する。て誘導車両に送信される叫 誘導車両は，それらの情報シミュレ、−ションでほ，交通管制センターと車両との双方向通信に用いるビーコンは全リンクの始点に設を用いて9 走行すべき経路を探索する。
3。2 経路誘導の効果評価置されているものとし，車線数は全リンクについて1

ここでは，C】ⅢRGSが導入された場合の効果を，車線のみとした。

交通流シミュレーションで評価した結果を示す。Lシミュレーション結果を図9に示す。横軸は誘導車

DRGSの場合でも，各車両の最適経路を求める際の両の割合（単位：％）を，縦軸は平均旅行時間（単使用データや評価基準が共通であれば，同様の結果が位：sec）を表す。この図9を見ると，誘導率が40％得られる。なお非誘導車両は，あらかじめ設定された程度の場合に全車両の平均旅行時間が最小になってお静的なリンク施行時閤を用いて求められた目的地までり，さらに誘導率が高くなると誘導車両の平均旅行時の最短時間経路に沿って走行する。

間が非誘導車両の平均旅行時間を上回る，いわゆるハシミュレーションの対象となる道路ネットワークはンチング現象が起こっている。この原因として，この車載ナビゲーションシステムで用いられている経路探シミュレ、州ションでは交通流配分を行っていないため，索用遠路ネットワ洲クであり，日本全国をカバーして最適経路に誘導車両が集中することや，旅行時間の予いる。 今回用いたのはその中でも非常に道路密度が高測を行っていないことが挙げられる。

い東京近郊約10kmXlOkmのエリアで，1，172本のリンクを含み9リンク総延長は約516kmに及ぶ。
遠路ネットワーク全図を図8に示す。この中で，以詔瑠晦（16）また9 筆者らの評価では，情事馴又集や通信によって生じる遅れ時間がDRGSの効果に大きく影響を与えており，情報伝達の遅れは少ない方がよいという結果© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ0リサーチ

中防止，および時間差出勤や経路変更等のTDMO0O5ント）による渋滞緩和等，環境面の配慮により，より00

生活に密着した具体的課題を，経路探索や誘導のロジ

1ックに組み込んで，来るべき21世紀のより良い道路
1・﹇0むS﹈匝盟虹栗℡計ウん0︵UO（Trafhc Demand Management：交通需要マネジメ

交通を目指してゆく必要がある．
参考文献
0 10 20 30 40 50 60 70 80 90 100
誘導率［％］

図10 誘導車両を2経路に配分した場合

Barbier，M．et al．（1994）， Multirouting Strategiesin
GuidanceSystems，TelematicsforTransport，thelSt

World Congress on Applications and ′rransportになっている．

さらに，誘導車両が少ないときに最適経路の更新周期が短すぎると，1周期内に十分な数の旅行時間データが集まらず，経路探索結果の信頼性が落ちることも判明しており，最適経路の更新周期は5分程度が妥当であることがわかっている．

Telematics andIntelligent Vehicle−Highway Sys−
tems．

Dial，R．，Glover，F．，Karney，D．，andKlingman，D．
AcomputationalanalysISOf alternative algorithms

andlabeling techniques for finding shortest pathtrees ，Networks，9，pp．215−248．

以上は，各ODに対して，垂加勺な交通情報を用いた最適経路探索の結果に従って誘導した場合について述

べたが，交通流の配分を行うと，誘導率が高くても動Dijkstra，E．W．（1959）， A note on two problemsin
COnneXionwithgraphs，NumerischeMathematik，1，pp．269−271．

的経路誘導の効果が維持されると言われている．ここ

土居陽一・吉井正明・厚朴靖広・天日健二・清水修・井上では，各ODに対してあらかじめ設定された2通りず

琢弥・長尾真伸・内田正樹（1990）「自動車の位置検出つの経路を与え，各経路の旅行時間に関して車両台数方式の開発」『住友電気』137，pp．105−112．

が反比例するように，誘導車両を配分した場合についEppstein，D．（1999）， Finding the k shortest paths ，
SIAMJournalonComputing，28，pp．653¶674．て，シミュレーションを行った．

シミュレーション結果を図10に示す．この図10を見ると，誘導率が高くなっても図9に比べて平均旅行時間が増加せず，例えば誘導率が80％の場合には，全車両の平均旅行時間が約20％減少していることがHart，P．，Nillson，N．and Rafael，B．（1968）， A formal
basisfortheheuristicdeterminationofminimumcost
path，IEEE Transactions on Systems Science andCybernetics，SSC−4，pp．100LlO7．
泉隆・中原正道・高橋寛（1990）「パソコンを用いた交通わかる．したがって，誘導率が高くなった場合に情報案内システム」，『電気学会，道路交通研究会』RTA−DRGSの効果を維持しようとすると，このような簡90−20．

単な配分手法を採用しても非常に有効であるといえる．

algorithmforKshortestsimplepaths

4．おわりにナビゲーシ

Ane侃cient，Networks，12，pp．411−427．

ョンにおけるいくつかの経路探索アルゴ

リズムと，これを用いた経路誘導システムの具体例，および経路誘導の効果評価の例を紹介した．現在，経路探索は，リアルタイムや統計値の旅行時間をベースとしたものが主流であり，道路の有効利用と渋滞緩和に役立っている．しかしながら，交通分野での問題には，渋滞緩和の課題だけでなく，交通事故あるいは交通安全の課題や，空中のCO2削減という意味で，環境整備の課題もある．

小林祥延・平野和夫・出川裕久・橋本武夫℡名倉充彦（1992）「推奨経路表示機能付ナビゲーションシステム」，『住友電気』141，pp．155−160．
於本俊哲・三上徹・油本暢勇・田部力（1979）「自動車総合管制システム」，『電子通信学会別冊』62（8）．
森津秀夫・大原竜也・多田典史・井上琢弥（1991）「経路誘導による交通ネットワークフローの変化に関する分析」，『土木計画学研究・論文集』9．
柴田潤・天日健二・下浦弘（1993）「ストカスティック経路探索アルゴリズムの開発」，『住友電気』143，pp．164−

今後は，事故多発地点の走行回避，あるいは交差点での安全な右折を目指す安全性の考慮や，大型車の集2000年7月号

Katoh，NリIbaraki，I．andMine，H．（1982），

173．

Shibuya，S・，Imai，H．，Nishimura，S．，Shimoura，H© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（17）317

Tenmoku，K．（1999），

Findingusefuldetoursingeo−

graphicaldatabases ，E82¶D，282290．

ミュレーションを用いた動的経路誘導の評価」，『住友電気』1略pp，4247。

F浦弘㍉六雄㌢健二。柴田潤①三藤邦彦（1996）「交通流シ

詔闇斎（18）

オペレドンョンズ。リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.