経路探索方法および経路探索プログラムおよび経路探索システム
【課題】 公共交通網において最優秀経路情報の他に複数の最優秀経路情報に次ぐ優秀な代替経路を探索できる経路探索方法および経路探索プログラムを提供する。
【解決手段】 出発駅および到着駅および出発駅から到着駅までの所要時間と距離を格納したリンクテーブルと、リンクテーブルの出発駅を到着駅とするリンクテーブルのレコードの位置を格納するブリッジテーブルを用いて、ダイクストラ法によって最優秀経路情報を生成すると共に、その生成過程で探索した経路をもとに、代替経路を生成すると共に、ＧＡ法によって代替経路を補正し、最優秀経路情報に次いで優秀な代替可能な複数の経路を探索する。
【解決手段】 出発駅および到着駅および出発駅から到着駅までの所要時間と距離を格納したリンクテーブルと、リンクテーブルの出発駅を到着駅とするリンクテーブルのレコードの位置を格納するブリッジテーブルを用いて、ダイクストラ法によって最優秀経路情報を生成すると共に、その生成過程で探索した経路をもとに、代替経路を生成すると共に、ＧＡ法によって代替経路を補正し、最優秀経路情報に次いで優秀な代替可能な複数の経路を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータを用いて公共交通網の出発駅から目的駅までの最適な経路を複数種類探索する方法およびプログラムおよびシステムに係り、特にダイクストラ法によって最優秀経路情報を求めるとともに前記最優秀経路情報を求める過程で使用した通過経路情報を再利用し、遺伝的アルゴリズム（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ、以下ＧＡと略す。）を用いて最優秀経路情報の代替経路を優秀な順に求める経路探索方法および経路探索プログラムおよび経路探索システムに関する。
【背景技術】
【０００２】
一般に従来技術による公共交通網の経路探索方法は、ダイクストラ法が用いられてきた。この方法は通過点に複数の選択できる経路が存在するとき、最優秀経路情報を選択し、その経路を進んで複数の選択できる経路が存在する点に至った場合には再度最優秀な経路を選択し、以下これを繰り返すことにより、全体として最優秀経路情報を探索する技術である。
【０００３】
ここで、公共交通網とは鉄道を始めとする出発時間と到着時間、区間距離、運賃が予め定められている交通手段を言う。
また、最優秀経路情報とは、例えば時間を探索条件とした探索の場合には最短時間の経路をいい、乗換え回数を探索条件とした場合には合計乗換え回数が最少の経路を言い、料金を探索条件とした場合には料金が最低な経路のように、探索条件が最適な経路を言う。
【０００４】
また、特許文献１にはダイクストラ法によって最優秀経路情報を探索した後、前記最優秀経路情報で使用した乗換駅を使用禁止にして、再度ダイクストラ法で最優秀経路情報に次ぐ経路を順次探索する技術が記載されている。
さらに、特許文献２には遺伝的アルゴリズムを利用して最適経路とそれに準ずる複数の代替経路を求めるカーナビゲーションシステムに関する技術が記載されている。
【特許文献１】特開平１１−４４５４７号公報
【特許文献２】特開平９−１７８５００号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
前述の従来技術による公共交通網の経路探索方法には次のような不具合があった。
先ず、ダイクストラ法は高速に最優秀経路情報を求めることが可能であり、広く用いられている。しかし、この方法は最優秀経路情報以外の代替経路を求めることはできないという不具合があった。
【０００６】
これに対し、特許文献１に開示されている技術は、有効な代替経路を探索できない場合がある。
例えば、ダイクストラ法によれば、枕崎から鹿児島中央までの経路を探索した場合、最優秀経路情報として（枕崎）−ＪＲ指宿枕崎線（枕崎−山川）−（山川）−ＪＲ指宿枕崎線（山川−鹿児島中央）−鹿児島中央という、枕崎から山川まで行き、山川で乗換え、鹿児島中央に行くという経路が探索される。
これに対して、特許文献１に開示されている技術に従い、山川での乗換えを経路探索において使用禁止にしてしまうと、有効な代替経路は探索できない。しかし実際には、（枕崎）−ＪＲ指宿枕崎線（枕崎−山川）−（山川）−ＪＲ指宿枕崎線（山川−鹿児島中央）−（南鹿児島）−徒歩−（南鹿児島駅前）−鹿児島市電１系統−（郡元）−鹿児島市電２系統−（鹿児島中央駅前）−徒歩−（鹿児島中央）、というように、山川での乗換え後、南鹿児島で乗り換える経路も存在する。
このように、特許文献１記載の技術では、最優秀経路情報に乗換駅が１つしか存在しない場合、また、乗換駅が存在しない場合には、代替経路を探索できないという不具合が存在する。
【０００７】
また、特許文献２に記載の技術は、カーナビゲーションシステムに広く用いられている。しかし、道路交通網においては運転者が自由に経路を選択することができるのに対し、鉄道網では列車の運行時刻、行き先、乗換駅などを条件として考慮しなければならない。また、カーナビゲーションシステムがＧＰＳを使用して現在位置と目的地から距離や右左折の回数等を基に経路を選択するのに対し、鉄道網においては所要時間を基に経路を選択する場合がある。このため、特許文献２記載の技術を単純に鉄道網に適用することはできないという不具合が存在する。
【０００８】
本発明の目的は、前述の従来技術による不具合を除去することであり、公共交通網において最優秀経路情報の他に複数の最優秀経路情報に次ぐ優秀な代替経路を探索できる経路探索方法および経路探索プログラムおよび経路探索システムを提供することである。
【課題を解決するための手段】
【０００９】
前記目的を達成するために請求項１記載の発明は、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムであって、
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、
該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、
該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、
該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを備えることを特徴とする。
【００１０】
また、請求項２記載の発明は、前記経路探索システムにおいて、前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込み、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクＩＤを読み込み、該接続リンクＩＤを含むレコードをリンクテーブルから検索することを特徴とする。
【００１１】
また、請求項３記載の発明は、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索方法であって、
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを設け、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行い、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出し、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求めることを特徴とする。
【００１２】
また、請求項４記載の発明は、前記経路探索方法において前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込み、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクＩＤを読み込み、該接続リンクＩＤを含むレコードをリンクテーブルから検索することを特徴とする。
【００１３】
また、請求項５記載の発明は、出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部と、前記各構成を制御するコンピュータとを備え、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行う機能と、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出する機能と、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求める機能とを実現させることを特徴とする。
【００１４】
また、請求項６記載の発明は、前記経路探索プログラムにおいて、前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加した請求項５記載の経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込む機能と、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索する機能と、該検索されたレコードに格納された接続リンクＩＤを読み込む機能と、該接続リンクＩＤを含むレコードをリンクテーブルから検索する機能とを実現することを特徴とする。
【発明の効果】
【００１５】
本発明による経路探索方法および経路探索プログラムおよび経路探索システムによれば、出発駅および到着駅および出発駅から到着駅までの所要時間と距離を格納したリンクテーブルと、リンクテーブルの出発駅を到着駅とするリンクテーブルのレコードの位置を格納するブリッジテーブルを予め用意し、これらのテーブルを読み込んで、ダイクストラ法によって最優秀経路情報を生成すると共に、その生成過程で探索した通過経路情報をもとに、生成経路情報を生成すると共に、ＧＡ法によって生成経路情報を補正するように構成したため、従来はダイクストラ法では最優秀経路情報しか導出できなかったのに対し、本願発明においては最優秀経路情報に次いで優秀な代替可能な複数の経路を探索することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明による経路探索方法および経路探索プログラムおよび経路探索システムの一実施形態を、図面を参照して詳細に説明する。
図１は、本発明の実施形態における経路検索システムの全体構成図である。
図２は、本発明の実施形態における処理のフローチャートである。
図３は、リンクテーブルとブリッジテーブルの例である。
図４は、路線図と停車駅単位のリンクおよび乗換駅単位のリンクの例である。
図５は、経路探索プログラムのフローチャートである。
図６は、路線図の例と通過経路情報の例である。
図７は、経路生成プログラムのフローチャートである。
図８は、経路生成プログラムによって生成された経路の例である。
図９は、遺伝的アルゴリズムによる経路補正プログラムのフローチャートである。
図１０は、経路補正プログラムによる経路分割例である。
図１１は、経路補正プログラムにより分割した経路の合成例である。
図１２は、経路補正プログラムによって補正された結果の例である。
【００１７】
<構成の説明>
本発明の一実施形態による経路探索方法および経路探索プログラムが実施される経路探索システムを、図１を用いて説明する。
本実施形態のシステムは、経路検索システム１００と、ユーザーの保持するコンピュータ３０と、経路探索システム１００とユーザーの保持するコンピュータ３０とを接続する公衆通信回線網２０とを備える。
【００１８】
前記経路検索システム１００は、プログラムが稼動するサーバ１０と、ダイクストラ法によって経路を探索する経路探索部１１と、前記経路探索部１１によって探索した経路から代替経路を生成する経路生成部１２と、前記経路生成部１２によって生成されて経路を遺伝的アルゴリズムによって補正する経路補正部１３と、出発駅から到着駅までの所要時間および距離を格納するリンクテーブル１４と、リンクテーブル１４において到着駅を出発駅とするレコードのＩＤおよび乗換え時間および列車の接続に関する情報である接続情報を格納するブリッジテーブル１５と、経路探索部１１によって使用された通過経路を格納する通過経路情報テーブル１６と、通過経路情報テーブル１６から生成された生成経路情報を格納する生成経路情報テーブル１７を備える。
【００１９】
経路探索部１１は、ダイクストラ法によって最優秀経路情報を求めると共に、その過程で使用した経路を全て通過経路情報テーブル１６に格納する。
経路生成部１２は、前記通過経路情報テーブル１６に格納された通過経路情報から最優秀経路情報に代替可能な生成経路情報を導出し、生成経路情報テーブル１７に格納する。
経路補正部１３は、前記生成経路情報テーブル１７に格納された生成経路情報を補正し、最優秀経路情報についで優秀な複数の代替経路を導出する。
【００２０】
<データの説明>
図３（Ａ）を用いてリンクテーブル１４のデータ構成例を説明する。
リンクテーブル１４は、レコードに一意に定められたリンクＩＤ３０１と、出発駅名を表す出発駅３０２と、到着駅名を表す到着駅３０３と、特急や急行といった列車の種別を表す列車３０４と、ブリッジテーブル１５内のブリッジＩＤ３０８を示す開始ブリッジＩＤ３０５と、出発駅から到着駅までかかる時間を表す所要時間３０６と、出発駅から到着駅までの距離を表す距離３０７とを備え、具体的なデータの例は、リンクＩＤ３０１が「１」、出発駅３０２が「ｎ（１）」、到着駅３０３が「ｎ（２）」、開始ブリッジＩＤ３０５が「１」、所要時間３０６が「ｘ（１）」、距離３０７が「ｄ（１）」である。
ここで、リンクとは出発駅，到着駅，列車，出発駅から到着駅に至るのに必要な所要時間、出発駅から到着駅の距離などを保持したデータを言う。リンクテーブル１４は全ての駅間のリンクを保持している。
【００２１】
図３（Ｂ）を用いてブリッジテーブル１５のデータ構成例を説明する。
ブリッジテーブル１５は、レコードに一意に定められたブリッジＩＤ３０８と、リンクテーブル１４において、あるレコードの到着駅を出発駅とするレコードのリンクＩＤを示す接続リンクＩＤ３０９と、乗換えにかかる時間を表す乗換え時間３１０と、乗換えまたは直通または折返しなど列車の接続に関する情報を表す接続情報３１１とを備え、具体的なデータの例は、ブリッジＩＤ３０８が「１」、接続リンクＩＤ３０９が「１１２」、乗換え時間３１０が「３２」、接続情報が「乗換え」である。
【００２２】
ここで、ブリッジテーブル１５の存在意義を説明する。
経路探索において、あるリンクから接続するリンクがどれなのかを探す場合に、リンクテーブル全体から検索していてはリンクテーブル１４のデータ量は膨大なものであるため時間がかかる。例えば、図３（Ａ）のリンクＩＤが「１」のリンクは到着駅がｎ（２）なので、これに接続するリンクはｎ（２）を出発駅とするリンクであるが、ｎ（２）を出発駅とするリンクはリンクテーブル１４のどこにあるか判らない。この為ｎ（２）を出発駅とするリンクをテーブル全体から探す必要があるが、リンクテーブル１４はレコード数が膨大な量に及ぶため、その中から探すのには時間がかかってしまう。そこで、あるリンクに対して接続するリンク情報を格納したデータを用意する。このデータをブリッジと呼ぶ。リンクにはブリッジの開始ＩＤを格納しておく。また、ブリッジには次に接続するリンクＩＤと、接続にかかる乗換え時間や接続情報を格納しておく。
【００２３】
このように構成することにより、例えば、図３（Ａ）のリンクテーブル１４のリンクＩＤ３０１が「１」のリンクでは、このリンクの開始ブリッジＩＤ３０５は「１」であるから、図３（Ｂ）のブリッジテーブル１５のブリッジＩＤ３０８が「１」のブリッジを参照する。ブリッジＩＤ３０８が「１」のブリッジの接続リンクＩＤ３０９は「１１２」であるから、リンクＩＤ３０１から接続するリンクはリンクＩＤ３０１が「１１２」であることがわかる。また、リンクＩＤ３０１が「１」のリンクから接続するリンク、具体的にはこのリンクの着駅ｎ（２）を出発駅とするリンクは複数存在するので、このリンクと同数だけブリッジも存在する。リンクＩＤ３０１が「２」のリンクの開始ブリッジＩＤ３０５が「５１」であることから、リンクＩＤ３０１が「１」のリンクから接続するリンクは、ブリッジテーブル１５のブリッジＩＤ３０８が「１」から「５０」までのブリッジに接続情報があることがわかる。これらのブリッジを全て参照することにより、接続するリンクを全て取得することができる。
【００２４】
また、取得したリンクの開始ブリッジＩＤ３０５を基に次に接続するリンクＩＤ３０１を取得することを繰り返すことにより、経路のネットワークを探索することができる。
このブリッジを用いることにより、次に接続するリンクを簡単に、かつ高速に取得することができる。また、このブリッジにリンクからリンクへの接続情報を予め持たせることにより、乗換なのか直通なのか等の判定処理を経路探索処理から省くことができ、経路探索の処理効率の向上が図れる。
【００２５】
図４を用いて、リンクテーブル１４のデータ構成例を説明する。
図４（Ａ）のような駅と路線が配置されている場合、図４（Ｂ）の様に停車駅単位でリンクを設定するのではなく、図４（Ｃ）の様に乗換可能駅単位にリンクを設定する。これにより、リンクデータを削減することができ、メモリ使用量の削減、探索対象の現象による処理効率の向上が図れる。出発駅または目的駅が乗換え可能駅ではない場合は、その出発駅または目的駅を乗換駅と仮定し、最寄りの乗換え可能駅までのリンクを生成することにより乗換え可能駅のみの鉄道経路のネットワークにおいて経路探索を行うことができる。
【００２６】
図６を用いて、通過経路情報テーブル１６のデータ構成例を説明する。
図６（Ａ）に経路のネットワークの例を示す。例えば、リンクＩＤが「５４５３」の経路は、Ｂ駅を出発駅とし、その直前の経路はリンクＩＤが「７７７」のものと、「１６７７」のものと「２２４５」がある。この場合の通過経路情報テーブル１６の例として、図６（Ｂ）を示す。通過経路情報テーブル１５のデータ構成例は、各リンクに対し、直前の経路である直前リンクＩＤ６０１と、直前格納位置６０２と、経路評価値６０３とを備え、経路評価値６０３は、所要時間６０４と、乗換え回数６０５と、距離６０６とを備え、具体的なデータの例は、リンクＩＤが「４５５３」の場合、直前リンクＩＤ６０１が「１６６７」、直前格納位置６０２が「３」、所要時間６０４が「７８」、乗換え回数６０５が「２」、距離６０６が「１１４．３ｋｍ」である。
【００２７】
図８を用いて生成経路情報テーブル１７のデータ構成例を説明する。生成経路情報テーブル１７は、生成された生成経路情報を示す経路８０１と、出発駅から目的駅までの所要時間を示す所要時間８０２と、乗換え回数を示す乗換回数８０３と、出発駅から目的駅までの距離を示す距離８０４とを備え、具体的なデータの例は、経路８０１が「Ｓ−Ａ−Ｂ−Ｃ−Ｇ」、所要時間８０２が「２５」、乗換回数８０３が「１」、距離８０４が「２３．８ｋｍ」である。
【００２８】
<動作の説明>
図２を用いて、本発明の実施形態の処理の流れの概要を説明する。
先ず、経路探索に必要なデータを読み込む［ステップ２０１］。
次に、探索条件を設定する［ステップ２０２］。ここで、探索条件とは、例えば出発駅、目的駅、利用列車種別、所要時間優先か乗換え回数優先か等の探索において優先すべき事項である探索種別等を指す。
【００２９】
次に、経路探索部１１はダイクストラ法による経路探索を行う［ステップ２０３］。ダイクストラ法では最優秀経路情報求め、同時に最優秀経路情報を求めるときに使用したリンクテーブルの全通過経路情報を通過経路情報テーブル１６に保持しておく。
ついで前記全通過情報から経路生成部１２によって複数の生成経路情報を生成する［ステップ２０４］。
【００３０】
次に、前記経路生成部１２によって生成された複数の生成経路情報をＧＡによって経路補正を行う［ステップ２０５］。ＧＡにおいては、一つの経路、つまり出発駅から目的駅までつながった経路を１つの遺伝子とし、１点交叉により新経路を生成し、この生成された経路の中から最優秀経路情報に次ぐ複数の代替経路が選択される［ステップ２０６］。
ここで１点交差とは、二つの経路を経路の途中の１点でそれ以降の経路を交換することを言う。
【００３１】
以上のように、本発明の実施形態の処理の概要は、先ず経路探索部１１がダイクストラ法によって最優秀経路情報と前記最優秀経路情報を求めるときに使用した通過経路情報を求め、次に経路生成部１２が前記最優秀経路情報を求めるときに使用した通過経路情報から生成経路情報を生成し、最後に経路補正部１３がＧＡによって経路補正を行い、最優秀経路情報に次いで優秀な複数の代替経路を求める、というものである。
【００３２】
次に、図５を用いて、経路探索部１１であるダイクストラ法による経路探索２０３の詳細動作を説明する。始めに経路探索部１１で用いる変数および値について説明する。
・Ｎ：探索対象指定駅を格納する変数である。
・Ｌ（ｉ）：指定駅を出発駅とするリンク群である。
・Ｅ：通過経路情報を格納する変数である。現リンクＩＤ、直前リンクＩＤ、直前通過経路情報格納位置、経路評価値を格納する。
・Ｔ（ｘ，ｙ）：当該リンク通過時の通過経路情報を格納する２次元配列である。ｘはリンクＩＤであり、ｙは格納位置である。
・Ｓ（ｊ）：経路探索対象の通過経路情報を格納する配列である。
・Ｄ（ｋ）：通過経路情報配列である。目的駅到達通過経路情報を保持する。
【００３３】
次に、処理フローを説明する。
経路探索部１１は、最初に出発駅を設定する［ステップＳ５０１］。
次に、経路探索部１１は、Ｎを出発駅とするリンク群をＬに代入する［ステップＳ５０２］。
次に、経路探索部１１は、リンク群が存在するかどうか判定する［ステップＳ５０３］。リンク群が存在しなければ処理を終了し、存在する場合、直前のリンクまでの通過経路情報を保持するための変数Ｅ１、現在のリンクまでの通過経過情報を保持するための変数Ｅ２を用意し、ステップＳ５０４に進む。Ｅ１およびＥ２の初期値は０（空）である。リンク群の添字をｉとし、ｉ＝１とする［ステップ５０４］。
【００３４】
次に、経路探索部１１は、Ｌ（ｉ）が存在するかどうか判定する［ステップＳ５０５］。存在すればステップＳ５０６に進む。存在しなければステップ５１６に進む。
現在のリンクＬ（ｉ）の通過経路情報Ｅ２の経路評価値をＥ１にＬ（ｉ）のリンクが持つ評価値を加算して求める［ステップＳ５０６］。
次に、経路探索部１１はＬ（ｉ）が通過か未通過かの判定を行う［ステップＳ５０７］。Ｌ（ｉ）が未通過の場合、ＳにＬ（ｉ）についての通過経路情報を追加し［ステップＳ５０８］Ｔ（Ｌ（ｉ））にＥ２を追加する［ステップＳ５１１］。Ｌ（ｉ）が通過の場合、ステップＳ５０９に進む。
【００３５】
経路探索部１１は、Ｌ（ｉ）が既に通過済みである場合、Ｅ２がＴ（Ｌ（ｉ））の最優秀経路情報評価値よりも優秀かどうか判定する［ステップＳ５０９］。最優秀のものより優秀である場合にはＳのＬ（ｉ）についての通過経路情報をＥ２に書換え［ステップＳ５１０］、Ｔ（Ｌ（ｉ））にＥ２を追加する［ステップＳ５１１］。
【００３６】
従来、ダイクストラ法では、最優秀経路情報のみを求めるために、最優秀経路情報のみを保持しており、より優秀な通過経路情報があった場合は元の値を書き換える。しかし、本実施形態では後の経路作成時に利用するために、最優秀でない通過経路情報も保持しておく。この為Ｔ（Ｌ（ｉ））へＥ２は書き換えではなく追加としている。
経路探索部１１は、Ｅ２がＴ（Ｌ（ｉ））の最優秀経路情報評価値よりも優秀でない場合、Ｌ（ｉ）がループ区間を含むかどうか判定する［ステップＳ５１２］。含まなければＳ５１１に進む。含む場合にはステップＳ５１５に進む。
ここで、「ループ区間を含む」とは、経路内で重複する列車停車駅が存在することを意味する。重複停車駅間は冗長な区間となり、非実用的な経路となるため、ループ区間を含む経路は切り捨てる。
【００３７】
経路探索部１１は、ステップＳ５１１に続き、Ｌ（ｉ）の到着駅が目的駅であるかどうかを判定する［ステップＳ５１３］。目的駅でない場合にはステップＳ５１５に進む。目的駅であった場合にはＤにＥ２を追加し［ステップＳ５１４］、ステップＳ５１５に進む。
ステップＳ５１５では、ｉに1を加えステップＳ５０５に戻る。
また、経路探索部１１はステップＳ５０５でＬ（ｉ）が存在しなくなった場合、つまり、Ｎを出発駅とするリンクの処理が全て完了すると、ステップＳ５１６に進む。ステップＳ５１６ではＳが空かどうかを判定する。空の場合は処理を終了する。空でない場合には、Ｓから次の検索対象となる通過経路情報を取得するために、Ｓの最優秀通過経路情報をＥ１に代入する［ステップＳ５１７］、Ｅ１に設定した値は検索対象となったので、Ｅ１への設定値をＳから削除する［ステップＳ５１８］。
次に、経路探索部１１はＮにＥ１の現リンクの到着駅を代入する［ステップＳ５１９］。
【００３８】
次に、経路探索部１１はＮが目的駅であるかどうか判定し［ステップＳ５２０］、Ｎが目的駅であれば、ＤにＥ１を追加し、ステップＳ５１６に戻る。Ｎが目的駅でなければ、ステップＳ５２０に戻り、Ｎを出発駅とするリンク群を取得する。ここで、Ｎを出発駅とするとするリンク群を取得する際に、リンクのブリッジ開始ＩＤをもとにブリッジを取得し、乗換えに関する情報と次に接続するリンクを取得することができる。このようにブリッジテーブル１５に予めデータを用意しておくことにより、次につながるリンクの探索、乗換情報に関する情報の判定、取得等を省略することができ、探索の処理を少なくし、探索時間の向上を図ることができる。
経路探索部１１はＳが空になったところで処理を終了する［ステップＳ５１６］。
【００３９】
以上の処理により、各リンクが通過経路情報を保持した状態となる。例えば、図６（Ａ）のようなネットワークにおいて、リンクＩＤ４５５３のリンクには、リンクＩＤ１６６７から来た場合の通過経路情報、リンクＩＤ７７７から来た場合の通過経路情報、リンクＩＤ２２４５から来た場合の通過経路情報、というように、前記経路探索終了時には、経路探索時に生成された通過経路情報を各リンクが干しした状態のネットワークおよび生成経路情報テーブル１７が生成される。この通過経路情報を用いて、出発駅から目的駅までの経路を作成する。
【００４０】
図７を用いて、経路生成部１２が前記経路探索部１１で求めた通過経路情報を元に経路作成を行う方法を説明する。
前記経路探索部１１で取得した目的駅へ到達する通過経路情報群Ｄを用いて、目的駅から出発駅へとたどってゆくことによって、出発駅から目的駅への経路を取得する。
まず、経路生成部１２は、ｋに１を代入する［ステップＳ７０１］。
次に、経路生成部１２はＤ（ｋ）が存在するかどうか判定する［ステップＳ７０２］。Ｄ（ｋ）が存在しない場合は既設経路を生成するか、新規経路を生成するかの判定を行い［ステップＳ７１４］、新規経路を生成する場合にはステップＳ７０１に戻り、既設経路を生成する場合には処理を終了する。Ｄ（ｋ）が存在する場合には、Ｄ（ｋ）の持つリンクを取得し［ステップＳ７０３］、ステップＳ７４０に進む。
【００４１】
次に、経路生成部１２は、ステップＳ７０３において取得したリンクが出発駅に到達しているかどうか判定する。到達していなければ直前の通過経路情報を取得する［ステップＳ７０５］。
次に、経路生成部１２は、ステップＳ７０５で取得した通過経路情報が使用済みかどうか判定する［ステップＳ７０６］。使用済みでなければそのまま利用し、ステップＳ７０９に進む。使用済みであればステップＳ７０５で取得した通過経路情報が他に未使用通過経路情報があるかどうか判定する［ステップＳ７０８］。未使用通過経路情報がある場合には未使用通過経路情報のうち、最優秀の通過経路情報を取得し［ステップＳ７０８］ステップＳ７０９に進む。
【００４２】
次に、経路生成部１２はステップＳ７０５において取得した通過経路情報またはステップＳ７０８において取得した通過経路情報と、現在まで取得している通過経路情報を比較して、経路がループ区間を含むかどうか判定する［ステップＳ７０９，Ｓ７１０］。ループ区間を含まなければステップＳ７０５において取得した通過経路情報またはステップＳ７０８において取得した通過経路情報の持つリンクを取得し［ステップＳ７１１］ステップＳ７０４に戻る。
ステップＳ７０４でリンクが出発駅に到達している場合、及びステップＳ７１０がループ区間を含む場合は、経路生成部１２は経路生成のために取得した通過経路情報を全て使用済みにし［ステップＳ７１２］、ｋに１を加算し［ステップＳ７１３］、ステップＳ７０２に戻る。
以上のようにして生成された経路情報を、生成経路情報という。
【００４３】
図８に経路生成部１２が生成した生成経路情報テーブル１７の例を示す。図８では出発駅をＳ、目的駅をＧとしている。経路生成部１２が生成した生成経路情報は、使用済み通過経路情報を避けて無理やり接続しているものであり、精度の低いものであるが、この後にＧＡを用いて生成された経路を補正する。
【００４４】
次に図９を用いて、ＧＡによる経路補正部１３の処理フロー例を説明する。
先ず、経路補正部１３は前記経路生成部１２が生成した生成経路情報を取得し、ランキングを生成する。ここでランキングとは、一定数の生成経路情報を、重複を排除し、評価順に保持しているテーブルである。経路補正部１３が新しい生成経路情報をランキングに挿入する場合には、例えばその生成経路情報が、現ランキングの１１位の生成経路情報より優秀で、１０位の生成経路情報より優秀でなければ、１０位と１１位の間に挿入する。１１位以下の生成経路情報は全て順位が１つ繰り下がり、最下位の生成経路情報を削除し、ランキング内の生成経路情報保持数は一定に保つ、という動作をする。
【００４５】
ランキングに経路を挿入後、経路生成部１２が生成した全生成経路情報に付き、各停車駅で分割し、前半経路と後半経路の集合を生成する。例えば図１０に示すように、Ａ−Ｂ−Ｃ−Ｄ−Ｅという経路がある場合、（Ａ−Ｂ）（Ｂ−Ｃ−Ｄ−Ｅ）、（Ａ−Ｂ−Ｃ）（Ｃ−Ｄ−Ｅ）、（Ａ−Ｂ−Ｃ−Ｄ）（Ｄ−Ｅ）のように分割することができる。
次に経路補正部１３は、分割した前半経路と後半経路を分割した経路毎にまとめ［ステップＳ９０２］、経路に停車駅があるかどうか判定する［ステップＳ９０３］。停車駅がなければ処理を終了する。停車駅がある場合、経路補正部１３は、停車駅毎に全ての接続パターンの評価を試み、評価の高い優秀な経路を取得してゆく。具体的には、先ず１つの停車駅を選び、前半経路の有無を判定する［ステップ９０５］。前半経路が存在しない場合、次の停車駅を取得し［ステップＳ９０４］、ステップＳ９０３に戻る。前半経路が存在する場合、後半経路の有無を判定する［ステップＳ９０７］。後半経路も存在する場合、前半経路と後半経路を接続し、出発駅から目的駅までの経路を作成する［ステップＳ９０８］。
【００４６】
生成した経路をランキングに挿入し［ステップＳ９０９］、挿入が成功したかどうか判定する［ステップＳ９１０］。挿入に成功した場合新経路としてその経路を別途保持しておく［ステップＳ９１１］。挿入に失敗した場合、現在のランキング最下位よりも評価値が低い、またはランキングに既に同じ経路があるということを意味するので、この経路は削除する。
【００４７】
図１１にＢ駅で分割した場合を示す。前半経路と後半経路を組み合わせて接続し、評価を行ってランキングへの挿入を試みることを示している。ランキングへの挿入成功とはランキング内にその経路が保持される状態を言い、失敗とはランキングの最下位よりも優秀でないためにランキング内にその経路が保持されないことを意味する。
次に経路補正部１３は、次の後半経路を取得し［ステップＳ９１２］、ステップＳ９０７に戻る。
次に経路補正部１３は、ステップ９０７で後半経路が存在しなくなったら、次の前半経路を取得し［ステップＳ９０６］、ステップＳ９０５に戻り、ステップＳ９０５で前半経路が存在しなくなったら、次の停車駅を取得し［ステップＳ９０４］、ステップＳ９０３に戻り、ステップＳ９０３で停車駅が存在しなくなったら処理を終了する。
【００４８】
図１２に、前記経路補正部１３による処理結果を示す。例として、出発駅をＳとし、目的駅をＧとした場合を示している。結果は、ダイクストラ法による経路探索部１１および経路生成部１２によって生成された経路が補正され、経路評価値の優秀な順に並んでいる。
【００４９】
以上述べた経路探索方法の具体的な実施例を挙げる。経路評価は所要時間、乗換回数、距離の３つの値を用い、所要時間探索、乗換探索、距離探索を行う。核探索における経路評価方法は以下の通りである。
（所要時間探索）
所要時間を基準に経路探索を行う。この場合、所要時間が短い方が優秀な経路となる。所要時間が同じ場合は乗換回数を比較し、乗換回数が少ない方を優先する。所要時間、乗換回数共に同じ場合は、距離が短いものを優先する。
（乗換回数探索）
乗換回数を基準に経路探索を行う。この場合、乗換回数が少ない方が優秀な経路となる。乗換回数が同じ場合は所要時間を比較し、所要時間が短いほうを優先する。乗換回数、所要時間共に同じ場合は、距離の短いものを優先する。
【００５０】
（距離探索）
距離を基準に経路探索を行う。この場合、距離が短い方が優秀な経路となる。鉄道経路は距離を元に運賃料金を計算している場合が多く、一概には言えないが、距離が短ければ金額が安い、という場合が多い。またＪＲの運賃規則において、ある区間内ではではどのように列車に乗っても最安となる運賃で計算する、といった規則があり、この場合に最安経路を求めるために、最短距離経路を求める必要がある。距離が同じ場合は所要時間を比較し、所要時間が短いほうを優先する。距離、所要時間共に同じ場合は、乗換回数が少ないものを優先する。
【００５１】
以下に（溝口）−（東京）間で行った結果を示す。［表１］が所要時間探索結果、［表２］が乗換回数探索結果、［表３］が距離探索結果で、
全て上位５経路を示している。なお本経路探索では、前記ランキングの数を２００として実行している。
【表１】
【表２】
【表３】
【００５２】
上記のように、第２経路以降も、第１最優秀評価経路に近い実用的な有効代替経路を導出している。また、各探索法によってさまざまな結果を導出していることがわかる。各表では上位５経路のみを表示したが、実際にはランキングの数だけの経路、今回であれば２００経路を保持している。［表３］の距離探索の結果では同じような経路ばかり導出されているが、例えば「乗換パターンが同じ経路をどういつのけいろとみなす」というような条件でランキング内の経路をグループ化し、各グループの上位から経路を導出する等により、さまざまなパターンの経路を導出できる。
【００５３】
また、上記の例では単純な所要時間探索、乗換回数探索、距離探索を示したが、例えば所要時間１分を１ポイント、乗換１回を１０ポイント、というように複数のパラメータを一意のポイントに変換し、それを経路評価値として用いれば、ＧＡによって評価値に応じた経路補正により、複数条件を用いた柔軟な経路探索が可能な経路探索システムを提供することが可能である。
【図面の簡単な説明】
【００５４】
【図１】本発明の実施形態における経路検索システムの全体構成図である。
【図２】本発明の実施形態における処理のフローチャートである。
【図３】リンクテーブルとブリッジテーブルの例である。
【図４】路線図と停車駅単位のリンクおよび乗換駅単位のリンクの例である。
【図５】経路探索プログラムのフローチャートである。
【図６】路線図の例と通過経路情報の例である。
【図７】経路生成プログラムのフローチャートである。
【図８】経路生成プログラムによって生成された生成経路情報の例である。
【図９】遺伝的アルゴリズムによる経路補正プログラムのフローチャートである。
【図１０】経路補正プログラムによる経路分割例である。
【図１１】経路補正プログラムにより分割した経路の合成例である。
【図１２】経路補正プログラムによって補正された結果の例である。
【符号の説明】
【００５５】
１０：サーバ、１１：ダイクストラ法経路作成部、１２：ＧＡ経路作成部、１３：リンクテーブル、１４：ブリッジテーブル、１５：通過経路情報テーブル、１６：生成経路情報テーブル、２０：公衆通信回線網、３０：ユーザー端末。
【技術分野】
【０００１】
本発明は、コンピュータを用いて公共交通網の出発駅から目的駅までの最適な経路を複数種類探索する方法およびプログラムおよびシステムに係り、特にダイクストラ法によって最優秀経路情報を求めるとともに前記最優秀経路情報を求める過程で使用した通過経路情報を再利用し、遺伝的アルゴリズム（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ、以下ＧＡと略す。）を用いて最優秀経路情報の代替経路を優秀な順に求める経路探索方法および経路探索プログラムおよび経路探索システムに関する。
【背景技術】
【０００２】
一般に従来技術による公共交通網の経路探索方法は、ダイクストラ法が用いられてきた。この方法は通過点に複数の選択できる経路が存在するとき、最優秀経路情報を選択し、その経路を進んで複数の選択できる経路が存在する点に至った場合には再度最優秀な経路を選択し、以下これを繰り返すことにより、全体として最優秀経路情報を探索する技術である。
【０００３】
ここで、公共交通網とは鉄道を始めとする出発時間と到着時間、区間距離、運賃が予め定められている交通手段を言う。
また、最優秀経路情報とは、例えば時間を探索条件とした探索の場合には最短時間の経路をいい、乗換え回数を探索条件とした場合には合計乗換え回数が最少の経路を言い、料金を探索条件とした場合には料金が最低な経路のように、探索条件が最適な経路を言う。
【０００４】
また、特許文献１にはダイクストラ法によって最優秀経路情報を探索した後、前記最優秀経路情報で使用した乗換駅を使用禁止にして、再度ダイクストラ法で最優秀経路情報に次ぐ経路を順次探索する技術が記載されている。
さらに、特許文献２には遺伝的アルゴリズムを利用して最適経路とそれに準ずる複数の代替経路を求めるカーナビゲーションシステムに関する技術が記載されている。
【特許文献１】特開平１１−４４５４７号公報
【特許文献２】特開平９−１７８５００号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
前述の従来技術による公共交通網の経路探索方法には次のような不具合があった。
先ず、ダイクストラ法は高速に最優秀経路情報を求めることが可能であり、広く用いられている。しかし、この方法は最優秀経路情報以外の代替経路を求めることはできないという不具合があった。
【０００６】
これに対し、特許文献１に開示されている技術は、有効な代替経路を探索できない場合がある。
例えば、ダイクストラ法によれば、枕崎から鹿児島中央までの経路を探索した場合、最優秀経路情報として（枕崎）−ＪＲ指宿枕崎線（枕崎−山川）−（山川）−ＪＲ指宿枕崎線（山川−鹿児島中央）−鹿児島中央という、枕崎から山川まで行き、山川で乗換え、鹿児島中央に行くという経路が探索される。
これに対して、特許文献１に開示されている技術に従い、山川での乗換えを経路探索において使用禁止にしてしまうと、有効な代替経路は探索できない。しかし実際には、（枕崎）−ＪＲ指宿枕崎線（枕崎−山川）−（山川）−ＪＲ指宿枕崎線（山川−鹿児島中央）−（南鹿児島）−徒歩−（南鹿児島駅前）−鹿児島市電１系統−（郡元）−鹿児島市電２系統−（鹿児島中央駅前）−徒歩−（鹿児島中央）、というように、山川での乗換え後、南鹿児島で乗り換える経路も存在する。
このように、特許文献１記載の技術では、最優秀経路情報に乗換駅が１つしか存在しない場合、また、乗換駅が存在しない場合には、代替経路を探索できないという不具合が存在する。
【０００７】
また、特許文献２に記載の技術は、カーナビゲーションシステムに広く用いられている。しかし、道路交通網においては運転者が自由に経路を選択することができるのに対し、鉄道網では列車の運行時刻、行き先、乗換駅などを条件として考慮しなければならない。また、カーナビゲーションシステムがＧＰＳを使用して現在位置と目的地から距離や右左折の回数等を基に経路を選択するのに対し、鉄道網においては所要時間を基に経路を選択する場合がある。このため、特許文献２記載の技術を単純に鉄道網に適用することはできないという不具合が存在する。
【０００８】
本発明の目的は、前述の従来技術による不具合を除去することであり、公共交通網において最優秀経路情報の他に複数の最優秀経路情報に次ぐ優秀な代替経路を探索できる経路探索方法および経路探索プログラムおよび経路探索システムを提供することである。
【課題を解決するための手段】
【０００９】
前記目的を達成するために請求項１記載の発明は、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムであって、
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、
該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、
該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、
該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを備えることを特徴とする。
【００１０】
また、請求項２記載の発明は、前記経路探索システムにおいて、前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込み、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクＩＤを読み込み、該接続リンクＩＤを含むレコードをリンクテーブルから検索することを特徴とする。
【００１１】
また、請求項３記載の発明は、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索方法であって、
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを設け、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行い、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出し、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求めることを特徴とする。
【００１２】
また、請求項４記載の発明は、前記経路探索方法において前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込み、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクＩＤを読み込み、該接続リンクＩＤを含むレコードをリンクテーブルから検索することを特徴とする。
【００１３】
また、請求項５記載の発明は、出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部と、前記各構成を制御するコンピュータとを備え、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行う機能と、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出する機能と、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求める機能とを実現させることを特徴とする。
【００１４】
また、請求項６記載の発明は、前記経路探索プログラムにおいて、前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加した請求項５記載の経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込む機能と、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索する機能と、該検索されたレコードに格納された接続リンクＩＤを読み込む機能と、該接続リンクＩＤを含むレコードをリンクテーブルから検索する機能とを実現することを特徴とする。
【発明の効果】
【００１５】
本発明による経路探索方法および経路探索プログラムおよび経路探索システムによれば、出発駅および到着駅および出発駅から到着駅までの所要時間と距離を格納したリンクテーブルと、リンクテーブルの出発駅を到着駅とするリンクテーブルのレコードの位置を格納するブリッジテーブルを予め用意し、これらのテーブルを読み込んで、ダイクストラ法によって最優秀経路情報を生成すると共に、その生成過程で探索した通過経路情報をもとに、生成経路情報を生成すると共に、ＧＡ法によって生成経路情報を補正するように構成したため、従来はダイクストラ法では最優秀経路情報しか導出できなかったのに対し、本願発明においては最優秀経路情報に次いで優秀な代替可能な複数の経路を探索することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明による経路探索方法および経路探索プログラムおよび経路探索システムの一実施形態を、図面を参照して詳細に説明する。
図１は、本発明の実施形態における経路検索システムの全体構成図である。
図２は、本発明の実施形態における処理のフローチャートである。
図３は、リンクテーブルとブリッジテーブルの例である。
図４は、路線図と停車駅単位のリンクおよび乗換駅単位のリンクの例である。
図５は、経路探索プログラムのフローチャートである。
図６は、路線図の例と通過経路情報の例である。
図７は、経路生成プログラムのフローチャートである。
図８は、経路生成プログラムによって生成された経路の例である。
図９は、遺伝的アルゴリズムによる経路補正プログラムのフローチャートである。
図１０は、経路補正プログラムによる経路分割例である。
図１１は、経路補正プログラムにより分割した経路の合成例である。
図１２は、経路補正プログラムによって補正された結果の例である。
【００１７】
<構成の説明>
本発明の一実施形態による経路探索方法および経路探索プログラムが実施される経路探索システムを、図１を用いて説明する。
本実施形態のシステムは、経路検索システム１００と、ユーザーの保持するコンピュータ３０と、経路探索システム１００とユーザーの保持するコンピュータ３０とを接続する公衆通信回線網２０とを備える。
【００１８】
前記経路検索システム１００は、プログラムが稼動するサーバ１０と、ダイクストラ法によって経路を探索する経路探索部１１と、前記経路探索部１１によって探索した経路から代替経路を生成する経路生成部１２と、前記経路生成部１２によって生成されて経路を遺伝的アルゴリズムによって補正する経路補正部１３と、出発駅から到着駅までの所要時間および距離を格納するリンクテーブル１４と、リンクテーブル１４において到着駅を出発駅とするレコードのＩＤおよび乗換え時間および列車の接続に関する情報である接続情報を格納するブリッジテーブル１５と、経路探索部１１によって使用された通過経路を格納する通過経路情報テーブル１６と、通過経路情報テーブル１６から生成された生成経路情報を格納する生成経路情報テーブル１７を備える。
【００１９】
経路探索部１１は、ダイクストラ法によって最優秀経路情報を求めると共に、その過程で使用した経路を全て通過経路情報テーブル１６に格納する。
経路生成部１２は、前記通過経路情報テーブル１６に格納された通過経路情報から最優秀経路情報に代替可能な生成経路情報を導出し、生成経路情報テーブル１７に格納する。
経路補正部１３は、前記生成経路情報テーブル１７に格納された生成経路情報を補正し、最優秀経路情報についで優秀な複数の代替経路を導出する。
【００２０】
<データの説明>
図３（Ａ）を用いてリンクテーブル１４のデータ構成例を説明する。
リンクテーブル１４は、レコードに一意に定められたリンクＩＤ３０１と、出発駅名を表す出発駅３０２と、到着駅名を表す到着駅３０３と、特急や急行といった列車の種別を表す列車３０４と、ブリッジテーブル１５内のブリッジＩＤ３０８を示す開始ブリッジＩＤ３０５と、出発駅から到着駅までかかる時間を表す所要時間３０６と、出発駅から到着駅までの距離を表す距離３０７とを備え、具体的なデータの例は、リンクＩＤ３０１が「１」、出発駅３０２が「ｎ（１）」、到着駅３０３が「ｎ（２）」、開始ブリッジＩＤ３０５が「１」、所要時間３０６が「ｘ（１）」、距離３０７が「ｄ（１）」である。
ここで、リンクとは出発駅，到着駅，列車，出発駅から到着駅に至るのに必要な所要時間、出発駅から到着駅の距離などを保持したデータを言う。リンクテーブル１４は全ての駅間のリンクを保持している。
【００２１】
図３（Ｂ）を用いてブリッジテーブル１５のデータ構成例を説明する。
ブリッジテーブル１５は、レコードに一意に定められたブリッジＩＤ３０８と、リンクテーブル１４において、あるレコードの到着駅を出発駅とするレコードのリンクＩＤを示す接続リンクＩＤ３０９と、乗換えにかかる時間を表す乗換え時間３１０と、乗換えまたは直通または折返しなど列車の接続に関する情報を表す接続情報３１１とを備え、具体的なデータの例は、ブリッジＩＤ３０８が「１」、接続リンクＩＤ３０９が「１１２」、乗換え時間３１０が「３２」、接続情報が「乗換え」である。
【００２２】
ここで、ブリッジテーブル１５の存在意義を説明する。
経路探索において、あるリンクから接続するリンクがどれなのかを探す場合に、リンクテーブル全体から検索していてはリンクテーブル１４のデータ量は膨大なものであるため時間がかかる。例えば、図３（Ａ）のリンクＩＤが「１」のリンクは到着駅がｎ（２）なので、これに接続するリンクはｎ（２）を出発駅とするリンクであるが、ｎ（２）を出発駅とするリンクはリンクテーブル１４のどこにあるか判らない。この為ｎ（２）を出発駅とするリンクをテーブル全体から探す必要があるが、リンクテーブル１４はレコード数が膨大な量に及ぶため、その中から探すのには時間がかかってしまう。そこで、あるリンクに対して接続するリンク情報を格納したデータを用意する。このデータをブリッジと呼ぶ。リンクにはブリッジの開始ＩＤを格納しておく。また、ブリッジには次に接続するリンクＩＤと、接続にかかる乗換え時間や接続情報を格納しておく。
【００２３】
このように構成することにより、例えば、図３（Ａ）のリンクテーブル１４のリンクＩＤ３０１が「１」のリンクでは、このリンクの開始ブリッジＩＤ３０５は「１」であるから、図３（Ｂ）のブリッジテーブル１５のブリッジＩＤ３０８が「１」のブリッジを参照する。ブリッジＩＤ３０８が「１」のブリッジの接続リンクＩＤ３０９は「１１２」であるから、リンクＩＤ３０１から接続するリンクはリンクＩＤ３０１が「１１２」であることがわかる。また、リンクＩＤ３０１が「１」のリンクから接続するリンク、具体的にはこのリンクの着駅ｎ（２）を出発駅とするリンクは複数存在するので、このリンクと同数だけブリッジも存在する。リンクＩＤ３０１が「２」のリンクの開始ブリッジＩＤ３０５が「５１」であることから、リンクＩＤ３０１が「１」のリンクから接続するリンクは、ブリッジテーブル１５のブリッジＩＤ３０８が「１」から「５０」までのブリッジに接続情報があることがわかる。これらのブリッジを全て参照することにより、接続するリンクを全て取得することができる。
【００２４】
また、取得したリンクの開始ブリッジＩＤ３０５を基に次に接続するリンクＩＤ３０１を取得することを繰り返すことにより、経路のネットワークを探索することができる。
このブリッジを用いることにより、次に接続するリンクを簡単に、かつ高速に取得することができる。また、このブリッジにリンクからリンクへの接続情報を予め持たせることにより、乗換なのか直通なのか等の判定処理を経路探索処理から省くことができ、経路探索の処理効率の向上が図れる。
【００２５】
図４を用いて、リンクテーブル１４のデータ構成例を説明する。
図４（Ａ）のような駅と路線が配置されている場合、図４（Ｂ）の様に停車駅単位でリンクを設定するのではなく、図４（Ｃ）の様に乗換可能駅単位にリンクを設定する。これにより、リンクデータを削減することができ、メモリ使用量の削減、探索対象の現象による処理効率の向上が図れる。出発駅または目的駅が乗換え可能駅ではない場合は、その出発駅または目的駅を乗換駅と仮定し、最寄りの乗換え可能駅までのリンクを生成することにより乗換え可能駅のみの鉄道経路のネットワークにおいて経路探索を行うことができる。
【００２６】
図６を用いて、通過経路情報テーブル１６のデータ構成例を説明する。
図６（Ａ）に経路のネットワークの例を示す。例えば、リンクＩＤが「５４５３」の経路は、Ｂ駅を出発駅とし、その直前の経路はリンクＩＤが「７７７」のものと、「１６７７」のものと「２２４５」がある。この場合の通過経路情報テーブル１６の例として、図６（Ｂ）を示す。通過経路情報テーブル１５のデータ構成例は、各リンクに対し、直前の経路である直前リンクＩＤ６０１と、直前格納位置６０２と、経路評価値６０３とを備え、経路評価値６０３は、所要時間６０４と、乗換え回数６０５と、距離６０６とを備え、具体的なデータの例は、リンクＩＤが「４５５３」の場合、直前リンクＩＤ６０１が「１６６７」、直前格納位置６０２が「３」、所要時間６０４が「７８」、乗換え回数６０５が「２」、距離６０６が「１１４．３ｋｍ」である。
【００２７】
図８を用いて生成経路情報テーブル１７のデータ構成例を説明する。生成経路情報テーブル１７は、生成された生成経路情報を示す経路８０１と、出発駅から目的駅までの所要時間を示す所要時間８０２と、乗換え回数を示す乗換回数８０３と、出発駅から目的駅までの距離を示す距離８０４とを備え、具体的なデータの例は、経路８０１が「Ｓ−Ａ−Ｂ−Ｃ−Ｇ」、所要時間８０２が「２５」、乗換回数８０３が「１」、距離８０４が「２３．８ｋｍ」である。
【００２８】
<動作の説明>
図２を用いて、本発明の実施形態の処理の流れの概要を説明する。
先ず、経路探索に必要なデータを読み込む［ステップ２０１］。
次に、探索条件を設定する［ステップ２０２］。ここで、探索条件とは、例えば出発駅、目的駅、利用列車種別、所要時間優先か乗換え回数優先か等の探索において優先すべき事項である探索種別等を指す。
【００２９】
次に、経路探索部１１はダイクストラ法による経路探索を行う［ステップ２０３］。ダイクストラ法では最優秀経路情報求め、同時に最優秀経路情報を求めるときに使用したリンクテーブルの全通過経路情報を通過経路情報テーブル１６に保持しておく。
ついで前記全通過情報から経路生成部１２によって複数の生成経路情報を生成する［ステップ２０４］。
【００３０】
次に、前記経路生成部１２によって生成された複数の生成経路情報をＧＡによって経路補正を行う［ステップ２０５］。ＧＡにおいては、一つの経路、つまり出発駅から目的駅までつながった経路を１つの遺伝子とし、１点交叉により新経路を生成し、この生成された経路の中から最優秀経路情報に次ぐ複数の代替経路が選択される［ステップ２０６］。
ここで１点交差とは、二つの経路を経路の途中の１点でそれ以降の経路を交換することを言う。
【００３１】
以上のように、本発明の実施形態の処理の概要は、先ず経路探索部１１がダイクストラ法によって最優秀経路情報と前記最優秀経路情報を求めるときに使用した通過経路情報を求め、次に経路生成部１２が前記最優秀経路情報を求めるときに使用した通過経路情報から生成経路情報を生成し、最後に経路補正部１３がＧＡによって経路補正を行い、最優秀経路情報に次いで優秀な複数の代替経路を求める、というものである。
【００３２】
次に、図５を用いて、経路探索部１１であるダイクストラ法による経路探索２０３の詳細動作を説明する。始めに経路探索部１１で用いる変数および値について説明する。
・Ｎ：探索対象指定駅を格納する変数である。
・Ｌ（ｉ）：指定駅を出発駅とするリンク群である。
・Ｅ：通過経路情報を格納する変数である。現リンクＩＤ、直前リンクＩＤ、直前通過経路情報格納位置、経路評価値を格納する。
・Ｔ（ｘ，ｙ）：当該リンク通過時の通過経路情報を格納する２次元配列である。ｘはリンクＩＤであり、ｙは格納位置である。
・Ｓ（ｊ）：経路探索対象の通過経路情報を格納する配列である。
・Ｄ（ｋ）：通過経路情報配列である。目的駅到達通過経路情報を保持する。
【００３３】
次に、処理フローを説明する。
経路探索部１１は、最初に出発駅を設定する［ステップＳ５０１］。
次に、経路探索部１１は、Ｎを出発駅とするリンク群をＬに代入する［ステップＳ５０２］。
次に、経路探索部１１は、リンク群が存在するかどうか判定する［ステップＳ５０３］。リンク群が存在しなければ処理を終了し、存在する場合、直前のリンクまでの通過経路情報を保持するための変数Ｅ１、現在のリンクまでの通過経過情報を保持するための変数Ｅ２を用意し、ステップＳ５０４に進む。Ｅ１およびＥ２の初期値は０（空）である。リンク群の添字をｉとし、ｉ＝１とする［ステップ５０４］。
【００３４】
次に、経路探索部１１は、Ｌ（ｉ）が存在するかどうか判定する［ステップＳ５０５］。存在すればステップＳ５０６に進む。存在しなければステップ５１６に進む。
現在のリンクＬ（ｉ）の通過経路情報Ｅ２の経路評価値をＥ１にＬ（ｉ）のリンクが持つ評価値を加算して求める［ステップＳ５０６］。
次に、経路探索部１１はＬ（ｉ）が通過か未通過かの判定を行う［ステップＳ５０７］。Ｌ（ｉ）が未通過の場合、ＳにＬ（ｉ）についての通過経路情報を追加し［ステップＳ５０８］Ｔ（Ｌ（ｉ））にＥ２を追加する［ステップＳ５１１］。Ｌ（ｉ）が通過の場合、ステップＳ５０９に進む。
【００３５】
経路探索部１１は、Ｌ（ｉ）が既に通過済みである場合、Ｅ２がＴ（Ｌ（ｉ））の最優秀経路情報評価値よりも優秀かどうか判定する［ステップＳ５０９］。最優秀のものより優秀である場合にはＳのＬ（ｉ）についての通過経路情報をＥ２に書換え［ステップＳ５１０］、Ｔ（Ｌ（ｉ））にＥ２を追加する［ステップＳ５１１］。
【００３６】
従来、ダイクストラ法では、最優秀経路情報のみを求めるために、最優秀経路情報のみを保持しており、より優秀な通過経路情報があった場合は元の値を書き換える。しかし、本実施形態では後の経路作成時に利用するために、最優秀でない通過経路情報も保持しておく。この為Ｔ（Ｌ（ｉ））へＥ２は書き換えではなく追加としている。
経路探索部１１は、Ｅ２がＴ（Ｌ（ｉ））の最優秀経路情報評価値よりも優秀でない場合、Ｌ（ｉ）がループ区間を含むかどうか判定する［ステップＳ５１２］。含まなければＳ５１１に進む。含む場合にはステップＳ５１５に進む。
ここで、「ループ区間を含む」とは、経路内で重複する列車停車駅が存在することを意味する。重複停車駅間は冗長な区間となり、非実用的な経路となるため、ループ区間を含む経路は切り捨てる。
【００３７】
経路探索部１１は、ステップＳ５１１に続き、Ｌ（ｉ）の到着駅が目的駅であるかどうかを判定する［ステップＳ５１３］。目的駅でない場合にはステップＳ５１５に進む。目的駅であった場合にはＤにＥ２を追加し［ステップＳ５１４］、ステップＳ５１５に進む。
ステップＳ５１５では、ｉに1を加えステップＳ５０５に戻る。
また、経路探索部１１はステップＳ５０５でＬ（ｉ）が存在しなくなった場合、つまり、Ｎを出発駅とするリンクの処理が全て完了すると、ステップＳ５１６に進む。ステップＳ５１６ではＳが空かどうかを判定する。空の場合は処理を終了する。空でない場合には、Ｓから次の検索対象となる通過経路情報を取得するために、Ｓの最優秀通過経路情報をＥ１に代入する［ステップＳ５１７］、Ｅ１に設定した値は検索対象となったので、Ｅ１への設定値をＳから削除する［ステップＳ５１８］。
次に、経路探索部１１はＮにＥ１の現リンクの到着駅を代入する［ステップＳ５１９］。
【００３８】
次に、経路探索部１１はＮが目的駅であるかどうか判定し［ステップＳ５２０］、Ｎが目的駅であれば、ＤにＥ１を追加し、ステップＳ５１６に戻る。Ｎが目的駅でなければ、ステップＳ５２０に戻り、Ｎを出発駅とするリンク群を取得する。ここで、Ｎを出発駅とするとするリンク群を取得する際に、リンクのブリッジ開始ＩＤをもとにブリッジを取得し、乗換えに関する情報と次に接続するリンクを取得することができる。このようにブリッジテーブル１５に予めデータを用意しておくことにより、次につながるリンクの探索、乗換情報に関する情報の判定、取得等を省略することができ、探索の処理を少なくし、探索時間の向上を図ることができる。
経路探索部１１はＳが空になったところで処理を終了する［ステップＳ５１６］。
【００３９】
以上の処理により、各リンクが通過経路情報を保持した状態となる。例えば、図６（Ａ）のようなネットワークにおいて、リンクＩＤ４５５３のリンクには、リンクＩＤ１６６７から来た場合の通過経路情報、リンクＩＤ７７７から来た場合の通過経路情報、リンクＩＤ２２４５から来た場合の通過経路情報、というように、前記経路探索終了時には、経路探索時に生成された通過経路情報を各リンクが干しした状態のネットワークおよび生成経路情報テーブル１７が生成される。この通過経路情報を用いて、出発駅から目的駅までの経路を作成する。
【００４０】
図７を用いて、経路生成部１２が前記経路探索部１１で求めた通過経路情報を元に経路作成を行う方法を説明する。
前記経路探索部１１で取得した目的駅へ到達する通過経路情報群Ｄを用いて、目的駅から出発駅へとたどってゆくことによって、出発駅から目的駅への経路を取得する。
まず、経路生成部１２は、ｋに１を代入する［ステップＳ７０１］。
次に、経路生成部１２はＤ（ｋ）が存在するかどうか判定する［ステップＳ７０２］。Ｄ（ｋ）が存在しない場合は既設経路を生成するか、新規経路を生成するかの判定を行い［ステップＳ７１４］、新規経路を生成する場合にはステップＳ７０１に戻り、既設経路を生成する場合には処理を終了する。Ｄ（ｋ）が存在する場合には、Ｄ（ｋ）の持つリンクを取得し［ステップＳ７０３］、ステップＳ７４０に進む。
【００４１】
次に、経路生成部１２は、ステップＳ７０３において取得したリンクが出発駅に到達しているかどうか判定する。到達していなければ直前の通過経路情報を取得する［ステップＳ７０５］。
次に、経路生成部１２は、ステップＳ７０５で取得した通過経路情報が使用済みかどうか判定する［ステップＳ７０６］。使用済みでなければそのまま利用し、ステップＳ７０９に進む。使用済みであればステップＳ７０５で取得した通過経路情報が他に未使用通過経路情報があるかどうか判定する［ステップＳ７０８］。未使用通過経路情報がある場合には未使用通過経路情報のうち、最優秀の通過経路情報を取得し［ステップＳ７０８］ステップＳ７０９に進む。
【００４２】
次に、経路生成部１２はステップＳ７０５において取得した通過経路情報またはステップＳ７０８において取得した通過経路情報と、現在まで取得している通過経路情報を比較して、経路がループ区間を含むかどうか判定する［ステップＳ７０９，Ｓ７１０］。ループ区間を含まなければステップＳ７０５において取得した通過経路情報またはステップＳ７０８において取得した通過経路情報の持つリンクを取得し［ステップＳ７１１］ステップＳ７０４に戻る。
ステップＳ７０４でリンクが出発駅に到達している場合、及びステップＳ７１０がループ区間を含む場合は、経路生成部１２は経路生成のために取得した通過経路情報を全て使用済みにし［ステップＳ７１２］、ｋに１を加算し［ステップＳ７１３］、ステップＳ７０２に戻る。
以上のようにして生成された経路情報を、生成経路情報という。
【００４３】
図８に経路生成部１２が生成した生成経路情報テーブル１７の例を示す。図８では出発駅をＳ、目的駅をＧとしている。経路生成部１２が生成した生成経路情報は、使用済み通過経路情報を避けて無理やり接続しているものであり、精度の低いものであるが、この後にＧＡを用いて生成された経路を補正する。
【００４４】
次に図９を用いて、ＧＡによる経路補正部１３の処理フロー例を説明する。
先ず、経路補正部１３は前記経路生成部１２が生成した生成経路情報を取得し、ランキングを生成する。ここでランキングとは、一定数の生成経路情報を、重複を排除し、評価順に保持しているテーブルである。経路補正部１３が新しい生成経路情報をランキングに挿入する場合には、例えばその生成経路情報が、現ランキングの１１位の生成経路情報より優秀で、１０位の生成経路情報より優秀でなければ、１０位と１１位の間に挿入する。１１位以下の生成経路情報は全て順位が１つ繰り下がり、最下位の生成経路情報を削除し、ランキング内の生成経路情報保持数は一定に保つ、という動作をする。
【００４５】
ランキングに経路を挿入後、経路生成部１２が生成した全生成経路情報に付き、各停車駅で分割し、前半経路と後半経路の集合を生成する。例えば図１０に示すように、Ａ−Ｂ−Ｃ−Ｄ−Ｅという経路がある場合、（Ａ−Ｂ）（Ｂ−Ｃ−Ｄ−Ｅ）、（Ａ−Ｂ−Ｃ）（Ｃ−Ｄ−Ｅ）、（Ａ−Ｂ−Ｃ−Ｄ）（Ｄ−Ｅ）のように分割することができる。
次に経路補正部１３は、分割した前半経路と後半経路を分割した経路毎にまとめ［ステップＳ９０２］、経路に停車駅があるかどうか判定する［ステップＳ９０３］。停車駅がなければ処理を終了する。停車駅がある場合、経路補正部１３は、停車駅毎に全ての接続パターンの評価を試み、評価の高い優秀な経路を取得してゆく。具体的には、先ず１つの停車駅を選び、前半経路の有無を判定する［ステップ９０５］。前半経路が存在しない場合、次の停車駅を取得し［ステップＳ９０４］、ステップＳ９０３に戻る。前半経路が存在する場合、後半経路の有無を判定する［ステップＳ９０７］。後半経路も存在する場合、前半経路と後半経路を接続し、出発駅から目的駅までの経路を作成する［ステップＳ９０８］。
【００４６】
生成した経路をランキングに挿入し［ステップＳ９０９］、挿入が成功したかどうか判定する［ステップＳ９１０］。挿入に成功した場合新経路としてその経路を別途保持しておく［ステップＳ９１１］。挿入に失敗した場合、現在のランキング最下位よりも評価値が低い、またはランキングに既に同じ経路があるということを意味するので、この経路は削除する。
【００４７】
図１１にＢ駅で分割した場合を示す。前半経路と後半経路を組み合わせて接続し、評価を行ってランキングへの挿入を試みることを示している。ランキングへの挿入成功とはランキング内にその経路が保持される状態を言い、失敗とはランキングの最下位よりも優秀でないためにランキング内にその経路が保持されないことを意味する。
次に経路補正部１３は、次の後半経路を取得し［ステップＳ９１２］、ステップＳ９０７に戻る。
次に経路補正部１３は、ステップ９０７で後半経路が存在しなくなったら、次の前半経路を取得し［ステップＳ９０６］、ステップＳ９０５に戻り、ステップＳ９０５で前半経路が存在しなくなったら、次の停車駅を取得し［ステップＳ９０４］、ステップＳ９０３に戻り、ステップＳ９０３で停車駅が存在しなくなったら処理を終了する。
【００４８】
図１２に、前記経路補正部１３による処理結果を示す。例として、出発駅をＳとし、目的駅をＧとした場合を示している。結果は、ダイクストラ法による経路探索部１１および経路生成部１２によって生成された経路が補正され、経路評価値の優秀な順に並んでいる。
【００４９】
以上述べた経路探索方法の具体的な実施例を挙げる。経路評価は所要時間、乗換回数、距離の３つの値を用い、所要時間探索、乗換探索、距離探索を行う。核探索における経路評価方法は以下の通りである。
（所要時間探索）
所要時間を基準に経路探索を行う。この場合、所要時間が短い方が優秀な経路となる。所要時間が同じ場合は乗換回数を比較し、乗換回数が少ない方を優先する。所要時間、乗換回数共に同じ場合は、距離が短いものを優先する。
（乗換回数探索）
乗換回数を基準に経路探索を行う。この場合、乗換回数が少ない方が優秀な経路となる。乗換回数が同じ場合は所要時間を比較し、所要時間が短いほうを優先する。乗換回数、所要時間共に同じ場合は、距離の短いものを優先する。
【００５０】
（距離探索）
距離を基準に経路探索を行う。この場合、距離が短い方が優秀な経路となる。鉄道経路は距離を元に運賃料金を計算している場合が多く、一概には言えないが、距離が短ければ金額が安い、という場合が多い。またＪＲの運賃規則において、ある区間内ではではどのように列車に乗っても最安となる運賃で計算する、といった規則があり、この場合に最安経路を求めるために、最短距離経路を求める必要がある。距離が同じ場合は所要時間を比較し、所要時間が短いほうを優先する。距離、所要時間共に同じ場合は、乗換回数が少ないものを優先する。
【００５１】
以下に（溝口）−（東京）間で行った結果を示す。［表１］が所要時間探索結果、［表２］が乗換回数探索結果、［表３］が距離探索結果で、
全て上位５経路を示している。なお本経路探索では、前記ランキングの数を２００として実行している。
【表１】
【表２】
【表３】
【００５２】
上記のように、第２経路以降も、第１最優秀評価経路に近い実用的な有効代替経路を導出している。また、各探索法によってさまざまな結果を導出していることがわかる。各表では上位５経路のみを表示したが、実際にはランキングの数だけの経路、今回であれば２００経路を保持している。［表３］の距離探索の結果では同じような経路ばかり導出されているが、例えば「乗換パターンが同じ経路をどういつのけいろとみなす」というような条件でランキング内の経路をグループ化し、各グループの上位から経路を導出する等により、さまざまなパターンの経路を導出できる。
【００５３】
また、上記の例では単純な所要時間探索、乗換回数探索、距離探索を示したが、例えば所要時間１分を１ポイント、乗換１回を１０ポイント、というように複数のパラメータを一意のポイントに変換し、それを経路評価値として用いれば、ＧＡによって評価値に応じた経路補正により、複数条件を用いた柔軟な経路探索が可能な経路探索システムを提供することが可能である。
【図面の簡単な説明】
【００５４】
【図１】本発明の実施形態における経路検索システムの全体構成図である。
【図２】本発明の実施形態における処理のフローチャートである。
【図３】リンクテーブルとブリッジテーブルの例である。
【図４】路線図と停車駅単位のリンクおよび乗換駅単位のリンクの例である。
【図５】経路探索プログラムのフローチャートである。
【図６】路線図の例と通過経路情報の例である。
【図７】経路生成プログラムのフローチャートである。
【図８】経路生成プログラムによって生成された生成経路情報の例である。
【図９】遺伝的アルゴリズムによる経路補正プログラムのフローチャートである。
【図１０】経路補正プログラムによる経路分割例である。
【図１１】経路補正プログラムにより分割した経路の合成例である。
【図１２】経路補正プログラムによって補正された結果の例である。
【符号の説明】
【００５５】
１０：サーバ、１１：ダイクストラ法経路作成部、１２：ＧＡ経路作成部、１３：リンクテーブル、１４：ブリッジテーブル、１５：通過経路情報テーブル、１６：生成経路情報テーブル、２０：公衆通信回線網、３０：ユーザー端末。
【特許請求の範囲】
【請求項１】
出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムであって、
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、
該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、
該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、
該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを備えることを特徴とする経路探索システム。
【請求項２】
前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込み、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクＩＤを読み込み、該接続リンクＩＤを含むレコードをリンクテーブルから検索することを特徴とする請求項１記載の経路探索システム。
【請求項３】
出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索方法であって、
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを設け、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行い、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出し、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求めることを特徴とする経路探索システムの経路探索方法。
【請求項４】
前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込み、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクＩＤを読み込み、該接続リンクＩＤを含むレコードをリンクテーブルから検索することを特徴とする請求項３記載の経路探索方法。
【請求項５】
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部と、前記各構成を制御するコンピュータとを備え、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行う機能と、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出する機能と、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求める機能とを実現させることを特徴とする経路探索システムの経路探索プログラム。
【請求項６】
前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加した請求項５記載の経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込む機能と、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索する機能と、該検索されたレコードに格納された接続リンクＩＤを読み込む機能と、該接続リンクＩＤを含むレコードをリンクテーブルから検索する機能とを実現することを特徴とする請求項５記載の経路探索プロラム。
【請求項１】
出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムであって、
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、
該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、
該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、
該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを備えることを特徴とする経路探索システム。
【請求項２】
前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込み、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクＩＤを読み込み、該接続リンクＩＤを含むレコードをリンクテーブルから検索することを特徴とする請求項１記載の経路探索システム。
【請求項３】
出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索方法であって、
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部とを設け、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行い、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出し、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求めることを特徴とする経路探索システムの経路探索方法。
【請求項４】
前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加し、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込み、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索し、該検索されたレコードに格納された接続リンクＩＤを読み込み、該接続リンクＩＤを含むレコードをリンクテーブルから検索することを特徴とする請求項３記載の経路探索方法。
【請求項５】
出発駅，到着駅，出発駅から到着駅に至る所要時間，出発駅から到着駅に至る距離，これらを含むレコードに一意に割り振られたリンクＩＤとを格納するリンクテーブルと、該リンクテーブルに格納したレコードを入力とし、該レコードを基にダイクストラ法を用いて出発駅から到達駅に至る最も探索条件に合致した最優秀経路情報及び該最優秀経路情報を算出する経緯で得た複数の通過経路情報を保持する経路探索部と、該経路探索部が保持した通過経路情報から複数の生成経路情報を算出する経路生成部と、該複数の生成経路情報を用いて遺伝的アルゴリズムによる通過経路情報の補正を行う経路補正部と、前記各構成を制御するコンピュータとを備え、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルに格納した複数レコードを基にダイクストラ法を用いて出発駅から到達駅に至る複数の通過経路情報の探索を行って最優秀経路情報の探索及び複数の通過経路情報の保持を行う機能と、
前記経路生成部が、前記通過経路情報を基に複数の生成経路情報を算出する機能と、
前記経路補正部が、前記最優秀経路情報以外の経路から最優秀経路情報の代替経路を優秀な順に求める機能とを実現させることを特徴とする経路探索システムの経路探索プログラム。
【請求項６】
前記リンクテーブルの到着駅が出発駅となっている対応レコードの接続リンクＩＤ，乗換え時間，接続の種別を示す接続情報，これらを含むレコードに一意に割り当てられたブリッジＩＤとを格納するブリッジテーブルを設けると共に、前記リンクテーブルの到着駅が出発駅となっている対応レコードに前記ブリッジＩＤを追加した請求項５記載の経路探索システムの経路探索プログラムであって、
前記コンピュータに、
前記経路探索部が、リンクテーブルの到着駅が出発駅となっている対応レコードを検索する場合、前記リンクテーブルのレコードに格納されているブリッジＩＤを読み込む機能と、当該ブリッジＩＤを持つレコードをブリッジテーブルから検索する機能と、該検索されたレコードに格納された接続リンクＩＤを読み込む機能と、該接続リンクＩＤを含むレコードをリンクテーブルから検索する機能とを実現することを特徴とする請求項５記載の経路探索プロラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００７−８３８００（Ｐ２００７−８３８００Ａ）
【公開日】平成１９年４月５日（２００７．４．５）
【国際特許分類】
【出願番号】特願２００５−２７３１３２（Ｐ２００５−２７３１３２）
【出願日】平成１７年９月２１日（２００５．９．２１）
【出願人】（０００１５２９８５）株式会社日立情報システムズ (409)
【Ｆターム（参考）】
【公開日】平成１９年４月５日（２００７．４．５）
【国際特許分類】
【出願日】平成１７年９月２１日（２００５．９．２１）
【出願人】（０００１５２９８５）株式会社日立情報システムズ (409)
【Ｆターム（参考）】
[ Back to top ]