JP2000258184A - 交通ネットワーク経路探索方法および装置 - Google Patents

Abstract

(57)【要約】 【課題】 歩行と他の機関との組み合わせによる経路探
索ナビゲーションシステム。 【解決手段】 出発地点から目的地点までの経路を、地
点をノード、地点間をリンクとして交通ネットワークを
表現し、コンピュータを用いてラベル確定法により最短
コスト条件下で探索する交通ネットワーク経路探索方法
において、出発地点および目的地点から利用する交通機
関の駅までの経路として、出発地点および目的地点から
利用する交通機関の駅までの直線距離、および目的地点
から利用する交通機関の駅までの直線距離を緯度経度情
報を用いて求め、該直線距離を変数として平均コストを
算出し、前記平均コストが指定したコストの範囲内に含
まれるすべての利用交通機関の駅を求め、歩行経路を決
定し、求められた歩行経路を交通機関の交通ネットワー
ク経路に組み込んで総合交通ネットワークを表現し、コ
ンピュータを用いてラベル確定法により求めるコスト条
件下で探索する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、歩行と交通機関を
含む交通ネットワークにおける、出発地点から目的地点
までの経路を最小コスト条件下で探索するコンピュータ
システムに関する。

【０００２】

【従来の技術】複雑な交通ネットワークにおいては、最
適な経路を求めることは容易でない。また最適といって
も、時間、費用など多くの要素がある。コンピュータを
用いて、すべての組み合わせを計算すれば最適な経路は
求まるが、ネットワークが複雑になると高性能のコンピ
ュータをもってしても計算時間が増加し、実質的に計算
が不可能な事態となる。

【０００３】このような、実質的に計算不可能な事態に
対応すべく、様々な手法が提案されている。交通ネット
ワークに対するコンピュータを用いた最短経路探索でよ
く用いられるラベル確定法は、コンピュータの要処理時
間が少なくてすみ、迅速に回答を得られる。以下、簡単
にこのラベル確定法を説明する。ラベル確定法はこの方
法の発明者の名をとってダイクストラ法と呼ばれること
もある。

【０００４】いま図１のようなネットワークで表現され
るシステムを例に説明する。特定の地点に対応する図の
丸印を「ノード」、そのノードとノードを結ぶ線は地点
間の経路に相当し、「リンク」と呼ぶ。数学的にはこれ
らのノードとリンクの集合をグラフと呼び、リンクに向
きが有るものを有向グラフ、無いものを無向グラフと呼
んでいる。図１の例は有向グラフの例である。このよう
なシステムで、出発点のノードｓから目的点のノードｔ
への経路で、最も短くなるものを見い出す問題が最短路
問題である。

【０００５】いま、ノードｓからノードｔへの最短路Ｐ
を Ｐ＝｛ｓ，ｉ，ｊ，……、ｋ，ｔ｝ とする。このとき、Ｐをあるノードを境にしてＰ１とＰ
２に分割した場合、部分集合Ｐ１とＰ２も、それぞれの
集合内で最短路になっている。これを最適性の原理と呼
ぶ。この原理を利用して数理的に最短路を求めるアルゴ
リズムがラベル確定法である。すなわち、ラベル確定法
は空集合から始めて、ノードに仮ラベルをつけて、最短
路となるノードを一つずつ求めて最短路部分集合を膨ら
ませていき、最終的に全部のノードに対してラベルを永
久ラベルに確定させ、最短路を求める方法である。以下
は、コンピュータでプログラミングするときのアルゴリ
ズムである。

【０００６】ノードｓからノードｔに到るあらゆるノー
ドの集合をＶ、ノードｓからノードｊに至る最短路の長
さｄ（ｊ）、その最短路のノードの集合をＳ１、その補
集合をＳ２（＝Ｖ−Ｓ１）とすると、以下の方法で最短
路が求まる。 (1)初期値化として、 Ｓ１←０（空集合）、Ｓ２←Ｖ ｄ（ｓ）←０、ｄ（ｉ）←∞ とする。ここで、ｉは最短路のノードの補集合Ｓ２に含
まれるノード、Ｘ←ＹはＸをＹで置き換えることを表
す。

【０００７】(2)Ｓ１＝Ｖなら計算終了。 (3)Ｓ１≠Ｖなら、 最短路の長さｄ（ｉ）を選び出し、 ｖ←ｉ とする。長さｄ（ｖ）はノードｓからノードｖに至る最
短路となっているから、ノードｖを最短路のノードの集
合Ｓ１に含め、ノードｖを最短路のノードの補集合Ｓ２
から外す。

【０００８】(4)ノードｖから出るリンク（出リンク）
が次に到達する、最短路のノードの補集合Ｓ２に含まれ
るすべてのノードｉに対して ｄ´（ｉ）←ｄ（ｖ）＋ａｖｉ を計算し、 ｄ（ｉ）＞ｄ´（ｉ） なら ｄ（ｉ）←ｄ´（ｉ） かつ ｐ（ｉ）←ｖ とする。ここで、ａｖｉはノードｖからノードｉに至る
長さ（リンクの長さ）であり、ｄ（ｉ）、ｄ´（ｉ）は
出発点ｓからｉに至る経路の長さである。この時点のｄ
（ｉ）は、最短路のノードの集合Ｓ１内のノードからの
最短路長になっている。最短路のノードの補集合Ｓ２に
はもっと短い経路が存在する可能性はあるが、それは繰
り返し計算のなかで求められることになる。(5)ステッ
プ(2)のステップに戻る。

【０００９】以上の方法で求めたｐ（ｉ）に対して、最
終ノードｔからｐ（ｔ）をもとに逆にたどっていけば、
出発ノードｓまでの最短路が求まる。たとえば、図１の
例を上記のアルゴリズムで求めると、 d(1)=0 d(2)=50 d(3)=70 d(4)=65 d(5)=85 p(2)= 1 p(3)= 2 p(4)= 2 p(5)= 3 となる。

【００１０】ｓ＝１、ｔ＝５であるから、ノード５の前
はノード３（p(5)=3）、ノード３の前はノード２（p(3)
=2）、ノード２の前はノード１（p(2)=1）、すなわち出
発点ｓにたどりつく。すなわち、最短路は１→２→３→
５、その長さは８５（=d(5)）である。また、ノード１
からノード４に至る経路（１→２→４）の長さd(4)は、
やはり最短路長になっている。

【００１１】実際に上記のアルゴリズムで用いた図１の
経路をシミュレーションしてみるとわかるが、ノード３
からノード４に至る長さd´(4)は計算しなくてもすむ。
すなわち、ラベル確定法を用いれば、総組み合わせによ
る最短路計算に比べて、計算量がはるかに少なくてす
む。

【００１２】応用例として、ある駅を出発点にして目的
の駅までの経路を求める路線経路探索に上記のラベル確
定法を応用することができる。この場合には、最短路長
を距離だけでなく、時間、運賃など別の単位を取り。こ
のような単位をコストとよぶ概念を使うことで適用でき
る。

【００１３】

【発明が解決しようとする課題】従来技術で説明したラ
ベル確定法は、コンピュータを用いた場合に処理速度が
速いという特徴をもっている。とくに出発点と目的点が
決まっている場合には、ラベル確定法によって出発点か
ら順次最小コストとなるノードを見つけながら、目的点
に最初に到達する経路を最小コスト経路として探索でき
る。対象となるコストは具体的には時間、あるいは距離
があてられ、「移動時間」あるいは「移動距離」を評価
することになる。

