(57)【要約】【課題】乗換回数の少ない経路を少ない計算量で求める。【解決手段】乗車駅と降車駅とがユーザによって入力される。乗車駅を含む乗車駅路線と降車駅を含む降車駅路線とに共通駅があるかどうかが判断される（ステップ117，118）。上記共通駅がある場合に（ステップ118でYES），上記乗車駅から上記共通駅までの経路データと，上記降車駅から上記共通駅までの経路データとが作成され，作成された２つの経路データが上記共通駅において結合される。乗車ターミナルから降車ターミナルに至る，上記共通駅を経由する１本の経路候補データが作成される（ステップ119）。【選択図】図９
2014145690.tif 000002
【特許請求の範囲】
【請求項１】
乗車ターミナル名および降車ターミナル名の入力を受付け，上記乗車ターミナルから降車ターミナルまでの交通機関の経路データを出力する経路検索装置であって，
交通機関の複数の路線のそれぞれについて，上記路線に含まれる複数のターミナルをそれぞれ特定するターミナル特定データおよび上記路線に含まれる複数のターミナルの並び順を表すデータを含む路線データを記憶する路線データ記憶手段を備え，
上記乗車ターミナルを含む乗車ターミナル路線に上記降車ターミナルが含まれていない場合に，
上記乗車ターミナル路線と上記降車ターミナルを含む降車ターミナル路線とに共通ターミナルがあるかどうかを，上記乗車ターミナル路線の路線データと上記降車ターミナル路線の路線データとに基づいて判断し，上記共通ターミナルがある場合に上記乗車ターミナルから上記共通ターミナルまでの第１経路データと，上記降車ターミナルから上記共通ターミナルまでの第２経路データを検索する第１の経路データ検索手段，ならびに
上記第１の経路データ検索手段によって見つけられた第１経路データと第２の経路データを上記共通ターミナルにおいて結合することによって，乗車ターミナルから降車ターミナルまでの経路データを作成する第１の経路データ作成手段を備える，
経路検索装置。
【請求項２】
上記路線データ記憶手段に記憶されている上記路線データの中から，上記乗車ターミナル路線と上記降車ターミナル路線とをつなぐ中継路線があるかどうかを判断し，上記中継路線がある場合に，上記乗車ターミナルから上記乗車ターミナル路線と上記中継路線とに共通する中継始点ターミナルまでの第３経路データと，上記降車駅から上記降車ターミナル路線と上記中継路線とに共通する中継終点ターミナルまでの第４経路データとを検索する第２の経路データ検索手段，ならびに
上記第２の経路データ検索手段によって見つけられた第３経路データと第４経路データを，上記中継始点ターミナルから上記中継終点ターミナルまでの上記中継路線上の経路データを挟んで結合することによって，乗車ターミナルから降車ターミナルまでの経路データを作成する第２の経路データ作成手段を備える，
請求項１に記載の経路検索装置。
【請求項３】
上記路線データ記憶手段に記憶されている上記路線データの中から，上記乗車ターミナル路線に交わる，上記降車ターミナル路線および上記中継路線以外の第１の別路線があるかどうかを判断し，上記第１の別路線がある場合に上記乗車ターミナル路線と上記第１の別路線とを組合せた乗車ターミナル延長路線を作成する第１の延長路線作成手段を備え，
上記第１の経路データ検索手段および第２の経路データ検索手段が，上記乗車ターミナル路線に代えて上記乗車ターミナル延長路線を用いる，
請求項２に記載の経路検索装置。
【請求項４】
上記路線データ記憶手段に記憶されている上記路線データの中から，上記降車ターミナル路線に交わる，上記乗車ターミナル路線および上記中継路線以外の第２の別路線があるかどうかを判断し，上記第２の別路線がある場合に上記降車ターミナル路線と上記第２の別路線とを組合せた降車ターミナル延長路線を作成する第２の延長路線作成手段を備え，
上記第１の経路データ検索手段および第２の経路データ検索手段が，上記降車ターミナル路線に代えて上記降車ターミナル延長路線を用いる，
請求項２または３に記載の経路検索装置。
【請求項５】
乗車ターミナル名および降車ターミナル名の入力を受付け，上記乗車ターミナルから降車ターミナルまでの交通機関の経路データを出力する経路検索装置を制御するプログラムであって，
路線データ記憶手段に，交通機関の複数の路線のそれぞれについて，上記路線に含まれる複数のターミナルをそれぞれ特定するターミナル特定データおよび上記路線に含まれる複数のターミナルの並び順を表すデータを含む路線データを記憶させ，
上記乗車ターミナルを含む乗車ターミナル路線に上記降車ターミナルが含まれていない場合に，
上記乗車ターミナル路線と上記降車ターミナルを含む降車ターミナル路線とに共通ターミナルがあるかどうかを，上記乗車ターミナル路線の路線データと上記降車ターミナル路線の路線データとに基づいて判断し，上記共通ターミナルがある場合に上記乗車ターミナルから上記共通ターミナルまでの第１経路データと，上記降車ターミナルから上記共通ターミナルまでの第２経路データを検索し，
見つけられた第１経路データと第２の経路データを上記共通ターミナルにおいて結合することによって，乗車ターミナルから降車ターミナルまでの経路データを作成するようにコンピュータを制御する，
コンピュータ読み取り可能な経路検索プログラム。
【請求項６】
上記路線データの中から，上記乗車ターミナル路線と上記降車ターミナル路線とをつなぐ中継路線があるかどうかを判断し，上記中継路線がある場合に，上記乗車ターミナルから上記乗車ターミナル路線と上記中継路線とに共通する中継始点ターミナルまでの第３経路データと，上記降車駅から上記降車ターミナル路線と上記中継路線とに共通する中継終点ターミナルまでの第４経路データとを検索し，
見つけられた第３経路データと第４経路データを，上記中継始点ターミナルから上記中継終点ターミナルまでの上記中継路線上の経路データを挟んで結合することによって，乗車ターミナルから降車ターミナルまでの経路データを作成するようにコンピュータを制御する，
請求項５に記載の経路検索プログラム。
【請求項７】
上記路線データの中から，上記乗車ターミナル路線に交わる，上記降車ターミナル路線および上記中継路線以外の第１の別路線があるかどうかを判断し，上記第１の別路線がある場合に上記乗車ターミナル路線と上記第１の別路線とを組合せた乗車ターミナル延長路線を作成し，
上記第１経路データおよび第２経路データ，ならびに第３経路データおよび第４経路データの検索に，上記乗車ターミナル路線に代えて上記乗車ターミナル延長路線を用いるようにコンピュータを制御する，
請求項６に記載の経路検索プログラム。
【請求項８】
上記路線データの中から，上記降車ターミナル路線に交わる，上記乗車ターミナル路線および上記中継路線以外の第２の別路線があるかどうかを判断し，上記第２の別路線がある場合に上記降車ターミナル路線と上記第２の別路線とを組合せた降車ターミナル延長路線を作成し，
上記第１経路データおよび第２経路データ，ならびに上記第３経路データおよび第４経路データの検索に，上記降車ターミナル路線に代えて上記降車ターミナル延長路線を用いるようにコンピュータを制御する，
請求項６または７に記載の経路検索プログラム。
【請求項９】
請求項５から８のいずれか一項に記載の経路検索プログラムが記録された，コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は経路検索装置および経路検索プログラムに関する。
【背景技術】
【０００２】
ダイクストラ法を用いて出発点から目的点までの最小コスト経路を検索する経路検索が知られている（特許文献１）。コストとは具体的には時間，距離，料金等であり，たとえば出発点から目的点まで最短時間で到達する経路がダイクストラ法によって見つけられる。
【０００３】
ダイクストラ法を用いると，上述したように，最短時間，最小距離または最低料金で出発点から目的点に到達する経路を見つけることができる。しかしながら，出発点（ノード）から目的点（ノード）に至るまでのリンク（枝）の数が少ない経路の検索にダイクストラ法は適していない。リンク数はリンクのそれぞれを別路線と考えると乗換回数を表す。最短時間，最小距離，最低料金等について複数の経路を検索し，その中から乗換回数の少ない経路を選び出すことはできる。しかしながら，この場合，乗換回数の少ない経路を見つけるためにはダイクストラ法を用いて最短時間，最小距離，最低料金等の複数の経路を先に見つけおかなければならず，その複数の経路を検索する処理を伴うことが前提となってしまう。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第３３５３０２９号公報
【発明の開示】
【０００５】
この発明は，経路検索処理の処理負担を軽くすることを目的とする。
【０００６】
この発明はさらに，乗換回数の少ない乗車ターミナルから降車ターミナルに至る経路を少ない計算量で求めることができる新たな経路検索処理を提供することを目的とする。
【０００７】
この発明による経路検索装置は，乗車ターミナル名および降車ターミナル名の入力を受付け，上記乗車ターミナルから降車ターミナルまでの交通機関の経路データを出力するものであって，交通機関の複数の路線のそれぞれについて，上記路線に含まれる複数のターミナルをそれぞれ特定するターミナル特定データおよび上記路線に含まれる複数のターミナルの並び順を表すデータを含む路線データを記憶する路線データ記憶手段を備え，上記乗車ターミナルを含む乗車ターミナル路線に上記降車ターミナルが含まれていない場合に，上記乗車ターミナル路線と上記降車ターミナルを含む降車ターミナル路線とに共通ターミナルがあるかどうかを，上記乗車ターミナル路線の路線データと上記降車ターミナル路線の路線データとに基づいて判断し，上記共通ターミナルがある場合に上記乗車ターミナルから上記共通ターミナルまでの第１経路データと，上記降車ターミナルから上記共通ターミナルまでの第２経路データを検索する第１の経路データ検索手段，ならびに上記第１の経路データ検索手段によって見つけられた第１経路データと第２の経路データを上記共通ターミナルにおいて結合することによって，乗車ターミナルから降車ターミナルまでの経路データを作成する第１の経路データ作成手段を備える。
【０００８】
この発明による経路検索装置は，乗車ターミナル路線上に降車ターミナルが存在しないことを前提とする。乗車ターミナル路線上に降車ターミナルが含まれていれば，乗換なしで（乗換回数０回），その路線を用いた乗車ターミナルから降車ターミナルまでの経路データを作成してもよい。乗車ターミナル路線上に降車ターミナルが含まれていないことは，乗車ターミナル路線の路線データに含まれるターミナル特定データに基づいて判断される。
【０００９】
この発明によると，乗車ターミナル路線と降車ターミナル路線の両方に共通ターミナルがあることが判断された場合に，乗車ターミナルから共通ターミナルを経由して降車ターミナルに至る経路データが作成される。共通ターミナルとは乗車ターミナル路線と降車ターミナル路線の両方に存在する共通のターミナルを意味する。共通ターミナルがあるかどうかは，乗車ターミナル路線の路線データと降車ターミナル路線の路線データとに基づいて判断される。ターミナル特定データ，たとえばターミナル名称，ターミナルごとにあらかじめ付与されるターミナルＩＤ等に基づいて，乗車ターミナル路線と降車ターミナル路線の両方に存在する共通のターミナルがあるかどうかを判断することができる。なお，名称は異なるものの間隔（距離）の短い２つのターミナル（たとえば「ＪＲ大阪駅」と「御堂筋線梅田駅」など）については同一のＩＤ（ターミナル特定データ）をそれぞれ付与しておくことで，共通ターミナルとして扱うこともできる。
【００１０】
上記経路データは，乗車ターミナルから共通ターミナルまでの第１経路データと，降車ターミナルから共通ターミナルまでの第２経路データを上記共通ターミナルにおいて結合することによって作成される。すなわち，本願発明の経路検索装置は，乗車ターミナルから降車ターミナルに到達する経路を，乗車ターミナル側からと降車ターミナル側からの両がわから求め，それを共通ターミナルで結合することによって作成する。乗換回数は１回であり，乗車ターミナルから降車ターミナルに到達する乗換回数の少ない経路が得られる。
【００１１】
この発明による経路検索装置の経路検索のアルゴリズムは，一般に用いられているダイクストラ法による検索と大きく異なる。ダイクストラ法では，空集合から始めて最短路となるノードを一つずつ求めて最短路部分集合を得（最短路となるノードを求めるためにノードとノードの間（リンク）のコスト（時間，料金など）は既知である），これを順次を膨らませていくことで最終的に全部のノードに対して最短路を求め，基本的に出発点から目的点に向かって最短路を得る。また，ダイクストラ法は，出発点から目的点に至るまでに通過するリンクの数（乗換回数）が最小の経路を求めるアルゴリズムではない。
【００１２】
この発明による経路検索装置は，従来用いられているダイクストラ法と異なり，乗換回数の少ない経路検索に適するアルゴリズムを持つ。乗車ターミナルから降車ターミナルまでの移動において，たとえば所要時間の短い経路よりも乗換回数の少ない経路を見つけたい場合に便利である。また，ノード（ターミナル）とノード（ターミナル）の間（リンク）のコスト（時間，料金など）は既知である必要も必ずしもない。ダイクストラ法よりもかなり計算回数が少ないので，経路検索装置にかかる処理負担が軽く短時間のうちに経路検索処理を終了することができる。
【００１３】
一実施態様では，上記路線データ記憶手段に記憶されている上記路線データの中から，上記乗車ターミナル路線と上記降車ターミナル路線とをつなぐ中継路線があるかどうかを判断し，上記中継路線がある場合に，上記乗車ターミナルから上記乗車ターミナル路線と上記中継路線とに共通する中継始点ターミナルまでの第３経路データと，上記降車駅から上記降車ターミナル路線と上記中継路線とに共通する中継終点ターミナルまでの第４経路データとを検索する第２の経路データ検索手段，ならびに上記第２の経路データ検索手段によって見つけられた第３経路データと第４経路データを，上記中継始点ターミナルから上記中継終点ターミナルまでの上記中継路線上の経路データを挟んで結合することによって，乗車ターミナルから降車ターミナルまでの経路データを作成する第２の経路データ作成手段を備える。
【００１４】
中継路線とは，上記乗車ターミナル路線および降車ターミナル路線とは異なる路線であって，上記乗車ターミナル路線上の一のターミナルと共通するターミナル（これが中継始点ターミナルである）を含み，かつ上記降車ターミナル路線上の他のターミナルと共通するターミナル（これが中継終点ターミナルである）を含む路線である。
【００１５】
「乗車ターミナル路線」〜「中継路線」〜「降車ターミナル路線」を通る経路データが作成される。乗換回数が２回の経路が検索される。
【００１６】
他の実施態様では，上記路線データ記憶手段に記憶されている上記路線データの中から，上記乗車ターミナル路線に交わる，上記降車ターミナル路線および上記中継路線以外の第１の別路線があるかどうかを判断し，上記第１の別路線がある場合に上記乗車ターミナル路線と上記第１の別路線とを組合せた乗車ターミナル延長路線を作成する第１の延長路線作成手段を備え，上記第１の経路データ検索手段および第２の経路データ検索手段が，上記乗車ターミナル路線に代えて上記乗車ターミナル延長路線を用いることを特徴とする。乗車ターミナル路線と第１の別路線の組合せ（乗車ターミナル路線と第１の別路線があたかも一つの路線であるかのように扱われる）（＝乗車ターミナル延長路線）と降車ターミナル路線とに共通ターミナルがあれば，「乗車ターミナル路線」〜「第１の別路線」〜「降車ターミナル路線」を通る経路データが作成される。乗車ターミナル路線と第１の別路線の組合せ（＝乗車ターミナル延長路線）と降車ターミナル路線とをつなぐ中継路線があれば，「乗車ターミナル路線」〜「第１の別路線」〜「中継路線」〜「降車ターミナル路線」を通る経路データが作成される。
【００１７】
他の実施態様では，上記路線データ記憶手段に記憶されている上記路線データの中から，上記降車ターミナル路線に交わる，上記乗車ターミナル路線および上記中継路線以外の第２の別路線があるかどうかを判断し，上記第２の別路線がある場合に上記降車ターミナル路線と上記第２の別路線とを組合せた降車ターミナル延長路線を作成する第２の延長路線作成手段を備え，上記第１の経路データ検索手段および第２の経路データ検索手段が，上記降車ターミナル路線に代えて上記降車ターミナル延長路線を用いることを特徴とする。降車ターミナル路線と第２の別路線の組合せ（降車ターミナル路線と第２の別路線があたかも一つの路線であるかのように扱われる）（＝降車ターミナル延長路線）と乗車ターミナル路線とに共通ターミナルがあれば，「乗車ターミナル路線」〜「第２の別路線」〜「降車ターミナル路線」を通る経路データが作成される。降車ターミナル路線と第２の別路線の組合せ（＝降車ターミナル延長路線）と乗車ターミナル路線とをつなぐ中継路線があれば，「乗車ターミナル路線」〜「中継路線」〜「第２の別路線」〜「降車ターミナル路線」を通る経路データが作成される。
【００１８】
この発明は，上述した経路検索装置を制御するのに適するコンピュータ・プログラムおよびこれを記録した記録媒体も提供している。
【図面の簡単な説明】
【００１９】
【図１】経路検索装置のブロック図である。
【図２】入力画面を示す。
【図３】検索結果画面を示す。
【図４】路線図を示す。
【図５】路線群データを示す。
【図６】駅データを示す。
【図７】経路検索処理のフローチャートである。
【図８】経路検索処理のフローチャートである。
【図９】経路検索処理のフローチャートである。
【図１０】経路検索処理のフローチャートである。
【図１１】経路検索処理のフローチャートである。
【図１２】経路検索処理のフローチャートである。
【図１３】経路検索処理のフローチャートである。
【図１４】（Ａ）および（Ｂ）は乗車駅路線「Ａ線」の乗車駅始点進行データを示す。
【図１５】（Ａ）および（Ｂ）は降車駅路線「Ｂ線」の降車駅終点進行データを示す。
【図１６】（Ａ）は「Ａ線」の駅データ条件を，（Ｂ）は「Ｂ線」の駅データ条件を，それぞれ示す。
【図１７】経路候補データを示す。
【図１８】（Ａ）および（Ｂ）は乗車駅延長路線「ＡＦ線」の乗車駅始点延長路線進行データを示す。
【図１９】乗車駅延長路線「ＡＦ線」の駅データ条件を示す。
【図２０】（Ａ）および（Ｂ）は降車駅延長路線「ＢＣ線」の降車駅終点延長路線進行データを，（Ｃ）および（Ｄ）は降車駅延長路線「ＢＥ線」の降車駅終点延長路線進行データを示す。
【図２１】（Ａ）は降車駅延長路線「ＢＣ線」の駅データ条件を，（Ｂ）は降車駅延長路線「ＢＥ線」の駅データ条件をそれぞれ示す。
【図２２】経路候補データを示す。
【図２３】（Ａ）および（Ｂ）は降車駅延長路線「ＢＣＤ線」の降車駅終点延長路線進行データを，（Ｃ）および（Ｄ）は降車駅延長路線「ＢＤＥ線」の降車駅終点延長路線進行データを，それぞれ示す。
【図２４】（Ａ）は降車駅延長路線「ＢＣＤ線」の駅データ条件を，（Ｂ）は降車駅延長路線「ＢＤＥ線」の駅データ条件を，それぞれ示す。
【発明を実施するための形態】
【００２０】
図１は経路検索装置のブロック図を示している。
【００２１】
経路検索装置１は，ユーザによって入力される「乗車駅」および「降車駅」間の交通機関の経路を検索し，検索により見つかった「乗車駅」から「降車駅」に至るまでの交通機関の経路を出力する装置である。「乗車駅」から「降車駅」に至るまでに乗換が必要とされる場合には，経路検索装置１によって出力される交通機関の経路には「乗換駅」も含まれる。
【００２２】
図１を参照して，経路検索装置１は中央演算処理装置（ＣＰＵ）２を含むコンピュータ・システムによって構成され，ＣＰＵ２によって経路検索装置１の全体が制御される。ＣＰＵ２に，データを一時的に記憶するメモリ３，経路検索に用いられるプログラムおよびデータを記憶する記憶装置（ハードディスクなど）４，上述した乗車駅，降車駅等の入力に用いられる入力装置（キーボード，マウスなど）５，入力される乗車駅の名称，降車駅の名称，検索によって見つけられた乗車駅から降車駅までの経路を表示する表示画面を備える表示装置６，およびデータ通信のための通信装置７が接続されている。記録装置４に記憶されている経路検索プログラムおよびデータがメモリ３に読込まれ，ＣＰＵ２によって経路検索プログラムが実行されることで，コンピュータ・システムが経路検索装置１として機能する。
【００２３】
ＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭ等（図示略）に記録されている経路検索プログラムおよびデータをコンピュータ・システムの記憶装置４にインストールすることでコンピュータ・システムを経路検索装置１として機能させることができる。もっとも，乗車駅，降車駅等の入力情報は，経路検索装置１とネットワーク接続された携帯端末装置（図示略）から通信装置７を介して経路検索装置１に与え，かつ経路検索装置１によって見つけられた乗車駅から降車駅までの経路情報（検索結果情報）を通信装置７を介して上記携帯端末装置に送信してもよい。
【００２４】
図２は上記表示装置６の表示画面に表示される入力画面11の一例を示している。図３は上記表示画面６の表示画面に表示される検索結果画面12の一例を示している。
【００２５】
入力画面11（図２）には「乗車駅」および「降車駅」を入力する入力ボックス11ａ，11ｂと，「経路探索」ボタン11ｃが設けられている。入力画面11の入力ボックス11ａ，11ｂに，上記入力装置５が用いられて「乗車駅」と「降車駅」とがそれぞれ入力される。入力ボックス11ａ，11ｂには文字入力によって乗車駅名および降車駅名をそれぞれ直接に入力してもよいし，表示画面上に表示される路線図の中から乗車駅と降車駅をそれぞれ選択（クリックまたはタッチで特定）してもよい。乗車駅に代えて現在位置をユーザに入力させてもよい（上記携帯端末装置にＧＰＳ機能が内蔵されている場合には現在位置を自動入力することができる）。この場合には現在位置からの距離が最も近い駅が「乗車駅」として扱われる。降車駅についても，降車駅自体を入力するのに代えて目的地（たとえば観光地など）をユーザに入力させてもよい。目的地からの距離が最も近い駅が「降車駅」として扱われる。
【００２６】
「経路探索」ボタン11ｃが入力装置５が用いられてクリックされると，後述する経路検索装置１による経路検索処理が実行される。見つけられた「乗車駅」から「降車駅」までの交通機関の経路は，入力画面11に代えて表示画面上に表示される検索結果画面12（図３）に表示される。検索結果画面12には，入力された乗車駅および降車駅，乗車駅から降車駅までの経路に存在する乗換駅（駅Ａおよび駅Ｂ），乗車駅から駅Ａまでの移動に用いられる路線（○○線），駅Ａから駅Ｂまでの移動に用いられる路線（△△線），および駅Ｂから降車駅までの移動に用いられる路線（□□線）が表示される。入力画面11に入力されかつ表示される乗車駅および降車駅，検索結果画面12に表示される乗車駅，降車駅，乗換駅および路線は，現実に敷設されている交通機関，この実施例では鉄道の駅名および路線名である。検索結果画面12に路線図を表示して，路線図上において乗車駅から降車駅に至る経路を色を変えて表示してもよい。
【００２７】
図４は路線図の一例を示している。図５は図４の路線図に対応するもので，経路検索装置１の記憶装置４に記憶されている路線群データを示している。図６も図４の路線図に対応するもので，記憶装置４に記憶されている駅データの一例を示している。
【００２８】
図４に示す路線図には，細長い矩形の枠によってＡ線，Ｂ線，Ｃ線，Ｄ線，Ｅ線およびＦ線の６つの異なる路線が示されている。各路線上の複数の駅が角が丸められた枠によって示されており，隣合う駅同士は実線によって結ばれている。
【００２９】
図５を参照して，路線群データは，複数の路線，この実施例ではＡ線〜Ｆ線の６つの路線のそれぞれについての路線データを含む。各路線データは，路線ＩＤ，路線名，路線上の駅名（駅を特定する駅ＩＤでもよい）および選択済フラグを含む。路線データには各路線における駅の並び順にしたがって駅名が順番に格納されており，路線データによって上り方向および下り方向の駅の並び順も特定される。選択済フラグには，後述するように，true またはfalseのいずれかが書き換え可能に格納される。
【００３０】
図６を参照して，駅データは，上記複数の路線のそれぞれについて，各駅ごとに，その駅に隣接する前の駅（下り方向）および次の駅（上り方向）を特定するデータと，駅間の移動に要する所要時間に関するデータとを含む。もちろん，駅データには，電車の種類（特急，急行など）ごとに，前の駅，次の駅および所要時間を格納してもよい。駅データによっても上り方向および下り方向の隣接駅が把握され，さらに隣接駅までの所要時間がわかる。時刻表データ，運賃データその他のデータを駅データにさらに含ませることもできる。
【００３１】
以下，図４に示す路線図を具体例にして，経路検索装置１の処理を詳細に説明する。
【００３２】
図７から図１３は，経路検索装置１によって実行される処理を示すフローチャートである。
【００３３】
上述したように，はじめに入力画面11（図２）が用いられて「乗車駅」と「降車駅」とが入力される。経路探索ボタン11ｃがクリックされると，以下の経路検索処理がスタートする。
【００３４】
図７を参照して，はじめにメモリ領域の初期化処理が行われる（ステップ101 ）。ここでは，メモリ３に設けられる「経路データ」，「経路候補データ群」および「未選択路線数」の３つのメモリ領域に対する初期化処理が行われる。「経路データ」および「経路候補データ群」のメモリ領域にはnullコードが格納され，「未選択路線数」のメモリ領域には初期値「０」が格納される。「経路データ」，「経路候補データ群」および「未選択路線数」の詳細な説明は後述する。詳細は後述するが，メモリ３には「乗車駅からの路線データ有フラグ」および「降車駅からの路線データ有フラグ」を格納するためのメモリ領域も用意される。
【００３５】
経路検索処理の対象の路線データ（図４参照）のそれぞれに規定される選択済フラグ（図５参照）の初期化処理が行われ，選択済フラグが「false」とされる（ステップ102）。Ａ線，Ｂ線，Ｃ線，Ｄ線，Ｅ線およびＦ線の６つの路線の路線データのそれぞれの選択済フラグが「false」とされる。
【００３６】
選択済フラグが「false」である路線データ数がカウントされ，カウントされた数が上述した「未選択路線数」のメモリ領域に格納される（ステップ103）。初期状態では６つの路線データのすべてに選択済フラグ「false」が設定されているので，「６」が未選択路線数となる。
【００３７】
以下，具体的な乗車駅および降車駅を挙げて，経路検索装置１による経路決定処理を詳細に説明する。
【実施例１】
【００３８】
乗車駅「駅２」，降車駅「駅５」の場合
ユーザによって入力された「乗車駅」を含む路線データが取得され（メモリ３に一時的に記憶され），その選択済フラグが「false」から「true」に変更される（ステップ104）。図４および図５を参照して，ユーザが入力した乗車駅が「駅２」であれば，乗車駅「駅２」を含む路線（「乗車駅路線」と呼ぶ）はＡ線である。乗車駅路線「Ａ線」の路線データの選択済フラグが「true」に変更される。なお，ユーザが入力した乗車駅が複数の路線が通る駅であれば複数の路線の選択済フラグが「true」となる。図４を参照して，たとえばユーザが入力した乗車駅が「駅３」であれば，Ａ線およびＢ線の２つの路線について選択済フラグが「true」になる。
【００３９】
選択済フラグが「true」の路線，ここでは乗車駅路線の路線データに基づいて，乗車駅を始点とする，上りと下りのそれぞれについての駅名およびその順番から構成される上り進行データおよび下り進行データが作成され，メモリ３に一時的に記憶される（ステップ105 ）。たとえば，図４および図１４（Ａ），（Ｂ）を参照して，ユーザが入力した乗車駅が「駅２」であれば，乗車駅（駅２）−駅３−駅４−駅５−駅６からなる乗車駅を始点とする上り進行データ（「乗車駅始点上り進行データ」と呼ぶ：図１４（Ａ））と，乗車駅（駅２）−駅１からなる乗車駅を始点とする下り進行データ（「乗車駅始点下り進行データ」と呼ぶ：図１４（Ｂ））とが作成されることになる。
【００４０】
次に，乗車駅始点上り進行データまたは乗車駅始点下り進行データ中に，ユーザによって入力された「降車駅」が含まれているかどうかが判断される（ステップ106）。
【００４１】
乗車駅始点上り／下り進行データ中に降車駅が含まれている場合（ステップ106でYES），乗車駅から降車駅までの駅名とその順番とから構成される経路データ（路線名を含む）が取り出され，上述した経路候補データ群のメモリ領域に格納される（ステップ107 ）。乗車駅が「駅２」でかつ降車駅が「駅５」であれば，降車駅「駅５」は乗車駅路線「Ａ線」上の駅であるから，上述した乗車駅始点上り進行データ（図１４（Ａ））に含まれている。乗車駅（駅２）−駅３−駅４−降車駅（駅５）からなる経路データが経路候補データ群のメモリ領域に格納されることになる。なお，乗車駅および降車駅がいずれも環状線上の駅であれば，乗車駅始点上り進行データと乗車駅下り進行データの両方に降車駅が含まれることになるので，乗車駅から降車駅までの２つの経路データ（内回りおよび外回り）が，経路候補データ群のメモリ領域に格納されることになる。
【００４２】
図９を参照して，乗車駅路線に降車駅が含まれている場合には，経路候補データ群に格納された経路候補データがそのまま経路データとして決定され，経路データのメモリ領域に格納される（ステップ108でYES ，ステップ109）。なお，経路候補データが複数存在する場合には，その中から，乗換回数が最も少ない経路，乗車駅から降車駅までの駅数が最も少ない経路，運賃が最も安い経路，または乗車駅から降車駅までの所要時間が最も短い経路が，経路データとして決定される。
【００４３】
決定された経路データが検索結果画面12（図３）における表示に用いられる（ステップ110 ）。経路データに含まれる乗車駅から降車駅までの駅名とその順番と路線名のうち，乗車駅名，降車駅名および路線名が用いられて検索結果画面12が作成される。経路検索処理が終了する。
【実施例２】
【００４４】
乗車駅「駅２」，降車駅「駅11」の場合
乗車駅が「駅２」，降車駅が「駅11」であったとする。図４を参照して，乗車駅路線（「Ａ線」と降車駅路線「Ｂ線」とは路線が異なっており，このため乗車駅始点上り／下り進行データ（図１４（Ａ），（Ｂ））に降車駅「駅11」は含まれていない。乗車駅始点上り／下り進行データに降車駅が含まれていない場合（図７，ステップ106 でNO），図８を参照して，降車駅を含む路線データが取得されて，その選択済フラグが「false」から「true」に変更され（ステップ111），さらに選択済フラグが「true」に変更された降車駅路線に基づいて，「降車駅」を終点とする，上りと下りのそれぞれについての駅名およびその順番から構成される上り進行データおよび下り進行データが作成される（ステップ112 ）。ユーザが入力した降車駅が「駅11」であれば，図１５（Ａ），（Ｂ）に示すように，降車駅路線「Ｂ線」について駅７−駅３−駅８−駅９−駅10−降車駅（駅11）からなる上り進行データと，駅12−降車駅（駅11）からなる下り進行データとが作成される。
【００４５】
選択済フラグが未だに「false 」である件数が，未選択路線数のメモリ領域に上書きされて格納される（ステップ113 ）。乗車駅が「駅２」，降車駅が「駅11」であれば，ここまでの処理で乗車駅路線「Ａ線」と降車駅路線「Ｂ線」の選択済フラグが「true」に変更されており，Ｃ線，Ｄ線，Ｅ線およびＦ線の選択済フラグが「false 」のままであるので，未選択路線数は「４」となる。
【００４６】
次に，乗車駅路線の駅データ条件と降車駅路線の駅データ条件とが作成される（ステップ114，115）。駅データ条件とは路線上の駅名（駅ＩＤでもよい）をorでつないだ条件式を意味する。図１６（Ａ），（Ｂ）に示すように，乗車駅が「駅２」，降車駅が「駅11」であれば，乗車駅路線の駅データ条件は乗車駅路線「Ａ線」上のすべての駅を含む（駅１or駅２or駅３or駅４or駅５or駅６）となり，降車駅路線の駅データ条件は降車駅路線「Ｂ線」上のすべての駅を含む（駅３or駅７or駅８or駅９or駅10or駅11or駅12）となる。
【００４７】
図９を参照して，乗車駅路線の駅データ条件と降車駅路線の駅データ条件がアンド検索されて，乗車駅路線と降車駅路線の両方を通る駅（以下，「共通駅」という）が検索される（ステップ116でNO，ステップ117）。すなわち，乗車駅路線「Ａ線」の駅データ条件と降車駅路線「Ｂ線」の駅データ条件の両方に含まれる駅が存在するかどうかが判断される。
【００４８】
図１６（Ａ），（Ｂ）に示す２つの駅データ条件には，そのいずれにも「駅３」が含まれている（破線で囲って示す）。ステップ117 で「駅３」が検索されて見つけられることになる。
【００４９】
共通駅が見つかった場合（ステップ118でYES），乗車駅始点進行データの中から乗車駅から共通駅に至る経路データを取得し，かつ降車駅終点進行データの中から降車駅から共通駅に至る経路データを取得し，共通駅で２つの経路データをつなげることによって１本の経路候補データを作成する（ステップ119 ）。乗車駅が「駅２」，降車駅が「駅11」，共通駅が「駅３」であれば，図１７に示すように，「乗車駅（駅２）−共通駅（駅３）−駅８−駅９−駅10−降車駅（駅11）」からなる，共通駅（駅３）を経由するＡ線およびＢ線を通る経路候補データ（路線名を含む）が作成される。
【００５０】
作成された経路候補データは，同じ経路候補データが経路候補データ群のメモリ領域に既に格納されていないことを条件にして，経路候補データ群のメモリ領域に格納される（ステップ120）。
【００５１】
次に乗車駅路線の駅データ条件を満たし，かつ降車駅路線の駅データ条件を満たす駅データ条件を持つ路線を，選択済フラグが「false」の路線データから検索する（ステップ121）。これは，乗車駅路線と降車駅路線とをつなぐ，乗車駅路線および降車駅路線とは異なる路線（以下，「中継路線」と呼ぶ）を見つける処理であり，詳細は後述する。乗車駅が「駅２」，降車駅が「駅11」であれば，ここまでの処理で選択済フラグが「false 」であるＣ線，Ｄ線，Ｅ線およびＦ線の中から，乗車駅路線「Ａ線」の駅データ条件を満たし，かつ降車駅路線「Ｂ線」の駅データ条件を満たす，そのような駅データ条件を持つ路線が検索される。このような路線は無いので，図１１のステップ128 に進む（図１０，ステップ122でNO）。
【００５２】
図１１を参照して，選択済フラグが「false 」の路線データのうち，乗車駅始点進行データ上の駅を通る別の路線データ（乗車駅路線に交わる路線）があるかが調べられる（ステップ128 ）。図４を参照して，乗車駅が「駅２」であれば，駅２を含む乗車駅路線「Ａ線」は，駅３において別の路線「Ｂ線」が通っており，さらに駅６において別の路線「Ｆ線」が通っている。「Ｂ線」は降車駅路線であって既に選択済フラグが「true」とされているので，ステップ128では「Ｆ線」が見つけられる。
【００５３】
ステップ128 で別路線データが見つかった場合（ステップ129でYES），「乗車駅からの路線データ有フラグ」が「true」とされ（ステップ132），さらにステップ128で見つかった別路線の路線データの選択済フラグが「true」とされる（ステップ133 ）。上述の例ではＦ線の路線データの選択済フラグが「true」になる。
【００５４】
乗車駅を始点とする上記別路線が交わる駅までの進行データと，上記別路線が交わる駅を始点とする別路線上の上り／下り進行データとが，上記交わる駅でつなげられて，乗車駅を始点とし，上記交わる駅を経由する，上記別路線上の上り／下り進行データが作成される（ステップ134 ）。乗車駅路線は「Ａ線」であり，見つかった別路線は「Ｆ線」であるから，図１８（Ａ），（Ｂ）に示すように，乗車駅（駅２）−駅３−駅４−駅５−交わる駅（駅６）−駅25−駅21−駅26からなるＡ線とＦ線の組合せ（乗車駅延長路線「ＡＦ線」）についての上り進行データ（図１８（Ａ））と，乗車駅（駅２）−駅３−駅４−駅５−交わる駅（駅６）−駅24からなる乗車駅延長路線「ＡＦ線」についての下り進行データ（図１８（Ｂ））とが作成される。以下，この進行データを「乗車駅始点延長路線進行データ」と呼ぶ。
【００５５】
乗車駅路線の駅データ条件（図８のステップ114 で作成されたもの）に上記別路線の駅データ条件が追加される（ステップ135 ）。乗車駅路線が「Ａ線」であり，上記見つかった別路線が「Ｆ線」であれば，図１９に示すように，Ａ線とＦ線（乗車駅延長路線「ＡＦ線」）の駅をすべて含む駅データ条件，すなわち（駅１or駅２or駅３or駅４or駅５or駅６or駅21or駅24or駅26）が作成される。ここで作成される駅データ条件を「乗車駅延長路線駅データ条件」と呼ぶ。
【００５６】
図１２を参照して，次に，選択済フラグが「false 」の路線データのうち，降車駅終点進行データ上の駅を通る別の路線データがあるかが調べられる（ステップ136 ）。図４を参照して，降車駅が駅11であって降車駅路線が「Ｂ線」であれば，Ｂ線は，駅３において別路線「Ａ線」が通っており，駅10において別路線「Ｃ線」が通っており，さらに駅12において別路線「Ｅ線」が通っている。Ａ線は既に選択済フラグが「true」であるから，ステップ136ではＣ線およびＥ線が見つけられる。
【００５７】
ステップ136 で別路線が見つかった場合（ステップ137でYES），「降車駅からの路線データ有フラグ」が「true」とされ（ステップ138），さらにステップ136で見つかった別路線の路線データの選択済フラグが「true」とされる（ステップ140 ）。この例ではＣ線とＥ線の路線データの選択済フラグが「true」となる。
【００５８】
降車駅を終点とする上記別路線が交わる駅までの進行データと，上記別路線が交わる駅を始点とする別路線上の上り／下り進行データとが，上記交わる駅でつなげられ，降車駅を終点とし，上記交わる駅を経由する，上記別路線上の上り／下り進行データが作成される（ステップ141 ）。ここでは，降車駅路線は「Ｂ線」であり，別路線が「Ｃ線」および「Ｅ線」である。図２０（Ａ），（Ｂ）に示すように，別路線が「Ｃ線」である場合について，駅13−交わる駅（駅10）−降車駅（駅11）からなる降車駅延長路線「ＢＣ線」の上り進行データと，駅16−駅15−駅14−交わる駅（駅10）−降車駅（駅11）からなる降車駅延長路線「ＢＣ線」の下り進行データ（降車駅終点延長路線進行データ）が作成される。図２０（Ｃ），（Ｄ）に示すように，別路線が「Ｅ線」である場合については，交わる駅（駅12）−降車駅（駅11）からなる降車駅延長路線「ＢＥ線」の上り進行データと，駅23−駅22−駅21−駅19−駅20−交わる駅（駅12）−降車駅（駅11）からなる降車駅延長路線「ＢＥ線」の下り進行データが作成される。
【００５９】
降車駅路線の駅データ条件（図８のステップ115 で作成されたもの）に，上記別路線の駅データが追加される（ステップ142 ）。図２１（Ａ）を参照して，別路線が「Ｃ線」である場合については，Ｂ線とＣ線の駅を全て含む駅データ条件（降車駅延長路線「ＢＣ線」の降車駅延長路線駅データ条件），すなわち（駅３or駅７or駅８or駅９or駅10or駅11or駅12or駅13or駅14or駅15or駅16）が作成される。図２１（Ｂ）を参照して，別路線が「Ｅ線」である場合については，Ｂ線とＥ線の駅を全て含む駅データ条件＝（駅３or駅７or駅８or駅９or駅10or駅11or駅12or駅19or駅20or駅21or駅22or駅23）（降車駅延長路線「ＢＥ線」の降車駅延長路線駅データ条件）が作成される。
【００６０】
図１３を参照して，上述した「乗車駅からの経路データ有フラグ」および「降車駅からの経路データ有フラグ」の少なくとも一方が「true」である場合（ステップ143 でNO），未選択路線数は０ではない（図９のステップ116でNO）。２回目のステップ117の処理に進む。２回目のステップ117の処理では，ステップ135で作成された乗車駅延長路線「ＡＦ線」の駅データ条件（図１９）と，ステップ142 で作成された降車駅延長路線「ＢＣ線」および「ＢＥ線」の駅データ条件（図２１（Ａ），（Ｂ））を満たす共通駅が検索される。ここでは乗車駅延長路線「ＡＦ」線の駅データ条件と，降車駅延長路線「ＢＣ線」および「ＢＥ線」の２つの駅データ条件のそれぞれとの間で，共通駅が検索される。
【００６１】
乗車駅延長路線「ＡＦ線」の乗車駅延長路線駅データ条件（図１９）と降車駅延長路線「ＢＣ線」の延長降車駅路線駅データ条件（図２１（Ａ））との間には共通駅は「駅３」がある（ステップ118でYES）。ステップ119に進む。
【００６２】
２回目のステップ119の処理では，乗車駅始点進行データとして，上述したステップ134で作成された乗車駅始点延長路線進行データ（図１８（Ａ），（Ｂ））が用いられ，かつ降車駅終点進行データとして，上述したステップ141 で作成された降車駅終点延長路線進行データ（図２０（Ａ）〜（Ｄ））が用いられる。２回目のステップ119 の処理では乗車駅始点延長路線進行データ（図１８（Ａ），（Ｂ））の中から乗車駅〜共通駅の経路データの作成が試みられ，かつ降車駅終点延長路線進行データ（図２０（Ａ）〜（Ｄ））の中から共通駅〜降車駅の経路データの作成が試みられ，共通駅で２つの経路データをつなぐ経路候補データの作成が試みられる。
【００６３】
ここで共通駅を「駅３」とする場合，乗車駅延長路線「ＡＦ線」の乗車駅始点延長路線進行データ（図１８（Ａ），（Ｂ））には共通駅「駅３」が含まれているが，降車駅延長路線「ＢＣ線」の降車駅終点延長路線進行データ（図２０（Ａ），（Ｂ））には共通駅「駅３」は含まれていないので，経路候補データは作成されないことになる。
【００６４】
次に，乗車駅延長路線「ＡＦ線」の乗車駅延長路線駅データ条件（図１９）と降車駅延長路線「ＢＥ線」の降車駅延長路線駅データ条件（図２１（Ｂ））との間には，共通駅は「駅３」と「駅21」がある。共通駅を「駅３」とすると，上述と同様に，降車駅延長路線「ＢＥ線」の降車駅終点延長路線進行データ（図２０（Ｃ），（Ｄ））に「駅３」は含まれていないので，経路候補データは作成されない。他方，共通駅を「駅21」とすると，「駅21」は乗車駅延長路線「ＡＦ線」の乗車駅始点延長路線進行データ（上り）（図１８（Ａ））と，降車駅延長路線「ＢＥ線」の降車駅終点延長路線進行データ（下り）（図２０（Ｄ））の両方に含まれているので，「駅21」を含む乗車駅延長路線「ＡＦ線」の乗車駅始点延長路線進行データ（図１８（Ａ））と，「駅21」を含む降車駅延長路線「ＢＥ線」の降車駅終点延長路線進行データ（図２０（Ｄ））とが用いられて，図２２に示すように，「乗車駅（駅２）−駅３−駅４−駅５−駅６−駅25−共通駅（駅21）−駅19−駅20−駅12−降車駅（駅11）」からなる経路候補データ（路線名を含む）が作成されて，経路候補データ群のメモリ領域に格納される（ステップ120）。
【００６５】
ここまでの処理で，Ａ線〜Ｆ線のうち，Ａ線，Ｂ線，Ｃ線，Ｅ線およびＦ線について選択済フラグが「true」となっており，Ｄ線のみが選択済フラグが「false」である。
【００６６】
２回目のステップ121 の処理では，乗車駅延長路線駅データ条件を満たし，かつ降車駅延長路線駅データ条件を満たす，そのような駅データ条件を持つ路線データ，すなわち乗車駅延長路線と降車駅延長路線とをつなぐ中継路線の路線データが，選択済フラグが「false」の路線データの中から検索される。ここで用いられる駅データ条件はステップ135およびステップ142 でそれぞれ得られた駅データ条件であり，具体的にはここでは乗車駅延長路線「ＡＦ線」の駅データ条件（図１９）と，降車駅延長路線「ＢＣ線」および「ＢＥ線」の駅データ条件（図２１（Ａ）および（Ｂ））である。
【００６７】
選択済フラグが「false 」である唯一の路線であるＤ線は，乗車駅延長路線「ＡＦ線」の乗車駅延長路線駅データ条件（図１９）を満たし，かつ降車駅延長路線「ＢＣ線」の降車駅延長路線駅データ条件（図２１（Ａ））を満たす，そのような駅データ条件を持たない。さらにＤ線は，乗車駅延長路線「ＡＦ線」の延長乗車駅延長路線駅データ条件（図１９）を満たし，かつ降車駅延長路線「ＢＥ線」の降車駅延長路線駅データ条件（図２１（Ｂ））を満たす，そのような駅データ条件も持たない。すなわちＤ線は，乗車駅延長路線「ＡＦ線」と降車駅延長路線「ＢＣ線」とをつなぐ中継路線でなく，かつ乗車駅延長路線「ＡＦ線」と降車駅延長路線「ＢＥ線」をつなぐ中継路線でもないので，図１１のステップ128に進む（図１０のステップ122でNO）。
【００６８】
２回目のステップ128では，選択済フラグが「false」の路線データのうち，乗車駅始点延長路線進行データ上の駅を通る別の路線データがあるかどうかが調べられる。ここで選択済フラグが「false 」である路線データはＤ線のみであり，Ｄ線は，乗車駅延長路線「ＡＦ線」の乗車駅始点延長路線進行データ（図１８（Ａ），（Ｂ））上の駅を通らない。「乗車駅からの路線データ有フラグ」が「false」とされる（ステップ129でNO，ステップ131），２回目のステップ134，135はスキップされる。
【００６９】
図１２を参照して，２回目のステップ136では，選択済フラグが「false」の路線データのうち，降車駅終点延長路線進行データ上の駅を通る別の路線データがあるかどうかが調べられる。降車駅延長路線「ＢＣ線」の降車駅終点延長路線進行データ（図２０（Ａ），（Ｂ））には，Ｄ線が通る駅（駅15）がある。降車駅延長路線「ＢＥ線」の降車駅終点延長進行データ（図２０（Ｃ），（Ｄ））にも，Ｄ線が通る駅（駅19）がある。別路線データ有の判断が行われる（ステップ137でYES）。「降車駅からの路線データ有フラグ」が「true」とされ（ステップ139），見つかった別路線，ここではＤ線の選択済フラグが「true」とされる（ステップ140）。
【００７０】
２回目のステップ141 の処理において，降車駅（駅11）を終点とする上記別路線「Ｄ線」が交わる駅（駅15および駅19のそれぞれ）までの進行データと，上記別路線「Ｄ線」が交わる駅（駅15，駅19）を始点とする上記別路線「Ｄ線」の上りおよび下りの進行データとが，上記交わる駅（駅15，駅19）でつなげられ，降車駅（駅11）を終点とする上記別路線「Ｄ線」が交わる駅（駅15，駅19）からの上り進行データと，降車駅（駅11）を終点とする上記別路線「Ｄ線」が交わる駅（駅15，駅19）からの下り進行データが作成される。
【００７１】
図２０（Ｂ）（降車駅延長路線「ＢＣ線」の降車駅終点延長路線進行データ（下り））を参照して，降車駅（駅11）を終点とする，別路線「Ｄ線」が交わる駅「駅15」までの進行データは，「交わる駅（駅15）−駅14−駅10−降車駅（駅11）」である。図２０（Ｄ）（降車駅延長路線「ＢＥ線」の降車駅終点延長路線進行データ（下り））を参照して，降車駅「駅11」を終点とする，別路線「Ｄ線」が交わる駅（駅19）までの進行データは「交わる駅（駅19）−駅20−駅12−降車駅（駅11）」である。図２３（Ａ）〜（Ｄ）を参照して，２回目のステップ141 では，降車駅延長路線「ＢＣ線」にさらに「Ｄ線」を追加した降車駅延長路線「ＢＣＤ線」について「駅17−交わる駅（駅15）−駅14−駅10−駅11（降車駅）」の進行データと「駅19−駅18−交わる駅（駅15）−駅14−駅10−降車駅（駅11）」の進行データが作成され，降車駅延長路線「ＢＥ線」にさらにＤ線を追加した降車駅延長路線「ＢＤＥ線」について「交わる駅（駅19）−駅20−駅12−降車駅（駅11）」の進行データと「駅17−駅15−駅18−交わる駅（駅19）−駅20−駅12−降車駅（駅11）」の進行データとが作成される。
【００７２】
次に２回目のステップ142 の処理に進む。降車駅延長路線駅データ条件，ここでは，１回目のステップ142 で作成された降車駅延長路線「ＢＣ線」の駅データ条件と降車駅延長路線「ＢＥ線」の駅データ条件（図２１（Ａ），（Ｂ））のそれぞれに，上記別路線，ここではＤ線の駅データ条件が加えられる。図２４（Ａ），（Ｂ）に示すように，（駅３or駅７or駅８or駅９or駅10or駅11or駅12or駅13or駅14or駅15or駅16or駅17or駅18or駅19）（降車駅延長路線「ＢＣＤ線」の降車駅延長路線駅データ条件）と，（駅３or駅７or駅８or駅９or駅10or駅11or駅12or駅17or駅18or駅19or駅20or駅21or駅22or駅23）（降車駅延長路線「ＢＤＥ線」の降車駅延長路線駅データ条件）が作成される。
【００７３】
３度目のステップ117以降の処理に進む（図１３のステップ143でNO，図９のステップ116でNO）。１回目のステップ134で作成された乗車駅延長路線「ＡＦ線」の乗車駅延長路線駅データ条件（図１９）と，２回目のステップ141 で作成された降車駅延長路線「ＢＣＤ線」および「ＢＤＥ線」のそれぞれの降車駅延長路線駅データ条件（図２４（Ａ），（Ｂ））とが用いられて，共通駅が検索される。
【００７４】
乗車駅延長路線「ＡＦ線」の乗車駅延長路線駅データ条件（図１９）と降車駅延長路線「ＢＣＤ線」の降車駅延長路線駅データ条件（図２４（Ａ））との間には共通駅「駅３」がある（ステップ118 ）。乗車駅延長路線「ＡＦ線」の乗車駅始点延長路線進行データ（図１８（Ａ），（Ｂ））の中から乗車駅〜共通駅の経路データの作成が試みられ，かつ降車駅延長路線「ＢＣＤ線」の降車駅終点延長路線進行データ（図２３（Ａ），（Ｂ））の中から共通駅〜降車駅の経路データの作成が試みられ，共通駅で２つの経路データをつなぐ経路候補データの作成が試みられる（ステップ119）。
【００７５】
ここで，共通駅を「駅３」とする場合，降車駅延長路線「ＢＣＤ線」の降車駅終点延長路線進行データ（図２３（Ａ），（Ｂ））に「駅３」は含まれていないので，経路候補データは作成されない。
【００７６】
次に乗車駅延長路線「ＡＦ線」の乗車駅延長路線駅データ条件（図１９）と降車駅延長路線「ＢＤＥ線」の降車駅延長路線駅データ条件（図２４（Ｂ））との間には，共通駅は駅３と駅21とがある。「駅３」を共通駅とすると，上述と同様に，降車駅延長路線「ＢＤＥ線」の降車駅終点延長路線進行データ（図２３（Ｃ），（Ｄ））に「駅３」は含まれていないので，経路候補データは作成されない。「駅21」を共通駅とすると，駅21も，降車駅延長路線「ＢＤＥ線」の降車駅終点延長路線進行データ（図２３（Ｃ），（Ｄ））に含まれていない。経路候補データは作成されない。
【００７７】
ここまでの処理で選択済フラグ「false 」を持つ路線データが無くなったので，ステップ131およびステップ138の処理で，「乗車駅からの路線データ有フラグ」および「降車駅からの路線データ有フラグ」がいずれも「false」となる。図１３のステップ143の判断がYESとなり，この場合に未選択路線数が０にセットされる（ステップ144）。
【００７８】
未選択路線数が０である場合（図９のステップ116でYES），経路候補データ群のデータがnullでないことを条件にして，経路候補データ群中の経路候補データのうちの一つが選択され，検索結果画面12（図３参照）に表示される（ステップ108でYES，ステップ109 ，ステップ110）。
【００７９】
結局，乗車駅「駅２」，降車駅「駅11」の場合，「乗車駅（駅２）−駅３−駅８−駅９−駅10−降車駅（駅11）」と，「乗車駅（駅２）−駅３−駅４−駅５−駅６−駅25−駅21−駅19−駅20−駅12−降車駅（駅11）」の２つの経路（経路候補データ）が検索される。２つの経路のうちの一つが検索結果画面12に表示されることになる。もちろん，２つの経路の両方を，たとえば乗換回数の少ない順番で表示してもよい。
【実施例３】
【００８０】
乗車駅「駅２」，降車駅「駅14」の場合
乗車駅が「駅２」，降車駅が「駅14」であった場合，図４を参照して，駅２と駅14は路線が異なっている（乗車駅路線「Ａ線」上に降車駅「駅14」が無い）。ユーザによって入力された「乗車駅」を含む乗車駅路線「Ａ線」および「降車駅」を含む降車駅路線「Ｃ線」の選択済フラグが「false 」から「true」に変更される（ステップ104，111）。乗車駅始点上り／下り進行データおよび降車駅終点上り／下り進行データが作成される（ステップ105，112）。
【００８１】
乗車駅路線「Ａ線」の駅データ条件（駅１or駅２or駅３or駅４or駅５or駅６）と，降車駅路線「Ｃ線」の駅データ条件（駅10or駅13or駅14or駅15or駅16）とが用いられて，共通駅が検索される（ステップ117）。
【００８２】
乗車駅路線「Ａ線」と降車駅路線「Ｃ線」とに共通駅がないので（ステップ118 でNO），乗車駅路線「Ａ線」の駅データ条件と降車駅路線「Ｃ線」の駅データ条件を満たす駅データ条件を持つ中継路線が，選択済フラグが「false 」の路線の中から検索される（ステップ121）。
【００８３】
選択済フラグが「false 」の路線，ここでは，Ｂ線，Ｄ線，Ｅ線およびＦ線のうち，Ｂ線が，乗車駅路線「Ａ線」の駅データ条件（駅３）と，降車駅路線「Ｂ線」の駅データ条件（駅10）とを満たす駅データ条件を持つ。ステップ121 ではＢ線が中継路線として検索によって見つけられる。
【００８４】
ステップ121 で中継路線が見つかった場合（ステップ122でYES），見つかった路線データの選択済フラグ，ここではＢ線についての選択済フラグが「true」とされる（ステップ123）。
【００８５】
次に，乗車駅路線「Ａ線」の駅データ条件と中継路線「Ｂ線」の駅データ条件のアンド検索を行うことで，乗車駅路線「Ａ線」と中継路線「Ｂ線」とに共通する駅（以下，中継始点駅という）が検索される（ステップ124 ）。同様に，降車駅路線「Ｃ線」の駅データ条件と中継路線「Ｂ線」の駅データ条件のアンド検索をすることで，降車駅路線「Ｃ線」と中継路線「Ｂ線」とに共通する駅（以下，中継終点駅という）が検索される（ステップ125 ）。具体的には，「駅３」が中継始点駅として見つけられ，かつ「駅10」が中継終点駅として見つけられる。
【００８６】
乗車駅から中継始点駅までの経路データと，降車駅から中継終点駅までの経路データとが，中継始点駅から中継終点駅までの経路データを挟んで，上記中継始点駅および中継終点駅においてつなげられることで，中継始点駅および中継終点駅を経由する，乗車駅から降車駅に至る一本の経路候補データが作成される（ステップ126 ）。「乗車駅（駅２）−中継始点駅（駅３）−駅８−駅９−中継終点駅（駅10）−降車駅（駅14）」の経路候補データが作成されることになる。重複データが存在しないことを条件に，作成された経路候補データが経路候補データ群のメモリ領域に記憶される（ステップ127）。
【００８７】
さらにステップ128からステップ135を経ることで，実施例２と同様に，乗車駅延長路線「ＡＦ線」の乗車駅始点延長路線進行データ（図１８（Ａ），（Ｂ））が作成され（ステップ134 ），乗車駅延長路線「ＡＦ線」の乗車駅延長路線駅データ条件（図１９）も作成される（ステップ135 ）。ステップ136からステップ142を経ることで，降車駅延長路線「ＣＤ線」の降車駅終点延長路線進行データが作成され（ステップ141 ），かつ降車駅延長路線「ＣＤ線」の降車駅延長路線駅データ条件も作成される（ステップ142 ）。Ｆ線およびＤ線の選択済フラグが「true」になる（ステップ133，ステップ140）。図４を参照して，乗車駅延長路線「ＡＦ線」と降車駅延長路線「ＣＤ線」との共通駅は無いので（２回目のステップ117，ステップ118でNO），２回目のステップ121 において，乗車駅延長路線「ＡＦ線」と降車駅延長路線「ＣＤ線」とをつなぐ中継路線が検索される。Ｅ線が中継路線として見つかる（ステップ122でYES）。
【００８８】
中継路線「Ｅ線」上の駅のうち，乗車駅延長路線「ＡＦ線」の駅条件を満たす駅，すなわち「駅21」が中継始点駅とされる（ステップ124 ）。中継路線「Ｅ線」上の駅のうち，降車駅延長路線「ＣＤ線」の駅条件を満たす駅，すなわち「駅19」が中継終点駅とされる。乗車駅（駅２）からＡＦ線上で中継始点駅（駅21）に至り，Ｅ線上で中継始点駅（駅21）から中継終点駅（駅19）に至り，ＣＤ線上で中継終点駅（駅19）から降車駅（駅14）に至る新たな経路候補データ（「乗車駅（駅２）−駅３−駅４−駅５−駅６−駅25−駅21−駅19−駅18−駅15−降車駅（駅14）」）が経路候補データ群のメモリ領域に記憶される（ステップ127）。
【００８９】
ここまでの処理でＡ線〜Ｆ線のすべての路線の選択済フラグが「true」となるので，検索処理は終了する（ステップ129でNO，ステップ131，ステップ137でNO，ステップ138，ステップ143でYES，ステップ144，ステップ116でYES，ステップ108でYES，ステップ109，ステップ110）。
【００９０】
結局，乗車駅「駅２」，降車駅「駅14」の場合，「乗車駅（駅２）−駅３−駅８−駅９−駅10−降車駅（駅14）」と，「乗車駅（駅２）−駅３−駅４−駅５−駅６−駅25−駅21−駅19−駅18−駅15−降車駅（駅14）」の２つの経路（経路候補データ）が検索される。
【実施例４】
【００９１】
乗車駅「駅２」，降車駅「駅22」の場合
たとえば乗車駅が「駅２」，降車駅が「駅22」である場合，乗車駅路線「Ａ線」と降車駅路線「Ｅ線」が異なり（ステップ106 でNO），乗車駅路線「Ａ線」と降車駅路線「Ｅ線」とに共通駅が無く（ステップ118 でNO），さらに中継路線も最初の検索では見つからない（ステップ122でNO）。
【００９２】
ステップ128において，選択済フラグが「false」であるＢ線，Ｃ線，Ｄ線およびＦ線の中から，乗車駅路線「Ａ線」に交わる路線，すなわちＢ線およびＦ線が検索される。Ｂ線およびＦ線の選択済フラグが「true」になる（ステップ133 ）。乗車駅延長路線「ＡＢ線」および「ＡＦ線」のそれぞれについて，乗車駅始点延長路線進行データが作成される（ステップ134 ）。乗車駅延長路線「ＡＢ線」および「ＡＦ線」のそれぞれについて乗車駅延長路線駅データ条件も作成される（ステップ135）。
【００９３】
同様に，降車駅路線「Ｅ線」に交わる路線が，選択済フラグが「false 」の路線の中から検索される（ステップ136）。ここまでの処理で選択済フラグが「false」の路線は，Ｃ線およびＤ線である。降車駅路線「Ｅ線」に交わる路線はＢ線，Ｄ線およびＦ線である。このうち選択済フラグが「false」であるＤ線のみが，ステップ136で検索される。Ｄ線の選択済フラグが「true」になる（ステップ140 ）。また降車駅延長路線「ＤＥ線」についての降車駅終点延長路線進行データが作成される（ステップ141 ）。さらに降車駅延長路線「ＤＥ線」について降車駅延長路線駅データ条件も作成される（ステップ142）。
【００９４】
２回目の共通駅検索が行われる（ステップ116でNO，ステップ117）。
【００９５】
乗車駅延長路線「ＡＢ線」と降車駅延長路線「ＤＥ線」との間では「駅12」が共通駅として見つかる（ステップ118でYES）。乗車駅（駅２）−駅３−駅８−駅９−駅10−駅11−共通駅（駅12）（ＡＢ線）と，共通駅（駅12）−駅20−駅19−駅21−降車駅（駅22）（ＤＥ線）とが，共通駅（駅12）でつなげられ，「乗車駅（駅２）−駅３−駅８−駅９−駅10−駅11−共通駅（駅12）−駅20−駅19−駅21−降車駅（駅22）」からなる経路候補データが作成されて経路候補データ群のメモリ領域に格納される（ステップ119，120）。
【００９６】
乗車駅延長路線「ＡＦ線」と降車駅延長路線「ＤＥ線」との間では，「駅21」が共通駅として見つかる（ステップ118でYES）。「乗車駅（駅２）−駅３−駅４−駅５−駅６−駅25−駅21−降車駅（駅22）」からなる経路候補データが作成されて経路候補データ群のメモリ領域に格納される（ステップ119，120）。
【００９７】
ここまでの処理で，Ａ線，Ｂ線，Ｄ線，Ｅ線およびＦ線の選択済フラグが「true」とされ，Ｃ線のみ選択フラグが「false 」となっている。Ｃ線について，Ｃ線が，乗車駅延長路線「ＡＢ線」と降車駅延長路線「ＤＥ線」とをつなぐ中継路線であるかどうかが判断され，かつ乗車駅延長路線「ＡＦ線」と降車駅延長路線「ＤＥ線」とをつなぐ中継路線であるかが判断される（ステップ121）。
【００９８】
Ｃ線は，乗車駅延長路線「ＡＢ線」につながる「駅10」と，降車駅延長路線「ＤＥ線」につながる「駅15」を有しており，このため，Ｃ線は，乗車駅延長路線「ＡＢ線」と降車駅延長路線「ＤＥ線」とをつなぐ中継路線と判断される（ステップ122でYES）。これに対し，Ｃ線は乗車駅延長路線「ＡＦ線」上の駅と降車駅延長路線「ＤＥ線」上の駅とをつなぐ駅を持たないので，乗車駅延長路線「ＡＦ線」と降車駅延長路線「ＤＥ線」とをつなぐ中継路線ではない（ステップ122でNO）。
【００９９】
Ｃ線が，乗車駅延長路線「ＡＢ線」と降車駅延長路線「ＤＥ線」とをつなぐ中継路線と判断されることで，Ｃ線の選択済フラグが「true」にされ（ステップ123 ），駅10が中継始点駅，駅15が中継終点駅としてそれぞれ決定される（ステップ124，125）。「乗車駅（駅２）−駅３−駅８−駅９−中継始点駅（駅10）−駅14−中継終点駅（駅15）−駅18−駅19−駅21−降車駅（駅22）」からなる経路候補データが検索され，経路候補データ群のメモリ領域に格納される（ステップ126，127）。この時点ですべての路線の選択済フラグが「true」となったので，処理が終了する。
【０１００】
結局，乗車駅「駅２」，降車駅「駅22」の場合，「乗車駅（駅２）−駅３−駅８−駅９−駅10−駅11−駅12−駅20−駅19−駅21−降車駅（駅22）」と，「乗車駅（駅２）−駅３−駅４−駅５−駅６−駅25−駅21−降車駅（駅22）」と，「乗車駅（駅２）−駅３−駅８−駅９−駅10−駅14−駅15−駅18−駅19−駅21−降車駅（駅22）」の３つの経路が得られることになる。
【０１０１】
図４に示す路線図では経路候補データ群がnullになる場合はない（ステップ108 でNOの場合はない）。経路候補データ群がnullとなった場合には，検索結果画面12には経路が見つからなかった旨が表示されて，処理が終了する。
【０１０２】
上述した実施例１〜４では鉄道の路線図を具体例としている。もちろん，経路検索装置１は，鉄道路線に限らず，他の交通機関，たとえばバス路線にも適用することができるし，鉄道路線とバス路線の組合せなどにも適用することができる。また，上述の実施例１〜４では駅の名称（または駅ＩＤ）を用いて共通駅を判断しているが，互いに異なる名称を持つ２つの駅であっても，距離が近く，乗換可能な２つの駅（たとえばＪＲ大阪駅と御堂筋線梅田駅など）であれば，これらに同一の駅ＩＤを持たせることで共通駅として取り扱ってもよい。
【０１０３】
上述した経路検索装置１による経路検索処理は，空集合から始めて最短路となるノードを一つずつ求めて最短路部分集合を得（最短路となるノードを求めるためにノードとノードの間（リンク）のコスト（時間，料金など）は既知である），これを順次を膨らませていくことで最終的に全部のノードに対して最短路を求め，基本的に出発点から目的点に向かって最短路を得る方法であるダイクストラ法と異なり，全部のノード（駅）について最短路を求める処理を行わず，また出発点（乗車駅）から目的点（降車駅）に到達する経路を出発点側からと目的点側からの両がわから求めている。ノード（駅）とノード（駅）の間（リンク）のコスト（時間，料金など）は既知である必要は必ずしもない。このためダイクストラ法と比べると計算回数が圧倒的に少ない。処理負担が軽く，したがって短時間のうちに経路検索処理を終了することができる。
【０１０４】
さらに，上述した経路検索装置１による経路検索処理では，乗車駅路線と降車駅路線との共通駅を検索し（ステップ117 ），乗車駅路線と降車駅路線をつなぐ中継路線を検索し（ステップ121 ），さらに乗車駅路線と乗車駅路線につながる別路線（乗車駅路線および中継路線以外の路線）との組合せ（乗車駅延長路線）（乗車駅始点延長路線進行データ）と，降車駅路線と降車駅路線につながる別路線との組合せ（降車駅延長路線）（降車駅終点延長路線進行データ）を用いて，上記共通駅検索（ステップ117 ）および中継路線検索（ステップ121 ）を再実行する。乗換回数が少ない経路を確実に見つけてユーザに提示することができる。
【０１０５】
上述した経路検索装置１によって複数の経路が見つかった場合，乗換回数が少ない順番で提示（出力）するのみならず，たとえば乗車駅から降車駅に至るまでの所要時間が短い順番で複数の経路を並べて提示してもよい。駅データ（図６）には駅間の移動に要する所要時間が格納されているので，この所要時間に基づいて，乗車駅から降車駅に到着するまでに要する所要時間を経路ごとに算出することができ，その所要時間が短い順番で，見つかった複数の経路を並び替えて提示することができる。また，駅データに時刻表データ，運賃データ，距離データ等をさらに含ませておくことで，降車駅により早い時刻に到達することができる順番，料金が安い順番，距離が短い順番などにより，見つかった複数の経路を並び替えて提示することもできる。
【０１０６】
なお，乗車駅と降車駅とがそれぞれ遠隔地である場合には，たとえば航空経路を介在させてもよい。この場合には，乗車駅から乗車駅に近い空港最寄り駅までの経路と，降車駅から降車駅に近い空港最寄り駅までの経路が，上述した経路検索装置１によって検索され，それらが航空経路によって結ばれる。
【符号の説明】
【０１０７】
１  経路検索装置
２  ＣＰＵ（第１の経路データ検索手段，第１の経路データ作成手段，第２の経路データ検索手段，第２の経路データ作成手段，第１の延長路線作成手段，第２の延長路線作成手段）
３  メモリ
４  記憶装置（路線データ記憶手段）
５  入力装置
６  表示装置
【図１】
2014145690.tif 000003
【図２】
2014145690.tif 000004
【図３】
2014145690.tif 000005
【図４】
2014145690.tif 000006
【図５】
2014145690.tif 000007
【図６】
2014145690.tif 000008
【図７】
2014145690.tif 000009
【図８】
2014145690.tif 000010
【図９】
2014145690.tif 000011
【図１０】
2014145690.tif 000012
【図１１】
2014145690.tif 000013
【図１２】
2014145690.tif 000014
【図１３】
2014145690.tif 000015
【図１４】
2014145690.tif 000016
【図１５】
2014145690.tif 000017
【図１６】
2014145690.tif 000018
【図１７】
2014145690.tif 000019
【図１８】
2014145690.tif 000020
【図１９】
2014145690.tif 000021
【図２０】
2014145690.tif 000022
【図２１】
2014145690.tif 000023
【図２２】
2014145690.tif 000024
【図２３】
2014145690.tif 000025
【図２４】
2014145690.tif 000026