JP5213403B2 - 料金計算ネットワーク生成装置及びこの料金計算ネットワークを用いた料金計算装置 - Google Patents

Description

本発明は、始点から終点までの最安料金を計算する料金計算ネットワークの生成装置及びこの料金計算ネットワークを用いた料金計算装置に関し、特に、料金体系の異なる複数の系に跨った２点間の最安料金計算に好適な料金計算ネットワークの生成装置及びこの料金計算ネットワークを用いた料金計算装置に関する。

始点から終点までの料金を計算する一例として、例えば、鉄道等の運賃計算がある。鉄道等の運賃計算は、出発駅と到着駅の情報が与えられた時に、駅間の接続関係を示す路線データと駅間距離データから出発駅と到着駅間の距離を算出した後、距離−運賃換算表データから、算出した距離を運賃に変換して出発駅と到着駅間の運賃を算出する（例えば、特許文献１及び特許文献２）。

ところで、鉄道等の運賃計算の場合、与えられた２駅間の運賃計算は、その２駅間の利用可能経路の中で最安運賃の経路を利用するものと仮定して計算しなければならない。このような最安運賃計算方法として、従来、図２９に示すような物理ネットワークを用いて最安運賃を計算する方法がある。図２９の物理ネットワークは、駅をノード、線路をアークとし、ノードの接続のコストを距離としたネットワークで、この物理ネットワークにおいて、最短経路探索アルゴリズムを用いて最短距離経路を探索し、探索した経路の合計距離を距離−運賃換算表データを用いて運賃に換算して最安運賃を求める。
特開平５−２５８１３７号公報 特開２０００−１１２１１号公報

しかしながら、例えば、出発駅と到着駅が、異なる料金体系（同一距離でも異なる料金が設定されている）の複数の会社を跨いでいるような場合、会社間の乗継に適用される割引制度等により、最短距離経路が最安運賃になる保証がない。このため、図２９の物理ネットワークを用いて最安運賃を計算する場合は、２駅間の利用可能な経路を全て求め、全経路の距離を計算した後、計算した距離を運賃に換算し、その中から最安運賃を選択するような計算処理を行う。従って、首都圏のような大規模な鉄道ネットワークでは、探索経路数が膨大となり、しかも、全ての探索経路について、距離計算及び距離から運賃への換算を行う必要があるので、計算量が膨大で最安運賃計算処理に時間がかかるという問題がある。

本発明は上記問題点に着目してなされたもので、最安料金計算処理における探索経路数を削減できると共に、計算処理量が少なく計算処理時間を短縮できる料金計算ネットワークを提供することを目的とする。また、この料金計算ネットワークを用いた料金計算装置を提供する。

このため、請求項１に記載の本発明の料金計算ネットワーク生成装置は、異なる料金体系の複数の系の各系毎の料金を定めた料金データと各系間の接続関係を示す接続関係データとを格納するデータ格納部と、前記複数の系の各系内の各点をノードとし、各ノードを必要に応じてアークで直接接続し、前記アークで接続したノード間の接続のコストを前記料金データに基づいた料金としたネットワークデータを生成し、前記各系毎のネットワークデータをそれぞれサブネットワークデータとし、前記接続関係データに基づいて異なるサブネットワークデータのノード間を接続する接続アークデータを生成し、前記サブネットワークデータと接続アークデータを料金計算ネットワークデータとするネットワークデータ生成部とを備えて構成したことを特徴とする。

請求項２のように、前記ネットワークデータ生成部は、前記複数の系の各系内の全てのノードをアークで互いに直接接続し、前記アークで接続したノード間の接続のコストを前記料金データに基づいた料金としたネットワークデータを、前記料金計算ネットワークデータとして生成する構成とした。
かかる構成では、アークで接続されるノード間の接続のコストを料金としたので、最短経路探索アルゴリズムを適用して直接最安の料金を算出できるようになり、計算量を軽減できる。

請求項３では、前記ネットワークデータ生成部は、前記アークで接続される前記ノード間の接続のコストを料金零とした前記料金計算ネットワークデータを生成する構成とした。

かかる構成では、料金体系の異なる系に跨る２点間の最安料金を、最短経路探索アルゴリズムを適用して算出することができるようになる。

請求項４の発明では、前記ネットワークデータ生成部は、前記料金計算ネットワークデータにおける各サブネットワークをそれぞれ１つの上位のノードと見なし、前記接続関係データに基づいて前記上位ノード間を１つの上位のアークで接続し、この上位アークで接続される前記上位ノード間の接続のコストを１とした上位ネットワークデータを生成してネットワークデータの階層化を行い、異なる料金体系の複数の系に跨る始点と終点の情報が入力されたときに、予め定めた料金計算上の禁止条件に基づいて、前記上位ネットワークの始点を含む上位ノードから終点を含む上位ノードまでの上位アークのコスト値が所定コスト値以下で且つ始点から終点への経路において上位ノードが重複しないような接続関係を有する連絡パターンを前記上位ネットワークデータから選択し、前記選択された連絡パターンデータにおける各上位ノードに対応するそれぞれのサブネットワークとこれらサブネットワーク間を接続する接続アークの各データから前記禁止条件を満たす下位ネットワークデータを生成し、この下位ネットワークデータを料金計算ネットワークデータとするようにした。

請求項５では、前記各サブネットワークデータを、前記接続アークで接続されるノードデータとこれらノード間を接続するアークデータのみで構成し、これらサブネットワークデータと前記接続アークデータからなる簡易ネットワークデータを生成し、異なる料金体系の複数の系を跨いだ始点と終点の情報が入力されたときに、前記簡易ネットワークデータに始点と終点の各ノードデータ及び始点と終点のそれぞれに接続する各アークデータを追加して、簡易料金計算ネットワークデータを生成する構成とした。

請求項６のように、前記各サブネットワークデータを、前記接続アークで接続されるノードデータとこれらノード間を接続するアークデータのみで構成し、これらサブネットワークデータと前記接続アークデータからなる簡易ネットワークデータを生成し、前記簡易ネットワークデータに異なる料金体系の複数の系を跨いだ始点と終点の各ノードデータ及び始点と終点のそれぞれに接続する各アークデータを追加した簡易料金計算ネットワークデータを、前記始点と終点の全ての組合せ分予め生成しておき、前記始点と終点の情報が入力されたときに、当該入力情報に対応した簡易料金計算ネットワークデータを選択する構成としてもよい。
かかる構成では、終点までたどり着けない分岐を削除するため、不要な分岐の探索をしなくなる。

請求項７の発明では、前記料金計算ネットワークデータは、各サブネットワークの各ノード毎にダミーノードを追加したノードデータと、各サブネットワーク内のノード間を接続する前記アークの接続元又は接続先のどちらか一方端をダミーノードとしたアークデータとで構成したサブネットワークデータを有すると共に、前記アークの接続元をダミーノードとしたとき、異なるサブネットワークのノード間を接続する前記接続アークの接続先をダミーノードとする接続アークデータを有し、前記アークの接続先をダミーノードとしたとき、異なるサブネットワークのノード間を接続する前記接続アークの接続元をダミーノードとする接続アークデータを有する構成とした。
かかる構成では、接続関係のない系間を跨いだ２点間の料金計算の防止、途中下車経路の防止ができるようになる。

請求項８の発明では、前記料金計算ネットワークデータは、異なる各サブネットワーク間の料金割引のある所定の２点間を直接接続する割引経路を示す割引アークデータを有し、予め定めた前記所定の２点間の料金割引データに基づいて、前記割引アークで接続されるノード間の接続のコストを割引後の料金とする構成とした。
かかる構成では、料金体系の異なる系間の料金割引のある２点間の料金計算を容易に行えるようになる。