【００１４】多くのナビゲーションシステムでは、コン
ピュータ上の問題解決手段として様々な方法を用いてい
るが、最小コストという条件で経路探索をする場合に
は、基本的にラベル確定法が用いられている。たとえ
ば、このような最小コスト経路探索には、鉄道機関を用
いての最小コスト経路探索や、自動車による最小コスト
経路探索システムがある。

【００１５】しかし従来のナビゲーションシステムで
は、歩行と他の機関との組み合わせによる経路探索はな
されていない。たとえば鉄道機関を利用するナビゲーシ
ョンシステムの場合、利用者が出発地点から徒歩でどの
駅に行き、到着する駅から徒歩で目的地点にどれだけ掛
かるかなどは、考慮されていない。したがって、このよ
うなナビゲーションシステムでは、出発点の最寄りの駅
と目的地点の最寄りの駅をあらかじめ指定してから、探
索が開始されている。このため、従来のナビゲーション
システムは指定した出発駅か到達駅までは正確な最小コ
スト探索が行えるが、徒歩の区間を含めた探索において
最小コストになっていることは保証されていない。

【００１６】そこで本発明が解決しようとする課題は、
歩行者が利用しようとしている交通機関の乗車地点へ徒
歩で行き、および交通機関の到達地点から目的地点まで
を徒歩で行くとした場合に、利用者が目的地点を指定す
るだけで、徒歩の区間も含めて最小コストの経路を探索
する手段を提唱することにある。

【００１７】

【課題を解決するための手段】本発明は上記の課題を解
決するために、出発地点から目的地点までの経路を、地
点をノード、地点間をリンクとして交通ネットワークを
表現し、コンピュータを用いてラベル確定法により最短
コスト条件下で探索する交通ネットワーク経路探索方法
において、(1)出発地点および目的地点から利用する交
通機関の駅までの経路として、出発地点および目的地点
から利用する交通機関の駅までの直線距離、および目的
地点から利用する交通機関の駅までの直線距離を緯度経
度情報を用いて求め、該直線距離を変数として平均コス
トを算出し、前記平均コストが指定したコストの範囲内
に含まれるすべての利用交通機関の駅を求め、歩行経路
を決定し、(2)前記求められた歩行経路を交通機関の交
通ネットワーク経路に組み込んで総合交通ネットワーク
を表現し、コンピュータを用いてラベル確定法により求
めるコスト条件下で探索する。

【００１８】また、歩行経路の決定の異なる次のような
手法も用いることができる。(1)出発地点および目的地
点から利用する交通機関の駅までの経路として、指定し
たコストの範囲内に含まれる駅までの歩行経路を、緯度
経度情報を含む地図データにより作られる道路網ネット
ワークを用いたラベル確定法により、求めるコスト条件
下で歩行経路を決定する、(2)前記求められた１以上の
歩行経路を交通機関の交通ネットワーク経路に組み込ん
で総合交通ネットワークを表現し、コンピュータを用い
てラベル確定法により求めるコスト条件下で探索する。

【００１９】請求項１〜３に記載した発明について説明
する。出発地点から利用する交通機関の乗車点（鉄道の
場合は駅）、および交通機関の下車点（鉄道の場合は
駅）から目的地点までをそれぞれ歩行し、その途中は交
通機関を利用する、出発地点から目的地点までの経路を
コンピュータを用いて最短コスト条件下で探索する。ま
ず、全体的な処理から説明する。 (1)出発地点から利用する交通機関の乗車点までの直線
距離、および目的地点から利用する交通機関の下車点ま
での直線距離を求め、その直線距離から徒歩で掛かる平
均コストを割り出し、平均コストが指定したコストの範
囲内に含まれるすべての利用交通機関の乗車点および下
車点を求め、この歩行経路を交通機関の交通ネットワー
ク経路に組み込む。これを『直線距離による歩行コスト
計算』と記すことにする。 (2)地点をノード、地点間をリンクとして交通ネットワ
ークを表現し、出発ノードと特定ノードを結ぶリンク
と、前記出発ノードから特定ノードまでの累計コストを
表すポテンシャルとから構成されるラベルを導入し、
「＊」は出発地点はどのリンクも入ってこないことを意
味し、「Φ」は、まだそのノードにどのリンクも到達し
ていないことを意味し、「∞」は扱う問題において十分
に大きい数を意味する表記としたとき、初期値として出
発ノードに対しては（＊，０）、その他のノードには
（Φ，∞）を仮ラベルとして設定する。 (3)仮ラベルのついたノードのうち最小のポテンシャル
のノードを選択し、このノードが目的地点の場合には経
路探索を終了して下記(5)の終了処理ルーチンを実行
し、目的地点でない場合には以下(4)の処理ルーチンを
続行する、 (4)前記最小のポテンシャルのノードから出るリンクの
うち仮ラベルを有する終点ノードのポテンシャルを算出
し、前記算出された終点ノードのポテンシャルが、前記
終点ノードにつけられている仮ラベルのポテンシャルよ
り小さいときは前記仮ラベルを前記算出された終点ノー
ドのポテンシャルで書き換え、前記最小のポテンシャル
のノードの仮ラベルを永久ラベルに変えて上記(3)の処
理ルーチンを実行する。 (5)目的地点から順に永久ラベルをもとに出発地点まで
の経路をたどり、歩行経路も含めた最小ポテンシャルの
経路を求める。

【００２０】まず、『直線距離による歩行コスト計算』
を説明する。 出発地点から利用する交通機関の乗車点
までの直線距離、および目的地点から利用する交通機関
の下車点までの直線距離の求め方は、次の式を用いる。 COSξ=SINφ1・SINφ2+COSφ1・COSφ2・COS(λ1-λ2) S=R・ξ ……………… （式１） ここで、Ｓは２地点をＡ、Ｂとしたときの直線距離Ａ
Ｂ、Ｒは日本付近の曲率半径（約6370km）、ξは弧ＡＢ
としたときの中心点と各２地点を結ぶ線がなす角度、
（λ1,φ1）はＡ地点の緯度と経度、（λ2,φ2）はＢ地
点の緯度と経度である。緯度経度情報は緯度経度情報を
含む地図データから取得するほかに、ＧＰＳを用いて現
在地点の緯度経度情報を得ることができる。特に、未知
の場所を歩行中などのように、出発地点が本人にとって
不明な場合もあるので、ＧＰＳなどの手段は効果があ
る。本発明では、歩行距離は起点Ａと起点Ｂの直線距離
に比例するものとして扱う。したがってコストを時間と
した場合には、直線距離ＡＢを平均歩行時速で割れば、
出発地点から最寄りの交通機関の乗車点までの所要時
間、および交通機関の到着点から目的地点までの所要時
間がそれぞれ求められる。ここで求められたコストを利
用する交通機関のネットワークにあらかじめ組み込んで
おく。

【００２１】なお、出発地点から交通機関の起点までの
所要時間、および交通機関から目的地点までの所要時間
の最大コストを予め指定おき、そのコスト内で歩行でき
る交通機関の乗車点または下車点を割り出す。割り出さ
れた点が複数の場合には、出発地点から乗車点までのリ
ンク、および下車点から目的地点までのリンクがそれぞ
れ複数存在することになる。

