(57)【要約】      （修正有）【課題】遅延ロバスト性を有するダイヤを作成する情報処理装置を提供する。【解決手段】情情報処理装置であるダイヤ作成装置１００は、車両が停車位置から出発する時刻、車両が停車位置に到着する時刻及び車両が停車位置を通過する時刻のうちの少なくとも１つを含む第１〜第ｎ車両スジの第１ダイヤに基づき、時刻の調整量を算出するダイヤ処理部５００と、算出した調整量と、第１ダイヤに基づいて、第２ダイヤを作成する出力ダイヤ作成部３９０と、を備える。【選択図】図１
2020203549.tif 000002
【特許請求の範囲】
【請求項１】
車両が停車位置から出発する時刻、車両が停車位置に到着する時刻及び車両が停車位置を通過する時刻のうちの少なくとも１つを含む第１〜第ｎ車両スジの第１ダイヤに基づき、前記時刻の調整量を算出するダイヤ処理部と、
算出した前記調整量と、前記第１ダイヤに基づいて、第２ダイヤを作成する出力ダイヤ作成部と
を備えた情報処理装置。
【請求項２】
前記ダイヤ処理部は、前記第１〜第ｎ車両スジの配置間隔に関する制約条件に基づき、前記時刻の調整量を算出する
請求項１に記載の情報処理装置。
【請求項３】
前記制約条件は、第１の期間に第１の前記停車位置を出発する時刻、第１の前記停車位置に到着する時刻又は第１の前記停車位置を通過する時刻が含まれる車両スジの本数の条件を含む
請求項２に記載の情報処理装置。
【請求項４】
前記制約条件は、前記第１〜第ｎ車両の車両種別ごとに、前記本数及び第１の前記停車位置の少なくとも一方の条件を含む
請求項２又は３に記載の情報処理装置。
【請求項５】
前記ダイヤ処理部は、前記第１〜第ｎ車両スジにおける前記時刻の調整量を表す変数に基づき、第２の前記停車位置を出発する時刻、第２の前記停車位置に到着する時刻又は第２の前記停車位置を通過する時刻の間隔の平準化に関する第１評価指標を作成し、前記第１評価指標に基づき、前記変数の値を算出する
請求項１〜４のいずれか一項に記載の情報処理装置。
【請求項６】
前記第１評価指標は、
第２の前記停車位置を出発する時刻、第２の前記停車位置に到着する時刻又は第２の停車位置を通過する時刻と、第２の前記停車位置の前の停車位置を出発する時刻、前記前の停車位置に到着する時刻又は前記前の停車位置を通過する時刻と、の差と、
第２の前記停車位置を出発する時刻、第２の前記停車位置に到着する時刻又は第２の停車位置を通過する時刻と、第２の前記停車位置の次の停車位置を出発する時刻、前記次の停車位置に到着する時刻又は前記次の停車位置を通過する時刻との差と、
の差分の絶対値の総和を表す
請求項５に記載の情報処理装置。
【請求項７】
前記ダイヤ処理部は、前記第１〜第ｎ車両の車両種別ごとに、前記第１評価指標を作成する
請求項５又は６に記載の情報処理装置。
【請求項８】
前記ダイヤ処理部は、前記第１〜第ｎ車両スジにおける前記時刻の調整量を表す変数に基づき、前記第１〜第ｎ車両スジのうち少なくとも１つの車両スジの評価区間における走行時間の総和に関する第２評価指標を作成し、前記第２評価指標に基づき、前記変数の値を算出する
請求項１〜７のいずれか一項に記載の情報処理装置。
【請求項９】
前記ダイヤ処理部は、前記第１〜第ｎ車両スジにおける前記時刻の調整量を表す変数と、前記停車位置間の遅延時間の分布情報とに基づき、第３の前記停車位置を出発する時刻、第３の前記停車位置に到着する時刻、又は第３の前記停車位置を通過する時刻に対する遅延時間に関する第３評価指標を作成し、前記第３評価指標に基づき、前記変数の値を算出する
請求項１〜７のいずれか一項に記載の情報処理装置。
【請求項１０】
前記第３評価指標は、第３の前記停車位置を出発する時刻、第３の前記停車位置に到着する時刻、又は第３の前記停車位置を通過する時刻に対する遅延時間の平均値の総和を表す
請求項９に記載の情報処理装置。
【請求項１１】
前記制約条件は、前記第１ダイヤにおける前記時刻のうち予め指定された時刻を固定するとの条件を含む
請求項１〜１０のいずれか一項に記載の情報処理装置。
【請求項１２】
前記制約条件は、前記停車位置間の時間間隔が、インターバル情報によって定められた時間間隔以上になるとの条件を含む
請求項１〜１１のいずれか一項に記載の情報処理装置。
【請求項１３】
前記出力ダイヤ作成部は、算出した前記調整量を、前記第１ダイヤにおける前記時刻に加算することにより、前記第２ダイヤを作成する
請求項１〜１２のいずれか一項に記載の情報処理装置。
【請求項１４】
前記ダイヤ処理部は、前記第１〜第ｎ車両スジごとに前記時刻を複数のブロックにブロック化し、前記調整量は、ブロック単位の時刻の調整量を表し、
前記出力ダイヤ作成部は、前記複数のブロックと、算出された前記調整量とに基づいて、前記第２ダイヤを生成する
請求項１〜１３のいずれか一項に記載の情報処理装置。
【請求項１５】
前記ダイヤ処理部は、停車せずに走行する区間の開始の停車位置を出発する時刻と、前記区間の終了の停車位置に到着する時刻と、前記時刻間に存在する全ての時刻とを１つのブロックにまとめる
請求項１４に記載の情報処理装置。
【請求項１６】
前記第１〜第ｎ車両スジは、複数の前記停車位置について、前記車両が停車位置から出発する時刻、車両が前記停車位置に到着する時刻又は車両が前記停車位置を通過する時刻を含む
請求項１〜１５のいずれか一項に記載の情報処理装置。
【請求項１７】
前記第１〜第ｎ車両スジは、少なくとも１つのイベントを含み、
前記イベントは、前記停車位置と、前記車両が前記停車位置から出発する時刻、前記停車位置に到着する時刻又は前記車両が前記停車位置を通過する時刻と、を含み、
前記ダイヤ処理部は、前記第１〜第ｎ車両スジにおける前記イベントの前記時刻の調整量を算出し、算出した調整量と前記第１ダイヤとに基づき、前記第２ダイヤを作成する
請求項１〜１６のいずれか一項に記載の情報処理装置。
【請求項１８】
車両が停車位置から出発する時刻、車両が停車位置に到着する時刻及び車両が停車位置を通過する時刻のうちの少なくとも１つを含む第１〜第ｎ車両スジの第１ダイヤに基づき、前記時刻の調整量を算出するステップと、
算出した前記調整量と、前記第１ダイヤに基づいて、第２ダイヤを作成するステップと
を備えた情報処理方法。
【請求項１９】
車両が停車位置から出発する時刻、車両が停車位置に到着する時刻及び車両が停車位置を通過する時刻のうちの少なくとも１つを含む第１〜第ｎ車両スジの第１ダイヤに基づき、前記時刻の調整量を算出するステップと、
算出した前記調整量と、前記第１ダイヤに基づいて、第２ダイヤを作成するステップと
をコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、情報処理装置、情報処理方法及びコンピュータプログラムに関する。
【背景技術】
【０００２】
鉄道会社等にとって、ダイヤの遅延は、売り上げ減少や、罰金支払いなどのコスト増をもたらす深刻な問題である。したがって、遅延ロバスト性を有するダイヤを作成することが望ましい。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】登録特許第4727459号公報
【特許文献２】登録特許第6062790号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の実施形態は、遅延ロバスト性を有するダイヤを作成する情報処理装置、情報処理方法及びコンピュータプログラムを提供する。
【課題を解決するための手段】
【０００５】
本実施形態に係る情報処理装置は、車両が停車位置から出発する時刻、車両が停車位置に到着する時刻又は車両が停車位置を通過する時刻含む第１〜第ｎ車両スジの第１ダイヤに基づき、前記時刻の調整量を算出するダイヤ処理部と、算出した前記調整量と、前記第１ダイヤに基づいて、第２ダイヤを作成する出力ダイヤ作成部と、を備える。
【図面の簡単な説明】
【０００６】
【図１】本実施形態に係る情報処理装置であるダイヤ作成装置のブロック図。
【図２】ダイヤの概要を説明するための図。
【図３】ダイヤを入力するインタフェース画面（入力画面）の一例を示す図。
【図４】ダイヤの一例を表形式で示した図。
【図５】ダイヤの一例をグラフ形式で表した図。
【図６】ダイヤの他の例をグラフ形式で示す図。
【図７】ダイヤの他の例を表形式で示した図。
【図８】イベント間インターバル情報の例を表す図。
【図９】前ノードとの間のアークにイベント間インターバル情報を付加した例を示す図。
【図１０】図９の表をグラフ形式で表した図。
【図１１】本数条件とその設定画面の一例を示す図。
【図１２】本数条件を満たす複数のスジの例を模式的に示す図。
【図１３】バランス条件とその設定画面の一例を示す図。
【図１４】列車（各駅停車）のＡ駅の発ノードとＣ駅の発ノードに、それぞれバランス条件を適用して複数のスジを生成する例を示す図。
【図１５】速達性評価条件情報とその設定画面の一例を示す図。
【図１６】遅延評価対象情報及びその設定画面の一例を示す図。
【図１７】各駅間の走行時間の遅延時間の平均値、及び各駅の停車時間の遅延時間の平均値の例を示す図。
【図１８】イベント間遅延分布として幾何分布の例を示す図。
【図１９】ダイヤを変換したネットワークの例を示す図。
【図２０】図１９のノード群から作成したブロックの例を示す図。
【図２１】前詰めダイヤの最初の部分の例を示す図。
【図２２】全てのノードの最速時刻を決定した前詰めダイヤの例を示す図。
【図２３】余裕時間を計算する例を示す図。
【図２４】密度条件処理部の処理の一例を示すフローチャート。
【図２５】ノードの２次遅延時間の算出を説明するための図。
【図２６】出力ダイヤを得るプロセスを表すデータを示す図。
【図２７】出力ダイヤのグラフの一例を示す図。
【図２８】他の出力ダイヤのグラフの一例を示す図。
【図２９】最適化処理のためのパラメータの入力インタフェース画面の一例を示す図。
【図３０】図１のダイヤ作成装置による処理の一例を示すフローチャート。
【図３１】本実施形態に係るダイヤ作成装置（情報処理装置）のハードウェア構成を示す図。
【発明を実施するための形態】
【０００７】
以下、図面を参照しながら、本発明の実施形態について説明する。
【０００８】
図１は、本実施形態に係る情報処理装置であるダイヤ作成装置１００のブロック図である。ダイヤ作成装置１００は、ダイヤ情報入力部１１０、列車密度条件入力部１２０，速達性評価条件入力部１３０、遅延評価条件入力部１４０、ダイヤ処理部５００、出力ダイヤ作成部３９０、表示部（出力ＧＵＩ）４００、及び各種記憶部を備える。ダイヤ処理部５００は、ネットワーク作成部５２０、ブロック作成部５２１、前詰めダイヤ作成部５２２、密度条件処理部５２３、評価指標作成部５２４、及び最適化部５２５を備える。各種記憶部は、記憶部１１１、記憶部１１２、記憶部１１３、記憶部１１４、記憶部１１５、記憶部１１６及び記憶部１１７を備える。
【０００９】
ダイヤ作成装置１００は、列車又はバス等の車両（以下では列車を想定）の運行スケジュールを定めたダイヤ（第１ダイヤ）における各イベントの時刻の調整量を、各列車の車両スジの配置間隔に関する制約条件、及びダイヤに要求される各種性能を評価するための指標（評価指標）に基づき算出し、算出した調整量とダイヤに基づき、出力ダイヤ（第２ダイヤ）を作成する。
【００１０】
ここでダイヤとは、複数の車両（列車、バスなど）に関して、少なくとも１つのイベントの系列を表したものである。イベントは、停車位置（場所）と、停車位置から出発する時刻、停車位置に到着する時刻又は停車位置を通過する時刻とを含む。すなわち、イベントは当該停車位置と当該時刻とを対応づけたデータである。停車位置は、例えば駅、停留所、留置場所、車庫、信号場などである。以下では、車両として主として列車を想定するが、バスなど他の車両の場合も、適宜交通機関の違いに応じた必要な読み替えを行うことで、同様に実施できる。例えば駅を停留所と読み替えるなどである。
【００１１】
車両スジは、同一車両について、１つ又は複数の停車位置を含む運行経路の各停車位置について、停車位置を出発する時刻、停車位置に到着する時刻、及び停車位置を通過する時刻の少なくとも１つを含むデータである。より詳細には、車両スジは、同一車両について、１つ又は複数の停車位置を含む運行経路について、各停車位置に関するイベントの系列のことである。本明細書において車両スジのことを単にスジと記載する場合もある。
【００１２】
本実施形態における車両スジの配置間隔に関する制約条件の例としては、イベント間の時間制約の条件や、所定の期間に含まれる車両スジの本数の条件（密度条件）がある。車両スジの本数を確保することは、列車の輸送力を確保することに相当する。
【００１３】
また、本実施形態におけるダイヤに要求される各種性能の例として、乗客ができるだけ早く目的地につけること(速達性)、スジ間の間隔が平準化されていること、遅延の影響を受けにくいこと（遅延ロバスト性）などがある。各種性能を評価するための評価指標を作成する方法については後述する。
【００１４】
本実施形態は、このような制約条件及び各種性能に関する評価指標に基づき、遅延ロバスト性を有するダイヤを作成することを実現する。本実施形態は、さらに好ましくは、乗客ができるだけ早く目的地につけること(速達性)、車両スジ間の間隔が平準化されていることの少なくとも一方を満たすダイヤを作成する。
【００１５】
以下、ダイヤ作成装置１００を説明するに先立ち、ダイヤにおけるイベント間の時間制約について簡単に説明する。
【００１６】
一般にダイヤの作成では、駅間の走行時間の最小値や、駅での停車時間の最小値に対して、列車の遅延を想定したマージン時間（余裕時間）を加算して、イベントの時刻（出発時刻や到着時刻等）を定めることが多い。また、ある列車の車両スジ（自スジ）と、これに先行する他の列車の車両スジ（先行スジ）の間には、時間間隔に関する制約（時隔制約）があることが多く、先行スジの遅延時間が所定の値を超えると、この影響が自スジの列車に波及する。すなわち遅延には、自スジ上の遅延と、先行スジからの影響に起因する遅延の二種類がある。より詳細には、自スジにおける先行イベントに起因する遅延（自スジ起因遅延）と、先行スジにおける先行イベントから起因する遅延（他スジ起因遅延）とがある。これらの自スジ上の遅延と先行スジからの遅延との２種類の影響が、自スジの列車に波及する。
【００１７】
図２（Ａ）に、ある列車のスジ１１のグラフと、他の列車のスジ１２のグラフとがネットワーク形式で示される。図中の丸はノードであり、ノードはイベントを表す。スジ１１はＡ駅を出発するイベント１１ａ、Ｂ駅に到着するイベント１１ｂ−１、Ｂ駅を出発するイベント１１ｂ−２、Ｃ駅に到着するイベント１１ｃ−１、Ｃ駅を出発するイベント１１ｃ−２、Ｄ駅に到着するイベント１１ｄを含む（イベントに対応するノードを同じ参照符号で示している）。各イベントにはダイヤの時刻が設定されている。紙面に沿って右方向が時間方向である。スジ１２はスジ１１と同じ経路を運行する他の列車のスジ（スジ１１の後続スジ）である。スジ１２はＡ駅を出発するイベント１２ａ、Ｂ駅に到着するイベント１２ｂ−１、Ｂ駅を出発するイベント１２ｂ−２、Ｃ駅に到着するイベント１２ｃ−１、Ｃ駅を出発するイベント１２ｃ−２、Ｄ駅に到着するイベント１２ｄを含む。各駅では上り（Ａ駅からＤ駅方向）、下り（Ｄ駅からＡ駅の方向）のそれぞれにおいて番線が１つのみ存在するとする。この場合において、他の列車のＣ駅の着イベント（イベント１２ｃ−１）を考える。イベント１２ｃ−１の遅延は、スジ１２における１つ前のイベント１２ｂ−２の遅延（自スジ起因遅延）と、先行スジ（スジ１）の駅Ｃのイベント１１ｃ−２の遅延（他スジ起因遅延）の影響を受ける。イベント１１ｃ−２以外の同駅Ｃのイベント（イベント１１ｃ−１等）の影響を受ける場合もある。自スジ起因遅延の具体例として、前駅Ｂからの走行時間の遅延や前駅Ｂからの出発時刻（発時刻）の遅延等があり得る。また、他スジ起因遅延の具体例として、先行スジ１の駅Ｃでの出発遅延等があり得る。イベント間には、最小限空けなければならない時間間隔である最小必要時間と、マージン時間（余裕時間）とがある。例えば、イベント１１ａ及びイベント１２ａ間は、最小必要時間以上空ける必要がある。ダイヤ上のイベント１１ａ及びイベント１２ａ間の時間は、一例として、最小必要時間にマージン時間を加算した時間である。列車のＡ駅の出発から他の列車のＡ駅の出発までの時間が最小必要時間を超えても、最小必要時間にマージンを加算した時間以下であれば、イベント１１ａ及びイベント１２ａ間に遅延はない。すなわちイベント１１ａ及びイベント１２ａ間の遅延時間（最小必要時間を超えた時間）がマージン時間以下であれば、当該イベント間に遅延はない。
【００１８】
図２（Ａ）では、着イベント（イベント１２ｃ−１）に着目したが、発イベントの場合も同様である。図２（Ｂ）において、Ｃ駅の発イベント（イベント１２ｃ−２）を考える。イベント１２ｃ−２の遅延は、スジ１２における１つ前のイベント１２ｃ−１の遅延（自スジ起因遅延）と、先行スジであるスジ１１のイベント（Ｃ駅の発イベント１１ｃ−２）の遅延（他スジ起因遅延）の影響を受ける。自スジ起因遅延の具体例として、Ｃ駅の到着の遅延やＣ駅の停車時間の遅延（乗降時間が長くなったなど）があり得る。イベント間には、最小限空けなければならない時間間隔（最小必要時間）と余裕時間（マージン時間）とがある。例えば、イベント１２ｃ−２及びイベント１２ｃ−１間は、最小必要時間（最小必要乗降時間）以上空ける必要がある。ダイヤ上のイベント１２ｃ−２及びイベント１２ｃ−１間の時間は、一例として、最小必要時間にマージン時間を加算した時間である。Ｃ駅の到着から出発までの時間が最小必要時間を超えても、最小必要時間にマージンを加算した時間以下であれば、イベント１２ｃ−２及びイベント１２ｃ−１間に遅延はない。すなわち当該２つのイベント間の遅延時間（最小必要時間を超えた時間）がマージン時間以下であれば、当該イベント間に遅延はない。ここではイベント間に空ける必要のある時間として最小必要時間を用いたが、通常空けることが期待される時間など、最小必要時間以外の時間を用いてもよい。このことは以下に詳述する本実施形態でも同様に適用される。
【００１９】
以下、図１のダイヤ作成装置１００について詳細に説明する。
【００２０】
［ダイヤ情報入力部１１０、ダイヤ２１０、イベント間インターバル情報２１１］
図１のダイヤ情報入力部１１０は、ダイヤ２１０を取得し、取得したダイヤ２１０を記憶部１１１に格納する。ダイヤ情報入力部１１０は、一例として、ダイヤ作成装置１００のオペレータが操作するキーボード、マウス、タッチパネル等の入力手段である。この場合、ダイヤを入力するためのインタフェース画面を提示する機能を、ダイヤ作成装置１００は備える。インタフェース画面は、表示部４００に表示される。
【００２１】
表示部４００は、データ又は情報を表示するＬＣＤ（液晶ディスプレイ）、ＣＲＴ（ブラウン管）、又はＰＤＰ（プラズマディスプレイ）などの表示装置である。
【００２２】
ダイヤ情報入力部１１０は、ダイヤ２１０を外部の装置又は記憶媒体から取得する取得手段でもよい。この場合、外部の装置は、一例として、ダイヤ作成装置１００と有線又は無線の通信ネットワークを介して接続された外部サーバである。また、記憶媒体は、一例として、ダイヤ作成装置１００の内部に配置された記憶媒体又は外部接続された記憶媒体である。記憶媒体の例は、メモリ装置、ハードディスク、ＳＳＤ、光学ディスクなどを含む。ダイヤの取得のトリガーは、ダイヤ作成装置１００のオペレータの指示でもよいし、その他の条件（例えば所定の時刻になったなど）でもよい。
【００２３】
図３は、ダイヤ２１０を入力するインタフェース画面（入力画面）の一例を示す図である。オペレータはこの画面からダイヤを入力することができる。
【００２４】
図３では、ある列車のスジ情報を入力する画面の例が示されている。入力画面は時刻表メニューＭ１とマージン時間メニューＭ２とを含む。図３では、時刻表メニューＭ１の画面が表示されている。
【００２５】
この列車はＡ駅からＣ駅まで運行される。Ａ駅を出発し、Ｂ駅に停車し、Ｃ駅に停車する。この列車は、Ａ駅、Ｂ駅、Ｃ駅に停車するため、通停項目（停車するか通過するかを表す）は「停車」に設定されている。また、Ａ駅の出発時刻（以下、発時刻）と、Ｂ駅の到着時刻（以下、着時刻）及び発時刻と、Ｃ駅の着時刻が設定されている。また、Ａ駅からＢ駅までの運転時間（Ａ駅の発時刻からＢ駅の着時刻までの時間）と、Ｂ駅での停車時間（Ｂ駅の着時刻から発時刻までの時間）が設定されている。列車は各駅で１番線に停車することが設定されている。Ａ駅に８：００に出発、Ｂ駅に８：１０に到着、Ｂ駅から８：１２に出発、Ｃ駅に８：３２に到着、などがそれぞれ１つのイベントに相当し、これらのイベントの列がスジである。
【００２６】
列車番号項目で列車の番号（ここでは０００００１）を設定できる。種別項目では、この列車が、ローカル（各駅停車）か急行かを設定できるようになっている。ローカルか急行かに応じて、各駅の通停項目の値（停車あるいは通過）が自動的に入力されてもよい。また、定期／不定期項目では、この列車の運行が定期か不定期かを設定できる。一例として、定期の場合、このスジ情報が、平日に適用され、不定期の場合、休日に適用される。
【００２７】
図４は、ダイヤ情報入力部１１０から入力されるダイヤ２１０の一部を表形式で示す。
【００２８】
図４の表は、Ａ駅からＣ駅まで移動する互いに異なる車両（列車）の３つのスジ情報を含む。これらの車両は一例として第１〜第ｎ車両に対応する。３つのスジは、第１〜第ｎ車両スジに対応する。ダイヤは、スジＩＤと、時刻と、駅と、イベントの種類との列を有する。種類は、出発（arrival）・到着(departure)・通過(pass)等を表すイベントの種類である。図示の表は、ダイヤは、８：００発のスジ１、８：２０発のスジ２、８：３０発のスジ３に関する情報を含む。スジ１は、図３で例示したスジに対応している。スジ１とスジ３の場合、車両は全ての駅に停車するため、通過イベントは存在しない。一方、スジ２では車両がＢ駅を通過するので、Ｂ駅に対して通過イベントが設定されている。
【００２９】
図５は、図４のダイヤに含まれるスジ１〜３をグラフ（ネットワーク）により表している。横軸は時間、縦軸は距離に対応する。横軸の時間は相対時間であり、「０」は本例では８：００に対応する。各グラフ（ネットワーク）はイベントに対応するノードと、ノード間を接続するアークとを含む。アークは、イベント間の遅延の伝播可能性を表す。具体的に、スジ１のグラフは、スジ１に含まれる時刻の早い順のイベント（それぞれイベント１、２、３、４）に対応するノードｅ１、ｅ２、ｅ３、ｅ４と、これらのノードを接続するアークと、を含む。同様に、スジ２のグラフは、スジ２に含まれる時刻の早い順のイベント（それぞれイベント５、６、７）のノードｅ５、ｅ６、ｅ７と、これらのノードを接続するアークと、を含む。スジ３のグラフは、スジ３に含まれる時刻の早い順のイベント（それぞれイベント８、９、１０、１１）のノードｅ８、ｅ９、ｅ１０、ｅ１１と、これらのノードを接続するアークと、を含む。
【００３０】
図６は、ダイヤ情報入力部１１０から入力されるダイヤ２１０の他の例のグラフ（ネットワーク）を示す。図７は、図６と同じ内容のダイヤ２１０をノード毎の属性として表形式で表したものである。ダイヤ情報入力部１１０から入力されるダイヤ２１０の形式は、図７の表又は図６のグラフ（ネットワーク）のいずれの形式でもよい。一方を入力して他方に変換してもよい。本実施形態では表形式のダイヤ２１０を入力し、後述するネットワーク作成部５２０で、表形式のダイヤ２１０をネットワークに変換することを想定する。
【００３１】
図６において、５：００発の列車１（スジＩＤが１の列車）は、駅Ａ、Ｂ、Ｃ、Ｄ、Ｅの全ての駅に停車する各駅停車を表す。５：０６発の列車２（スジＩＤが２の列車）はＢ駅とＤ駅を通過する急行列車を表す。列車１は全ての駅に停車するので、列車１のスジ（スジ１）のノードは発ノード・着ノードのいずれかである。列車２のスジ（スジ２）は、通過駅に関しては、通過ノードで表され、それ以外駅については発ノード・着ノードである。なおＣ駅で、列車１は列車２と待ち合わせており、Ｄ駅以降は列車２が列車１よりも先に通過・到着する。破線のアークは、異なる列車のスジ間のアーク、実線のアークは自列車のスジにおけるアークを表す。異なる列車のスジ間のアークの例として、同一番線を利用する複数の列車間のアーク、折り返しがある場合の連続する複数の列車間に関するアークなどがある。
【００３２】
図７のダイヤは、ノードＩＤ（各ノードのＩＤ）、スジＩＤ（列車のＩＤ）、時刻（時刻表上の時刻。図示の例は時分で表している）、駅、ノード（イベント）の種類、Ｐｎｏｄｅ１（１個目の前ノードのノードＩＤ。１個目の前ノードが存在しなければ０）、Ｐｎｏｄｅ２（２個目の前ノードのノードＩＤ。２個目の前ノードが存在しなければ０）を含む。なお、Ｐｎｏｄｅ１、Ｐｎｏｄｅ２の順序は任意でよく、Ｐｎｏｄｅ１、Ｐｎｏｄｅ２を入れ替えてもよい。図４の例と異なる点として、ノードＩＤ、Ｐｎｏｄｅ１、Ｐｎｏｄｅ２が追加されている。Ｐｎｏｄｅ１、Ｐｎｏｄｅ２はユーザが直接入力してもよいし、他の入力された情報から演算により算出してもよい。前ノード（Ｐｎｏｄｅ）の数は３個以上の場合もあるが、その場合は必要個数の情報を含めればよい。
【００３３】
図６又は図７の情報は、既存のダイヤがもっている情報から抽出してもよいし、ユーザが図３に示したような入力画面を用いてこれらの情報を入力してもよい。ここでは、各列車について片道の運行をスジとして表したが、何往復分かの運行をスジとして表してもよい。
【００３４】
以上では、ダイヤの例として、図４及び図５の例と、図６及び図７の例を示したが、以下の説明では、主として図６及び図７の形式のグラフ情報をベースに説明を行う。
【００３５】
図１のダイヤ情報入力部１１０は、ダイヤ２１０の他、イベント間インターバル情報２１１を取得し、取得したイベント間インターバル情報２１１を記憶部１１１に格納する。イベント間インターバル情報２１１の取得方法の具体例は、ダイヤ２１０の場合と同様である。イベント間インターバル情報２１１のことを単純にインターバル情報と呼んでもよい。以下、イベント間インターバル情報２１１の詳細について説明する。
【００３６】
イベント間インターバル情報２１１は、アーク（ノード間）に定義される最小時間を表す。
【００３７】
図８は、図６及び図７の例に対応するイベント間インターバル情報２１１の例を表している。イベント間インターバル情報２１１には、自スジの中のイベント間の時間間隔の制約（時隔制約）として、各駅の最小停車時間と、各駅間（区間）の最小走行時間を定めている。最小走行時間は、種別（各駅停車、急行など）ごとに定められている。最小停車時間も種別ごとに定められていてもよい。
【００３８】
また、先行スジと自スジ間の時隔制約として、先行スジの着時刻と自スジの発時刻の間に最小限空けなければならない時間（最小インターバル時間）が定められている。最小インターバル時間は、先行スジ及び自スジにおける同一駅のイベント間に対して定められている。但し、先行スジ及び自スジにおける異なる駅のイベント間に最小インターバル時間が定められていてもよい。
【００３９】
図９は、図７の全てのノードについて、前ノード（Ｐｎｏｄｅ１、Ｐｎｏｄｅ２）との間のアークにイベント間インターバル情報２１１を付加した表の例を示す。図１０は、図９の表をグラフで表したものである。これは、図６のグラフの全てのノードについて、当該ノードとその前ノード間のアークに、イベント間インターバル情報２１１を付加したものに相当する。
【００４０】
なお、複数の番線がある場合に、同一番線と異なる番線の着着時隔、発発時隔を区別して扱ってもよい。また、折り返しがある場合には折り返しに関する時隔の制約を与えてもよい。追い越し又は通過などの場合に、着着時隔や発発時隔等と異なる時隔値を使ってもよい。車両の種類や走行する時間帯（ラッシュ時かそうでないかなど）によって異なる時隔値を使ってもよい。
【００４１】
なお、イベント間インターバル情報２１１を入力する代わりに、例えば各駅間などに与えられた余裕時間に関する情報を入力してもかまわない。この場合、本ダイヤ作成装置において、ダイヤ上の時刻差と余裕時間との差分を計算することにより、イベント間インターバル情報２１１を得ることができる。またイベント間インターバル情報２１１は、駅間の距離や、車両ごとの最高速度や加速性能などの情報から計算してもよい。
【００４２】
ここでは、イベント間インターバル情報２１１はアーク（ノード間）に定義される最小時間を表すとして定義したが、アークの時間（ノード間の時間間隔）に関する値であれば、最小時間に限定されるものではない。例えば、イベント間に通常空けておくことが望まれる時間などでもよい。
【００４３】
［列車密度条件入力部１２０、本数条件情報２２０、バランス条件情報２２１］
図１の列車密度条件入力部１２０は、本数条件情報２２０及びバランス条件情報２２１を取得し、取得したこれらの情報を記憶部１１２に格納する。列車密度条件入力部１２０の具体的な実装例は、ダイヤ情報入力部１１０の場合と同様である。
【００４４】
本数条件情報２２０は、特定のイベント（特定の駅及び特定のイベント種類）を対象に、１時間ごとの列車の本数の要求値を本数条件として表したものである。特定の駅を対象駅、特定のイベント種類を対象イベント種類と記載する。対象駅及び対象イベント種類の組を対象ノードと記載する。本数条件は、第１の期間に第１の停車位置を出発する時刻、第１の停車位置に到着する時刻又は第１の停車位置を通過する時刻が含まれる車両スジの本数の条件である。
【００４５】
図１１は、本数条件とその設定画面の一例を示す。対象種別（各駅停車、急行）と方向（上り、下り）ごとに、対象ノード（対象駅及び対象イベント種類）に対して、1時間ごとの本数を設定している。画面左側で対象種別として各駅停車、急行の両方（すなわち全列車）を指定している。また方向として上りを指定している。画面右側の対象ノードの設定では、左側で対象種別に設定された全ての列車に関して、本数を数えるべき駅を指定する。図の例では、各駅停車及び急行の列車について、Ｃ駅を５時台（５：００−６：００）の間に３本、６時台（６：００−７；００）の間に３本、７時台（７：００〜８：００）の間に３本・・・、２３時台（２３：００−２４：００)の間に３本出発することが設定されている。なお、５：００−６：００等の表記は５時台等を表す簡易表記であり、厳密には６：００丁度は含まないことに注意する。以下同じである。対象イベント種別はここでは出発であるが、到着又は通過など、他のイベント種別でもよい。５時台、６時台等の各時間帯は、スジの本数を設定する第１の期間に対応する。Ｃ駅は、本数条件が設定される対象駅である第１の停車位置に対応する。
【００４６】
図１１の例では、本数条件の設定を、各駅停車と急行の両方（全列車）に共通に行っているが、例えば急行列車と、各駅停車の列車とのそれぞれについて別々に本数条件の設定を行ってもよい。また急行列車又は各駅停車の列車の一方にのみ、本数条件を設定してもよい。また、本数条件の設定を、一部の列車（例えば複数の急行列車のうちの一部の急行列車など）にのみ行ってもよい。
【００４７】
以下、本数条件を満たす複数のスジの例を具体的に示す。図１２は、図１１で示した本数条件を満たす複数のスジの例を模式的に示す。全列車を本数条件の設定の対象とし、いずれの列車もＣ駅の発ノードを対象ノードとしている。各スジＥは各駅停車の列車のスジ、各スジＲは急行列車のスジを表す。この場合、塗りつぶした丸で示したノードが対象ノードであり、５：００台、６：００台、７：００台等に、それぞれ３，３，５個の対象ノードが入っており、本数条件が満たされていることが分かる。
【００４８】
なお、ここまでの説明はダイヤが予め与えられることを前提としたが、ここで定める本数条件を元に、図６又は図７のダイヤ又はグラフ情報を本装置１００が自動生成してもよい。この場合は、種別毎に各駅の発・着・通過の情報を予め与えておき、ここで定める本数条件と組み組合せて、ダイヤ又はグラフ(ノードとアーク)を作成する。この際、駅間の時間間隔に関しては、図８のような最小時間間隔を用いて定めてもよいし、標準的な時間間隔を別に定めて採用してもよい。また列車の追い抜き駅や追い抜きのタイミングを別途定めてもよい。このようにダイヤ又はグラフ情報を自動生成することにより、本実施形態は、予め与えられたダイヤを修正して上述した制約条件や各種性能を満たすダイヤを作成する他、ダイヤを最初から制約条件や各種性能を満たすダイヤを作成することも可能である。
【００４９】
バランス条件情報２２１は、スジ間の時間間隔の制約に関する条件（バランス条件）を定めた情報である。上述の本数条件により、所定の時間当たりに設定する本数を定めることができるが、バランス条件を定めることで、スジの間隔をできるだけ均等にすることができる。間隔を調整する対象ノードは、一例として、本数条件を設定した対象ノード（対象駅及び対象イベント種別）である。但し、本数条件を設定したノードとは別のノードを、バランス条件を適用するノードとして定めてもよい。
【００５０】
図１３は、バランス条件とその設定画面の一例を示す。バランス条件の設定の対象は、種別ごと、又は全列車共通など、任意に定義できる。図の例では、種別（各駅停車、急行）ごとに設定している。この場合、各駅停車の列車のスジ間で間隔を均等にし、急行の列車のスジ間で間隔を均等にすることを意味する。バランス制約の与え方としては、全列車共通を設定した場合は、全列車の間隔を均等にすることを意味する。その他、一部の種別の間隔のみを均等にする場合、一部の時間帯のみを均等にする場合、それらの組合せ、など様々なバリエーションが可能である。なお上述のようにバランス条件を、本数条件で定めた対象ノードは別のノードに対して設定されてもよい。例えば本数条件ではＣ駅の発イベントを対象としつつ、バランス条件はＣ駅の発イベントだけではなく、Ａ駅の発イベントを対象としてもよい。
【００５１】
図１４は、列車（各駅停車）のＡ駅の発ノードとＣ駅の発ノードに対して、それぞれバランス条件が満たされる複数のスジの例を示す。この場合、Ａ駅の発ノードの隣り合う間隔Ａ１、Ａ２、Ａ３、Ａ４、Ａ５、Ａ６と、Ｃ駅の発ノードの隣り合う間隔Ｃ１、Ｃ２、Ｃ３、Ｃ４、Ｃ５、Ｃ６がそれぞれなるべく等しくなるよう、複数のスジ間の間隔が調整されている。
【００５２】
速達性評価条件入力部１３０は、速達性評価条件情報２３０を取得し、取得した情報を記憶部１１３に格納する。速達性評価条件入力部１３０の具体的な実装例は、ダイヤ情報入力部１１０と同様である。
【００５３】
速達性評価条件情報２３０は、各列車の走行時間（速達性）を評価する対象となる区間を定めている。区間の走行時間が短いほど、速達性が高い。区間は、一例として、区間の開始点（評価開始点）及び終了点（評価終了点）により特定される。評価開始点は評価開始ノードで表し、評価終了点は、評価終了ノードで表すことができる。評価開始ノードは例えば評価開始駅の発ノード、評価終了ノードは、例えば評価終了駅の到着ノードである。
【００５４】
図１５は、速達性評価条件とその設定画面の一例を示す。種別（各駅停車、急行）ごとに、評価開始駅（評価開始ノード）と評価終了駅（評価終了ノード）を設定している。これ以外の設定方法として、列車ごとに、評価開始駅と評価終了駅を設定する方法でもよい。
【００５５】
遅延評価条件入力部１４０は、遅延評価用の情報として、遅延評価対象情報２４０及び遅延時間分布情報２４１を取得し、これらの取得した情報を記憶部１１４に格納する。遅延評価条件入力部１４０の具体的な実装例は、ダイヤ情報入力部１１０と同様である。
【００５６】
遅延評価対象情報２４０は、各列車の遅延を評価する対象となるノード（遅延評価ノード）を表す。評価遅延ノードは、評価対象駅と、評価対象のイベント種類（出発、到着、通過など）との組により表される。
【００５７】
図１６は、遅延評価対象情報２４０及びその設定画面の一例を示す。ここでは、種別（各駅停車、急行）及び方向（上り、下り）ごとに、評価対象駅をチェックボックスで与えている。評価対象のイベント種類は、出発であることが事前に指定されている。但し、イベント種類は、到着又は通過などでもよく、イベント種類を指定するチェックボックスを設けてもよい。図の例では、始発駅であるＡ駅、中間駅であるＣ駅、終着駅であるＥ駅を評価対象駅に指定されている。したがって、Ａ駅、Ｃ駅、Ｅ駅の発ノードが評価対象ノードとして指定されている。
【００５８】
遅延時間分布情報２４１は、イベント間の遅延時間の分布であるイベント間遅延分布、又はイベント間遅延分布を作成するために必要な情報である。そのような情報の例として、確率分布のパラメータがある。平均値、分散値、中間値といった統計量をパラメータとしてもつ確率分布に対するパラメータを、遅延時間分布情報としてもよい。イベント間遅延分布は、一例として、幾何分布又は負の二項分布がある。イベント間遅延分布の具体例として、駅間の走行時間の遅延分布、駅の停車時間の遅延分布などがある。走行時間は前の駅の発時刻（発イベントの時刻）から、次の駅の着時刻又は通過時刻（着イベントの時刻又は通過ベントの時刻）までの時間に対応する。停車時間は、駅の着時刻（着イベントの時刻）から同駅の発時刻（発イベントの時刻）までの時間に対応する。
【００５９】
イベント間遅延分布の一例として、幾何分布を用いた確率分布の例を示す。式（１）は幾何分布の確率関数（離散分布）を表し、Ｄ（ｋ）は遅延時間がｋである確率を表す。ｋは確率変数である。ｐは幾何分布である。幾何分布は、遅延時間の平均値がｘであるとき、ｐ＝１／（ｘ＋１）と定めることができる。
【数１】
2020203549.tif 000003
幾何分布では、パラメータはp１個だけである。従って、１個の統計値をパラメータに与えるだけで、分布を決定することができる。
【００６０】
図１７に、各種別（各駅停車（各停）、急行など）に、各駅間の走行時間の遅延時間の平均値の例と、各駅の停車時間の遅延時間の平均値の例が示されている。幾何分布を用いる場合、このような平均値をパラメータとして用いて分布を定めることができる。列車の種別に応じて、異なる遅延時間分布情報を用いてもよい。また、時間帯（ラッシュ時かそうでないかなど）に応じて、異なる遅延時間分布情報を用いてもよい。なお、遅延を考慮しない場合は、イベント間の遅延時間を全て０とすればよい。
【００６１】
図１８にイベント間遅延分布の例として幾何分布を用いた確率分布の例を示す。横軸がｋ（遅延時間）であり、縦軸がＤ（ｋ）（遅延時間がｋである確率）である。この例では最初に確率関数が非負になる値はｋ＝０であるが、分布を左右にシフトして、kが負又は正の部分で最初に確率関数が非負になるようにしてもよい。
【００６２】
遅延時間分布情報２４１の他の例として、遅延時間の実績に基づくヒストグラムを用いてもよい。この場合のヒストグラムは、運行実績を直接用いてもよいし、何らかの近似分布から発生したサンプルであってもよい。
【００６３】
［ダイヤ処理部５００］
ダイヤ処理部５００は、記憶部１１１〜１１４に記憶された情報に基づき、イベント間の時間制約や、列車の輸送力を確保すること（密度条件）を満たしつつ、乗客ができるだけ早く目的地につけること(速達性)、平準化されていること(バランス条件)、遅延の影響を受けにくさ（遅延ロバスト性）などの各種性能を満たすダイヤを高速に作成する。
【００６４】
［ダイヤ処理部５００のネットワーク作成部５２０］
ネットワーク作成部５２０は、記憶部１１１からダイヤ２１０を読み出し、読み出したダイヤ２１０をネットワークに変換する。ダイヤ２１０が最初からネットワークを有する場合は、この変換は不要である。
【００６５】
図１９は、ダイヤ２１０を変換したネットワークの例を示す。以下では、このネットワークを前提として説明を行う。
【００６６】
ネットワーク作成部５２０は、各ノードの前ノード（Ｐｎｏｄｅ１、Ｐｎｏｄｅ２）（図７参照）を特定し、特定した前ノードの情報をダイヤ２１０に追加する。ダイヤ２１０に最初から前ノードの情報が付加されている場合は、前ノードを特定する作業は不要である。
【００６７】
［ブロック作成部５２１］
ブロック作成部５２１は、ダイヤ２１０に含まれるノード群をブロック化することにより、それぞれ１つ以上のノードを含む複数のブロックを作成する。ブロックとは、あるノードの時刻を一定時間ずらした場合に、同じ時間だけ時刻をずらさなければならないノードを全てまとめたノード集合のことである。複数のブロックは、ダイヤ２１０に含まれる時刻をブロックしたものと考えることもできる。
ノードは全て自由に動かせる場合もあるが、束縛したい場合もある。例えば、横軸を時刻、縦軸を距離とした座標系にスジを表した場合に、走行中のアークの傾きが変えられない場合（速度が変えられない場合）、アークの両端のノード間の時間差は固定になる。例えば、ある列車のある区間（Ａ駅からＢ駅とする）中のＡ駅の発ノードｊ１からＢ駅の着ノードｊ２までの時間差は固定となる。この場合、発ノードｊ１の時刻を１分遅らせると、着ノードｊ２の時刻も１分遅らせることとなる。したがって、このような相対的に動けないノード群は組にし、ブロックと呼ぶ。
例えば、停車せずに走行する区間の開始の停車位置のイベント（開始ノード）及び区間の終了の停車位置のイベント（終了ノード）と、開始イベント及び終了イベント間に存在するすべてのイベント（ノード）を１つのブロックにまとめる。あるいは、停車せずに走行する区間の開始の停車位置を出発する時刻と、区間の終了の停車位置に到着する時刻と、当該時刻間に存在する全ての時刻とを１つのブロックにまとめる。
【００６８】
このとき、全てのノードはいずれかのブロックに排他的に含まれるため、ノード集合Ｖは、集合ｂ０，ｂ１，．．．，ｂＢに分割される。なお以下ではｂ（ｊ）により、ノードｊが属するブロックを表すこととする。
【００６９】
図２０は、図１９のノード群から作成したブロックの例を示す。図１９のノード群は、ブロックｂ０，ｂ１，．．．，ｂ２５に分割される。例えばノード１とノード２間の移動速度は固定であると仮定すると、ノード１とノード２間の相対位置は調整できないため、ノード１とノード２を同じブロックに分類する。一方、ノード３は、ノード２に対してその位置を余裕時間の範囲内で移動させることができる（すなわちノード２との相対位置を調整できる）ため、ノード３をノード２と同じブロックには分類しない。
【００７０】
［前詰めダイヤ作成部５２２］
前詰めダイヤ作成部５２２は、ブロック作成部５２１で作成したブロックの束縛関係を前提とした条件下で、最速のダイヤを作成する。このダイヤを、前詰めダイヤ３００と呼ぶ。ブロックの束縛関係とは、ブロック内のノードの相対位置を変えないことである。最速のダイヤとは、最後のノードの時刻が最も早いダイヤである。前詰めダイヤ作成部５２２は、前詰めダイヤ３００を記憶部１１５に格納する。
【００７１】
図２１は、前詰めダイヤの最初の部分（前詰めダイヤの列車１と列車２の部分）の例を示す。これは、図２０のブロック群と、図８のようなイベント間インターバル情報２１１とに基づき作成されている。
【００７２】
図２１の各アークに沿った数字は、図８のイベント間インターバル情報２１１に示した、各アークに対する最小インターバル時間である。また各ノードに付記した太字の数字は、前詰めダイヤ作成部５２２によって作成された時刻を表す。ここでは、ノード１の時刻を０としたときのノード１の時刻に対する相対時間（分）で、他のノードの時刻を表している。
【００７３】
以下、図２１に基づき、前詰めダイヤの具体的な作成方法を説明する。
【００７４】
まず、最初のノード１の時刻は０とする。
【００７５】
次にノード２に関しては、ノード１，２間のアークのイベント間インターバル情報２１１が６であることから、ノード２の時刻は６となる。
【００７６】
同様にしてノード３の時刻７、ノード４の時刻１５などが計算できる。
【００７７】
次に、ブロックｂ５（図２０参照）に属するノード１０，１１，１２については、直前のノードとの関係で、制約が一番厳しいノード１２を最初に決定する。この場合、ノード４から最低１のインターバル時間をノード１２に対して空ける必要があるため、ノード１２の時刻は１６となる。このノードを基準とすると、ブロックｂ５内の相対位置関係は変えられないことから、ノード１１の時刻は、１０（＝「ノード１２の時刻」−「ノード１１，１２間の最小インターバル時間」＝１６−６）と計算できる。同様に、ノード１０の時刻は、６（＝１０−４）と計算できる。なお、ここでは最小インターバル時間を用いて、ブロック内の各ノードの時刻を定めたが、それ以外の時間を用いてもよい。
【００７８】
以降、同様の手続きにより、時間的に手前にあるブロックに属するノードから順に時刻を定めていくことで、全てのノードの時刻を決定できる。これにより前詰めダイヤが作成される。
【００７９】
図２２は、全てのノードの時刻を決定した前詰めダイヤの例を示す。ここではブロックの表記や、最小インターバル時間の表記は省略している。なお、種別（各駅停車、急行）ごとに駅間の最小走行時間の値が示されている。例えば駅Ａと駅Ｂ間に記載された（６，４）は、各駅停車の最小走行時間は６分、急行の最小走行時間は４分であることを意味する。
【００８０】
以下では、この前詰めダイヤの各ノードｊの時刻をｔ０ｊとする。この前詰めダイヤでは、アークが定められたノードｉ，ｊ間において、時刻の差分ｔ０ｊ−ｔ０ｉは、必ず、このアークに定められた最小インターバル時間以上となる。したがって、この前詰めダイヤにおけるノードｉ，ｊの間の余裕時間（Ｍ０ｉ，ｊとする）は、必ず非負である。余裕時間Ｍ０ｉ，ｊは、（ノードｊの時刻−ノードｉの時刻）−最小インターバル時間で計算される。“−”は減算を表す。
【００８１】
図２３（Ａ）は、図２０に示すブロック化後のダイヤのアークに対する余裕時間を計算する例を示す。ノード４とノード１２の間の時刻の差分は１（＝１６−１５）となっており、これはノード４とノード１２の間の最小インターバル時間である１（図８参照）に等しい。この場合、余裕時間Ｍ０４，１２は０（＝１−１）である。また、ノード１とノード１０の間の時刻の差分は６（＝６−０）となっており、これはノード１とノード１０の間の最小インターバル時間である２（図８参照）よりも大きい。この場合、余裕時間Ｍ０１，１０は４（＝６−２）である。
【００８２】
ここで、各ブロックｂｋ（集合Ｂの要素である）に対し、変数ｘｋ（＞＝０）を定義する。変数ｘｋは、前詰めダイヤに対し何分時刻を調整するか、すなわち時刻の調整量を表す。前詰めダイヤに対して変数ｘｋだけ各ブロックをシフトさせた新たなダイヤを作成した場合、各ブロックにおけるノードｊの時刻ｔｊは、以下のように計算される。
ｔｊ＝ｔ０ｊ＋ｘｂ（ｊ）      （２）
ここでｂ（ｊ）はノードｊが属するブロックのＩＤを示す。ｔ０ｊは、前詰めダイヤにおけるノードｊの時刻である。ｘｂ（ｊ）は、前詰めダイヤにおけるノードｊが属するブロックをシフトさせる時間（ブロックに対する時刻の調整量。この調整量はブロック内の各ノードに共通に適用される）を表す。
【００８３】
また新たに作成されたダイヤにおけるノードｉ，ｊ間のアークの余裕時間（Ｍｉｊ）は、以下の式で表される
Ｍｉｊ＝Ｍ０ｉｊ＋ｘｂ（ｊ）−ｘｂ（ｉ）      （３）
【００８４】
図２３（Ｂ）は、図２３（Ａ）の状態において、ｘ０＝０（ブロック０を移動させない），ｘ１＝１（ブロック１を１分、正の時間方向にシフトさせる），ｘ２＝２（ブロック２を２分、正の時間方向にシフトさせる）の場合に、各ブロックをシフトさせた結果得られる新たなダイヤの例を示す。
図２３（Ｂ）において各ノードの時刻は、以下のように計算される。
ｔ１＝ｔ０１＋ｘ０＝０＋０＝０      （４−１）
ｔ２＝ｔ０２＋ｘ０＝６＋０＝６      （４−２）
ｔ３＝ｔ０３＋ｘ１＝７＋１＝８      （４−３）
ｔ４＝ｔ０４＋ｘ１＝１５＋１＝１６      （４−４）
ｔ１０＝ｔ０１０＋ｘ２＝６＋２＝８      （４−５）
ｔ１１＝ｔ０１１＋ｘ２＝１０＋２＝１２      （４−６）
ｔ１２＝ｔ０１２＋ｘ２＝１６＋２＝１８      （４−７）
となる。
【００８５】
また、アークの余裕時間は、以下のように計算される。
Ｍ１，１０＝Ｍ０１，１０＋ｘ５−ｘ０＝２＋２−０＝４      （５−１）
Ｍ３，１１＝Ｍ０３，１１＋ｘ５−ｘ１＝１＋２−１＝２      （５−２）
Ｍ４，１２＝Ｍ０４，１２＋ｘ５−ｘ１＝０＋２−１＝１      （５−３）
【００８６】
［密度条件処理部５２３］
密度条件処理部５２３は、本数条件が設定された各ノード（図１１の例ではＣ駅の発イベントを有するノード）について、当該各ノードを配置可能な時刻範囲（上限時刻及び下限時刻）を導出する。
【００８７】
図２４は、密度条件処理部５２３の処理の一例を示すフローチャートである。本フローチャートの説明において、本数条件が設定されたノードをカウント対象ノードと呼ぶ。
【００８８】
まずステップＳ１１では、カウント対象ノードを時刻順にソートし、ノード配列ａに格納する。ａ［ｋ］は、ノード配列のｋ番目のノードを表す。なお、カウント対象ノードは、記憶部１１１に格納されているダイヤ２１０から特定してもよいし、ネットワーク作成部５２０で作成されたネットワークから特定してもよいし、前詰めダイヤ作成部５２２で作成された前詰めダイヤ３００から特定してもよい。
【００８９】
次に、本数条件が設定された時間帯（時刻スロット（ｔ））ごとに（ステップＳ１２）、その時刻スロット（ｔ）に割り当てるノードを本数Ｎ（ｔ）分だけ時刻の早いノードから優先的にノード配列から選択する（ステップＳ１３）。そして、選択したＮ（ｔ）個のノードｊに対して、時刻スロット（ｔ）の開始時刻ｓｔａｒｔ（ｔ）を下限時刻Ｌｊに設定し，時刻スロット（ｔ）の終了時刻を表すｅｎｄ（ｔ）を上限時刻Ｕｊに設定する処理を行う（Ｓ１４）。
【００９０】
具体例を示す。前述した図１９の例において、カウント対象ノードを各駅停車の中間駅（Ｃ駅）とする場合、そのノード配列は、［１３，５，２１，３８，３０，５４、４６，・・・］となる。
１時間あたりの列車本数が５時台（＝時刻スロット（５））、６時台（＝時刻スロット（６））、７時台（＝時刻スロット（７））の順に、［３，３，５，・・・］と定められているとする（図１１参照）。ｓｔａｒｔ（５）＝５：００、ｅｎｄ（５）＝５：５９、ｓｔａｒｔ（６）＝６：００、ｅｎｄ（６）＝６：５９、ｓｔａｒｔ（７）＝７：００、ｅｎｄ（７）＝７：５９、・・・である。このとき、ノード配列の最初の３つ（１３，５，２１）を５時台に割り当て、次の３つ（３８，３０，５４）を６時台に割り当て・・・となる。この結果、ノード配列の各ノードの下限時刻Ｌｊ及び上限時刻Ｕｊは、以下のようになる。ノード４６以降も同様にして計算される。
Ｌ１３，Ｌ５，Ｌ２１＝５：００，Ｕ１３，Ｕ５，Ｕ２１＝５：５９
Ｌ３８，Ｌ３０，Ｌ５４＝６：００，Ｕ３８，Ｕ３０，Ｕ５４＝６：５９
【００９１】
このように、各ノードｊの時刻の下限Ｌｊと上限Ｕｊの組で、本数条件を表現することができる。なお、本数条件が設定されていないノードについては、Ｌｊ＝−∞，Ｕｊ＝∞などと設定しておくことにする。
【００９２】
［評価指標作成部５２４］
評価指標作成部５２４は、平準化条件（バランス条件）、速達性、及び遅延ロバスト性のそれぞれに関する評価指標を作成する。後述する最適化処理では、これらの評価指標の重み付きの和を評価指標（総合指標）とする。
【００９３】
上述した記載において、ブロックｂｋをシフト（遅延）させる時間を表す変数としてｘｋ（＞＝０）を定義したが、各ノードｊのシフト時間の期待値を表す変数として、μｊを定義する。アークの遅延を１次遅延と呼び、アークの遅延によって引き起こされるノードの遅延を２次遅延と呼ぶ。各ノードｊの遅延時間の期待値は、２次遅延時間の期待値である。
【００９４】
後述するように、各アークに対し、異なる１次遅延時間を与えるＳ個の複数シナリオ（ｓ＝１，２，．．．，Ｓ）による遅延シミュレーションを行うことを考える。ノードｊのシナリオｓでの２次遅延の大きさｙｓｊとする。この場合、ノードｊの遅延時間の期待値μｊは、各シナリオｓの２次遅延時間ｙｓｊの平均値となるので、以下のように表される。
【数２】
2020203549.tif 000004
｜Ｓ｜＝１の場合は、１回だけ遅延シミュレーションを行う場合に相当する。
【００９５】
以下、これらの変数ｘｋ及び変数μｊを用いて、評価指標の式を作成する。
【００９６】
＜平準化の評価指標（バランス条件の評価指標）＞
最初に、ダイヤの平準化の評価指標（バランス条件を満たすための評価指標）について述べる。
ダイヤのバランス条件は、図１４で述べたように、あるノードの前ノードの時刻との時間差と、当該ノードの後の時刻との時間差との差分（Ｄとする）に基づいて表される。したがって、ある駅（図１４の例では駅Ｃ及び駅Ａ）を発する全ての発ノードに関して、以下の式（７）を計算し、これらを最小化すればよい。
Ｄ＝［次のノードの発時刻−現ノードの発時刻］−［現ノードの発時刻−前のノードの発時刻］（７）
【００９７】
ここで、次ノードをｎ（ｊ）、前ノードをｐ（ｊ）で表すと、現ノード、次ノード及び前ノードの発時刻は、以下のように表される。
現ノードの発時刻＝ｔ０ｊ＋ｘｂ（ｊ）      （７）
次ノードの発時刻＝ｔ０ｎ（ｊ）＋ｘｂ（ｎ（ｊ））      （８）
前ノードの発時刻＝ｔ０ｐ（ｊ）＋ｘｂ（ｐ（ｊ））      （９）
【００９８】
このことから、この平準化の評価指標の最小化は、以下の式で表される。ｚｊは、上記差分Ｄの絶対値の上限値を表す変数である。
【数３】
2020203549.tif 000005
【００９９】
このように各ノード（イベント）の時刻の調整量を表す変数ｘｂ（ｊ）に基づき、評価対象となる駅（第２の停車位置）に関するイベント（第２イベント）の間隔の平準化に関する評価指標（第１評価指標）を作成する。また、この評価指標の最小化を定式化する。第２イベントは、上記の例では駅Ａ、Ｃの発ノードに対応する。第１評価指標は、第２イベントと第２イベントの前のイベントとの時刻の差と、第２イベントと第２イベントの次のイベントとの時刻の差と、の差分Ｄの絶対値の総和を表す。
換言すれば、第１評価指標は、第２の停車位置を出発する時刻、第２の停車位置に到着する時刻又は第２の停車位置を通過する時刻の間隔の平準化に関する指標である。この場合、第１評価指標は、時刻差Ａと時刻差Ｂとの差分の絶対値の総和を表す。時刻差Ａは、第２の停車位置を出発する時刻、第２の停車位置に到着する時刻又は第２の停車位置を通過する時刻と、第２の停車位置の前の停車位置を出発する時刻、当該前の停車位置に到着する時刻又は当該前の停車位置を通過する時刻との差である。時刻差Ｂは、第２の停車位置を出発する時刻、第２の停車位置に到着する時刻又は第２の停車位置を通過する時刻と、第２の停車位置の次の停車位置を出発する時刻、次の停車位置に到着する時刻又は次の停車位置を通過する時刻との差である。
【０１００】
＜速達性の評価指標＞
次に、ダイヤの速達性の評価指標は、下記のように、各スジの所要時間の和として表される。
【数４】
2020203549.tif 000006
【０１０１】
式（１１）の最小化を考える。この値は変数ｘｂと変数μｊにより、以下の式で表すことができる。ＶＳ，ＶＦは、それぞれ、スジの最初のノード集合および最後のノード集合を表すものとする。前述したようにｘｂ（ｊ）は、ノードｊが属するブロックをシフトさせる（遅らせる）時間を表す。
【数５】
2020203549.tif 000007
【０１０２】
このように少なくとも１つの各スジの評価区間における走行時間の総和に関する評価指標（第２評価指標）を作成する。また、この評価指標の最小化を定式化する。上記の例では評価区間は始発駅と終着駅であるが、評価区間は、評価開始駅と評価終了駅として任意に設定できる（図１５参照）。
【０１０３】
＜遅延ロバスト性の評価指標＞
最後に、ダイヤの遅延ロバスト性とは、遅延の影響を受けにくさを表すものである。例えば、遅延ロバスト性の評価指標は、以下の式で表すことができる。対象ノード（評価ノード）は遅延を評価する対象となるノード（図１６参照）である。例えば評価対象となる駅の発ノード（発イベント）である。
【数６】
2020203549.tif 000008
【０１０４】
式（１３）の値の最小化を考える。この最小化の値はμｊを用いて表すことができる。つまり、評価ノードの集合をＶＥとして、以下のように表すことができる。
【数７】
2020203549.tif 000009
それ以外にも、遅延時間の分散も考慮し、一定時間以上の遅延の確率などを評価指標としてもよい。
【０１０５】
このように複数のイベント間の遅延時間の分布情報に基づき、評価対象となる駅（第３停車駅）のイベント（第３イベント）の遅延時間に関する評価指標（第３評価指標）を作成する。また、第３評価指標の最小化を定式化する。第３評価指標は一例として、第３イベントの遅延時間の平均値の総和を表す（式１３参照）。
換言すれば、第３評価指標は、第３の停車位置を出発する時刻、第３の停車位置に到着する時刻、又は第３の停車位置を通過する時刻に対する遅延時間を評価するための指標である。この場合、第３評価指標は、第３の停車位置を出発する時刻、第３の停車位置に到着する時刻、又は第３の停車位置を通過する時刻に対する遅延時間の平均値の総和を表す。
【０１０６】
［最適化部５２５］
最適化部５２５、評価指標作成部５２４で作成された評価指標の重み付け和により定義される目的関数（評価関数）と、複数の車両スジの配置間隔に関する制約条件を含む１つ以上の制約条件を作成し、制約条件を満たすように、目的関数を最小化することで、変数（ｘｂ（ｊ）、μｊ等）の最適解もしくは準最適解を求める。最適化部５２５は、求めた変数の値（調整量）を記憶部１１６に格納する。
【０１０７】
最適化部５２５が作成する目的関数の一例を式（１５）に示す。式（１６）〜式（２１）は制約条件の一例である。
【数８】
2020203549.tif 000010
【０１０８】
ここで変数は以下の通り定義され、全て非負の連続変数である。ただし、添え字ｂ、ｓ、ｊはそれぞれ集合Ｂ，Ｓ，Ｖ上で定義される。
・ｙｓｊ：ノードｊのシナリオｓでの２次遅延の時間の大きさ。
・μｊ：ノードｊの２次遅延の平均値。
・ｘｂ：ブロックｂを前詰めダイヤからシフトさせる時間の大きさ（＞＝０）。この時間をシフト値又は調整量と呼ぶ。なおノードｊはブロックｂ（ｊ）に属するので、ノードｊを遅らせる時間はｘｂ（ｊ）により与えられる。
・ｚｊ：前述した差分Ｄの絶対値の上限値。すなわち、ノードｊの前ノードの時刻との時間差と、ノードｊの後ノードの時刻の時間差との差分の上限値（前後のノードのバランスの崩れ度合い）
・Ｍｉ，ｊ：アーク（ｉ，ｊ）に対するマージン時間。
【０１０９】
次に定数は以下の通り定義される。
・Ｖ＝｛１，２，．．．，Ｖ｝はノードの集合。ＶＳは始発駅ノードの集合、ＶＦは終着駅ノードの集合、ＶＥは遅延を評価するノード（評価ノード）の集合、ＶＢは平準化したいノード（バランス条件の対象となるノード）の集合。
・Ａ：アークの集合。ｐｒｅｖ（ｊ）は、ノードｊの時刻より前の時刻を持つノードの集合。
・Ｂ：変数ｘの添え字集合。変数ｘをシフト変数（バッファ変数）ｘと呼ぶこともある。
・Ｓ＝｛１，２，．．．，Ｓ｝はシナリオの集合。
・ｄｓｉ，ｊ：シナリオｓにおけるノードｉ，ｊ間のアークに対する１次遅延時間。
・Ｌｊ：ノードｊの下限時刻，Ｕｊ：ノードｊの上限時刻。
・ｂ（ｊ）：ノードｊが所属するブロックのＩＤ
・ｐ（ｊ）：ノードｊと同一駅のノードで、手前のスジの発（ｏｒ通過）ノードのＩＤ。
・ｎ（ｊ）：ノードｊと同一駅のノードで、次のスジの発（ｏｒ通過）ノードのＩＤ。
・ａ０（ｊ）：ノードｊの最速時刻（前詰めダイヤにおけるノードｊの時刻）。
・Ｍ０ｉ，ｊ：前詰めダイヤにおけるアーク（ｉ，ｊ）に対するマージン時間。
・λ１，λ２，λ３：各評価指標の重みであり、予め与えておく。
【０１１０】
以下では、各アーク（ｉ，ｊ）の遅延時間が、Ｓ個の複数シナリオ（ｓ＝１，２，．．．，Ｓ）ごとに異なる値ｄｓｉ，ｊとして与えられる場合について述べる。ここでｄｓｉ，ｊはイベント間遅延分布(たとえば図１８の幾何分布など)に従って発生させ、この結果得られる２次遅延時間の分布を考える。つまり複数回のシナリオｓを考えて、その２次遅延の平均をμｋとする。式（１６）は、各ノードｊの平均遅延時間μｊが、各シナリオｓの２次遅延時間ｙｓｊの平均により与えられることを表す。またノードｉ，ｊ間のアークに与えられる余裕時間（マージン時間）は、前に述べたとおり式（１７）により与えられる。
【０１１１】
次に式（１８）〜式（１９）は、シナリオｓのシミュレーションにおいて、各ノードの２次遅延時間を得る処理に相当する。なおシナリオｓにおけるノードｉ，ｊ間のアークに対する１次遅延時間はｄｓｉ，ｊとする。このとき、各ノードｊの２次遅延時間は、ノードｊにつながる直前のノードｉ（ｐｒｅｖ（ｊ）の要素である）の２次遅延時間と、ノードｉ，ｊ間で発生する１次遅延時間ｄｉ，ｊおよび余裕時間Ｍｉ，ｊを用いて、以下のように表される。
【数９】
2020203549.tif 000011
【０１１２】
この式（２２）を最初のノードから順に適用することで、結果的に全てのノードの２次遅延時間ｙｓｊを得ることができる。以上を一次不等式で表したのが、式（１８）〜式（１９）である。
【０１１３】
図２５は、ノードｊの２次遅延時間の算出を説明するための図である。あるノードｊが自列車の前ノードｉ１と、先行列車の前ノードｉ２との２つのノードの遅延の影響を受ける場合、自列車の前ノードｉ１からの遅延時間は、ｙｉ１＋ｄｉ１，ｊ−Ｍｉ１，ｊと表される（余裕時間Ｍｉ１，ｊを超えた分が遅延時間になる）。また、ノードｊの先行列車の前ノードｉ２からの遅延時間は、ｙｉ２＋ｄｉ２，ｊ−Ｍｉ２，ｊと表される（余裕時間Ｍｉ２，ｊを超えた分が遅延時間になる）。遅延は大きい値が伝播するので、これらのうちの最大値を選択（式（２２）内の内側のｍａｘ関数）すればよい。さらに通常、ダイヤにおいては所定の時刻よりも早く出発することは許されないため、この選択した値と０の内、大きな値を選択し（式（２２）内の外側のｍａｘ関数）、選択した値を、ｙｊと考えればよい。
【０１１４】
次に式（２０）は、各ブロックの上限時刻及び下限時刻を制約として与えるものであり、この式におけるＬｊ，Ｕｊは、本数条件に基づき算出した各ノードの時刻の上下限値を表す値である。式（２０）は本数条件に基づく制約条件であり、複数のスジの配置間隔に関する制約条件の一例である。
【０１１５】
最後に式（２１）は、上で述べた平準化のため（バランス条件を満たすため）の不等式である。
【０１１６】
以上の式（１５）〜式（２１）によって表される数理計画モデルは、線形計画となっており、例えば、Ｇｕｒｏｂｉ  Ｏｐｔｉｍｉｚｅｒ，ＣＰＬＥＸなどの数理計画ソルバーを用いることにより解くことができる。また、ＧＡ（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ），ＳＡ（ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ）などのメタヒューリスティック手法を用いて解いてもよい。結果として、ｘｂ（ｊ），μｊ，ｚｊに関する最適解もしくは準最適解を求めることができる。求めたｘ（ｘｂ（１），ｘｂ（２），ｘｂ（３），・・・）は、前詰めダイヤに対する各ノードｊのシフト値を表す。
【０１１７】
最適化部５２５は、求めた変数ｘ（ｘｂ（１），ｘｂ（２），ｘｂ（３），・・・）をシフト情報として記憶部１１６に格納する。変数ｘに加えて、変数μ（μ１，μ２，μ３，・・・）を記憶部１１６に格納してもよい。また変数ｚ（ｚ１，ｚ２，ｚ３，・・・）の値を記憶部１１６に格納してもよい。
【０１１８】
［出力ダイヤ作成部３９０］
出力ダイヤ作成部３９０は、記憶部１１６に格納されている各ノードのシフト値（調整量）ｘｂ（ｊ）と、記憶部１１５に格納されている前詰めダイヤ３００とに基づき、出力ダイヤ５１０を作成する。前詰めダイヤ３００における各ノードｊの時刻に、各ノードのシフト値ｘｂ（ｊ）を加算することで、出力ダイヤ５１０が得られる。これは、前詰めダイヤ３００における各ノードを、各ノードのシフト値ｘｂ（ｊ）だけ時間軸に沿って移動させる（遅らせる）ことに相当する。なお、同じブロックに属するノードのシフト値は同じである。前述した図２０の例では、ノード１のシフト値ｘｂ（１）＝ノード２のシフト値ｘｂ（２）であり、これは、ブロックｂ０（ブロックＩＤ＝０のブロック）のシフト値に相当する。
【０１１９】
図２６は、出力ダイヤ５１０を得るプロセスを表すデータである。このデータは、ノードＩＤ、スジＩＤ、時刻、駅、最速時刻、ブロックＩＤ、シフト値、シフト後時刻（調整後時刻）を含む。最速時刻は、前詰めダイヤにおけるノードの時刻である。ブロックＩＤは、各ノードが属するブロックのＩＤである。シフト値は、当該ノードが属するブロックのシフト値である。シフト後時刻は、最速時刻にシフト値を加算した時刻である。
【０１２０】
図２７は、図２６のデータを、横軸を時刻、縦軸を駅として、各列車のスジをプロットしたグラフである。各ノードの位置として、シフト後時刻を用いてグラフを描いている。このグラフは、出力ダイヤ５１０に対応する。図２６のデータからダイヤとして必要な情報（例えばノードＩＤ、スジＩＤ、時刻、駅、種類、シフト後時刻など）を抽出したものを出力ダイヤ５１０としてもよい。出力ダイヤ５１０では、バランス条件、速達性、遅延ロバスト性、本数条件等が満たされている。以下、別の具体例を用いて、バランス条件、速達性、遅延ロバスト性、本数条件等が満たされている出力ダイヤについて説明する。
【０１２１】
図２８は、図２６とは別の例に係るダイヤに対して作成した出力ダイヤ５１０を表すグラフである。列車（スジ）１〜１２は、Ａ駅を出発駅とし、Ｅ駅を終着駅としている。実線で示すスジが各駅停車の列車のスジ、破線で示すスジが急行列車のスジを表している。
【０１２２】
この例では、本数条件（１時間あたりの列車本数）として、Ｃ駅の発ノードを対象に、５：００〜６：００では３本、６：００〜７：００では３本、７：００〜８：００では３本・・・を指定している。図示の出力ダイヤ５１０において、５：００〜６：００では各駅停車の列車が２本、急行列車が１本の計本が、含まれている。６：００〜７：００では各駅停車の列車が１本、急行列車が２本の計３本が含まれている。７：００〜８：００では、各駅停車の列車が３本、急行列車が２本、含まれている。よって、本数条件は満たされている。
【０１２３】
またこの例では、バランス条件がＣ駅の発ノードと、Ａ駅の発ノードとを対象に、種別（各駅停車、急行）別に、設定されている。Ａ駅の発ノードを見ると、各駅停車の列車間は概ね均等の間隔であり、急行列車間の間隔も概ね均等である。また、Ｃ駅の発ノードを見ると、各駅停車の列車間は概ね均等の間隔であり、急行列車間の間隔も概ね均等である。よって、バランス条件は満たされている。なお、各駅停車と急行列車との間に対してバランス条件は設定されていないため、例えば各駅停車の列車のＣ駅の発ノードと、急行列車のＣ駅の発ノードとが近接していても問題ない。
【０１２４】
またこの例では、遅延が起こりにくい（余裕時間を超えないもしくは超えにくい）ように各ノードの時刻が最適化されており、遅延路バスト性も満たされている。例えば黒丸を付けた箇所で、もし急行列車９がダイヤの時刻よりＤ駅の通過が遅れても、各駅停車の列車８は、Ｄ駅の発車を余裕時間内で行うことができ、遅延は起こらない、もしくは起こりにくい。
【０１２５】
またこの例では、各列車が始発から終着駅までの区間をできるだけ速く到達するように各列車の計画（最適化）されており、速達性も満たされている。
【０１２６】
出力ダイヤ５１０の形式は、図２７又は図２８の例に限定されない。例えば、注目すべき駅（例えば終着駅や分岐駅など）の一部の列車・駅に対して出力ダイヤ５１０を出力するような手法を採ってもよいし、またユーザが設定した一部の列車・駅に対して出力ダイヤ５１０を出力するような手法を採ってもよい。出力ダイヤ５１０を、ノード毎の属性からなる表形式で表してもよいし、表形式と同等のデータであってもよい。また、遅延ロバスト性、速達性及びバランス条件などの指標に関して、ダイヤ全体の代表値や、列車毎の値などを表示してもよい。
【０１２７】
以上のような処理により、最終的に制約条件又は各種性能を満たす出力ダイヤ５１０が得られる。表示部４００は、出力ダイヤ５１０を表示する。また表示部４００は、変数ｘ（ｘｂ（１），ｘｂ（２），ｘｂ（３），・・・）を表示してもよい。また表示部４００は、変数μ（μ１，μ２，μ３，・・・）を表示してもよい。また表示部４００は、変数ｚ（ｚ１，ｚ２，ｚ３，・・・）を表示してもよい。
【０１２８】
また表示部４００は、当該イベントの遅延分布または期待遅延時間，Ｘ分以上遅れる確率，遅れ時間の期待値・分散、遅れ時間のＸパーセンタイル値などの統計値を表示してもよい。
【０１２９】
これらは、各シナリオにおける遅延時間ｙｓｊを遅延時間のヒストグラムとみなすことで、計算できる。式（１５）の各項で表されるバランス条件、速達性、遅延ロバスト性の値を出力してもよい。これらは単位が（分）となっており、ユーザの直感的に理解できる値となっている。
【０１３０】
また追加的な入力情報が得られている場合に、得られた出力ダイヤと組み合わせることで、下記のような出力情報を得てもよい。
・ある列車・駅（複数であってもよい）において、Ｙ分遅れた場合にＣ円のペナルティコストが発生する場合の、遅延によるペナルティコストの期待値。この期待値は、各シナリオにおける遅延時間ｙｓｊを遅延時間のヒストグラムとみなすことで、計算できる。
・乗客のＯＤ（乗降駅の統計値）を用いる場合の、遅延による影響人数の期待値。この期待値は、上記同様ｙｓｊを用いて計算できる。
【０１３１】
また出力ダイヤの全体を示すのではなく、一部だけを示すようにして、その一部について、上記の指標を計算して表示するような出力であってもよい。一部の取り出し方としては、特定の区間、特定の時間帯、特定の列車（群）もしくは、その組合せなどが考えられる。
【０１３２】
図２９は、本数条件、平準化条件（バランス条件）、速達性、及び遅延ロバスト性に関するパラメータを入力し、最適化を実行する画面の例を示している。
【０１３３】
図２９のプルダウンリスト２〜７は平準化（バランス条件）および本数条件の対象ノードである基準ノードＶＢの設定と、時間帯の設定とを行うためのプルダウンリストである。プルダウンを用いた設定は、ユーザが入力手段を用いて行う。
【０１３４】
プルダウンリスト２では平準化及び本数条件の基準駅を選択する。
【０１３５】
プルダウンリスト３では列車種別の選択を行う。登録済みのリスト化された列車種別名の中から種別を選択することができる。デフォルト値は、一例として、全ての種別を表す“すべて”である。
【０１３６】
プルダウンリスト４では平準化する時間帯の幅を選択する。例えば、“3時間”, “2時間”,“1時間”,“30分”などを選択できる。デフォルト値は、一例として”1時間”である。
【０１３７】
プルダウンリスト５では、プルダウンリスト４で選択した時間帯のオフセット間隔を選択する。オフセット間隔は、上記時間帯の開始時刻を所定の開始時刻（例えば５：００）からどれだけずらすかを表す。デフォルト値は、一例として0分である。プルダウンリスト４で選択した時間帯が30分の場合は”0分”,”10分”,”15分”,”20分”などの値を選択できる。選択した時間帯が1時間の場合は”0分”,”15分”,”30分”,”45分”などの値を選択できる。
【０１３８】
プルダウンリスト６では、プルダウンリスト２で選択した基準駅に対して、平準化及び本数条件の対象となるタイミングを選択する。例えば、“出発時”,”到着時”のいずれを選択できる。デフォルト値は、一例として、“出発時”である。
【０１３９】
プルダウンリスト７は、平準化の対象又は本数条件の本数のカウントの対象として基準駅の通過を含めるか否かを設定する。一例として、“通過を考慮しない”、“通過を考慮する”を選択できる。デフォルト値は、一例として“通過を考慮しない”である。
【０１４０】
次にプルダウンリスト８、９、１０は、各評価指標（λ１，λ２，λ３）の設定用のプルダウンリストである。前述したように、λ１，λ２，λ３は、平準化（バランス条件）、速達性及び遅延ロバスト性のそれぞれの評価指標に関する重みである。
【０１４１】
例えば、“標準”（たとえば1.0）,“重視する”(例えば10.0),“重視しない”(例えば0.1)を選択できる。デフォルト値は、一例として、“標準”である。なおλ１，λ２，λ３については、ここで設定した値に対し、総ノード数、総スジ数、又は評価対象ノード数などで割った値を用いてもよい。プルダウンリスト８、９、１０により、ユーザがより重視する評価指標を設定できるため、ユーザが効率的に試行錯誤を行い、求める方向性のダイヤを得ることができる。
【０１４２】
次に項目１１〜１９は本数条件の設定用の項目である。
【０１４３】
項目１３は、プルダウンリスト４、５で設定した各時間帯を表す。各時間帯に対する2方向(たとえば上りと下り)の本数を、項目１１、１２、１４〜１８で設定可能となっている。
【０１４４】
項目１１、１２は方向名であり、例えば上り又は下りなどの名称を表す。図では項目１１が「上り」方向、項目１２が「下り」方向を表しているが、逆にしてもよい。
【０１４５】
項目１５、１８は、「上り」及び「下り」の各方向に対する設定本数（時間帯別本数）を示す。項目１５、１８には、デフォルトでは、元ダイヤにおける各時間帯に対する本数(つまり当該時間帯に含まれる基準ノードの個数)が表示されている（図では本数の記載が省略されており、空白になっている）。
【０１４６】
項目１４及び項目１６は、「上り」の方向に対し、前後の時間帯に本数を移動するためボタンである。項目１７及び項目１９は、「下り」の方向に対し、前後の時間帯に本数を移動するためボタンである。項目１４、１６、１７、１９はそれぞれボタンとして、押下可能である。
【０１４７】
例えば、項目１４は、ボタン押下により、項目１５の「上り」の時間帯別本数を1減らし、1つ上の行の「上り」の時間帯別本数を1増やす機能である。また項目１６は、ボタン押下により、項目１５の「上り」の時間帯別本数を1減らし、1つ下の行の「上り」の時間帯別本数を1増やす機能である。項目１７は、ボタン押下により、項目１８の「下り」の時間帯別本数を1減らし、1つ上の行の「下り」の時間帯別本数を1増やす機能である。また項目１９は、ボタン押下により、項目１８の「下り」の時間帯別本数を1減らし、1つ下の行の「下り」の時間帯別本数を1増やす機能である。なお、先頭の行には、項目１４及び項目１７は表示されず、また項目１５の「上り」の時間帯別本数が0の時は、項目１４を押下できない。また項目１６は、最終行には表示されず、また「上り」の時間帯別本数が0の時は、項目１６を押下できない。
【０１４８】
以上の項目１１〜１９は、本数設定の合計が、元のダイヤの総本数と異なってしまい、解が得られなくなることを防ぐための入力インタフェースである。この入力インタフェースにより、効率的に入力作業を行うことができる効果がある。
【０１４９】
最後に、以上を入力した上で、ユーザがボタン１を押下することで、ダイヤ処理部５００による処理が実行される。
【０１５０】
図２９は、図１のダイヤ作成装置による処理の一例を示すフローチャートである。ネットワーク作成部５２０が、記憶部１１１内のダイヤ（第１ダイヤ）２１０とイベント間インターバル情報２１１に基づき、ダイヤのネットワークを作成する（Ｓ２１）。
【０１５１】
ブロック作成部５２１が、ダイヤのネットワークに基づき、相対位置を変更できないイベント（ノード）群を１つのブロックにまとめることにより、複数のブロックを作成する（Ｓ２２）。例えばアークでの速度が一定の場合は、アークの両端のノードの相対位置は変更できないため、これらのノードを１つのブロックに含める。アーク間の速度が変更可能な場合は、個々のノードをそれぞれブロック（１つのノードを含むブロック）とすればよい。
【０１５２】
前詰めダイヤ作成部５２２が、時間的に手前にあるブロックに属するノードの時刻から順に最早の時刻を定めていくことで、全てのノードの時刻を暫定的に決定した前詰めダイヤを作成する（Ｓ２３）。
【０１５３】
密度条件処理部５２３が、記憶部１１２内の本数条件情報２２０に基づき、各スジの評価対象のノード（評価対象となる駅及びイベントの組）について、時間帯ごとに指定数のノードが含まれるように、当該ノードの下限時刻及び上限時刻の制約条件を作成する（Ｓ２４）。
【０１５４】
評価指標作成部５２４が、記憶部１１２内のバランス条件情報２２１に基づき、各ブロックのシフト量（各ブロックに含まれるノードの時刻の調整量）を表す変数を含む、平準化に関する評価指標（第１評価指標）を作成する（Ｓ２５）。また、評価指標作成部５２４が、記憶部１１３内の速達性評価条件情報２３０に基づき、上記変数を含む、速達性に関する評価指標（第２評価指標）を作成する（同Ｓ２５）。また、評価指標作成部５２４が、記憶部１１４内の遅延評価対象情報２４０及び遅延時間分布情報２４１に基づき、上記変数を含む、遅延ロバスト性に関する評価指標（第３評価指標）を作成する（同Ｓ２５）。
【０１５５】
最適化部５２５が、評価指標作成部５２４で作成された評価指標の和をとることにより目的関数（評価関数）を作成する（Ｓ２６）。最適化部５２５は、目的関数を、ステップＳ２４で作成された制約条件及びその他の制約条件の元、最適化又は準最適化（例えば最小化又は閾値以下など）することにより、変数の値（調整量又はシフト値）を算出する（同Ｓ２６）。
【０１５６】
出力ダイヤ作成部３９０は、算出された変数の値と、前詰めダイヤ３００とに基づき、出力ダイヤ５１０を作成する（Ｓ２７）。具体的には、算出された変数の値を、前詰めダイヤ３００における各ノード（イベント）の時刻に加算することにより、出力ダイヤ５１０を作成する。作成された出力ダイヤ５１０は記憶部１１７に格納される。表示部４００は、記憶部１１７に格納されている出力ダイヤ５１０を表示する。
【０１５７】
以上、本実施形態によれば、平準化、速達性及び遅延ロバスト性に関する評価指標に基づく目的関数を、本数条件等に基づく制約条件の元、最小化することにより、本数条件、平準化、速達性及び遅延ロバスト性の各種要求を満たしたダイヤを高速に作成することができる。
【０１５８】
（変形例１）
上述した実施形態では前詰めダイヤを作成したが、前詰めダイヤを作成せずに、密度条件処理部５２３以降の処理を行ってもよい。この場合も、各ブロックの移動量として正の値のみならず、負の値もとるように変数ｘを定義することで、本実施形態と同様の処理が可能である。この際、上述した実施形態では、前詰めダイヤを作成する際に各ブロックを最小インターバル時間の制約を満たすように配置したため、上記の最適化処理では考慮する必要はなかった。つまり、前詰めダイヤを生成する時点で、最小インターバル時間の制約を満たす処理をしていた。前詰めダイヤを作成しない場合は、最適化処理における制約条件の一部として、イベント間の時間間隔を、イベント間インターバル情報によって示される時間以上にするとの条件を追加すればよい。このように最小インターバル時間の制約を満たすようにする処理は前詰めダイヤの生成時点で行っても、最適化処理の時点で行ってもよい。
【０１５９】
（変形例２）
元のダイヤの一部を固定する制約条件を追加して、最適化処理を行ってもよい。例えば、Ａ駅の発時刻だけは、元のダイヤと同じ時刻又は特定の時刻を使いたいという場合がある。このような場合は、予め定めたイベントであるＡ駅の発イベント（第４イベント）の時刻を固定する制約条件を追加する。上の定式化においてＵｊ＝Ｌｊ＝ｔ＊ｊとすればよい。ここでｔ＊ｊはノードｊに対して設定したい時刻である。また元ダイヤの時刻をできるだけ守りたい場合は、上の定式化においてＵｊ＝ｔ＊ｊ−Ａ，Ｌｊ＝ｔ＊ｊ＋Ａなどとして、かつＡをできるだけ小さくするような数理モデル化を実施すればよい。
【０１６０】
（変形例３）
上述した複数の評価指標の一部を用いなくてもよい。例えば、速達性条件を評価指標として用いなくてもよい。この場合、λ２＝０とすればよい。構成として、速達性評価条件入力部１３０、速達性評価条件情報２３０及び記憶部１１３は不要である。また、遅延ロバスト性を評価指標として用いなくてもよい。この場合、λ３＝０とすればよい。構成として、遅延評価条件入力部１４０、遅延評価対象情報２４０、遅延時間分布情報２４１及び記憶部１１４は不要である。
【０１６１】
（変形例４）
最適化処理で制約条件を満たす解が得られない場合に、その旨と、その理由をユーザに提示してもよい。例えば、本数条件情報２２０において、１時間あたりの本数が多すぎると、スジ間（異なるスジのノード間）に所定のインターバル時間を取れなくなり、バランス条件を満たす解が得られない場合がある。そのような場合は、その旨と、その理由を表す情報を表示部４００に出力してもよい。
【０１６２】
（変形例５）
評価関数をユーザによって変更可能にしてもよい。例えば、式（１５）のバランス条件、速達性及び遅延ロバスト性のそれぞれの評価指標に関する重みλ１，λ２，λ３を画面から（例えばスライドバーなどで）ユーザが自由に入力できるようにしてもよい。例えばバランス条件をより重視したいユーザは相対的に大きな値をλ１に設定する。このようにして、ユーザが評価関数を自由に調整できる。
【０１６３】
（ハードウェア構成）
図３１に、本実施形態に係るダイヤ作成装置（情報処理装置）１０１のハードウェア構成を示す。本実施形態に係る情報処理装置１０１は、コンピュータ装置１５０により構成される。コンピュータ装置１５０は、ＣＰＵ１５１と、入力インタフェース１５２と、表示装置１５３と、通信装置１５４と、主記憶装置１５５と、外部記憶装置１５６とを備え、これらはバス１５７により相互に接続されている。
【０１６４】
ＣＰＵ（中央演算装置）１５１は、主記憶装置１５５上で、情報処理装置１０１の上述の各機能構成を実現するコンピュータプログラムを実行する。ＣＰＵ１５１が、コンピュータプログラムを実行することにより、各機能構成は実現される。
【０１６５】
入力インタフェース１５２は、キーボード、マウス、及びタッチパネルなどの入力装置からの操作信号を、情報処理装置１０１に入力するための回路である。ダイヤ情報入力部１１０、列車密度条件入力部１２０、速達性評価条件入力部１３０及び遅延評価条件入力部１４０の入力機能を担う部分は、入力インタフェース１５２上に構築されることができる。
【０１６６】
表示装置１５３は、情報処理装置１０１から出力されるデータ又は情報を表示する。表示装置１５３は、例えば、ＬＣＤ（液晶ディスプレイ）、ＣＲＴ（ブラウン管）、及びＰＤＰ（プラズマディスプレイ）であるが、これに限られない。コンピュータ装置１５０から出力されたデータ又は情報は、この表示装置１５３により表示することができる。表示部４００は、表示装置１５３上に構築されることができる。
【０１６７】
通信装置１５４は、情報処理装置１０１が外部装置と無線又は有線で通信するための回路である。通信装置１５４を介して外部装置から情報を入力することができる。外部装置から入力した情報を、ＤＢに格納することができる。ダイヤ情報入力部１１０、列車密度条件入力部１２０、速達性評価条件入力部１３０及び遅延評価条件入力部１４０の通信機能を担う部分は、通信装置１５４上に構築されることができる。
【０１６８】
主記憶装置１５５は、本実施形態の処理を実現するプログラム、及びプログラムの実行に必要なデータ、及びプログラムの実行により生成されたデータなどを記憶する。プログラムは、主記憶装置１５５上で展開され、実行される。主記憶装置１５５は、例えば、ＲＡＭ、ＤＲＡＭ、ＳＲＡＭであるが、これに限られない。各実施形態における各種ＤＢ及び記憶部は、主記憶装置１５５上に構築されてもよい。
【０１６９】
外部記憶装置１５６は、上記プログラム及びプログラムの実行に必要なデータ、及びプログラムの実行により生成されたデータなどを記憶する。これらのプログラムやデータは、本実施形態の処理の際に主記憶装置１５５に読み出される。外部記憶装置１５６は、例えば、ハードディスク、光ディスク、フラッシュメモリ、及び磁気テープであるが、これに限られない。各実施形態における各種ＤＢ及び記憶部は、外部記憶装置１５６上に構築されてもよい。
【０１７０】
なお、上述のプログラムは、コンピュータ装置１５０に予めインストールされていてもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶されていてもよい。また、当該プログラムは、インターネット上にアップロードされていてもよい。
【０１７１】
なお、コンピュータ装置１５０は、プロセッサ１５１、入力インタフェース１５２、表示装置１５３、通信装置１５４、及び主記憶装置１５５を、それぞれ１つ又は複数備えてもよいし、プリンタやスキャナなどの周辺機器を接続されていてもよい。
【０１７２】
また、情報処理装置１０１は、単一のコンピュータ装置１５０により構成されてもよいし、相互に接続された複数のコンピュータ装置１５０からなるシステムとして構成されてもよい。
【０１７３】
なお、本発明は上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記各実施形態に開示されている複数の構成要素を適宜組み合わせることによって種々の発明を形成できる。また例えば、各実施形態に示される全構成要素からいくつかの構成要素を削除した構成も考えられる。さらに、異なる実施形態に記載した構成要素を適宜組み合わせてもよい。
【符号の説明】
【０１７４】
１００：ダイヤ作成装置
１１１〜１１７：記憶部
１１０：ダイヤ情報入力部
１２０：列車密度条件入力部
１３０：速達性評価条件入力部
１４０：遅延評価条件入力部
１５０：コンピュータ装置
１５１：プロセッサ（ＣＰＵ）
１５２：入力インタフェース
１５３：表示装置
１５４：通信装置
１５５：主記憶装置
１５６：外部記憶装置
１５７：バス
３９０：出力ダイヤ作成部
４００：表示部
５００：ダイヤ処理部
５２０：ネットワーク作成部
５２１：ブロック作成部
５２２：前詰めダイヤ作成部
５２３：密度条件処理部
５２４：評価指標作成部
５２５：最適化部
【図１】
2020203549.tif 000012
【図２】
2020203549.tif 000013
【図３】
2020203549.tif 000014
【図４】
2020203549.tif 000015
【図５】
2020203549.tif 000016
【図６】
2020203549.tif 000017
【図７】
2020203549.tif 000018
【図８】
2020203549.tif 000019
【図９】
2020203549.tif 000020
【図１０】
2020203549.tif 000021
【図１１】
2020203549.tif 000022
【図１２】
2020203549.tif 000023
【図１３】
2020203549.tif 000024
【図１４】
2020203549.tif 000025
【図１５】
2020203549.tif 000026
【図１６】
2020203549.tif 000027
【図１７】
2020203549.tif 000028
【図１８】
2020203549.tif 000029
【図１９】
2020203549.tif 000030
【図２０】
2020203549.tif 000031
【図２１】
2020203549.tif 000032
【図２２】
2020203549.tif 000033
【図２３】
2020203549.tif 000034
【図２４】
2020203549.tif 000035
【図２５】
2020203549.tif 000036
【図２６】
2020203549.tif 000037
【図２７】
2020203549.tif 000038
【図２８】
2020203549.tif 000039
【図２９】
2020203549.tif 000040
【図３０】
2020203549.tif 000041
【図３１】
2020203549.tif 000042