請求項９に記載の本発明の料金計算装置は、始点と終点の情報を入力する入力部と、請求項１〜８のいずれか１つに記載の料金計算ネットワーク生成装置で生成した料金計算ネットワークデータを格納するネットワークデータ格納部と、始点と終点の情報が入力されたときに、前記ネットワークデータ格納部の料金計算ネットワークデータに基づいて料金計算ネットワークを構築し、前記料金計算ネットワークの前記始点から終点までの最安料金を算出する最安料金算出部と、算出した前記最安料金結果を出力する出力部とを備えて構成したことを特徴とする。

かかる構成では、入力部から始点と終点の情報が入力されると、最安料金算出部が、ネットワークデータ格納部に格納された料金計算ネットワークデータに基づいて料金計算ネットワークを構築し、料金計算ネットワークの始点から終点までの最安料金を算出し、出力部から算出した最安料金結果を出力するようにする。

請求項１０のように、前記料金計算ネットワークデータが、請求項１〜７のいずれか１つに記載の料金計算ネットワーク生成装置で生成されたデータであるとき、前記最安料金算出部は、前記料金計算ネットワークにおける前記始点から終点までのアークのコストが最小となる経路を探索する最小コスト探索部と、料金割引を適用する経路とその割引額を示す料金割引データに基づいて、前記始点から終点までの経路に適用される割引額の最大値を算出する最大割引額算出部と、前記最小コスト探索部で探索された最小コストの料金に前記最大割引額算出部で算出した最大割引額を加算して探索閾値を設定する探索閾値設定部と、前記料金計算ネットワークに基づいて、アークのコストが前記探索閾値以下となる全ての経路を探索し、各経路の料金を算出する第１の料金算出部と、前記料金割引データに基づいて、探索された経路に割引が適用される経路があるときに、前記第１の料金算出部で算出したその経路の割引適用前料金からその経路に適用される割引額を減算して割引適用後の料金を算出する第２の料金算出部と、前記第１の料金算出部で算出した料金及び前記第２の料金算出部で算出した料金の中で最安の料金を選択する最安料金選択部と、を備える構成である。

また、請求項１１のように、前記料金計算ネットワークデータが、請求項８に記載の料金計算ネットワーク生成装置で生成されたデータであるとき、前記最安料金算出部は、前記料金計算ネットワークにおける前記始点から終点までのアークのコストが最小となる経路を探索する最小コスト探索部を備え、この最小コスト探索部で探索された経路のコストを最安料金とする構成である。

請求項１２のように、前記料金を、鉄道運賃とすれば、複雑な鉄道ネットワークの運賃を効率よく短時間で計算できるようになる。

本発明によれば、料金体系の異なる複数の系間を跨いだ２点間の料金計算を、最短経路探索アルゴリズムを適用して少ない計算処理量で効率良く短時間で算出することができる料金計算ネットワークを提供することが可能となり、この料金計算ネットワークを使用することにより、例えば、複雑な鉄道運賃等の料金を容易に短時間で計算することが可能になる。

以下、本発明の実施形態を図面に基づいて説明する。尚、以下の各実施形態では、鉄道の運賃計算に適用した場合を例に説明する。
図１は、本発明に係る料金計算装置の第１実施形態の構成を示すブロック図である。
図１において、本実施形態の料金計算装置１は、一鉄道会社の料金体系の系に属する始点になる出発駅（以下、発駅とする）と終点になる到着駅（以下、着駅とする）間は勿論、料金体系の異なる複数の系に跨った発駅と着駅間の最安運賃を計算するものである。また、料金計算装置１は、後述するように料金計算用のネットワークデータ生成機能を備えており、料金計算ネットワーク生成装置を兼ねる。ここで、料金体系とは各鉄道会社毎に設定されている運賃計算の規則であり、各鉄道会社はそれぞれの料金体系を持っているものとする。尚、本発明では、仮に、各鉄道会社が同一の料金体系を持っていたとしても、会社が異なるためそれぞれ別の料金体系として扱うものであり、また、同一の鉄道会社が２以上の料金体系を持っている場合にもそれぞれ別の料金体系として扱うものである。

前記料金計算装置１は、入力部２と、データストレージ装置３と、ネットワークデータ生成部４と、最小コスト探索部５と、探索閾値設定部６と、最安運賃算出部７と、出力部８と、記憶装置９とを備えて構成される。ここで、料金計算装置１は、例えばコンピュータで構成され、前記ネットワークデータ生成部４、最小コスト探索部５、探索閾値設定部６及び最安運賃算出部７の機能はソフトウエア的に備えられるものである。

前記入力部２は、始点となる発駅と終点となる着駅の各データ等を入力するものである。
前記データストレージ装置３は、各社別運賃三角表データ、各社間の乗継関係データ及び乗継割引表データ等を予め格納しておくもので、データ格納部に相当する。前記運賃三角表データは、図２に示すように同一会社内の２駅間の運賃を定めたもので料金データに相当する。前記乗継関係データは、会社毎の別会社への乗継可能な駅データとその接続関係を定めたものである。前記乗継割引表データは、図３に示すような料金体系の異なる複数の会社間の乗継割引を適用する経路とその割引額を定めたデータであり、料金割引データに相当する。

前記ネットワークデータ生成部４は、データストレージ装置３内に格納されたデータに基づいて図５に示すような料金ネットワークを構築するネットワークデータを生成するもので、サブネットワークデータ生成部４Ａと接続アークデータ生成部４Ｂを備える。前記サブネットワーク生成部４Ａは、同一体系内の各駅をノードとし、全てのノードをアークで互いに直接接続し、アークで接続したノード間の接続の重み付けを図３の運賃三角表データに基づいた料金とする図５に示すサブネットワークＮ１〜Ｎ３構築用のサブネットワークデータを、料金体系毎に生成する。尚、ノードまたはアークのどちらかに重み付けされていれば、アークで接続したノード間の接続の重み付け（以下、コストとする）がなされているものとする。前記接続アークデータ生成部４Ｂは、前記乗継関係データに基づいて料金体系の異なる会社間の連絡駅に対応するノード間を接続する図５の点線で示す接続アークを生成し、接続アークで接続されるノード間の接続のコストを料金零に設定する。尚、同一料金体系内のノード間を接続するアークデータ及び異なる料金体系間を接続する接続アークデータは、一方のノードから他方のノードへ、他方のノードから一方のノードへ、それぞれ向かう２本のアークデータからなっているが、図５では図を簡略にするために１本線で示してある。

前記最小コスト探索部５は、前記サブネットワークデータと接続アークデータから構築される料金ネットワークを用い、例えばダイクストラ法等の最短経路探索アルゴリズムによって、入力部２から入力された発駅と着駅間でコストが最小となる経路を探索する。この最小コスト探索部５で探索する経路の運賃は、後述する乗継割引を考慮したものでなく、乗継割引適用前の運賃である。

前記探索閾値設定部６は、入力された発駅と着駅間に乗継割引が適用される経路が存在する可能性がある場合に、図３の乗継割引表データに基づいて後述する図６のフローチャートで説明するように、発駅−着駅間の経路に適用される割引額の最大値を算出し、この最大割引額と最小コスト探索部５で探索した最小コストの経路の運賃を合算して、発駅と着駅間の最安運賃の算出に必要な探索閾値を設定する。ここで、探索閾値設定部６は、最大割引額算出部の機能を備えるものである。

前記最安運賃算出部７は、後述する図６のフローチャートで説明するように、料金ネットワークを利用して探索閾値設定部６で設定した探索閾値以下の運賃となる全ての経路を探索し、探索経路の中に乗継割引適用経路があればその経路の割引後の運賃を求めた後、全ての探索経路中の最も安い運賃を選択し、その運賃を最安運賃として算出するもので、最安料金算出部に相当する。ここで、最安運賃算出部７は、第１の料金算出部、第２の料金算出部及び最安料金選択部の機能を備えるものである。