【００２２】以上のように、歩行区間のリンクが交通ネ
ットワークに組み込まれたあとは、歩行経路が組み込ま
れた交通ネットワークに対して、以下のような探索処理
を行う。 (1)地点をノード、地点間をリンクとして交通ネットワ
ークを表現し、出発ノードと特定ノードを結ぶリンク
と、前記出発ノードから特定ノードまでの累計コストを
表すポテンシャルとから構成されるラベルを導入し、
「＊」は出発地点はどのリンクも入ってこないことを意
味し、「Φ」は、まだそのノードにどのリンクも到達し
ていないことを意味し、「∞」は扱う問題において十分
に大きい数を意味する表記を用いて、初期値として出発
ノードに対しては（＊，０）、その他のノードには
（Φ，∞）を仮ラベルとして設定する。 (2)仮ラベルのついたノードのうち最小のポテンシャル
のノードを選択し、選択されたノードが目的地点の場合
には(4)の終了処理を終了する。それ以外は、(3)の処理
ルーチンを行う。 (3)前記最小のポテンシャルのノードから出るリンクの
うち仮ラベルを有する終点ノードのポテンシャルを算出
し、前記算出された終点ノードのポテンシャルが、前記
終点ノードにつけられている仮ラベルのポテンシャルよ
り小さいときは前記仮ラベルを前記算出された終点ノー
ドのポテンシャルで書き換え、前記最小のポテンシャル
のノードの仮ラベルを永久ラベルに変えて上記(2)の処
理ルーチンを実行する。 (4)目的地点から順に永久ラベルをもとに出発地点まで
の経路をたどり、歩行経路も含めた最小ポテンシャルの
経路を求める。

【００２３】以上のラベル確定方法を従来のラベル確定
法に対して、ここでは便宜上『ポテンシャルによるラベ
ル確定法』と呼ぶことにする。

【００２４】次に、請求項４〜６に記載された発明につ
いて説明する。出発地点から利用する交通機関の乗車点
（鉄道機関の場合は駅）、および交通機関の下車点（鉄
道機関の場合は駅）から目的地点までをそれぞれ歩行
し、その途中は交通機関を利用する、出発地点から目的
地点までの経路をコンピュータを用いて最小コスト条件
下で探索する。その方法を以下の手順で示す。 (1)出発地点から利用する交通機関の乗車点までのコス
ト計算、および目的地点から利用する交通機関の下車点
までのコスト計算を、それぞれ道路地図から求め、指定
コストの範囲内に含まれる利用交通機関のすべての点を
求め、この歩行経路を交通機関の交通ネットワーク経路
に組み込む。以下、この処理を『道路地図による歩行コ
スト計算』とよぶことにする。 (2)地点をノード、地点間をリンクとして交通ネットワ
ークを表現し、出発ノードと特定ノードを結ぶリンク
と、前記出発ノードから特定ノードまでの累計コストを
表すポテンシャルとから構成されるラベルを導入し、
「＊」は出発地点はどのリンクも入ってこないことを意
味し、「Φ」は、まだそのノードにどのリンクも到達し
ていないことを意味し、「∞」は扱う問題において十分
に大きい数を意味する表記を用いて、初期値として出発
ノードに対しては（＊，０）、その他のノードには
（Φ，∞）を仮ラベルとして設定する。 (4)仮ラベルのついたノードのうち最小のポテンシャル
のノードを選択し、選択したノードが目的地点の場合に
は経路探索を終了して下記(5)の終了処理ルーチンを実
行し、目的地点でない場合には以下(4)の処理ルーチン
を続行する、 (4)前記最小のポテンシャルのノードから出るリンクの
うち仮ラベルを有する終点ノードのポテンシャルを算出
し、前記算出された終点ノードのポテンシャルが、前記
終点ノードにつけられている仮ラベルのポテンシャルよ
り小さいときは前記仮ラベルを前記算出された終点ノー
ドのポテンシャルで書き換え、前記最小のポテンシャル
のノードの仮ラベルを永久ラベルに変えて上記(3)の処
理ルーチンを実行する。 (5)目的地点から順に永久ラベルをもとに出発地点まで
の経路をたどり、歩行経路も含めた最小ポテンシャルの
経路を求める。

【００２５】請求項１の場合には、出発地点から乗車点
までの歩行によるコスト、および下車点から目的地点ま
での歩行によるコストをそれぞれ直線距離でコスト計算
した。しかし、請求項４の場合は、道路地図から正確な
コストを割り出す。『道路地図による歩行コスト計算』
で求められたコストがあらかじめ決められた範囲内の駅
の場合、その駅と出発地点または目的地点とを結ぶ経路
をリンクとし、利用する交通機関の交通ネットワークに
組み込む。

【００２６】『道路地図による歩行コスト計算』は、請
求項１で行ったと同じ『ポテンシャルによるラベル確定
法』を用いる。ただし、ここで用いるネットワークは道
路地図である。『ポテンシャルによるラベル確定法』を
若干手直しして使うことになるが、この点は［発明の実
施の形態］で説明する。

【００２７】『道路地図による歩行コスト計算』で求め
られたリンクが組み込まれた交通ネットワークに対し
て、請求項１で行ったと同じ『ポテンシャルによるラベ
ル確定法』を用いて、最小コスト経路を探索する。

【００２８】次に請求項１〜６に共通して利用される、
本発明の『ポテンシャルによるラベル確定法』を具体的
に説明する。『ポテンシャルによるラベル確定法』で
は、ラベル確定法にノードのポテンシャルを用いる。こ
こでラベルは、各ノードについて （ｌ，ｐ（ｖ）） と定義される。ｌはノードとノードを結ぶリンク、ｖは
現在対象としているノード、ｐ（ｖ）は経路ｖのポテン
シャルである。なおポテンシャルｐ（ｖ）は起点からノ
ードｖに到るまでの経路にかかる累計コストである。

【００２９】最小コストを条件に、出発地点（出発ノー
ド）から発して到達できる目的地点（目的ノード）まで
の経路を求める手法、すなわち『ポテンシャルによるラ
ベル確定法』について説明する。 ［初期値設定処理］出発ノードｓに仮ラベル（＊，０）
を設定し、他のノードに仮ラベル（Φ，∞）を設定す
る。「＊」は出発地点はどのリンクも入ってこないこと
を意味し、「Φ」は、まだそのノードにどのリンクも到
達していないことを意味する表記である。このノードを
未探索と呼ぶ。また、「∞」は課題に対して十分に大き
な数を意味する。

【００３０】［最小ポテンシャルの探索処理］仮ラベル
を有するノードのうち最小ポテンシャルのノードを探索
し、それを最小ポテンシャルノードｖとする。ここで求
められたノードが目的ノード（目的地点）の場合、この
ノードを永久ラベルとして、［終了処理］へ行く。それ
以外は、［経路探索処理］へ行く。

【００３１】［経路探索処理］ノードｖから出るリンク
ａ（出リンクａ）に接続するノードを δ−１ａ、 出発ノードからの、すでに求められているポテンシャル
を ｐ（ｖ） とすると、ノードδ−１ａのポテンシャルは ｐ（ｖ）＋ｄ（ａ） である。すでにノードδ−１ａ対して設定されているポ
テンシャルを ｐ（δ−１ａ） としたとき、ｐ（ｖ）＋ｄ（ａ）がｐ（δ−１ａ）より
小さければ、 ｐ（ｖ）＋ｄ（ａ） を新たなポテンシャル ｐ（δ−１ａ） とし、仮ラベルを （ａ，ｐ（δ−１ａ）） とする。ｖから出るすべてのリンク（出リンク）に対し
て上記の処理をしたあと、ｖの仮ラベルを永久ラベルと
する。その後、［最小ポテンシャルの探索処理］に戻
る。

