(57)【要約】【課題】無駄な検索を省き、効率的な検索を行うことができる経路探索方法及び経路探索プログラムを提供する。【解決手段】駅をノードに持ち、駅間の路線及び徒歩乗り換えをアークで表現するネットワークを作成し（Ｓ１０１）、検索条件を読み込み（Ｓ１０２）、検索に必要なデータを読み込む（Ｓ１０３）。次に、路線変更アークの重みを変更し（Ｓ１０４）、最短パス木の作成を行い（Ｓ１０５）、最短パス木をもとに複数の最短パスを探索する（Ｓ１０６）。次に、複数の最短パスに対して路線変更アークの除去及び連続した同一路線名のアークを短縮を行い、複数の最短経路を求める（Ｓ１０７）。次に、複数の最短経路に対して時間を割り当て（Ｓ１０８）、料金を計算する（Ｓ１０９）。次に、優先基準に基づき、上位複数の経路を選択して表示する（Ｓ１１０）。【選択図】　　　図１
2004061298.tif 000002
【特許請求の範囲】
【請求項１】
データ記憶装置に保存されている、複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークを読み込むステップと、
入力された検索条件に基づき、前記ネットワーク上で出発地点及び目的地点における、クリーク化によって設けられたクリーク地点間の路線変更アークの重みを変更するステップと、
入力された検索条件に基づき、前記ネットワーク上で前記出発地点から前記目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記最短パス木をもとに前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップ
とを含むことを特徴とする経路探索方法。
【請求項２】
前記変更するステップは、前記路線変更アークの重みを０にすることを特徴とする請求項１に記載の経路探索方法。
【請求項３】
前記変更するステップは、前記出発地点で乗車する路線名が指定された場合は、前記出発地点の路線変更アークの重みを極大値にし、前記目的地点で下車する路線名が指定された場合は、前記目的地点の路線変更アークの重みを極大値にすることを特徴とする請求項１に記載の経路探索方法。
【請求項４】
一部並走する異なる路線がある場合は、それらの路線間の路線変更アークの一部を削除するステップと、
前記出発地点及び前記目的地点のクリークにおける削除された前記路線変更アークを復活するステップ
とを更に含むことを特徴とする請求項１〜３のいずれか１項に記載の経路探索方法。
【請求項５】
前記最短パス木の、前記出発地点及び前記目的地点のクリークにおいて、重みが０である路線変更アークが連続する場合に、該連続した路線変更アークを一つの路線変更アークに張り替えるステップを更に含むことを特徴とする請求項１〜４のいずれか１項に記載の経路探索方法。
【請求項６】
前記複数の最短パスに対して、前記路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップと、
優先基準に基づき、前記複数の最短経路の一部を選択して出力装置に出力するステップ
とを更に含むことを特徴とする請求項１〜５のいずれか１項に記載の経路探索方法。
【請求項７】
データ記憶装置に保存されている、複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークを読み込む命令と、
入力された検索条件に基づき、前記ネットワーク上で出発地点及び目的地点における、クリーク化によって設けられたクリーク地点間の路線変更アークの重みを変更する命令と、
入力された検索条件に基づき、前記ネットワーク上で前記出発地点から前記目的地点までの最短パスに関わる最短パス木の作成を行う命令と
前記最短パス木をもとに前記出発地点から前記目的地点までの複数の最短パスの検索を行う命令
とを与えることを特徴とする経路探索プログラム。
【請求項８】
前記複数の最短パスに対して、前記路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求める命令と、
優先基準に基づき、前記複数の最短経路の一部を選択して出力装置に出力する命令
とを更に与えることを特徴とする請求項７に記載の経路探索プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータを用いて出発地と目的地間の経路を１つ又は複数検索できる経路探索方法及び経路探索プログラムに関する。
【０００２】
【従来の技術】
従来、コンピュータを用いて出発地、目的地、出発希望時刻等を入力すると、出発地から目的地に至る１つ又は複数の経路を表示（案内）するソフトウェアが存在する。例えば、列車の乗り換え案内の場合、表示される経路は、出発駅、乗換駅、目的駅、利用路線又は利用列車等からなり、更に、出発駅での発時刻、乗換駅での発／着時刻、目的駅での着時刻や、所要時間、料金等も表示されることが多い。このような検索サービスは、パッケージソフトあるいはサービス提供会社のＷｅｂページ上で行われている。
【０００３】
この経路探索は、通常、各ノード間をアークで接続し、各アークに重み（コスト）が割り振られたグラフであるネットワークをもとに考える。ネットワークにおいて、出発ノードｓから目的ノードｔへのパスを考えるとき、ｓからｔへの第ｉ番目に短いパスをｓからｔへの第ｉ最短パスと言う。第１最短パスがいわゆる最短パスである。最短パスは、良く知られているようにダイクストラ法によって高速に求められる。第２最短パス以降の最短パスを求めるアルゴリズムについても古くから研究され、種々の効率良いアルゴリズムが提案されている。
【０００４】
第１〜Ｋ最短パスを求めるアルゴリズムとしては、例えば、マーチンのアルゴリズム（「複数のループレスパスを短い順に列挙するためのアルゴリズム（Ａｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｒａｎｋｉｎｇ　ｌｏｏｐｌｅｓｓ　ｐａｔｈｓ）」，　イー・キュー・ブイ・マーチン他（Ｅ．Ｑ．Ｖ．Ｍａｒｔｉｎｓ　ｅｔ　ａｌ．，）、コインブラ大学研究レポート（Ｒｅｓｅａｒｃｈ　Ｒｅｐｏｒｔ，　Ｕｎｉｖ．　ｄｅ　Ｃｏｉｍｂｒａ）、１９９９など）が知られている。第１〜Ｋ最短パスを求める場合、ループ（閉路）を許す場合と許さない場合とがある。ループを許すというのは、同じノードを２度以上通るような冗長なパスも第ｉ最短パスとして採用しようというものである。ループを許した方が問題としては扱いやすいが、一般にはループを許さない場合の方が実用的である。マーチンのアルゴリズムは、ループを許さない場合のアルゴリズムの１つである。
【０００５】
各アークの重みが非負の連結なネットワークにおいて、各ノードから目的ノードｔへの最短パスは、同一のノードを２度通ることのないパスとなる。そして、全てのノードからｔへの最短パスはｔを根とする根付き木で表現できる。この根付き木を最短パス木という（「情報の構造（下）」、浅野孝夫著、日本評論社、ｐ．２４１参照）。又、条件「根以外の各節点ｖに対して、親の要素の方が子の要素よりも小さいか等しい」を満すように、木の各節点ｖに順序集合Ｓの要素が割り当てられた根付き木をヒープという（「情報の構造（上）」、浅野孝夫著、日本評論社、ｐ．４５参照）。
【０００６】
マーチンのアルゴリズムにおいては、出発ノードｓから目的ノードｔへのパスがヒープの節点に相当し、パスのコスト（パス上のアークの重みの和）が順序集合Ｓの要素に相当する。マーチンのアルゴリズムの概要を説明すると、まずダイクストラ法で目的ノードｔを根に持つ最短パス木を作り、最短パスをヒープに蓄える。次に、ｋ＝０として次の処理（ｉ）、（ｉｉ）　を繰り返す。
【０００７】
（ｉ）　ヒープからコスト最小のパスｐを抜き出す。もしｐがループを含まないならば、ｐを第ｋ＋１最短パスとして登録し、ｋに１を加算する。ｋ＝Ｋなら終了。
【０００８】
（ｉｉ）ｐがループを含む／含まないに関わらず、ｐに対する派生パス（１歩横にそれて、そこから最短パス木上のアークを一気に進むパス）をｐ上の各ノードにつき高々１つずつ求め、ヒープに蓄える。（ｉ）　に戻る。
【０００９】
派生パスを作る際のアーク、つまり元のパスｐから１歩横にそれる際のアークの選び方がポイントである。
【００１０】
【発明が解決しようとする課題】
しかし、上記の方法では、駅をノードに持ち、駅間の路線及び徒歩乗り換えをアークで表現するネットワークにおいて、乗車駅又は下車駅に複数の路線が乗り入れている場合、それらの路線に対応する駅をすべて同等に扱うことが難しく、又、乗車駅あるいは下車駅で利用したい路線名を指定することが難しかった。
【００１１】
又、一部並走する異なる路線があると、それらの路線間での様々な乗り換えパターンが可能となり、その結果、互いに似通った経路が頻繁に出力されるという問題があった。
【００１２】
更に、複数の路線が乗り入れる乗車駅又は下車駅を含む最短パス木を作成する際、最短パス木のアークの冗長性から、無駄な探索を行うことが多いという問題があった。
【００１３】
よって、上記の問題を鑑み、本発明は、無駄な検索を省き、効率的な検索を行うことができる経路探索方法及び経路探索プログラムを提供することを目的とする。
【００１４】
【課題を解決するための手段】
上記目的を達成するため、本発明の第１の特徴は、（イ）データ記憶装置に保存されている、複数の地点をそれぞれノードで、隣り合う地点間の路線を複数のアークで表現し、ノードの一部がクリーク化されたネットワークを読み込むステップと、（ロ）入力された検索条件に基づき、ネットワーク上で出発地点及び目的地点における、クリーク化によって設けられたクリーク地点間の路線変更アークの重みを変更するステップと、（ハ）入力された検索条件に基づき、ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、（ニ）最短パス木をもとに出発地点から目的地点までの複数の最短パスの検索を行うステップとを含むことを特徴とする経路探索方法であることを要旨とする。ここで、「地点」とは、列車の駅、空港、バス停、あるいは道路などの特定の地点を指す。「クリーク化」とは、一つの地点を、その地点に接続する路線数に相当する複数のノードとして表し、それらのノード間に路線変更のためのアークを設けることである。この路線変更のためのアークを、「路線変更アーク」という。又、「クリーク」とは、与えられたグラフに含まれる複数の点（ノード）からなる完全部分グラフのことであり、「クリーク地点」とは、クリーク内のそれぞれのノードを指す。又、「アーク」とは、「始点となるノード」、「終点となるノード」及び「両端のノード間の移動時間（重み）」から構成される。
【００１５】
第１の特徴に係る経路探索方法によると、駅をノードに持ち、駅間の路線及び徒歩乗り換えをアークで表現するネットワークにおいて、出発地点あるいは目的地点のクリーク地点を同等に扱うことにより、効率的な検索を行うことができる。
【００１６】
又、第１の特徴に係る経路探索方法の変更するステップは、路線変更アークの重みを０にしても良い。この経路探索方法によると、クリーク内の任意のクリーク地点を、実質的な出発地点あるいは目的地点と見なすことができる。
【００１７】
又、第１の特徴に係る経路探索方法の変更するステップは、出発地点で乗車する路線名が指定された場合は、出発地点の路線変更アークの重みを極大値にし、目的地点で下車する路線名が指定された場合は、目的地点の路線変更アークの重みを極大値にしても良い。ここで、「極大値」とは、実質的に無限大とみなせる値であり、例えば、最も遠く離れた出発地点（乗車駅）と目的地点（下車駅）間の平均的な移動時間（所要時間）の２桁程度以上大きな値である。この経路探索方法によると、例えば出発地点あるいは目的地点で利用したい路線名を指定することが可能となる。
【００１８】
又、第１の特徴に係る経路探索方法は、（ホ）一部並走する異なる路線がある場合は、それらの路線間の路線変更アークの一部を削除するステップと、（へ）出発地点及び目的地点のクリークにおける削除された路線変更アークを復活するステップとを更に含んでも良い。この経路探索方法によると、一部の路線変更アークを禁止アークとして予めネットワーク上から削除しておくことにより、互いに似通った経路が頻繁に出力されることがなく、効率的な検索を行うことができる。
【００１９】
又、第１の特徴に係る経路探索方法は、最短パス木の、出発地点及び目的地点のクリークにおいて、重みが０である路線変更アークが連続する場合に、連続した路線変更アークを一つの路線変更アークに張り替えるステップを更に含んでも良い。この経路探索方法によると、出発地点あるいは目的地点のクリーク内の最短パス木のアークの張り替え操作によって、効率的な検索を行うことができる。
【００２０】
又、第１の特徴に係る経路探索方法は、（ト）複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップと、（チ）優先基準に基づき、複数の最短経路の一部を選択して出力装置に出力するステップとを更に含んでも良い。この経路探索方法によると、出発地点から目的地点への複数の最短経路を効率的に表示することができる。
【００２１】
本発明の第２の特徴は、（イ）データ記憶装置に保存されている、複数の地点をそれぞれノードで、隣り合う地点間の路線を複数のアークで表現し、ノードの一部がクリーク化されたネットワークを読み込む命令と、（ロ）入力された検索条件に基づき、ネットワーク上で出発地点及び目的地点における、クリーク化によって設けられたクリーク地点間の路線変更アークの重みを変更する命令と、（ハ）入力された検索条件に基づき、ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行う命令と、（ニ）最短パス木をもとに出発地点から目的地点までの複数の最短パスの検索を行う命令とを与える経路探索プログラムであることを要旨とする。第２の特徴に係る経路探索プログラムは、（ホ）複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求める命令と、（へ）優先基準に基づき、複数の最短経路の一部を選択して出力装置に出力する命令とを更に与えても良い。
【００２２】
上記の命令を実現させる経路探索プログラムは、経路探索装置の処理制御装置（ＣＰＵ）に接続されているプログラム記憶装置等に保存される。本発明の第２の特徴に係る経路探索プログラムを読み出すことにより、経路探索装置等に上記の命令を実現させることが可能となる。
【００２３】
【発明の実施の形態】
次に、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。但し、図面は模式的なものであることに留意すべきである。
【００２４】
本発明の実施の形態に係る経路探索方法として、まず、複数の「ノード」とノード間を接続する「アーク」からなるネットワークについて説明する。経路探索で用いるネットワークは、基本的には、駅を「ノード」とみなし、線路上で隣り合う駅間に「アーク」を設けて作成する。この例として、Ｘ駅とＹ駅のネットワークを図３に示す。ここでは、Ｘ駅、Ｙ駅がノードとなり、記号Ａ、Ｂ、Ｃ、Ｄ、Ｅを付した実線で示す両端矢印がアークを表す（上り／下りの２本のアークを１本にまとめて表している）。アークに付された記号Ａ、Ｂ、Ｃ、Ｄ、Ｅは路線名を表す。この他に、路線の各アークには、上り／下りのフラグ、平均所要時間等が付されている。又、図３では、Ｘ駅とＹ駅の間を破線のアークで示し、徒歩１３分の位置にあるとしている。
【００２５】
路線間の乗り換えには、同じ駅で乗り換える場合と、異なる駅間を移動して乗り換える場合とがある。同じ駅での乗り換えについては、駅をクリーク化する。「クリーク」とは、与えられたグラフに含まれる複数の点（ノード）からなる完全部分グラフのことである。「クリーク化」とは、一つの駅を、その駅に接続する路線数に相当する複数のノードとして表すことである。クリーク化された駅の複数のノード間にはアークを張って乗り換え時間を付す。図４は、Ｘ駅、Ｙ駅をクリーク化した例である。Ｘ駅は、Ａ路線のＸ駅（Ａ）、Ｂ路線のＸ駅（Ｂ）、Ｃ路線のＸ駅（Ｃ）からなる３点完全グラフ（三角形）にクリーク化されており、ノード間の乗り換え時間はすべて３分となっている。又、Ｙ駅は、Ｄ路線のＹ駅（Ｄ）、Ｅ路線のＹ駅（Ｅ）からなる２点完全グラフにクリーク化されており、ノード間の乗り換え時間は２分となっている。クリーク内のノードを「クリーク駅」と呼び、クリーク駅間のアークを「路線変更アーク」と呼ぶ。異なる駅間での徒歩による乗り換えについては、新たに「徒歩アーク」を設ける。路線変更アークも徒歩アークも徒歩による移動であるが、便宜上、区別して用いる。図４において、太線は路線変更アークを、破線は徒歩アークを表す。徒歩アークは、Ｘ駅とＹ駅のクリーク駅のすべてのペアに対して張られる。徒歩アーク又は路線変更アークには、それを識別するためのフラグや、移動又は乗り換え時間等が付されている。以下において、この移動又は乗り換え時間を「重み」と呼ぶ。
【００２６】
又、本来の駅とクリーク駅を区別するために、本来の駅を本来駅と呼ぶことにする。例えば、Ｘ駅やＹ駅は本来駅であり、Ｘ駅（Ａ）、Ｘ駅（Ｂ）、Ｘ駅（Ｃ）はクリーク駅である。Ｘ駅は複数のクリーク駅としてネットワークに残る。
【００２７】
（第１の実施の形態）
第１の実施の形態では、駅をノードに持ち、駅間の路線及び徒歩乗り換えをアークで表現するネットワークにおいて、一つの駅に複数の路線が乗り入れている場合、それらの路線に対応する駅をすべて同等に扱うことができる経路探索方法について説明する。
【００２８】
本発明の第１の実施の形態に係る経路探索装置は、図２に示すように、処理制御装置（ＣＰＵ）５に入力装置１１、出力装置１２、データ記憶装置１３、一時記憶装置１４、プログラム記憶装置１５、最短パス木記憶装置２５、複数パス記憶装置２６、複数経路記憶装置２７が接続されている。ＣＰＵ５は、ネットワークを作成するネットワーク作成モジュール５ａ、検索条件及び検索に必要なデータを読み込むデータ読み込みモジュール５ｂ、路線変更アークの重みを変更する重み変更モジュール５ｃ、最短パス木の作成を行う最短パス木作成モジュール５ｄ、最短パス木をもとに複数の最短パスを探索する複数パス探索モジュール５ｅ、複数の最短パスに対して路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるパス短縮モジュール５ｆ、複数の最短経路に対して時間を割り当てる時間割当モジュール５ｇ、複数の最短経路に対して料金を計算する料金計算モジュール５ｈ、優先基準に基づき、上位複数の経路を選択して表示する表示モジュール５ｉを備える。以下の経路探索の説明においては、Ｋ通りの最短経路を求めることを前提とする。
【００２９】
ネットワーク作成モジュール５ａは、路線図や駅間の所要時間等のデータをもとに上述したクリーク化したネットワークを作成する。データ読み込みモジュール５ｂは、入力装置１１から入力された検索条件を読み込み、ネットワークデータ、時刻表データ、料金データ等の必要なデータをデータ記憶装置１３から読み込む。このとき、検索条件である乗車駅名と下車駅名に対して、それらの本来駅番号をそれぞれ求める。乗車駅あるいは下車駅がクリーク化されている場合は、クリーク駅の中の代表クリーク駅の番号を求める。クリーク内の他のクリーク駅の番号は、代表クリーク駅の番号に続く連番であるとする。乗車駅あるいは下車駅がクリーク化されていない場合は、本来駅を代表クリーク駅とみなす。
【００３０】
重み変更モジュール５ｃは、検索条件である乗車駅あるいは下車駅がクリークをなす場合、ネットワーク上で、乗車駅あるいは下車駅の路線変更アークの重みをすべて０にする。これによって、乗車駅あるいは下車駅のクリーク内での移動が重み０で済むため、クリーク内の任意のクリーク駅を、実質的な乗車駅あるいは下車駅と見なすことができる。乗車駅あるいは下車駅の路線変更アークの重みを０にしないと、乗車駅あるいは下車駅のクリーク内での移動に正の重みがかかるため、代表クリーク駅以外のクリーク駅が不利になり、代表クリーク駅と同等に扱えない。又、ユーザによっては、乗車駅で乗車する路線名や、下車駅で下車する路線名を指定したい場合がある。例えば、乗車駅において出発地に最も近いホームから出ている路線を使いたい、あるいは下車駅において目的地に最も近い路線のホームで下車したい、あるいは乗車駅あるいは下車駅で人と待ち合わせる約束をしていたりという場合が考えられる。このように乗車路線あるいは下車路線を指定する場合は、乗車駅あるいは下車駅のクリーク内のアークの重みをすべて実質的に無限大とみなせる極大値（例えば、最も遠く離れた出発地点（乗車駅）と目的地点（下車駅）間の平均的な移動時間（所要時間）の２桁程度以上大きな値）にする。又、指定された路線名のクリーク駅に接続する徒歩アークの重みも極大値にする。そして、乗車駅で乗車する路線名が指定された場合は、その路線名のクリーク駅を乗車駅の代表クリーク駅とみなし、下車駅で下車する路線名が指定された場合は、その路線名のクリーク駅を下車駅の代表クリーク駅とみなし、乗車駅の代表クリーク駅から下車駅の代表クリーク駅に至る第１〜Ｋ最短パスを求める。その探索過程において、重みが極大値のアークは実際には使われることはないので、乗車駅あるいは下車駅では、ユーザが指定した路線名のアークが使われることになる。
【００３１】
最短パス木作成モジュール５ｄは、ダイクストラ（Ｄｉｊｋｓｔｒａ）法等を用いて、最短パス木の作成を行う。そして、作成した最短パス木を最短パス木記憶装置２５に保存する。複数パス探索モジュール５ｅは、マーチンのアルゴリズム等を用いて、乗車駅の代表クリーク駅から下車駅の代表クリーク駅に至る第１〜Ｋ最短パスを求める。そして、探索した複数最短パスを複数パス記憶装置２６に保存する。
【００３２】
パス短縮モジュール５ｆは、上記のようにして得られた第１〜Ｋ最短パスに対して、路線変更アークをすべて除去し、更に連続する同一路線名のアークをすべて短縮する。例えば、Ｊ駅からＮ駅までを検索した際、第ｉ最短パスとして、「Ｊ駅；Ｈ路線；Ｋ駅；Ｈ路線；Ｌ駅（乗り換え）；Ｉ路線；Ｍ駅；Ｉ路線；Ｎ駅」が検索されたとする。路線変更アークと連続する同一路線名のアークを短縮して、「Ｊ駅；Ｈ路線；Ｌ駅；Ｉ路線；Ｎ駅」が求められる。このように得られたパスを「経路」と呼ぶ。又、以下の説明において、第ｉ最短パスに対応するものを第ｉ経路と呼ぶ。求められた最短経路は、複数経路記憶装置２７に保存される。
【００３３】
時間割当モジュール５ｇは、求められた第１〜Ｋ経路に対して、時刻表データ等により、乗車駅、下車駅、乗換駅等における時間を割り当てる。料金計算モジュール５ｈは、求められた第１〜Ｋ経路に対して、料金データ等により、料金を計算する。表示モジュール５ｉは、時刻と料金が割当てられた経路の中から、所要時間等の優先基準に基づき、上位複数の経路を選択して、出力装置１２あるいはインターネット上のＷｅｂページ等に表示する。
【００３４】
入力装置１１は、キーボード、マウス等の機器を指す。入力装置１１から入力操作が行われると対応するキー情報がＣＰＵ５に伝達される。出力装置１２は、モニタなどの画面を指し、液晶表示装置（ＬＣＤ）、発光ダイオード（ＬＥＤ）パネル、エレクトロルミネッセンス（ＥＬ）パネル等が使用可能である。データ記憶装置１３は、ネットワークデータや時刻表データ、料金データ等を保存する。一時記憶装置１４は、ＣＰＵ５における演算において、計算途中や解析途中のデータを一時的に保存する。プログラム記憶装置１５は、重み変更や最短パスの作成、検索などをＣＰＵ５に実行させるためのプログラムを保存する。最短パス木記憶装置２５は、最短パス木作成モジュール５ｄが作成した最短パス木を保存する。複数パス記憶装置２６は、複数パス探索モジュール５ｅが探索した複数パスを保存する。複数経路記憶装置２７は、パス短縮モジュール５ｆが求めた複数経路を保存する。
【００３５】
次に、本発明の第１の実施の形態に係る経路探索方法について、図１及び図２を用いて説明する。
【００３６】
（イ）まず、経路探索を行う前提として、図１のステップＳ１０１において、複数の駅をそれぞれノードで、複数の駅間の接続を複数のアークで表現し、複数の駅の一部のノードがクリーク化されたネットワークの作成を行う。作成されたネットワークはデータ記憶装置１３に保存される。ネットワークは、別の装置で予め作成され、データ記憶保存装置１３に保存されていても良い。次に、ステップＳ１０２において、入力装置１１等を用いて入力された乗車駅、下車駅、出発・到着時刻等の検索条件を読み込む。ステップＳ１０３において、ネットワークデータや時刻表データ、料金データ等の必要なデータをデータ記憶装置１３から読み込む。
【００３７】
（ロ）次に、ステップＳ１０４において、乗車駅あるいは下車駅のクリーク内の路線変更アークの重みの変更を行う。乗車駅あるいは下車駅がクリークをなす場合は、乗車駅あるいは下車駅のクリーク内のアークの重みをすべて０にする。乗車駅で乗車する路線名や下車駅で下車する路線名を指定する場合は、乗車駅あるいは下車駅のクリーク内のアークの重みをすべて実質的に無限大とみなせる極大値にする。又、指定された路線名のクリーク駅に接続する徒歩アークの重みも極大値にする。
【００３８】
（ハ）ステップＳ１０５において、ダイクストラ法等を用いて、入力された検索条件に基づき、ネットワーク上で乗車駅の代表クリーク駅から下車駅の代表クリーク駅までの最短パスに関わる最短パス木の作成を行う。作成された最短パス木は、最短パス木記憶装置２５に保存される。そして、ステップＳ１０６において、マーチンのアルゴリズム等を用いて、最短パス木記憶装置２５から読み出された最短パス木をもとに乗車駅の代表クリーク駅から下車駅の代表クリーク駅に至る第１〜Ｋ最短パスの検索を行う。得られた第１〜Ｋ最短パスは、複数パス記憶装置２６に保存される。そして、ステップＳ１０７において、第１〜Ｋ最短パスを短縮して第１〜Ｋ経路を得る。具体的には、第１〜Ｋ最短パスそれぞれに対して、路線変更アークをすべて除去し、更に連続する同一路線名のアークをすべて短縮する。求められた複数経路は、複数経路記憶装置２７に保存される。
【００３９】
（ニ）次に、ステップＳ１０８において、第１〜Ｋ経路それぞれに対して時刻表データを照らしあわせながら時間割り当てを行い、ステップＳ１０９において、料金データに基づき、料金を計算する。時刻と料金が割り当てられた第１〜Ｋ経路の中から、所要時間等の優先基準に基づき、ステップＳ１１０において、上位複数の経路を選択して出力装置１２に出力（表示）する。
【００４０】
尚、上記の経路探索を実行した後で、再度、乗車駅あるいは下車駅を変更して経路探索を行う場合は、乗車駅あるいは下車駅の路線変更アークの重みを初期値に戻す処理を行う。
【００４１】
この経路探索方法を適用した具体例として、乗車駅がＳ駅で下車駅がＴ駅を指定したとする。この場合、第１経路として「Ｓ駅；Ａ路線；Ｔ駅」が、第２経路として「Ｓ駅；Ｂ路線；Ｕ駅；Ｃ路線；Ｖ駅；Ｄ路線；Ｔ駅」が、第３経路として「Ｓ駅；Ｅ路線；Ｗ駅；Ｄ路線；Ｔ駅」が得られる。たとえＳ駅の代表クリーク駅がＥ路線のノードであっても、Ｓ駅のＡ路線やＢ路線のノードも同等に扱われる。Ｓ駅でＥ路線からＡ路線への乗り換え時間が３分であっても、０分として扱われるため、Ａ路線が不利になることはない。下車駅のＴ駅についても同様である。
【００４２】
第１の実施形態に係る経路探索方法によると、駅をノードに持ち、駅間の路線及び徒歩乗り換えをアークで表現するネットワークにおいて、乗車駅あるいは下車駅のクリーク駅を同等に扱うことにより、効率的な検索を行うことができる。又、乗車駅あるいは下車駅で利用したい路線名を指定することも可能となる。
【００４３】
（第２の実施の形態）
第２の実施の形態では、駅をノードに持ち、駅間の路線及び徒歩乗り換えをアークで表現するネットワークにおいて、一部の路線変更アークを禁止アークとして予めネットワーク上から削除しておくことにより、互いに似通った経路が頻繁に出力されることがなく、効率的な検索を行うことができる経路探索方法について説明する。
【００４４】
本発明の第２の実施の形態に係る経路探索装置は、図５に示すように、処理制御装置（ＣＰＵ）５に入力装置１１、出力装置１２、データ記憶装置１３、一時記憶装置１４、プログラム記憶装置１５、最短パス木記憶装置２５、複数パス記憶装置２６、複数経路記憶装置２７が接続されている。ＣＰＵ５は、ネットワークを作成するネットワーク作成モジュール５ａ、検索条件及び検索に必要なデータを読み込むデータ読み込みモジュール５ｂ、路線変更アークの重みを変更する重み変更モジュール５ｃ、最短パス木の作成を行う最短パス木作成モジュール５ｄ、最短パス木をもとに複数の最短パスを探索する複数パス探索モジュール５ｅ、複数の最短パスに対して路線変更アークの除去及び連続した同一路線名のアークを短縮を行い、複数の最短経路を求めるパス短縮モジュール５ｆ、複数の最短経路に対して時間を割り当てる時間割当モジュール５ｇ、複数の最短経路に対して料金を計算する料金計算モジュール５ｈ、優先基準に基づき、上位複数の経路を選択して表示する表示モジュール５ｉ、削除された路線変更アークを復活する禁止アーク復活モジュール５ｊを備える。以下の説明においては、Ｋ通りの最短経路を求めることとする。
【００４５】
ネットワーク作成モジュール５ａは、禁止アークを設定したネットワークを作成する。例えば、ＪＲ山手線とＪＲ京浜東北線のように一部並走する路線があると、それらの路線間での様々な乗り換えパターンが可能となり、その結果、互いに似通った経路が頻繁に出力される可能性がある。それを避けるために、路線変更アークの一部を予めネットワーク上から削除する処理を行う。そのように削除した路線変更アークを禁止アークと呼ぶ。
【００４６】
禁止アーク復活モジュール５ｊは、検索条件である乗車駅あるいは下車駅がクリークをなす場合、その乗車駅あるいは下車駅の禁止アークを復活させる。
【００４７】
データ読み込みモジュール５ｂ、重み変更モジュール５ｃ、最短パス木作成モジュール５ｄ、複数パス探索モジュール５ｅ、パス短縮モジュール５ｆ、時間割当モジュール５ｇ、料金計算モジュール５ｈ、表示モジュール５ｉ、入力装置１１、出力装置１２、データ記憶装置１３、一時記憶装置１４、プログラム記憶装置１５、最短パス木記憶装置２５、複数パス記憶装置２６、複数経路記憶装置２７は第１の実施の形態と同様であるので、ここでは説明を省略する。
【００４８】
次に、本発明の第２の実施の形態に係る経路探索方法について、図６を用いて説明する。
【００４９】
（イ）まず、経路探索を行う前提として、ステップＳ２０１において、駅をノードに持ち、駅間の路線及び徒歩乗り換えをアークで表現するネットワークの作成を行う。このとき、一部並走する異なる路線がある場合は、それらの路線間の路線変更アークの一部を予め削除したネットワークを作成する。即ち、路線変更アークの一部を禁止アークとして削除したネットワークを作成する。次に、ステップＳ２０２及びＳ２０３は、図１のステップＳ１０２及びＳ１０３と同様であるのでここでは説明を省略する。
【００５０】
（ロ）次に、ステップＳ２０４において、検索条件である乗車駅あるいは下車駅がクリークをなす場合、その乗車駅あるいは下車駅の禁止アークを復活させる。
【００５１】
（ハ）次に、ステップＳ２０５において、乗車駅あるいは下車駅のクリーク内の路線変更アークの重みの変更を行う。乗車駅あるいは下車駅がクリークをなす場合は、乗車駅あるいは下車駅のクリーク内のアークの重みをすべて０にする。乗車駅あるいは下車駅の禁止アークは復活しており、又、乗車駅あるいは下車駅のクリーク内での移動が重み０で済むため、クリーク内の任意のクリーク駅を、実質的な乗車駅あるいは下車駅と見なすことができる。更に、乗車駅で乗車する路線名や下車駅で下車する路線名を指定する場合は、乗車駅あるいは下車駅のクリーク内のアークの重みをすべて実質的に無限大とみなせる極大値にする。又、指定された路線名のクリーク駅に接続する徒歩アークの重みも極大値にする。乗車駅あるいは下車駅の禁止アークは復活しており、その探索過程において、重みが極大値のアークは実際には使われることはないので、乗車駅あるいは下車駅では、ユーザが指定した路線名のアークが使われることになる。
【００５２】
（ニ）ステップＳ２０６〜Ｓ２１１は、図１のステップＳ１０５〜Ｓ１１０と同様であるのでここでは説明を省略する。
【００５３】
尚、上記の経路探索を実行した後で、再度、乗車駅あるいは下車駅を変更して経路探索を行う場合は、乗車駅あるいは下車駅の路線変更アークの重みを初期値に戻す処理と共に、復活させた禁止アークを元に戻す（つまり再び削除する）処理を行う。
【００５４】
第２の実施の形態に係る経路探索方法によると、一部の路線変更アークを禁止アークとして予めネットワーク上から削除しておくことにより、互いに似通った経路が頻繁に出力されることがなく、効率的な検索を行うことができる。又、乗車駅あるいは下車駅のクリーク内に禁止アークがあっても、乗車駅あるいは下車駅のクリーク駅を同等に扱うことができる。
【００５５】
（第３の実施の形態）
第１〜Ｋ最短パスを求めるアルゴリズムとして、例えばマーチンのアルゴリズムを用いる場合、まず乗車駅の代表クリーク駅から下車駅の代表クリーク駅に至る最短パスに関わる最短パス木を求める。乗車駅あるいは下車駅がクリーク化されていて、且つそのクリーク内の路線変更アークの重みをすべて０として扱う場合、最短パス木の上に重み０の路線変更アークが連続したり、あるいは徒歩アークと重み０の路線変更アークが連続する場合がある。このような連続部分があると、第２最短パス以降の最短パスを求める際に、等価なパスを重複して探索するという無駄が生じる場合がある。
【００５６】
第３の実施の形態では、駅をノードに持ち、駅間の路線及び徒歩乗り換えをアークで表現するネットワークにおいて、乗車駅あるいは下車駅のクリークに関わる最短パス木のアークを張り替えることにより、効率的な検索を行うことができる経路探索方法について説明する。
【００５７】
本発明の第３の実施の形態に係る経路探索装置は、図７に示すように、処理制御装置（ＣＰＵ）５に入力装置１１、出力装置１２、データ記憶装置１３、一時記憶装置１４、プログラム記憶装置１５、最短パス木記憶装置２５、複数パス記憶装置２６、複数経路記憶装置２７が接続されている。ＣＰＵ５は、ネットワークを作成するネットワーク作成モジュール５ａ、検索条件及び検索に必要なデータを読み込むデータ読み込みモジュール５ｂ、路線変更アークの重みを変更する重み変更モジュール５ｃ、最短パス木の作成を行う最短パス木作成モジュール５ｄ、最短パス木をもとに複数の最短パスを探索する複数パス探索モジュール５ｅ、複数の最短パスに対して路線変更アークの除去及び連続した同一路線名のアークを短縮を行い、複数の最短経路を求めるパス短縮モジュール５ｆ、複数の最短経路に対して時間を割り当てる時間割当モジュール５ｇ、複数の最短経路に対して料金を計算する料金計算モジュール５ｈ、優先基準に基づき、上位複数の経路を選択して表示する表示モジュール５ｉ、最短パス木のアークを張り替えるアーク張り替えモジュール５ｋを備える。以下の説明においては、Ｋ通りの最短経路を求めることとする。
【００５８】
アーク張り替えモジュール５ｋは、乗車駅あるいは下車駅のクリークに関わる最短パス木のアークを張り替える。最短パス木の上に重み０の路線変更アークが連続したり、徒歩アークと重み０の路線変更アークが連続する場合に、この連続したアークを一つの路線変更アーク又は一つの徒歩アークに置き換える。この例として、図９では、下車駅のクリークに関わる最短パス木のアークの張り替えを行っている。クリーク内には、複数のクリーク駅２０、２１ａ、２１ｂ、２１ｃ、２１ｄが存在するが、その中の一つを代表クリーク駅２０とする。実線はクリーク駅間を結ぶ路線変更アーク、破線は徒歩アークを表す。又、太線の矢印が最短パス木のアークを表している。図９（ａ）では、最短パス木の路線変更アークを、代表クリーク駅２０を終点に持つアークになるように張り替えている。図９（ｂ）では、代表クリーク駅２０ではないクリーク駅２１ａへの最短パス木の徒歩アークを、代表クリーク駅２０への最短パス木の徒歩アークへ張り替えている。
【００５９】
又、図１０では、乗車駅のクリークに関わる最短パス木のアークの張り替えを行っている。クリーク内には、複数のクリーク駅２１ａ、２１ｂ、２１ｃ、２１ｄ、２１ｅが存在する。図９と同様に、実線はクリーク駅間を結ぶ路線変更アーク、破線は徒歩アークを表す。又、太線の矢印が最短パス木のアークを表している。図１０（ａ）では、最短パス木のアークが、乗車駅のクリーク内で２以上の路線変更アークを通過している際は、１の路線変更アークを通過するように、各クリーク駅からパスの終点へのクリーク駅へと張り替えている。ここでは、クリーク駅２１ｂからクリーク駅２１ｃへ張られた最短パス木のアークは、クリーク駅２１ｂからクリーク駅２１ｅへ張り替えられ、クリーク駅２１ｃからクリーク駅２１ｄへ張られた最短パス木のアークは、クリーク駅２１ｃからクリーク駅２１ｅへ張り替えられている。図１０（ｂ）及び図１０（ｃ）は、最短パス木の徒歩アークと最短パス木の路線変更アークが連続している場合のアークの張り替え操作を示している。図１０（ｂ）では、最短パス木の徒歩アークから最短パス木の路線変更アークへと連続している際に、最短パス木の徒歩アークを、その終点が、路線変更アークの終点２１ｂと一致するように張り替えている。図１０（ｃ）では、最短パス木の路線変更アークから最短パス木の徒歩アークへと連続している際に、最短パス木の乗り換えアークを、クリーク駅２１ｂを始点とする最短パス木の徒歩アークの終点へ張り替えている（最短パス木の乗り換えアークが１本減り、最短パス木の徒歩アークが１本増える）。
【００６０】
ネットワーク作成モジュール５ａ、データ読み込みモジュール５ｂ、重み変更モジュール５ｃ、最短パス木作成モジュール５ｄ、複数パス探索モジュール５ｅ、パス短縮モジュール５ｆ、時間割当モジュール５ｇ、料金計算モジュール５ｈ、表示モジュール５ｉ、入力装置１１、出力装置１２、データ記憶装置１３、一時記憶装置１４、プログラム記憶装置１５、最短パス木記憶装置２５、複数パス記憶装置２６、複数経路記憶装置２７は第１の実施の形態と同様であるので、ここでは説明を省略する。
【００６１】
次に、本発明の第３の実施の形態に係る経路探索方法について、図８を用いて説明する。
【００６２】
（イ）まず、ステップＳ３０１〜Ｓ３０５は、図１のステップＳ１０１〜Ｓ１０５と同様であるのでここでは説明を省略する。
【００６３】
（ロ）次に、ステップＳ３０６において、乗車駅あるいは下車駅のクリークに関わる最短パス木のアークを張り替える。最短パス木の上に重み０の路線変更アークが連続したり、徒歩アークと重み０の路線変更アークが連続する場合に、この連続したアークを一つの路線変更アーク又は一つの徒歩アークに置き換える。
【００６４】
（ハ）ステップＳ３０７〜Ｓ３１１は、図１のステップＳ１０６〜Ｓ１１０と同様であるのでここでは説明を省略する。
【００６５】
尚、上記の経路探索を実行した後で、再度、乗車駅あるいは下車駅を変更して経路探索を行う場合は、乗車駅あるいは下車駅の路線変更アークの重みを初期値に戻す処理を行う。
【００６６】
第３の実施の形態に係る経路探索方法によると、乗車駅あるいは下車駅のクリーク内の最短パス木のアークの張り替え操作によって、効率的な検索を行うことができる。
【００６７】
（その他の実施の形態）
本発明は上記の実施の形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例及び運用技術が明らかとなろう。
【００６８】
例えば、本発明の第１〜第３の実施の形態において、電車路線の駅を例として説明したが、これに限らず、空港やバス停を出発地、目的地として経路探索を行っても構わない。
【００６９】
又、本発明の第１〜第３の実施の形態において、求められた第１〜Ｋ経路の中から上位複数の経路を選択して経路探索装置の出力装置１２に出力すると説明したが、本発明に係る経路探索装置をインターネットに接続し、検索結果の経路をＷｅｂページ等に表示しても構わない。
【００７０】
又、本発明の第１〜第３の実施の形態に係る経路探索装置は、データ記憶装置１３、一時記憶装置１４、プログラム記憶装置１５、最短パス木記憶装置２５、複数パス木億装置２６、複数経路記憶装置２７を分けて備えると記述したが、これらの記憶装置を一つの記憶装置で代用しても構わない。同様に、ＣＰＵ５内の各モジュールは、一つのＣＰＵ５内にあると記述したが、複数のＣＰＵ５に分けて備えられていても良い。その際、複数のＣＰＵ５間でデータのやりとりが行えるようにバスなどで装置間を接続する。
【００７１】
このように、本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。従って、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【００７２】
【発明の効果】
本発明によれば、無駄な検索を省き、効率的な検索を行うことができる経路探索方法及び経路探索プログラムを提供することができる。
【図面の簡単な説明】
【図１】第１の実施の形態に係る経路検索方法のフローチャートである。
【図２】第１の実施に形態に係る経路探索装置のブロック図である。
【図３】第１〜第３の実施の形態に係る経路探索方法のネットワークの一例である。
【図４】第１〜第３の実施の形態に係る経路探索方法のクリーク化されたネットワークの一例である。
【図５】第２の実施の形態に係る経路探索装置のブロック図である。
【図６】第２の実施の形態に係る経路探索方法のフローチャートである。
【図７】第３の実施の形態に係る経路探索装置のブロック図である。
【図８】第３の実施の形態に係る経路探索方法のフローチャートである。
【図９】第３の実施の形態に係る経路探索方法において、下車駅のクリークに関わる最短パス木のアークの張り替えの一例である。
【図１０】第３の実施の形態に係る経路探索方法において、乗車駅のクリークに関わる最短パス木のアークの張り替えの一例である。
【符号の説明】
５　ＣＰＵ（処理制御装置）
５ａ　ネットワーク作成モジュール
５ｂ　データ読み込みモジュール
５ｃ　重み変更モジュール
５ｄ　最短パス木作成モジュール
５ｅ　複数パス探索モジュール
５ｆ　パス短縮モジュール
５ｇ　時間割当モジュール
５ｈ　料金計算モジュール
５ｉ　表示モジュール
５ｊ　禁止アーク復活モジュール
５ｋ　アーク張り替えモジュール
１１　入力装置
１２　出力装置
１３　データ記憶装置
１４　一時記憶装置
１５　プログラム記憶装置
２０　代表クリーク駅
２１ａ、２１ｂ、２１ｃ、２１ｄ、２１ｅ　クリーク駅
２５　最短パス木記憶装置
２６　複数パス記憶装置
２７　複数経路記憶装置
【図１】
2004061298.tif 000003
【図２】
2004061298.tif 000004
【図３】
2004061298.tif 000005
【図４】
2004061298.tif 000006
【図５】
2004061298.tif 000007
【図６】
2004061298.tif 000008
【図７】
2004061298.tif 000009
【図８】
2004061298.tif 000010
【図９】
2004061298.tif 000011
【図１０】
2004061298.tif 000012