(57)【要約】【課題】修正された列車ダイヤに対する旅客の移動経路の算出に要する演算量の削減。【解決手段】修正後のダイヤネットワークにおいて、修正されたノード、この修正されたノードを終端とする各アークの始端ノード、及び、修正されたアークの始端ノードが要チェックノードとして抽出され、これらの要チェックノードについて、その基準時刻が遅い順に、目的ノードｖまでの最適移動経路を更新する。【選択図】図１
2014144724.tif 000002
【特許請求の範囲】
【請求項１】
各列車の各駅の着発に係る事象それぞれを表わすノード同士をコストが関連づけられたアークで結んだダイヤネットワークについて、各ノード毎に、当該ノードを出発ノードとする全ての目的候補ノードについて最小コストで当該目的候補ノードに至るための次ノードと当該最小コストとを表す最適移動経路情報が定められており、前記ダイヤネットワークの一部を修正した場合の修正後のダイヤネットワークに適合するように前記最適移動経路情報をコンピュータに更新させるためのプログラムであって、
修正後のダイヤネットワークにおいて、修正されたノード、修正されたノードを終端ノードとするアークの始端ノード、及び、修正されたアークの始端ノードを抽出し、要チェックノードとして記憶部に記憶させる抽出手段、
前記要チェックノードのうち、該当事象の発生時刻が遅い順に一のノードを選択する選択手段、
前記一のノードに係る前記最適移動経路情報を更新する更新手段、
前記更新手段により前記一のノードに係る前記最適移動経路情報に含まれる最小コストが更新された場合に、前記一のノードを終端ノードとするアークの始端ノードを前記要チェックノードとして前記記憶部に追加記憶させる追加記憶制御手段、
として前記コンピュータを機能させるためのプログラム。
【請求項２】
前記更新手段は、前記一のノードに係る前記最適移動経路情報に含まれる最小コストが、修正後のダイヤネットワークに適合するか否かを判定し、適合しない場合に最小コストを更新する手段を有する、
請求項１に記載のプログラム。
【請求項３】
前記更新手段は、前記一のノードに係る前記最適移動経路情報に含まれる次ノードが修正後のダイヤネットワークに存在するか否か、及び、当該最適移動経路情報に含まれる最小コストが修正後のダイヤネットワークに適合するか否か、に基づいて、当該次ノードの更新要否を判定する手段を有する、
請求項１又は２に記載のプログラム。
【請求項４】
各アークについて、当該アークに係るノード間遷移の所要時分に基づいて当該アークのコストを設定するコスト設定手段、
として前記コンピュータを更に機能させるための請求項１〜３の何れか一項に記載のプログラム。
【請求項５】
各列車の各駅の着発に係る事象それぞれを表わすノード同士をコストが関連づけられたアークで結んだダイヤネットワークについて、各ノード毎に、当該ノードを出発ノードとする全ての目的候補ノードについて最小コストで当該目的候補ノードに至るための次ノードと当該最小コストとを表す最適移動経路情報が定められており、前記ダイヤネットワークの一部を修正した場合の修正後のダイヤネットワークに適合するように前記最適移動経路情報を更新する最適移動経路算出装置であって、
修正後のダイヤネットワークにおいて、修正されたノード、修正されたノードを終端ノードとするアークの始端ノード、及び、修正されたアークの始端ノードを抽出し、要チェックノードとして記憶部に記憶させる抽出手段と、
前記要チェックノードのうち、該当事象の発生時刻が遅い順に一のノードを選択する選択手段と、
前記一のノードに係る前記最適移動経路情報を更新する更新手段と、
前記更新手段により前記一のノードに係る前記最適移動経路情報に含まれる最小コストが更新された場合に、前記一のノードを終端ノードとするアークの始端ノードを前記要チェックノードとして前記記憶部に追加記憶させる追加記憶制御手段と、
を備えた最適移動経路算出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、修正後のダイヤネットワークに適合するように最適移動経路を更新する最適移動経路算出装置等に関する。
【背景技術】
【０００２】
鉄道においては、コンピュータを用いた列車ダイヤの作成が行われている。かかる列車ダイヤの作成では、先ずは暫定的な列車ダイヤを作成し、この列車ダイヤの修正、評価を繰り返すことで、最終的に評価の高い（良い）列車ダイヤを得る方法が知られている（例えば、特許文献１参照）。
【０００３】
列車ダイヤの評価の際には、この列車ダイヤに対する各旅客の移動経路の算出を行う必要が有る。この旅客の移動経路の算出方法としては、旅客の出現駅（或いは出発駅）から目的駅に至る経路を候補として列挙し、旅客の乗車に係るコスト（不効用値）が最小となる経路を当該旅客の移動経路として選択する方法が一般的であった。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−２３７９４８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
列車ダイヤを一部修正した場合には各旅客の移動経路を再算出する必要があるが、従来は、列車ダイヤの修正が一部であるにも関わらず、列車ダイヤの全体を対象として移動経路を一から算出する必要があった。想定する旅客が多いほど、或いは、対象とする列車ダイヤの規模が大きいほど、各旅客の移動経路の算出に要する演算量が多くなる。より“良い”列車ダイヤを得るために列車ダイヤの修正を繰り返そうとすると、その修正毎に全ての旅客について移動経路の算出を行う必要が有る。
【０００６】
本発明は、上記事情に鑑みてなされたものであり、その目的とするところは、修正された列車ダイヤに対する旅客の移動経路の算出に要する演算量を削減することである。
【課題を解決するための手段】
【０００７】
各列車の各駅の着発に係る事象それぞれを表わすノード同士をコストが関連づけられたアークで結んだダイヤネットワークについて、各ノード毎に、当該ノードを出発ノードとする全ての目的候補ノードについて最小コストで当該目的候補ノードに至るための次ノードと当該最小コストとを表す最適移動経路情報が定められており、前記ダイヤネットワークの一部を修正した場合の修正後のダイヤネットワークに適合するように前記最適移動経路情報をコンピュータに更新させるためのプログラムであって、
修正後のダイヤネットワークにおいて、修正されたノード、修正されたノードを終端ノードとするアークの始端ノード、及び、修正されたアークの始端ノードを抽出し、要チェックノードとして記憶部に記憶させる抽出手段、
前記要チェックノードのうち、該当事象の発生時刻が遅い順に一のノードを選択する選択手段、
前記一のノードに係る前記最適移動経路情報を更新する更新手段、
前記更新手段により前記一のノードに係る前記最適移動経路情報に含まれる最小コストが更新された場合に、前記一のノードを終端ノードとするアークの始端ノードを前記要チェックノードとして前記記憶部に追加記憶させる追加記憶制御手段、
として前記コンピュータを機能させるためのプログラムである。
【０００８】
また、他の発明として、
各列車の各駅の着発に係る事象それぞれを表わすノード同士をコストが関連づけられたアークで結んだダイヤネットワークについて、各ノード毎に、当該ノードを出発ノードとする全ての目的候補ノードについて最小コストで当該目的候補ノードに至るための次ノードと当該最小コストとを表す最適移動経路情報が定められており、前記ダイヤネットワークの一部を修正した場合の修正後のダイヤネットワークに適合するように前記最適移動経路情報を更新する最適移動経路算出装置であって、
修正後のダイヤネットワークにおいて、修正されたノード、修正されたノードを終端ノードとするアークの始端ノード、及び、修正されたアークの始端ノードを抽出し、要チェックノードとして記憶部に記憶させる抽出手段と、
前記要チェックノードのうち、該当事象の発生時刻が遅い順に一のノードを選択する選択手段と、
前記一のノードに係る前記最適移動経路情報を更新する更新手段と、
前記更新手段により前記一のノードに係る前記最適移動経路情報に含まれる最小コストが更新された場合に、前記一のノードを終端ノードとするアークの始端ノードを前記要チェックノードとして前記記憶部に追加記憶させる追加記憶制御手段と、
を備えた最適移動経路算出装置を構成しても良い。
【０００９】
この第１の発明等によれば、一部を修正した修正後のダイヤネットワークにおいて要チェックノードが抽出され、該当事象の発生時刻が遅い順に、要チェックノードに係る最適移動経路情報が更新される。更に、一のノードに係る最適移動経路情報の最小コストが更新された場合に、当該一のノードを終端とするアークの始端ノードが要チェックノードとして追加される。つまり、修正後のダイヤネットワークについて、要チェックノードとして抽出したノードについてのみ最適移動経路の算出を行えば良い。これにより、修正後のダイヤネットワークの全てのノードについて最適移動経路の算出を行う必要が無いため、最適移動経路情報の更新に要する演算量の削減が図れる。
【００１０】
また、第２の発明として、第１の発明のプログラムであって、
前記更新手段は、前記一のノードに係る前記最適移動経路情報に含まれる最小コストが、修正後のダイヤネットワークに適合するか否かを判定し、適合しない場合に最小コストを更新する手段を有する、
プログラムを構成しても良い。
【００１１】
この第２の発明によれば、一のノードに係る最適移動経路情報の更新として、一のノードに係る最適移動経路に含まれる最小コストが、修正後のダイヤネットワークに適合するか否かが判定され、適合しない場合に最小コストの更新がなされる。
【００１２】
また、第３の発明として、第１又は第２の発明のプログラムであって、
前記更新手段は、前記一のノードに係る前記最適移動経路情報に含まれる次ノードが修正後のダイヤネットワークに存在するか否か、及び、当該最適移動経路情報に含まれる最小コストが修正後のダイヤネットワークに適合するか否か、に基づいて、当該次ノードの更新要否を判定する手段を有する、
プログラムを構成しても良い。
【００１３】
この第３の発明によれば、一のノードに係る最適移動経路情報の更新として、この最適移動経路情報に含まれる次ノードが修正後のダイヤネットワークに存在するか否か、及び、最適移動経路情報に含まれる最小コストが修正後のダイヤネットワークに適合するか否かに基づいて、次ノードの更新要否を判定する。
【００１４】
また、第４の発明として、第１〜第３の何れかの発明のプログラムであって、
各アークについて、当該アークに係るノード間遷移の所要時分に基づいて当該アークのコストを設定するコスト設定手段、
として前記コンピュータを更に機能させるためのプログラムを構成しても良い。
【００１５】
この第４の発明によれば、ダイヤネットワークを構成する各アークについて、当該アークに係るノード間遷移の所要時分に基づいてコストが設定される。
【図面の簡単な説明】
【００１６】
【図１】ダイヤネットワークの構成例。
【図２】最適移動経路の算出の説明図。
【図３】ダイヤネットワークの修正の説明図。
【図４】ダイヤネットワークの修正の説明図。
【図５】ダイヤネットワークの修正の説明図。
【図６】ダイヤネットワークの修正の説明図。
【図７】ダイヤネットワークの修正の説明図。
【図８】ダイヤネットワークの修正の説明図。
【図９】ダイヤネットワークの修正の説明図。
【図１０】ダイヤネットワークの修正の説明図。
【図１１】最適移動経路の再算出の説明図。
【図１２】最適移動経路情報算出装置の構成図。
【図１３】最適移動経路情報のデータ構成例。
【図１４】最適移動経路算出処理のフローチャート。
【図１５】最適移動経路算出処理において実行される最適移動経路情報更新処理のフローチャート。
【図１６】図１５のフローチャートの続き。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施形態を説明する。但し、本発明の適用可能な実施形態がこれに限定されるものでは無い。
【００１８】
［原理］
本実施形態は、列車ダイヤの修正がなされた際に、修正後の列車ダイヤを表現するダイヤネットワーク上において旅客の移動経路の再算出を行うものである。
【００１９】
（１）ダイヤネットワークの構成
図１は、ダイヤネットワークの一例である。図１に示す例では、Ａ駅〜Ｃ駅間を対象とし、Ａ駅からＣ駅へ向かう３台の列車（１〜３列車）からなる列車ダイヤを表現したダイヤネットワークを示している。Ｂ駅には２つのホーム（１，２番線）が設けられ、進行方向が同一方向の２台の列車が同時に停車可能となっている。
【００２０】
ダイヤネットワークは、列車の着発に係る事象を表すノード１０と、遷移可能なノード１０間を結ぶアーク２０とから構成される。
【００２１】
ノード１０には、列車が駅に到着した事象を表す着ノードと、列車が駅から発車した事象を表す発ノードと、発ノードそれぞれに対応して設定されて当該列車へ乗車する旅客が滞留している事象を表す滞留ノードと、の３種類がある。
【００２２】
また、各ノード１０には、該当する事象の発生時刻を表す基準時刻が定められる。すなわち、着ノードの基準時刻は、列車ダイヤにおける着時刻である。発ノードの基準時刻は、列車ダイヤにおける発時刻である。滞留ノードの基準時刻は、対応する発ノードの基準時刻の所定時分前（例えば、１分前）の時刻である。
【００２３】
アーク２０には、列車が駅間を走行していることを表す列車アークと、列車が駅に停車していることを表す停車アークと、旅客が列車から降車することを表す乗換アークと、旅客が列車に乗車することを表す乗車アークと、乗客が駅に滞留していることを表す滞留アークと、の５種類がある。
【００２４】
アーク２０は、基準時刻が早いほうのノード１０から遅いほうのノード１０へ向かうように設定される。すなわち、列車アークは、発ノードから、同一列車の次駅の着ノードへ向かうように設定される。停車アークは、着ノードから、同一列車の同一駅における発ノードへ向かうように設定される。
【００２５】
乗換アークは、着ノードから、同一駅の次の滞留ノードへ向かうように設定される。特に、複数のホームが存在する駅（図１では、Ｂ駅）では、乗換アークは、同一駅の同一ホームにおける次の滞留ノードへ向かう同一ホーム乗換アークと、同一駅の異ホームにおける次の滞留ノードへ向かう異ホーム乗換アークとに分類される。異ホーム乗換アークについては、始端の着ノードの基準時刻と終端の滞留ノードの基準時刻との差が、所定の乗換時分以上（例えば、２分以上）となる場合に設定される。
【００２６】
乗車アークは、滞留ノードから、同一駅の同一ホームの次の発ノードへ向かうように設定される。滞留アークは、滞留ノードから、同一駅の同一ホームにおける次の滞留ノードへ向かうように設定される。
【００２７】
ここで、あるノード１０の“次”のノード１０や“直前”のノード１０とは、各ノード１０に定められた基準時刻に従った順序を表す。
【００２８】
また、アーク２０には、ノード１０間の遷移に要する時間（すなわち、基準時刻の差）に基づくコストが定められる。但し、乗換アークについては、該当するノード間の基準時分の差である乗換時分と、所定の乗換コストとの和が、コストとして設定される。乗換コストは、異ホームの乗り換えのほうが、同一ホームの乗り換えよりも大きい値が設定される。
【００２９】
（２）最適移動経路
本実施形態において、最適移動経路を求める際には、先ず、ダイヤネットワークを構成する全てのノード１０のうち、基準時刻が最も遅い（ネットワークにおいて最も下流側の）ノード１０を出発ノードとして選択する。次に、その出発ノードから到達可能な出発ノード以降の目的候補駅の着ノードを基準時刻が遅い順に目的ノードとして選択することで、出発ノードと目的ノードの組み合わせを求める。出発ノード以降の全ての着ノードを目的ノードとして選択した後は、当該出発ノードの次に基準時刻が遅いノード１０を出発ノードとして選択し、当該出発ノードに対する目的ノードの選択を行うことで、出発ノードと目的ノードの組み合わせを求める。これを繰り返す。
【００３０】
また、組み合わせ１つ１つを求めた際に、当該組み合わせに係る最適移動経路を算出する。最適移動経路は、当該組み合わせに係る出発ノードから、他のノード１０及びアーク２０を経由して、当該組み合わせに係る目的ノードへ至る経路であって、経由したアーク２０それぞれのコストＣの総和が最小となる経路である。
【００３１】
つまり、ある出発ノードについて最適移動経路を求めるとき、それより基準時刻が遅い（下流の）ノード１０の全てについて、最適移動経路が算出されている。
【００３２】
例えば、図２を参照して説明する。出発ノードｕから目的ノードｓに至る最適移動経路を算出する場合、先ず、ダイヤネットワークにおいて、出発ノードｕを始端とする全てのアークｕｖ−１，ｕｖ−２，・・・、を抽出する。
【００３３】
次いで、これらのアークｕｖ−ｎ（ｎ＝１，２，・・・）それぞれについて、当該アークｕｖ−ｎを経由した場合の、出発ノードｕから目的ノードｓへ至る経路のコストＣｕｓｎを算出する。すなわち、出発ノードｕからアークｕｖ−ｎを経由して目的ノードｓへ至る経路のコストＣｕｓｎは、アークｕｖ−ｎのコストＣｕｖｎと、アークｕｖ−ｎの終端ノードｖｎから目的ノードｓへの最小コストＣｖｓｎとの和となる。（Ｃｕｓｎ＝Ｃｕｖｎ＋Ｃｖｓｎ）。
【００３４】
そして、これらの経路それぞれのうち、コストＣｕｓｎが最小となる経路が、出発ノードｕから目的ノードｓまでの最適移動経路となり、その経路のコストが最小コストＣｕｓとなる。なお、本実施形態において、最適移動経路の情報としては、出発ノードの次のノードｖｎと、最小コストＣｕｓとによって表されることとして説明する。
【００３５】
（３）ダイヤネットワークの修正
列車ダイヤに対する修正に応じて、ダイヤネットワークの修正がなされる。ダイヤネットワークの修正には、１）新たなノードの追加、ノードの削除、ノードの基準時刻の変更といったノードの修正と、２）新たなアークの追加、アークの削除、アークの終端ノードの変更（アークの付け替え）、アークのコストの変更といったアークの修正と、がある。ダイヤネットワークの修正について具体的に説明する。
【００３６】
（３−１）ノードの追加
ノードの追加は、新たな列車の設定や、通過駅での停車といった列車ダイヤの修正にともなってなされる。
【００３７】
図３，図４は、ノードの追加の一例を説明する図である。図３は、修正前のダイヤネットワークの一例である。Ｂ駅を対象とし、１列車が１番線ホームに着発した後、２番線ホームに２列車が着発する列車ダイヤを表現したダイヤネットワークを示している。このような列車ダイヤに対して“Ｂ駅の１番線ホームに３列車を停車する”修正がなされた場合、図４のようなダイヤネットワークの修正がなされる。
【００３８】
すなわち、図４の（１）に示すように、Ｂ駅の１番線ホームに３列車の着事象を表す着ノード１０ａ、及び、発事象を表す発ノード１０ｂを追加する。次いで、このノード１０ａ，１０ｂの追加に応じたアーク２０の修正を行う。すなわち、着ノード１０ａを終端とする列車アーク２０ａ、着ノード１０ａから発ノード１０ｂに向かう停車アーク２０ｂ、及び、着ノード１０ａから同一駅の異ホームにおける次の滞留ノード１０ｃへ向かう乗換アーク２０ｃ、発ノード１０ｂを始端とする列車アーク２０ｄ、を追加する。
【００３９】
更に、図４の（２）に示すように、追加した発ノード１０ｂに対応する滞留ノード１０ｄを追加し、この滞留ノード１０ｄの追加に応じたアーク２０の修正を行う。すなわち、着ノード１０ａから滞留ノード１０ｄに向かう乗換アーク２０ｅ、及び、滞留ノード１０ｄから発ノード１０ｂに向かう乗車アーク２０ｆ、を追加する。
【００４０】
また、滞留ノード１０ｄと同一駅の同一ホームにおける直前の滞留ノード１０ｅ、及び、次の滞留ノード１０ｆを特定する。そして、滞留ノード１０ｅから滞留ノード１０ｆに向かう滞留アーク２０ｇを削除し、滞留ノード１０ｅから滞留ノード１０ｄに向かう滞留アーク２０ｈ、滞留ノード１０ｄから滞留ノード１０ｆに向かう滞留アーク２０ｉを追加する。
【００４１】
また、滞留ノード１０ｆを終端とする異ホーム乗換アーク２０ｊについて、この異ホーム乗換アーク２０ｊの始端の着ノード１０ｇから滞留ノード１０ｄへ向かう異ホーム乗換アークの設定が可能ならば、この異ホーム乗換アーク２０ｊの終端を滞留ノード１０ｄに変更する（すなわち、乗換アーク２０ｊを削除し、着ノード１０ｇから滞留ノード１０ｄへ向かう乗換アーク２０ｋを追加する）。
【００４２】
（３−２）ノードの削除
ノードの削除は、列車の運休や、停車駅の通過といった列車ダイヤの修正に伴ってなされる。
【００４３】
図５は、ノードの削除の一例を示す図である。図５の（１）は、修正前のダイヤネットワークの一例である。Ｂ駅を対象とし、１，３，４列車が順に１番線ホームに着発し、２列車が２番線ホームに着発する列車ダイヤを表現したダイヤネットワークを示している。このような列車ダイヤに対して、“３列車を削除する”修正がなされた場合、図５の（２）のようなダイヤネットワークの修正がなされる。
【００４４】
すなわち、図５の（２）に示すように、３列車の着ノード１０ａ、滞留ノード１０ｂ、及び、発ノード１０ｃを削除する。次いで、このノード１０ａ〜１０ｃの削除に応じたアークの修正を行う。すなわち、着ノード１０ａを始端とする停車アーク２０ａ、及び、乗換アーク２０ｂ，２０ｃ、滞留ノード１０ｂを始端とする乗車アーク２０ｄ、及び、滞留アーク２０ｅ、を削除する。
【００４５】
また、削除した滞留ノード１０ｂを終端とする滞留アーク２０ｆの終端を、削除した滞留ノード１０ｂの次の滞留ノード１０ｅに変更する（すなわち、滞留アーク２０ｆを削除し、滞留ノード１０ｄから滞留ノード１０ｅへ向かう滞留アーク２０ｇを追加する）。また、削除した滞留ノード１０ｂを終端とする異ホーム乗換アーク２０ｈについて、この異ホーム乗換アーク２０ｈの終端を、削除した滞留ノード１０ｂの次の滞留ノード１０ｅに変更する（すなわち、乗換アーク２０ｈを削除し、着ノード１０ｆから滞留ノード１０ｅへ向かう乗換アーク２０ｉを追加する）。
【００４６】
（３−３）着ノードの変更
着ノードの変更は、着時刻の変更といった列車ダイヤの修正に伴ってなされる。
【００４７】
図６は、着ノードの変更の一例を示す図である。図６の（１）は、修正前のダイヤネットワークの一例を示している。Ｂ駅を対象とし、２列車が１番線ホームに着発する列車ダイヤを表現したダイヤネットワークを示している。このような列車ダイヤに対して、“Ｂ駅における２列車の着時刻を変更する”修正がなされた場合、図６の（２）のようなダイヤネットワークの修正がなされる。
【００４８】
すなわち、図６の（２）に示すように、２列車のＢ駅の着ノード１０ａの基準時刻ｔ１を時刻ｔ１’（図６では、ｔ１’＞ｔ１）に変更する。次いで、この着ノード１０ａの変更に応じたアークの修正を行う。すなわち、着ノード１０ａを終端とする列車アーク２０ａ、着ノード１０ａを始端とする乗換アーク２０ｂ、及び、停車アーク２０ｃのコストを変更する。
【００４９】
また、修正後の着ノード１０ａから異ホーム乗換アークを設定可能な異ホームの次の滞留ノード１０ｅを特定し、この特定した滞留ノード１０ｅが、修正前に設定されている着ノード１０ａを始端とする異ホーム乗換アーク２０ｅの終端の滞留ノード１０ｄと異なるならば、異ホーム乗換アーク２０ｅの終端を、特定した滞留ノード１０ｅに変更する（すなわち、乗換アーク２０ｅを削除し、着ノード１０ａから滞留ノード１０ｅへ向かう乗換アーク２０ｆを追加する）。
【００５０】
（３−４）発ノードの変更
発ノードの変更は、発時刻の変更といった列車ダイヤの修正に伴ってなされる。
【００５１】
図７〜図１０は、発ノードの変更の一例を示す図である。図７は、修正前のダイヤネットワークの一例である。Ｂ駅を対象とし、１列車が１番線ホームに着発する列車ダイヤを表現したダイヤネットワークを示している。このような列車ダイヤに対して、“Ｂ駅における１列車の発時刻を変更する”修正がなされた場合、図８〜図１０のようなダイヤネットワークの修正がなされる。
【００５２】
すなわち、図８の（１）に示すように、１列車のＢ駅の発ノード１０ｃの基準時刻ｔ３を時刻ｔ３’（図８では、ｔ３’＞ｔ３）に変更する。次いでこの発ノード１０ｃの変更に応じたアークの修正を行う。すなわち、発ノード１０ｃを終端とする停車アーク２０ａ、及び、発ノード１０ｃを始端とする列車アーク２０ｂのコストを変更する。
【００５３】
次いで、図８の（２）に示すように、発ノード１０ｃの変更に応じて、対応する滞留ノード１０ｂの基準時刻ｔ２を時刻ｔ２’に変更する。次いで、この滞留ノード１０ｂの変更に応じたアークの修正を行う。すなわち、滞留ノード１０ｂを終端とする同一ホーム乗換アーク２０ｃ、及び、滞留ノード１０ｂを終端とする異ホーム乗換アーク２０ｅのコストを変更する。
【００５４】
また、図９の（３）に示すように、滞留ノード１０ｂを終端とする異ホーム乗換アーク２０ｅの始端の着ノード１０ｅから異ホーム乗換アークを設定可能な異ホームの次の滞留ノード１０ｄを特定し、この特定した滞留ノード１０ｄが滞留ノード１０ｂと異なるならば、特定した異ホーム乗換アーク２０ｅの終端を、特定した滞留ノード１０ｄに変更する（すなわち、乗換アーク２０ｅを削除し、着ノード１０ｅから滞留ノード１０ｄへ向かう乗換アーク２０ｆを追加する）。
【００５５】
また、図９の（４）に示すように、滞留ノード１０ｂの次の滞留ノード１０ｇを終端とする異ホーム乗換アーク２０ｇを特定し、この異ホーム乗換アーク２０ｇの始端の着ノード１０ｆから滞留ノード１０ｂへの異ホーム乗換アークの設定が可能ならば、この異ホーム乗換アーク２０ｇの終端を滞留ノード１０ｂに変更する（すなわち、乗換アーク２０ｇを削除し、着ノード１０ｆから滞留ノード１０ｂへ向かう乗換アーク２０ｈを追加する）。
【００５６】
また、図１０の（５）に示すように、滞留ノード１０ｂを始端とする滞留アーク２０ｉを削除し、滞留ノード１０ｂを終端とする滞留アーク２０ｊの終端ノードを、この削除した滞留アーク２０ｉの終端ノードである滞留ノード１０ｉに変更する（すなわち、滞留アーク２０ｊを削除し、滞留ノード１０ｈから滞留ノード１０ｉへ向かう滞留アーク２０ｋを追加する）。
【００５７】
また、滞留ノード１０ｂの直前の滞留ノード１０ｉを始端ノードとする滞留アーク２０ｌの終端ノードを、滞留ノード１０ｂに変更する（すなわち、滞留アーク２０ｌを削除し、滞留ノード１０ｉから滞留ノード１０ｂへ向かう滞留アーク２０ｍを追加する）。そして、滞留ノード１０ｂを始端とし、滞留ノード１０ｂの次の滞留ノード１０ｊを終端とする滞留アーク２０ｎを追加する。
【００５８】
（４）要チェックノードの抽出
このようなダイヤネットワークに対する修正内容をもとに、最適移動経路が変化した可能性のあるノードを、要チェックノードリストとして抽出する。具体的には、１）追加、或いは、基準時刻の変更といった修正されたノード、２）修正されたノードを終端とするアークの始端ノード、３）追加、終端ノードの変更、或いは、コストの変更といった修正されたアークの始端ノード、を要チェックノードとして抽出する。
【００５９】
例えば、図４の（１）においては、ノード１０ａ，１０ｂが要チェックノードとなる。また、図４の（２）においては、ノード１０ｄ，１０ｅ，１０ｇが要チェックノードとなる。また、図５の（２）においては、ノード１０ｄ，１０ｆが要チェックノードとなる。また、図６の（２）においては、ノード１０ａが要チェックノードとなる。また、図８の（１），（２）においては、ノード１０ａ〜１０ｃが、図９の（３）においては、ノード１０ｅが，図９の（４）においては、ノード１０ｆが、図１０の（５）においては、ノード１０ｂ，１０ｈ，１０ｉが、それぞれ要チェックノードとなる。
【００６０】
（５）最適移動経路の再算出
要チェックノードとして抽出したノードそれぞれについて、最適移動経路の再算出を行う。このとき、基準時刻が遅い順に対象ノードｕとして、目的ノードｓそれぞれへの最適移動経路の再算出を行う。
【００６１】
図１１は、最適移動経路の再算出を説明する図である。再算出前の状態において、修正前のダイヤネットワークにおける対象ノードｕから目的ノードｓに至る最適移動経路として、次ノードｖ１、及び、最小コストＣｕｓが定められている。
【００６２】
最適移動経路の再算出においては、先ず、修正後のダイヤネットワークにおいて、対象ノードｕを始端とするアークの終端ノードｖｎ（ｎ＝１，２，…）のうちから、修正前の最適移動経路である次ノードｖ１以外のノードｖｎを経由して目的ノードｓに至る経路のコストＣｕｓｎが最小となるノードｖ２を選択する。このとき、ノードｕからノードｖ１へ向かうアークのコストＣｕｖ１を算出し、ノードｕからノードｖ２へ向かうアークのコストＣｕｖ２を算出する。
【００６３】
また、対象ノードｕより遅いノードであるノードｖ１から目的ノードｓに至る最適移動経路の情報は既知であり、最小コストＣｖｓ１が定められ、ノードｖ２から目的ノードｓに至る最適移動経路の情報も既知であり、最小コストＣｖｓ２が定められている。
【００６４】
つまり、対象ノードｕからノードｖ１を経由して目的ノードｓへ至る経路のコストＣｕｓ１は、Ｃｕｓ１＝Ｃｕｖ１＋Ｃｖ１ｓ、となり、対象ノードｕから、ノードｖ２を経由して、目的ノードｓへ至る経路のコストＣｕｓ２は、Ｃｕｓ２＝Ｃｕｖ２＋Ｃｖ２ｓ、となる。
【００６５】
そして、次の更新条件（ａ）〜（ｄ）の何れの条件を満たすかによって、対象ノードｕから目的ノードｓに至る最適移動経路を更新する。
【００６６】
（ａ）次ノード及び最小コストをともに更新
次の（ａ−１）〜（ａ−３）の何れかを満たす場合、最適移動経路の次ノードｖ１をノードｖ２に変更するとともに、最小コストＣｕｓを、ノードｖ２を経由する経路のコストＣｕｓ２に変更する。
（ａ−１）ノードｖ１が存在せず、ノードｖ２は存在する。
（ａ−２）対象ノードｓからノードｖ１へのアークｕｖ−１が存在せず、ノードｖ２は存在する。
（ａ−３）ノードｖ１，ｖ２、アークｕｖ−１がともに存在し、且つ、ノードｖ１を経由する移動経路のコストＣｕｓ１がノードｖ２を経由する移動経路のコストＣｕｓ２より大きい（Ｃｕｓ１＞Ｃｕｓ２）。
【００６７】
（ｂ）最小コストのみを更新
次の（ｂ−１），（ｂ−２）の何れかを満たす場合、最適移動経路の最小コストＣｕｓを、ノードｖ２を経由する経路のコストＣｕｓ２（＝Ｃｕｖ２＋Ｃｖｓ２）に変更する。
（ｂ−１）ノードｖ１、アークｕｖ−１は存在するが、ノードｖ２が存在せず、且つ、ノードｖ１を経由する移動経路のコストＣｕｓ１が最小コストＣｕｓに一致しない（Ｃｕｓ１≠Ｃｕｓ）。
（ｂ−２）ノードｖ１，ｖ２、アークｕｖ−１がともに存在するが、ノードｖ１を経由する移動経路のコストＣｕｓ１がノードｖ２を経由する移動経路のコストＣｕｓ２以下であり（Ｃｕｓ≦Ｃｕｓ２）、且つ、ノードｖ１を経由する移動経路のコストＣｕｓ１が最小コストＣｕｓに一致しない（Ｃｕｓ１≠Ｃｕｓ）。
【００６８】
（ｃ）最適移動経路を更新しない
上述の（ａ），（ｂ）の何れも満たさない場合には、最適移動経路の更新を行わない。
【００６９】
（ｄ）最適移動経路を削除
但し、（ｄ−１）ノードｖ１，ｖ２がともに存在しない場合、或いは、（ｄ−２）ノードｖ１は存在するが対象ノードｓからノードｖ１へ向かうアークｕｖ−１が存在せず、ノードｖ２が存在しない場合には、出発ノードｕから目的ノードｓに至る経路が存在しないため、最適移動経路（次ノードｖ１、最小コストＣｕｓ）を削除する。なお、「ノードｖ１が存在しない」とは、対象ノードｕがダイヤネットワーク（列車ダイヤ）の修正によって追加されたノードである場合、或いは、ノードｖ１が削除された場合に相当する。
【００７０】
［構成］
図１２は、上述した原理を実現するための本実施形態の最適移動経路情報算出装置１の機能構成図である。最適移動経路情報算出装置１は、機能的には、操作部１１０と、表示部１２０と、通信部１３０と、処理部２００と、記憶部３００とを備えて構成されるコンピュータシステムである。
【００７１】
操作部１１０は、例えばキーボードやマウス、タッチパネル、各種スイッチ等で実現される入力装置であり、操作入力に応じた操作信号を処理部２００に出力する。
【００７２】
表示部１２０は、例えばＬＣＤ等で実現される表示装置であり、処理部２００からの表示信号に応じた表示を行う。
【００７３】
通信部１３０は、例えば無線通信モジュールやルータ、モデム、ＴＡ、有線用の通信ケーブルのジャックや制御回路等で実現される通信装置であり、外部機器との間でデータ通信を行う。
【００７４】
処理部２００は、例えばＣＰＵ等の演算装置であり、記憶部３００に記憶されたプログラムやデータ、操作部１１０からの操作信号等に基づいて、最適移動経路情報算出装置１を構成する各部への指示やデータ転送を行い、最適移動経路情報算出装置１の全体制御を行う。また、処理部２００は、ダイヤネットワーク作成部２１０と、最適移動経路情報作成部２２０と、ダイヤネットワーク修正部２３０と、要チェックノード抽出部２４０と、最適移動経路情報更新部２５０とを有し、最適移動経路算出プログラム３１０に従った最適移動経路算出処理（図１４参照）を実行する。
【００７５】
ダイヤネットワーク作成部２１０は、基本ダイヤデータ３２０として記憶されている列車ダイヤに基づくダイヤネットワーク（図１参照）を作成する。作成したダイヤネットワークは、基本ダイヤネットワークデータ３３０として記憶される。
【００７６】
ダイヤネットワーク修正部２３０は、列車ダイヤの修正に応じて、ダイヤネットワーク作成部２１０によって作成されたダイヤネットワークを修正する。修正後のダイヤネットワークは、修正ダイヤネットワークデータ３６０として記憶される。
【００７７】
最適移動経路情報作成部２２０は、ダイヤネットワーク作成部２１０によって作成されたダイヤネットワークにおいて、各ノードについての最適移動経路を算出する。算出された最適移動経路は、最適移動経路情報３４０として記憶される。
【００７８】
図１３は、最適移動経路情報３４０のデータ構成の一例を示す図である。最適移動経路情報３４０は、ダイヤネットワークを構成する全てのノードである対象ノード３４１と、この対象ノードから到達可能な全ての駅の着ノードである目的ノード３４２それぞれとの組み合わせ毎に、最適移動経路３４３である次ノード及び最小コストを対応付けて格納している。
【００７９】
要チェックノード抽出部２４０は、ダイヤネットワーク修正部２３０によるダイヤネットワークに対する修正内容をもとに、修正後のダイヤネットワークを構成するノードのうちから、要チェックノードを抽出する。具体的には、修正されたノード、修正されたノードを終端とするアークの始端ノード、修正されたアークの始端ノードを、要チェックノードとして抽出する。抽出された要チェックノードは、要チェックノードリスト３７０として記憶される。
【００８０】
最適移動経路情報更新部２５０は、要チェックノード抽出部２４０によって抽出された要チェックノードについて最適移動経路の再算出を行って、最適移動経路情報３４０を更新する。すなわち、要チェックノードリスト３７０に記憶されている要チェックノードのうち、その基準時刻が遅い順に対象ノードｕとして、対象ノードｕから目的ノードｓそれぞれに至る最適移動経路の再算出を行う。そして、最適移動経路の最小コストを変更した場合には、修正後のダイヤネットワークにおいて、当該対象ノードｕを終端とする全てのアークそれぞれの始端ノードを、新たな要チェックノードとして要チェックノードリスト３７０に追加する。
【００８１】
記憶部３００は、例えばハードディスクやＲＯＭ、ＲＡＭ等の記憶装置で実現され、処理部２００が最適移動経路情報算出装置１を統合的に制御するためのシステムプログラムやデータ等を記憶しているとともに、処理部２００の作業領域として用いられ、処理部２００が各種プログラムに従って実行した演算結果や、操作部１１０からの操作信号等が一時的に格納される。本実施形態では、記憶部３００には、最適移動経路算出プログラム３１０と、基本ダイヤデータ３２０と、基本ダイヤネットワークデータ３３０と、最適移動経路情報３４０と、修正ダイヤデータ３５０と、修正ダイヤネットワークデータ３６０と、要チェックノードリスト３７０とが記憶される。
【００８２】
［処理の流れ］
図１４は、最適移動経路算出処理の流れを説明するフローチャートである。先ず、ダイヤネットワーク作成部２１０が、列車ダイヤに基づくダイヤネットワーク（基本ダイヤネットワークデータ３３０）を作成し、最適移動経路情報作成部２２０が、作成されたダイヤネットワークをもとに、最適移動経路情報３４０を作成する（ステップＡ１）。次いで、ダイヤネットワーク修正部２３０が、修正後の列車ダイヤ、修正内容にもとづいて、ダイヤネットワークを修正して修正ダイヤネットワークデータ３６０を作成する（ステップＡ３）。
【００８３】
続いて、要チェックノード抽出部２４０が、基本ダイヤネットワークデータ３３０と修正ダイヤネットワークデータ３６０とを対比して、ダイヤネットワークに対する修正内容に基づいて、修正ダイヤネットワークデータ３６０を構成するノードのうちから、要チェックノードを抽出して要チェックノードリスト３７０を作成する（ステップＡ５）。その後、最適移動経路情報更新部２５０が、最適移動経路情報更新処理（図１５参照）を行って、最適移動経路情報３４０を修正する（ステップＡ７）。
【００８４】
最適移動経路更新処理が終了すると、例えば外部からの終了指示が入力された等といったことで所定の終了条件を満たしたか否かを判断し、終了条件を満たしていないならば（ステップＡ９：ＮＯ）、ステップＡ３に戻り同様の処理を繰り返す。終了条件を満たしたならば（ステップＡ９：ＹＥＳ）、本処理を終了する。
【００８５】
図１５，図１６は、最適移動経路情報更新処理の流れを説明するフローチャートである。最適移動経路情報更新処理では、要チェックノードリスト３７０に記憶されている全ての要チェックノードについて、基準時刻が遅い順に対象ノードｕとした繰り返し処理（ループＡ）を行う。
【００８６】
ループＡでは、対象ノードｕから到達可能な各駅の着ノードそれぞれを目的ノードｓとした繰り返し処理（ループＢ）を行う。ループＢでは、先ず、対象ノードｕを始端とする全てのアークそれぞれの終端ノードｖｎのうちから、このノードｖｎを経由して目的ノードｓに至る経路のコストＣｕｓｎが最小となるノードｖｎを求めて次ノード候補ｖ＊とし、この次ノード候補ｖ＊を経由した経路の最小コストＣｕｓｎを最小コスト候補Ｃｕｓ＊とする（ステップＢ１）。
【００８７】
次いで、更新条件（ｄ）を満たすかを判断する。すなわち、修正後のダイヤネットワークにおいて、最適移動経路である次ノードｖ、及び、対象ノードｕから次ノードｖに向かうアークｕｖの少なくとも一方が存在せず（ステップＢ３：ＹＥＳ）、且つ、次ノード候補ｖ＊が存在しないならば（ステップＢ５：ＹＥＳ）、更新条件（ｄ）を満たすと判断し、対象ノードｕから目的ノードｓへ至る最適移動経路情報を削除（無し）とする（ステップＢ７）。
【００８８】
更新条件（ｄ）を満たさないならば（ステップＢ３：ＮＯ，ステップＢ５：ＮＯ）、続いて、更新条件（ａ）を満たすかを判断する。すなわち、修正後のダイヤネットワークにおいて、最適移動経路である次ノードｖ、及び、アークｕｖの少なくとも一方が存在しないが（ステップＢ９：ＹＥＳ）、次ノード候補ｖ＊が存在するならば（ステップＢ１１：ＹＥＳ）、更新条件（ａ−１），（ａ−２）を満たすと判断する。
【００８９】
或いは、修正後のダイヤネットワークにおいて、最適移動経路である次ノードｖ、及び、アークｕｖの両方が存在し（ステップＢ９：ＮＯ）、次ノード候補ｖ＊が存在し（ステップＢ１３：ＹＥＳ）、更に、次ノードｖを経由した経路のコストＣｕｓ１（アークｕｖのコストＣｕｓと、ノードｖから目的ノードｓへの最適移動経路の最小コストＣｖｓとの和）が最小コスト候補Ｃｕｓ＊より大きいならば（ステップＢ１５：ＹＥＳ）、更新条件（ａ−３）を満たすと判断する。
【００９０】
更新条件（ａ）を満たすと判断したならば、最適移動経路情報における次ノードｖを次ノード候補ｖ＊に更新する（ステップＢ１７）。また、最適移動経路情報において、最小コストＣｕｓを最小コスト候補Ｃｕｓ＊に更新し（ステップＢ１９）、対象ノードｕを終端とする全てのアークそれぞれの始端ノードを、要チェックノードとして要チェックノードリスト３７０に追加する（ステップＢ２１）。
【００９１】
更新条件（ａ），（ｄ）の何れも満たさないならば（ステップＢ１１：ＮＯ，ステップＢ１３：ＮＯ，ステップＢ１５：ＮＯ）、続いて、更新条件（ｂ）を満たすかを判断する。すなわち、修正後のダイヤネットワークにおいて、最適移動経路情報である次ノードｖ、及び、アークｕｖの両方が存在するが（ステップＢ２３：ＹＥＳ）、次ノード候補ｖ＊が存在せず（ステップＢ２５：ＹＥＳ）、更に、次ノードＶを経由した経路のコストＣｕｓ１が最小コストＣｕｓに一致しないならば（ステップＢ２７：ＹＥＳ）、更新条件（ｂ−１）を満たすと判断する。
【００９２】
或いは、修正後のダイヤネットワークにおいて、最適移動経路情報である次ノードｖ、及び、アークｕｖの両方が存在するとともに（ステップＢ２３：ＹＥＳ）、次ノード候補ｖ＊が存在し（ステップＢ２５：ＮＯ）、ノードｖを経由する経路のコストＣｕｓ１が最小コスト候補Ｃｕｓ＊以下であり（ステップＢ２９：ＹＥＳ）、更に、コストＣｕｓ１が最小コストＣｕｓに一致しないならば（ステップＢ３１：ＹＥＳ）、更新条件（ｂ―２）を満たすと判断する。
【００９３】
更新条件（ｂ）を満たすと判断したならば、最適経路情報における最小コストＣｕｓをコストＣｕｓ１に更新し（ステップＢ３５）、対象ノードｕを終端とする全てのアークそれぞれの始端ノードを、要チェックノードとして要チェックノードリスト３７０に追加する（ステップＢ３７）。
【００９４】
また、上述の更新条件（ａ），（ｂ），（ｄ）の何れの条件も満たさないならば（ステップＢ２３：ＮＯ，ステップＢ２７：ＮＯ，ステップＢ２９：ＮＯ，ステップＢ３１：ＮＭＯ）、最適移動経路の更新を行わない（ステップＢ３９）。
【００９５】
ループＢの処理はこのように行われる。全ての目的ノードｓを対象としたループＢの処理が終了し、更に、全ての要チェックノードを対象としたループＡの処理が終了すると、最適移動経路情報更新処理を終了する。
【００９６】
［作用・効果］
このように、本実施形態によれば、修正後のダイヤネットワークにおいて、修正されたノード、この修正されたノードを終端とする各アークの始端ノード、及び、修正されたアークの始端ノードが要チェックノードとして抽出され、これらの要チェックノードについて、その基準時刻が遅い順に、目的ノードｖまでの最適移動経路が更新される。つまり、ダイヤネットワークを構成する全てのノードを対象として最適移動経路の再算出を行うのではなく、修正によって最適移動経路が変化した可能性の有る一部の範囲についてのみ、最適移動経路の更新を行う。これにより、最適移動経路の算出に要する演算量を削減することが可能となる。
【００９７】
［変形例］
なお、本発明の適用可能な実施形態は上述の実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲で適宜変更可能なのは勿論である。
【００９８】
（Ａ）コストの設定
上述の実施形態では、アーク２０のコストを、その始端ノードと終端ノードｔの基準時刻の差に応じて設定することとしたが、任意に設定可能である。例えば、列車アークのコストとして、運用される列車編成の長さ（編成車両数）に応じて、上述のコストを増減或いは加算するとしても良い。また、各列車の乗車人数が分かるのであれば、その乗車人数に応じて列車アークのコストを増減させることとしてもよい。列車編成の長さや乗車人数は、コストを決定するための係数とも言える。
【００９９】
以上、列車ダイヤに関する発明として、特許請求の範囲や、明細書の［発明が解決しようとする課題］欄及び［発明を実施するための形態］欄等を記述した。これは、特許請求の範囲を明確且つ簡潔に記載すること（特許法第３６条第６項第２号、第３号）、発明の詳細な説明をその発明を実施できる程度に明確かつ十分に記載すること（特許法第３６条第４項）、という要件を満たすためである。しかし、いわゆる均等論が本発明について適用されることは勿論である。すなわち、本発明は列車ダイヤ以外へも適用可能である。例えば、路線バスの他、船舶や航空機の航路などに代表される、列車ダイヤと同様の特性をもつネットワークにも適用可能である。これらのネットワークが本発明と均等の範囲であることは当業者にとって明らかである。
【符号の説明】
【０１００】
１０  ノード、２０  アーク
１  最適移動経路情報算出装置
１１０  操作部、１２０  表示部、１３０  通信部
２００  処理部
２１０  ダイヤネットワーク作成部、２２０  最適移動経路情報作成部
２３０  ダイヤネットワーク修正部、２４０  要チェックノード抽出部
２５０  最適移動経路情報更新部
３００  記憶部
３１０  最適移動経路算出プログラム
３２０  基本ダイヤデータ、３３０  基本ダイヤネットワークデータ
３４０  最適移動経路情報、３５０  修正ダイヤデータ
３６０  修正ダイヤネットワークデータ、３７０  要チェックノードリスト
【図１】
2014144724.tif 000003
【図２】
2014144724.tif 000004
【図３】
2014144724.tif 000005
【図４】
2014144724.tif 000006
【図５】
2014144724.tif 000007
【図６】
2014144724.tif 000008
【図７】
2014144724.tif 000009
【図８】
2014144724.tif 000010
【図９】
2014144724.tif 000011
【図１０】
2014144724.tif 000012
【図１１】
2014144724.tif 000013
【図１２】
2014144724.tif 000014
【図１３】
2014144724.tif 000015
【図１４】
2014144724.tif 000016
【図１５】
2014144724.tif 000017
【図１６】
2014144724.tif 000018