【００３２】［終了処理］上記の処理によって得られた
永久ラベルをもつノードを、要求される形式で出力す
る。

【００３３】本発明についてさらに詳細に説明する。図
２にノードとリンクとの関係を示す。ここで使用する記
号は以下の意味をもつ。 ｖ ：仮ラベルを有するノード中、最小ポテンシャ
ルをもつノード ｕ ：ノードｖに隣接するノード ａ、ｂ ：リンク δ−１ａ ：リンクａが入るノード δ＋１ａ ：リンクａが出て行くノード ｄ（ａ）：リンクａに掛かるコスト ｐ（ｖ）：ノードｖのポテンシャル、起点からの累計コ
スト（＝Σｄ（ａｉ）） ここでノードｖから見たとき、ａは出リンク、ｂは入リ
ンクと呼ぶ。逆にノードｕから見たとき、ａは入リン
ク、ｂは出リンクとなる。ｄ（ａ）は時間、距離、金額
等の、リンクａを利用する場合に掛かるコストである。
単位をどれにするかによって求める結果も異なってく
る。また図２の（３）のような場合、通常はｄ（ａ）＝
ｄ（ｂ）であるが、ｄ（ａ）≠ｄ（ｂ）の場合もある。
ポテンシャルｐ（ｖ）は、起点０からノードｖに到るま
でのコストの累計を表す。

【００３４】ノードｖとリンクａによって接続するノー
ドｕ（δ−１ａ、δ＋１ａと同じ）のラベルは、 （ａ，ｐ（ｖ）＋ｄ（ａ）） または ｕ（ａ，ｐ（ｖ）＋ｄ（ａ）） で定義する。ｐ（ｖ）＋ｄ（ａ）はｐ（ｕ）であるか
ら、 （ａ，ｐ（ｕ）） またはｕ（ａ，ｐ（ｕ））とも書ける。すなわち、ラベ
ルはノードｖとノードｕを結ぶリンクａとノードｕまで
のポテンシャルで表される。将来、変わることのあるラ
ベルを仮ラベルといい、それ以上変わらないラベルを永
久レベルという。すなわち、永久ラベルはノードｕに到
るポテンシャルの最小値をもっている。なぜなら、本発
明では起点ノードからの経路探索につねに最小のポテン
シャルをもつノードを選んで新しい経路を探索するから
である。この点を説明する。

【００３５】ノードのポテンシャルの概念の導入は、プ
ログラム記述が簡略化できるようにすることと、処理の
終了時点を判定できるようにする。本発明では探索手法
としてはラベル確定法を用いる。図３は、ノードの全集
合Ｓと、永久ラベルを有するノードの集合Ｓ´（斜線
部）を表している。まず、最小ポテンシャル経路を見い
だすために、仮ラベルを有するノード中（＝Ｓ−Ｓ´）
からもっとも小さなポテンシャルを有するラベルを探
す。それがノードｖだったとしよう。ここでは外向きの
リンクだけを対象にした場合、ノードｖと隣接するノー
ドがｕ１、ｕ２だったとする。そこでｕ１とｕ２に仮ラ
ベルが付けられる（ただしここでは、いずれも未探索の
ノードと仮定する）。 ｕ１：（ａ１，ｐ（ｖ）＋ｄ（ａ１）） ｕ２：（ａ２，ｐ（ｖ）＋ｄ（ａ２）） そこで、ノードｖの仮ラベル（ｌ，ｐ（ｖ））を永久ラ
ベルに変え、ノードｖを永久ラベルを有するノードの集
合Ｓ´に組み込む。このラベルで示されるポテンシャル
ｐ（ｖ）が最小であることが以下のように証明できる。

【００３６】次に最小ポテンシャルをもつ仮ラベルを検
索したところ、ノードｗが見つかったとしよう。ここで
はノードｗが、リンクｂ１、ｂ２、ｂ３によって隣接ノ
ードｖ、ｕ２、ｘに接続していたとしよう。それぞれの
ノードにおける仮ラベルを求めると、 ｖ ：（ｂ１，ｐ（ｗ）＋ｄ（ｂ１）） ｕ２：（ｂ２，ｐ（ｗ）＋ｄ（ｂ２）） ｘ ：（ｂ３，ｐ（ｗ）＋ｄ（ｂ３）） となる。すでに永久ラベル化したノードｖのラベル
（ｌ，ｐ（ｖ））のポテンシャルｐ（ｖ）は、 ｐ（ｖ）≦ｐ（ｗ）＋ｄ（ｂ１） の関係が成り立つ。なぜなら、ｖを探索したとき、ｐ
（ｖ）が最小のポテンシャルとして選ばれたものである
から、ｐ（ｖ）≦ｐ（ｗ）が成り立っているためであ
る。したがって、ノードｗの経路探索では、ノードｖと
ノードｗを結ぶリンクは選ぶ必要はない。このことは同
時に、ノードｖの永久ラベル（ｌ，ｐ（ｖ））はこれ以
上変わることがないことを意味している。ゆえに、ｐ
（ｖ）は最小ポテンシャルであることが証明される。

【００３７】次にｕ２に着目する。すでに設定されてい
る仮ラベル （ａ２，ｐ（ｖ）＋ｄ（ａ２）） と、新たに求められた仮ラベル （ｂ２，ｐ（ｗ）＋ｄ（ｂ２）） のポテンシャルを比較する。かりに ｐ（ｖ）＋ｄ（ａ２）≦ｐ（ｗ）＋ｄ（ｂ２） ならラベルを変えずに、 ｕ２：（ａ２，ｐ（ｖ）＋ｄ（ａ２）） のままとし、 ｐ（ｖ）＋ｄ（ａ２）＞ｐ（ｗ）＋ｄ（ｂ２） なら、ｕ２の仮ラベルを ｕ２：（ｂ２，ｐ（ｗ）＋ｄ（ｂ２）） とする。したがって、このようなラベルの付け変えによ
って、より小さなポテンシャルとなる経路が仮ラベルと
して設定されることになる。

【００３８】以上のことから、永久ラベルには最小ポテ
ンシャルが設定されており、仮ラベルはまだポテンシャ
ルを小さくするような経路が発見される可能性を表して
いる。

【００３９】プログラミング上のテクニックとして、起
点０すなわち経路探索の開始ノードとするためには、初
期値として、起点０の仮ラベルを 起点０：（＊，０） とし、他の仮ラベルを 起点０以外のノード：（Φ，∞） としておけばよいことになる。

【００４０】したがって、本発明の歩行区間を含む最初
コスト探索の終了判定は、「新たに永久ラベル化された
ノードが目的地点」であるかどうかをチェックすればよ
いことになる。以上のことをプログラム化するには、以
下のような処理ステップを踏めばよいことになる。

【００４１】ステップ１（初期値設定） 起点ノードに仮ラベル（＊，０）を設定し、他のノード
に仮ラベル（Φ，∞）を設定する。

【００４２】ステップ２（最小ポテンシャルの探索処
理） 仮ラベルを有するノード中、最小ポテンシャルのノード
を探索し、それを最小ポテンシャルノードｖとする。こ
の最小ポテンシャルと探索されてノードが目的地点の場
合には、ステップ４（終了処理）へ行く。それ以外は、
ステップ３（経路探索処理）へ行く。