前記出力部８は、最安運賃算出部７で算出された結果を最安運賃データとして出力する。
前記記憶装置９は、ネットワークデータ生成部４で生成された料金ネットワークデータを料金計算ネットワークデータとして格納すると共に、最安運賃算出処理過程において必要とされる各種データを一時的に格納しておくもので、ネットワークデータ格納部に相当する。

次に、料金計算装置１による料金ネットワークデータの生成及び最安運賃算出の各動作について説明する。
図４は、料金ネットワークデータの生成のフローチャートである。
ステップ１（図中Ｓ１で示し、以下同様とする）で、ネットワークデータ生成部４はデータストレージ装置３から各社別運賃三角表データ、乗継関係データを読込む。
ステップ２で、サブネットワークデータ生成部４Ａにより、各社の運賃三角表データから異なる料金体系毎のサブネットワークデータを生成する。
ステップ３で、接続アークデータ生成部４Ｂにより、乗継関係データから異なる料金体系のサブネットワーク間を接続する接続アークデータを生成する。
ステップ４で、生成した異なる料金体系毎のサブネットワークデータ及び接続アークデータからなる料金ネットワークデータを、料金計算ネットワークデータとして記憶装置９に格納する。

かかる料金ネットワークデータを用いて、図５に示すような、同一体系内の各駅をノード（図中のａ〜ｆ、ｇ〜ｌ、ｍ〜ｒ）とし、全てのノードをアーク（図中の実線）で互いに直接接続しノード間の接続のコストを料金とした異なる料金体系１〜３毎のサブネットワークＮ１〜Ｎ３と、サブネットワークＮ１〜Ｎ３のノード間（図５では、ｄとｇ、ｄとｍ、ｋとｏ）を接続する接続アーク（図中の点線）からなる料金ネットワークを構築する。

図６は、生成した料金ネットワークによる最安運賃算出を示すフローチャートである。ここでは、発駅と着駅が料金体系の異なる会社に跨る場合について説明する。この場合、入力された発駅と着駅間に乗継割引が適用される経路が存在すれば、最小コスト探索部５で探索される最安運賃が最安になるとは限らない。
ステップ１１で、入力部２から発着駅データが入力されるまで待機し、入力されるとステップ１２に進む。
ステップ１２で、最小コスト探索部５が、記憶装置９から料金ネットワークデータを読込み、図５の料金ネットワークにおいて最短経路探索アルゴリズムを用いて発駅−着駅間の乗継割引適用前の最安運賃を求め、例えば記憶装置９に格納しておく。
ステップ１３で、探索閾値設定部６が、データストレージ装置３から乗継割引表データを読込み、発駅−着駅間での最大割引額を求め、例えば記憶装置９に格納しておく。

最大割引額の算出手法について図７を参照して説明する。尚、図７では、異なる料金体系の系が４つで、且つ、３料金体系間割引まで設定されている場合で説明する。
図７において、ノードｃからノードｕへ向かう経路を例として説明する。ここで求める最大割引額は料金体系間の最大割引額である。例えば、ｃからｕへ向かう全ての経路で可能性のある料金体系間割引の組合せは以下の（ａ）〜（ｅ）ようになる。
（ａ）２料金体系間割引１回（料金体系１，２間、料金体系２，３間、料金体系３，４間のいずれか１つ）
（ｂ）２料金体系間割引２回（前記３つの料金体系間の中の２つを組合せ）
（ｃ）２料金体系間割引３回（前記３つの料金体系間の全て）
（ｄ）３料金体系間割引１回（料金体系１〜３間又は料金体系２〜４間のいずれか１つ）
（ｅ）３料金体系間割引１回＋２料金体系間割引１回（料金体系１〜３間と料金体系３,４間、又は、料金体系１，２間と料金体系２〜４間のいずれか１つ）

各料金体系間の最大割引額は、データストレージ装置３に格納された乗継関係データの料金体系間の最大割引額から求めることができる。
例えば、２料金体系間最大割引額が２０円、３料金体系間最大割引額が３０円であれば、（ａ）は２０円、（ｂ）は４０円、（ｃ）は６０円、（ｄ）３０円、（ｅ）は５０円となり、最大割引額は６０円と定めることができる。図７の料金計算ネットワークにおいて、例えば実線で示すような経路（ｃ→ｄ→ｇ→ｉ→ｋ→ｏ→ｒ→ｍ→ｖ→ｕ）が考えられる。尚、この経路に限らない。
この最大割引額の算出は、下記の数１の（１）式から算出できる。

ここで、ｄ_iはｉ料金体系間最大割引額、ｘ_iはｉ料金体系間割引回数、Ｎは利用する料金体系の最大数を表す。また、ｉ料金体系間の割引適用回数の制約条件を数１の（２）式のように定める。
尚、料金ネットワークにおける最大割引額は、各料金体系間の最大割引額の変更や割引が適用される料金体系の最大数が変わらなければ変わらないので、予め求めてデータとして格納しておくとよい。
図７の説明では、料金体系の系が４つで、且つ、３料金体系間割引まで設定されている場合であったが、本発明ではこれに限らず系の数がいくつでもよく、また、料金体系間割引も２料金体系間割引、３料金体系間割引に限られることはない。

ステップ１４で、ステップ１２，１３でそれぞれ求めた最安運賃と最大割引額とから、探索閾値＝適用前最安運賃＋最大割引額として設定する。即ち、最大割引額を適用した場合に適用前最安運賃以下となる運賃の上限値として探索閾値を設定し、この探索閾値以下の乗継割引適用前の運賃経路だけを探索するようにしている。これにより、最安運賃を求める際に、探索閾値を超える運賃経路を探索する必要がなくなり、探索経路数を大幅に削減できる。この探索閾値を、例えば記憶装置９に格納しておく。
ステップ１５で、料金ネットワークにより探索閾値以下となる割引適用前運賃の全ての経路及び探索された全ての経路で割引が適用される経路の探索を行う。
ステップ１６で、乗継割引表データに基づいてステップ１５で探索した各割引適用経路の乗継割引額を算出し、例えば記憶装置９に格納しておく。
ステップ１７で、ステップ１５で求めた各割引適用経路の乗継割引適用前運賃からステップ１６で求めた乗継割引額を減算し、割引適用経路の乗継割引後の運賃を算出する。
ステップ１８で、全ての乗継割引適用経路について割引後の運賃算出が終了したか否かを判定し、判定がＹＥＳであれば、ステップ１９に進む。
ステップ１９で、ステップ１２で求めた最安運賃とステップ１７で算出した全ての割引適用経路の各運賃の中で最も安いものを最安運賃として出力部８を介して出力する。

かかる第１実施形態の料金ネットワークを用いれば、ノード間を直接アークで接続し、ノード間の計算のコストを料金としたので、従来の物理的ネットワークを用いる場合に比べて、距離から運賃への変換処理を行わずに済む。また、異なる料金体系間を発駅と着駅が跨る場合でも、各料金体系で算出した運賃の足し算で運賃を求めることができ、最短経路探索問題としてダイクストラ法等の最短経路探索アルゴリズムを用いて計算できる。従って、特に発駅と着駅が異なる料金体系間を跨る場合に、探索経路数及び計算量を大幅に削減でき、最安運賃を極めて短時間で算出できるようになる。

