(57)【要約】【課題】経路数パラメータの推奨値テーブルを活用することによって、平均処理速度を高速化し、経路品質も向上させることができる経路探索方法を提供する。【解決手段】経路数パラメータのデフォルト値を配列Ｒにセットし（Ｓ３０）、ユーザの検索条件が設定条件を満すか否かをチェックする（Ｓ３１）。設定条件を全て満す場合は推奨値テーブルの推奨値パラメータを読み込み（Ｓ３２）、検索する乗車駅、下車駅が存在するかどうか２分探索する（Ｓ３３）。一方設定条件を満さない場合はそのまま経路探索アルゴリズムを実行する。更に、推奨値テーブルに検索する乗車駅、下車駅が存在した場合には該当する推奨値パラメータの値を配列Ｒに上書き（Ｓ３４）して、この配列Ｒを基に経路探索のアルゴリズムが実行される。一方、乗車駅、下車駅が存在しない場合には経路探索アルゴリズム（Ｓ３５）を実行する。【選択図】      図６
2004291825.tif 000002
【特許請求の範囲】
【請求項１】
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、
入力された検索条件に基づき、前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
予め前記ネットワーク上で求めたい経路数の推奨値を規定した推奨値テーブルに基づき、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップと
を含むことを特徴とする経路探索方法。
【請求項２】
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、
予め前記ネットワーク上で求めたい経路数の推奨値を規定した推奨値テーブルに基づき、前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
前記複数の最短パスにおいて使用頻度に基づいて、該使用頻度が高いアークの重みを変更し、再度複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップと、
を含むことを特徴とする経路探索方法。
【請求項３】
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、
予め前記ネットワーク上で求めたい経路数の推奨値を規定した推奨値テーブルに基づき、前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
徒歩アークと路線変更アークに重みを加算した後、複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップと
を含むことを特徴とする経路探索方法。
【請求項４】
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、
入力された検索条件が、予め準備された設定条件と一致するか否か条件判定するステップと、
前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記条件判定に基づいて、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップと、
を含むことを特徴とする経路探索方法。
【請求項５】
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、
入力された検索条件が、予め準備された設定条件と一致するか否か条件判定するステップと、
前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記条件判定に基づき、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
前記複数の最短パスにおいて使用頻度に基づいて、該使用頻度が高いアークの重みを変更し、再度複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップと、
を含むことを特徴とする経路探索方法。
【請求項６】
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、
入力された検索条件が、予め準備された設定条件と一致するか否か条件判定するステップと、
前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記条件判定に基づき、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
徒歩アークと路線変更アークに重みを加算した後、複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップと、
を含むことを特徴とする経路探索方法。
【請求項７】
前記条件判定するステップで前記設定条件と一致したとき、更に推奨値テーブル記憶装置から推奨値テーブルを読み込むステップと、
前記推奨値テーブルに前記出発地点及び目的地点が存在するか否か地点判定するステップと、
を含むことを特徴とする請求項４乃至請求項６記載の経路探索方法。
【請求項８】
前記条件判定するステップで前記設定条件と一致しないとき、最短パスの検索を行うステップは、前記最短パス木をもとに前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パスの検索を行うことを特徴とする請求項４乃至請求項６記載の経路探索方法。
【請求項９】
前記地点判定するステップで前記推奨値テーブルに前記出発地点及び目的地点が存在するとき、前記最短パスの検索を行うステップは、前記推奨値テーブルの該当する推奨値パラメータに基づいて、前記ネットワークを利用して出発地点から目的地点までの複数の最短パスの検索を行うことを特徴とする請求項７記載の経路探索方法。
【請求項１０】
前記地点判定するステップで前記推奨値テーブルに前記出発地点及び目的地点が存在しないとき、前記最短パス木の作成を行うステップは、入力された検索条件に基づいて前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うことを特徴とする請求項７記載の経路探索方法。
【請求項１１】
前記設定条件は、推奨値テーブルを設定する際の条件であることを特徴とする請求項４乃至請求項６記載の経路探索方法。
【請求項１２】
更に、優先基準に基づき、前記複数の最短経路の一部を選択して出力装置に出力するステップを含むことを特徴とする請求項４乃至請求項６記載の経路探索方法。
【請求項１３】
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークを作成するネットワーク作成手段と、
入力された検索条件が、予め準備された設定条件と一致するか否か判定する条件判定手段と、
前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木を作成する最短パス木作成手段と、
前記条件判定手段の結果に基づいて、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスを検索する最短パス検索手段と、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるパス短縮手段と、
を含むことを特徴とする経路探索装置。
【請求項１４】
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークを作成するネットワーク作成手段と、
入力された検索条件が、予め準備された設定条件と一致するか否か判定する条件判定手段と、
前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木を作成する最短パス木作成手段と、
前記条件判定手段の結果に基づき、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスを検索する最短パス検索手段と、
前記複数の最短パスにおいて使用頻度に基づいて、該使用頻度が高いアークの重みを変更し、再度複数の最短パスの検索を行う再探索手段と、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるパス短縮手段と、
を含むことを特徴とする経路探索装置。
【請求項１５】
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークを作成するネットワーク作成手段と、
入力された検索条件が、予め準備された設定条件と一致するか否か判定する条件判定手段と、
前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木を作成する最短パス木作成手段と、
前記条件判定手段の結果に基づき、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスを検索する最短パス検索手段と、
徒歩アークと路線変更アークに重みを加算した後、再度複数の最短パスの検索を行う再探索手段と、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるパス短縮手段と、
を含むことを特徴とする経路探索装置。
【請求項１６】
前記条件判定手段で前記設定条件と一致したとき、更に推奨値テーブル記憶装置から推奨値テーブルを読み込み、前記推奨値テーブルに前記出発地点及び目的地点が存在するか否か判定する地点判定手段を含むことを特徴とする請求項１３乃至請求項１５記載の経路探索装置。
【請求項１７】
前記条件判定手段で前記設定条件と一致しないとき、最短パス木作成手段は、入力された検索条件に基づいて前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うことを特徴とする請求項１３乃至請求項１５記載の経路探索装置。
【請求項１８】
前記地点判定手段で前記推奨値テーブルに前記出発地点及び目的地点が存在するとき、前記最短パス木作成手段は、前記推奨値テーブルの該当する推奨値パラメータに基づいて、前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うことを特徴とする請求項１６記載の経路探索装置。
【請求項１９】
前記地点判定手段で前記推奨値テーブルに前記出発地点及び目的地点が存在しないとき、前記最短パス木作成手段は、入力された検索条件に基づいて前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うことを特徴とする請求項１６記載の経路探索装置。
【請求項２０】
前記設定条件は、推奨値テーブルを設定する際の条件であることを特徴とする請求項１３乃至請求項１５記載の経路探索装置。
【請求項２１】
更に、優先基準に基づき、前記複数の最短経路の一部を選択して出力装置に出力する出力手段を含むことを特徴とする請求項１３乃至請求項１５記載の経路探索装置。
【請求項２２】
コンピュータ上で実行可能なプログラムであって、
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、
入力された検索条件が、予め準備された設定条件と一致するか否か条件判定するステップと、
前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記条件判定に基づいて、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップとを実行することを特徴とする経路探索プログラム。
【請求項２３】
コンピュータ上で実行可能なプログラムであって、
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、
入力された検索条件が、予め準備された設定条件と一致するか否か条件判定するステップと、
前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記条件判定に基づき、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
前記複数の最短パスにおいて使用頻度に基づいて、該使用頻度が高いアークの重みを変更し、再度複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップとを実行することを特徴とする経路探索プログラム。
【請求項２４】
コンピュータ上で実行可能なプログラムであって、
複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、
入力された検索条件が、予め準備された設定条件と一致するか否か条件判定するステップと、
前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記条件判定に基づき、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
徒歩アークと路線変更アークに重みを加算した後、複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップとを実行することを特徴とする経路探索プログラム。
【請求項２５】
少なくとも出発地点、目的地点を複数ファイルにしたサンプルを読み込むステップと、
データ記憶装置に保存されている、複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化され、アークのグループ毎に切り替えられるネットワークを読み込むステップと、
検索する時分を変更するステップと、
前記サンプルに基づいて、前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、
前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、
前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップと、
優先基準に基づき、前記複数の最短経路を選択するステップと、
前記選択した最短経路を求めるために最低限必要な経路数を前記ネットワーク毎にベクトルとした推奨値パラメータと、前記推奨値パラメータを求めるのにかかる平均処理時間とを求めるステップと、
前記推奨値パラメータに基づいて、再度前記最短パス木の作成を行うステップ、
最短パスの検索を行うステップ、及び複数の最短経路を求めるステップとを行い、これにかかる推奨値処理時間を求めるステップと、
前記推奨値処理時間が前記平均処理時間よりも所定時間以上小さいときに、前記出発地点、前記目的地点及び前記推奨値パラメータを推奨値テーブルに保存するステップと
を含むことを特徴として推奨値テーブル作成方法。
【請求項２６】
前記推奨値パラメータは、経路数の代わりに、実際に有効な経路番号そのものを推奨値テーブルに登録しておくことを特徴とする請求項２５記載の推奨値テーブル作成方法。
【請求項２７】
一定期間の過去の利用履歴情報からテーブル化した前記サンプルを抽出し、再度推奨値パラメータを求めて推奨値テーブルを更新する推奨値更新手段を有することを特徴とする請求項２５の推奨値テーブル作成方法。
【請求項２８】
前記推奨値テーブルは、請求項２５で作成された推奨値テーブルであることを特徴とする請求項１乃至請求項３記載の経路探索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータを用いて出発地と目的地間の経路を１つまたは複数検索できる経路探索装置、例えば列車の乗り換え案内装置、に関するものである。
【０００２】
【従来の技術】
従来、コンピュータを用いて出発地、目的地、出発希望時刻等を入力すると、出発地から目的地に至る１つまたは複数の経路を表示（案内）するソフトウェアが存在する。例えば、列車の乗り換え案内の場合、経路は、出発駅、乗換駅、目的駅、利用路線または利用列車等からなり、更に、出発駅での発時刻、乗換駅での発／着時刻、目的駅での着時刻や、所要時間、料金等も表示されることが多い。（例えば、特許文献１参照。）
【０００３】
このような検索サービスは、パッケージソフト、あるいはサービス提供会社のＷｅｂページ上で行われている。（例えば、特許文献２参照。）
この経路探索は、通常、各ノード間をアークで接続し、各アークに重み（コスト）が割り振られたグラフであるネットワークをもとに考える。ネットワークにおいて、出発ノードｓから目的ノードｔへのパスを考えるとき、ｓからｔへの第ｉ番目に短いパスをｓからｔへの第ｉ最短パスと言う。第１最短パスがいわゆる最短パスである。最短パスは、良く知られているようにダイクストラ法によって高速に求められる。第２最短パス以降の最短パスを求めるアルゴリズムについても古くから研究され、種々の効率良いアルゴリズムが提案されている。
【０００４】
第１〜Ｋ最短パスを求めるアルゴリズムとしては、マーチンのアルゴリズムが知られている。（例えば、非特許文献１参照。）第１〜Ｋ最短パスを求める場合、ループ（閉路）を許す場合と許さない場合とがある。ループを許すというのは、同じノードを２度以上通るような冗長なパスも第ｉ最短パスとして採用しようというものである。ループを許した方が問題としては扱いやすいが、一般にはループを許さない場合の方が実用的である。マーチンのアルゴリズムは、ループを許さない場合のアルゴリズムの１つである。
【０００５】
探索方法としては、２分探索が知られている。（例えば、非特許文献２参照）ｎ個の要素を持つ配列があったときにｎ／２番目のデータと探索対象のデータとを比較し、等しければそれが求めるデータとなる。探索対象のデータの方が小さければ、配列の前半部分に目的のデータがあり（探索対象を配列の前半部分にして探索を行う。）そうでなければ、配列の後半部分にある。（探索対象を配列の後半部分にして探索を行う。）
【０００６】
よって、１回の比較により検索範囲を半分に縮めることができる。その半分になった区間について同様なことを繰り返すといった考え方の探索法である。
【特許文献１】
特開平１１−９１５６９  号公報（図４、図６）
【特許文献２】
特開２００１−３３１６０４公報（第５頁、図４）
【非特許文献１】
Ｅ．Ｑ．Ｖ．  Ｍａｒｔｉｎｓ，  Ｍ．Ｍ．Ｂ．  Ｐａｓｃｏａｌ，  ａｎｄ  Ｊ．Ｌ．Ｅ．  Ｓａｎｔｏｓ，  Ａｎ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｒａｎｋｉｎｇ  ｌｏｏｐｌｅｓｓ  ｐａｔｈｓ，  Ｒｅｓｅａｒｃｈ  Ｒｅｐｏｒｔ，  Ｕｎｉｖ．  ｄｅ  Ｃｏｉｍｂｒａ，  Ｄｅｃ．  １９９９．
【０００７】
【非特許文献２】
石畑清著「アルゴリズムとデータ構造」岩波書店，  １９８９
【０００８】
【発明が解決しようとする課題】
しかし、駅等（空港、バス停も含む）をノードに持ち、駅間の路線を飛行機、新幹線、有料特急、普通列車等によりグループ分けしたアークで表現するネットワーク上で、各グループのアーク群を取捨選択しながら仮想的に複数のネットワーク上で複数ずつ（経路数パラメータに相当）の経路を求ようとする際、それぞれのサンプル（乗車駅、下車駅の組合せ）に対して経路数パラメータを幾つに設定するのが適切かを判断するのが困難であった。そのため、どのサンプルに対しても一律同じ経路数パラメータを用いることになり、処理時間が全体的に増大してしまうという問題があった。
【０００９】
よって、上記の問題を鑑み、本発明は、アクセス数が多い、あるいは処理時間のかかる複数のサンプルに対して、経路数パラメータの推奨値テーブルを活用することによって、平均処理速度を高速化し、経路品質も向上させることができる経路探索装置、経路探索方法及び推奨値テーブル作成方法を提供することを目的とする。
【００１０】
【課題を解決するための手段】
上記目的を達成するために、本発明は、複数の地点をそれぞれノードで、隣り合う前記地点間の路線を複数のアークで表現し、前記ノードの一部がクリーク化されたネットワークをデータ記憶装置から読み込むステップと、予め前記ネットワーク上で求めたい経路数の推奨値を求めた推奨値テーブルに基づき、前記ネットワーク上で出発地点から目的地点までの最短パスに関わる最短パス木の作成を行うステップと、前記最短パス木をもとに、前記ネットワークを利用して、前記出発地点から前記目的地点までの複数の最短パスの検索を行うステップと、前記複数の最短パスに対して、路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるステップとを含むことを特徴とする。
【００１１】
上記によりアクセス数が多い、あるいは処理時間のかかる複数のサンプルに対して、経路数パラメータの推奨値テーブルを活用することによって、平均処理速度を高速化し、経路品質も向上させることができる。
【００１２】
【発明の実施の形態】
図面を参照して、本発明の実施の形態を説明する。
本発明の実施の形態に係る経路探索方法として、まず、複数の「ノード」とノード間を接続する「アーク」からなるネットワークについて説明する。経路探索で用いるネットワークは、基本的には、駅を「ノード」とみなし、線路上で隣り合う駅間に「アーク」を設けて作成する。「アーク」には駅間の移動時間が付されており、これを「重み」という。この例として、Ｘ駅とＹ駅のネットワークを図１に示す。ここでは、Ｘ駅、Ｙ駅がノードとなり、記号Ａ、Ｂ、Ｃ、Ｄ、Ｅを付した実線で示す両端矢印がアークを表す（上り／下りの２本のアークを１本にまとめて表している）。アークに付された記号Ａ、Ｂ、Ｃ、Ｄ、Ｅは路線名を表す。この他に路線の各アークには、上り／下りのフラグ、平均所要時間等が付されている。また、図１ではＸ駅とＹ駅の間を破線のアークで示し、徒歩１３分の位置にあるとしている。
【００１３】
路線間の乗り換えには、同じ駅で乗り換える場合と、異なる駅間を移動して乗り換える場合とがある。同じ駅での乗り換えについては、駅をクリーク化する。「クリーク」とは、与えられたグラフに含まれる複数の点（ノード）からなる完全部分グラフのことである。「クリーク化」とは、一つの駅を、その駅に接続する路線数に相当するノードで表し、ノード間に乗り換えのためのアークを設けることである。クリーク化された複数のノード間にはアークを張って乗り換え時間を付す。図２は、Ｘ駅、Ｙ駅をクリーク化した例である。Ｘ駅は、Ａ路線のＸ駅（Ａ）、Ｂ路線のＸ駅（Ｂ）、Ｃ路線のＸ駅（Ｃ）からなる３点完全グラフ（三角形）にクリーク化されており、ノード間の乗り換え時間はすべて３分となっている。また、Ｙ駅は、Ｄ路線のＹ駅（Ｄ）、Ｅ路線のＹ駅（Ｅ）からなる２点完全グラフにクリーク化されており、ノード間の乗り換え時間は２分となっている。クリーク内のノードを「クリーク駅」と呼び、クリーク駅間のアークを「路線変更アーク」と呼ぶ。列車の場合の路線変更とは、路線を乗り換えることを指す。
【００１４】
異なる駅間での徒歩による乗り換えについては、新たに「徒歩アーク」を設ける。路線変更アークも徒歩アークも徒歩による移動であるが、便宜上、区別して用いる。図２において、太線は路線変更アークを、破線は徒歩アークを表す。徒歩アークは、Ｘ駅とＹ駅からなるクリーク駅のすべてのペアに対して張られる。徒歩アークまたは路線変更アークには、それを識別するためのフラグや、移動又は乗り換え時間等が付されている。
【００１５】
また、本来の駅とクリーク駅を区別するために、本来の駅を本来駅と呼ぶことにする。例えば、Ｘ駅やＹ駅は本来駅であり、Ｘ駅（Ａ）、Ｘ駅（Ｂ）、Ｘ駅（Ｃ）はクリーク駅である。Ｘ駅は複数のクリーク駅としてネットワークに残る。
【００１６】
本発明の実施の形態に係る経路探索装置は、図３に示すように処理制御装置（ＣＰＵ）５に入力装置１１、出力装置１２、データ記憶装置１３、一時記憶装置１４、プログラム記憶装置１５、最短パス木記憶装置２０、複数パス記憶装置２１、複数経路記憶装置２２、推奨値テーブル記憶装置２３が接続されている。ＣＰＵ５は、アークのグループ毎に分けられた複数のネットワークを作成するネットワーク作成モジュール５ａ、検索条件及び検索に必要なデータを読み込むデータ読み込みモジュール５ｂ、最短パス木の作成を行う最短パス木作成モジュール５ｃ、最短パス木をもとに、複数のネットワークを用いてバランス良く複数の最短パスを探索する複数パス探索モジュール５ｄ、複数の最短パスに対して路線変更アークの除去及び連続した同一路線名のアークの短縮を行い、複数の最短経路を求めるパス短縮モジュール５ｅ、複数の最短経路に対して時間を割り当てる時間割当モジュール５ｆ、複数の最短経路に対して料金を計算する料金計算モジュール５ｇ、優先基準に基づき、複数のネットワークから求められた上位複数の経路をバランス良く選択して表示する表示モジュール５ｈを備える。以下の経路探索の説明においては、ｋ通りの最短経路を求めることを前提とする。
【００１７】
ネットワーク作成モジュール５ａは、路線図や駅間の所要時間等のデータをもとに、上述したクリーク化したネットワークを作成する。このとき、作成されるネットワークは、アークのグループ毎に分けられた複数のネットワークである。
【００１８】
ネットワークＡとは、全ての駅をノードに持ち、駅間の全ての路線または徒歩乗り換えをアークに持つネットワークを指す。例えば、飛行機、新幹線、有料特急、その他の列車のアーク、徒歩アーク、路線変更アークを含むネットワークをネットワークＡとする。ネットワークＡを用いて経路探索を行うと、飛行機や新幹線を利用した経路ばかり求まってしまうことがある。これは、経路探索のアルゴリズムは基本的にコスト（平均所要時間）の小さい経路から順に求めるからである。しかし、たとえ乗車駅と下車駅が遠く離れていても、別料金の不要な快速や各駅停車で行く経路、あるいは在来線特急だけで行くような経路が要求されることも多い。
【００１９】
ネットワークＡには、上述したように飛行機、新幹線、有料特急のアークも含まれる。このような飛行機、新幹線、有料特急、普通列車を利用した多様な経路をバランスよく求めるために、まず、予め各アークに次のようなグループ番号を付す。
【００２０】
３：飛行機のアーク
２：新幹線のアーク
１：有料特急のアーク
０：その他の列車のアーク、徒歩アーク、路線変更アーク
そして、ネットワークＡから各グループのアークを大きい順に順次除いたネットワークＡ２、Ａ１、Ａ０を、次のように定義する。
Ａ２：  グループ番号０，１，２  のアークからなるネットワーク
Ａ１：  グループ番号０，１のアークからなるネットワーク
Ａ０：  グループ番号０のアークからなるネットワーク
ネットワークの各アークに付されたアーク番号（例えば、通し番号等）や、各ノードに接続するアークのリストにおけるアークの並び順を、上記のグループ番号に関して昇順に並べておけば、ネットワーク  Ａ，Ａ２，Ａ１、Ａ０の間の切り替えは容易に実現できる。即ち、Ａ２、Ａ１、Ａ０のそれぞれはＡの一部分として容易に（仮想的に）実現できる。
【００２１】
例えばＡ２はＡからグループ番号３のアークをすべて除去したものであるが、上述したように、グループ番号が切り替わる箇所を記憶してあるので、Ａ２はＡから容易に切り替えが実現できる。ネットワーク作成モジュール５ａは、上記のようなネットワークＡを作成し、Ａ、Ａ２、Ａ１、Ａ０間のグループ番号が切り替わる箇所を記憶する。
【００２２】
データ読み込みモジュール５ｂは、入力装置１１から入力された検索条件を読み込み、ネットワーク、時刻表データ、料金データ等の必要なデータをデータ記憶装置１３から読み込む。このとき、検索条件である乗車駅名と下車駅名に対して、それらの本来駅番号をそれぞれ求める。乗車駅あるいは下車駅がクリーク化されている場合は、クリーク駅内の代表クリーク駅の番号を求める。クリーク内の他のクリーク駅の番号は、代表クリーク駅の番号に続く連番であるとする。乗車駅あるいは下車駅がクリーク化されていない場合は、本来駅を代表クリーク駅とみなす。
【００２３】
最短パス木作成モジュール５ｃは、ダイクストラ法等を用いて、最短パス木の作成を行う。複数パス探索モジュール５ｄは、マーチンのアルゴリズム等を用いて、乗車駅の代表クリーク駅から下車駅の代表クリーク駅に至る第１〜ｋ最短パスを求める。このとき、ネットワークＡ、Ａ２、Ａ１、Ａ０を用いて、飛行機、新幹線、有料特急、普通列車等を利用したパス群をバランスよく求める。即ち、飛行機を利用するパス、新幹線を利用するパス、有料特急を利用するパス、普通列車等を利用するパスをそれぞれ複数本ずつ求める。これらのパス群の中にはたまたま同一のパスが含まれることもあるので、それらを除去し、最終的に第１〜ｋ最短パスを得る。
【００２４】
パス短縮モジュール５ｅは、上記のようにして得られた第１〜ｋ最短パスに対して、路線変更アークをすべて除去し、更に連続する同一路線名のアークをすべて短縮する。例えば、Ｆ駅からＪ駅までを検索した際、第ｉ最短パスとして、「Ｆ駅；Ｌ路線；Ｇ駅；Ｌ路線；Ｈ駅（乗り換え）；Ｏ路線；Ｉ駅；Ｏ路線；Ｊ駅」が検索されたとする。路線変更アークと連続する同一路線名のアークを短縮して、「Ｆ駅；Ｌ路線；Ｈ駅；Ｏ路線；Ｊ駅」が求められる。このように得られたパスを「経路」と呼ぶ。又、以下の説明において、第ｉ最短パスに対応するものを第ｉ経路と呼ぶ。
【００２５】
時間割当モジュール５ｆは、求められた第１〜ｋ経路に対して、時刻表データ等により、乗車駅、下車駅、乗換駅等における時間を割り当てる。料金計算モジュール５ｇは、求められた第１〜ｋ経路に対して、料金データ等により、料金を計算する。表示モジュール５ｈは、時刻と料金が割り当てられた経路の中から、所要時間、料金等の優先基準に基づき、上位複数の経路を選択して、出力装置１２あるいはインターネット上のＷｅｂページ等に表示する。上位複数の経路を選択する際には、ネットワークＡ、Ａ２、Ａ１、Ａ０を用いて求められた経路それぞれから、経路を選択する。
【００２６】
入力装置１１は、キーボード、マウス等の機器を指す。入力装置１１から入力操作が行われると対応するキー情報がＣＰＵ５に伝達される。出力装置１２は、モニタなどの画面を指し、液晶表示装置（ＬＣＤ）、発光ダイオード（ＬＥＤ）パネル、エレクトロルミネッセンス（ＥＬ）パネル等が使用可能である。データ記憶装置１３は、ネットワークや時刻表データ、料金データ等を保存する。一時記憶装置１４は、ＣＰＵ５における演算において、計算途中や解析途中のデータを一時的に保存する。プログラム記憶装置１５は、ネットワークの作成や最短パス木の作成、複数最短パスの検索などをＣＰＵ５に実行させるためのプログラムを保存する。最短パス木記憶装置２０は、最短パス木作成モジュール５ｃが作成した最短パス木を保存する。複数パス記憶装置２１は、複数パス探索モジュール５ｄが探索した複数パスを保存する。複数経路記憶装置２２は、パス短縮モジュール５ｅが求めた複数経路を保存する。推奨値テーブル記憶装置２３は、ネットワーク上で求めた経路数の推奨値を求めた推奨値テーブルを保存する。
【００２７】
次に、実施の形態で用いる経路探索アルゴリズムについて説明する。
図４に経路探索アルゴリズムの概要を示す。Ｓ１０では、入力装置１１から入力された乗車駅、下車駅、出発・到着時刻等の検索条件を読み込む。Ｓ１１では、ネットワークや時刻表データ、料金データ等の必要なデータをデータ記憶装置１３から読み込む。Ｓ１２では、ダイクストラ法等を用いて乗車駅から下車駅に至る最短パスに関わる最短パス木を作成する。作成された最短パス木は、最短パス木記憶装置２０に保存される。Ｓ１３では、ネットワーク上で、最短パス木記憶装置２０から読み出された最短パス木をもとに、マーチンのアルゴリズム等を用いて乗車駅のノードから下車駅のノードに至る複数の最短パス（１〜ｋ最短パス）を探索する。探索された複数の最短パスは、複数パス記憶装置２１に保存される。Ｓ１４とＳ１５では、ネットワークの条件を変えて、更に複数の最短パスを再探索する。Ｓ１２〜Ｓ１５の一連の処理は、ネットワーク  Ａ，Ａ２，Ａ１、Ａ０のそれぞれに対して適用される。
【００２８】
つまり、まずＡに対してＳ１３〜Ｓ１５を実行し、次にＡ２に対してＳ１３〜Ｓ１５を実行し、次にＡ１に対してＳ１３〜Ｓ１５を実行し、最後にＡ０に対してＳ１３〜Ｓ１５を実行する。Ｓ１６では、それぞれの最短パスを短縮し、経路に変換する。求められた複数の経路は複数経路記憶装置２２に保存される。Ｓ１７では各経路に対して時刻表を照らしあわせながら時間割り当てを行い、Ｓ１８では料金を計算する。Ｓ１９では、時刻と料金が割当てられた経路の中から、所要時間等の優先基準に基づき、上位複数の経路を選択して出力装置１２に出力する。上位複数の経路を選択する際には、ネットワークＡ、Ａ２、Ａ１、Ａ０を用いて求められた経路それぞれから、バランス良く経路を選択する。
【００２９】
ところで、上述した経路探索アルゴリズムは、平均所要時間に関して小さい経路から順に探索する。経路の良さの評価基準には、平均所要時間の他に料金や乗り換え回数等もあるため、できるだけ多様な代替経路も求める必要がある。
【００３０】
多様な経路を求める１つの方法として、一旦ネットワークＡ（Ａ２，Ａ１，Ａ０についても同様）上でパス群を求めた後で、徒歩アークと乗り換えアークの全てに所定の時間を加算して、更に１つまたは複数のパスを求めるという処理を行う。これをここでは「再探索１」とする。再探索１によって乗り換え回数の少ないパスが求まりやすくなる。
【００３１】
多様な経路を求める他の方法として、通常探索（Ｓ１３）と再探索１（Ｓ１４）で求めたパス群において使用頻度がある閾値より大きいアークの重みを例えば一律ｎ％（例えばｎ＝５０）一時的に増加させ、再度ネットワークＡ（Ａ２，Ａ１，Ａ０についても同様）上で複数のパスを求めるという処理を行う。これをここでは「再探索２」とする。
【００３２】
上述したように、ネットワークＡ，Ａ２，Ａ１，Ａ０のそれぞれに対して再探索１及び再探索２を行うので、実質的に計１２のネットワークを順に用い、それぞれのネットワーク上で複数ずつ（経路数パラメータ）の経路を求めている。これらのネットワークに番号０，１・・・・・１１を付す。
【００３３】
上記では再探索が２つの例を示したが、これに限ることなく、例えば乗り入れのある乗り換えアークの重みのみをそのままとして再探索する手段を加えて、３つ以上再探索するようにしても適用できる。
【００３４】
各ネットワークの意味と経路数パラメータの例を以下表１に列挙する。
【００３５】
【表１】
2004291825.tif 000003
【００３６】
原則として、上記のパラメータはどのサンプルに対しても一律同じ値を用いる。サンプルによっては、上記よりも少ない経路を求めるだけで十分な場合もあるし、あるいは或ネットワーク上での探索が全く無駄になる場合もある。
【００３７】
なお、上記の例の場合は、経路数パラメータの割り振り方の特徴（大小関係）から、幾つかのネットワーク上の探索を省略（スキップ）することができる。即ち、Ａ上の探索（ネットワークＮｏ．０〜２上の探索）で得られた経路群の中に飛行機を用いた経路がなくて且つ新幹線を用いた経路がある場合は、Ａ２上の探索は冗長なのでネットワークＮｏ．３〜５上の探索はスキップすることができる。これは、ネットワークＮｏ．３〜５に対する経路数がそれぞれネットワークＮｏ．０〜２に対する経路数よりも小さいためである。
【００３８】
また、Ａ上の探索で得られた経路群の中に飛行機や新幹線を用いた経路がなくて且つ有料特急を用いた経路がある場合は、Ａ２とＡ１上の探索は冗長なのでネットワークＮｏ．３〜８上の探索はスキップすることができる。このようなスキップの処理は経路探索アルゴリズムの中に含まれているとしてよい。
【００３９】
ここで、利用者が多く利用する検索条件について注目する。例えば、殆どのユーザは、乗車駅、下車駅、時分以外はデフォルトの検索条件を用いる場合が多く、また検索日は圧倒的に平日が多いと仮定する。
【００４０】
デフォルトの検索条件というのは、例えば、早く到着する経路を優先して求める、航空会社の指定は無し、近距離においては別料金が必要な列車はなるべく使用しない、経由駅は指定しない等である。この仮定は１つの例であり、実際は乗り換え案内エンジン（乗り換え案内サービスのシステム）の使用状況に応じて（仮定内容を）決定する。
【００４１】
このような仮定の下で、アクセス数の多いサンプル群に対して「乗車駅番号、下車駅番号、経路数の推奨値パラメータ（計１２）のリスト」を求めてテーブル（以下、推奨値テーブルと呼ぶ）で保持しておく。
【００４２】
そして経路探索の初期段階で、まず乗車駅、下車駅、時分以外のユーザの検索条件がデフォルト設定か否か、及び検索日が平日か否かをチェックする。デフォルト設定で且つ平日の場合は、更にユーザ指定の乗車駅と下車駅が推奨値テーブルに存在するか否かをチェックする。このチェックは例えば、２分探索等によって行なうことができる。推奨値テーブルに存在する場合は、その経路数パラメータをセットする。
【００４３】
以下、推奨値テーブルの作成について詳細に説明する。
図５は、推奨値テーブルの作成に関するフローチャートである。Ｓ２０では、サンプル群として例えばある一週間に採取したアクセス数の多いサンプル群（サンプル数＝Ｎとする）を読み込む。Ｓ２１では、１番目のサンプルを参照するためにｋに１をセットする。Ｓ２２では、サンプルＮｏ．ｋに対して検索時分を種々変更して経路探索アルゴリズムを繰り返し実行し、推奨値パラメータと平均ＣＰＵ時間ｃ１を求める。Ｓ２３では、同サンプルに対して、Ｓ２２で求めた推奨値パラメータを用いて乗り換え案内エンジンを再実行しＣＰＵ時間ｃ２を求める。Ｓ２４では、ｃ２がｃ１よりも所定時間以上小さければ、サンプルＮｏ．ｋの乗車、下車駅番号と推奨値パラメータを推奨値テーブルＴとして推奨値テーブル記憶装置２３に保存する。Ｓ２５では、ｋがサンプル数に達しているか判断し、ｋ≠Ｎ（Ｎｏ）であればＳ２６で次のサンプルの処理に移るためにｋに１を加算する。更に加算されたサンプルｋについて再度Ｓ２２〜Ｓ２４の処理が繰り返される。Ｓ２７では、推奨値テーブルＴを乗車駅番号に関して昇順ソートし、乗車駅番号が同じものについては下車駅番号について昇順ソートする。Ｓ２８では、推奨値テーブルＴを出力する。一方、ｋ＝Ｎ（Ｙｅｓ）であれば、全てのサンプルＮに対する処理が終わったため、推奨値テーブルの作成処理を終了する。
【００４４】
アクセス数の多いサンプル群は、例えば表２のように「サンプル番号、乗車駅名、下車駅名」を列挙したファイルとして予め用意しておく。
【００４５】
【表２】
2004291825.tif 000004
【００４６】
また、例えば乗車駅、下車駅以外の検索条件のデフォルト値または初期値を書いた、表３のようなファイルも予め用意しておく（右側の欄は説明用のコメントである）。
【００４７】
【表３】
2004291825.tif 000005
【００４８】
ここで、発着指定というのは、例えばユーザの検索時分が１０：００の場合、１０：００以降に出発する列車を検索したいのか、１０：００以前に到着する列車を検索したいのかを指定する項目である。
【００４９】
検索結果の優先順が「時刻」の場合は、発指定ならば下車駅に早く到着する経路を優先して案内し、着指定ならば乗車駅を遅く出発する経路を優先して案内する。「料金」の場合は、料金の安い経路を優先して案内する。「乗り換え回数」の場合は、乗り換え回数の少ない経路を優先して案内する。
【００５０】
これらの２つのファイルを用いてＳ２２とＳ２３の乗り換え案内エンジンが実行される。Ｓ２２では、検索年月日を平日に設定し、検索時分を例えば１１：００から１５：００まで３０分おきに変更して、乗り換え案内エンジンを繰り返し実行する。
【００５１】
乗り換え案内エンジンでは、最終的に出力されるデフォルト  ５件以下の経路が、それぞれ経路探索プロセスにおいてどのネットワークで何番目に得られた経路なのかを調べ、その順番の最大値の組合せ（１２桁のベクトル）を保存する。
【００５２】
例えば、
第１経路：Ａ上の通常探索の８番目
第２経路：Ａ上の再探索１の３番目
第３経路：Ａ０上の通常探索の１７番目
第４経路：Ａ０上の通常探索の５５番目
第５経路：Ａ０上の再探索２の２３番目
の場合は（８，  ３，  ０，  ０，  ０，  ０，  ０，  ０，  ０，  ５５，  ０，  ２３）となる。
乗車駅ｓと下車駅ｔに対して、検索時分を種々変更して実行した場合の、この１２桁のベクトルの各成分の最大値からなるベクトルを、（ｓ，ｔ）に対する推奨値パラメータと呼ぶ。
【００５３】
例えば、ａ駅→ｃ駅の場合１１：００〜１５：００発指定で３０分おきに経路数パラメータを採取したとき、表４のようにとなったとする。
【００５４】
【表４】
2004291825.tif 000006
【００５５】
この場合、これらの各成分の最大値を取ると、推奨値パラメータとして（１，  ２，  ０，  ２７，  ０，  ０，  １，  ０，  ０，  ０，  ０，  ０）が得られる。
またそれぞれの実行におけるＣＰＵ時間の平均として、例えば１２００ｍｓという値が得られたとする。なお、より精度の高い推奨値パラメータを得るためには、例えば計測間隔３０分から１分にするといった具合に計測間隔をもっと狭くしてデータを採取すればよい。
【００５６】
Ｓ２３では、推奨値パラメータを用いた場合のＣＰＵ時間だけを知りたいので、検索年月日を平日に設定して検索時分を例えば推奨値パラメータと同じ値であった１１：００発を指定にし、１回だけ実行する。そのときのＣＰＵ時間が例えば６５０ｍｓであったとする。
【００５７】
Ｓ２４における所定時間を例えば５００ｍｓとすると、６５０ｍｓ（＝ｃ２）は１２００ｍｓ（＝ｃ１）よりも５００ｍｓ以上小さいので、サンプルＮｏ．ｋ（ｋ＝１）「ａ駅→ｃ駅」は推奨値テーブルへの登録対象となり、乗車／下車駅番号と推奨値パラメータ（１，  ２，  ０，  ２７，  ０，  ０，  １，  ０，  ０，０，  ０，  ０）が推奨値テーブルＴに保存される。Ｓ２７では、推奨値テーブルＴを乗車駅番号に関して昇順ソートし、乗車駅番号が同じものについては下車駅番号について昇順ソートする。Ｓ２８では、推奨値テーブルＴを出力する。
【００５８】
図６に推奨値テーブルＴを用いた経路検索について説明する。
Ｓ３０では、経路数パラメータのデフォルト値をｍ個（ここでは１２個）の経路数からなる配列Ｒにセットする。Ｓ３１ではユーザの検索条件が表３のような設定条件（デフォルト値）を満すか否かをチェックする。設定条件を全て満す場合はＳ３２に進む。一方設定条件を満さない場合はＳ３５に進み、上述したＳ１１〜Ｓ１９の経路探索アルゴリズムを実行する。Ｓ３２では推奨値テーブルＴの推奨値パラメータを読み込み、Ｓ３３で検索する乗車駅、下車駅が推奨値テーブルに存在するかどうか２分探索する。Ｓ３３で推奨値テーブルに検索する乗車駅、下車駅が存在した場合にはＳ３４に進む。一方、推奨値テーブルに検索する乗車駅、下車駅が存在しない場合にはＳ３５に進み、上述したＳ１１〜Ｓ１９の経路探索アルゴリズムを実行する。Ｓ３４では、推奨値テーブルの該当する推奨値パラメータの値を配列Ｒに上書きする。但し、再探索２の推奨値が非零の場合は、それと同じネットワーク（Ａ，Ａ２，Ａ１，ｏｒＡ０）上の通常探索と再探索１の経路数パラメータはデフォルト値のままにしておく。再探索２は、通常探索と再探索１で得られたパス群に依存するためである。
【００５９】
例えば、ネットワークＮｏ．８の推奨値が非零の場合は、Ｎｏ．６とＮｏ．７の経路数はそれぞれ３０と１０のままにしておく。最後に、Ｓ３５では、配列Ｒを基に経路探索のアルゴリズムのＳ１１〜Ｓ１９が実行される。
【００６０】
このように、実施の形態に係る経路探索では、アクセス数が多い、あるいは処理時間のかかる複数のサンプルに対して、経路数パラメータの推奨値テーブルを活用することによって、平均処理速度を高速化させることができる。
【００６１】
上記実施の形態では、発着指定＝０（発指定）をデフォルトとしたが、もし、着指定での検索も非常に多いという傾向がある場合は次のように処理すればよい。
推奨値テーブルを作成する際に、発指定で時分を種々変更して実行した後で、着指定に変更して再度時分を種々変更して実行し、データを採取する。そして推奨値テーブルを活用する際は、上記のＳ３１の「発着指定＝０（発指定）」という項目についてはチェックしないように変更する。
【００６２】
経路探索に関わるパラメータには、経路数以外にも、例えば再探索１で徒歩アークと乗り換えアークに加算する「所定時間」や、再探索２における「使用頻度がある閾値以上」と「重みのアップ率」などがある。これらのパラメータについてもテーブル化し、それを活用することもできる。
【００６３】
上記実施の形態では、ネットワーク（Ｎｏ．０〜１１）ごとに、有効な経路番号の最大値をテーブルに保存して活用するというものであったが、その代わりに、実際に有効な経路番号そのものをテーブルに登録するようにしてもよい。このように経路番号そのものをテーブルに登録しておくと、更に効率的である。その場合、Ｓ１７以降では有効な経路番号の経路に対してのみ時間割り当て等の処理が行われるため、処理が高速になる。
【００６４】
上述した他の実施の形態は、経路数のデフォルト設定値の範囲内での最良値、あるいはその範囲内での（個々の）有効な経路番号をテーブルに登録するというものであり、高速化に役立つものである。テーブルに登録されたサンプルに対する処理時間が大幅に短縮されるため、全体のサンプルに対する平均処理時間も短縮する。
【００６５】
推奨値テーブルはその他に「出て欲しい経路を出すために必要な」経路数あるいは経路番号を登録するために使用してもよい。この場合はデフォルト設定よりも大きな経路数あるいは経路番号を設定することになるので、経路品質の向上には有効である。
【００６６】
具体的には、所望の経路の乗車駅／下車駅に対して、経路数のデフォルト設定値を例えば一律３倍して乗り換え案内エンジンを１回実行し、経路探索（Ｓ１６の結果）において所望の経路が求まるか否かを調べる。求まった場合は、その経路が得られたネットワーク番号と経路番号を推奨値テーブルに反映する。
【００６７】
推奨値テーブルＴを用いた経路探索は上述のＳ３０〜Ｓ３５と同様であるが、Ｓ３４の「再探索２の推奨値が非零の場合」の通常探索と再探索１の経路数には、本来のデフォルト値を３倍した値をセットする。
【００６８】
また、上記で述べた推奨値テーブルは、オンライン化してもよい。つまりある一定期間ごとにその内容を自動更新することによって、更に効果を発揮する。アクセスの多いサンプル群は日々変化しうるものである。そこで、推奨値テーブルのそれぞれのサンプルに対して、その推奨値のヒット数（活用回数）を常にカウントして覚えておく。
【００６９】
そして、過去のある一定期間の（例えば１時間または１日間の）利用履歴情報から、アクセス数が多いにも関わらず推奨値テーブルにヒットしなかったサンプルを複数抽出し、それらの（経路数または経路番号の）推奨値を求めて推奨値テーブルに追加登録する。その際、ＣＰＵ時間の減少の割合が大きいものに限って追加登録してもよい。
【００７０】
逆に、推奨値テーブルに登録済みのサンプルの中に、過去のある一定期間に殆んど活用されなかったサンプルがある場合は、それらを推奨値テーブルから削除する。このようにして、推奨値テーブルに常に新しいアクセス情報を反映することによって、ユーザの利用状況の変化に適切に対応していくことができる。
【００７１】
推奨値テーブルの作成には、アクセス数が多いサンプル群、あるいは処理時間のかかるサンプル群等が必要となるが、そのようなサンプル群を予め用意できない場合は、日々のアクセス状況に応じてテーブルを徐々に拡大していってもよい。
【００７２】
また、計算機資源が少なくテーブルを一括して作成することができない場合も、テーブルを徐々に拡大していけばよい。そのような場合、テーブルの拡大とともに検索時間が速くなっていくという効果も見込める。
【００７３】
推奨値テーブルは、全てのユーザに対して同一のものを用いてもよいが、あるグループ単位で、あるいはユーザごとに用意してもよい。例えば、ある会社の従業員を対象に推奨値テーブルを作成して、その会社専用に高速化のサービスを行うことも可能である。あるいは、予めユーザ登録してあるユーザに対しては、年代層や居住地域によってグループ化し、それぞれのグループに適した推奨値テーブルを作成して、高速化のサービスを行うことも可能である。
【００７４】
ユーザごとに推奨値テーブルを作成する場合は、ユーザの検索状況に応じてテーブルを自動更新してもよい（一種の学習機能）。推奨値テーブルはユーザの個人マシンに置いておいてもよい。このようにユーザごとにサービスを行う場合は、ユーザにとっては自分がよく検索するサンプルの検索時間が短くなるという効果がある。あるサンプルが推奨値テーブルに登録されると、そのサンプルがヒットした場合の処理時間が短縮するため、同一のサンプルを頻繁に検索するユーザにとっては、使っているうちにどんどん速くなっていくという効果を実感することができる。
【００７５】
【発明の効果】
本実施形態によれば、アクセス数が多い、あるいは処理時間のかかる複数のサンプルに対して、経路数パラメータの推奨値テーブルを活用することによって、平均処理速度を高速化し、経路品質も向上させることができる。
【図面の簡単な説明】
【図１】実施の形態に係る経路探索方法のネットワークの一例である。
【図２】実施の形態に係る経路探索方法のクリーク化されたネットワークの一例である。
【図３】実施の形態に係る経路探索装置のブロック図である。
【図４】実施の形態に係る経路検索方法のフローチャートである。
【図５】実施の形態に係る推奨値テーブル作成方法のフローチャートである。
【図６】実施の形態に係る推奨値テーブルを用いた経路検索のフローチャートである。
【符号の説明】
５：ＣＰＵ（処理制御装置）
５ａ：ネットワーク作成モジュール
５ｂ：データ読み込みモジュール
５ｃ：最短パス木作成モジュール
５ｄ：複数パス検索モジュール
５ｅ：パス短縮モジュール
５ｆ：時間割当モジュール
５ｇ：料金計算モジュール
５ｈ：表示モジュール
１１：入力装置
１２：出力装置
１３：データ記憶装置
１４：一時記憶装置
１５：プログラム記憶装置
２０：最短パス木記憶装置
２１：複数パス記憶装置
２２：複数経路記憶装置
２３：推奨値テーブル記憶装置
【図１】
2004291825.tif 000007
【図２】
2004291825.tif 000008
【図３】
2004291825.tif 000009
【図４】
2004291825.tif 000010
【図５】
2004291825.tif 000011
【図６】
2004291825.tif 000012