【００４３】ステップ３（経路探索処理） ノードｖからリンクａで接続する隣接ノードをδａ、こ
れに掛かるコストｄ（δａ）、起点からのすでに求めら
れているポテンシャルｐ（ｖ）とすると、ノードδａの
ポテンシャルはｐ（ｖ）＋ｄ（ａ）である。すでにノー
ドδａ対して設定されているポテンシャルをｐ（δａ）
としたとき、ｐ（ｖ）＋ｄ（ａ）がｐ（δａ）より小さ
ければ、ｐ（ｖ）＋ｄ（ａ）を新たなポテンシャルｐ
（δａ）とし、仮ラベル（ａ，ｐ（δａ））とする。上
記の処理をしたあと、ｖの仮ラベルを永久ラベルとす
る。その後、ステップ２（最小ポテンシャルの探索処
理）に戻る。

【００４４】ステップ４（終了処理） ｖを永久ラベル化し、ｖから永久ラベルを逆経路をたど
って出発地点までの経路を要求される形式で出力する。

【００４５】図４は、上記の処理をフローチャートにま
とめたものである（図の処理Ｓ「歩行コスト計算」を除
いた処理が、『ポテンシャルによるラベル確定法』に相
当）。図中、ｐ（δａ）はノードδａのすでに設定され
ているポテンシャルである。ｐ（δａ）が新たに計算し
たポテンシャル ｐ（ｖ）＋ｄ（ａ） より大きいときには、ｐ（δａ）を ｐ（ｖ）＋ｄ（ａ） で置き換え、かつリンクをａで置き換えることによっ
て、ノードδａに新しい仮ラベル （ａ，ｐ（δａ）） が付けられる。なお、隣接ノードを探索する場合は、リ
ンクは出リンクのみが検索の対象となる。また図４のフ
ローチャートは“DO WHILE”型の形態にしているため
に、ｖの永久ラベルかは終了処理の「最小ポテンシャル
ｖの検索し、それをｖとする」で行っている。すなわ
ち、上記の説明でステップ２の処理になっているが、フ
ローチャートではステップ３での処理に組み込んであ
る。この点はプログラム上の問題であり、基本的な考え
方に違いはない。

【００４６】図４は請求項１、４に共通する処理として
記述してある。したがって実際の処理における「歩行コ
スト計算」は、請求項１では『直線距離による歩行コス
ト計算』を用い、請求項４では『道路地図による歩行コ
スト計算』を用いる。これらの処理の詳細は［発明の実
施の形態］で説明する。

【００４７】以上の経路探索においては、図５に示すよ
うなリンクテーブルをあらかじめ作っておけば、目的地
点の永久ラベルに設定されているリンクでノードをたど
って行けるために、目的地点の永久ラベルを有するノー
ドから起点までの経路がわかる。

【００４８】

【発明の実施の形態】本発明の応用の一例として、図６
の電車網路線図を用いて、出発地点を東京、京橋、銀座
周辺の緯度経度とし、目的地点を三越前と人形町の間に
位置する緯度経度としたときの、最小コスト路線経路探
索を取り上げる。ここで取り上げる実施例１は直線距離
により乗車駅および下車駅を探索し、実施例２では道路
地図で乗車駅および下車駅を探索する。いずれも、徒歩
１０分以内の駅を乗車および下車候補駅として探索する
ものとする。なお、実際の探索ソフトでは利用者は出発
地点および目的地点が具体的な地名で指定することにな
る。その緯度経度は、あらかじめデータとして用意され
ている地図情報から導かれる。なお以下では便宜上、電
車の待ち時間は０分、乗換（図の破線部分）は一律徒歩
３分とする。またここで求める最小コストは時間を単位
とする。すなわち、時間を最小にする経路探索を行う。
当然、以下で扱うポテンシャルの単位も時間である。

【００４９】（実施例１）まず、『直線距離による歩行
コスト計算』から説明する。地図情報から得られる位置
情報が正規座標系（直角座標系）の座標値として得られ
るときには、徒歩１０分に平均時速を掛け、探索範囲内
を求める。平均歩行時速を４ｋｍとしたときには、出発
地点あるいは目的地点から半径約７００ｍの以内の駅を
洗い出し、これを利用候補駅とする。また、地図情報か
ら緯度経度で位置情報が得られる場合には、［課題を解
決するための手段］で示した（式１）を用いて、出発地
点または目的地点と候補駅を結ぶ距離Ｓを求める。すな
わち、出発地点または目的地点の緯度経度を（φ1，λ
1）、候補駅の緯度経度を（φ2，λ2）とすると、この
直線距離Ｓは、 COSξ=SINφ1・SINφ2+COSφ1・COSφ2・COS(λ1-λ2) S=R・ξ と計算される。したがって、S≦700を満たす駅が、出発
地点あるいは目的地点とを結ぶリンクとして路線図に組
み込まれる。このとき、リンクのコストは直線距離Ｓを
平均時速で割った値である。図６の例では、出発地点と
京橋駅を結ぶリンクのコストが４分、出発地点と東京駅
を結ぶリンクのコストが３分と求められたとしてある。
また、目的地点と人形町駅を結ぶリンクのコストが２
分、目的地点と三越前駅を結ぶリンクのコストが３分と
求められたとしてある。これを、図５に示すリンクテー
ブルに組み込み、以下の経路探索を行う。

【００５０】（初期設定）まず初期値設定として、出発
地点の仮ラベルを（＊，０）、その他の駅の仮ラベルを
（Φ，∞）とする。ここで、「＊」は出発地点はどのリ
ンクも入ってこないことを意味し、「Φ」は、まだその
ノードにどのリンクも到達していないことを意味する表
記である。初期状態では、出発地点のノードをｖと置
く。

【００５１】（１回目のループ処理）仮ラベル中で最小
ポテンシャルの駅を探す。ｖから出る終点ノードは東京
駅と京橋駅である。終点ノードはすべて未探索であるた
めに、終点ノードのポテンシャルはｖのポテンシャル０
＋ｖから各終点ノードまでの時間合計となる。したがっ
て、仮ラベルは 丸の内線東京駅 ：（出発地点，３分） 銀座線京橋駅 ：（出発地点，４分） となり、永久ラベルは 出発地点 ：（＊，０） となる。次に仮ラベル中で最小ポテンシャルのノードを
探す。この時点では、丸の内線東京駅が最小ポテンシャ
ル３分であるから、このノードをｖとする。

【００５２】（２回目のループ処理）このｖは目的地点
でないから、処理は続行する。丸の内線東京駅ｖから出
ているリンクは、丸の内線→大手町駅、丸の内線→銀座
駅である。ともにポテンシャルは３＋２すなわち５分で
ある。新たに探索したリンクには仮ラベルが貼られ、丸
の内線東京駅は永久ラベルが貼られる。したがって、こ
の時点では仮ラベルは、 丸の内線大手町駅：（丸の内線東京駅→丸の内線，５
分） 丸の内線銀座駅 ：（丸の内線東京駅→丸の内線，５
分） 銀座線京橋駅 ：（出発地点，４分） であり、永久ラベルは 出発地点 ：（＊，０） 丸の内線東京駅 ：（出発地点，３分） となる。次に仮ラベル中で最小のポテンシャルを検索す
ると、銀座線京橋駅（出発地点、４分）であるから、銀
座線京橋駅ノードをｖとする。