次に、本発明の第２実施形態について説明する。
本実施形態は、異なる料金体系を跨いだ発駅−着駅間の最安運賃計算を第１実施形態よりも更に高速に行うことを可能としたネットワークである。
図８は、本発明に係る料金計算装置の第２実施形態の構成を示すブロック図である。尚、第１実施形態と同一要素には同一符号を付して説明を省略する。
図８において、本実施形態の料金計算装置１０は、第１実施形態の料金計算装置１に、簡易ネットワークデータ生成部１１を付加して構成される。
前記簡易ネットワークデータ生成部１１は、ネットワークデータ生成部４で生成された料金ネットワークデータのサブネットワークデータから、前記接続アークで接続されるノード以外のノードを取除き、接続アークで接続されるノードデータとこれらノード間を接続するアークデータのみで構成されるサブネットワークデータと、これらサブネットワークデータと接続アークデータからなる簡易なネットワークデータ（簡易ネットワークデータ）を生成して記憶装置９に格納する。
尚、ネットワークデータ生成部４で生成された料金ネットワークデータのサブネットワークデータから、前記接続アークで接続されるノード以外のノードを取除く代わりに、前記簡易ネットワークデータ生成部１１において、最初から図１０に示すような接続アークで接続されるノードデータ及びノード間を接続するアークからなるサブネットワークデータと接続アークデータからなるネットワークデータ（簡易ネットワークデータ）を生成して記憶装置９に格納してもよい。

次に、料金計算装置１０による簡易ネットワークデータの生成及び最安運賃算出の各動作について説明する。
図９は、簡易ネットワークデータの生成のフローチャートである。
ステップ２１で、ネットワークデータ生成部４により第１実施例と同様のサブネットワークデータと接続アークデータからなる第１実施形態で説明した料金ネットワークデータを生成し、記憶装置９に格納する。この料金ネットワークデータの生成手順は、第１実施形態の図４のフローチャートのようにして生成する。
ステップ２２で、簡易ネットワークデータ生成部１１が記憶装置９から料金ネットワークデータを読込む。
ステップ２３で、簡易ネットワークデータ生成部１１は、読込んだデータに基づいて、接続アークで接続されるノード及びこれらノード間を接続するアークのみのサブネットワークデータと、サブネットワーク間のノードを接続する接続アークで構成される簡易ネットワークデータを生成する（第１の方法）。
ステップ２４で、ステップ２３で生成した簡易ネットワークデータを記憶装置９に格納する。
尚、ステップ２３で生成した簡易ネットワークデータにおいて、料金体系の異なるサブネットワーク間を跨いだ発駅と着駅の全ての組合せに対応した各ネットワークデータを予め生成しておき、ステップ２４で、実際に料金計算を行うための後述する実行簡易ネットワークデータとして各ネットワークデータを記憶装置９に格納しておいてもよい（第２の方法）。

図１０は、図５の料金ネットワークデータに基づいて生成した簡易ネットワークデータによる簡易ネットワークの例を示す。

図１１は、簡易ネットワークを利用して最安運賃算出を示すフローチャートである。
ステップ３１で、入力部２から発着駅データが入力されるまで待機し、入力されるとステップ３２に進む。
ステップ３２で、簡易ネットワークを用いて実際に運賃計算を行うための簡易料金計算ネットワークデータとして実行簡易ネットワークデータを生成する。具体的には、簡易ネットワークデータ生成部１１において、接続アークで接続されるノードとこれらノード間を接続するアークのみで構成したサブネットワークデータと、サブネットワーク間のノードを接続する接続アークとで構成される簡易ネットワークデータが格納されている場合（前記第１の方法）、入力された発駅及び着駅データ（例えば後述する発駅のノードａ、着駅のノードｒのデータ）と前記発駅と着駅のそれぞれに接続する各アークデータである料金アークデータ（例えば後述するノードａ−ｄ間、ノードｍ−ｒ間、ノードｏ−ｒ間のデータ）を追加し、これを料金計算用の実行簡易ネットワークデータ（図９には図示せず）として生成して記憶装置９に一時格納する。
また、記憶装置９内に予め発駅と着駅の全ての組合せに対する実行簡易ネットワークデータが格納されている場合（第２の方法）、入力された発駅及び着駅データ（例えば後述する発駅のノードa、着駅のノードｒのデータ）に対応する実行簡易ネットワークデータ（図９には図示せず）を選択して記憶装置９の別の場所に一時格納する。

その後、ステップ３３〜４０で、ステップ３２で生成した実行簡易ネットワークデータにより構築した図１２に示すような実行簡易ネットワークを用いて、第１実施形態と同様にして最安運賃を算出し出力する。図１２の実行簡易ネットワークは、図１０の簡易ネットワークに、発駅のノードａ、着駅のノードｒ、ノードａ−ｄ間、ノードｍ−ｒ間、ノードｏ−ｒ間をそれぞれ接続する各料金アークを追加したものである。尚、ステップ３３〜４０の動作は、第１実施形態の図６のフローチャートのステップ１２〜１９と同様であるので説明を省略する。

かかる簡易ネットワークを利用した実行簡易ネットワークを用いれば、運賃計算過程において経路を求めるときの（探索の）分岐数を大幅に削減できるので、異なる料金体系間に跨った発駅−着駅間の運賃計算をより一層高速に行うことが可能となり、運賃計算処理時間を短縮できる。

次に、本発明の第３実施形態を説明する。
図５に示す第１実施形態の料金ネットワークでは、異なる料金体系に属する発駅と着駅の間の最安運賃を計算しようとした場合、運賃計算に関して定義されているルールと矛盾する経路が求まる可能性を含んでいる。

ここで、ルールと矛盾する経路とは、以下の２つである。
１つは、連絡不可能な経路である。これについて、図１３の料金ネットワークで説明する。図１３は、料金体系ＡとＣはノードｄとｆで連絡可能であり、料金体系ＢとＣはノードｅとｆで連絡可能であるが、料金体系ＡとＣは連絡不可能と定義されている料金ネットワークの場合である。ここで、連絡可能とは、改札を通らずに乗継ができる、言い換えれば、１つの経路として一括計算してもよいことを意味し、連絡不可能とは、一度改札を通らないと乗継ができない、言い換えれば、１つの経路として一括計算できないことを意味する。従って、例えば、料金体系Ａの地点ａから料金体系Ｂの地点ｂまでの運賃計算は、運賃計算で定義されているルールでは、本来は経路なしとして計算してはいけない経路であるが、図１３の料金ネットワークでは、ａ→ｄ→ｆ→ｅ→ｂの経路のｄ→ｆ→ｅの経路部分の接続のコストが零であるために、恰もｄ−ｅ間が連絡されているものとして、ａ→ｄ→ｅ→ｂの経路を地点ａから地点ｂまでの経路として運賃計算してしまう可能性がある。

もう１つは途中下車経路である。これについて、図１３の料金ネットワークで説明する。例えば、同一料金体系Ａ内で地点ａから地点ｄまでの運賃は、乗車形態として、地点ａからｄまで途中下車することなく乗車することを想定して定めたもので、地点ｍで一旦下車（改札を通過する）することは想定していない。従って、運賃計算のルールとして、ａ−ｄ間の運賃計算は、地点ｍで一旦下車するａ−ｍ−ｄの経路で運賃計算してはならないことになっている。しかし、図１３の料金ネットワークにおいて、例えば、ａ−ｄ間の接続コストと、ａ−ｍ間の接続コストとｍ−ｄ間の接続コストとを加算したコストとが等しい場合、地点ａから地点ｄまでの運賃計算を行う際に、ａ−ｍ−ｄの経路を求めてしまう可能性がある。

第３実施形態は、上述のような運賃計算に関して定義されているルールと矛盾する乗継経路を求めてしまうことを回避できるようにしたネットワークを生成するものである。以下、前記ネットワークをダイレクトネットワークとする。
図１４は、本発明に係る料金計算装置の第３実施形態の構成を示すブロック図である。尚、第１実施形態と同一要素には同一符号を付して説明を省略する。
図１４において、本実施形態の料金計算装置２０は、第１実施形態の料金計算装置１に、ダイレクトネットワークデータ生成部２１を付加して構成される。

