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

Description

【０００１】
【発明の属する技術分野】
本発明は、歩行と交通機関を含む交通ネットワークにおける、出発地点から目的地点までの経路を最小コスト条件下で探索するコンピュータシステムに関する。
【０００２】
【従来の技術】
複雑な交通ネットワークにおいては、最適な経路を求めることは容易でない。また最適といっても、時間、費用など多くの要素がある。コンピュータを用いて、すべての組み合わせを計算すれば最適な経路は求まるが、ネットワークが複雑になると高性能のコンピュータをもってしても計算時間が増加し、実質的に計算が不可能な事態となる。
【０００３】
このような、実質的に計算不可能な事態に対応すべく、様々な手法が提案されている。交通ネットワークに対するコンピュータを用いた最短経路探索でよく用いられるラベル確定法は、コンピュータの要処理時間が少なくてすみ、迅速に回答を得られる。以下、簡単にこのラベル確定法を説明する。ラベル確定法はこの方法の発明者の名をとってダイクストラ法と呼ばれることもある。
【０００４】
いま図１のようなネットワークで表現されるシステムを例に説明する。特定の地点に対応する図の丸印を「ノード」、そのノードとノードを結ぶ線は地点間の経路に相当し、「リンク」と呼ぶ。数学的にはこれらのノードとリンクの集合をグラフと呼び、リンクに向きが有るものを有向グラフ、無いものを無向グラフと呼んでいる。図１の例は有向グラフの例である。このようなシステムで、出発点のノードｓから目的点のノードｔへの経路で、最も短くなるものを見い出す問題が最短路問題である。
【０００５】
いま、ノードｓからノードｔへの最短路Ｐを
Ｐ＝｛ｓ，ｉ，ｊ，……、ｋ，ｔ｝
とする。このとき、Ｐをあるノードを境にしてＰ１とＰ２に分割した場合、部分集合Ｐ１とＰ２も、それぞれの集合内で最短路になっている。これを最適性の原理と呼ぶ。この原理を利用して数理的に最短路を求めるアルゴリズムがラベル確定法である。すなわち、ラベル確定法は空集合から始めて、ノードに仮ラベルをつけて、最短路となるノードを一つずつ求めて最短路部分集合を膨らませていき、最終的に全部のノードに対してラベルを永久ラベルに確定させ、最短路を求める方法である。以下は、コンピュータでプログラミングするときのアルゴリズムである。
【０００６】
ノードｓからノードｔに到るあらゆるノードの集合をＶ、ノードｓからノードｊに至る最短路の長さｄ（ｊ）、その最短路のノードの集合をＳ１、その補集合をＳ２（＝Ｖ−Ｓ１）とすると、以下の方法で最短路が求まる。
(1)初期値化として、
Ｓ１←０（空集合）、Ｓ２←Ｖ
ｄ（ｓ）←０、ｄ（ｉ）←∞
とする。ここで、ｉは最短路のノードの補集合Ｓ２に含まれるノード、Ｘ←ＹはＸをＹで置き換えることを表す。
【０００７】
(2)Ｓ１＝Ｖなら計算終了。
(3)Ｓ１≠Ｖなら、
最短路の長さｄ（ｉ）を選び出し、
ｖ←ｉ
とする。長さｄ（ｖ）はノードｓからノードｖに至る最短路となっているから、ノードｖを最短路のノードの集合Ｓ１に含め、ノードｖを最短路のノードの補集合Ｓ２から外す。
【０００８】
(4)ノードｖから出るリンク（出リンク）が次に到達する、最短路のノードの補集合Ｓ２に含まれるすべてのノードｉに対して
ｄ'（ｉ）←ｄ（ｖ）＋ａｖｉ
を計算し、
ｄ（ｉ）＞ｄ'（ｉ） なら
ｄ（ｉ）←ｄ'（ｉ） かつ ｐ（ｉ）←ｖ
とする。ここで、ａｖｉはノードｖからノードｉに至る長さ（リンクの長さ）であり、ｄ（ｉ）、ｄ'（ｉ）は出発点ｓからｉに至る経路の長さである。この時点のｄ（ｉ）は、最短路のノードの集合Ｓ１内のノードからの最短路長になっている。最短路のノードの補集合Ｓ２にはもっと短い経路が存在する可能性はあるが、それは繰り返し計算のなかで求められることになる。
(5)ステップ(2)のステップに戻る。
【０００９】
以上の方法で求めたｐ（ｉ）に対して、最終ノードｔからｐ（ｔ）をもとに逆にたどっていけば、出発ノードｓまでの最短路が求まる。たとえば、図１の例を上記のアルゴリズムで求めると、