【００５３】（３回目のループ処理）ｖは目的地点でな
いから処理は続行する。銀座線京橋駅ｖから出るリンク
は、銀座線→銀座駅、銀座線→日本橋駅である。ポテン
シャルは前者が４＋１すなわち５分、後者が４＋２すな
わち６分である。新たに探索したリンクには仮ラベルが
貼られ、銀座線京橋駅は永久ラベルが貼られる。したが
って、この時点では仮ラベルは、 丸の内線大手町駅：（丸の内線東京駅→丸の内線，５
分） 丸の内線銀座駅 ：（丸の内線東京駅→丸の内線，５
分） 銀座線銀座駅 ：（銀座線京橋駅→銀座線，５分） 銀座線日本橋駅 ：（銀座線京橋駅→銀座線，６分） であり、永久ラベルは 出発地点 ：（＊，０分） 丸の内線東京駅 ：（出発地点，３分） 銀座線京橋駅 ：（出発地点，４分） となる。次に仮ラベル中で最小のポテンシャルを検索す
ると、５分で３候補あるが、ここでは丸の内線東京駅ノ
ードをｖとする。

【００５４】以上の処理をｖが目的地点に達するまで継
続すると、永久ラベルは以下のように求められる。 出発地点 ：（＊，０分） 丸の内線東京駅 ：（出発地点，３分） 銀座線京橋駅 ：（出発地点，４分） 丸の内線大手町駅：（丸の内線東京駅→丸の内線，５
分） 丸の内線銀座駅 ：（丸の内線東京駅→丸の内線，５
分） 銀座線銀座駅 ：（銀座線京橋駅→銀座線，５分） 銀座線日本橋駅 ：（銀座線京橋駅→銀座線，６分） 丸の内線淡路町 ：（丸の内線大手町駅→丸の内線，７
分） 丸の内線霞ヶ関駅：（丸の内線銀座駅→丸の内線，７
分） 銀座線新橋駅 ：（銀座線銀座駅→銀座線，７分） 銀座線三越前駅 ：（銀座線日本橋駅→銀座線，７分） 日比谷線銀座駅 ：（丸の内線銀座駅→徒歩，８分） 日比谷線大手町駅：（日比谷線大手町駅→徒歩，８分） 銀座線神田橋駅 ：（銀座線三越前→銀座線，８分） 日比谷線日本橋駅：（銀座線日本橋駅→徒歩，９分） 都営浅草線日本橋駅：（銀座線日本橋駅→徒歩，９分） 日比谷線日比谷駅：（日比谷線銀座駅→日比谷線，９
分） 都営浅草線室町駅：（都営浅草線日本橋駅→都営浅草
線，１０分） 日比谷線東銀座駅：（日比谷線銀座駅→日比谷線，１０
分） 日比谷線霞ヶ関駅：（丸の内線霞ヶ関駅→徒歩，１０
分） 都営浅草線新橋駅：（銀座線新橋駅→徒歩，１０分） 日比谷線竹橋駅 ：（日比谷線大手町駅→大手町，１０
分） 目的地点 ：（銀座線三越前駅→徒歩，１０分） したがって、目的地点までは１０分で行けることにな
る。目的地点からの最短経路は永久ラベルをたどること
によって求められる。なお図４のフローチャートに従え
ば、最後の“目的地点：（銀座線三越前駅→徒歩，１０
分）”は、終了処理で目的地点ｖを永久ラベル化するこ
とによって求められる。

【００５５】目的地点のラベルは“目的地点：（銀座線
三越前駅→徒歩，１０分）”なので、目的地点に最初に
到達したのは“銀座線三越前駅→徒歩”である。次に銀
座線三越前駅のラベルを見ると“銀座線三越前駅：（銀
座線日本橋駅→銀座線，７）”なので、銀座線日本橋駅
から銀座線で銀座線三越前駅であることがわかる。以下
同様にして出発地点のラベル（＊，０分）まで経路をた
どれば、最短経路が得られる。したがって、最短経路は
“出発地点→銀座線京橋駅→銀座線日本橋駅→銀座線三
越前駅→目的地点”となる。

【００５６】（実施例２）ここでは、歩行区間を『道路
地図による歩行コスト計算』で求めることにする。使用
する交通機関は実施例１と同様に図６の路線図に従うも
のとする。したがって実施例１と実施例２の違いは、出
発地点から乗車駅まで、または目的地点から下車駅まで
の、リンクを求める方法だけである。本実施例では、図
７の道路網ネットワークを用いて歩行コスト計算を行う
ものとする。図７において、交差点（ノード）が丸印
（○）、道路枝（リンク）が矢印（→）で表してある。
また丸印の中の番号はノード番号、四角（□）の中の番
号はリンク番号である。またリンクに付けられた裸の数
字はコストを表し、単位は分（時間）である。

【００５７】『道路地図による歩行コスト計算』は、基
本的に図４で示した探索方法すなわち『ポテンシャルに
よるラベル確定法』を使える。ただしこの場合、出発地
点および目的地点から求められる駅は指定コストの範囲
内のものであるから、『道路地図による歩行コスト計
算』の計算処理では図４のフローチャート中の判定Ｄ１
を ｐ（ｖ）＞Ｐ と書き換える。ここでｐ（ｖ）はノードｖのポテンシャ
ル、Ｐは歩行区間の指定コストである。また終了処理Ｅ
では、「永久ラベルの付けられた駅を乗車駅候補または
下車駅候補として、電車路線網ネットワークに組み込
む」処理を行う。もちろん、最初の処理Ｓの「歩行コス
ト計算」も不要である。

【００５８】上記のように書き換えた処理を実行する
と、永久ラベルの付いてた駅が複数求められ、出発地点
と乗車候補駅を結ぶリンクおよび下車候補駅と目的地点
を結ぶリンクが図５のリンクテーブルに組み込まれる。
図７の道路網ネットワークにおいて出発地点ノードを１
０（図では２重丸にしてある）としたとき、乗車候補駅
は 丸の内線東京駅２６（経路：１０→１→２６、コスト１
１分） 銀座線京橋駅１４ （経路：１０→５→１４、コスト１
３分） が探索される。上記の経路を１本のリンクとして電車路
線網ネットワークに組み込む。すなわち、 出発地点→丸の内線東京駅Ｌ１，コスト１１分 出発地点→銀座線京橋駅Ｌ２，コスト１３分 として組み込む。ここでＬ１、Ｌ２はリンク暗号を表
し、リンクテーブルにない番号を設定する。

【００５９】目的地点から下車候補駅の探索も、乗車駅
探索と同様に行える。乗車駅探索では出発地点から始
め、出リンクを対象にしたが、下車駅探索では目的地点
から入リンクを対象に目的地点から逆探索する。ただし
歩行の場合には、車の場合と違って一方通行、信号、渋
滞などの影響をほとんど受けないので、出リンクと入リ
ンクのコストは同じとして扱っても問題はない。新しい
リンクが電車路線網ネットワークに組み込まれたあと
は、実施例１と同じように『ポテンシャルによるラベル
確定法』で経路探索が行える。

【００６０】

【発明の効果】現在、都会の交通網は発達している。と
くに地下鉄の路線は蜘蛛の巣のように複雑に入り組んで
いる。これらの電車を利用する場合、出発地から乗車駅
および下車駅から目的地までは徒歩となることが多い。
ところが、これまでの路線探索は徒歩の区間を無視し、
乗車駅と下車駅を最寄りの駅としてあらかじめ指定して
路線探索を行っていた。しかし、この探索方法に落とし
穴がある。それは、最寄りの駅として指定した駅が、歩
行区間を含めてみたときに最小のコストになっているか
は保証されていないことである。この点、本発明では出
発地と目的地を直接指定し、歩行区間も含めて経路探索
をするために、正確な最小コスト探索が行える。したが
って、本発明での探索結果は、乗車駅および下車駅が必
ずしも最寄りの駅（駅から出発地あるいは目的地の歩行
区間が最短の駅）とは限らない。しかし、歩行区間も含
めたトータルのコスト（通常、時間）が最小になってい
ることを保証している。慣れた土地での路線探索なら最
寄りの駅を指定して最小コスト探索を行えばよいが、慣
れない土地での最小コスト探索は本発明の効果がより発
揮される。しかも、乗車駅や下車駅を指定するのでな
く、直接出発地と目的地を指定することができるため
に、指定が簡単であり、より正確なトータルコストが得
られる。

