経路探索システム、経路探索方法および経路探索プログラム
【課題】鉄道経路網において、少ない負荷で時刻表を加味した経路探索を実現することができる経路探索システムを提供する。
【解決手段】経路探索システムにおいて、出発駅、到着駅、出発駅から到着駅の間を走行する列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータ１０３と、リンクデータ１０３と関連付けるための第２のリンクＩＤ、第２のリンクＩＤに対応した列車の運転日および列車の１日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータ１０４と、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する時刻表ビットパターンデータ１０４の各ビットを検索し、探索対象の出発駅から到着駅に至る経路を取得する経路探索部１０２とを備えた。
【解決手段】経路探索システムにおいて、出発駅、到着駅、出発駅から到着駅の間を走行する列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータ１０３と、リンクデータ１０３と関連付けるための第２のリンクＩＤ、第２のリンクＩＤに対応した列車の運転日および列車の１日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータ１０４と、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する時刻表ビットパターンデータ１０４の各ビットを検索し、探索対象の出発駅から到着駅に至る経路を取得する経路探索部１０２とを備えた。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発駅から目的駅までの最適な経路を取得する経路探索システム、経路探索方法および経路探索プログラムに関し、特に少ない負荷で処理可能な技術に関するものである。
【背景技術】
【０００２】
鉄道経路網において、出発駅から目的駅に到達するまでの経路は多数存在しており、これらの経路の中から最適な経路を導出するための手法として、例えば特開平１１−４４５４７号公報（特許文献１）や、特開２００７−８３８００号公報（特許文献２）等に記載のものがある。
【０００３】
これらの技術は、各駅間に一定のコストを設定し、当該コストを用いて経路探索を行っているが、鉄道経路網においては、列車は時刻表に従って運行しており、各駅間のコストは一定ではないため、導出された経路について時刻表を加味した場合、最適な経路でない可能性がある。
【０００４】
一般的な鉄道経路探索では、以下のような手法となる。
（１）上記特許文献１や、特許文献２の技術を用い、各駅間に平均的な所要時間を設定した鉄道経路ネットワークを生成し、経路探索を実施する。
（２）（１）で求まった経路に対し、経路探索条件として指定された時刻に対して最適となる時刻表を設定する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１１−４４５４７号公報
【特許文献２】特開２００７−８３８００号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、前述した一般的な鉄道経路探索の場合、（１）の段階では時刻表を考慮しない探索となるため、臨時列車等の平均的に運行していない列車についての最適な探索が困難である。時刻表を直接探索するという選択もあるが、時刻表データは膨大であるため、探索負荷が大きく、性能面で問題がある。
【０００７】
また、鉄道経路網（空路、バス、船舶等の交通網も含む）は、出発駅、到着駅、列車、出発駅から到着駅に至る所要時間、距離等の駅間列車情報を表す「リンク」と、前記リンクで表現されるネットワーク上を実際に運行する列車の発着時刻（出発駅ＸＸ時ＸＸ分出発〜到着駅ＸＸ時ＸＸ分到着）を表す「時刻表」で構成されている。
【０００８】
前記時刻表は、例えばリンクＡ駅→Ｂ駅に対して、０６：００出発、０６：３０出発、・・・というように、１つのリンクに対して複数存在している。日本全国の鉄道に対する時刻表データのレコード数は膨大であり、またリンクと時刻表が１対多の関係であることが、時刻表を加味して経路探索を行うことを困難にしている。
【０００９】
以上のように、従来の技術では、鉄道経路網（空路、バス、船舶等の交通網も含む）において、時刻表を加味した経路探索を少ない探索負荷で実施することは困難であった。
【００１０】
そこで、本発明の目的は、鉄道経路網において、少ない負荷で時刻表を加味した経路探索を実現することができる経路探索システム、経路探索方法および経路探索プログラムを提供することにある。
【００１１】
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１２】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次の通りである。
【００１３】
すなわち、代表的なものの概要は、経路探索システムにおいて、出発駅、到着駅、出発駅から到着駅の間を走行する列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、リンクデータと関連付けるための第２のリンクＩＤ、第２のリンクＩＤに対応した列車の運転日および列車の１日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータと、探索対象の出発駅から到着駅に至るリンクデータの複数のレコードに対応する時刻表ビットパターンデータの各ビットを検索し、探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部とを備えたものである。
【００１４】
また、経路探索方法において、出発駅、到着駅、列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、リンクデータと関連付けるための第２のリンクＩＤ、第２のリンクＩＤに対応した列車の運転日および列車の１日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有し、経路探索部により、探索対象の出発駅から到着駅に至るリンクデータの複数のレコードに対応する時刻表ビットパターンデータの各ビットを検索し、探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得するものである。
【００１５】
また、経路探索プログラムにおいて、出発駅、到着駅、列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、リンクデータと関連付けるための第２のリンクＩＤ、第２のリンクＩＤに対応した列車の運転日および列車の１日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有したコンピュータ上で実行され、コンピュータを、探索対象の出発駅から到着駅に至るリンクデータの複数のレコードに対応する時刻表ビットパターンデータの各ビットを検索し、探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部として機能させるものである。
【発明の効果】
【００１６】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下の通りである。
【００１７】
すなわち、代表的なものによって得られる効果は、時刻表を加味し、臨時運行列車や臨時運休列車を加味した経路探索を、高い精度で且つ少ない負荷で実行することができる。例えば、災害時等、急遽変更が発生した状態においても、変更内容を反映した時刻表を取り込むことにより、当変更内容を加味した精度の高い経路探索を実行することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施の形態にかかる経路探索システムの構成を示す構成図である。
【図２】本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの一例を示す図である。
【図３】本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの生成の一例を示す図である。
【図４】本発明の一実施の形態にかかる経路探索システムによる経路探索方法を示すフローチャートである。
【図５】本発明の一実施の形態にかかる経路探索システムによる経路探索方法の経路探索処理の具体例を示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００２０】
＜経路探索システムの構成＞
図１および図２により、本発明の一実施の形態にかかる経路探索システムの構成について説明する。図１は本発明の一実施の形態にかかる経路探索システムの構成を示す構成図、図２は本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの一例を示す図である。
【００２１】
図１において、経路探索システム１００は、経路探索サーバ１０１および経路探索部１０２から構成され、経路探索サーバ１０１には、公衆通信回線網１０６を介して利用者１０７が操作する端末などが接続され、利用者からの経路探索の条件の入力や利用者への経路探索結果の送信などが行われる。
【００２２】
経路探索部１０２には、リンクデータ１０３、リンクデータ１０３と１対１に関連付けられビットパターン化した時刻表データ（以下、時刻表ビットパターンデータ１０４と呼ぶ）、列車の乗り換えに関する情報が格納された乗換情報データ１０５が格納されたデータベースが接続され、各データは経路探索部１０２で実行される経路探索プログラムによる経路探索処理に使用される。
【００２３】
図１においては、経路探索部１０２で実行されている経路探索プログラムにより、リンクデータ１０３、時刻表ビットパターンデータ１０４、および乗換情報データ１０５を用いて、経路探索部１０２で経路探索を行い、回答経路を導出している。
【００２４】
図２において、リンクデータ１０３とは、レコードに一意に割り振られたリンクＩＤ、出発駅、到着駅、列車、出発駅から到着駅に至るのに必要な平均的な所要時間、距離等を保持したデータである。このリンクデータ１０３を全ての駅間について保持したリンクテーブルを用いて、出発駅から目的駅まで接続するリンクを順に探索していくことにより、経路を導出することができる。
【００２５】
時刻表ビットパターンデータ１０４とは、リンクデータ１０３の各レコードと関連付けるためのリンクＩＤ、１分を１ビットとし、１日（６０分×２４時間＝１４４０分）を１４４０ビットで表し、該当するリンクＩＤで運行している列車の出発時刻の位置に「１」、それ以外を「０」に設定した列車出発時刻ビットパターンと、１日を１ビットとし、該当するリンクＩＤで運行している列車が運行する日を「１」、運休する日を「０」に設定した列車運転日ビットパターン、および該当するリンクＩＤで運行している列車群の出発駅から到着駅までの所要時間において、各時間帯別（０時台、１時台、…、２３時台）に最も短い所要時間を設定した時間帯別最短所要時間からなるデータである。リンクデータ１０３と時刻表ビットパターンデータ１０４は、リンクＩＤで関連付けられており、１対１の関連となる。
【００２６】
＜リンクデータ１０３および時刻表ビットパターンデータ１０４の生成＞
次に、図３により、本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの生成について説明する。図３は本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの生成の一例を示す図である。
【００２７】
まず鉄道の時刻表は、図３の時刻表に示すように、列車毎に、列車名、運転日、運転区間の出発駅、出発時刻、到着駅、到着時刻等の項目で表現されている。図３の時刻表に示したようなフォーマットで日本全国全ての列車についてデータ化されたものが、鉄道時刻表販売業者により販売されており、当該時刻表データより、リンクデータ１０３、時刻表ビットパターンデータ１０４を生成する。
【００２８】
まず、リンクデータ１０３については、時刻表データの全列車の駅間について、図３に示すようなフォーマットで生成される。リンクデータ１０３は、図３に示すように、「ＪＲ山手線」は、１日に朝から晩まで何本も運行しているため、時刻表データ上に同一区間を別時刻で運行する列車データが複数存在している。同一区間については１レコードに纏める。平均所要時間については、当該区間を１日に運行する全列車の所要時間の平均値から求める等して設定する。距離については、各駅間において固定で定められているので、その値を設定する。
【００２９】
次に、時刻表ビットパターンデータ１０４については、該当リンクの区間を運行する列車の出発時刻を基に、列車出発時刻ビットパターンの該当位置に「１」を設定し、当該列車の運転日情報を基に、列車運転日ビットパターンの該当位置に「１」を設定する。例えば図３に示した「ＪＲ山手線」は、同一区間を１日に朝から晩まで何本も運行しているため、１レコードの時刻表ビットパターンデータにおける列車出発時刻ビットパターンの様々な位置に「１」が設定される。
【００３０】
図３に示す時刻表ビットパターンデータ１０４の網掛けの太字箇所が、図３の時刻表で示している時刻表データに対するビット設定であり、それ以外は別時刻に運行する列車に対するものである。
【００３１】
列車運転日ビットパターンについては、当該区間を運行する全列車に対して設定するものである。例えば、図３に示した「ＪＲ山手線」の時刻表においては、「＃１」の列車は「全日運転」であり、毎日同じ時刻で運行するが、「＃２」の列車は「平日運転」、「＃３」の列車は「土休運転」であり、運転日によって運行時刻が異なる。リンクデータ１０３と時刻表ビットパターンデータ１０４を１対１に関連付けるため、該当リンク区間に対して、運転日パターン毎に時刻表ビットパターンレコードを生成する必要がある。
【００３２】
図３に示す例では、「＃２」と「＃３」は運転時刻が異なるため、平日運転日のレコードと、土休運転日のレコードを別々に生成する必要がある。
【００３３】
時間帯別最短所要時間については、該当リンク区間を該当運転日に運行する該当時間帯の全列車の中で、最短の所要時間を設定する。ここで平均ではなく最短の所要時間を設定しているのは、経路探索時にリンクＡからリンクＢへの乗継が可能かを判定する際、リンクＢに対する時刻表ビットパターンデータ１０４の列車出発時刻ビットパターンで、リンクＢの最短乗継可能時刻をチェックするが、リンクＡの所要時間が平均値であった場合、最短乗継時間をオーバーし、最適なリンクＢへの乗継を取得できない可能性がある。このため、確実に最短の乗継が取得できるよう、最短所要時間を設定する。
【００３４】
このリンクデータ１０３、時刻表ビットパターンデータ１０４について、経路探索時に時刻表データから生成するのは負荷が非常に大きいため、時刻表データからリンクデータ１０３、時刻表ビットパターンデータ１０４を生成する変換プログラム等を用意しておき、事前にデータファイル化しておく。
【００３５】
当該データファイルを用いることで、経路検索時にリンクデータ１０３、時刻表ビットパターンデータ１０４を当フォーマットのまま利用でき、データ生成の負荷をなくすことができる。
【００３６】
＜経路探索方法の詳細＞
次に、図４により、本発明の一実施の形態にかかる経路探索システムによる経路探索方法について説明する。図４は本発明の一実施の形態にかかる経路探索システムによる経路探索方法を示すフローチャートであり、リンクデータ１０３、時刻表ビットパターンデータ１０４を用いた経路探索処理を示している。
【００３７】
始めに、経路探索処理で用いる値について説明する。
●Ｎ：探索対象指定駅を格納する値。
●Ｍ：経路探索中の現在時分を格納する値、１日の時刻を分（０〜１４３９）で保持する。
●Ｄ：経路探索中の現在日を格納する値。
●Ｂ：現リンクに対する時刻表ビットパターンを格納する値。
●Ｌ（ｉ）：指定駅を発駅とするリンク群。
●Ｅ1，Ｅ2：通過経路情報。現リンクＩＤ、直前リンクＩＤ、現在時分、現在日を保持。
●Ｔ（ｘ）：該当リンク通過時の通過経路情報を格納する配列。ｘ＝リンクＩＤ。
●Ｂ1（ｘ）：探索指定日に運行する時刻表ビットパターンを格納した配列。ｘ＝リンクＩＤ、レコード数はリンクと同一。
●Ｂ2（ｘ）：探索指定日の翌日に運行する時刻表ビットパターンを格納した配列。ｘ＝リンクＩＤ、レコード数はリンクと同一。
●Ｓ（ｊ）：経路探索対象の通過経路情報を格納する配列。
【００３８】
まず、Ｎに出発駅、Ｍに探索指定日時、Ｄに０を設定する（ステップ４０１）。次に、時刻表ビットパターンデータ１０４を取得する。日本国内を運行する列車であれば、寝台列車等、翌日へ跨いで運行する列車が存在するが、翌々日まで跨いで運行する列車は存在しない。よって、必要となる時刻表ビットパターンデータは、探索指定日分と、その翌日分である。Ｂ1に探索指定日に運行（列車運転日ビットパターンの探索指定日位置に「１」が設定されている）の時刻表ビットパターンデータ１０４を設定し（ステップ４０２）、Ｂ2に探索指定日の翌日に運行（列車運転日ビットパターンの探索指定日翌日位置に「１」が設定されている）の時刻表ビットパターンデータ１０４を設定する（ステップ４０３）。
【００３９】
１つのリンクに対して、１運行日に対する時刻表ビットパターンデータ１０４は１レコードのみなので、リンクデータ１０３とＢ1およびＢ2に設定された時刻表ビットパターンデータ１０４のレコード数は同一となり、１対１の関連となる。
【００４０】
次に、Ｎを発駅とするリンク群をＬに設定し（ステップ４０４）、リンク群が存在するか否かを判定し（ステップ４０５）、ステップ４０５でＬが空である場合はＮから繋がるリンクが存在しないので、ここで探索終了とする。
【００４１】
ステップ４０５でＮから繋がるリンクが存在する場合、リンク群Ｌの添字をｉとし、ｉ＝１として、リンクＬ（ｉ）の通過経路情報についての処理を行う（ステップ４０６）。
【００４２】
まず、リンクＬ（ｉ）が存在するか否かを判定し（ステップ４３１）、ステップ４３１でリンクＬ（ｉ）が存在する場合は、Ｍに直前リンクからの乗換時間を加算する（ステップ４０７）。
【００４３】
乗換時間は、直前リンク、現リンクを基に、乗換情報データより取得する。乗換時間を加算したことで、Ｍが１４４０以上となっているか否かを判定する（ステップ４０８）。
【００４４】
ステップ４０８でＭが１４４０以上となっている場合、１日分の時間範囲（６０分×２４時間＝１４４０分）を超えているので、翌日設定をする必要がある。ここで、Ｄが０であるか否かを判定し（ステップ４０９）、ステップ４０９でＤが０でなければ、既に翌日であり、翌々日となってしまうので、探索終了とする。
【００４５】
ステップ４０９でＤが０であれば、Ｍから１４４０を減算し、翌日の時刻に設定し、Ｄを１に設定する（ステップ４１０）。
【００４６】
ステップ４０８でＭが１４４０未満であれば、Ｄが０か否かを判定する（ステップ４１１）。ステップ４１１でＤが０であれば、探索指定日当日であるので、時刻表ビットパターンデータＢ1から該当リンクに対する時刻表ビットパターンデータレコードＢ1（Ｌ（ｉ））を取得し、Ｂに格納する（ステップ４１２）。
【００４７】
ステップ４１１でＤが０でなければ（Ｄが１）、探索指定日翌日であるので、時刻表ビットパターンデータＢ2から取得し、Ｂに格納する（ステップ４１３）。
【００４８】
現在時刻Ｍで乗継可能な最早の列車は、現在時刻以降で最も小さい時刻の列車である。Ｂの列車出発時刻ビットパターンから、Ｍ以上で最小となるビット位置を検索する（ステップ４１４）。
【００４９】
具体的には、Ｂの列車出発時刻ビットパターンにおいて、現在時刻Ｍのビット位置から、ビット位置を１つずつインクリメントし、最初に「１」となる位置を取得する。
【００５０】
次に、ステップ４１４での検索によりビット位置が見つかるか否かを判定し（ステップ４１５）、ステップ４１５でビット位置が見つからない場合、つまり列車出発時刻ビットパターンの最終位置（１４４０）まで検索しても「１」がなかった場合は、翌日に跨いでいる可能性がある。
【００５１】
この場合は、Ｄが０か否かを判定し（ステップ４１６）、ステップ４１６でＤが０でなかった場合は、翌々日へ跨いでしまうので、探索終了とする。
【００５２】
ステップ４１６でＤが０の場合は、翌日となるので、時刻表ビットパターンデータＢ2から該当リンクに対する時刻表ビットパターンデータレコードＢ2（Ｌ（ｉ））を取得し、Ｂに格納し（ステップ４１７）、Ｍに０を設定、Ｄに１を設定し（ステップ４１８）、ステップ４１４を再度実行する。
【００５３】
ステップ４１５で、ビット位置が見つかった場合は、Ｍに見つかったビット位置を設定する（ステップ４１９）。その後、当該リンクの運行時間を加算するため、Ｍから現在時刻を判定し、該当するＢの時間帯別最短所要時間値を取得し、Ｍに加算する（ステップ４２０）。
【００５４】
次に、ステップ４０８〜ステップ４１０と同様に、翌日判定、設定を行い（ステップ４２１〜ステップ４２３）、Ｅ2にＭ，Ｄの値を設定する（ステップ４２４）。
【００５５】
次に、Ｌ（ｉ）が未通過か否かを判定し（ステップ４２５）、ステップ４２５でＬ（ｉ）が未通過の場合、ＳにＬ（ｉ）についての通過経路情報Ｅ2を追加し（ステップ４２６）、Ｔ（Ｌ（ｉ））にＥ2を追加する（ステップ４２９）。
【００５６】
ステップ４２５でＬ（ｉ）が未通過ではなく既に通過済みである場合、ＭがＴ（Ｌ（ｉ））の持つ時分より小さいか否かを判定し（ステップ４２７）、ステップ４２７で小さければ、ＳのＬ（ｉ）についての通過経路情報をＥ2に書き換え（ステップ４２８）、Ｔ（Ｌ（ｉ））にＥ2を追加する（ステップ４２９）。
【００５７】
ステップ４２７で小さくなければ、ｉを１加算し（ステップ４３０）、ステップ４３１に戻り、Ｌ（ｉ）が存在しなくなるまで前記処理を繰り返す。
【００５８】
ステップ４３１で、Ｌ（ｉ）が存在しなくなった、つまりＮを発駅とするリンク全てについて処理が完了すると、Ｓが空か否かを判定し（ステップ４３２）、ステップ４３２でＳが空の場合は、探索対象となる通過経路情報がないため終了する。
【００５９】
ステップ４３２でＳが空でない場合は、Ｓから次の探索対象となる通過経路情報を取得する。Ｓの最早通過経路情報をＥ1に設定し（ステップ４３３）、Ｅ1に設定した値は探索対象となったので、Ｓから削除する（ステップ４３４）。ＮにＥ1の現リンクの着駅、ＭにＥ1の時分、ＤにＥ1の日を設定する（ステップ４３５）。
【００６０】
次に、Ｎが目的駅か否かを判定し（ステップ４３６）、ステップ４３６でＮが目的駅であれば、出発駅から目的駅まで到達しているので、現リンクに対するＴから、直前リンクＩＤを基に出発駅まで辿って、出発駅から目的駅の経路を生成する（ステップ４３７）。
【００６１】
ステップ４３６でＮが目的駅でなければ、ステップ４０４に戻り、Ｎを発駅とするリンク群を取得し、これまでの処理を目的駅に到達するまで繰り返す。
【００６２】
以上で出発駅から目的駅までの経路を取得することができる。
【００６３】
前記で説明した処理では、出発駅の出発時刻を指定した出発時刻指定経路探索であるが、経路探索時の使用者の要望としては、目的駅の到着時刻を指定した経路探索もある。到着時刻指定経路探索では、探索指定日と探索指定日前日の時刻表ビットパターンデータ１０４を取得し、目的駅から出発駅の方向に、現在時刻を減算していくように前記経路探索処理を実行することで実現できる。
【００６４】
＜経路探索処理の具体例＞
次に、図５により、本発明の一実施の形態にかかる経路探索システムによる経路探索方法の経路探索処理の具体例について説明する。図５は本発明の一実施の形態にかかる経路探索システムによる経路探索方法の経路探索処理の具体例を示す図であり、図５（ａ）は出発が渋谷駅、到着が恵比寿駅のデータ、図５（ｂ）は出発が恵比寿駅、到着が目黒駅のデータ、図５（ｃ）は出発が目黒駅、到着が白金台駅のデータであり、出発駅：渋谷駅、目的駅：白金台駅、８／２（月）９：００出発の経路探索の一例を示している。
【００６５】
まず、図５（ａ）に示すように、最初に検索指定日８／２（月）と検索指定日翌日８／３（火）が運転となっている時刻表ビットパターンデータ１０４のみを取得する。
【００６６】
次に、渋谷駅を出発し、恵比寿駅へ運行するＪＲ山手線のリンクＩＤが１のレコードを取得する。リンクＩＤが１のレコードに該当する時刻表ビットパターンを取得すると、９：００以降で最小の出発時刻は９：０１であることがわかる。現在時刻９：０１に９時台の最短所要時間２分を加算し、現在時刻を９：０３とする。
【００６７】
次に、図５（ｂ）に示すように、恵比寿駅を出発するリンクＩＤのレコードを取得する。恵比寿駅を出発し、目黒駅へ運行するＪＲ山手線のリンクＩＤが２のレコードを取得する。リンクＩＤが２のレコードには、８／２（月）は運行しない時刻表ビットパターンデータも存在するが、当データは運転日不一致で取得されない。リンクＩＤが１のレコードの列車とリンクＩＤが２のレコードの列車は両方ともＪＲ山手線であり、乗換が発生しないため、乗換時間の加算はない。
【００６８】
リンクＩＤが２のレコードに該当する時刻表ビットパターンデータ１０４を取得すると、９：０１出発の列車があることがわかるが、現在時刻より過去であるため、乗継不可であることがわかる。現在時刻９：０３以降では、９：０３出発となる列車があることがわかるので、リンクＩＤが１のレコードからリンクＩＤが２のレコードは乗継可能である。９：０３に９時台の最短所要時間３分を加算し、現在時刻を９：０６とする。
【００６９】
次に、図５（ｃ）に示すように、目黒駅を出発するリンクＩＤを取得する。目黒駅を出発し、白金台駅へ運行する東京メトロ南北線のリンクＩＤが３のレコードを取得する。リンクＩＤが２のレコードとリンクＩＤが３のレコードは別列車で乗換が発生するため、乗換情報データ１０５より乗換時間５分が取得される。現在時刻９：０６に乗換時間５分を加算し、現在時刻を９：１１とする。リンクＩＤが３のレコードに該当する時刻表ビットパターンデータ１０４を取得すると、９：１１以降では９：１２に出発する列車があるので、リンクＩＤが２のレコードの列車からリンクＩＤが３のレコードの列車は乗継可能であることがわかる。当該リンクにより、目的駅である白金台駅へ到達する。このような手法で経路探索を行う。
【００７０】
１つのリンクＩＤで特定される区間を運行する列車は、１日の間で数多く存在する。例えば、図５の（ａ）に示すリンクＩＤが１のレコードの区間（渋谷駅出発、恵比寿駅到着のＪＲ山手線）を運行する列車は、１日で５００本以上存在する。このため、時刻表データをそのまま利用する場合、当該リンクＩＤに対して５００本以上の列車から最適な時間で乗継可能な列車を選択し、次のリンクＩＤを取得、当リンクＩＤに対してまた数多くの列車を探索・・・、という処理を繰り返すことになり、経路探索処理の負荷が非常に大きい。
【００７１】
本実施の形態では、上述したような経路探索方法を用いることにより、１つのリンクＩＤに対して１つの時刻表となり、数多くの列車を探索する負荷を省くことが可能である。
【００７２】
また、乗継可能時刻をビット位置検索で実現しているが、ビット位置検索は、Ｎｕｍｂｅｒ ｏｆ Ｌｅａｄｉｎｇ Ｚｅｒｏ（ＮＬＺ）（ビット列を左側から見て、最初に１が立っているビット位置を探す）、Ｎｕｍｂｅｒ ｏｆ Ｔｒａｉｎｉｎｇ Ｚｅｒｏ（ＮＴＺ）（ビット列を右側から見て、最初に１が立っているビット位置を探す）という分野で、高速に実行するアルゴリズムが研究されており、このような高速アルゴリズムを適用することで、高速な処理を実現することが可能である。
【００７３】
更に、特許第４３５８８０６号公報などで述べられているブリッジテーブルの概念を用いることで、リンク間乗継時の検索処理の負荷を省くことができ、更なる処理効率の向上が図れる。また、特許第４３５８８０６号公報などに記載の探索方法を適用することで、時刻表を加味した優秀な代替経路を導出することができる。
【００７４】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【産業上の利用可能性】
【００７５】
本発明は、出発駅から目的駅までの最適な経路を取得する経路探索システム、経路探索方法および経路探索プログラムに関し、特に少ない負荷で処理する必要のあるシステムやプログラムに広く適用可能である。
【符号の説明】
【００７６】
１００…経路探索システム、１０１…経路探索サーバ、１０２…経路探索部、１０３…リンクデータ、１０４…時刻表ビットパターンデータ、１０５…乗換情報データ、１０６…公衆通信回線網、１０７…利用者。
【技術分野】
【０００１】
本発明は、出発駅から目的駅までの最適な経路を取得する経路探索システム、経路探索方法および経路探索プログラムに関し、特に少ない負荷で処理可能な技術に関するものである。
【背景技術】
【０００２】
鉄道経路網において、出発駅から目的駅に到達するまでの経路は多数存在しており、これらの経路の中から最適な経路を導出するための手法として、例えば特開平１１−４４５４７号公報（特許文献１）や、特開２００７−８３８００号公報（特許文献２）等に記載のものがある。
【０００３】
これらの技術は、各駅間に一定のコストを設定し、当該コストを用いて経路探索を行っているが、鉄道経路網においては、列車は時刻表に従って運行しており、各駅間のコストは一定ではないため、導出された経路について時刻表を加味した場合、最適な経路でない可能性がある。
【０００４】
一般的な鉄道経路探索では、以下のような手法となる。
（１）上記特許文献１や、特許文献２の技術を用い、各駅間に平均的な所要時間を設定した鉄道経路ネットワークを生成し、経路探索を実施する。
（２）（１）で求まった経路に対し、経路探索条件として指定された時刻に対して最適となる時刻表を設定する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１１−４４５４７号公報
【特許文献２】特開２００７−８３８００号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、前述した一般的な鉄道経路探索の場合、（１）の段階では時刻表を考慮しない探索となるため、臨時列車等の平均的に運行していない列車についての最適な探索が困難である。時刻表を直接探索するという選択もあるが、時刻表データは膨大であるため、探索負荷が大きく、性能面で問題がある。
【０００７】
また、鉄道経路網（空路、バス、船舶等の交通網も含む）は、出発駅、到着駅、列車、出発駅から到着駅に至る所要時間、距離等の駅間列車情報を表す「リンク」と、前記リンクで表現されるネットワーク上を実際に運行する列車の発着時刻（出発駅ＸＸ時ＸＸ分出発〜到着駅ＸＸ時ＸＸ分到着）を表す「時刻表」で構成されている。
【０００８】
前記時刻表は、例えばリンクＡ駅→Ｂ駅に対して、０６：００出発、０６：３０出発、・・・というように、１つのリンクに対して複数存在している。日本全国の鉄道に対する時刻表データのレコード数は膨大であり、またリンクと時刻表が１対多の関係であることが、時刻表を加味して経路探索を行うことを困難にしている。
【０００９】
以上のように、従来の技術では、鉄道経路網（空路、バス、船舶等の交通網も含む）において、時刻表を加味した経路探索を少ない探索負荷で実施することは困難であった。
【００１０】
そこで、本発明の目的は、鉄道経路網において、少ない負荷で時刻表を加味した経路探索を実現することができる経路探索システム、経路探索方法および経路探索プログラムを提供することにある。
【００１１】
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１２】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次の通りである。
【００１３】
すなわち、代表的なものの概要は、経路探索システムにおいて、出発駅、到着駅、出発駅から到着駅の間を走行する列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、リンクデータと関連付けるための第２のリンクＩＤ、第２のリンクＩＤに対応した列車の運転日および列車の１日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータと、探索対象の出発駅から到着駅に至るリンクデータの複数のレコードに対応する時刻表ビットパターンデータの各ビットを検索し、探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部とを備えたものである。
【００１４】
また、経路探索方法において、出発駅、到着駅、列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、リンクデータと関連付けるための第２のリンクＩＤ、第２のリンクＩＤに対応した列車の運転日および列車の１日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有し、経路探索部により、探索対象の出発駅から到着駅に至るリンクデータの複数のレコードに対応する時刻表ビットパターンデータの各ビットを検索し、探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得するものである。
【００１５】
また、経路探索プログラムにおいて、出発駅、到着駅、列車、出発駅から到着駅に至る平均所要時間、出発駅から到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、リンクデータと関連付けるための第２のリンクＩＤ、第２のリンクＩＤに対応した列車の運転日および列車の１日の出発時刻を特定ビットで表したビット列、および列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有したコンピュータ上で実行され、コンピュータを、探索対象の出発駅から到着駅に至るリンクデータの複数のレコードに対応する時刻表ビットパターンデータの各ビットを検索し、探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部として機能させるものである。
【発明の効果】
【００１６】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下の通りである。
【００１７】
すなわち、代表的なものによって得られる効果は、時刻表を加味し、臨時運行列車や臨時運休列車を加味した経路探索を、高い精度で且つ少ない負荷で実行することができる。例えば、災害時等、急遽変更が発生した状態においても、変更内容を反映した時刻表を取り込むことにより、当変更内容を加味した精度の高い経路探索を実行することができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施の形態にかかる経路探索システムの構成を示す構成図である。
【図２】本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの一例を示す図である。
【図３】本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの生成の一例を示す図である。
【図４】本発明の一実施の形態にかかる経路探索システムによる経路探索方法を示すフローチャートである。
【図５】本発明の一実施の形態にかかる経路探索システムによる経路探索方法の経路探索処理の具体例を示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００２０】
＜経路探索システムの構成＞
図１および図２により、本発明の一実施の形態にかかる経路探索システムの構成について説明する。図１は本発明の一実施の形態にかかる経路探索システムの構成を示す構成図、図２は本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの一例を示す図である。
【００２１】
図１において、経路探索システム１００は、経路探索サーバ１０１および経路探索部１０２から構成され、経路探索サーバ１０１には、公衆通信回線網１０６を介して利用者１０７が操作する端末などが接続され、利用者からの経路探索の条件の入力や利用者への経路探索結果の送信などが行われる。
【００２２】
経路探索部１０２には、リンクデータ１０３、リンクデータ１０３と１対１に関連付けられビットパターン化した時刻表データ（以下、時刻表ビットパターンデータ１０４と呼ぶ）、列車の乗り換えに関する情報が格納された乗換情報データ１０５が格納されたデータベースが接続され、各データは経路探索部１０２で実行される経路探索プログラムによる経路探索処理に使用される。
【００２３】
図１においては、経路探索部１０２で実行されている経路探索プログラムにより、リンクデータ１０３、時刻表ビットパターンデータ１０４、および乗換情報データ１０５を用いて、経路探索部１０２で経路探索を行い、回答経路を導出している。
【００２４】
図２において、リンクデータ１０３とは、レコードに一意に割り振られたリンクＩＤ、出発駅、到着駅、列車、出発駅から到着駅に至るのに必要な平均的な所要時間、距離等を保持したデータである。このリンクデータ１０３を全ての駅間について保持したリンクテーブルを用いて、出発駅から目的駅まで接続するリンクを順に探索していくことにより、経路を導出することができる。
【００２５】
時刻表ビットパターンデータ１０４とは、リンクデータ１０３の各レコードと関連付けるためのリンクＩＤ、１分を１ビットとし、１日（６０分×２４時間＝１４４０分）を１４４０ビットで表し、該当するリンクＩＤで運行している列車の出発時刻の位置に「１」、それ以外を「０」に設定した列車出発時刻ビットパターンと、１日を１ビットとし、該当するリンクＩＤで運行している列車が運行する日を「１」、運休する日を「０」に設定した列車運転日ビットパターン、および該当するリンクＩＤで運行している列車群の出発駅から到着駅までの所要時間において、各時間帯別（０時台、１時台、…、２３時台）に最も短い所要時間を設定した時間帯別最短所要時間からなるデータである。リンクデータ１０３と時刻表ビットパターンデータ１０４は、リンクＩＤで関連付けられており、１対１の関連となる。
【００２６】
＜リンクデータ１０３および時刻表ビットパターンデータ１０４の生成＞
次に、図３により、本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの生成について説明する。図３は本発明の一実施の形態にかかる経路探索システムで使用されるリンクデータおよび時刻表ビットパターンデータの生成の一例を示す図である。
【００２７】
まず鉄道の時刻表は、図３の時刻表に示すように、列車毎に、列車名、運転日、運転区間の出発駅、出発時刻、到着駅、到着時刻等の項目で表現されている。図３の時刻表に示したようなフォーマットで日本全国全ての列車についてデータ化されたものが、鉄道時刻表販売業者により販売されており、当該時刻表データより、リンクデータ１０３、時刻表ビットパターンデータ１０４を生成する。
【００２８】
まず、リンクデータ１０３については、時刻表データの全列車の駅間について、図３に示すようなフォーマットで生成される。リンクデータ１０３は、図３に示すように、「ＪＲ山手線」は、１日に朝から晩まで何本も運行しているため、時刻表データ上に同一区間を別時刻で運行する列車データが複数存在している。同一区間については１レコードに纏める。平均所要時間については、当該区間を１日に運行する全列車の所要時間の平均値から求める等して設定する。距離については、各駅間において固定で定められているので、その値を設定する。
【００２９】
次に、時刻表ビットパターンデータ１０４については、該当リンクの区間を運行する列車の出発時刻を基に、列車出発時刻ビットパターンの該当位置に「１」を設定し、当該列車の運転日情報を基に、列車運転日ビットパターンの該当位置に「１」を設定する。例えば図３に示した「ＪＲ山手線」は、同一区間を１日に朝から晩まで何本も運行しているため、１レコードの時刻表ビットパターンデータにおける列車出発時刻ビットパターンの様々な位置に「１」が設定される。
【００３０】
図３に示す時刻表ビットパターンデータ１０４の網掛けの太字箇所が、図３の時刻表で示している時刻表データに対するビット設定であり、それ以外は別時刻に運行する列車に対するものである。
【００３１】
列車運転日ビットパターンについては、当該区間を運行する全列車に対して設定するものである。例えば、図３に示した「ＪＲ山手線」の時刻表においては、「＃１」の列車は「全日運転」であり、毎日同じ時刻で運行するが、「＃２」の列車は「平日運転」、「＃３」の列車は「土休運転」であり、運転日によって運行時刻が異なる。リンクデータ１０３と時刻表ビットパターンデータ１０４を１対１に関連付けるため、該当リンク区間に対して、運転日パターン毎に時刻表ビットパターンレコードを生成する必要がある。
【００３２】
図３に示す例では、「＃２」と「＃３」は運転時刻が異なるため、平日運転日のレコードと、土休運転日のレコードを別々に生成する必要がある。
【００３３】
時間帯別最短所要時間については、該当リンク区間を該当運転日に運行する該当時間帯の全列車の中で、最短の所要時間を設定する。ここで平均ではなく最短の所要時間を設定しているのは、経路探索時にリンクＡからリンクＢへの乗継が可能かを判定する際、リンクＢに対する時刻表ビットパターンデータ１０４の列車出発時刻ビットパターンで、リンクＢの最短乗継可能時刻をチェックするが、リンクＡの所要時間が平均値であった場合、最短乗継時間をオーバーし、最適なリンクＢへの乗継を取得できない可能性がある。このため、確実に最短の乗継が取得できるよう、最短所要時間を設定する。
【００３４】
このリンクデータ１０３、時刻表ビットパターンデータ１０４について、経路探索時に時刻表データから生成するのは負荷が非常に大きいため、時刻表データからリンクデータ１０３、時刻表ビットパターンデータ１０４を生成する変換プログラム等を用意しておき、事前にデータファイル化しておく。
【００３５】
当該データファイルを用いることで、経路検索時にリンクデータ１０３、時刻表ビットパターンデータ１０４を当フォーマットのまま利用でき、データ生成の負荷をなくすことができる。
【００３６】
＜経路探索方法の詳細＞
次に、図４により、本発明の一実施の形態にかかる経路探索システムによる経路探索方法について説明する。図４は本発明の一実施の形態にかかる経路探索システムによる経路探索方法を示すフローチャートであり、リンクデータ１０３、時刻表ビットパターンデータ１０４を用いた経路探索処理を示している。
【００３７】
始めに、経路探索処理で用いる値について説明する。
●Ｎ：探索対象指定駅を格納する値。
●Ｍ：経路探索中の現在時分を格納する値、１日の時刻を分（０〜１４３９）で保持する。
●Ｄ：経路探索中の現在日を格納する値。
●Ｂ：現リンクに対する時刻表ビットパターンを格納する値。
●Ｌ（ｉ）：指定駅を発駅とするリンク群。
●Ｅ1，Ｅ2：通過経路情報。現リンクＩＤ、直前リンクＩＤ、現在時分、現在日を保持。
●Ｔ（ｘ）：該当リンク通過時の通過経路情報を格納する配列。ｘ＝リンクＩＤ。
●Ｂ1（ｘ）：探索指定日に運行する時刻表ビットパターンを格納した配列。ｘ＝リンクＩＤ、レコード数はリンクと同一。
●Ｂ2（ｘ）：探索指定日の翌日に運行する時刻表ビットパターンを格納した配列。ｘ＝リンクＩＤ、レコード数はリンクと同一。
●Ｓ（ｊ）：経路探索対象の通過経路情報を格納する配列。
【００３８】
まず、Ｎに出発駅、Ｍに探索指定日時、Ｄに０を設定する（ステップ４０１）。次に、時刻表ビットパターンデータ１０４を取得する。日本国内を運行する列車であれば、寝台列車等、翌日へ跨いで運行する列車が存在するが、翌々日まで跨いで運行する列車は存在しない。よって、必要となる時刻表ビットパターンデータは、探索指定日分と、その翌日分である。Ｂ1に探索指定日に運行（列車運転日ビットパターンの探索指定日位置に「１」が設定されている）の時刻表ビットパターンデータ１０４を設定し（ステップ４０２）、Ｂ2に探索指定日の翌日に運行（列車運転日ビットパターンの探索指定日翌日位置に「１」が設定されている）の時刻表ビットパターンデータ１０４を設定する（ステップ４０３）。
【００３９】
１つのリンクに対して、１運行日に対する時刻表ビットパターンデータ１０４は１レコードのみなので、リンクデータ１０３とＢ1およびＢ2に設定された時刻表ビットパターンデータ１０４のレコード数は同一となり、１対１の関連となる。
【００４０】
次に、Ｎを発駅とするリンク群をＬに設定し（ステップ４０４）、リンク群が存在するか否かを判定し（ステップ４０５）、ステップ４０５でＬが空である場合はＮから繋がるリンクが存在しないので、ここで探索終了とする。
【００４１】
ステップ４０５でＮから繋がるリンクが存在する場合、リンク群Ｌの添字をｉとし、ｉ＝１として、リンクＬ（ｉ）の通過経路情報についての処理を行う（ステップ４０６）。
【００４２】
まず、リンクＬ（ｉ）が存在するか否かを判定し（ステップ４３１）、ステップ４３１でリンクＬ（ｉ）が存在する場合は、Ｍに直前リンクからの乗換時間を加算する（ステップ４０７）。
【００４３】
乗換時間は、直前リンク、現リンクを基に、乗換情報データより取得する。乗換時間を加算したことで、Ｍが１４４０以上となっているか否かを判定する（ステップ４０８）。
【００４４】
ステップ４０８でＭが１４４０以上となっている場合、１日分の時間範囲（６０分×２４時間＝１４４０分）を超えているので、翌日設定をする必要がある。ここで、Ｄが０であるか否かを判定し（ステップ４０９）、ステップ４０９でＤが０でなければ、既に翌日であり、翌々日となってしまうので、探索終了とする。
【００４５】
ステップ４０９でＤが０であれば、Ｍから１４４０を減算し、翌日の時刻に設定し、Ｄを１に設定する（ステップ４１０）。
【００４６】
ステップ４０８でＭが１４４０未満であれば、Ｄが０か否かを判定する（ステップ４１１）。ステップ４１１でＤが０であれば、探索指定日当日であるので、時刻表ビットパターンデータＢ1から該当リンクに対する時刻表ビットパターンデータレコードＢ1（Ｌ（ｉ））を取得し、Ｂに格納する（ステップ４１２）。
【００４７】
ステップ４１１でＤが０でなければ（Ｄが１）、探索指定日翌日であるので、時刻表ビットパターンデータＢ2から取得し、Ｂに格納する（ステップ４１３）。
【００４８】
現在時刻Ｍで乗継可能な最早の列車は、現在時刻以降で最も小さい時刻の列車である。Ｂの列車出発時刻ビットパターンから、Ｍ以上で最小となるビット位置を検索する（ステップ４１４）。
【００４９】
具体的には、Ｂの列車出発時刻ビットパターンにおいて、現在時刻Ｍのビット位置から、ビット位置を１つずつインクリメントし、最初に「１」となる位置を取得する。
【００５０】
次に、ステップ４１４での検索によりビット位置が見つかるか否かを判定し（ステップ４１５）、ステップ４１５でビット位置が見つからない場合、つまり列車出発時刻ビットパターンの最終位置（１４４０）まで検索しても「１」がなかった場合は、翌日に跨いでいる可能性がある。
【００５１】
この場合は、Ｄが０か否かを判定し（ステップ４１６）、ステップ４１６でＤが０でなかった場合は、翌々日へ跨いでしまうので、探索終了とする。
【００５２】
ステップ４１６でＤが０の場合は、翌日となるので、時刻表ビットパターンデータＢ2から該当リンクに対する時刻表ビットパターンデータレコードＢ2（Ｌ（ｉ））を取得し、Ｂに格納し（ステップ４１７）、Ｍに０を設定、Ｄに１を設定し（ステップ４１８）、ステップ４１４を再度実行する。
【００５３】
ステップ４１５で、ビット位置が見つかった場合は、Ｍに見つかったビット位置を設定する（ステップ４１９）。その後、当該リンクの運行時間を加算するため、Ｍから現在時刻を判定し、該当するＢの時間帯別最短所要時間値を取得し、Ｍに加算する（ステップ４２０）。
【００５４】
次に、ステップ４０８〜ステップ４１０と同様に、翌日判定、設定を行い（ステップ４２１〜ステップ４２３）、Ｅ2にＭ，Ｄの値を設定する（ステップ４２４）。
【００５５】
次に、Ｌ（ｉ）が未通過か否かを判定し（ステップ４２５）、ステップ４２５でＬ（ｉ）が未通過の場合、ＳにＬ（ｉ）についての通過経路情報Ｅ2を追加し（ステップ４２６）、Ｔ（Ｌ（ｉ））にＥ2を追加する（ステップ４２９）。
【００５６】
ステップ４２５でＬ（ｉ）が未通過ではなく既に通過済みである場合、ＭがＴ（Ｌ（ｉ））の持つ時分より小さいか否かを判定し（ステップ４２７）、ステップ４２７で小さければ、ＳのＬ（ｉ）についての通過経路情報をＥ2に書き換え（ステップ４２８）、Ｔ（Ｌ（ｉ））にＥ2を追加する（ステップ４２９）。
【００５７】
ステップ４２７で小さくなければ、ｉを１加算し（ステップ４３０）、ステップ４３１に戻り、Ｌ（ｉ）が存在しなくなるまで前記処理を繰り返す。
【００５８】
ステップ４３１で、Ｌ（ｉ）が存在しなくなった、つまりＮを発駅とするリンク全てについて処理が完了すると、Ｓが空か否かを判定し（ステップ４３２）、ステップ４３２でＳが空の場合は、探索対象となる通過経路情報がないため終了する。
【００５９】
ステップ４３２でＳが空でない場合は、Ｓから次の探索対象となる通過経路情報を取得する。Ｓの最早通過経路情報をＥ1に設定し（ステップ４３３）、Ｅ1に設定した値は探索対象となったので、Ｓから削除する（ステップ４３４）。ＮにＥ1の現リンクの着駅、ＭにＥ1の時分、ＤにＥ1の日を設定する（ステップ４３５）。
【００６０】
次に、Ｎが目的駅か否かを判定し（ステップ４３６）、ステップ４３６でＮが目的駅であれば、出発駅から目的駅まで到達しているので、現リンクに対するＴから、直前リンクＩＤを基に出発駅まで辿って、出発駅から目的駅の経路を生成する（ステップ４３７）。
【００６１】
ステップ４３６でＮが目的駅でなければ、ステップ４０４に戻り、Ｎを発駅とするリンク群を取得し、これまでの処理を目的駅に到達するまで繰り返す。
【００６２】
以上で出発駅から目的駅までの経路を取得することができる。
【００６３】
前記で説明した処理では、出発駅の出発時刻を指定した出発時刻指定経路探索であるが、経路探索時の使用者の要望としては、目的駅の到着時刻を指定した経路探索もある。到着時刻指定経路探索では、探索指定日と探索指定日前日の時刻表ビットパターンデータ１０４を取得し、目的駅から出発駅の方向に、現在時刻を減算していくように前記経路探索処理を実行することで実現できる。
【００６４】
＜経路探索処理の具体例＞
次に、図５により、本発明の一実施の形態にかかる経路探索システムによる経路探索方法の経路探索処理の具体例について説明する。図５は本発明の一実施の形態にかかる経路探索システムによる経路探索方法の経路探索処理の具体例を示す図であり、図５（ａ）は出発が渋谷駅、到着が恵比寿駅のデータ、図５（ｂ）は出発が恵比寿駅、到着が目黒駅のデータ、図５（ｃ）は出発が目黒駅、到着が白金台駅のデータであり、出発駅：渋谷駅、目的駅：白金台駅、８／２（月）９：００出発の経路探索の一例を示している。
【００６５】
まず、図５（ａ）に示すように、最初に検索指定日８／２（月）と検索指定日翌日８／３（火）が運転となっている時刻表ビットパターンデータ１０４のみを取得する。
【００６６】
次に、渋谷駅を出発し、恵比寿駅へ運行するＪＲ山手線のリンクＩＤが１のレコードを取得する。リンクＩＤが１のレコードに該当する時刻表ビットパターンを取得すると、９：００以降で最小の出発時刻は９：０１であることがわかる。現在時刻９：０１に９時台の最短所要時間２分を加算し、現在時刻を９：０３とする。
【００６７】
次に、図５（ｂ）に示すように、恵比寿駅を出発するリンクＩＤのレコードを取得する。恵比寿駅を出発し、目黒駅へ運行するＪＲ山手線のリンクＩＤが２のレコードを取得する。リンクＩＤが２のレコードには、８／２（月）は運行しない時刻表ビットパターンデータも存在するが、当データは運転日不一致で取得されない。リンクＩＤが１のレコードの列車とリンクＩＤが２のレコードの列車は両方ともＪＲ山手線であり、乗換が発生しないため、乗換時間の加算はない。
【００６８】
リンクＩＤが２のレコードに該当する時刻表ビットパターンデータ１０４を取得すると、９：０１出発の列車があることがわかるが、現在時刻より過去であるため、乗継不可であることがわかる。現在時刻９：０３以降では、９：０３出発となる列車があることがわかるので、リンクＩＤが１のレコードからリンクＩＤが２のレコードは乗継可能である。９：０３に９時台の最短所要時間３分を加算し、現在時刻を９：０６とする。
【００６９】
次に、図５（ｃ）に示すように、目黒駅を出発するリンクＩＤを取得する。目黒駅を出発し、白金台駅へ運行する東京メトロ南北線のリンクＩＤが３のレコードを取得する。リンクＩＤが２のレコードとリンクＩＤが３のレコードは別列車で乗換が発生するため、乗換情報データ１０５より乗換時間５分が取得される。現在時刻９：０６に乗換時間５分を加算し、現在時刻を９：１１とする。リンクＩＤが３のレコードに該当する時刻表ビットパターンデータ１０４を取得すると、９：１１以降では９：１２に出発する列車があるので、リンクＩＤが２のレコードの列車からリンクＩＤが３のレコードの列車は乗継可能であることがわかる。当該リンクにより、目的駅である白金台駅へ到達する。このような手法で経路探索を行う。
【００７０】
１つのリンクＩＤで特定される区間を運行する列車は、１日の間で数多く存在する。例えば、図５の（ａ）に示すリンクＩＤが１のレコードの区間（渋谷駅出発、恵比寿駅到着のＪＲ山手線）を運行する列車は、１日で５００本以上存在する。このため、時刻表データをそのまま利用する場合、当該リンクＩＤに対して５００本以上の列車から最適な時間で乗継可能な列車を選択し、次のリンクＩＤを取得、当リンクＩＤに対してまた数多くの列車を探索・・・、という処理を繰り返すことになり、経路探索処理の負荷が非常に大きい。
【００７１】
本実施の形態では、上述したような経路探索方法を用いることにより、１つのリンクＩＤに対して１つの時刻表となり、数多くの列車を探索する負荷を省くことが可能である。
【００７２】
また、乗継可能時刻をビット位置検索で実現しているが、ビット位置検索は、Ｎｕｍｂｅｒ ｏｆ Ｌｅａｄｉｎｇ Ｚｅｒｏ（ＮＬＺ）（ビット列を左側から見て、最初に１が立っているビット位置を探す）、Ｎｕｍｂｅｒ ｏｆ Ｔｒａｉｎｉｎｇ Ｚｅｒｏ（ＮＴＺ）（ビット列を右側から見て、最初に１が立っているビット位置を探す）という分野で、高速に実行するアルゴリズムが研究されており、このような高速アルゴリズムを適用することで、高速な処理を実現することが可能である。
【００７３】
更に、特許第４３５８８０６号公報などで述べられているブリッジテーブルの概念を用いることで、リンク間乗継時の検索処理の負荷を省くことができ、更なる処理効率の向上が図れる。また、特許第４３５８８０６号公報などに記載の探索方法を適用することで、時刻表を加味した優秀な代替経路を導出することができる。
【００７４】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【産業上の利用可能性】
【００７５】
本発明は、出発駅から目的駅までの最適な経路を取得する経路探索システム、経路探索方法および経路探索プログラムに関し、特に少ない負荷で処理する必要のあるシステムやプログラムに広く適用可能である。
【符号の説明】
【００７６】
１００…経路探索システム、１０１…経路探索サーバ、１０２…経路探索部、１０３…リンクデータ、１０４…時刻表ビットパターンデータ、１０５…乗換情報データ、１０６…公衆通信回線網、１０７…利用者。
【特許請求の範囲】
【請求項１】
出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムであって、
出発駅、到着駅、前記出発駅から前記到着駅の間を走行する列車、前記出発駅から前記到着駅に至る平均所要時間、前記出発駅から前記到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、
前記リンクデータと関連付けるための第２のリンクＩＤ、前記第２のリンクＩＤに対応した前記列車の運転日および前記列車の１日の出発時刻を特定ビットで表したビット列、および前記列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータと、
探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する前記時刻表ビットパターンデータの各ビットを検索し、前記探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部とを備えたことを特徴とする経路探索システム。
【請求項２】
請求項１に記載の経路探索システムにおいて、
前記時刻表ビットパターンデータは、ビット列として、１日を１ビットとし、該当する前記リンクＩＤで運行している列車が運行する日を「１」、運休する日を「０」に設定した列車運転日ビットパターン、および１分を１ビットとし、１日を１４４０ビットで表し、該当する前記リンクＩＤで運行している列車の出発時刻の位置に「１」、それ以外を「０」に設定した列車出発時刻ビットパターンを有することを特徴とする経路探索システム。
【請求項３】
出発駅、到着駅、列車、前記出発駅から前記到着駅に至る平均所要時間、前記出発駅から前記到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、前記リンクデータと関連付けるための第２のリンクＩＤ、前記第２のリンクＩＤに対応した前記列車の運転日および前記列車の１日の出発時刻を特定ビットで表したビット列、および前記列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有し、経路探索部により、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索方法であって、
前記経路探索部により、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する前記時刻表ビットパターンデータの各ビットを検索し、前記探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得することを特徴とする経路探索方法。
【請求項４】
請求項３に記載の経路探索方法において、
前記時刻表ビットパターンデータは、ビット列として、１日を１ビットとし、該当する前記リンクＩＤで運行している列車が運行する日を「１」、運休する日を「０」に設定した列車運転日ビットパターン、および１分を１ビットとし、１日を１４４０ビットで表し、該当する前記リンクＩＤで運行している列車の出発時刻の位置に「１」、それ以外を「０」に設定した列車出発時刻ビットパターンから構成されたことを特徴とする経路探索方法。
【請求項５】
出発駅、到着駅、列車、前記出発駅から前記到着駅に至る平均所要時間、前記出発駅から前記到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、前記リンクデータと関連付けるための第２のリンクＩＤ、前記第２のリンクＩＤに対応した前記列車の運転日および前記列車の１日の出発時刻を特定ビットで表したビット列、および前記列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有したコンピュータ上で実行され、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索プログラムであって、
前記コンピュータを、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する前記時刻表ビットパターンデータの各ビットを検索し、前記探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部として機能させることを特徴とする経路探索プログラム。
【請求項６】
請求項５に記載の経路探索プログラムにおいて、
前記時刻表ビットパターンデータは、ビット列として、１日を１ビットとし、該当する前記リンクＩＤで運行している列車が運行する日を「１」、運休する日を「０」に設定した列車運転日ビットパターン、および１分を１ビットとし、１日を１４４０ビットで表し、該当する前記リンクＩＤで運行している列車の出発時刻の位置に「１」、それ以外を「０」に設定した列車出発時刻ビットパターンから構成されたことを特徴とする経路探索プログラム。
【請求項１】
出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムであって、
出発駅、到着駅、前記出発駅から前記到着駅の間を走行する列車、前記出発駅から前記到着駅に至る平均所要時間、前記出発駅から前記到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、
前記リンクデータと関連付けるための第２のリンクＩＤ、前記第２のリンクＩＤに対応した前記列車の運転日および前記列車の１日の出発時刻を特定ビットで表したビット列、および前記列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータと、
探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する前記時刻表ビットパターンデータの各ビットを検索し、前記探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部とを備えたことを特徴とする経路探索システム。
【請求項２】
請求項１に記載の経路探索システムにおいて、
前記時刻表ビットパターンデータは、ビット列として、１日を１ビットとし、該当する前記リンクＩＤで運行している列車が運行する日を「１」、運休する日を「０」に設定した列車運転日ビットパターン、および１分を１ビットとし、１日を１４４０ビットで表し、該当する前記リンクＩＤで運行している列車の出発時刻の位置に「１」、それ以外を「０」に設定した列車出発時刻ビットパターンを有することを特徴とする経路探索システム。
【請求項３】
出発駅、到着駅、列車、前記出発駅から前記到着駅に至る平均所要時間、前記出発駅から前記到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、前記リンクデータと関連付けるための第２のリンクＩＤ、前記第２のリンクＩＤに対応した前記列車の運転日および前記列車の１日の出発時刻を特定ビットで表したビット列、および前記列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有し、経路探索部により、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索システムの経路探索方法であって、
前記経路探索部により、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する前記時刻表ビットパターンデータの各ビットを検索し、前記探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得することを特徴とする経路探索方法。
【請求項４】
請求項３に記載の経路探索方法において、
前記時刻表ビットパターンデータは、ビット列として、１日を１ビットとし、該当する前記リンクＩＤで運行している列車が運行する日を「１」、運休する日を「０」に設定した列車運転日ビットパターン、および１分を１ビットとし、１日を１４４０ビットで表し、該当する前記リンクＩＤで運行している列車の出発時刻の位置に「１」、それ以外を「０」に設定した列車出発時刻ビットパターンから構成されたことを特徴とする経路探索方法。
【請求項５】
出発駅、到着駅、列車、前記出発駅から前記到着駅に至る平均所要時間、前記出発駅から前記到着駅に至る距離、およびこれらを含むレコードに一意に割り振られた第１のリンクＩＤが格納されたリンクデータと、前記リンクデータと関連付けるための第２のリンクＩＤ、前記第２のリンクＩＤに対応した前記列車の運転日および前記列車の１日の出発時刻を特定ビットで表したビット列、および前記列車の時間帯別の最短所要時間が格納された時刻表ビットパターンデータとを保有したコンピュータ上で実行され、出発駅から到着駅に至る探索条件に合致した経路情報を探索する経路探索プログラムであって、
前記コンピュータを、探索対象の出発駅から到着駅に至る前記リンクデータの複数のレコードに対応する前記時刻表ビットパターンデータの各ビットを検索し、前記探索対象の出発駅から到着駅に至る経路で乗り継ぎ可能な経路を取得する経路探索部として機能させることを特徴とする経路探索プログラム。
【請求項６】
請求項５に記載の経路探索プログラムにおいて、
前記時刻表ビットパターンデータは、ビット列として、１日を１ビットとし、該当する前記リンクＩＤで運行している列車が運行する日を「１」、運休する日を「０」に設定した列車運転日ビットパターン、および１分を１ビットとし、１日を１４４０ビットで表し、該当する前記リンクＩＤで運行している列車の出発時刻の位置に「１」、それ以外を「０」に設定した列車出発時刻ビットパターンから構成されたことを特徴とする経路探索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１３−６００３９（Ｐ２０１３−６００３９Ａ）
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【出願番号】特願２０１１−１９８１５８（Ｐ２０１１−１９８１５８）
【出願日】平成２３年９月１２日（２０１１．９．１２）
【出願人】（０００２３３４９１）株式会社日立システムズ (394)
【Ｆターム（参考）】
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【出願日】平成２３年９月１２日（２０１１．９．１２）
【出願人】（０００２３３４９１）株式会社日立システムズ (394)
【Ｆターム（参考）】
[ Back to top ]