(57)【要約】【課題】　所定の経路上で運行される交通機関に関する情報を検索する際に、検索条件として経由駅が入力された場合、ユーザーのニーズに則した、利便性の高い経路検索サービスを提供する。【解決手段】　駅をノードとし、駅間の移動手段をアークとして表現された運行ネットワークを格納する情報データベース４と、出発駅、経由駅、目的駅等の検索条件に基づいて、該当する運行ネットワーク上のノード及びアークを検索する検索部３４と、検索部３４による検索結果内に、目的駅と経由駅が同一のノードであるループ経路が含まれる場合に、ループ経路を検索結果から削除するループ排除部３７と、ループ経路に含まれるアークの属性を検出し、検出された属性に応じて、ループ排除部３７による削除処理を禁止する判断部３６とを有する。【選択図】　　　図１
2004133927.tif 000002
【特許請求の範囲】
【請求項１】
　所定の経路上で運行される交通機関に関する情報を検索する交通情報検索システムであって、
　駅をノードとし、該駅間の移動手段をアークとして表現された運行ネットワークを格納する情報データベースと、
　出発駅、経由駅、目的駅等の検索条件に基づいて、該当する前記運行ネットワーク上のノード及びアークを検索する検索手段と、
　前記検索手段による検索結果内に、目的駅と経由駅が同一のノードであるループ経路が含まれる場合に、該ループ経路を該検索結果から削除するループ排除手段と、
　前記ループ経路に含まれる前記アークの属性を検出し、検出された属性に応じて、前記ループ排除手段による削除処理を禁止する判断手段と
を有することを特徴とする交通情報検索システム。
【請求項２】
　前記アークの属性は、普通、急行など、前記移動手段の停車駅数により定められていることを特徴とする請求項１に記載の交通情報検索システム。
【請求項３】
　前記アークの属性は、会社や自治体など、前記移動手段を運営する組織により定められていることを特徴とする請求項１又は２に記載の交通情報検索システム。
【請求項４】
　前記ループ排除手段は、経由駅で分割される各区間内で前記ループ経路を検出することを特徴とする請求項１乃至３に記載の交通情報検索システム。
【請求項５】
　所定の経路上で運行される交通機関に関する情報を検索する交通情報検索システムであって、
　駅をノードとし、該駅間の移動手段をアークとして表現された運行ネットワークを格納する情報データベースと、出発駅、経由駅、目的駅等の検索条件に基づいて、該当する前記運行ネットワーク上のノード及びアークを検索する検索手段と、
　前記ノードが、前記移動手段の通過駅であるときに、その経由駅をアーク上のノードとして追加するノード埋め込み手段と
を備え、
　前記検索手段は、前記ノード埋め込み手段によって追加されたノードを含めて検索を行うことを特徴とする交通情報検索システム。
【請求項６】
　前記ノード埋め込み手段は、前記ノードを追加する際に、ノードが追加される対象となるアークを削除し、追加されたノードとその最寄のノードとの間に新たなアークを形成することを特徴とする請求項５に記載の交通情報検索システム。
【請求項７】
　所定の経路上で運行される交通機関に関する情報を検索する交通情報検索方法であって、
　駅をノードとし、該駅間の移動手段をアークとして表現された運行ネットワークについて、出発駅、経由駅、目的駅等の検索条件に基づいて、該当するノード及びアークを検索する第１のステップと、
　前記第１のステップにおける検索結果内に、目的駅と経由駅が同一のノードであるループ経路が含まれる場合に、該ループ経路に含まれるアークの属性を検出する第２のステップと、
　前記第２のステップで検出された属性に応じて、該ループ経路を前記検索結果から削除する第３のステップと
を有することを特徴とする交通情報検索方法。
【請求項８】
　前記アークの属性は、普通、急行など、前記移動手段の停車駅数により定められていることを特徴とする請求項７に記載の交通情報検索方法。
【請求項９】
　前記アークの属性は、会社や自治体など、前記移動手段を運営する組織により定められていることを特徴とする請求項７又は８に記載の交通情報検索方法。
【請求項１０】
　前記第２のステップでは、経由駅で分割される各区間内で前記ループ経路を検出することを特徴とする請求項７乃至９に記載の交通情報検索方法。
【請求項１１】
　所定の経路上で運行される交通機関に関する情報を検索する交通情報検索方法であって、
　駅をノードとし、該駅間の移動手段をアークとして表現された運行ネットワークについて、前記ノードが、前記移動手段の通過駅であるときに、その経由駅をアーク上のノードとして追加する第１のステップと、
　前記第１のステップにおいて追加されたノードを含めた前記運行ネットワークについて、出発駅、経由駅、目的駅等の検索条件に基づいて、該当するノード及びアークを検索する第２のステップと
を有することを特徴とする交通情報検索方法。
【請求項１２】
　前記第１のステップでは、前記ノードを追加する際に、ノードが追加される対象となるアークを削除し、追加されたノードとその最寄のノードとの間に新たなアークを形成することを特徴とする請求項１１に記載の交通情報検索方法。
【請求項１３】
　所定の経路上で運行される交通機関に関する情報を検索する交通情報検索プログラムであって、コンピュータに、
　駅をノードとし、該駅間の移動手段をアークとして表現された運行ネットワークについて、出発駅、経由駅、目的駅等の検索条件に基づいて、該当するノード及びアークを検索する第１のステップと、
　前記第１のステップにおける検索結果内に、目的駅と経由駅が同一のノードであるループ経路が含まれる場合に、該ループ経路に含まれるアークの属性を検出する第２のステップと、
　前記第２のステップで検出された属性に応じて、該ループ経路を前記検索結果から削除する第３のステップと
を有する処理を実行させることを特徴とする交通情報検索プログラム。
【請求項１４】
　前記アークの属性は、普通、急行など、前記移動手段の停車駅数により定められていることを特徴とする請求項１３に記載の交通情報検索プログラム。
【請求項１５】
　前記アークの属性は、会社や自治体など、前記移動手段を運営する組織により定められていることを特徴とする請求項１３又は１４に記載の交通情報検索プログラム。
【請求項１６】
　前記第２のステップでは、経由駅で分割される各区間内で前記ループ経路を検出することを特徴とする請求項１３乃至１５に記載の交通情報検索プログラム。
【請求項１７】
　所定の経路上で運行される交通機関に関する情報を検索する交通情報検索プログラムであって、コンピュータに、
　駅をノードとし、該駅間の移動手段をアークとして表現された運行ネットワークについて、前記ノードが、前記移動手段の通過駅であるときに、その経由駅をアーク上のノードとして追加する第１のステップと、
　前記第１のステップにおいて追加されたノードを含めた前記運行ネットワークについて、出発駅、経由駅、目的駅等の検索条件に基づいて、該当するノード及びアークを検索する第２のステップと
を有する処理を実行させることを特徴とする交通情報検索プログラム。
【請求項１８】
　前記第１のステップでは、前記ノードを追加する際に、ノードが追加される対象となるアークを削除し、追加されたノードとその最寄のノードとの間に新たなアークを形成することを特徴とする請求項１７に記載の交通情報検索プログラム。
【請求項１９】
　所定の経路上で運行される交通機関において、出発駅から経由駅を経由して目的駅を移動する経路を検索する交通情報検索システムにおいて、
駅をノードとし、該駅間の移動手段をアークとして表現された運行ネットワークを格納する情報データベースと、
　出発駅、経由駅、目的駅の検索条件を取得して、前記運行ネットワークに該当する前記出発駅から前記経由駅を経由して前記目的駅を移動する最短パスの経路上のノード及びアークを検索する検索手段と、
　前記検索手段で検索された前記最短パスの経路において、前記出発駅と経由駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、前記出発駅から前記派生元ノードを経由した前記派生ノードまでの経路と、前記派生ノードから前記経由駅までの最短パスの経路と、前記経由駅から前記目的駅までの経路を併合して第Ｎ最短パスの経路として検索する第Ｎ最短パス検索手段
　を備えることを特徴とする交通情報検索システム。
【請求項２０】
　前記第Ｎ最短パス検索手段は、前記最短パスの経路において、前記経由駅と前記目的駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、前記出発駅から前記経由駅及び前記派生元ノードを経由した前記派生ノードまでの経路と、前記派生ノードから前記目的駅までの最短パスの経路を併合して第Ｎ最短パスの経路として検索する
　ことを特徴とする請求項１９に記載の交通情報検索システム。
【請求項２１】
前記検索条件として更に第２の経由駅が含まれている場合、前記第Ｎ最短パス検索手段は、前記運行ネットワークに該当する前記出発駅から前記経由駅及び前記第２の経由駅を経由して前記目的駅を移動する最短パスの経路上のノード及びアークを検索し、前記経由駅と前記第２の経由駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、前記出発駅から前記経由駅及び前記派生元ノードを経由した前記派生ノードまでの経路と、前記派生ノードから前記第２の経由駅までの最短パスの経路と、前記第２の経由駅から前記目的駅までの経路とを併合して第Ｎ最短パスの経路として検索する
　ことを特徴とする請求項１９に記載の交通情報検索システム。
【請求項２２】
　前記第Ｎ最短パス検索手段で検索された経路を更に派生させて、前記第Ｎ最短パスの経路として検索することを特徴とする請求項１９乃至２１のいずれか１項に記載の交通情報検索システム。
【請求項２３】
　所定の経路上で運行される交通機関において、出発駅から経由駅を経由して目的駅を移動する経路を検索する交通情報検索方法において、
検索手段によって、駅をノードとし、該駅間の移動手段をアークとして表現された運行ネットワークを格納する情報データベースを参照して、出発駅、経由駅、目的駅の検索条件を取得して、前記運行ネットワークに該当する前記出発駅から前記経由駅を経由して前記目的駅を移動する最短パスの経路上のノード及びアークを検索するステップと、
　第Ｎ最短パス検索手段によって、前記最短パスの経路において、前記出発駅と経由駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、前記出発駅から前記派生元ノードを経由した前記派生ノードまでの経路と、前記派生ノードから前記経由駅までの最短パスの経路と、前記経由駅から前記目的駅までの経路を併合して第Ｎ最短パスの経路として検索するステップ
　を備えることを特徴とする交通情報検索方法。
【請求項２４】
　前記第Ｎ最短パスの経路として検索するステップは、前記最短パスの経路において、前記経由駅と前記目的駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、前記出発駅から前記経由駅及び前記派生元ノードを経由した前記派生ノードまでの経路と、前記派生ノードから前記目的駅までの最短パスの経路を併合して第Ｎ最短パスの経路として検索する
　ことを特徴とする請求項２３に記載の交通情報検索方法。
【請求項２５】
　前記検索条件として更に第２の経由駅が含まれている場合、前記第Ｎ最短パスの経路として検索するステップは、前記運行ネットワークに該当する前記出発駅から前記経由駅及び前記第２の経由駅を経由して前記目的駅を移動する最短パスの経路上のノード及びアークを検索し、前記経由駅と前記第２の経由駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、前記出発駅から前記経由駅及び前記派生元ノードを経由した前記派生ノードまでの経路と、前記派生ノードから前記第２の経由駅までの最短パスの経路と、前記第２の経由駅から前記目的駅までの経路とを併合して第Ｎ最短パスの経路として検索する
　ことを特徴とする請求項２３に記載の交通情報検索方法。
【請求項２６】
　前記第Ｎ最短パスの経路として検索するステップで検索された経路を更に派生させて、前記第Ｎ最短パスの経路として検索することを特徴とする請求項２３乃至２５のいずれか１項に記載の交通情報検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、コンピュータを用いて、所定の経路上で運行される交通機関に関する情報を検索する技術に関し、例えば、出発地と目的地間の経路を検索する列車の乗り換え案内サービスに利用できる交通情報検索システム、交通情報検索方法及び交通情報検索プログラムに関する。
【背景技術】
【０００２】
　従来、コンピュータを用いて出発地、目的地、出発希望時刻等を入力すると、出発地から目的地に至る１つ又は複数の経路を表示（案内）するソフトウェアやインターネットサービスが存在する。
【０００３】
　このソフトウェアやインターネットサービスにおいては、例えば、列車の乗り換え案内の場合、出発駅、乗換駅、目的駅、利用路線又は利用列車等を検索条件とし、さらに、出発駅での発時刻、乗換駅での発／着時刻、目的駅での着時刻や、所要時間、料金等も検索条件とし、最短の経路（パス）を求めることができる（例えば、特許文献１乃至３参照）。
【０００４】
　このような経路検索において、第１〜ｋ最短パスを求めるアルゴリズムとしては、例えばＭａｒｔｉｎｓ　ｅｔ　ａｌ．のアルゴリズム（Ｅ．Ｑ．Ｖ．　Ｍａｒｔｉｎｓ　ｅｔ　ａｌ．，”Ａｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｒａｎｋｉｎｇ　ｌｏｏｐｌｅｓｓ　ｐａｔｈｓ”，Ｒｅｓｅａｒｃｈ　ｒｅｐｏｒｔ　，Ｕｎｉｖ　ｄｅ　Ｃｏｉｍｂｒａ　１９９９）が知られている（非特許文献１参照）。以下にこのアルゴリズムの概要を述べる。
【０００５】
　このアルゴリズムにおいては、駅をノードとし、ノード間をアークで接続した運行ネットワークを用い、各アークに重み（コスト、移動時間等）を割り振り、重みを計算することにより検索を行う。
【０００６】
　図１２に示すように、運行ネットワークにおいて、出発ノードｓから目的ノードｔへのパスを考える場合、ｓからｔへの第ｉ番目に短いパスをｓからｔへの第ｉ最短パスとし、第１最短パスをいわゆる最短パスとする。この最短パスは、例えばダイクストラ法によって高速に算出することができる。第２以降の最短パスを求めるアルゴリズムについても古くから研究され、種々の効率良いアルゴリズムが提案されている。
【０００７】
　第１〜ｋの最短パスを求める際に、ループ（閉路）を許す場合と、許さない場合とがある。ここで、ループを許すとは、図１２に示すように、同じノードｒを２度以上通るような冗長なパスも第ｉ最短パスとして採用するというものである。
【０００８】
　Ｍａｒｔｉｎｓ　ｅｔ　ａｌ．のアルゴリズムは、基本的にループを許さない場合のアルゴリズムの１つである。このアルゴリズムは、まずダイクストラ法で目的ノードｔを根に持つ最短パス木を作り、最短パスをヒープに蓄える（ダイクストラ法、最短パス木、ヒープについては、例えば浅野孝夫著「情報の構造（下）」、日本評論社（非特許文献２）を参照）。次にｋ：＝０として次の処理（ｉ）、（ii）を繰り返す。
【０００９】
（ｉ）ヒープからコスト最小のパスｐを抜き出す。もしｐがループを含まないならば、ｐを第ｋ＋１パスとして登録し、ｋに１を加算する。ｋ＝ｋなら終了する。
【００１０】
（ii）ｐがループを含む／含まないに関わらず、ｐに対する派生パス（１歩横にそれて、そこから最短パス木上のアークを一気に進むパス）をｐ上の各ノードにつき高々１つずつ求め、ヒープに蓄える。）。（ｉ）に戻る。
【００１１】
　派生パスを作る際のアーク、つまり元のパスｐから１歩横にそれる際のアークの選び方がポイントである。上記の説明はあくまで概要であり、詳細は前記論文に述べられている。
【００１２】
　また、在来線と平行している特急停車駅を経由駅としたときの従来の処理について、図１３及び図１４を用いて説明する。
【００１３】
　図１３に示すように特急路線Ｌ２と在来線Ｌ１が平行して運行されている場合に、ユーザーが特急通過駅を経由駅として指定して経路を探索することがある。
【００１４】
　このとき、従来の探索処理では、実際に停車可能な駅のみを探索するため、図１４に示すように、特急路線Ｌ１から経由駅を含む在来線Ｌ２に乗り換える経路が検出され、経由駅を単に通過する特急路線Ｌ１のみの経路は、検索結果から除外される。
【特許文献１】特開２００２−１４１９４３号公報
【特許文献２】特開２００１−３４６６３号公報
【特許文献３】特許第３１７６００９号公報
【非特許文献１】E.Q.V. Martins et al.,"An algorithm for ranking loopless paths",Research report ,Univ de Coimbra,1999
【非特許文献２】浅野孝夫著「情報の構造（下）」、日本評論社
【発明の開示】
【発明が解決しようとする課題】
【００１５】
　しかしながら、上述した従来のループ判定方法では、アークの属性によらず一律にループ経路を削除するものであるため、同じノード（すなわち駅）を異なるアーク（すなわち路線）で通るときにもループ経路であるとして、有効な経路とはみなされなくなるという問題点がある。
【００１６】
　つまり、在来線で１回通った駅を今度は新幹線で通る場合や、異なる会社の路線で通る場合などでもループを含んだ経路として検索結果から落としてしまうことになる。このように経由駅指定時は無条件にループ経路を落としてしまうと、在来線（各駅停車）で特急の始発駅まで行って、始発の特急に乗車するなどの経路が求まらないといった問題が生じる。
【００１７】
　また、図１３に示したような、在来線と平行している特急停車駅を経由駅としたときの従来の処理では、上述したように、実際に停車可能な駅のみを探索するため、ユーザーが経由駅を下車駅でなく単に通過駅として入力した場合にも、図１４のように特急から在来線に乗り換える経路が検出されてしまうことがあった。この結果、ユーザーは、経由駅に急行が停車するのかしないのかを意識して検索条件を入力する必要があり、「概ねこの辺りの駅を通過して目的に行きたい」といったあいまい検索ができないという問題がある。
【００１８】
　そこで、本発明は、上述の課題に鑑みてなされたものであり、所定の経路上で運行される交通機関に関する情報を検索する際に、検索条件として経由駅が入力された場合、ユーザーのニーズに則した、利便性の高い経路検索サービスを提供することのできる交通情報検索システム、交通情報検索方法及び交通情報検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
　上記課題を解決するために、本発明は、所定の経路上で運行される交通機関に関する情報を検索する際に、駅をノードとし、駅間の移動手段をアークとして表現された運行ネットワークについて、出発駅、経由駅、目的駅等の検索条件に基づいて、該当するノード及びアークを検索し、この検索結果内に目的駅と経由駅が同一のノードであるループ経路が含まれる場合に、ループ経路に含まれるアークの属性を検出し、この検出された属性に応じてループ経路を検索結果から削除する。なお、上記発明においては、アークの属性は、普通、急行など移動手段の停車駅数や、会社や自治体など移動手段を運営する組織により定められていることが好ましい。
【００２０】
　このような本発明によれば、検索条件として経由駅が入力された場合、路線におけるループ経路を検出するとともに、そのループ経路を構成する路線の属性に応じて検索結果から除外する。例えば、同じ会社同士や在来線同士など、属性が同一であるループ経路を検索結果から除外して無効とし、不要なループ経路がユーザーに提示されるのを回避することができる。
【００２１】
　上記発明においては、経由駅で分割される各区間内でループ経路を検出することが好ましい。この場合には、各区間毎にループ経路の検出を行うため、ループ検索処理の対象路線が不必要に拡大するのを防止することができ、処理が遅延するのを防止しつつ、適切な経路の探索を行うことができる。
【００２２】
　なお、上記発明において、ループ経路を削除した場合には、その旨を通知するメッセージをユーザーに提示したり、再入力を促す処理を行うことが好ましい。
【００２３】
　また、他の発明は、所定の経路上で運行される交通機関に関する情報を検索する際に、駅をノードとし駅間の移動手段をアークとして表現された運行ネットワークについて、ノードが移動手段の通過駅であるときに、その経由駅をアーク上のノードとして追加し、この追加されたノードを含めた運行ネットワークについて、出発駅、経由駅、目的駅等の検索条件に基づいて、該当するノード及びアークを検索する。なお、この他の発明においては、ノードを追加する際に、ノードが追加される対象となるアークを削除し、追加されたノードとその最寄のノードとの間に新たなアークを形成することが好ましい。
【００２４】
　このような他の発明によれば、実際には特急等が停車しない駅を仮想駅として新たなノードとして追加するため、特急通過駅を経由駅に指定された場合であっても、従来の経路探索アルゴリズムに大きな変更を加えることなく、特急路線を含めた経路探索結果を出力することができる。この結果、ユーザーは、経由駅として指定した駅に急行等が停車するのか否かを意識することなく検索条件を入力することができる。
【００２５】
　更に本発明は、所定の経路上で運行される交通機関において、出発駅から経由駅を経由して目的駅を移動する経路を検索する交通情報検索システムにおいて、駅をノードとし、該駅間の移動手段をアークとして表現された運行ネットワークを格納する情報データベースと、出発駅、経由駅、目的駅の検索条件を取得して、運行ネットワークに該当する出発駅から経由駅を経由して目的駅を移動する最短パスの経路上のノード及びアークを検索する検索手段と、検索手段で検索された最短パスの経路において、出発駅と経由駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、出発駅から派生元ノードを経由した派生ノードまでの経路と、派生ノードから経由駅までの最短パスの経路と、経由駅から目的駅までの経路を併合して第Ｎ最短パスの経路として検索する第Ｎ最短パス検索手段を備える。
【００２６】
　このような本発明によれば、求められた最短パスの一部のノードを派生させることにより、容易に第Ｎ最短パスを求めることができる。
【００２７】
　又、第Ｎ最短パス検索手段は、最短パスの経路において、経由駅と目的駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、出発駅から経由駅及び派生元ノードを経由した派生ノードまでの経路と、派生ノードから目的駅までの最短パスの経路を併合して第Ｎ最短パスの経路として検索してもよい。
【００２８】
　そして、検索条件として更に第２の経由駅が含まれている場合、第Ｎ最短パス検索手段は、運行ネットワークに該当する出発駅から経由駅及び第２の経由駅を経由して目的駅を移動する最短パスの経路上のノード及びアークを検索し、経由駅と第２の経由駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、出発駅から経由駅及び派生元ノードを経由した派生ノードまでの経路と、派生ノードから第２の経由駅までの最短パスの経路と、第２の経由駅から目的駅までの経路とを併合して第Ｎ最短パスの経路として検索しても良い。
【００２９】
　更に、第Ｎ最短パス検索手段で検索された経路を更に派生させて、前記第Ｎ最短パスの経路として検索しても良い。これにより、多数の第Ｎ最短パスを検索することができ、これらのパスに重みをつけることにより、第２最短パス、第３最短パス…と求めることができる。
【発明の効果】
【００３０】
　本発明に係る交通情報検索システム、交通情報検索方法及び交通情報検索プログラムによれば、所定の経路上で運行される交通機関に関する情報を検索する際に、検索条件として経由駅が入力された場合、ユーザーのニーズに則した利便性の高い経路検索サービスを提供することができる。
【００３１】
　すなわち、検索条件として経由駅が入力された場合、路線におけるループ経路を検出し、同じ会社や、在来線同士以外のループ経路を検索結果から除外して無効とすることができ、ユーザーにとって利便性の高い経路を出力することができる。また、本発明によれば、特急通過駅を経由駅に指定されたときにも特急路線を含めた経路探索結果を出力することができる。
【発明を実施するための最良の形態】
【００３２】
　本発明に係る交通情報検索システムの第１実施形態について図を参照しつつ説明する。
【００３３】
（交通情報検索システムの構成）
　図１は、本実施形態に係る交通情報検索システムの全体構成を模式的に示す機能ブロック図である。
【００３４】
　図１（ａ）に示すように、本実施形態に係る交通情報検索システムは、ユーザーが使用し、インターネット２に接続可能なユーザー端末１と、インターネット２に接続され、情報データベース４を備えた交通情報検索サーバ３とから構成される。
【００３５】
　ユーザー端末１は、パーソナルコンピュータやＰＤＡ、移動電話等の通信機能を備えた端末装置である。インターネット２は、通信機器を通信回線で相互に接続して構築される通信ネットワークの一形態であり、ＬＡＮやＷＡＮなども含む概念である。
【００３６】
　交通情報検索サーバ３は、インターネット２を介して鉄道の乗り換え情報など、所定の経路上で運行される交通機関に関する情報を情報データベース４から検索し、提供するデータベースサーバである。情報データベース４は、駅をノードとし、駅間の移動手段をアークとして表現された運行ネットワークを格納するデータベースである。
【００３７】
　具体的に、交通情報検索サーバ３は、図１（ｂ）に示すように、通信部３１と、データ変換部３２と、条件解析部３３と、検索部３４と、属性判定部３５と、判断部３６と、ループ排除部３７と、ノード埋込部３８とを備えている。
【００３８】
　通信部３１は、インターネット２に接続し、所定のプロトコルを通じてパケット等のデータを送受信することにより、ユーザー端末１に対してサービスを提供する通信モジュールである。データ変換部３２は、通信部３１で送受信されるデータを変換するモジュールであり、通信部３１で受信されたデータを変換して条件解析部３３に出力するとともに、検索結果を通信部３１で送信可能なデータ形式に変換し、通信部３１に出力する。
【００３９】
　条件解析部３３は、ユーザー端末１から送信された検索条件を解析し、解析結果を検索部３４に送出するモジュールである。
【００４０】
　検索部３４は、出発駅、経由駅、目的駅等の検索条件に基づいて、情報データベース４から、該当する運行ネットワーク上のノード及びアークを検索し、最短パス木の作成・探索を実行するモジュールである。なお、本実施形態において検索部３４は、ノード埋込部３８を介して情報データベース４に接続されており、ノード埋込部３８によって追加されたノードを含めて検索を行う機能を有する。
【００４１】
そして、この検索部３４による検索結果は、属性判定部３５に受け渡される。
【００４２】
　属性判定部３５は、検索部３４による検索結果に含まれるアークの属性を検出し、その検出結果を判断部３６に出力するモジュールである。
【００４３】
　判断部３６は、属性判定部３５による判定結果に基づいて、検索部３４で検出されたループ経路を削除すべきか否かを判断するモジュールである。本実施形態において判断部３６は、ループ経路内のアークの属性が、往路と復路とで異なる場合にループ排除部３７による削除処理を禁止する機能を有する。なお、本実施形態において、アークの属性は、普通、急行など、前記移動手段の停車駅数や、会社や自治体など、前記移動手段を運営する組織により定められる。
【００４４】
　ループ排除部３７は、検索部３４による検索結果に対してループチェックを実行するモジュールであり、このループチェックによって、検索結果内に、目的駅と経由駅が同一のノードであるループ経路が含まれる場合に、このループ経路を検索結果から削除する。具体的には、検索部３４による検索結果を属性判定部３５及び判断部３６を介して受け取るとともに、属性判定部３５による判定結果を取得し、これらに基づいて、ループ経路の検出を行う。また、このループ排除部３７は、経由駅で分割される各区間内で前記ループ経路を検出する機能を備えている。
【００４５】
　ノード埋込部３８は、ノードが経由駅であり、この経由駅が移動手段の通過駅であるときに、その経由駅をアーク上のノードとして追加するモジュールである。具体的に、このノード埋込部３８は、ノードを追加する際に、ノードが追加される対象となるアークを削除し、追加されたノードとその最寄のノードとの間に新たなアークを形成する。
【００４６】
（運行ネットワーク）
　次いで、上記情報データベース４に格納された運行ネットワークについて説明する。
【００４７】
　運行ネットワークは、図３に示すように、駅をノードとし、駅間の移動手段をアークとして、ノードをアークで接続したデータであり、路線図や駅間の所要時間等のデータをもとに作成する。
【００４８】
　路線間の乗り換えには、同じ駅で乗り換える場合と、異なる駅間を徒歩により移動して乗り換える場合とがある。同じ駅での乗り換えについては、駅をクリーク化する。このクリーク化とは、駅を複数の分岐ノード（駅に接続する路線数に相当するノード）の集合で表し、その分岐ノード間に乗り換えアークを張って乗り換え時間を付す。ここでは、同一駅内にある分岐ノードをクリーク駅と呼び、同一駅内の乗り換えを乗り換えアークで表現する。
【００４９】
　異なる駅での乗り換えについては、新たに徒歩アークを設ける。乗り換えアークも徒歩アークも徒歩による移動であるが、本実施形態では区別して用いる。なお、本実施形態では、本来の駅とクリーク駅を区別するために、本来の駅を本来駅と称し、実際の駅に相当するノードは本来駅である。また、本来駅内に複数の路線が接続され、同一駅内において乗り換えが可能であるときには、複数のクリーク駅が本来駅内に包含されて、それぞれ運行ネットワーク上に表現される。
【００５０】
　従って、運行ネットワークとは、全ての駅をノードに持ち、駅間の全ての路線又は徒歩乗り換えをアークに持つネットワークを指す。但し、徒歩以外に２つ以上の異なる路線が接続している駅はクリーク化され、その駅に接続する路線毎にクリーク駅としてノード化されている。
【００５１】
　また、徒歩乗り換えのアークには、前述したように徒歩アークと乗り換えアークがある。路線の各アークには、路線名、上り／下りのフラグ、平均所要時間（コスト）等が付されている。徒歩アーク又は乗り換えアークには、それを識別するためのフラグや、移動又は乗り換え時間（コスト）が付されている。徒歩アーク又は乗り換えアークが接続するノードをＡの分岐ノードと呼ぶ。クリーク駅は全て分岐ノードである。
【００５２】
（交通情報検索方法）
　上述した構成を有する交通情報検索システムを用いた交通情報検索方法は、以下の手順による。図２は、本実施形態に係る交通情報検索方法の手順を示すフローチャート図である。
【００５３】
　ステップＳ１０では、ユーザーが、自己が使用するユーザー端末１を通じて、検索条件である乗車駅、下車駅、経由駅、出発・到着時刻等を通信部３１により受信し、データ変換部３２でデータ変換をした後、条件解析部３３により解析を行う。これと併せて、検索部３４は、情報データベース４から運行ネットワークデータや、時刻表データ等を読み込む。
【００５４】
　次いで、ステップＳ２０では、検索部３４において、最短パス木を作成し（Ｓ２１）、最短パス木の探索し（Ｓ２２）、第ｉ最短パスの探索（Ｓ２３）、ループチェックを行い（Ｓ２４）、第ｉ最短パスを短縮して第ｉ最短経路を得る（Ｓ２５）という一連の処理を行う。
【００５５】
　次いで、ステップＳ３０では、時間割り当て処理を行う。この時間割当て処理では、各経路に対して時刻表を照らし合わせながら時間割り当てを行い、料金を計算する。ステップＳ４０では、時刻と料金が割り当てられた経路の中から、所要時間等の優先基準に基づき、上位複数の経路を選択して出力する。この出力は、
　前記ステップＳ２２における経路探索アルゴリズムでは、まず、検索条件である乗車駅名と下車駅名、経由駅名に対して、それらの本来駅番号をそれぞれ求める。それらの駅がクリーク化されている場合は、クリーク内の代表クリーク駅の番号を求める（クリーク内の他のクリーク駅の番号は、代表クリーク駅の番号に続く連番であるとする）。駅がクリーク化されていない場合は、本来駅を代表クリーク駅とみなす。
【００５６】
　このステップＳ２２では、次に、乗車駅の代表クリーク駅から経由駅１の代表クリーク駅までの第１最短パスを求める。次に経由駅１の代表クリーク駅から経由駅２の代表クリーク駅までの第１最短パスを求める。最後の経由駅ｎから下車駅の代表クリーク駅に至る第ｋ最短パスを求める（例えばＭａｒｔｉｎｓ　ｅｔ　ａｌ．のアルゴリズムを用いて求める）。このようにして第１最短パスを求めた状態が図４である。
【００５７】
　次に、ステップＳ２３における、第２以降のパスを求める方法について図５を用いて説明する。まず乗車駅から経由駅１までの最短パスｉからパスを派生させる。このときに派生させたノードから経由駅１まではその派生ノードからの最短パスによって接続する。こうして求めた経路をヒープに加えるなどの方法により処理する。
【００５８】
　経由駅ｉから経由駅iiまでの間で派生させた場合には、その派生ノードから経由駅２までの最短パスによって接続する。このような派生処理を行うことによって、常に経由駅を通る経路のみを求めることができる。ここで行う第２移行のパスを求める方法について、後に詳述する。
【００５９】
　次に、上述したステップＳ２４におけるループを検出する処理について図６及び図７を用いて説明する。本実施形態では、ループを検出する処理は２段階となっている。まず第１段階では、第１−ｋ最短パスをＭａｒｔｉｎ　ｅｔ　ａｌ．のアルゴリズムにより求めているときにチェックし、第２段階ではそれらのパスが最終的に求まり、時間割り当て処理を行う（Ｓ３０）際、それらの経路データを渡すときに行う。
【００６０】
　第１段階のループチェック処理では、乗車駅―経由駅１間、経由駅１−経由駅２間、経由駅２−経由駅３間、経由駅３−下車駅間でそれぞれループをチェックする。図６の場合は、経由駅２−経由駅３間でループしているため、この経路は無効と判定し、検索結果から削除する。一方、図７に示すように経由駅１−経由駅２間の駅と経由駅３−下車駅間で同一の駅が存在してもそのときにはループとは判定せず、削除処理を禁止する。これは図７の経路自体にループが含まれていてもそれをＭａｒｔｉｎ　ｅｔ　ａｌ．のアルゴリズムを用いてさらに派生させたときにはループを含まなくなり、有効な経路となる可能性があるためである。
【００６１】
　第２段階では図７のような経路はループ経路として削除の対象となる。またその第２段階のループチェック処理においては、その駅を通っている路線の両方が在来線でかつ同じ会社であるかどうかを判定して、真のときにはループ経路として無効とするが、偽のときにはループ経路とはみなさずに有効な経路として出力するようにする。
【００６２】
　以上の処理によって、在来線と新幹線、在来線と特急路線、会社が異なるループ経路を出力し、同じ会社の在来線のループ経路を無効にすることができ、ユーザーにとって利便性の高い経路を出力することができる。
【００６３】
（ノード埋込処理）
　次に、上述したノード埋込部３８によるノード埋込処理について説明する。ここでは、特急駅と平行した在来線の特急通過駅を経由駅として指定した場合を例に説明する。
【００６４】
　図８に示すように、経由駅５３が、経由駅５３を含む在来線Ｌ１と平行する特急路線Ｌ２の通過駅だったときには、経由駅５３に相当する仮想駅５４を特急路線Ｌ２上において推定し、この仮想駅５４の最寄の特急通過駅（ここでは、駅５５，５６）を割り出して、その間にクリークノードとして埋め込むようにする。
【００６５】
　このとき、この埋め込み処理によって上下線２つのアーク１０３，１０４の代わりに、図９に示すように、新たにアーク１０７，１０８，１０９，１１０を接続する。また、本実施形態に係る埋込処理では、クリークノード内に乗り換えアーク５２も追加する。このアーク５２は、その属性を乗り換え禁止アークとしてもよいし、アークの重みを大きくして実質上、乗換駅の対象外となるようにしてもよい。
【００６６】
　このような埋め込み処理によって特急路線Ｌ２上についても、図１０に示すように、経由駅を通るようになるため、経路探索の結果、特急が停車しない経由駅を検索対象として入力した場合であっても、特急路線を探索結果に含めて出力することができる。
【００６７】
（交通情報検索プログラム）
　なお、上述した実施形態においては、インターネット２を通じて、検索サービスを提供する場合を例に説明したが、本発明はこれに限定されるものではなく、例えば、検索条件入力用のユーザー端末１と、情報データベース４と、交通情報検索サーバ３を単一の端末とし、この端末上でスタンドアローン形式で実行されるアプリケーションにより実現することも可能である。
【００６８】
　このアプリケーションは、所定のプログラミング言語で表現されたプログラムとすることができる。すなわち、ユーザーが使用するパーソナルコンピュータや、ＰＤＡ等の端末のメモリやハードディスク内に上述した運行ネットワークを格納しておく。
【００６９】
　そして、端末上において、ユーザーが入力した出発駅、経由駅、目的駅等の検索条件に基づいて、該当するノード及びアークを検索するステップと、第１のステップにおける検索結果内に、目的駅と経由駅が同一のノードであるループ経路が含まれる場合に、ループ経路に含まれるアークの属性を検出する第２のステップと、第２のステップで検出された属性に応じて、ループ経路を検索結果から削除する第３のステップとを有する処理を実行させる。
【００７０】
　なお、本実施形態において上記第２のステップでは、経由駅で分割される各区間内でループ経路を検出する。
【００７１】
　また、上記第３のステップにおいては、ループ経路内のアークの属性が、往路と復路とで異なる場合に削除処理を禁止する。この削除禁止処理は、例えば、アークの属性として、普通、急行など、移動手段の停車駅数や、会社や自治体など、移動手段を運営する組織により定める。
【００７２】
　また、前記第１のステップにおける検索に際して、ノードが、急行の通過駅である場合などに、その経由駅をアーク上のノードとして追加し、この追加されたノードを含めて検索を行う。このノードを追加する際には、ノードが追加される対象となるアークを削除し、追加されたノードとその最寄のノードとの間に新たなアークを形成する。
【００７３】
　そして、このような交通情報検索プログラムは、インターネット等の電気通信回線を介して配信することができるとともに、図１１に示すような、ユーザー端末１で読み取り可能な記録媒体２１６〜２１９に記録することができる。すなわち、同図に示すような、フレキシブルディスク２１６やカセットテープ２１９等の磁気記録媒体、若しくはＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の光ディスク２１７の他、ＲＡＭカード２１８などのコンピュータで読み取り可能な記録媒体に記録することができる。
【００７４】
　このような交通情報検索プログラムを記録したコンピュータ読み取り可能な記録媒体によれば、ユーザーのニーズに則した、利便性の高い経路検索を可能とすることができるという有用なソフトウェアの保存、運搬及びインストールを容易に行うことができ、交通情報の検索をより迅速且つ簡便なものとすることができる。
【００７５】
　次に、本発明の最良の実施の形態において、第Ｎ最短パスの経路を検索する場合について詳述する。
【００７６】
　図１（ｂ）に示した検索部３４は、図示しないが第Ｎ最短パス検索手段と第２最短パス検索手段を備える。
【００７７】
　第Ｎ最短パス検索手段は、検索手段３４で検索された最短パスの経路において、出発駅と経由駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、出発駅から派生元ノードを経由した派生ノードまでの経路と、派生ノードから経由駅までの最短パスの経路と、経由駅から目的駅までの経路を併合して第Ｎ最短パスの経路として検索する手段である。
【００７８】
　又、第Ｎ最短パス検索手段は、最短パスの経路において、経由駅と目的駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、出発駅から経由駅及び派生元ノードを経由した派生ノードまでの経路と、派生ノードから目的駅までの最短パスの経路を併合して第Ｎ最短パスの経路として検索しても良い。
【００７９】
　更に、検索条件として更に第２の経由駅が含まれている場合、第Ｎ最短パス検索手段は、運行ネットワークに該当する出発駅から経由駅及び第２の経由駅を経由して目的駅を移動する最短パスの経路上のノード及びアークを検索し、経由駅と第２の経由駅の間の任意の派生元ノードから任意の派生ノードまでアークを派生し、出発駅から経由駅及び派生元ノードを経由した派生ノードまでの経路と、派生ノードから第２の経由駅までの最短パスの経路と、第２の経由駅から目的駅までの経路とを併合して第Ｎ最短パスの経路として検索しても良い。
【００８０】
　即ち、第Ｎ最短パス経路は、最短パス経路上の任意の派生元ノードから派生ノードに経路を派生させ、派生元ノードが次に到達すべき経由駅或いは目的駅までの最短パス経路を求める。この様に最短パスを利用して、最短パスから一部を派生させた経路を求めることにより、第２、第３最短パスを求めることができる。
【００８１】
　又、第Ｎ最短パス検索手段で検索された経路を更に派生させて、前記第Ｎ最短パスの経路として検索しても良い。
【００８２】
　第２最短パス取得手段は、第Ｎ最短パス検索手段で検索された複数の第Ｎ最短パスの経路についてコストを付与し、第２最短パスの経路を取得する手段である。第Ｎ最短パス検索手段で検索された経路のそれぞれについてコストを割り当て、コストの降順に並べることにより、第２最短パス経路、第３最短パス経路…を取得することができる。
【００８３】
　ここでは、第Ｎ最短パス検索手段において複数の第Ｎ最短パスを求めてから、コストを付与して第２最短パス経路を取得するように記載したが、この処理の順序はこれに限らない。即ち、第Ｎ最短パス検索手段において第Ｎ最短パスが求められるたびにコストを付与して、重みの降順に並べ、第Ｎ最短パス検索手段が終了してから、重み順に並んだ経路を参照して第２最短パス経路を取得しても良い。
【００８４】
　この様に、最短パス経路を有効に活用することにより、容易に第Ｎ最短パスを求めることができる。更に、求められた第Ｎ最短パスを利用して別の第Ｎ最短パスを求めることにより、容易に複数の経路を求めることができる。
【図面の簡単な説明】
【００８５】
【図１】実施形態に係る交通情報検索システムの構成を示すブロック図である。
【図２】実施形態に係る交通情報検索方法の手順を示すフロー図である。
【図３】実施形態に係る運行ネットワークの説明図である。
【図４】実施形態に係る経路探索処理の説明図である。
【図５】実施形態に係る経路探索処理の説明図である。
【図６】実施形態に係るループ経路排除処理の説明図である。
【図７】実施形態に係るループ経路排除処理の説明図である。
【図８】実施形態に係るノード追加処理の説明図である。
【図９】実施形態に係るノード追加処理の説明図である。
【図１０】実施形態に係るノード追加処理の説明図である。
【図１１】実施形態に係る交通情報検索プログラムを記録したコンピュータ読み取り可能な記録媒体の説明図である。
【図１２】従来の交通情報検索方法において、ループ経路探索の概要を示す説明図である。
【図１３】従来の交通情報検索方法において、在来線と特急路線とが平行している場合の経路探索の概要を示す説明図である。
【図１４】従来の交通情報検索方法において、在来線と特急路線とが平行している場合の経路探索の概要を示す説明図である。
【符号の説明】
【００８６】
　１…ユーザー端末
　２…インターネット
　３…交通情報検索サーバ
　４…情報データベース
　３１…通信部
　３２…データ変換部
　３３…条件解析部　３４…検索部
　３５…属性判定部
　３６…判断部
　３７…ループ排除部
　３８…ノード埋込部
　５１，５２…アーク
　５３…経由駅
　５４…仮想駅
　５５，５６…駅
　１０３，１０４，１０７，１０８，１０９，１１０…アーク
　２１６…フレキシブルディスク
　２１７…光ディスク
　２１８…ＲＡＭカード
　２１９…カセットテープ
　Ｌ１…在来線
　Ｌ２…特急路線
【図１】
2004133927.tif 000003
【図２】
2004133927.tif 000004
【図３】
2004133927.tif 000005
【図４】
2004133927.tif 000006
【図５】
2004133927.tif 000007
【図６】
2004133927.tif 000008
【図７】
2004133927.tif 000009
【図８】
2004133927.tif 000010
【図９】
2004133927.tif 000011
【図１０】
2004133927.tif 000012
【図１１】
2004133927.tif 000013
【図１２】
2004133927.tif 000014
【図１３】
2004133927.tif 000015
【図１４】
2004133927.tif 000016