前記ダイレクトネットワークデータ生成部２１は、ネットワークデータ生成部４で生成された各サブネットワーク内の全てのノード（以下、元ノードとする）にダミーノードを追加する。更に、各サブネットワーク内のノード（以下、元ノードとする）間を接続するアークについては、その接続元であるアーク元の元ノードを当該元ノードに対応するダミーノードに変更し接続先であるアーク先を元ノードする。また、料金体系の異なるサブネットワーク間を接続する接続アークについては、接続元であるアーク元を元ノードとしその接続先であるアーク先の元ノードを当該元ノードに対応するダミーノードに変更してアークデータを生成する。そして、このようにアークデータ（接続アークデータも含む）の変更された料金ネットワークデータと追加したダミーノードデータからなるダイレクトネットワークデータを料金計算ネットワークデータとして記憶装置９に格納する。

次に、料金計算装置２０によるダイレクトネットワークデータの生成及び最安運賃算出の各動作について説明する。
図１５は、ダイレクトネットワークデータの生成のフローチャートである。
ステップ５１で、ネットワークデータ生成部４により第１実施例の料金ネットワークデータを生成し、記憶装置９に格納する。この料金ネットワークデータの生成手順は、第１実施形態の図４のフローチャートに示す。
ステップ５２で、ダイレクトネットワークデータ生成部２１が記憶装置９から料金ネットワークデータを読込む。
ステップ５３で、読込んだ料金ネットワークデータの全てのノードにダミーノードを追加する。
ステップ５４で、料金ネットワークデータのアークデータの１つを取出す。
ステップ５５で、取出したアークデータが接続アークか否かを判定し、接続アークでなければ、サブネットワーク内のノード同士を接続するアークデータと判断し、ステップ５６に進み、そのアーク元の元ノードをダミーノードに変更する。一方、接続アークであれば、ステップ５７で、そのアーク先の元ノードをダミーノードに変更する。
ステップ５８で、料金ネットワークデータの全てのアークデータを取出したか否かを判定し、判定がＹＥＳであれば、ステップ５９に進み、ダミーノードを追加したサブネットワークデータと変更したアークデータとをダイレクトネットワークデータとし、このダイレクトネットワークデータを記憶装置９に料金計算ネットワークデータとして格納する。

図１６は、図１３の料金ネットワークデータに基づいて生成したダイレクトネットワークデータを用いて構築されるダイレクトネットワークの例を示す。図中、ａ′〜ｆ′、ｍ′〜ｏ′がダミーノードを示す。そして、運賃計算する場合には、各ダミーノードを発駅ノードとし、元ノードを着駅ノードとして扱う。

かかるダイレクトネットワークを用いて、例えば、料金体系Ａの地点ａから料金体系Ｂの地点ｂまでの運賃計算を行う場合、ダミーノードａ′が発駅ノードとなり、ａ′→ｄ→ｆ′の経路で料金体系Ａ−Ｃ間は接続しているが、ダミーノードｆ′の接続先は同一料金体系Ｃ内の元ノードだけであり、料金体系Ｂのノードは接続先になっていないので、料金体系Ａから料金体系Ｃを経由して料金体系Ｂへ行く経路は構成されない。料金体系Ａから料金体系Ｂに行くには、一度改札を通らないと行くことはできないネットワークになっている。従って、上述したルール上の矛盾の１つである連絡不可能経路の問題を回避できる。

また、例えば、同一料金体系Ａ内で地点ａから地点ｄまでの運賃計算を行う場合、ダミーノードａ′が発駅ノードとなり、このダミーノードａ′の接続先は元ノードｍ，ｄであるが、元ノードｍは着駅ノードとして扱うので接続先はない。従って、ダミーノードａ′を発駅として元ノードｄを着駅とする経路のみとなり、上述した２つ目のルール上の矛盾である途中下車経路の問題も回避できる。
尚、アークの接続元・接続先についてであるが、各元ノードを発駅ノードとし、各ダミーノードを着駅ノードとした場合、上記実施形態の接続元・接続先を逆にして、各サブネットワーク内の元ノード間を接続するアークについて、その接続元を元ノードにし、接続先であるアーク先をダミーノードに変更し、また、料金体系の異なるサブネットワーク間を接続する接続アークについては、接続元であるアーク元をダミーノードに変更し、その接続先であるアーク先を元ノードにしてもよい。

このダイレクトネットワークによる最安運賃算出過程は、第１実施形態の料金ネットワークを用いた図６のフローチャートと同様である。ただし、探索閾値設定部６による最大割引額の算出手法が異なる。
以下に、ダイレクトネットワークにおける最大割引額の算出方法について、図７を参照して説明する。

図７において、料金ネットワークの場合と同じノードｃからノードｕへ向かう経路を例として説明する。第１実施形態の料金ネットワークは同一料金体系内で複数のアークを使用する経路が選択可能であるが、ダイレクトネットワークは同一料金体系内では１つのアークしか使用できない。このため、ダイレクトネットワークにおいて最大割引額が適用される可能性のある経路は、図中の点線で示す経路（ｃ→ｄ→ｇ→ｋ→ｏ→ｍ→ｖ→ｕ）である。この経路に適用される可能性のある料金体系間の割引の組合せは以下の（ａ）〜（ｃ）である。
（ａ）２料金体系間割引１回（料金体系１，２間、料金体系２，３間、料金体系３，４間のいずれか１つ）
（ｂ）２料金体系間割引２回（前記３つの料金体系間の中の２つを組合せ）
（ｃ）３料金体系間割引１回（料金体系１〜３間又は料金体系２〜４間のいずれか１つ）

各料金体系間の最大割引額は、データストレージ装置３に格納された乗継関係データの料金体系間の最大割引額から求めることができ、前述した料金ネットワークの場合と同じで、２料金体系間最大割引額が２０円、３料金体系間最大割引額が３０円とすれば、（ａ）は２０円、（ｂ）は４０円、（ｃ）３０円となり、最大割引額は４０円となる。
この最大割引額の算出は、料金ネットワークの場合と同様に数１の（１）式から算出できる。ｉ料金体系間の割引適用回数の制約条件を数２の（３）式のようになる。

尚、料金ネットワークでの最大割引額は、ダイレクトネットワークにおける最大割引額より大きくなることは明らかであるので、ダイレクトネットワークにおける上限値算出のための最大割引額として用いてもよい。
また、図７の説明では、料金体系の系が４つで、且つ、３料金体系間割引まで設定されている場合であったが、本発明ではこれに限らず系の数がいくつでもよく、また、料金体系間割引も２料金体系間割引、３料金体系間割引に限られることはない。

次に、本発明の第４実施形態について説明する。
第４実施形態は、異なる料金体系間において乗継割引制度が存在する場合でも、最短経路探索問題として最安運賃を求めることができるネットワークを生成する。このネットワークを以下では、ディスカウントネットワークとする。
図１７は、本発明に係る料金計算装置の第４実施形態の構成を示すブロック図である。尚、第１実施形態と同一要素には同一符号を付して説明を省略する。
図１７において、本実施形態の料金計算装置３０は、第１実施形態の料金計算装置１から探索閾値設定部６及び最安運賃算出部７を取除き、乗継割引適用アークデータ生成部３１を付加して構成される。

前記乗継割引適用アークデータ生成部３１は、データストレージ装置３に格納された図２のような各社別運賃三角表データ及び図３のような乗継割引表データに基づいて、乗継割引適用アークデータを生成する。乗継割引適用アークは、乗継割引が適用される経路の発駅と着駅にそれぞれ相当するノード間を接続するもので、乗継割引適用アークで接続されるノード間の接続のコストを、その経路の割引前の運賃から割引額を減算した割引適用後の運賃とする。乗継割引が適用される経路及びその発着駅データは、乗継割引表データの発着範囲データと連絡駅データから設定でき、前記コストは確定した経路と各社別運賃三角表データの運賃データに基づいて設定できる。