【００６１】路線探索をする場合、「ここからだとどこ
の駅が一番いい」などとほかの人に聞いている光景をよ
く見かける。その点、本発明では歩行区間も含めた出発
地と目的地を指定するために、最寄りの駅はどこかなど
と悩む必要がない。もっとも最寄りの駅（歩いて最短の
駅）を見たい場合には、本発明の『道路地図による歩行
コスト計算』部分を独立されて、最小ポテンシャルの駅
を探索すれば、容易に最寄り駅が探索できる。本発明
は、その点の柔軟性も有している。

【００６２】乗車駅候補、下車駅候補を求める方法とし
て、本発明では２通りの手法を提唱した。『直線距離に
よる歩行コスト計算』では歩行区間のコストは２点間を
結ぶ直線距離に比例している点に注目して、簡易的に乗
車候補駅および下車候補駅を求めている。通常、都会の
道路は直角に曲がることが多いので、最大で直線距離の
２の平方根倍（約１．４）の誤差が生じる可能性を有し
ている。たとえば、指定歩行コストを１０分とした場合
には、徒歩で最大１４分程度の候補駅が抽出される場合
もある。この点は、プログラミングする際に考慮する必
要があるかも知れない。たとえば、図８のようにＡ点か
らＢ点に行く場合、実際の経路はＡ→Ｄ→Ｅ→Ｆ→Ｇ→
Ｂのような折れ線（いずれも直角に曲がるものとしてい
る）で示す経路になっているとすれば、折れ線の距離は
直角三角形ＡＢＣの２辺の和、すなわちＡＣ＋ＣＢで表
した方がより正確にコスト計算ができるかも知れない。
しかし、本発明の主旨である、プログラミングが簡単
で、しかも処理時間の速い処理が可能であるという点に
は、変わりはない。とくにここで大切なのは、歩行区間
も含めた探索が自動的に行え、しかも現実的にそれほど
誤差がないという点である。

【００６３】一方、正確な歩行コストを割り出すため
に、『道路地図による歩行コスト計算』を提唱してい
る。このコスト計算処理は『ポテンシャルによるラベル
確定法』とほとんど同じ処理で求められるために、プロ
グラミング的には共通する処理をサブルーチン化すれ
ば、プログラムが極端に大きくなるということはない。
『直線距離による歩行コスト計算』に比べて処理時間が
かかるという点はあるが、正確な歩行コストと、歩行区
間の経路も利用者に提供できるというメリットをもって
いる。

【図面の簡単な説明】

【図１】従来技術におけるラベル確定法を用いて最適解
を求める方法を具体的に説明するためのネットワーク図
である。

【図２】本発明の実施の形態におけるノード、リンク、
ポテンシャルおよびその記号を説明するための図であ
る。

【図３】本発明の実施の形態における仮ラベルを有する
ノードと永久ラベルを有するノードを説明するための図
である。

【図４】本発明の実施の形態における最小コスト条件下
で出発地点から目的地点までの経路探索を行う処理をフ
ローチャート化したものである。

【図５】本発明の実施の形態におけるリンクテーブルを
説明するための図である。

【図６】本発明の実施の形態において、直線距離による
候補駅探索を含む実施例として使用した地下鉄路線図で
ある。

【図７】本発明の実施の形態において、道路地図による
候補駅探索を含む実施例として使用した道路網ネットワ
ーク図である。

【図８】発明の効果おいて、直線距離による候補駅探索
の別形態を補足的に説明した図である。

Claims (9)

【特許請求の範囲】
1. 【請求項１】出発地点から目的地点までの経路を、地点
   をノード、地点間をリンクとして交通ネットワークを表
   現し、コンピュータを用いてラベル確定法によりコスト
   として移動時間または移動距離を用いて、最短コスト条
   件下で探索する交通ネットワーク経路探索方法におい
   て、(1)出発地点および目的地点から利用する交通機関
   の駅までの経路として、出発地点および目的地点から利
   用する交通機関の駅までの直線距離、および目的地点か
   ら利用する交通機関の駅までの直線距離を緯度経度情報
   を用いて求め、該直線距離を変数として平均コストを算
   出し、前記平均コストが指定したコストの範囲内に含ま
   れるすべての利用交通機関の駅を求め、歩行経路を決定
   する、(2)前記求められた歩行経路を交通機関の交通ネ
   ットワーク経路に組み込んで総合交通ネットワークを表
   現し、コンピュータを用いてラベル確定法により求める
   コスト条件下で探索することを特徴とする交通ネットワ
   ーク経路探索方法。
2. 【請求項２】出発地点から目的地点までの経路を、地点
   をノード、地点間をリンクとして交通ネットワークを表
   現し、コンピュータを用いてラベル確定法によりコスト
   として移動時間または移動距離を用いて、最短コスト条
   件下で探索する交通ネットワーク経路探索システムにお
   いて、(1)出発地点および目的地点から利用する交通機
   関の駅までの経路として、出発地点および目的地点から
   利用する交通機関の駅までの直線距離、および目的地点
   から利用する交通機関の駅までの直線距離を緯度経度情
   報を用いて求め、該直線距離を変数として平均コストを
   算出し、前記平均コストが指定したコストの範囲内に含
   まれるすべての利用交通機関の駅を求め、歩行経路を決
   定する手段、(2)前記求められた歩行経路を交通機関の
   交通ネットワーク経路に組み込んで総合交通ネットワー
   クを表現し、コンピュータを用いてラベル確定法により
   求めるコスト条件下で探索する手段を備えたことを特徴
   とする交通ネットワーク経路探索システム。
3. 【請求項３】出発地点から目的地点までの経路を、地点
   をノード、地点間をリンクとして交通ネットワークを表
   現し、コンピュータを用いてラベル確定法によりコスト
   として移動時間または移動距離を用いて、最短コスト条
   件下で探索する交通ネットワーク経路探索において、
   (1)出発地点および目的地点から利用する交通機関の駅
   までの経路として、出発地点および目的地点から利用す
   る交通機関の駅までの直線距離、および目的地点から利
   用する交通機関の駅までの直線距離を緯度経度情報を用
   いて求め、該直線距離を変数として平均コストを算出
   し、前記平均コストが指定したコストの範囲内に含まれ
   るすべての利用交通機関の駅を求め、歩行経路を決定
   し、(2)前記求められた歩行経路を交通機関の交通ネッ
   トワーク経路に組み込んで総合交通ネットワークを表現
   し、コンピュータを用いてラベル確定法により求めるコ
   スト条件下で探索する処理を実行するプログラムを記録
   したコンピュータ用記録媒体。