となる。
【００１０】
ｓ＝１、ｔ＝５であるから、ノード５の前はノード３（p(5)=3）、ノード３の前はノード２（p(3)=2）、ノード２の前はノード１（p(2)=1）、すなわち出発点ｓにたどりつく。すなわち、最短路は１→２→３→５、その長さは８５（=d(5)）である。また、ノード１からノード４に至る経路（１→２→４）の長さd(4)は、やはり最短路長になっている。
【００１１】
実際に上記のアルゴリズムで用いた図１の経路をシミュレーションしてみるとわかるが、ノード３からノード４に至る長さd'(4)は計算しなくてもすむ。すなわち、ラベル確定法を用いれば、総組み合わせによる最短路計算に比べて、計算量がはるかに少なくてすむ。
【００１２】
応用例として、ある駅を出発点にして目的の駅までの経路を求める路線経路探索に上記のラベル確定法を応用することができる。この場合には、最短路長を距離だけでなく、時間、運賃など別の単位を取り。このような単位をコストとよぶ概念を使うことで適用できる。
【００１３】
【発明が解決しようとする課題】
従来技術で説明したラベル確定法は、コンピュータを用いた場合に処理速度が速いという特徴をもっている。とくに出発点と目的点が決まっている場合には、ラベル確定法によって出発点から順次最小コストとなるノードを見つけながら、目的点に最初に到達する経路を最小コスト経路として探索できる。対象となるコストは具体的には時間、あるいは距離があてられ、「移動時間」あるいは「移動距離」を評価することになる。
【００１４】
多くのナビゲーションシステムでは、コンピュータ上の問題解決手段として様々な方法を用いているが、最小コストという条件で経路探索をする場合には、基本的にラベル確定法が用いられている。たとえば、このような最小コスト経路探索には、鉄道機関を用いての最小コスト経路探索や、自動車による最小コスト経路探索システムがある。
【００１５】
しかし従来のナビゲーションシステムでは、歩行と他の機関との組み合わせによる経路探索はなされていない。たとえば鉄道機関を利用するナビゲーションシステムの場合、利用者が出発地点から徒歩でどの駅に行き、到着する駅から徒歩で目的地点にどれだけ掛かるかなどは、考慮されていない。したがって、このようなナビゲーションシステムでは、出発点の最寄りの駅と目的地点の最寄りの駅をあらかじめ指定してから、探索が開始されている。このため、従来のナビゲーションシステムは指定した出発駅か到達駅までは正確な最小コスト探索が行えるが、徒歩の区間を含めた探索において最小コストになっていることは保証されていない。
【００１６】
そこで本発明が解決しようとする課題は、歩行者が利用しようとしている交通機関の乗車地点へ徒歩で行き、および交通機関の到達地点から目的地点までを徒歩で行くとした場合に、利用者が目的地点を指定するだけで、徒歩の区間も含めて最小コストの経路を探索する手段を提唱することにある。
【００１７】
【課題を解決するための手段】
本発明は上記の課題を解決するために、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法によりコストとして移動時間または移動距離を用いて、最短コスト条件下で探索する交通ネットワーク経路探索方法において、
出発地点および目的地点から利用する交通機関の駅として、出発地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コス トを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、利用する駅を決定する、
前記求められた利用する交通機関の駅までの前記平均コストを交通機関の交通ネットワークに組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索することを特徴とする交通ネットワーク経路探索方法を用いる。
【００１８】
また、処理時間はかかるが歩行経路の決定に異なる次のような手法も用いることができる。(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)地点をノード、地点間をリンクとして交通ネットワークを表現し、出発ノードと特定ノードを結ぶリンクと、前記出発ノードから特定ノードまでの累計コストを表すポテンシャルとから構成されるラベルを導入し、「＊」は出発地点はどのリンクも入ってこないことを意味し、「Φ」は、まだそのノードにどのリンクも到達していないことを意味し、「∞」は扱う問題において十分に大きい数を意味する表記を用いて、初期値として出発ノードに対しては（＊，０）、その他のノードには（Φ，∞）を仮ラベルとして設定する。
(3)仮ラベルのついたノードのうち最小のポテンシャルのノードを選択し、選択したノードが目的地点の場合には経路探索を終了して下記(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 (3)

1. 出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法によりコストとして移動時間または移動距離を用いて、最短コスト条件下で探索する交通ネットワーク経路探索方法において、
   出発地点および目的地点から利用する交通機関の駅として、出発地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、利用する駅を決定する、
   前記求められた利用する交通機関の駅までの前記平均コストを交通機関の交通ネットワークに組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索することを特徴とする交通ネットワーク経路探索方法。
2. 出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法によりコストとして移動時間または移動距離を用いて、最短コスト条件下で探索する交通ネットワーク経路探索システムにおいて、
   出発地点および目的地点から利用する交通機関の駅として、出発地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、利用する駅を決定する手段、
   前記求められた利用する交通機関の駅までの前記平均コストを交通機関の交通ネットワークに組み込んで総合交通ネットワークを表現し、コンピュータを用 いてラベル確定法により求めるコスト条件下で探索する手段を備えたことを特徴とする交通ネットワーク経路探索システム。
3. 出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法によりコストとして移動時間または移動距離を用いて、最短コスト条件下で探索する交通ネットワーク経路探索において、
   出発地点および目的地点から利用する交通機関の駅として、出発地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、利用する駅を決定し、
   前記求められた利用する交通機関の駅までの前記平均コストを交通機関の交通ネットワークに組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索する
   処理を実行するプログラムを記録したコンピュータ用記録媒体。

Images