次に、料金計算装置３０によるディスカウントネットワークデータの生成及び最安運賃算出の各動作について説明する。
図１８は、ディスカウントネットワークデータの生成のフローチャートである。
ステップ６１で、ネットワークデータ生成部４により料金ネットワークデータを生成し、記憶装置９に格納する。この料金ネットワークデータの生成手順は、第１実施形態の図４のフローチャートに示す。
ステップ６２で、乗継割引適用アークデータ生成部３１で、各社別運賃三角表データと乗継割引表データに基づいて乗継割引適用アークデータを生成する。
ステップ６３で、料金ネットワークデータとステップ６２で生成した乗継割引適用アークデータとを結合して、ディスカウントネットワークデータを生成する。
ステップ６４で、ステップ６３で生成したディスカウントネットワークデータを、記憶装置９に料金計算ネットワークデータとして格納する。

図１９に、ディスカウントネットワークデータを用いたディスカウントネットワークの一例を示す。図１９において、料金体系１のノードｂと料金体系３のノードｎの間や、料金体系２のノードｉと料金体系３のノードｐの間を、それぞれ接続している図中の太線が乗継割引適用アークである。

図２０は、ディスカウントネットワークを用いた最安運賃算出のフローチャートである。
ステップ７１で、入力部２から発着駅データが入力されるまで待機し、入力されるとステップ７２に進む。
ステップ７２で、最小コスト探索部５は記憶装置９からディスカウントネットワークデータを読込み、ディスカウントネットワークにおいて最短経路探索アルゴリズムを用いて入力された発駅−着駅間の最安運賃経路を探索する。
ステップ７３で、ステップ７２で探索された経路運賃を最安運賃結果として出力部８を介して出力する。
かかるディスカウントネットワークを用いれば、最小コスト探索部５の探索結果がそのまま最安運賃となるので、計算量を大幅に削減できる利点がある。

次に、本発明の第５実施形態について説明する。
本発明のネットワークを鉄道運賃計算に適用した場合、（イ）同一料金体系の複数回通過、（ロ）５料金体系以上を連絡する経路（現状の鉄道運賃計算規則では４社線以内で運賃計算をする必要がある）、（ハ）同一地点の複数通過等の、禁止されている経路を計算対象に含めてしまう可能性があるという問題が起こる。ただし、（ハ）に関しては、ダイレクトネットワークの場合のみ生じる問題である。

例えば、図２１のネットワーク構成において、地点ｐ−ｆ間の運賃計算を行った場合を考える。この場合、ｐ→ｎ→ｑ→ｒ→ｕ→ｖ→ｌ→ｉ→ｋ→ｈ→ｆの経路は５料金体系に跨った経路であり、ｐ→ｎ→ｑ→ｔ→ｗ→ｕ→ｒ→ｑ→ｇ→ｆの経路は同一地点（地点ｑ）及び同一料金体系を複数回通過する経路であり、ｐ→ｎ→ｑ→ｔ→ｗ→ｕ→ｒ→ｈ→ｆの経路は同一料金体系を複数回通過する経路である。
このような問題を解決するためには、禁止されていない経路が探索されるまで繰返し、ｋ−最短経路探索アルゴリズムにより経路を探索する必要がある。しかし、ノード数が多い場合、計算負荷が大きいことや、ネットワークの形状によってはｋが大きくなる可能性があり、効率が悪い。

本実施形態は、ネットワークを簡略化した上位ネットワークと詳細な下位ネットワークとに階層化したネットワーク形態とすることによって、上述の問題点を解決し、効率良く最安運賃を算出するようにしたものである。

図２２は、本発明に係る料金計算装置の第５実施形態の構成を示すブロック図である。尚、第１実施形態と同一要素には同一符号を付して説明を省略する。
図２２において、本実施形態の料金計算装置４０は、第１実施形態の料金計算装置１の構成に、上位ネットワークデータ生成部４１と、連絡パターンデータ生成部４２と、下位ネットワークデータ生成部４３とを追加して構成されている。また、データストレージ装置３には、前述した（イ）〜（ハ）の禁止条件データが予め格納される。

前記上位ネットワークデータ生成部４１は、料金ネットワークにおける料金体系の異なる各サブネットワーク（各料金体系）を１つのノード（上位ノードとする）と見なし、乗継関係データに基づいて、図２３に示すような上位ノード（サブネットワーク）間を１つのアーク（上位アークとする）で互いに直接接続する簡略化した上位ネットワークデータを生成する。ここで、上位ネットワークの上位アークで接続される上位ノード間の接続のコストを１に設定する。これにより、コストが３までの経路を最短経路探索アルゴリズムによって算出することで、探索経路を４料金体系内に制限でき、５料金体系に跨る経路の探索を防止できる。

前記連絡パターンデータ生成部４２は、上位ネットワークデータと禁止条件データに基づいて、異なる料金体系に跨る発駅と着駅のノードの組合せ数に対応する数の各料金体系のペア毎の図２４に示すような連絡パターンデータを予め生成する。料金体系間を接続する上位アークは、図中の矢印で示すように方向性を持っている。図２４は、図２１のネットワークにおいて初駅を地点ｐ、着駅を地点ｆとした場合の連絡パターン例を示しており、この場合、（Ａ）、（Ｂ）の２通りの連絡パターンとなる。これら連絡パターンデータは、上位ネットワークの始点を含む上位ノードから終点を含む上位ノードまでの上位アークのコスト値が所定コスト値（例えば前述のコスト３）以下で且つ始点から終点への経路において上位ノードが重複しないような接続関係を有した、前記禁止条件を満した連絡パターンデータとなっている。

前記下位ネットワークデータ生成部４３は、連絡パターンの各上位ノードを料金ネットワークのサブネットワークデータに置換え、これらサブネットワーク間を接続アークで接続した図２５のような前記禁止条件を満たす詳細な下位ネットワークデータを生成する。図２５の（Ａ）は、図２４の（Ａ）の連絡パターンに対応するものであり、（Ｂ）は、図２４の（Ｂ）の連絡パターンに対応するものである。

尚、下位ネットワーク形態としては、図２５に示す第１実施形態の料金ネットワーク形態の他、第２〜第４実施形態の簡易料金計算ネットワーク形態、ダイレクトネットワーク形態、或いはディスカウントネットワーク形態でもよい。また、これら簡易料金計算ネットワーク、ダイレクトネットワーク及びディスカウントネットワークの少なくとも２つのネットワーク形態を組み合わせるようにしてもよい。

図２６は、第５実施形態の階層化構造のネットワークデータの生成のフローチャートである。
ステップ８１で、ネットワークデータ生成部４により料金ネットワークデータを生成し、記憶装置９に格納する。この料金ネットワークデータの生成手順は、第１実施形態の図４のフローチャートに示す。
ステップ８２で、上位ネットワークデータ生成部４１により図２３に示すような上位ネットワークデータを生成する。
ステップ８３で、連絡パターンデータ生成部４２で、上位ネットワークデータと禁止条件データに基づいて、発駅と着駅のノードの組合せ数に対応する数の各料金体系のペア毎の連絡パターンデータを生成する。
ステップ８４で、下位ネットワークデータ生成部４３で、入力された発駅と着駅の情報に基づいて、選択された連絡パターンデータと料金ネットワークのサブネットワークデータから詳細な下位ネットワークデータを生成する。
ステップ８５で、生成した上位ネットワーク、連絡パターン及び下位ネットワークの各データを記憶装置９に格納する。