4. 【請求項４】出発地点から目的地点までの経路を、地点
   をノード、地点間をリンクとして交通ネットワークを表
   現し、コンピュータを用いてラベル確定法によりコスト
   として移動時間または移動距離を用いて、最短コスト条
   件下で探索する交通ネットワーク経路探索方法におい
   て、(1)出発地点および目的地点から利用する交通機関
   の駅までの経路として、指定したコストの範囲内に含ま
   れる駅までの歩行経路を、緯度経度情報を含む地図デー
   タにより作られる道路網ネットワークを用いたラベル確
   定法により、求めるコスト条件下で歩行経路を決定す
   る、(2)前記求められた１以上の歩行経路を交通機関の
   交通ネットワーク経路に組み込んで総合交通ネットワー
   クを表現し、コンピュータを用いてラベル確定法により
   求めるコスト条件下で探索することを特徴とする交通ネ
   ットワーク経路探索方法。
5. 【請求項５】出発地点から目的地点までの経路を、地点
   をノード、地点間をリンクとして交通ネットワークを表
   現し、コンピュータを用いてラベル確定法によりコスト
   として移動時間または移動距離を用いて、最短コスト条
   件下で探索する交通ネットワーク経路探索システムにお
   いて、(1)出発地点および目的地点から利用する交通機
   関の駅までの経路として、指定したコストの範囲内に含
   まれる駅までの歩行経路を、緯度経度情報を含む地図デ
   ータにより作られる道路網ネットワークを用いたラベル
   確定法により、求めるコスト条件下で歩行経路を決定す
   る手段、(2)前記求められた１以上の歩行経路を交通機
   関の交通ネットワーク経路に組み込んで総合交通ネット
   ワークを表現し、コンピュータを用いてラベル確定法に
   より求めるコスト条件下で探索する手段を備えたことを
   特徴とする交通ネットワーク経路探索システム。
6. 【請求項６】出発地点から目的地点までの経路を、地点
   をノード、地点間をリンクとして交通ネットワークを表
   現し、コンピュータを用いてラベル確定法によりコスト
   として移動時間または移動距離を用いて、最短コスト条
   件下で探索する交通ネットワーク経路探索において、
   (1)出発地点および目的地点から利用する交通機関の駅
   までの経路として、指定したコストの範囲内に含まれる
   駅までの歩行経路を、緯度経度情報を含む地図データに
   より作られる道路網ネットワークを用いたラベル確定法
   により、求めるコスト条件下で歩行経路を決定し、(2)
   前記求められた１以上の歩行経路を交通機関の交通ネッ
   トワーク経路に組み込んで総合交通ネットワークを表現
   し、コンピュータを用いてラベル確定法により求めるコ
   スト条件下で探索する処理を実行するプログラムを記録
   したコンピュータ用記録媒体。
7. 【請求項７】前記ラベル確定法が、(1)、出発ノードと
   特定ノードを結ぶリンクと、前記出発ノードから特定ノ
   ードまでの累計コストを表すポテンシャルとから構成さ
   れるラベルを導入し、「＊」は出発地点はどのリンクも
   入ってこないことを意味し、「Φ」はまだそのノードに
   どのリンクも到達していないことを意味し、「∞」は扱
   う問題において十分に大きい数を意味する表記としたと
   き、初期値として出発ノードに対しては（＊，０）、そ
   の他のノードには（Φ，∞）を仮ラベルとして設定す
   る、(2)前記仮ラベルのついたノードのうち最小のポテ
   ンシャルのノードを選択し、このノードが目的地点の場
   合には経路探索を終了して下記（4）の終了処理ルーチ
   ンを実行し、目的地点でない場合には以下（3）の処理
   ルーチンを続行する、(3)前記最小のポテンシャルのノ
   ードから出るリンクの終点ノードのなかで仮ラベルを有
   する終点ノードのポテンシャルを算出し、前記算出され
   た終点ノードのポテンシャルが、前記終点ノードにつけ
   られている仮ラベルのポテンシャルより小さいときは前
   記仮ラベルを前記算出された終点ノードのポテンシャル
   で書き換え、前記最小のポテンシャルのノードの仮ラベ
   ルを永久ラベルに変えて上記(2)の処理ルーチンを実行
   する、(4)目的地点から順に永久ラベルをもとに出発地
   点までの経路をたどり、歩行経路も含めた最小ポテンシ
   ャルの経路を求める、方法であることを特徴とする請求
   項１または３記載の交通ネットワーク経路探索方法 。
8. 【請求項８】前記ラベル確定法が、(1)、出発ノードと
   特定ノードを結ぶリンクと、前記出発ノードから特定ノ
   ードまでの累計コストを表すポテンシャルとから構成さ
   れるラベルを導入し、「＊」は出発地点はどのリンクも
   入ってこないことを意味し、「Φ」はまだそのノードに
   どのリンクも到達していないことを意味し、「∞」は扱
   う問題において十分に大きい数を意味する表記としたと
   き、初期値として出発ノードに対しては（＊，０）、そ
   の他のノードには（Φ，∞）を仮ラベルとして設定す
   る、(2)前記仮ラベルのついたノードのうち最小のポテ
   ンシャルのノードを選択し、このノードが目的地点の場
   合には経路探索を終了して下記（4）の終了処理ルーチ
   ンを実行し、目的地点でない場合には以下（3）の処理
   ルーチンを続行する、(3)前記最小のポテンシャルのノ
   ードから出るリンクの終点ノードのなかで仮ラベルを有
   する終点ノードのポテンシャルを算出し、前記算出され
   た終点ノードのポテンシャルが、前記終点ノードにつけ
   られている仮ラベルのポテンシャルより小さいときは前
   記仮ラベルを前記算出された終点ノードのポテンシャル
   で書き換え、前記最小のポテンシャルのノードの仮ラベ
   ルを永久ラベルに変えて上記(2)の処理ルーチンを実行
   する、(4)目的地点から順に永久ラベルをもとに出発地
   点までの経路をたどり、歩行経路も含めた最小ポテンシ
   ャルの経路を求める、方法であることを特徴とする請求
   項２または４記載の交通ネットワーク経路探索システム
   。
9. 【請求項９】前記ラベル確定法が、(1)、出発ノードと
   特定ノードを結ぶリンクと、前記出発ノードから特定ノ
   ードまでの累計コストを表すポテンシャルとから構成さ
   れるラベルを導入し、「＊」は出発地点はどのリンクも
   入ってこないことを意味し、「Φ」はまだそのノードに
   どのリンクも到達していないことを意味し、「∞」は扱
   う問題において十分に大きい数を意味する表記としたと
   き、初期値として出発ノードに対しては（＊，０）、そ
   の他のノードには（Φ，∞）を仮ラベルとして設定す
   る、(2)前記仮ラベルのついたノードのうち最小のポテ
   ンシャルのノードを選択し、このノードが目的地点の場
   合には経路探索を終了して下記（4）の終了処理ルーチ
   ンを実行し、目的地点でない場合には以下（3）の処理
   ルーチンを続行する、(3)前記最小のポテンシャルのノ
   ードから出るリンクの終点ノードのなかで仮ラベルを有
   する終点ノードのポテンシャルを算出し、前記算出され
   た終点ノードのポテンシャルが、前記終点ノードにつけ
   られている仮ラベルのポテンシャルより小さいときは前
   記仮ラベルを前記算出された終点ノードのポテンシャル
   で書き換え、前記最小のポテンシャルのノードの仮ラベ
   ルを永久ラベルに変えて上記(2)の処理ルーチンを実行
   する、(4)目的地点から順に永久ラベルをもとに出発地
   点までの経路をたどり、歩行経路も含めた最小ポテンシ
   ャルの経路を求める、方法であることを特徴とする請求
   項３または６記載のコンピュータ用記録媒体。