(57)【要約】【課題】特急列車等の運行を取りやめることなく、列車全体に対して最適な復旧ダイヤを自動的に作成することができる列車ダイヤ作成装置を提供する。【解決手段】演算手段１６ｃは、第一抽出手段１６ａによって抽出された追い越し可能な列車の組の集合の各要素について第二抽出手段１６ｂによって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅を表すための整数変数を導入すると共に、復旧ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入する。そして、演算手段１６ｃは、整数変数及び実数変数に対して所定の複数の制約条件を課して、複数の制約条件の下で所定の評価指標が最大又は最小となるような整数変数及び実数変数を求めることにより、復旧ダイヤを決定する。【選択図】図１
2007106145.tif 000002
【特許請求の範囲】
【請求項１】
列車ダイヤに乱れが生じた場合における列車の運行に適用される復旧ダイヤを作成する列車ダイヤ作成装置であって、
各列車について列車種別、停車駅、各駅への到着予定時刻、各駅からの発車予定時刻を含む列車情報と各駅について列車の追い越しが物理的に可能であるかどうかを示す情報を含む駅情報とを記憶する記憶手段と、
現在運行している各列車についての運行状況情報を受信する受信手段と、
前記記憶手段に記憶されている前記列車情報及び前記駅情報と前記受信手段で受信した前記運行状況情報とに基づいて、復旧ダイヤの作成対象となる列車の中から時間的な追い越し可能条件に合致する列車の組を抽出する第一抽出手段と、
前記記憶手段に記憶されている前記列車情報及び前記駅情報に基づいて、前記第一抽出手段によって抽出された列車の組の集合の各要素について、当該列車の組が共有する追い越し可能な駅を抽出する第二抽出手段と、
前記第二抽出手段によって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅を表すための整数変数を導入すると共に、復旧ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入し、前記整数変数及び前記実数変数に対して所定の制約条件を課して、前記制約条件の下で所定の評価指標が最大又は最小となるような前記整数変数及び前記実数変数を求めることにより、前記第一抽出手段によって抽出された列車の各組について追い越し駅を決定する演算手段と、
を具備することを特徴とする列車ダイヤ作成装置。
【請求項２】
前記評価指標としては、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものを用いたことを特徴とする請求項１記載の列車ダイヤ作成装置。
【請求項３】
前記評価指標としては、列車の通る各駅における発車予定時刻からの遅延時間の総和を各列車について加算したものを用いたことを特徴とする請求項１記載の列車ダイヤ作成装置。
【請求項４】
改正列車ダイヤを作成する列車ダイヤ作成装置であって、
改正前の各列車について列車種別、停車駅、各駅への到着予定時刻、各駅からの発車予定時刻を含む改正前列車情報と各駅について列車の追い越しが物理的に可能であるかどうかを示す情報を含む駅情報とを記憶する第一記憶手段と、
改正後に追加、変更又は削除される各列車についての改正列車情報を記憶する第二記憶手段と、
前記第一記憶手段に記憶されている前記改正前列車情報及び前記駅情報と前記第二記憶手段に記憶されている前記改正列車情報とに基づいて、改正列車ダイヤの作成対象となる列車の中から時間的な追い越し可能条件に合致する列車の組を抽出する第一抽出手段と、
前記第一記憶手段に記憶されている前記改正前列車情報及び前記駅情報と前記第二記憶手段に記憶されている前記改正列車情報とに基づいて、前記第一抽出手段によって抽出された列車の組の集合の各要素について、当該列車の組が共有する追い越し可能な駅を抽出する第二抽出手段と、
前記第二抽出手段によって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅を表すための整数変数を導入すると共に、改正列車ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入し、前記整数変数及び前記実数変数に対して所定の制約条件を課して、前記制約条件の下で所定の評価指標が最大又は最小となるような前記整数変数及び前記実数変数を求めることにより、前記第一抽出手段によって抽出された列車の各組について追い越し駅を決定する演算手段と、
を具備することを特徴とする列車ダイヤ作成装置。
【請求項５】
列車ダイヤに対して一部の列車の追加、変更又は削除を施して得られる修正ダイヤを作成する列車ダイヤ作成装置であって、
各列車について列車種別、停車駅、各駅への到着予定時刻、各駅からの発車予定時刻を含む列車情報と各駅について列車の追い越しが物理的に可能であるかどうかを示す情報を含む駅情報とを記憶する第一記憶手段と、
追加、変更又は削除される各列車についての修正列車情報を記憶する第二記憶手段と、
前記第一記憶手段に記憶されている前記列車情報及び前記駅情報と前記第二記憶手段に記憶されている前記修正列車情報とに基づいて、修正ダイヤの作成対象となる列車の中から時間的な追い越し可能条件に合致する列車の組を抽出する第一抽出手段と、
前記第一記憶手段に記憶されている前記列車情報及び前記駅情報と前記第二記憶手段に記憶されている前記修正列車情報とに基づいて、前記第一抽出手段によって抽出された列車の組の集合の各要素について、当該列車の組が共有する追い越し可能な駅を抽出する第二抽出手段と、
列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものが最小となるように、前記第一抽出手段によって抽出された列車の各組について、前記第二抽出手段によって抽出された追い越し可能な駅の中から追い越し駅を決定する演算手段と、
を具備することを特徴とする列車ダイヤ作成装置。
【請求項６】
請求項１、２、３、４又は５のいずれかに記載の列車ダイヤ作成装置の機能をコンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項７】
請求項１、２、３、４又は５のいずれかに記載の列車ダイヤ作成装置の機能をコンピュータに実現させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、事故や故障等により列車ダイヤに乱れが生じた場合における列車の運行に適用される緊急時の列車ダイヤ（復旧ダイヤ）や、既存の列車ダイヤの一部に追加・修正等を施して得られる改正列車ダイヤ等の修正ダイヤを作成する列車ダイヤ作成装置に関するものである。
【背景技術】
【０００２】
従来、列車ダイヤの作成は人による手作業で行われていた。すなわち、列車ダイヤ作成担当者は、自己の知識と経験により試行錯誤を繰り返して、列車ダイヤを作成していた。しかし、手作業による列車ダイヤの作成には多大な労力と時間とが費やされるという問題があり、また、個人の経験と勘に頼って列車ダイヤを作成しているため、その作成される列車ダイヤは必ずしも満足のいく内容のものとはならないという問題があった。
【０００３】
近年、コンピュータを用いて列車ダイヤを自動的に作成することにより最適な列車ダイヤを求めるというアイデアが多数提案されている。一方、首都圏などでは乗客の増加により列車ダイヤが緻密化し、また、普通（各駅停車）、急行、特急など停車駅や速度の異なる複数種類の列車が同一路線を走行するなど、列車の運行形態が多様複雑化している。かかる列車種別の異なる列車同士が駅間で競合する場合には、列車ダイヤの作成に際して、一方の列車が待避して、他方の列車が当該一方の列車を追い越す駅を決める必要がある。このような列車の追い越しを含む列車ダイヤを自動作成する技術としては、追い越される列車と追い越す列車の相対的な優先度を設定し、優先度と待避駅間でそれら二つの列車の運行軌跡を表すスジが交差する位置の関係とに基づいて、待避駅を選択するという方法が提案されている（例えば、特許文献１参照。）。
【０００４】
【特許文献１】特開平４−２７８８７９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、事故や故障等の障害によって列車ダイヤに乱れが生じた場合などには、緊急時の列車ダイヤ（復旧ダイヤ）を早急に作成し、列車の運行をできるだけ早く平常時のダイヤに戻す必要がある。しかし、上記の先行技術は、平常時の列車ダイヤの作成を行うものであり、復旧ダイヤの作成には適していない。復旧ダイヤの作成については、未だに大半の作業を担当者の知識と経験に頼って手作業で行われているのが実状である。また、この復旧ダイヤの作成に際しては、しばしば特急や急行等の列車の運行を取りやめてしまうことがあるが、関係者からは、できれば特急や急行等の列車も運行したいという要求がある。
【０００６】
また、上記の先行技術を復旧ダイヤや改正列車ダイヤの作成に適用したとしても、次のような問題がある。すなわち、上記の先行技術では、二つの列車の組について、運行軌跡であるスジが交差する位置の関係のみに基づいて待避駅を決定している。このため、かかる待避駅の決定に際しては、当該二つの列車以外の他の列車との関係を考慮していないので、上記の先行技術を用いても、必ずしも列車全体に対して最適な列車ダイヤを作成することができるわけではない。
【０００７】
本発明は上記事情に基づいてなされたものであり、特急列車等の運行を取りやめることなく、列車全体に対して最適な復旧ダイヤを自動的に作成することができる列車ダイヤ作成装置を提供することを目的とするものである。
【０００８】
また、本発明は上記事情に基づいてなされたものであり、列車全体に対して最適な改正列車ダイヤ等の修正ダイヤを自動的に作成することができる列車ダイヤ作成装置を提供することを目的とするものである。
【課題を解決するための手段】
【０００９】
上記の目的を達成するための請求項１記載の発明は、列車ダイヤに乱れが生じた場合における列車の運行に適用される復旧ダイヤを作成する列車ダイヤ作成装置であって、各列車について列車種別、停車駅、各駅への到着予定時刻、各駅からの発車予定時刻を含む列車情報と各駅について列車の追い越しが物理的に可能であるかどうかを示す情報を含む駅情報とを記憶する記憶手段と、現在運行している各列車についての運行状況情報を受信する受信手段と、前記記憶手段に記憶されている前記列車情報及び前記駅情報と前記受信手段で受信した前記運行状況情報とに基づいて、復旧ダイヤの作成対象となる列車の中から時間的な追い越し可能条件に合致する列車の組を抽出する第一抽出手段と、前記記憶手段に記憶されている前記列車情報及び前記駅情報に基づいて、前記第一抽出手段によって抽出された列車の組の集合の各要素について、当該列車の組が共有する追い越し可能な駅を抽出する第二抽出手段と、前記第二抽出手段によって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅を表すための整数変数を導入すると共に、復旧ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入し、前記整数変数及び前記実数変数に対して所定の制約条件を課して、前記制約条件の下で所定の評価指標が最大又は最小となるような前記整数変数及び前記実数変数を求めることにより、前記第一抽出手段によって抽出された列車の各組について追い越し駅を決定する演算手段と、を具備することを特徴とするものである。
【００１０】
請求項２記載の発明は、請求項１記載の列車ダイヤ作成装置において、前記評価指標としては、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものを用いたことを特徴とするものである。
【００１１】
請求項３記載の発明は、請求項１記載の列車ダイヤ作成装置において、前記評価指標としては、列車の通る各駅における発車予定時刻からの遅延時間の総和を各列車について加算したものを用いたことを特徴とするものである。
【００１２】
上記の目的を達成するための請求項４記載の発明は、改正列車ダイヤを作成する列車ダイヤ作成装置であって、改正前の各列車について列車種別、停車駅、各駅への到着予定時刻、各駅からの発車予定時刻を含む改正前列車情報と各駅について列車の追い越しが物理的に可能であるかどうかを示す情報を含む駅情報とを記憶する第一記憶手段と、改正後に追加、変更又は削除される各列車についての改正列車情報を記憶する第二記憶手段と、前記第一記憶手段に記憶されている前記改正前列車情報及び前記駅情報と前記第二記憶手段に記憶されている前記改正列車情報とに基づいて、改正列車ダイヤの作成対象となる列車の中から時間的な追い越し可能条件に合致する列車の組を抽出する第一抽出手段と、前記第一記憶手段に記憶されている前記改正前列車情報及び前記駅情報と前記第二記憶手段に記憶されている前記改正列車情報とに基づいて、前記第一抽出手段によって抽出された列車の組の集合の各要素について、当該列車の組が共有する追い越し可能な駅を抽出する第二抽出手段と、前記第二抽出手段によって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅を表すための整数変数を導入すると共に、改正列車ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入し、前記整数変数及び前記実数変数に対して所定の制約条件を課して、前記制約条件の下で所定の評価指標が最大又は最小となるような前記整数変数及び前記実数変数を求めることにより、前記第一抽出手段によって抽出された列車の各組について追い越し駅を決定する演算手段と、を具備することを特徴とするものである。
【００１３】
上記の目的を達成するための請求項５記載の発明は、列車ダイヤに対して一部の列車の追加、変更又は削除を施して得られる修正ダイヤを作成する列車ダイヤ作成装置であって、各列車について列車種別、停車駅、各駅への到着予定時刻、各駅からの発車予定時刻を含む列車情報と各駅について列車の追い越しが物理的に可能であるかどうかを示す情報を含む駅情報とを記憶する第一記憶手段と、追加、変更又は削除される各列車についての修正列車情報を記憶する第二記憶手段と、前記第一記憶手段に記憶されている前記列車情報及び前記駅情報と前記第二記憶手段に記憶されている前記修正列車情報とに基づいて、修正ダイヤの作成対象となる列車の中から時間的な追い越し可能条件に合致する列車の組を抽出する第一抽出手段と、前記第一記憶手段に記憶されている前記列車情報及び前記駅情報と前記第二記憶手段に記憶されている前記修正列車情報とに基づいて、前記第一抽出手段によって抽出された列車の組の集合の各要素について、当該列車の組が共有する追い越し可能な駅を抽出する第二抽出手段と、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものが最小となるように、前記第一抽出手段によって抽出された列車の各組について、前記第二抽出手段によって抽出された追い越し可能な駅の中から追い越し駅を決定する演算手段と、を具備することを特徴とするものである。
【００１４】
上記の目的を達成するための請求項６記載の発明に係るコンピュータ読み取り可能な記録媒体は、請求項１、２、３、４又は５のいずれかに記載の列車ダイヤ作成装置の機能をコンピュータに実現させるためのプログラムを記録したものである。
【００１５】
上記の目的を達成するための請求項７記載の発明に係るプログラムは、請求項１、２、３、４又は５のいずれかに記載の列車ダイヤ作成装置の機能をコンピュータに実現させるためのものである。
【発明の効果】
【００１６】
請求項１記載の発明では、演算手段は、第一抽出手段によって抽出された列車の組の集合の各要素について第二抽出手段によって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅を表すための整数変数を導入すると共に、復旧ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入し、整数変数及び実数変数に対して所定の制約条件を課して、かかる制約条件の下で所定の評価指標が最大又は最小となるような整数変数及び実数変数を求めることにより、第一抽出手段によって抽出された列車の各組について追い越し駅を決定する。このため、第一抽出手段が特急や急行等の列車を含めて、追い越し可能な列車の組を抽出すると共に、演算手段が復旧ダイヤの作成対象となる列車に特急や急行等の列車を含めて、それらの列車についての実数変数を導入することによって、特急や急行等の列車をも含んだ復旧ダイヤを自動的に作成することができる。また、評価指標としては、例えば、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものや、列車の通る各駅における発車予定時刻からの遅延時間の総和を各列車について加算したものを用いることができる。このように、演算手段が、復旧ダイヤの作成対象となる列車の全体に関連する評価指標を用いることによって、それら列車全体に対して最適な復旧ダイヤを自動的に作成することができる。
【００１７】
同様に、請求項４記載の発明では、改正列車ダイヤの作成対象となる列車全体に対して最適な改正列車ダイヤを自動的に作成することができる。また、請求項５記載の発明では、列車全体に対して最適な修正ダイヤを自動的に作成することができる。
【発明を実施するための最良の形態】
【００１８】
以下に、図面を参照して、本願に係る発明を実施するための最良の形態について説明する。図１は本発明の一実施形態に係る列車ダイヤ作成装置の概略構成ブロック図である。
【００１９】
本実施形態の列車ダイヤ作成装置は、事故や故障等により列車ダイヤに乱れが生じた場合における列車の運行に適用される緊急時の列車ダイヤ（復旧ダイヤ）を作成するためのものである。一般に、列車には、普通（各駅停車）、急行、特急等の列車種別があり、これら列車種別の異なる列車が同一の路線を走行している。このとき、例えば、急行列車等は、先行している普通列車等を途中で追い越して、終着駅まで走行することがある。このため、列車ダイヤ（復旧ダイヤを含む。）の作成に際しては、かかる列車同士の追い越しが行われる場合を考慮する必要がある。以下では、特に、列車の線路が複線となっており、列車の追い越しは特定の駅で行われるものとする。
【００２０】
本実施形態の列車ダイヤ作成装置は、図１に示すように、入力装置１１と、表示装置１２と、通信部（受信手段）１３と、第一記憶部（記憶手段）１４と、第二記憶部１５と、制御部１６とを備える。
【００２１】
入力装置１１は、例えば、各種の命令やデータを入力するものである。この入力装置１１としては、キーボードやマウス等が用いられる。表示装置１２は、制御部１６によって作成された復旧ダイヤを表示するものである。また、通信部１３は、他のコンピュータやデータベース等から情報を受信したり、他のコンピュータやデータベース等に情報を送信したりするものである。具体的に、通信部１３は、現在運行している各列車についての運行状況情報を受信する。
【００２２】
第一記憶部１４は、平常時の列車ダイヤに関する情報（列車ダイヤ情報）を記憶するものである。列車ダイヤ情報は、列車情報と駅情報とからなる。列車情報には、各列車について「列車番号」、「列車種別」、「停車駅」、「各駅への到着予定時刻」、「各駅からの発車予定時刻」等が含まれている。
【００２３】
「列車番号」は当該列車に付与された識別情報である。「列車種別」は、当該列車が普通、急行、特急等のいずれの種別のものであるかを示すものである。鉄道会社によっては、これら以外に、準急、快速、快速急行等を列車種別に含ませていることがあるが、本実施形態では、列車種別として、普通、急行、特急の三種類のみを考えることにする。また、列車種別に関しては、等級が定められている。具体的には、特急の等級を「一」に、急行の等級を「二」に、そして、普通の等級を「三」に設定している。「一」の等級が一番高く、数字が大きくなるほど、等級は低くなる。この等級は、追い越し可能な列車を区別する役割を果たす。等級が高い列車種別の列車は、それよりも等級の低い列車種別の列車を追い越すことができる。すなわち、特急列車は特急列車を追い越すことはできないが、急行列車、普通列車を追い越すことができ、急行列車は特急列車、急行列車を追い越すことができないが、普通列車を追い越すことができる。そして、普通列車はいずれの列車も追い越すことができない。「停車駅」は当該列車が停車する駅を示すものである。また、「各駅への到着予定時刻」は当該列車が当該駅に到着する予定時刻であり、「各駅からの発車予定時刻」は当該列車が当該駅を発車する予定時刻である。ここで、当該列車が当該駅に停車する場合には、到着予定時刻と発車予定時刻とは一致せず、発車予定時刻は到着予定時刻よりも遅く設定されている。一方、当該列車が当該駅を通過する場合には、到着予定時刻と発車予定時刻とは一致する。この場合、この一致する時刻は、当該列車が当該駅を通過する通過予定時刻となる。
【００２４】
駅情報には、各駅について「駅番号」、「駅名」、「番線」等が含まれている。「駅番号」は当該駅に付与された識別情報である。「駅名」は当該駅の名称である。「番線」は、当該駅に設けられているプラットホームの数を示すものである。プラットホームの数に基づいて当該駅において構造上、物理的に列車の追い越しが可能であるかどうかを知ることができる。このため、かかる「番線」についての情報は、当該駅で列車の追い越しが物理的に可能であるかどうかを示す情報であるといえる。
【００２５】
第二記憶部１５は、現在運行している各列車についての運行状況情報を記憶するものである。この運行状況情報には、現在運行している各列車についての「列車番号」、「現在位置」、「遅延時間」等が含まれている。通常、鉄道会社には運転司令室が設けられており、運転司令室のコンピュータは、現在運行しているすべての列車の運行状況を管理している。第二記憶部１５に記憶されている運行状況情報は、運転司令室のコンピュータから送られたものである。具体的に、運転司令室のコンピュータには、現在運行している各列車から、何分遅れでどの駅を発車したというような運行状況情報が逐次送信されている。そして、運転司令室のコンピュータの画面上には、現在運行しているすべての列車から送られた運行状況情報がリアルタイムで表示され、管理者はその画面上に表示された運行状況情報を見て、各列車を監視している。また、運転司令室のコンピュータから本実施形態の列車ダイヤ作成装置へは、運行状況情報が送信される。通信部１３は、運転司令室のコンピュータから運行状況情報を受け取ると、その運行状況情報を第二記憶部１５に格納する。このように、本実施形態においては、かかる運転司令室のコンピュータは、現在運行している各列車についての運行状況情報を列車ダイヤ作成装置に通知する運行状況情報通知手段としての役割を果たしている。
【００２６】
制御部１６は、列車ダイヤ作成装置の各部を統括して制御するものである。この制御部１６は、図１に示すように、第一抽出手段１６ａと、第二抽出手段１６ｂと、演算手段１６ｃとを有する。これら第一抽出手段１６ａ、第二抽出手段１６ｂ及び演算手段１６ｃが、復旧ダイヤの作成に関する処理を行う。
【００２７】
第一抽出手段１６ａは、復旧ダイヤを作成する旨の指示を受けたときに、第一記憶部１４に記憶されている列車情報及び駅情報と第二記憶部１５に記憶されている運行状況情報とに基づいて、復旧ダイヤの作成対象となる列車の中から追い越し可能な列車の組（二つの列車）を抽出するものである。ここで、「追い越し可能な」とは、平常時の列車ダイヤに乱れが発生し、復旧ダイヤを作成する必要が生じた場合において、その復旧ダイヤにおける追い越しの可能性を指している。このため、「追い越し可能な列車の組」には、平常時の列車ダイヤにおいては追い越すことのない二つの列車も、第一抽出手段１６ａによって追い越し可能な列車の組として抽出されることがある。
【００２８】
具体的に、第一抽出手段１６ａは、次のような条件に従って、追い越し可能な列車の組を抽出する。すなわち、第一に、追い越し可能な列車の組として抽出される二つの列車の進行方向は同じでなければならない。第二に、追い越し可能な列車の組として抽出される二つの列車の列車種別は異なっていなければならない。本実施形態では、同じ種別の列車同士の間では追い越すことを想定していないからである。第三に、追い越し可能な列車の組として抽出される二つの列車は、少なくとも一つの同じ駅を通るものでなければならない。二つの列車について共有する駅がない場合には、追い越すことができないからである。第四に、追い越し可能な列車の組として抽出される二つの列車は、時間的に明らかに追い越すことができないものであってはならない。例えば、ある列車が始発駅を発車して１時間後に終着駅に到着する場合、当該列車がそれよりも例えば３時間前に始発駅を発車した列車を追い越すことは、当然考えられない。このような列車の組は予め抽出の対象から除外しておくことが望ましいからである。こうして第一抽出手段１６ａによって抽出された追い越し可能な列車の組は、集合Ｐを構成する。
【００２９】
第二抽出手段１６ｂは、第一記憶部１４に記憶されている列車情報及び駅情報に基づいて、第一抽出手段１６ａによって抽出された列車の組の集合Ｐの各要素について、当該列車の組が共有する追い越し可能な駅を抽出するものである。すなわち、第二抽出手段１６ｂは、列車情報に基づいて、第一抽出手段１６ａによって抽出された列車の組毎に、当該二つの列車の停車駅を調べ、当該二つの列車がともに通る共通の駅を特定する。その後、駅情報に基づいて、それら共通の駅の中で追い越し可能な駅を特定する。こうして特定された駅が、当該列車の組が共有する追い越し可能な駅である。列車の組の集合Ｐの各要素ｐについて、第二抽出手段１６ｂによって抽出された追い越し可能な駅は、集合Ｓ[p]を構成する。
【００３０】
また、第二抽出手段１６ｂは、当該列車の組について両方の列車が通る共通の駅であって最も遠い駅を、当該列車の組が共有する追い越し可能な駅の集合Ｓ[p]に含めることにしている。ここで、この最も遠い駅は、物理的に追い越し可能な駅であるかどうかにかかわらず、集合Ｓ[p]に含められる。後述するように、復旧ダイヤを作成する際には、第二抽出手段１６ｂによって抽出された追い越し可能な駅の中からいずれか一つの駅が選ばれ、その選ばれた駅において当該列車の組について追い越しが行われることになる。そして、上記の最も遠い駅が選ばれた場合には、結局、当該列車の組については追い越しが行われないということになる。すなわち、上記の最も遠い駅を、当該列車の組が共有する追い越し可能な駅の集合Ｓ[p]に含めておくことにより、復旧ダイヤの作成に際して、当該列車の組については、追い越しが行われるという選択の他に、追い越しが行われないという選択も起こり得ることを保障しているのである。
【００３１】
尚、列車の組が共有する追い越し可能な駅の集合Ｓ[p]には、それらの列車の始発駅をも含めるようにしてもよい。これにより、復旧ダイヤの作成に際して、当該列車の組については、始発駅でそれらの列車の発車順序を入れ替えるという選択も起こり得ることになる。
【００３２】
演算手段１６ｃは、第一抽出手段１６ａによって抽出された列車の組の集合の各要素について第二抽出手段１６ｂによって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅等を表すための整数変数を導入すると共に、復旧ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入し、そして、整数変数及び実数変数に対して所定の複数の制約条件を課して、それら複数の制約条件を混合整数計画問題として解くことにより、整数変数及び実数変数を求めて、復旧ダイヤを決定するものである。
【００３３】
上述したように、第一抽出手段１６ａは追い越し可能な列車の組の集合Ｐを生成し、第二抽出手段１６ｂは列車の組の集合Ｐの各要素ｐについて追い越し可能な駅の集合Ｓ[p]を生成する。演算手段１６ｃは、追い越し可能な駅の集合Ｓ[p]の各要素ｓに対して、整数変数として、追い越し駅変数ｘ[p][s]、追い越し後駅変数ａ[p][s]、追い越し前駅変数ｂ[p][s]という三種類の変数を導入する。各整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]の個数は、集合Ｐ、集合Ｓ[p]の要素の数により決まる。また、これら整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]は、０以上１以下であって且つ整数の値をとる変数である。すなわち、「０」と「１」の二つの値をとるバイナリ変数である。
【００３４】
図２は整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]を説明するための図である。図２には、二つの列車Train１，Train２についての運行軌跡と、Train１，Train２の列車の組についての整数変数を示す表とが示されている。ここで、運行軌跡を示すグラフの横軸には時間を、縦軸には駅番号（距離）をとっている。また、Train１は普通列車、Train２は急行列車であり、その運行軌跡によれば、Train１はＢ駅でTrain２に追い越される。図２では、Ｂ駅が追い越し可能な駅であることを示すため、Ｂ駅を丸で囲んでいる。このとき、Train１，Train２の列車の組についての整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]は図２の表のようになる。
【００３５】
追い越し駅変数ｘ[p][s]は、追い越し駅であることを表す整数変数である。すなわち、ｘ[p][s]＝１ということは、列車の組ｐについて駅ｓは追い越しが行われる駅であることを表し、ｘ[p][s]＝０ということは、列車の組ｐについて駅ｓは追い越しが行われる駅でないことを表す。図２の例では、Train１，Train２の列車の組については、Ｂ駅で追い越しが行われるので、ｓ＝Ｂのとき、ｘ[p][s]＝１であり、ｓ＝Ａ，Ｃ，Ｄのとき、ｘ[p][s]＝０である。このように、列車の組の各々については、当該二つの列車同士は一回しか追い越しを行わない。このため、かかる追い越し駅変数ｘ[p][s]には、
∀ｐ∈Ｐ：Σ（ｓ∈Ｓ[p]）ｘ[p][s]＝１
という制約がある。ここで、ｘ[p][s]についての和（Σ）は、追い越し可能な駅の集合Ｓ[p]のすべての要素ｓにわたってとられる。
【００３６】
追い越し後駅変数ａ[p][s]は、追い越し後の駅であることを表す整数変数である。すなわち、ａ[p][s]＝１ということは、列車の組ｐについて駅ｓは追い越しが行われた後の駅であることを表し、ａ[p][s]＝０ということは、列車の組ｐについて駅ｓは追い越しが行われた後の駅でないことを表す。図２の例では、Train１，Train２の列車の組については、Ｂ駅で追い越しが行われるので、ｓ＝Ｃ，Ｄのとき、ａ[p][s]＝１であり、ｓ＝Ａ，Ｂのとき、ａ[p][s]＝０である。また、かかる追い越し後駅変数ａ[p][s]については、ｓ１，ｓ２を隣接する追い越し可能な駅とし、ｓ１が前方の駅、ｓ２が後方の駅であるとすると、
∀ｐ∈Ｐ：ａ[p][s1]≦ａ[p][s2]
という制約がある。
【００３７】
追い越し前駅変数ｂ[p][s]は、追い越し前の駅であることを表す整数変数である。すなわち、ｂ[p][s]＝１ということは、列車の組ｐについて駅ｓは追い越しが行われる前の駅であることを表し、ｂ[p][s]＝０ということは、列車の組ｐについて駅ｓは追い越しが行われる前の駅でないことを表す。図２の例では、Train１，Train２の列車の組については、Ｂ駅で追い越しが行われるので、ｓ＝Ａのとき、ｂ[p][s]＝１であり、ｓ＝Ｂ，Ｃ，Ｄのとき、ｂ[p][s]＝０である。また、かかる追い越し前駅変数ｂ[p][s]については、ｓ１，ｓ２を隣接する追い越し可能な駅とし、ｓ１が前方の駅、ｓ２が後方の駅であるとすると、
∀ｐ∈Ｐ：ｂ[p][s1]≧ｂ[p][s2]
という制約がある。
【００３８】
また、追い越し駅変数ｘ[p][s]、追い越し後駅変数ａ[p][s]、追い越し前駅変数ｂ[p][s]の定義から分かるように、列車の組ｐについてそれぞれの駅ｓでは、常に、追い越し駅変数ｘ[p][s]、追い越し後駅変数ａ[p][s]、追い越し前駅変数ｂ[p][s]のうちいずれか一つの変数だけが１であり、他の二つの変数は０である。図２の例では、Train１，Train２の列車の組について、Ａ駅ではｂ[p][s]だけが１であり、Ｂ駅ではｘ[p][s]だけが１であり、Ｃ駅とＤ駅ではａ[p][s]だけが１である。すなわち、これらの三種類の整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]の間には、
∀ｐ∈Ｐ，∀ｓ∈Ｓ[p]：ｘ[p][s]＋ａ[p][s]＋ｂ[p][s]＝１
という制約がある。
【００３９】
このように、演算手段１６ｃが導入した整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]については、それらの整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]がその性質上満たさなければならない複数の制約条件がある。
【００４０】
また、演算手段１６ｃは、復旧ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入する。いま、列車ｔが駅ｓに到着する到着時刻をarrivalTime[t][s]とし、列車ｔが駅ｓを発車する発車時刻をdepartureTime[t][s]とする。駅ｓが列車ｔの停車駅である場合には、arrivalTime[t][s]＜departureTime[t][s]である。また、駅ｓが列車ｔの通過駅である場合には、arrivalTime[t][s]＝departureTime[t][s]であり、これは列車ｔが駅ｓを通過する通過時刻となる。
【００４１】
整数変数に対する複数の制約条件とは別に、実数変数に対しても複数の制約条件が課せられる。一般に、列車運行上、各列車について各駅における到着時刻及び発車時刻には、それらが満たさなければならない複数の制約がある。具体的には、時隔制約、早発禁止制約、基準運転時分制約、基準停車時分制約の各条件がある。復旧ダイヤを作成する際には、当然、これらの制約条件を考慮する必要がある。次に、これらの制約条件について説明する。
【００４２】
まず、時隔制約条件について説明する。以下の時隔制約条件の説明においては、追い越し可能な列車の組の集合Ｐの各要素ｐを構成する列車をｔ１，ｔ２とし、列車ｔ２が列車ｔ１を追い越す可能性があるものとする。この時隔制約条件は大きく五つに分けられる。第一の時隔制約条件は、追い越し可能な列車の組ｔ１，ｔ２について、追い越し前の駅ｓには、列車ｔ１が発車してから一定時間ｍが経過しないと、列車ｔ２が到着することができないというものである。図２の例では、楕円(1)で示す部分に第一の時隔制約条件が適用される。この第一の時隔制約条件は、
∀ｐ∈Ｐ、∀ｓ∈Ｓ[p]：arrivalTime[t2][s]−departureTime[t1][s]≧−Ｌ＋（Ｌ＋ｍ）×ｂ[p][s]
という式で表現することができる。ここで、ｍは時隔の最小値（定数）であり、Ｌは十分大きな正数である。追い越し前の駅ｓでは、ｂ[p][s]＝１であるので、上式の右辺はｍとなり、これは上述した第一の時隔制約条件の内容そのものを表す。これに対し、追い越す駅又は追い越し後の駅では、ｂ[p][s]＝０であるので、上式の右辺は−Ｌとなる。これは、列車ｔ２の到着時刻と列車ｔ１の発車時刻との差が十分小さな負の数よりも大きいという内容を表しているに過ぎず、当然に満たされる条件である。本実施形態では、整数変数ｂ[p][s]を用いて、第一の時隔制約条件をどの駅ｓに対しても適用できるような形で表現しているのである。これにより、混合整数計画問題を解く際に、時隔制約条件が取り扱いやすくなるというメリットがある。
【００４３】
第二の時隔制約条件は、追い越し可能な列車の組ｔ１，ｔ２について、追い越し駅ｓでは、列車ｔ１が到着してから一定時間ｍが経過しないと、列車ｔ２が到着することができないというものである。図２の例では、楕円(2)で示す部分に第二の時隔制約条件が適用される。この第二の時隔制約条件は、
∀ｐ∈Ｐ、∀ｓ∈Ｓ[p]：arrivalTime[t2][s]−arrivalTime[t1][s]≧−Ｌ＋（Ｌ＋ｍ）×ｘ[p][s]
という式で表現することができる。ここで、ｍは時隔の最小値（定数）であり、Ｌは十分大きな正数である。追い越し駅ｓでは、ｘ[p][s]＝１であるので、上式の右辺はｍとなり、これは上述した第二の時隔制約条件の内容そのものを表す。これに対し、追い越し前の駅又は追い越し後の駅では、ｘ[p][s]＝０であるので、上式の右辺は−Ｌとなる。これは、列車ｔ２の到着時刻と列車ｔ１の到着時刻との差が十分小さな負の数よりも大きいという内容を表しているに過ぎず、当然に満たされる条件である。この場合にも、整数変数ｘ[p][s]を用いて、第二の時隔制約条件をどの駅ｓに対しても適用できるような形で表現している。
【００４４】
第三の時隔制約条件は、追い越し可能な列車の組ｔ１，ｔ２について、追い越し駅ｓでは、列車ｔ２が発車してから一定時間ｍが経過しないと、列車ｔ１が発車することができないというものである。図２の例では、楕円(3)で示す部分に第三の時隔制約条件が適用される。この第三の時隔制約条件は、
∀ｐ∈Ｐ、∀ｓ∈Ｓ[p]：departureTime[t1][s]−departureTime[t2][s]≧−Ｌ＋（Ｌ＋ｍ）×ｘ[p][s]
という式で表現することができる。ここで、ｍは時隔の最小値（定数）であり、Ｌは十分大きな正数である。追い越し駅ｓでは、ｘ[p][s]＝１であるので、上式の右辺はｍとなり、これは上述した第三の時隔制約条件の内容そのものを表す。これに対し、追い越し前の駅又は追い越し後の駅では、ｘ[p][s]＝０であるので、上式の右辺は−Ｌとなる。これは、列車ｔ１の発車時刻と列車ｔ２の発車時刻との差が十分小さな負の数よりも大きいという内容を表しているに過ぎず、当然に満たされる条件である。この場合にも、整数変数ｘ[p][s]を用いて、第三の時隔制約条件をどの駅ｓに対しても適用できるような形で表現している。
【００４５】
第四の時隔制約条件は、追い越し可能な列車の組ｔ１，ｔ２について、追い越し後の駅ｓでは、列車ｔ２が発車してから一定時間ｍが経過しないと、列車ｔ１が到着することができないというものである。図２の例では、楕円(4)，(5)で示す部分に第四の時隔制約条件が適用される。この第四の時隔制約条件は、
∀ｐ∈Ｐ、∀ｓ∈Ｓ[p]：arrivalTime[t1][s]−departureTime[t2][s]≧−Ｌ＋（Ｌ＋ｍ）×ａ[p][s]
という式で表現することができる。ここで、ｍは時隔の最小値（定数）であり、Ｌは十分大きな正数である。追い越し後の駅ｓでは、ａ[p][s]＝１であるので、上式の右辺はｍとなり、これは上述した第四の時隔制約条件の内容そのものを表す。これに対し、追い越し前の駅又は追い越す駅では、ａ[p][s]＝０であるので、上式の右辺は−Ｌとなる。これは、列車ｔ１の到着時刻と列車ｔ２の発車時刻との差が十分小さな負の数よりも大きいという内容を表しているに過ぎず、当然に満たされる条件である。この場合にも、整数変数ａ[p][s]を用いて、第四の時隔制約条件をどの駅ｓに対しても適用できるような形で表現している。
【００４６】
上記の第一から第四までの時隔制約条件は、追い越し可能な列車の組に対して適用されるものであったが、第五の時隔制約条件は、追い越し可能な列車の組に含まれない二つの列車であって、各々の駅において連続して発車する二つの列車に対して適用される。この第五の時隔制約条件は、各々の駅ｓにおいて連続して発車する二つの列車をｔ３，ｔ４とし、列車ｔ３が列車ｔ４に先行しているとしたときに、駅ｓでは、列車ｔ３が発車してから一定時間ｍが経過しないと、列車ｔ４が到着することができないというものである。すなわち、それぞれの駅ｓにおいて、
arrivalTime[t4][s]−departureTime[t3][s]≧ｍ
が満たされなければならない。ここで、ｍは時隔の最小値（定数）である。
【００４７】
尚、上記の五つの時隔制約条件においては、時隔の最小値ｍをすべて同じ記号で示しているが、一般には、時隔の最小値ｍはそれぞれの時隔制約条件毎に異なってもよいし、駅毎に設備が違うことから駅毎に異なってもよい。また、ｍやＬに関するデータは所定の記憶部に記憶されている。
【００４８】
次に、早発禁止制約条件について説明する。早発禁止制約条件は、復旧ダイヤにおいて、列車は発車予定時刻より早く発車してはいけないというものである。列車ｔの駅ｓにおける発車予定時刻をplannedDepartureTime[t][s]とすると、早発禁止制約条件は、
departureTime[t][s]≧plannedDepartureTime[t][s]
と表現することができる。ここで、発車予定時刻とは、平常時の列車ダイヤにおける列車ｔの駅ｓにおける発車時刻のことであり、第一記憶部１４に記憶されている列車情報に含まれている。
【００４９】
次に、基準運転時分制約条件と基準停車時分制約条件について説明する。これらの条件は、各列車について基本的な運行条件を定めたものである。これらの条件が満たされないと、実現不可能なダイヤが作成されてしまうおそれがある。基準運転時分制約条件は、列車がある駅を出発してから次の駅に到着するまでの時間はある一定の値（基準運転時分）より小さく（早く）なってはいけないというものである。列車ｔの通る連続する二つの駅ｓ１，ｓ２（ｓ１は前方の駅、ｓ２は後方の駅）における基準運転時分をminRunningTime[t][s1][s2]とすると、基準運転時分制約条件は、
arrivalTime[t][s2]−departureTime[t][s1]≧minRunningTime[t][s1][s2]
と表現することができる。また、基準停車時分制約条件は、列車が駅に停車する時間はある一定の値（基準停車時分）を下回ってはいけないというものである。列車ｔの通る駅ｓにおける基準停車時分をminStoppingTime[t][s]とすると、基準停車時分制約条件は、
deartureTime[t][s]−arrivalTime[t][s]≧minStoppingTime[t][s]
と表現することができる。尚、基準運転時分minRunningTime及び基準停車時分minStoppingTimeに関するデータは、所定の記憶部に記憶されている。
【００５０】
演算手段１６ｃは、復旧ダイヤを作成する際に、上述した複数の制約条件（整数変数に対する制約条件、実数変数に対する制約条件）を混合整数計画問題として解くことになる。すなわち、複数の制約条件の下で所定の評価指標（目的関数）が最大又は最小となるような整数変数及び実数変数を求める。整数変数を求めれば、第一抽出手段によって抽出された列車の各組についての追い越し駅が決まることになる。実数変数は各列車についての各駅における到着時刻及び発車時刻であるので、実数変数を求めれば、復旧ダイヤが決まることになる。最近では、各種の線形問題用のソフトウェアが市販されている。このため、かかる線形問題用のソフトウェアを本装置にインストールしておくことにより、演算手段１６ｃは、かかる線形問題用ソフトウェアの機能を利用して、混合整数計画問題を解く演算処理を実行することができる。
【００５１】
また、本実施形態では、演算手段１６ｃは、評価指標（目的関数）として、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものを用いる。ここで、「遅延時間を各列車について加算したもの」（遅延時間の総和）とは、復旧ダイヤの作成対象となるすべての列車についての遅延時間を加え合わせたものである。このため、このような評価指標を用いて混合整数計画問題を解くことにより、列車ダイヤの乱れを最も早く回復させることができるような復旧ダイヤを作成することができる。
【００５２】
次に、本実施形態の列車ダイヤ作成装置において復旧ダイヤを作成する処理の手順を説明する。図３は本実施形態の列車ダイヤ作成装置において復旧ダイヤを作成する処理の手順を説明するためのフローチャートである。
【００５３】
復旧ダイヤの作成処理は、列車の運転をいつ再開するのかが決まった後に、その再開の予定時刻よりも一定時間前に行われる。これは、その再開予定時刻までに復旧ダイヤを作成するためである。
【００５４】
管理者が、入力装置１１を用いて、表示装置１２の画面上で所定のボタンを押すと、復旧ダイヤを作成する旨の指示が制御部１６に送られ、制御部１６は、図３に示す処理フローを開始する。まず、制御部１６の第一抽出手段１６ａは、第一記憶部１４に記憶されている列車情報及び駅情報と第二記憶部１５に記憶されている運行状況情報とに基づいて、復旧ダイヤの作成対象となる列車の中から追い越し可能な列車の組を抽出し、追い越し可能な列車の組の集合Ｐを生成する（Ｓ１１）。その後、第二抽出手段１６ｂは、第一記憶部１４に記憶されている列車情報及び駅情報に基づいて、その生成された追い越し可能な列車の組の集合Ｐの各要素ｐについて、当該列車の組が共有する追い越し可能な駅を抽出し、追い越し可能な駅の集合Ｓ[p]を生成する（Ｓ１２）。
【００５５】
次に、演算手段１６ｃは、集合Ｐの各要素ｐについて、集合Ｓ[p]の各要素ｓ毎に、整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]を導入する（Ｓ１３）。ここで、整数変数ｘ[p][s]は追い越し駅であることを表す追い越し駅変数、整数変数ａ[p][s]は追い越し後の駅であることを表す追い越し後駅変数、整数変数ｂ[p][s]は追い越し前の駅であることを表す追い越し前駅変数である。また、整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]はそれぞれ、０以上１以下であって且つ整数の値をとるバイナリ変数である。
【００５６】
その後、演算手段１６ｃは、整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]に対する各種の制約条件を生成する（Ｓ１４）。具体的には、まず、追い越し可能な列車の組の各々について、当該二つの列車同士が一回しか追い越しを行わないという制約条件、すなわち、
∀ｐ∈Ｐ：Σ（ｓ∈Ｓ[p]）ｘ[p][s]＝１
を生成する。次に、追い越し可能な列車の組の各々について、整数変数ａ[p][s]が追い越し可能な駅に関して単調且つ非減少であるという制約条件、すなわち、ｓ１，ｓ２を隣接する駅、ｓ１が前方の駅、ｓ２が後方の駅であるとしたときに、
∀ｐ∈Ｐ：ａ[p][s1]≦ａ[p][s2]
を生成する。同様に、追い越し可能な列車の組の各々について、整数変数ｂ[p][s]が追い越し可能な駅に関して単調且つ非増加であるという制約条件、すなわち、ｓ１，ｓ２を隣接する駅、ｓ１が前方の駅、ｓ２が後方の駅であるとしたときに、
∀ｐ∈Ｐ：ｂ[p][s1]≧ｂ[p][s2]
を生成する。また、列車の組ｐについてそれぞれの駅ｓでは、常に、追い越し駅変数ｘ[p][s]、追い越し後駅変数ａ[p][s]、追い越し前駅変数ｂ[p][s]のうちいずれか一つの変数だけが１であるという制約条件、すなわち、
∀ｐ∈Ｐ，∀ｓ∈Ｓ[p]：ｘ[p][s]＋ａ[p][s]＋ｂ[p][s]＝１
を生成する。
【００５７】
次に、演算手段１６ｃは、復旧ダイヤの作成対象となる各列車ｔについて各駅ｓにおける到着時刻arrivalTime[t][s]及び発車時刻departureTime[t][s]を実数変数として導入する（Ｓ１５）。そして、演算手段１６ｃは、実数変数に対する各種の制約条件を生成する（Ｓ１６）。具体的に、かかる制約条件としては、時隔制約条件と、早発禁止制約条件と、基準運転時分制約条件と、基準停車時分制約条件とがある。
【００５８】
次に、演算手段１６ｃは、評価指標（目的関数）を設定する（Ｓ１７）。ここでは、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものを評価指標とする。その後、演算手段１６ｃは、ステップＳ１４及びステップＳ１６で生成した複数の制約条件を混合整数計画問題として解く（Ｓ１８）。すなわち、複数の制約条件の下でステップＳ１７において設定した評価指標が最小となるような整数変数及び実数変数を求める。こうして問題を解いて得られた整数変数ｘ[p][s]は、各列車の組ｐについて、どこが追い越し駅であるかを示している。そして、問題を解いて得られた実数変数arrivalTime[t][s]，departureTime[t][s]は、各列車ｔについて各駅ｓにおける時刻情報であるので、演算手段１６ｃは、かかる実数変数arrivalTime[t][s]，departureTime[t][s]に基づいて復旧ダイヤを決定することができる。最後に、制御部１６は、その決定した復旧ダイヤを表示装置１２に表示すると共に、その復旧ダイヤを、通信部１３を介して所定の部署に設けられたコンピュータ等に送信する（Ｓ１９）。
【００５９】
次に、本実施形態の列車ダイヤ作成装置を用いて作成される復旧ダイヤの具体例を説明する。図４は平常時の列車ダイヤの一例を説明するための図、図５はその平常時の列車ダイヤにおける列車の追い越しを模式的に説明するための図、図６は列車に遅延が生じた場合にその平常時の列車ダイヤがどのように変更されるのかを説明するための図である。図７は本実施形態の列車ダイヤ作成装置を用いて作成された復旧ダイヤの一例を説明するための図、図８はその復旧ダイヤにおける列車の追い越しを模式的に説明するための図である。
【００６０】
図４、図６、図７の各グラフは各列車についての運行軌跡を示すものであり、横軸に時間を、縦軸に駅番号（距離）をとっている。図４〜図８では、三つの列車（Train１，Train２，Train３）のみが示されている。Train１とTrain２は普通列車であり、Train３は急行列車である。追い越し可能な列車の組は、Train１及びTrain３と、Train２及びTrain３とである。また、これら追い越し可能な列車の組のいずれにおいても、追い越し可能な駅は、図４〜図７において丸で囲まれたＢ，Ｃ，Ｅ，Ｆの各駅である。
【００６１】
図４に示す平常時の列車ダイヤでは、Train１，Train２，Train３がこの順序でＡ駅を発車する。そして、図４及び図５に示すように、Ａ駅を後から発車したTrain３は、まず、Ｃ駅でTrain２を追い越し、次に、Ｅ駅でTrain１を追い越す。
【００６２】
いま、Train１がＡ駅を発車した後、Ａ駅で事故等が発生し、Train２とTrain３がＡ駅を発車する時刻が大幅に遅れたとする。このとき、平常時の列車ダイヤにしたがって列車の運行を行うことにすると、図６に示すように、Train１は、Train３により追い越される駅であるＥ駅で、Train３が到着するのを長時間にわたって待たなければならない。これにより、Train２及びTrain３だけでなく、Train１についても遅延が生じてしまうことになる。
【００６３】
このような場合、本実施形態の列車ダイヤ作成装置を用いると、図７に示すような復旧ダイヤを作成することができる。すなわち、この復旧ダイヤによれば、図７及び図８に示すように、追い越し可能な列車の組（Train２，Train３）については、平常時の列車ダイヤでの追い越し駅Ｃよりも一つ手前の駅Ｂで列車の追い越しを行うことにすると共に、Train３がＡ駅を発車する時刻を図６の場合の発車時刻よりも早めている。これにより、Train３の遅延を抑えることができる。一方、追い越し可能な列車の組（Train１，Train３）については、平常時の列車ダイヤでの追い越し駅Ｅよりも一つ先の駅Ｆで列車の追い越しを行うことにする。これにより、Train１は駅ＥでTrain３を待たずに駅Ｆへ先に行くので、Train１がTrain３を待つ時間を短縮することができる。このため、かかる復旧ダイヤを用いることにより、Train１の遅延を抑えることができる。
【００６４】
本実施形態の列車ダイヤ作成装置では、演算手段は、第一抽出手段によって抽出された列車の組の集合の各要素について第二抽出手段によって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅を表すための整数変数を導入すると共に、復旧ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入し、整数変数及び実数変数に対して所定の複数の制約条件を課して、複数の制約条件の下で所定の評価指標が最大又は最小となるような整数変数及び実数変数を求めることにより、復旧ダイヤを決定する。このため、第一抽出手段が特急や急行等の列車を含めて、追い越し可能な列車の組を抽出すると共に、演算手段が復旧ダイヤの作成対象となる列車に特急や急行等の列車を含めて、それらの列車についての実数変数を導入することによって、特急や急行等の列車をも含んだ復旧ダイヤを自動的に作成することができる。また、演算手段が、評価指標として、例えば、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものを用いることによって、復旧ダイヤの作成対象となる列車全体に対して最適な復旧ダイヤを自動的に作成することができる。
【００６５】
尚、本発明は上記の実施形態に限定されるものではなく、その要旨の範囲内において種々の変形が可能である。
【００６６】
例えば、上記の実施形態では、運転司令室のコンピュータが運行状況情報を列車ダイヤ作成装置に通知する場合について説明したが、運行状況情報を所定のデータベースに蓄積しておき、列車ダイヤ作成装置が一定期間毎にそのデータベースにアクセスして運行状況情報を取得するようにしてもよい。
【００６７】
また、上記の実施形態では、追い越し可能な列車の組には、列車種別の同じ列車同士を含めない場合について説明したが、追い越し可能な列車の組に列車種別の同じ列車同士を含めるようにしてもよい。例えば、同じ列車種別であっても、終着駅の異なる列車同士については、遠い駅まで行く列車が、近い駅までしか行かない列車と途中の駅で待ち合わせて、その駅でその列車を追い越すという場合も考えられるからである。このように遠い駅まで行く列車を途中の駅で先に発車させることにより、遠い駅まで行く列車がさらに他の列車に追い越されるというようなケースを少なくして、全体の運行時間を短く抑えることが可能となる。尚、一般に、列車種別の同じ列車同士での追い越しを認めるかどうかは、その鉄道会社の方針にしたがって決められることになる。
【００６８】
また、上記の実施形態では、混合整数計画問題を解く際に使用する評価指標（目的関数）として、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものを用いた場合について説明したが、評価指標としてはさまざまなものを用いることができる。例えば、列車の通る各駅における発車予定時刻からの遅延時間の総和を各列車について加算したもの、列車の通る各駅における到着予定時刻からの遅延時間の総和を各列車について加算したもの、運転を再開してから列車が終着駅に到着するまでの時間を各列車について加算したもの等を用いることができる。また、評価指標としては、列車種別毎に異なる指標を定義し、その指標を各列車について加え合わせたものを用いてもよい。
【００６９】
更に、上記の実施形態において、線路が部分的に複々線化されており、その複々線化された駅間の区間で列車の追い越しが行うことができる場合には、その駅間の区間をも追い越し可能な駅の概念に含めるようにしてもよい。但し、この追い越し可能な区間では、追い越しを行う列車の組に対して時隔制約条件は課されない。
【００７０】
また、本発明の列車ダイヤ作成装置は、既存の列車ダイヤの一部に追加・修正等を施して得られる改正列車ダイヤ（臨時列車の列車ダイヤをも含む。）を作成する場合にも適用することができる。この場合には、上記の実施形態の列車ダイヤ作成装置における運行状況情報の代わりに、改正後に追加、変更又は削除される各列車についての改正列車情報が用いられる。このため、管理者は、入力装置を用いて、かかる改正列車情報を予め入力しておく必要がある。ここで、追加される列車についての改正列車情報には、例えば、当該列車の列車番号・列車種別・停車駅、当該列車が始発駅を発車する発車予定時刻等が含まれる。変更される列車についての改正列車情報には、例えば、当該列車の列車番号、変更に関する内容等が含まれる。また、削除される列車についての改正列車情報には、例えば、当該列車の列車番号等が含まれる。
【００７１】
具体的に、改正列車ダイヤを作成する列車ダイヤ作成装置は、改正前の各列車について列車種別、停車駅、各駅への到着予定時刻、各駅からの発車予定時刻を含む改正前列車情報と各駅について列車の追い越しが物理的に可能であるかどうかを示す情報を含む駅情報とを記憶する第一記憶手段と、改正後に追加、変更又は削除される各列車についての改正列車情報を記憶する第二記憶手段と、第一記憶手段に記憶されている改正前列車情報及び駅情報と第二記憶手段に記憶されている改正列車情報とに基づいて、改正列車ダイヤの作成対象となる列車の中から時間的な追い越し可能条件に合致する列車の組を抽出する第一抽出手段と、第一記憶手段に記憶されている改正前列車情報及び駅情報と第二記憶手段に記憶されている改正列車情報とに基づいて、第一抽出手段によって抽出された列車の組の集合の各要素について、当該列車の組が共有する追い越し可能な駅を抽出する第二抽出手段と、第二抽出手段によって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅を表すための整数変数を導入すると共に、改正列車ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入し、整数変数及び実数変数に対して所定の制約条件を課して、制約条件の下で所定の評価指標が最大又は最小となるような整数変数及び実数変数を求めることにより、第一抽出手段によって抽出された列車の各組について追い越し駅を決定する演算手段と、を具備するように構成される。このため、演算手段が、改正列車ダイヤの作成対象となる列車の全体に関連する評価指標を用いることによって、それら列車全体に対して最適な改正列車ダイヤを自動的に作成することができる。尚、この場合、評価指標としては、例えば、列車の走行時間を各列車について加算したものを用いることができる。そして、演算手段は、かかる評価指標が最小（最短）となるような整数変数及び実数変数を求めることになる。
【００７２】
更に、本発明の列車ダイヤ作成装置は、列車ダイヤに対して一部の列車の追加、変更又は削除を施して得られる修正ダイヤ（復旧ダイヤ、改正列車ダイヤを含む。）を作成する場合にも適用することができる。具体的に、かかる列車ダイヤ作成装置は、各列車について列車種別、停車駅、各駅への到着予定時刻、各駅からの発車予定時刻を含む列車情報と各駅について列車の追い越しが物理的に可能であるかどうかを示す情報を含む駅情報とを記憶する第一記憶手段と、追加、変更又は削除される各列車についての修正列車情報を記憶する第二記憶手段と、第一記憶手段に記憶されている列車情報及び駅情報と第二記憶手段に記憶されている修正列車情報とに基づいて、修正ダイヤの作成対象となる列車の中から時間的な追い越し可能条件に合致する列車の組を抽出する第一抽出手段と、第一記憶手段に記憶されている列車情報及び駅情報と第二記憶手段に記憶されている修正列車情報とに基づいて、第一抽出手段によって抽出された列車の組の集合の各要素について、当該列車の組が共有する追い越し可能な駅を抽出する第二抽出手段と、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものが最小となるように、第一抽出手段によって抽出された列車の各組について、第二抽出手段によって抽出された追い越し可能な駅の中から追い越し駅を決定する演算手段と、を具備するように構成される。このような列車ダイヤ作成装置を用いることにより、列車全体に対して最適な修正ダイヤを自動的に作成することができる。
【００７３】
本発明の目的は、上述した実施形態の装置の機能を実現するソフトウェアのプログラムコード（実行形式を含む）を、その全体あるいは一部を記録した記録媒体により、本実施形態の装置に供給し、その装置のコンピュータ（又はＣＰＵ、ＭＰＵ）が記録媒体に格納されたプログラムコードを読み出して、動作の全部あるいは一部を実行することによっても達成されることは言うまでもない。この場合、記録媒体から読み出されたプログラムコード自体が本実施形態の機能を実現することになり、そのプログラムコードを記録した記録媒体は本発明を構成することになる。
【００７４】
プログラムコードを供給するための記録媒体としては、ＲＯＭ、フロッピー（登録商標）ディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード等を用いることができる。さらに、通信回線を介してダウンロードすることによってプログラムコードを供給するようにしてもよいし、ＪＡＶＡ（登録商標）などの技術を利用してプログラムコードを供給して実行するようにしてもよい。
【００７５】
また、コンピュータが読み出したプログラムコードを実行することにより、本実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳなどが実際の処理の一部又は全部を行い、その処理によって本実施形態の機能が実現される場合も本発明に含まれることは言うまでもない。
【００７６】
更に、記録媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータが接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部又は全部を行い、その処理によって本実施形態の機能が実現される場合も本発明に含まれることは言うまでもない。
【００７７】
加えて、本発明はコンピュータに上記の実施形態の装置の機能を実現させるためのプログラムを含むプログラム・プロダクトであってもよい。ここで、プログラム・プロダクトというのは、コンピュータ・プログラムだけでなく、プログラムを記録した記録媒体あるいはコンピュータを含むものである。
【産業上の利用可能性】
【００７８】
以上説明したように、本発明の列車ダイヤ作成装置では、演算手段は、第一抽出手段によって抽出された列車の組の集合の各要素について第二抽出手段によって抽出された追い越し可能な駅の集合の各要素毎に、追い越し駅を表すための整数変数を導入すると共に、復旧ダイヤの作成対象となる各列車について各駅における到着時刻及び発車時刻を実数変数として導入し、整数変数及び実数変数に対して所定の制約条件を課して、かかる制約条件の下で所定の評価指標が最大又は最小となるような整数変数及び実数変数を求めることにより、第一抽出手段によって抽出された列車の各組について追い越し駅を決定する。このため、第一抽出手段が特急や急行等の列車を含めて、追い越し可能な列車の組を抽出すると共に、演算手段が復旧ダイヤの作成対象となる列車に特急や急行等の列車を含めて、それらの列車についての実数変数を導入することによって、特急や急行等の列車をも含んだ復旧ダイヤを自動的に作成することができる。また、評価指標としては、例えば、列車の終着駅における到着予定時刻からの遅延時間を各列車について加算したものや、列車の通る各駅における発車予定時刻からの遅延時間の総和を各列車について加算したものを用いることができる。このように、演算手段が、復旧ダイヤの作成対象となる列車の全体に関連する評価指標を用いることによって、それら列車全体に対して最適な復旧ダイヤを自動的に作成することができる。したがって、本発明は、特に、事故や故障等により列車ダイヤに乱れが生じた場合における列車の運行に適用される復旧ダイヤを作成する列車ダイヤ作成装置に適用することができる。
【図面の簡単な説明】
【００７９】
【図１】本発明の一実施形態に係る列車ダイヤ作成装置の概略構成ブロック図である。
【図２】整数変数ｘ[p][s]，ａ[p][s]，ｂ[p][s]を説明するための図である。
【図３】本実施形態の列車ダイヤ作成装置において復旧ダイヤを作成する処理の手順を説明するためのフローチャートである。
【図４】平常時の列車ダイヤの一例を説明するための図である。
【図５】その平常時の列車ダイヤにおける列車の追い越しを模式的に説明するための図である。
【図６】列車に遅延が生じた場合にその平常時の列車ダイヤがどのように変更されるのかを説明するための図である。
【図７】本実施形態の列車ダイヤ作成装置を用いて作成された復旧ダイヤの一例を説明するための図である。
【図８】その復旧ダイヤにおける列車の追い越しを模式的に説明するための図である。
【符号の説明】
【００８０】
１１  入力装置
１２  表示装置
１３  通信部
１４  第一記憶部
１５  第二記憶部
１６  制御部
１６ａ  第一抽出手段
１６ｂ  第二抽出手段
１６ｃ  演算手段
【図１】
2007106145.tif 000003
【図２】
2007106145.tif 000004
【図３】
2007106145.tif 000005
【図４】
2007106145.tif 000006
【図５】
2007106145.tif 000007
【図６】
2007106145.tif 000008
【図７】
2007106145.tif 000009
【図８】
2007106145.tif 000010