図２７は、階層化したネットワークを用いた最安運賃算出のフローチャートであり、図２１のネットワークにおいて、発駅として地点ｐ、着駅として地点ｆが入力された場合を例に説明する。
ステップ９１で、入力部２から発着駅データが入力されるまで待機し、入力されるとステップ９２に進む。
ステップ９２で、入力された発着駅情報に対応する連絡パターンを選択する。ここで、発駅が地点ｐ、着駅が地点ｆとすると、禁止条件から連絡パターンは、図２４の（Ａ）に示す料金体系４→料金体系１→料金体系２の連絡パターンと、（Ｂ）に示す料金体系４→料金体系５→料金体系２の連絡パターンの２通りが選択される。
ステップ９３で、選択された連絡パターンから下位ネットワークを生成する。この場合、図２５の（Ａ）、（Ｂ）に示す下位ネットワークが生成される。

ステップ９４で、最小コスト探索部５により、ステップ９３で生成された各下位ネットワークにおける最安運賃を、最短経路探索アルゴリズムを用いてそれぞれ算出する。ここで、乗継割引が適用される可能性がなければ、最小コスト探索部５で求めた運賃を最安運賃とすればよい。乗継割引が適用される可能性が存在する場合は、第１実施形態と同様にして探索閾値を設定し、それ以下の運賃の最も安い運賃を最安運賃とする。また、下位ネットワークとして、乗継割引適用アークを設定したディスカウントネットワークを適用すれば、最小コスト探索部５の算出した運賃を最安とすることができる。
ステップ９５で、ステップ９４で算出された各下位ネットワークの最安運賃を比較し、安い方を最安運賃として出力部８を介して出力する。

尚、上述の例では階層化したネットワークの下位ネットワークとして、料金ネットワークのサブネットワークを用いた例を示したが、下位ネットワーク形態としては、第２実施形態の簡略料金計算ネットワーク、第３実施形態のダイレクトネットワーク及び第４実施形態のディスカウントネットワークをそれぞれ適用してもよく、また、これらの中の２つを組み合わせてもよく、３つ全てを組み合わせたものでもよい。乗継割引経路が存在する場合、下位ネットワークがディスカウントネットワーク形態である場合を除いて、ステップ９４の運賃算出後、第１実施形態と同様に、図６のステップ１３以降の処理を行って最安運賃を算出することになる。
また、連絡パターンデータ生成部４２は、発駅及び着駅情報が入力されたときに、その発駅及び着駅情報に応じて、予め定めた料金計算上の禁止条件を満足させる接続関係にある系のみを上位ネットワークデータから選択して連絡パターンを生成するようにしてもよい。この場合、多数の連絡パターンデータを格納する必要がなくなる。

このようにネットワーク構成を、簡略化した上位ネットワークと、禁止条件に基づいて経路を制限した詳細な下位ネットワークとに階層化し、下位ネットワークによって最安運賃を算出するようにすれば、禁止されている経路は算出されなくなると共に、求める経路数は大幅に削減される。よって、前述の問題点を回避でき、効率良く短時間で最安運賃を算出することが可能となる。

上述の各実施形態では、簡易料金計算ネットワーク、ダイレクトネットワーク、ディスカウントネットワークについてそれぞれ個別に説明したが、簡易料金計算ネットワークにダミーノード及び乗継割引適用アークを追加して、簡易料金計算ネットワークとダイレクトネットワークとディスカウントネットワークを組み合わせてもよい。また、簡易料金計算ネットワークとダイレクトネットワークの組合せ、簡易料金計算ネットワークとディスカウントネットワークの組合せ、ダイレクトネットワークとディスカウントネットワークの組合せも考えられる。

本発明の料金計算ネットワークは、鉄道の運賃計算への適用に限るものではない。例えば、以下のような適用が可能である。
（１）時間帯によって単位時間当たりの料金設定が異なる駐車場等の駐車料金や電力料金等の計算への適用。
（２）重さや距離等によって料金設定が異なる陸運、海運や空輸等の運送／配送料金等の計算への適用。この場合、陸運、海運や空輸は異なる系として相互に跨ってもよい。
（３）有料道路の料金計算への適用。
（４）保険料の計算への適用。保険の内容毎に保険会社を選択する等が考えられる。
（５）税金等の計算への適用。
（６）生活保護を受ける人の手取りを減らさず、生活保護支給額を最小にする生活保護の支給金額の計算への適用。例えば、仕事についた（生活保護が無くなった）ときの手取りが生活保護を受けているときの手取りにならないように、生活保護の支給額を決定するための計算に用いることができる。
（７）ＳａａＳ（ｓｏｆｔｗａｒｅ ａｓ ａ ｓｅｒｖｉｃｅ）によるアプリ利用の課金計算への適用。例えば、長時間使うと割引率を高くしたり、特定の機能の組合せなら割引する等の料金計算をすることが考えられる。

上述の実施形態におけるサブネットワークは、系内の全てのノードをアークで互いに直接接続する構成であるが、料金計算ネットワークの適用対象によっては全てのノードを直接接続する構成としなくともよく、各ノードを必要に応じてアークで直接接続し、アークで接続したノード間の接続のコストを料金とする構成のものであればよい。このような例として、例えば上述の駐車料金計算に適用する場合が考えられる。
例えば、入庫から３時間までは３００円、それ以後３０分毎に１００円が加算されるような料金体系の駐車場の駐車料金計算に用いる料金計算ネットワーク構成としては、図２８に示すような料金計算ネットワーク構成とすればよい。
図２８の料金計算ネットワークは、駐車時間０分のノードを中心とし、当該ノードを接続元としてアークを放射状に配置し、各アークの接続先を入庫からの駐車時間を示すノードとし、アークで接続したノード間のコストを、アーク先のノードの駐車時間に応じた駐車料金とする構成である。ここで、駐車時間の設定間隔は、分単位、秒単位等、自由であり、その料金体系等に合わせて適切に設定すればよい。
そして、駐車時間０分のノードを他のサブネットワーク（例えば、ある駐車場の位置する駅の鉄道運賃）と接続アークで接続することで、複数のサブネットワークに跨る料金計算ネットワークを構成することが可能となる。

尚、本発明では、各会社が全く同一の料金体系を持っていたとしても、会社が異なるためそれぞれ別の料金体系として扱うことができ、また、同一の会社が２以上の料金体系を持っている場合にもそれぞれ別の料金体系として扱うことができるため、料金体系の変更等にも柔軟に対応でき、多様な料金ネットワークの設定を行うことができる。

本発明に係る料金計算装置の第１実施形態の構成を示すブロック図 運賃三角表データの例を示す図 乗継割引表データの例を示す図 第１実施形態の料金ネットワークデータの生成フローチャート 料金ネットワークの例を示す図 料金ネットワークを用いた最安運賃算出フローチャート 最大割引額の算出手法の説明図 本発明に係る料金計算装置の第２実施形態の構成を示すブロック図 第２実施形態の簡易ネットワークデータの生成フローチャート 簡易ネットワークの例を示す図 簡易ネットワークを用いた最安運賃算出フローチャート 実行簡易ネットワークの例を示す図 料金ネットワークで最安運賃を算出する場合の問題点の説明図 本発明に係る料金計算装置の第３実施形態の構成を示すブロック図 ダイレクトネットワークデータの生成フローチャート ダイレクトネットワークの例を示す図 本発明に係る料金計算装置の第４実施形態の構成を示すブロック図 ディスカウントネットワークデータの生成フローチャート ディスカウントネットワークの例を示す図 ディスカウントネットワークを用いた最安運賃算出フローチャート 料金ネットワークを鉄道運賃計算に適用する場合の問題点の説明図 本発明に係る料金計算装置の第５実施形態の構成を示すブロック図 上位ネットワークの例を示す図 連絡パターン例を示す図 下位ネットワークの例を示す図 階層化したネットワークデータの生成フローチャート 階層化したネットワークを用いた最安運賃算出フローチャート 駐車場の駐車料金計算に適用する料金計算ネットワークの一例を示す図 物理ネットワークの例を示す図

符号の説明

１，１０，２０，３０，４０ 料金計算装置
２ 入力部
３ データストレージ装置
４ ネットワークデータ生成部
５ 最小コスト探索部
６ 探索閾値設定部
７ 最安運賃算出部
８ 出力部
９ 記憶装置
１１ 簡易ネットワークデータ生成部
２１ ダイレクトネットワークデータ生成部
３１ 乗継割引適用アークデータ生成部
４１ 上位ネットワークデータ生成部
４２ 連絡パターン生成部
４３ 下位ネットワークデータ生成部

Claims (12)

1. 異なる料金体系の複数の系の各系毎の料金を定めた料金データと各系間の接続関係を示す接続関係データとを格納するデータ格納部と、
   前記複数の系の各系内の各点をノードとし、各ノードを必要に応じてアークで直接接続し、前記アークで接続したノード間の接続のコストを前記料金データに基づいた料金としたネットワークデータを生成し、前記各系毎のネットワークデータをそれぞれサブネットワークデータとし、前記接続関係データに基づいて異なるサブネットワークデータのノード間を接続する接続アークデータを生成し、前記サブネットワークデータと接続アークデータを料金計算ネットワークデータとするネットワークデータ生成部と、
   を備えて構成したことを特徴とする料金計算ネットワーク生成装置。
2. 前記ネットワークデータ生成部は、前記複数の系の各系内の全てのノードをアークで互いに直接接続し、前記アークで接続したノード間の接続のコストを前記料金データに基づいた料金としたネットワークデータを、前記料金計算ネットワークデータとして生成する構成とした請求項１に記載の料金計算ネットワーク生成装置。
3. 前記ネットワークデータ生成部は、前記アークで接続される前記ノード間の接続のコストを料金零とした前記料金計算ネットワークデータを生成する構成とした請求項１又は２に記載の料金計算ネットワーク生成装置。
4. 前記ネットワークデータ生成部は、前記料金計算ネットワークデータにおける各サブネットワークをそれぞれ１つの上位のノードと見なし、前記接続関係データに基づいて前記上位ノード間を１つの上位のアークで接続し、この上位アークで接続される前記上位ノード間の接続のコストを１とした上位ネットワークデータを生成してネットワークデータの階層化を行い、
   異なる料金体系の複数の系に跨る始点と終点の情報が入力されたときに、予め定めた料金計算上の禁止条件に基づいて、前記上位ネットワークの始点を含む上位ノードから終点を含む上位ノードまでの上位アークのコスト値が所定コスト値以下で且つ始点から終点への経路において上位ノードが重複しないような接続関係を有する連絡パターンを前記上位ネットワークデータから選択し、
   前記選択された連絡パターンデータにおける各上位ノードに対応するそれぞれのサブネットワークとこれらサブネットワーク間を接続する接続アークの各データから前記禁止条件を満たす下位ネットワークデータを生成し、この下位ネットワークデータを料金計算ネットワークデータとする請求項１〜３のいずれか１つに記載の料金計算ネットワーク生成装置。
5. 前記各サブネットワークデータを、前記接続アークで接続されるノードデータとこれらノード間を接続するアークデータのみで構成し、これらサブネットワークデータと前記接続アークデータからなる簡易ネットワークデータを生成し、
   異なる料金体系の複数の系を跨いだ始点と終点の情報が入力されたときに、前記簡易ネットワークデータに始点と終点の各ノードデータ及び始点と終点のそれぞれに接続する各アークデータを追加して、簡易料金計算ネットワークデータを生成する構成とした請求項１〜４のいずれか１つに記載の料金計算ネットワーク生成装置。
6. 前記各サブネットワークデータを、前記接続アークで接続されるノードデータとこれらノード間を接続するアークデータのみで構成し、これらサブネットワークデータと前記接続アークデータからなる簡易ネットワークデータを生成し、
   前記簡易ネットワークデータに異なる料金体系の複数の系を跨いだ始点と終点の各ノードデータ及び始点と終点のそれぞれに接続する各アークデータを追加した簡易料金計算ネットワークデータを、前記始点と終点の全ての組合せ分予め生成しておき、前記始点と終点の情報が入力されたときに、当該入力情報に対応した簡易料金計算ネットワークデータを選択する構成とした請求項１〜４のいずれか１つに記載の料金計算ネットワーク生成装置。
7. 前記料金計算ネットワークデータは、各サブネットワークの各ノード毎にダミーノードを追加したノードデータと、各サブネットワーク内のノード間を接続する前記アークの接続元又は接続先のどちらか一方端をダミーノードとしたアークデータとで構成したサブネットワークデータを有すると共に、
   前記アークの接続元をダミーノードとしたとき、異なるサブネットワークのノード間を接続する前記接続アークの接続先をダミーノードとする接続アークデータを有し、
   前記アークの接続先をダミーノードとしたとき、異なるサブネットワークのノード間を接続する前記接続アークの接続元をダミーノードとする接続アークデータを有する構成とした請求項１〜６のいずれか１つに記載の料金計算ネットワーク生成装置。
8. 前記料金計算ネットワークデータは、異なる各サブネットワーク間の料金割引のある所定の２点間を直接接続する割引経路を示す割引アークデータを有し、予め定めた前記所定の２点間の料金割引データに基づいて、前記割引アークで接続されるノード間の接続のコストを割引後の料金とする構成である請求項１〜７のいずれか１つに記載の料金計算ネットワーク生成装置。
9. 始点と終点の情報を入力する入力部と、
   請求項１〜８のいずれか１つに記載の料金計算ネットワーク生成装置で生成した料金計算ネットワークデータを格納するネットワークデータ格納部と、
   始点と終点の情報が入力されたときに、前記ネットワークデータ格納部の料金計算ネットワークデータに基づいて料金計算ネットワークを構築し、前記料金計算ネットワークの前記始点から終点までの最安料金を算出する最安料金算出部と、
   算出した前記最安料金結果を出力する出力部と、
   を備えて構成したことを特徴とする料金計算装置。
10. 前記料金計算ネットワークデータが、請求項１〜７のいずれか１つに記載の料金計算ネットワーク生成装置で生成されたデータであるとき、
    前記最安料金算出部は、
    前記料金計算ネットワークにおける前記始点から終点までのアークのコストが最小となる経路を探索する最小コスト探索部と、
    料金割引を適用する経路とその割引額を示す料金割引データに基づいて、前記始点から終点までの経路に適用される割引額の最大値を算出する最大割引額算出部と、
    前記最小コスト探索部で探索された最小コストの料金に前記最大割引額算出部で算出した最大割引額を加算して探索閾値を設定する探索閾値設定部と、
    前記料金計算ネットワークに基づいて、アークのコストが前記探索閾値以下となる全ての経路を探索し、各経路の料金を算出する第１の料金算出部と、
    前記料金割引データに基づいて、探索された経路に割引が適用される経路があるときに、前記第１の料金算出部で算出したその経路の割引適用前料金からその経路に適用される割引額を減算して割引適用後の料金を算出する第２の料金算出部と、
    前記第１の料金算出部で算出した料金及び前記第２の料金算出部で算出した料金の中で最安の料金を選択する最安料金選択部と、
    を備える構成である請求項９に記載の料金計算装置。
11. 前記料金計算ネットワークデータが、請求項８に記載の料金計算ネットワーク生成装置で生成されたデータであるとき、
    前記最安料金算出部は、前記料金計算ネットワークにおける前記始点から終点までのアークのコストが最小となる経路を探索する最小コスト探索部を備え、この最小コスト探索部で探索された経路のコストを最安料金とする構成である請求項９に記載の料金計算装置。
12. 前記料金が、鉄道運賃である請求項９〜１１のいずれか１つに記載の料金計算装置。

Images