(57)【要約】【課題】  列車の運行ダイヤに変更が生じたときに、ダイヤ変更当日と翌日以降の運用計画をあわせて再作成を行う。【解決手段】  再計画手段0110が、ダイヤ変更当日から所定の日数の期間の運用計画を、期間終了時の車両もしくは乗務員の運用終了場所を当初計画された場所に固定した条件で再作成する。運用計画の対象とする列車もしくは列車を分割したセグメントを、変更された運行ダイヤ0121に基づいて当初の計画より変更し、変更した列車もしくはセグメント、及び翌日以降の行路に対して、同一の車両もしくは乗務員を割り当てる各列車もしくはセグメント及び行路が接続するように、当日の運用計画においては列車もしくはセグメントごとに車両もしくは乗務員を割り当て、翌日以降の運用計画においては当初の運用計画において定められた1日分の行路ごとに車両もしくは乗務員を割り当てて、新たな計画を作成する。【選択図】  図１
2010285053.tif 000002
【特許請求の範囲】
【請求項１】
列車の運行ダイヤに変更が生じたときに鉄道車両もしくは乗務員の運用計画の再作成を行う運用計画再作成装置であって、
前記運行ダイヤを入力される入力手段と、
前記鉄道車両もしくは乗務員の当初の運用計画及び入力された前記運行ダイヤを格納する記憶手段と、
ダイヤ変更当日から所定の日数の期間の前記運用計画を、前記期間終了時の前記車両もしくは乗務員の運用終了場所を当初計画された場所に固定した条件で再作成する再計画手段と、
前記再作成した運用計画を出力する出力手段とを備え、
前記記憶手段が格納する前記運用計画は、予め定められた前記複数の前記列車の組み合わせである行路の情報を含み、
前記再計画手段は、
前記記憶手段に格納された運行ダイヤが前記入力により変更されると、前記当初の運用計画及び変更された前記運行ダイヤを前記記憶手段より読み出し、
ダイヤ変更当日の運用計画の対象とする列車もしくは列車を分割したセグメントを、前記運行ダイヤに基づいて前記当初の計画より変更し、
変更した列車もしくはセグメント、及び翌日以降の行路に対して、同一の前記車両もしくは乗務員を割り当てる各列車もしくはセグメント及び行路が接続し、かつ前記運用終了場所の固定条件を満たすように、
当日の運用計画においては前記列車もしくはセグメントごとに前記車両もしくは乗務員を割り当て、
翌日以降の運用計画においては当初の前記運用計画において定められた1日分の前記行路ごとに前記車両もしくは乗務員を割り当てて、
新たな計画を作成することを特徴とする運用計画再作成装置。
【請求項２】
請求項１に記載の運用計画再作成装置であって、
前記再計画手段は、
ダイヤ変更当日に前記車両もしくは乗務員を割り当てる前記列車もしくはセグメント、および翌日以降に前記車両もしくは乗務員を割り当てる前記行路を、ノードとして、前記ノードをリンクで接続したネットワークを生成し、前記ネットワーク上のダイヤ変更時を表す開始ノードから前記期間終了時を表す終了ノードまでの最短経路を、新たな計画とすることを特徴とする運用計画作成装置。
【請求項３】
請求項２に記載の運用計画再作成装置であって、
前記記憶手段が、
前記車両に対する作業実施もしくは乗務員の勤務について、運用日数に基づいて規定した運用条件を格納し、
前記再計画手段は、
前記最短経路が示す計画が前記条件を満たさない場合は、
前記条件を満たすべき期限日より順に遡って、前記条件を満たす、遡った日より前記期限日までの行路の組み合わせを探索し、
前記探索の結果、前記条件を満たす行路の組み合わせが存在する場合は、前記遡った日より期限日までの前記車両もしくは乗務員を割り当てる行路を前記組み合わせに変更することにより、新たな計画を作成することを特徴とする運用計画再作成装置。
【請求項４】
請求項３に記載の運用計画再作成装置であって、
前記期間に前記車両の組成変更が行われる場合は、
前記再計画手段が、
前記組成変更の行われる日で前記期間を分割し、
分割した各期間について、早い期間から順に、前記条件を満たさない場合は前記探索を行い、
最初の期間以外についての前記探索の結果、前記期間に前記条件を満たす行路の組み合わせが存在しない場合は、１つ前の期間に戻って前記探索を行うことにより、新たな計画を作成することを特徴とする運用計画再作成装置。
【請求項５】
請求項２ないし請求項４のいずれか１つに記載の運用計画再作成装置であって、
前記再計画手段が作成した新たな計画を、所定の評価指標に基づいてさらに修正する計画修正手段を備え、
前記計画修正手段は、
前記計画が対象とする列車もしくはセグメント、及び行路をノードとして、前記ノードを時系列順にリンクで接続したネットワークを生成し、前記ネットワークの構造を変更して複数の計画を生成し、前記指標に基づいて前記複数の計画の評価値を算出し、最も評価値が高い計画を採用することを特徴とする運用計画再作成装置。
【請求項６】
請求項２に記載の運用計画再作成装置であって、
前記再計画手段は、
前記生成したネットワーク上のリンクについて、
変更前の前記運用計画を前記ネットワーク上の経路としたときに、前記経路に含まれるリンクの長さを、前記経路に含まれないリンクの長さより小さく設定し、
前記経路に含まれないリンクのうち、
当日の運用に関するノード同士を接続するリンクの長さは、前記リンクの時間的長さに関して非線形かつ単調増加の性質を持つ関数値を設定し、
翌日以降の運用に関するノード同士を接続するリンクの長さは、所定の固定値を設定し、
当日の運用計画に関するノードを始点、翌日の運用計画に関するノードを終点とするリンクであって、前記始点の示す当日の運用終了場所と前記終点の示す翌日の運用開始場所が一致しないリンクの長さは、前記所定の固定値に比して大きな値を設定することを特徴とする運用計画再作成装置。
【請求項７】
請求項１ないし請求項６のいずれか１つに記載の運用計画再作成装置であって、
前記再計画手段が、前記計画の対象であって前記車両もしくは乗務員が割当てられなかった列車もしくはセグメントを検出し、
前記出力手段が、前記検出された列車もしくはセグメントを出力することを特徴とする運用計画再作成装置。
【請求項８】
請求項１ないし請求項６のいずれか１つに記載の運用計画再作成装置であって、
前記再計画手段が、前記車両もしくは乗務員の当日の運用終了場所と翌日の運用開始場所が一致するかを判定し、
前記判定が不一致の場合は、前記出力手段が、前記車両もしくは乗務員を当日の運用終了後に翌日の運用開始場所まで移動させる必要がある旨の情報を出力することを特徴とする運用計画再作成装置。
【請求項９】
列車の運行ダイヤに変更が生じたときに、鉄道車両もしくは乗務員の運用計画の再作成を行う運用計画再作成装置であって、
前記運行ダイヤを入力される入力手段と、
前記鉄道車両もしくは乗務員の当初の運用計画及び入力された前記運行ダイヤを格納する記憶手段と、
ダイヤ変更当日から所定の日数の期間の前記運用計画を、前記期間終了時の前記車両もしくは乗務員の運用終了場所を当初計画された場所に固定した条件で再作成する手段であって、
前記記憶手段に格納された運行ダイヤが前記入力により変更されると、前記当初の運用計画及び変更された前記運行ダイヤを前記記憶手段より読み出し、
ダイヤ変更当日の運用計画の対象とする列車もしくは列車を分割したセグメントを、前記運行ダイヤに基づいて前記当初の計画より変更し、
変更した列車もしくはセグメント及び翌日以降の行路に対して、
ダイヤ変更当日に前記車両もしくは乗務員を割り当てる前記列車もしくはセグメント、および翌日以降に前記車両もしくは乗務員を割り当てる前記行路を、ノードとして、前記ノードをリンクで接続したネットワークを生成し、前記車両もしくは乗務員を前記ネットワーク上に流すアイテムとして、前記アイテムの流れの最適化を演算することにより、同一の前記車両もしくは乗務員を割り当てる各列車もしくはセグメント及び行路が接続し、かつ前記運用終了場所の固定条件を満たすように、前記計画の評価値に基づく計画の再作成を行う再計画手段と、
前記再作成した運用計画を出力する出力手段とを備え、
前記記憶手段が格納する前記運用計画は、予め定められた前記複数の前記列車を組み合わせた行路の情報を含み、
前記再計画手段は、
最適化の目的関数と制約条件を記述した数理モデルを作成し、
前記数理モデルの前記準最適解及び最適解の評価値の推定値を最適化演算により算出して、前記準最適解を新たな計画とし、
前記出力手段は、
前記新たな計画とともに前記準最適解の評価値と最適解の評価値の推定値との差分情報を出力することを特徴とする運用計画再作成装置。
【請求項１０】
請求項９に記載の運用計画再作成装置であって、
前記再計画手段は、
前記制約条件の一部を緩和してラグランジュ緩和問題を構成し、ラグランジュ緩和法を用いて準最適解、及び最適解の評価値の推定値を算出することを特徴とする運用計画再作成装置。
【請求項１１】
請求項９または請求項１０に記載の運用計画再作成装置であって、
前記再計画手段は、ラグランジュ緩和問題をアイテム１個毎の部分問題と車両もしくは乗務員の不足数を決定する部分問題とに分割し、各部分問題を独立に解くことを特徴とする運用計画再作成装置。
【請求項１２】
請求項９ないし請求項１１のいずれか１つに記載の運用計画再作成装置であって、
前記再計画手段は、前記数理モデルで定義されたコストをラグランジュ乗数で調整した値を前記ネットワークのリンクの長さとし、アイテム１個毎の部分問題の最適解を前記ネットワーク上の最短経路問題として算出することを特徴とする運用計画再作成装置。
【請求項１３】
請求項９または請求項１２のいずれか１つに記載の運用計画再作成装置であって、
前記再計画手段は、前記ネットワーク上のダイヤ変更時を表す開始ノードから前記期間終了時を表す終了ノードまでの最短経路問題を、前記ネットワークのノードを削除しながら繰返し解くことにより前記数理モデルの実行可能解を算出することを特徴とする運用計画再作成装置。
【請求項１４】
列車の運行ダイヤに変更が生じたときに鉄道車両もしくは乗務員の運用計画の再作成を行う運用計画再作成方法であって、
前記鉄道車両もしくは乗務員の当初の運用計画を格納するコンピュータの記憶手段が、入力手段により入力された前記運行ダイヤを記憶する第1のステップと、
コンピュータの再計画手段が、ダイヤ変更当日から所定の日数の期間の前記運用計画を、前記期間終了時の前記車両もしくは乗務員の運用終了場所を当初計画された場所に固定した条件で再作成する第２のステップと、
コンピュータの出力手段が、前記再作成した運用計画を出力する第３のステップとを備え、
前記記憶手段が格納する前記運用計画は、予め定められた前記複数の前記列車を組み合わせた行路の情報を含み、
前記第２のステップにおいて、前記再計画手段は、
前記記憶手段に格納された運行ダイヤが前記入力により変更されると、前記当初の運用計画及び変更された前記運行ダイヤを前記記憶手段より読み出し、
ダイヤ変更当日の運用計画の対象とする列車もしくは列車を分割したセグメントを、前記運行ダイヤに基づいて前記当初の計画より変更し、
変更した列車もしくはセグメント及び翌日以降の行路に対して、同一の前記車両もしくは乗務員を割り当てる各列車もしくはセグメント及び行路が接続し、かつ前記運用終了場所の固定条件を満たすように、
当日の運用計画においては前記列車もしくはセグメントごとに前記車両もしくは乗務員を割り当て、
翌日以降の運用計画においては当初の前記運用計画において定められた1日分の前記行路ごとに前記車両もしくは乗務員を割り当てて、
新たな計画を作成することを特徴とする運用計画再作成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鉄道分野において、列車の運行が乱れた際に、車両の運用計画もしくは乗務員の運用計画を再作成する技術に関するものである。
【背景技術】
【０００２】
鉄道事業者は通常、事前に策定された列車ダイヤに沿って列車の運行をおこなうが、事故や故障、災害などの不測の事態のために運行乱れが発生した場合には、乱れ回復のために列車ダイヤの変更をおこなう。その一方で、変更後の列車ダイヤが実施可能であるためには、ダイヤ変更と矛盾がないように車掌や運転士などの乗務員の列車への割当て、すなわち乗務員運用計画を変更することが必要となる。運用計画の変更案は「運用整理案」と呼ばれることが多い。
【０００３】
従来より、乗務員運用整理案を作成する装置が提案されている（特許文献１）。特許文献１は、乗務員運用整理案の作成を対象としたものであり、計画列車ダイヤによる列車の運行に乱れが発生した場合に、列車運行管理装置から将来の予測列車ダイヤを取得する予測ダイヤ取得部、計画列車ダイヤに基づいて作成され、乗務員の一連の作業である行路に乗務員の乗務作業単位である行程が割当てられた乗務員運用計画を、乗務員運用情報管理装置から取得する乗務員運用情報取得部、乗務員運用整理の開始時刻を指定する時刻指定部、この時刻指定部により指定された乗務員運用整理の開始時刻以降の乗務員運用計画の行路を行程単位に切断する行路分解部、及びこの行路分解部により切断された各行程を、予測列車ダイヤに基づいて行路に割当てることにより乗務員運用整理案を作成する行程割当部を備えたものである。
【０００４】
ところで、車両と乗務員の区別に関わらず、運用計画は運行当日分だけが存在する訳ではなく、一般的には数日から数週間、ときには数ヶ月といったように、翌日以降の一定期間分の計画が事前に策定される。翌日以降の運用計画のことを、特に「割当計画」と呼ぶ。割当計画に関する技術として、鉄道分野の車両割当計画にも適用できる資源割り当て方法及び資源割り当て装置が挙げられる（特許文献２）。上記装置は、どの車両編成が翌日以降のどの列車を担当するかを決めるものであり、より具体的には、車両を「資源」、車両を充当する列車の集まりを「作業」とし、割当計画作成を一定期間の複数の作業群に対してそれぞれの作業を実行するために必要な資源を割り当てる問題として捉え、グラフカラーリングの手法を応用して再作成を効率良くおこなうものである。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開2006-079440号公報
【特許文献２】特開平10-149347号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
運行当日の運用計画を再作成すると、翌日以降の計画に支障をきたす場合がある。例えば再作成によりある車両の最終到着地が変更されると、翌日の出発地と不一致が生じるため、翌日以降の計画の実施が物理的に不可能となる。したがって、運行当日の運用計画を再作成するにあたっては、本来であれば翌日以降の計画に支障がおきないように配慮すべきであり、支障が避けられない場合には翌日以降の計画も当日とあわせて再作成することが望ましい。しかしながら、例えば鉄道分野では、運行当日と翌日以降の運用計画の再作成は担当部署が分かれており、それぞれが別個におこなわれているのが現状である。すなわち、まずある部署（Ａとする）で運行当日の運用計画を再作成し、その結果を受けて他の部署（Ｂとする）で翌日以降の運用計画の再作成をおこなっている。当日の再計画の内容次第では翌日以降の運用計画に支障が発生し、それをどうしても修復できない場合がある。その場合は部署Ｂの再計画担当者が、電話、ＦＡＸ、あるいは口頭で運行当日の運用計画の担当者や列車ダイヤの担当者などに対して計画の再考を依頼することになる。これは部署にまたがる煩雑な調整作業が必要なことを意味する。
【０００７】
先に示した従来技術は、運行当日の運用計画だけ（特許文献１）、あるいは翌日以降の運用計画だけ（特許文献２）を対象として再作成をおこなうものであり、どちらも運行当日と翌日以降の計画をあわせて再作成をおこなうことができない。その理由のひとつは、従来技術が運行当日もしくは翌日以降のどちらか一方の運用計画の入力手段しか持たないためである。より重要なもうひとつの理由は、ひとくちに運用計画といっても、運行当日と翌日以降では計画そのものの構造や再作成にあたっての制約条件、評価指標に違いがあるため、どちらか一方だけを扱うことを前提として再計画処理が構成されている従来技術では、両者をあわせて全体として矛盾のない再作成をおこなうことができないためである。
【０００８】
そこで、運行当日と翌日以降の運用計画をあわせた統合的な再作成を可能にすることを、本発明が解決しようとする主たる課題とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、本発明の提供する運用計画再作成装置は、列車の運行ダイヤに変更が生じたときに鉄道車両もしくは乗務員の運用計画の再作成を行う運用計画再作成装置であって、運行ダイヤを入力される入力手段と、鉄道車両もしくは乗務員の当初の運用計画及び入力された運行ダイヤを格納する記憶手段と、ダイヤ変更当日から所定の日数の期間の運用計画を、期間終了時の車両もしくは乗務員の運用終了場所を当初計画された場所に固定した条件で再作成する再計画手段と、再作成した運用計画を出力する出力手段とを備える。
【００１０】
記憶手段が格納する運用計画は、予め定められた複数の前記列車の組み合わせである行路の情報を含み、再計画手段は、記憶手段に格納された運行ダイヤが前記入力により変更されると、当初の運用計画及び変更された運行ダイヤを記憶手段より読み出し、ダイヤ変更当日の運用計画の対象とする列車もしくは列車を分割したセグメントを、運行ダイヤに基づいて当初の計画より変更し、変更した列車もしくはセグメント及び翌日以降の行路に対して、同一の車両もしくは乗務員を割り当てる各列車もしくはセグメント及び行路が接続し、かつ運用終了場所の固定条件を満たすように、当日の運用計画においては列車もしくはセグメントごとに車両もしくは乗務員を割り当て、翌日以降の運用計画においては当初の運用計画において定められた1日分の行路ごとに車両もしくは乗務員を割り当てて、新たな計画を作成することを特徴とする。
【発明の効果】
【００１１】
本発明によれば、運行ダイヤの変更があった当日と翌日以降の運用計画をあわせた統合的な再作成をおこなうことができる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施形態における機能並びに装置構成を示す図である。
【図２】第１の実施形態における再計画手段の処理の流れを示す図である。
【図３】列車ダイヤの例を示す図である。
【図４】運行当日の車両運用計画の例を示す図である。
【図５】翌日以降の車両運用計画の例を示す図である。
【図６】列車運行乱れの例を示す図である。
【図７】運行当日の車両運用計画の違反例を示す図である。
【図８】運行当日の車両運用計画の違反解消例を示す図である。
【図９】第１の実施形態における違反解消処理の流れを示す図である。
【図１０】第１の実施形態における編成1個を対象とした接続違反解消処理の流れを示す図である。
【図１１】第１の実施形態における編成1個を対象とした接続違反解消処理の考え方を示す図である。
【図１２】第１の実施形態におけるネットワーク構成例の運行当日部分を示す図である。
【図１３】第１の実施形態におけるネットワーク構成例の翌日以降部分を示す図である。
【図１４】第１の実施形態におけるネットワーク構成例の全体を示す図である。
【図１５】第１の実施形態における計画の一部を固定する場合のネットワーク構成例を示す図である。
【図１６】第１の実施形態における編成１個を対象とした運用パターン違反解消処理の流れを示す図である。
【図１７】第１の実施形態における運用パターン１個を対象とした違反解消処理の流れを示す図である。
【図１８】第１の実施形態における計画修正処理の考え方を示す図である。
【図１９】第１の実施形態における計画修正処理の流れを示す図である。
【図２０】第１の実施形態における第m-t日以降の計画変更処理の流れを示す図である。
【図２１】第１の実施形態における組成変更がある場合の運用パターン違反解消処理の考え方を示す図である。
【図２２】第１の実施形態における計画修正手段の処理の流れを示す図である。
【図２３】第１の実施形態における評価指標の例を示す図である。
【図２４】第１の実施形態における修正解生成処理の流れを示す図である。
【図２５】第１の実施形態における修正操作の例を示す図である。
【図２６】第１の実施形態における修正操作の例を示す図である。
【図２７】第２の実施形態における修正操作の例を示す図である。
【図２８】第３の実施形態における機能並びに装置構成を示す図である。
【図２９】第３の実施形態における再計画手段の処理の流れを示す図である。
【図３０】第３の実施形態における数理モデルの解を算出する処理の流れを示す図である。
【図３１】第３の実施形態における実行可能解を算出する処理の流れを示す図である。
【発明を実施するための形態】
【実施例１】
【００１３】
以下では第１の実施形態である鉄道分野における統合型車両運用再計画システムについて説明する。
【００１４】
図１は統合型車両運用再計画システム0100の機能並びに装置構成を表す図である。統合型車両運用再計画システム0100は計算機システムであり、処理装置0110と、記憶装置0120と、入力装置0130と、表示装置0140とから構成される。記憶装置0120と処理装置0110は同一計算機の構成要素であっても良いし、図示しない通信ネットワークを介して接続する、相異なる計算機の構成要素であっても良い。
【００１５】
記憶装置0120には、運行当日の列車ダイヤ0121、運行当日の車両運用計画0122、翌日以降の車両運用計画0123、基礎情報0124、計画の評価指標0125が少なくとも格納される。ここで基礎情報0124は、計画作成の対象となる車両の定義情報、車両を列車ダイヤに充当する単位である編成の定義情報、清掃や検査などの作業の定義情報、列車が停車、通過する駅の定義情報、車両の走行履歴と作業履歴、運用パターン、が少なくとも含まれる。これらについては以降の関連箇所で必要に応じて詳しく説明する。
【００１６】
入力装置0130は、再計画の担当者がシステムを操作するために用いる装置であり、少なくともキーボード及びマウス等のポインティングデバイスを備える。表示装置0140は、列車ダイヤ、当日または翌日以降の車両運用計画、計画の評価値など、再計画担当者の作業に必要な情報を提示するために用いる装置である。
【００１７】
処理装置はCPU（図示せず）およびメモリを備え、メモリには、当日と翌日以降の運用計画を合わせた形で再計画をおこなう再計画手段0111、再計画手段で得られた結果を評価指標が改善されるように修正する計画修正手段0112、がプログラムとして格納され、演算装置たるCPUによって実行される。ワークエリア0113はプログラム実行の作業領域として使用されるメモリ上の領域である。上記プログラムは、記憶装置0120に格納し、この記憶装置0120の起動装置（図示せず）あるいは図示しない通信ネットワークを介して処理装置0110に伝送した上で実行される。あるいは、記憶装置0120とは別の記憶装置に格納されていてもよい。
【００１８】
図２は、図１の再計画手段0111の処理フロー図である。この処理は、再計画担当者が図１の入力装置0130を介して再作成を指示する、あるいは列車ダイヤに変更が生じ、その内容が同じく入力装置0130などを介して図１の記憶装置に格納されるといった、あらかじめ決められた何らかのイベントをトリガーとして開始されるものとする。以下ではこの処理を詳細に説明していく。なお、以下で説明する再計画方法に対応する各動作は、処理装置0110のCPUが、メモリに読み出して実行する各プログラムによって実現される。そして各プログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
【００１９】
まず、ステップ0201において、再計画手段0111が図１の記憶装置0120に格納されている各情報を読込み、処理装置のワークエリア0113内に配置する。以降の説明では、特に断らない限り必要な情報はワークエリア0113から取得するものとする。読み込んだ情報のうち、ダイヤ変更当日の運用計画に、列車ダイヤに生じた変更を反映させて、計画の対象とする列車を当初の計画から変更する。次にステップ0202において、再計画手段0111が、変更した列車及び翌日以降の行路に対して、車両を割り当て直して再計画をおこなう。次にステップ0203において、計画修正手段0112が、ステップ0202で再作成した運用計画を出発点として、あらかじめ定義された評価値が改善されるように計画を修正する。ステップ0204では、最終的に得られた計画を図１の表示装置0140に出力し全体処理を終了する。
【００２０】
ここで、車両が割当てられない列車や回送が必要な車両などの情報を参考情報として出力しても良い。割り当てられない列車や回送が必要な車両があるなど、再計画を行っても運用計画の矛盾が解消できない場合には、列車ダイヤ、予備の車両の数、運用ルールなど、運用計画再作成の前提条件を変更する必要がある。具体的には列車の運休、駅の着発時刻の変更、回送の設定、他の線区から車両を借りる、などが挙げられる。前提条件の変更は業務担当者が判断して行われるが、本実施例によれば、必要な参考情報を提示することにより、再計画業務における担当者の負担軽減や効率化に寄与することができる。
【００２１】
以降ではさらにステップ0202及びステップ0203について詳細に述べるが、その前に本実施例が対象とする当日及び翌日以降の車両運用計画の概要、及び統合型車両運用再計画システム0100の機能概要について、図３〜図８を用いて説明する。
【００２２】
図３は列車ダイヤの例である。列車ダイヤとは列車の走行計画のことであり、一般的には図３のように横軸が時刻、縦軸が駅の２次元平面上のグラフとして描かれる。例えば図３のアはＡ駅を出発してＢ駅を通りＣ駅に向かう列車を表している。列車ダイヤを参照すれば、各列車の駅通過時刻や駅間の走行時間、列車の走行間隔など、列車の運行管理に必要な様々な情報を把握することができる。
【００２３】
図４は運行当日の車両運用計画0122の例である。車両運用計画とは各車両が担当する列車ダイヤと、付加的な情報として運行の合間におこなう清掃や点検などの作業内容を定めたものである。ダイヤに基づいた列車運行をおこなうためには、全ての列車に対して必要な車両が漏れなく割当てられる必要がある。図４は図３の列車ダイヤに対する当日の車両運用計画0122の一例である。これは３つの編成によって図３の全ての列車をもれなくカバーするものである。ここで編成とは、いくつかの車両を連結した車両のまとまりのことであり、この単位で車両が割当てられ列車が運行される。編成がどの車両の組合せで構成されるかは、図１の基礎情報0124において定められる。なお、以降では特に断らない限り、「車両」と「編成」は区別せずに用いる。
【００２４】
図４において、編成01の計画は次の通りである。まず、列車アに充当され駅Ａから駅Ｃに向かう。Ｃ駅から隣接した車両基地に入庫し、点検作業を受ける。その後再び本線に戻り、列車ウに充当されＣ駅からＡ駅に向かう。Ａ駅では折り返し列車として列車カに充当されてＣ駅に向かい、そこで当日の運行を終了する。この例が示すように、計画は車両の充当を切れ目なくおこなうことができる複数の列車から構成される。編成01、02、03の各計画に含まれる列車に重複はなく、かつ図３の全ての列車がいずれかの編成に含まれる。なお、図示しないが、この例では編成01,02,03以外に編成がもうひとつ存在し（編成04とする）、Ｃ駅に隣接する車両基地で予備編成として待機するものとする。
【００２５】
図５は、翌日以降の車両運用計画0123の例である。なお、鉄道分野においては翌日以降の車両の計画は「車両割当計画」と呼ばれる事が一般的であるが、本実施例は当日と翌日以降の車両の計画をまとめて扱うものであることから、用語を統一して「車両運用計画」と呼ぶ。
【００２６】
翌日以降の車両運用計画0123は縦軸が編成、横軸が日付の表形式である。表の各マスには編成１個の１日の計画、すなわち編成をどの列車に充当するか、そしてどんな作業を実施するかが記される。図５の例では、充当する１日分の列車をまとめたもの（これを行路と呼ぶ）の番号を該当するマスの上段に、実施する作業を表す記号を同じく下段にそれぞれ記入する。例えばマス0501は編成04の第2日目の計画を指し、行路番号は(1)であり、作業は何も実施しない。この行路がどういうものかは別途定義され、運用計画の一部として保持されている。例えば行路(1)は行路詳細0502で定義される。ここで、行路(1)は列車ア、列車ウ、列車カの3つの列車を含むこと、また列車アと列車ウの合い間に作業の一種である「点検」を実施できること、が規定される。作業を実際に実施するかどうかは、この行路に割当てる編成の作業履歴や走行履歴、作業員や作業設備等の各種制約に基づいて判断される。この例ではマス0501の下段が空欄なので、作業は実施しない。
【００２７】
運行が乱れた際に臨時列車を出す場合に備え、編成によっては車両基地で一日中待機するものがある。これを「予備」と呼ぶ。予備の編成に対しては、マス0503のように行路番号に代えて上段に「予備」と表記する。予備も行路の一種として扱い、待機場所と待機中に実施可能な作業が規定される。行路と同様に、ある作業が実施可能であっても、実際に作業を実施するかは別途判断される。
【００２８】
編成によっては長期間にわたり検査や修理などの作業を受けるものがある。図５のマス0504がその例を表している。上段に「長検」と記されているが、これは編成02に対して第５日から第７日まで長期検査という作業をおこなうものである。長期検査については車両運用計画とは別に実施予定があらかじめ作成されるのが一般的である。したがってその予定を守って運用計画を作成する必要がある。
【００２９】
作業の中には、点検など、規定の日数、あるいは規定の走行距離のサイクルで定期的に実施することが法令等で定められているものがある。それらについては、全ての編成に対して実施サイクルを守って運用計画を立案しなければならない。この条件が満足されているかは、実施サイクルに含まれる日数にわたって計画をチェックする必要がある。したがってこの種の条件は、より一般的には車両や（他の実施例で扱う）乗務員の運用を複数の日付にまたがって規定する条件として捉えることができる。以降では運用日数に関連するこの種の条件を「運用パターン」と呼ぶこととする。
【００３０】
以降では、法令で定められた点検など必ず満足しなければならない運用パターンの作業を「必須作業」、それ以外の作業を、「非必須作業」と呼ぶ。非必須作業の例としては各種の清掃があげられる。非必須作業の場合は運用パターンは絶対的なものではなく、できるだけ守るべき目標条件として位置づけられる。運用パターン、すなわち設定すべき作業種類とその実施サイクルの情報は、図１の基礎情報0124に格納される。
【００３１】
図６は列車運行に乱れが発生し、それに伴い列車ダイヤが変化した例である。軸線0601は現在時刻を表す線である。この線より左側の領域が列車の走行実績、右側が乱れの結果変更された今後の走行スケジュールを表している。この例では、列車イが車両故障などの理由によりＢ駅の直前で一定時間停車するため、Ｂ駅、Ａ駅への到着が大幅に遅延する。また、その遅れが列車ウ、列車エにも波及し、同様にＢ駅、Ａ駅への到着に遅延が生じる。
【００３２】
図７は、列車ダイヤの変化によって当日の車両運用計画に不具合が発生する例である。具体的には図６の運行乱れに伴って発生したものである。編成02の計画において、列車イのＡ駅への到着時刻と次列車である列車オの出発時刻に逆転が生じており、このままでは列車運行が物理的に不可能である。また、列車イの影響で列車ウの到着時刻も遅れるため、編成01の計画において列車ウの到着時刻と次列車である列車カの出発時刻の間にも逆転が発生する。編成03も同様であり、列車エと列車キの間に時刻逆転が発生し、このままでは計画を実行する事ができない。
【００３３】
２つの列車に対して編成を連続して充当するためには、先行列車の到着と次列車の出発との間に、車両の折り返しに必要な手続きや作業などを加味した適切な間合い時間が必要である。また、当然ながら先行列車の到着場所と次列車の出発場所が同じでなければならない。１つの車両が割り当てられる各列車および行路は、適切に接続している必要がある。この時間と場所に関する条件をあわせたものを「接続条件」と呼ぶ。なお、間合い時間は図１の基礎情報0124の中で定義される。
【００３４】
接続条件のほかに車両運用計画が満たすべき条件としては、必須作業の運用パターンを守ること、作業を割当てるにあたっては行路や予備で規定された実施可能なものを割当てること（作業割当条件と呼ぶ）、が挙げられる。
【００３５】
本実施例の統合型車両運用再計画システム0100の１つの機能は、列車ダイヤの乱れに伴って、計画の対象とする列車が変更になった結果、条件違反が発生した当日の車両運用計画を修正し、条件違反を解消するものである。具体的には図８に示すように、編成を割当てる列車を変更することで違反の解消をおこなう。また図示しないが、必要に応じて予備編成の割当てもおこなう。また、別の実施形態である乗務員の運用再計画と同様に、編成の変更が可能な区間でひとつの列車を分割したもの（セグメントと呼ぶ）を単位として編成の割り当てを行ってもよい。
【００３６】
図８の点線の列車（列車オ）は、運用計画を修正した結果、編成を割当てることができなかったものである。本実施例の統合型車両運用再計画システム0100は、編成を割当てられない列車がある場合、その旨を参考情報として再計画担当者に示す。再計画担当者はこの情報に基づき、(1)該当列車を運休する、(2)編成の追加や時刻変更などのダイヤ変更をした上で再作成する、のいずれか、あるいは両方を必要なだけおこなうことで実施可能な計画を作成することができる。
【００３７】
列車ダイヤの変更を反映させて当日の車両運用計画を修正すると、翌日以降の車両運用計画に不具合を生じることがある。例えば図８に示す修正では、編成02の最終到着地がＣ駅からＡ駅に変更されるので、翌日の車両運用計画で指定される出発地（図５よりＣ駅とわかる）と不一致が生じる。すなわち当日と翌日の境界部分で接続条件違反が発生するので、計画が物理的に実施不能となる。この場合、翌日の行路を変更して接続条件を満足するか、当日の運用終了後にＡ駅からＣ駅に回送を設定しなければならない。翌日の行路を変更すると運用パターンや翌々日との接続条件を損なう可能性があるので、これを解消するための行路変更や作業の追加設定がさらに必要となる。本実施例の統合型車両運用再計画システム0100は、当日の車両運用計画を修正するだけでなく、その影響で生じた翌日以降の計画の不具合も検知し、あわせて行路・作業の割当変更をおこなう。すなわち当日と翌日以降の再計画を包括的におこなうものである。
【００３８】
次に、図２の再計画手段0111によるステップ0202（計画に生じた違反解消）の詳細について、図９の処理フロー図を用いて説明する。なお、以下で説明する違反解消方法に対応する各動作は、処理装置0110のCPUが、メモリに読み出して実行するプログラムによって実現される。そしてプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
【００３９】
再計画手段0111はまず、ステップ0901で初期化をおこなう。具体的には、接続、運用パターン、作業割当の３つの条件の違反をチェックし、作業割当条件違反については違反した作業を削除し、さらに各種変数の初期化をおこなう。なお、作業割当条件に違反する作業を削除することで運用パターン違反が発生する可能性があるが、これは後に説明する運用パターン違反解消処理で解消が試みられる。
【００４０】
次に再計画手段0111は、ステップ0902からステップ0909で囲まれる一連のステップを、全編成を処理済にするまで繰り返し実行する。
まずステップ0903では、ダイヤ変更を反映した計画のうちから未処理の編成をひとつ取り出しこれをＡとする。複数の候補がある場合は、計画に違反がある編成を優先的に選択する、後述する「キャンセル」された編成を優先的に選択する、予備として車両基地に待機するものを後回しにする、あるいはそれ以外の方法など、任意のやり方に基づいておこなう。次に、ステップ0904においてＡの接続違反を解消、すなわち接続条件の違反がなくなるようにＡの計画を修正する。この詳細は後述するが、これにより元の計画からの変更ができるだけ少なく接続違反がない計画が得られる。次にステップ0905においてＡの運用パターン違反を解消する。すなわち、先のステップで得られた計画の運用パターンをチェックし、違反がある場合はそれを解消するように行路と作業の割当を変更する。この詳細は後述するが、これにより必須作業の運用パターン違反を解消し、非必須作業については違反の度合いを抑えた計画を作成することができる。次にステップ0906で編成Ａに対して「処理済」のマークをつける。ステップ0907では、ステップ0904の接続違反解消、ステップ0905の運用パターン違反解消の各処理の中で計画のキャンセル（詳細は後述）が発生したかチェックする。その結果、キャンセルが発生しなければ次の繰り返し（次の未処理の編成）に進む。キャンセルが発生した場合はステップ0908に進み、キャンセルした計画に該当する編成を未処理に戻して次の繰り返しに進む。
【００４１】
繰り返し処理が終了したらステップ0910に進み、後処理をおこなう。ここでは当日の列車に編成の未割当があるかチェックし、未割当があれば図１の表示装置0140に出力するための参考情報を生成し、表示装置0140が最終的に運用計画の出力とあわせて出力する。また、各編成の計画をチェックし、当日の終了場所と翌日の開始場所との不一致があれば回送設定が必要である旨の参考情報を生成する。さらには表示装置0140へ出力する他の情報として、条件違反が残った部分や評価指標の値をここで生成して、表示装置0140が運用計画とあわせて出力しても良い。業務担当者が、再作成された運用計画とともに参考情報を確認することにより、再作成された計画に対してダイヤ変更や回送設定などを行うことができ、また必要に応じて、担当者の修正した計画を基に運用再計画システム0100にさらなる再計画作成を実行させることができる。
【００４２】
次に、ステップ0904における編成１個（Ａとする）を対象とした接続違反解消処理の詳細を図１０の処理フロー図を用いて説明するが、その前に図１１を用いて本処理の基本的な考え方を説明する。本処理は大きく分けて２段階の処理から構成される。まず第一段階では、既に処理した編成（図１１では編成Ｂ）の計画を崩さずに編成Ａの計画作成を試みる。図１１は今までの例とは別の翌日以降の運用計画だけを抜き出した計画作成処理のイメージである。開始／終了場所IDは、駅などを表し、点線矢印で結ばれた行路が編成Ｂの計画を表している。編成Ａは編成Ｂの計画を崩さないように、かつ接続条件を満足するように充当行路を選択する（図の太線矢印）。ここで解が得られない場合は第二段階に進み、既に処理した編成の計画を一旦崩して計画作成をおこなう。
【００４３】
この処理を高速、かつ、後述する列車や行路の割当固定指示を考慮して確実におこなうため、数理的な手法を応用する。すなわち、ダイヤ変更当日に編成を割り当てる単位である列車と、翌日以降に編成を割り当てる単位である行路をノードとし、接続条件を満足する２つのノードをリンクで結んだネットワークを考え、接続条件違反の無い計画の作成を、そのネットワーク上の最短経路問題としてモデル化する。そして、最短経路問題を解くアルゴリズム、例えばダイクストラ法、あるいはそれ以外の方法を適用して最適解を高速に算出する。第一段階と第二段階の要件の違い、すなわち第一段階は作成済の計画を崩さないが第二段階はそれを許す点については、最短経路探索用ネットワークの構成方法を変えることで実現できる。また、第一段階と第二段階の両方に共通する、当初の計画からの変更を抑えて計画を作成する点についても、同様に最短経路探索用ネットワークの構成を工夫する事で対応できる。詳細については以降の関連部分で説明する。なお、以降では列車と行路を区別しない場合は、両者を「トリップ」と呼ぶこととする。
【００４４】
図１０に戻り、再計画手段0111による接続違反解消処理の説明を続ける。
再計画手段0111はまずステップ1001において、前述した第一段階向けの最短経路探索用ネットワークを作成する。第一段階では作成済の計画は崩さないので、トリップから作成済の計画に含まれるものを除いたものをノードとする。さらに、計画の開始と終了を識別する特別なノードとして、開始ノードs、終了ノードtを生成する。リンクの設定方法は、まずs,t以外の通常のノードに関しては次の通りである。まず当日同士、翌日以降同士の２つの通常ノードa,bは、これらがaからbの向きに接続条件を満たせば、aを始点、bを終点とするリンクを設定する。当日と翌日（翌日以降ではなく、翌日一日のみ）のノードの組合せについては、全ての組合せに対して当日から翌日の向きにリンクを設定する。すなわち、当日から翌日の接続に関しては接続条件の違反を許す。違反が発生すると翌日の開始場所まで編成を移動するために回送を設定する必要がある。
【００４５】
ノードsに関しては、現在時刻における編成の位置から開始可能な列車を検索し、ノードsからそれらの全てに対してこの向きでリンクを設定する。ノードtに関しては、再計画範囲の最後の日付までしか当初の計画が策定されていない場合は、最後の日付に含まれる全てのノードからノードtに対してこの向きでリンクを設定する。当初の計画が最後の日付の翌日分も策定されている場合は、最終日に元の計画の運用終了場所と同じ場所で終了するよう、該当編成を翌日に割当てるノードに接続できるノードだけを抽出し、それらからノードtに対してこの向きでリンクを設定する。
【００４６】
また、最短経路を求めるためにはリンクの長さを設定する必要があるが、これは次の考え方に基づいて設定する。まず、元の計画をネットワーク上の経路として表したとして、その経路に含まれるリンクは長さを小さく(長さ(1)）、その他のリンクは長さを大きく設定する(長さ(2)）。こうすることにより、元の計画に近い経路を最短経路として得ることができる。次に、長さ(2)をリンクの特性に応じてさらに細かく設定する。まず、当日に関しては、リンクの時間的長さ、すなわち始点ノードの終了時刻と終点ノードの開始時刻の差tを求める。そしてtに関して非線形かつ単調増加な性質を持つ関数f(t)を用意し、時間的長さをその関数で変換したものをリンク長とする(長さ(2)-1)。非線形かつ単調増加な関数の例としては、f(t)=t^2が挙げられる。このようにリンク長を設定すれば、時間間隔をおかずに多くの列車をつなぐ経路が最短経路として選ばれやすくなる。したがって列車がどの編成にも割当てられない充当漏れを抑えることができる。一方、翌日以降に関しては、リンクは日付が連続する２つのノードを接続するのでリンクの時間的長さは全て同じである。したがって任意の同じ値を設定する（長さ(2)-2)。また、当日から翌日へのリンクは、回送の発生をできるだけ少なくするため、接続条件を満たさないリンクの長さを極端に大きくする(長さ(2)-3）。そして、その他の長さを当日と同様に関数f(t)で定める（長さ(2)-1）。ただし、当日の最終列車の終了時刻から翌日の行路の開始時刻は非常に長い場合があるので、時間的長さtは実際の時間から一定値を引くなどして適当に小さな値に調整したり、一律同じ値としても良い。
【００４７】
今、元の計画に沿って編成を時間順にトリップへ割当てることを考える。その途中で別の編成のトリップに割当を切り替えて、以降は元の計画に戻すことができない場合、編成全体として元に近い計画を得るためには、そこからさらに別の編成に割当てを切り替えるよりも、最初に切り替えた編成のトリップに次々と割当てていく方が良い。なぜならばその方が他の編成への影響、すなわち他の編成の計画を崩す可能性を小さくできるからである。そこで、あるリンクが他の編成の元計画を経路表現したものに含まれていれば、長さ(2)-1,2,3から一定の値d（d>0とする）を引いてそのリンクを選ばれやすくする。これを長さ(2)-4とする。先ほどの長さ(2)-1の例では、この条件に該当するリンクは長さがf(t)-d=t^2-dとなる。これ以外にも、元の計画で開始場所が接続違反をおこしているトリップを終点にもつリンクの長さを小さくする、必ず計画変更が発生する編成の元計画に含まれるリンクの長さを小さくするといったように、その他の調整を加えても良い。
【００４８】
図１２はネットワークの構成例を示している。ネットワークの全体から当日部分だけを切り出したものである。ここで、図８に示す編成01の計画が既に得られて編成01は処理済となっており、編成02の計画を得るためにネットワークを作成することを仮定する。したがって、編成01の計画に含まれる列車ア、ウ、キに該当するノードはネットワークに含まれない。また、ネットワークを作成する時点で編成02は列車イに割当てられて走行中なので、開始ノードsからのリンクは列車イのノードに接続するものだけになる。
【００４９】
リンクの長さは、長さ(1)は0、長さ(2)-1はt^2とした。列車イから列車カへの時間的長さ(t)は5分、列車カから列車クへの時間的長さは20分、列車オから列車クへの時間的長さは60分、である。この例の場合、長さ(2)-3,4に該当するものは存在しない。
【００５０】
なお、列車の中には複数の編成を併合して運行しなければならないものがある。どの列車に対して編成をいくつ併合するかは列車ダイヤで指定される。併合が必要な列車がある場合の特別な扱いとして、作成済の計画の中にその列車が既に含まれていても、含まれている数の合計が必要な数に満たなければその列車をノードに加えてネットワークを作成する。
【００５１】
図１３は同じネットワークの翌日以降の部分である。ここでは再計画の範囲を４日間としている。ノードt以外のノードに付された記号は相互の識別用であり、行路番号もしくは予備を表す「予」に日付を表す枝番号をつけたものである。例えばノード1301は、第４日目の行路(2)（図５参照）を意味する。ここでも当日部分と同様に編成01は処理済で編成02用のネットワークを作成することを仮定する。したがって編成01の計画に含まれる行路（第1日目の行路(2)、第2日目の予備、第3日目の行路(3)、第4日目の行路(1)）に該当するノードはネットワークに含まない。また、再計画範囲の最終日の翌日（第５日目）は、C駅に隣接する車両基地で長期検査が割当てられていることが図５よりわかるので、ノードtに対してはＣ駅を終了場所とする第４日目の行路（２）、及びC駅で待機する予備からリンクをはる。リンクの長さは、長さ(1)は0、長さ(2)-2は100、長さ(2)-3は100-5=95とした。
【００５２】
図１２と図１３のネットワークを合わせた全体像を図１４に示す。当日と翌日を結ぶリンクの長さは、長さ(2)-1は一定値100、長さ(2)-3は10000とした。その他のリンクは図１２、１３と同じなので省略した。なお、長距離列車の中には複数の日にまたがる行路を含むものがあるが、その場合は複数日にまたがる行路を１個のノードとして扱えば良い。
【００５３】
図１５は、トリップの一部を固定する場合のネットワークの構成例である（リンク長は省略）。トリップの固定指示は、図１の入力装置0130を介して再計画担当者が設定することとしても良いし、図１の当日計画0122、翌日以降計画0123にあらかじめ設定されていても良い。なお、翌日以降の長期検査の予定は動かすことができないので、これも固定指示と同様に扱いネットワークを作成する。
【００５４】
図１５は、当日については列車カを、翌日以降については第２日目の行路（３）を固定する例である。当日の場合、固定対象のトリップ（列車）と時間的に重なるノードとリンクを全て削除する。図１５の例では列車カと時間的に重なる列車エのノード、列車オから列車クへのリンク、列車イから翌日ノードへのリンクをそれぞれ削除する（図の点線のノードとリンク）。なお、当然ながら削除したノードに接続していたリンクも削除する。一方、翌日以降の場合は、固定したノードの日付を第Ｘ日とすると、第Ｘ−１日から第Ｘ日へのリンクのうち、固定したノードに接続するもの以外を削除する。同様に、第Ｘ日から第Ｘ＋１日へのリンクの中で、固定したノードに接続するもの以外を削除する。
【００５５】
図１０に戻り、接続違反解消処理の説明を続ける。最短経路探索用ネットワークを作成したらステップ1002に進み、そのネットワーク上でダイヤ変更時を表す開始ノードsから再計画範囲の終了を表す終了ノードtまでの最短経路を探索する。ここで最短経路の探索手法としてはどのようなものを用いても良いが、本実施例では最短経路の効率的な探索手法として良く知られているダイクストラ法を使用する。
【００５６】
以上が接続違反解消処理の第一段階である。次に再計画手段0111はステップ1003の判定処理を行い、最短経路が得られた場合は、ステップ1011に進み、最短経路を計画に変換して接続違反解消処理を終了する。最短経路を計画に変換するとは、具体的には最短経路に含まれるノードから該当編成を割当てるトリップの集まりを得て、さらに作業の実施内容を決定することである。作業の実施内容は元の計画をそのまま引き継ぐ。すなわち、当日であればリンク、翌日以降であればノードに元の計画の作業実施内容を属性値として設定しておき、それに基づき作業の有無を決定する。
【００５７】
最短経路が得られない場合は第二段階に進む。すなわち、再計画手段0111がステップ1004からステップ1010で囲まれる一連のステップを、作成済の編成を全て選択するまで繰り返し実行する。繰り返しの詳細は次の通りである。まずステップ1005において作成済の計画をひとつ取り出し、これをＢとし、Ｂの計画をキャンセルする。次にステップ1006に進み、最短経路探索用ネットワークを作成する。この作成方法はステップ1001と同じだが、Ｂの計画をキャンセルしたので、作成されるネットワークにはＢの計画に含まれていたノードも含まれる。次にステップ1007で最短経路を探索する。この探索方法はステップ1002と同じである。その結果最短経路が得られれば、判定処理(ステップ1008)を経由して繰返しを即座に抜けてステップ1011へ進み、最短経路を計画に変換して処理を終了する。最短経路がなければステップ1009においてキャンセルしたＢの計画を元に戻してから次の繰り返しへ進む。
【００５８】
以上が接続違反解消処理の詳細である。なお、キャンセルした編成はその後で計画作成をやり直す事になるが、キャンセルが際限なく発生すると計画作成が終わらない、あるいは長時間を要する可能性があるので、ステップ1005で編成を選択する際にある種のフィルタをかけても良い。例えばキャンセル回数に上限値を設定し、既にその値に達した編成は選択対象から除外することとしても良いし、キャンセルした際の状況（どの編成のためにキャンセルしたかなど）を保持しておき、同じ状況では同じ編成をキャンセルしないようにすることとしても良いし、さらに別の方法を用いても良い。
【００５９】
第二段階の反復処理を最後まで実行しても最短経路が得られない可能性がある。その場合は接続違反の解消を諦め、任意の方法で計画を仮作成して処理を終了する。計画の仮作成方法としては、接続条件違反を許したネットワークを構築して最短経路を求めることとしても良いし、別の方法を用いても良い。
以上が図９のステップ0904の説明である。
【００６０】
次に、図９のステップ0905における、編成１個（Ａとする）を対象とした運用パターン違反解消処理の詳細を、図１６の処理フロー図を用いて説明する。まずステップ1601において、再計画手段0111が再試行カウンタrを0に初期化する。次に再計画手段0111がステップ1602からステップ1609で囲まれる一連のステップを、全ての運用パターンを処理するまで繰り返し実行する。繰り返しの詳細は次の通りである。まずステップ1603において未処理の運用パターンを選択し、それをwとする。次にステップ1604に進み、編成Ａの計画に含まれる運用パターンwの違反解消をおこなう。このステップの詳細については後述する。ステップ1605では運用パターンwを処理済に設定する。ステップ1606では、違反解消処理による計画の変更の有無を検査する。計画の変更がなければ次の繰り返し処理（次の未処理の運用パターン）に進む。変更がある場合はステップ1607に進み、再試行カウンタrの値をチェックする。rが規定値を超えていれば次の繰り返し処理（次の未処理の運用パターン）に進む。rが規定値以下であればステップ1608に進み、rの値を１増やし、これまでに処理した運用パターンを全て「未処理」に戻して次の繰り返し処理に進む。この場合、運用パターン毎の違反解消処理をはじめからやりなおすことになる。
【００６１】
なお、ステップ1603において複数の運用パターンがある場合は、必須のものを先に選択する、逆に必須ではないものを先に選択する、またはその他の方法など、任意の方法を用いて選択する。
【００６２】
次に、ステップ1604の運用パターン毎の違反解消処理について、図１７の処理フロー図を用いて説明する。この処理は、日付変数(mとする)を開始日から終了日まで進めながら、ステップ1701からステップ1712で囲まれる一連のステップを繰り返し実行するものである。ここで開始日とは通常は運行当日を指す（翌日以降だけを再計画する場合を除く）。これを第0日とする。終了日とは翌日以降の計画において再計画を実行する範囲の最終日のことである。
【００６３】
繰り返しの詳細は次の通りである。まずステップ1702において、編成Ａの第m日における運用パターンwの違反の有無をチェックする。すなわち、図１の基礎情報0124から読み出した車両の走行履歴と作業履歴、そして第m日までの作業割当内容を用いて、運用パターンwが対象とする作業が第m日に実施サイクルを満たしているかを確認する。
【００６４】
違反がなければ、ステップ1703の判定処理を介して次の繰り返し処理（mを１増やす）に進む。違反がある場合はステップ1704に進み、違反を解消するための計画修正処理をおこなう。この詳細については後述するが、この処理により編成Ａの計画が変更される可能性がある。次にステップ1705に進み、計画修正が成功したかを判定する。その結果、修正が成功すれば次の繰り返し処理（mを１増やす）に進む。修正に失敗した場合は、接続違反解消処理と同様に、既に作成した計画を崩して計画修正を試みる。具体的にはステップ1706からステップ1711で囲まれる一連のステップを、作成済の編成を全て選択するまで繰り返す。ただし、処理時間を短縮するため、対象の運用パターンが非必須ならば繰り返し処理をおこなわず、この時点で違反解消をあきらめて処理を終了することとしても良い。
【００６５】
繰り返し処理の詳細は次の通りである。まずステップ1707において、作成済の編成をひとつ取り出し、これをＢとし、Ｂの計画をキャンセルする。次にステップ1708で計画修正処理を実行する。Ｂの計画をキャンセルしたので、この処理により割り当てが変更され、編成Ｂの計画に含まれていたトリップが編成Ａの計画に移る可能性がある。修正が成功した場合は、第m日における違反は解消されたので、ステップ1709の判定処理を介して次の繰り返し処理（mを1増やす）に進む。修正が失敗した場合はステップ1710でＢの計画を元に戻してから次の繰り返し処理（次の作成済の編成）に進む。
【００６６】
以上が運用パターン毎の違反解消処理のフローである。なお、ステップ1707でキャンセルした編成はステップ1710で元に戻さない限り後で計画作成をやり直すことになるが、キャンセルが際限なく発生すると計画作成が終わらない、あるいは長時間を要する可能性があるので、ステップ1707で編成を選択する際にある種のフィルタをかけても良い。例えばキャンセル回数に上限値を設定し、既にその値に達した編成は選択対象から除外することとしても良いし、キャンセルした際の状況（どの編成のためにキャンセルしたかなど）を保持しておき、同じ状況では同じ編成をキャンセルしないようにすることとしても良いし、さらに別の方法を用いても良い。
【００６７】
次にステップ1704及びステップ1708の計画修正処理の詳細を説明する。まず図１８は計画修正処理のイメージである。ここでは編成Ａが第m日に運用パターンwの違反があることを想定している。たとえば、運用パターンwが扱う作業をw'とすると、第m日までにw'を実施する必要があるにもかかわらず、設定できていないということである。それを解消するため、まず現状の計画において、第m日に運用パターンwが対象とする作業を設定することを試みる。それが成功すれば処理を終了するが、成功しない場合は第m日の行路を運用パターンwを満たすもの、すなわち作業w'が設定済、あるいは設定可能なもの、に変更することを試みる。この処理は接続違反解消処理と同様に最短経路問題として扱うことが可能である（図１８の(1)）。すなわち、第m日を計画作成の初日とみなし、ノードとリンク長の定義を工夫して最短経路探索用ネットワークを構築することで、w'が設定済、あるいは設定可能な行路を第m日に通る経路を最短経路として得ることができる。ここで、第m日を計画作成の初日とするとは、開始ノードsから伸びるリンクを第m日の行路（ノード）に接続したネットワークを作成することを意味する（m>0の場合。m=0は通常と同じ）。
【００６８】
最短経路が得られれば、それに基づき計画を変更し必要に応じて作業を設定することで第m日の違反を解消することができる。最短経路が見つからなければ、第m日までに作業w'を設定することによって、第m日の違反を解消することを考える。日付を１日ずらし、第m-1日を対象として作業の設定を試行する。追加設定ができない場合は、第m-1日を計画作成の初日とみなし、運用パターンwを満たす行路を第m-1から第m日の間に通る経路を最短経路問題として探索する（図１８の(2)）。最短経路問題が見つかれば必要に応じて作業を設定して処理を終了する。最短経路がなければさらに日付をずらし、第m-2日を対象として同様の処理をおこなう（図１８の(3)）。以降、違反解消に成功するか、既に作業が設定されている日付まで戻る、計画作成範囲から外れる日付まで戻る、これらのいずれかの条件を満たすまで日付を遡りながら最短経路探索を繰り返し実行する。日付を遡りながら最短経路探索を繰り返すことを、以降では「バックトラック」と呼ぶ。
【００６９】
以上の概要を踏まえ、図１９の処理フロー図を用いて計画修正処理の詳細を説明する。まずステップ1901においてバックトラック日数tを0に設定する。次にステップ1902からステップ1908で囲まれる一連のステップを、第m-t日が計画作成の範囲外、または運用パターンwが対象とする作業が第m-t日に設定済になるまで繰り返し実行する。繰り返しの詳細は次の通りである。まずステップ1903において、第m-t日に運用パターンwが対象とする作業の設定を試みる。ステップ1904で設定が成功したかを判定し、成功した場合は違反を解消できたので処理を終了する。設定ができなかった場合はステップ1905に進み、第m日の違反がなくなるように第m-t日以降の計画変更、すなわち最短経路探索をおこなう。この処理の詳細は後述する。次にステップ1906で変更が成功したかを判定し、成功であれば違反を解消できたので処理を終了する。変更ができなかった場合はステップ1907へ進み、バックトラック日数tの値を1増やして次の繰り返し処理へ進む。
【００７０】
以上が計画修正処理の全体である。次に第m-t日以降の計画変更処理（ステップ1905）について、図２０の処理フロー図を用いて説明する。まず、ステップ2001において、計画変更をする上で着目する日付pを第m日に設定する。次にステップ2002からステップ2007で囲まれる一連のステップを、pが第m-t日より前になるまで繰り返し実行する。まず、ステップ2003において、運用パターンwを満たす行路を第p日に通る最短経路、すなわちwの対象作業を設定済、または設定可能なノードを通る最短経路を探索するためのネットワークを作成する。
【００７１】
探索用ネットワークは、pが0、すなわち着目する日が当日か、もしくはpが0より大きい、すなわち着目する日が翌日以降かによって作成方法が異なる。pが0の場合は、リンク長以外は図１０の接続違反解消処理におけるネットワーク構成方法と同じである（リンク長については後述）。pが0より大きい場合（翌日以降）は、まず第m-t日より以前の計画は変更しないので、当日から第m-t-1日までのノードは全て除外する。さらに開始ノードsからのリンクを第m-t日のノードに対して設定する。そして第p日の行路は、対象作業が設定済か設定可能なものだけをノードとする。
【００７２】
リンク長の設定は接続違反解消処理の場合と以下の点で異なる。まず、元の計画ではなく現在の計画にできるだけ近い結果が得られるように、現在の計画を経路表現した際に含まれるリンクの長さを小さく(長さ(1))、その他のリンクの長さを大きくする（長さ(2)）。現在の計画はwよりも前に処理した運用パターンに関しては違反解消処理が施されているので、それに近い計画を得ることで以前に処理した運用パターンの違反が発生することを抑える狙いがある。そして、当日のリンクを含む場合（p=0）は、対象作業を設定可能なリンク（車両基地に入区でき、対象作業を実施する時間が十分あるもの）の長さをその他のリンクよりも小さくする。これは作業可能なリンクが選択される可能性を高める狙いがある。pが0より大きい場合、第p日に複数のノードがあれば、対象作業が設定済のノードの長さを、設定可能なノードよりも小さくする。これは作業設定済のノードが選択されやすくすることで作業の追加を抑える狙いがある。
【００７３】
上記の処理の補足事項として以下を挙げる。あるノードにおいて運用パターンwの対象作業が設定可能かどうかの判定は、ノードが表す行路が該当作業を実施可能かどうかでおこなう。ただし、設備や作業人員等の関係で車両基地が一日に実施可能な作業量を保持し、それを超えないことを判断基準に加えても良い。
【００７４】
ネットワークを作成した後は、ステップ2004で最短経路の探索を実行する。ステップ2005で最短経路が得られたかどうかを判定し、得られた場合はステップ2008へ進み、最短経路を計画に変換して処理終了する。なお、得られた最短経路が第p日に運用パターンwの対象作業を設定可能だが実際には設定されていなければ、ここでその作業を設定する。最短経路が得られなかった場合はステップ2006に進み、pの値を１減らして次の繰り返し処理に進む。以上が運用パターンを満足するための計画変更処理の詳細である。これにより、各種の運用パターンを満足した再計画をおこなうことができる。
【００７５】
ここまでが図２のステップ0202（計画に生じた違反を解消）に関する説明である。
以下では補足として、編成の組成変更がある場合、すなわち各編成がどの車両の組合せで構成されるかが計画の途中で変わる場合の対応方法について説明する。編成がどの車両から構成されるか、すなわち編成の組成は通常は固定されているが、個別の事情で一部の車両が変更されて組成が変化することが起こりうる。組成変更がなければ編成を単位として計画を作成することに問題はないが、組成変更がある場合、運用パターン（作業の実施サイクル）を編成ではなく個々の車両毎に満足する必要がある。そこで再計画手段0111が、図２１に示すとおり、再作成の期間を組成が変わる日で分割し、日付が早い期間から順番に運用パターン違反解消処理（図９のステップ0905）を実行する。最初の期間（図２１の期間１）以外は、バックトラックで最初の日付まで戻っても違反解消ができない場合、その一つ前の期間までバックトラックして違反解消処理を実行する。この時、処理時間を短縮するため、トリップの変更はおこなわず、作業の設定だけで違反の解消を試みても良い。また、これも処理時間を短縮するため、後戻りするのは一つ前の期間迄に限定し、それ以上前の期間へは戻らないことにしても良い。
【００７６】
次に図２の計画修正手段0112によるステップ0203（評価値が良くなるように計画を修正）の詳細を図２２の処理フロー図を用いて説明する。なお、以下で説明する計画修正方法に対応する各動作は、処理装置0110のCPUが、メモリに読み出して実行するプログラムによって実現される。そしてプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
【００７７】
まずステップ2201において、図２のステップ0202の結果として得られた計画を暫定解Ｘとする。次にステップ2202に進み、Ｘを修正することで別の計画を生成する。これを修正解Ｙとする。この修正解の作成方法については後述する。ステップ2203では修正解Ｙと暫定解Ｘの評価値を比較する。その結果、修正解Ｙの方が評価値が良ければステップ2205へ進み、Ｙを改めて暫定解Ｘとした上でステップ2202へ戻る。暫定解Ｙの評価値が悪い場合はステップ2204に進み、Ｘを最終結果として出力して処理を終了する。この処理の意味するところは、評価値が改善されるまで暫定解の修正と更新を繰り返しおこなう、というものである。なお、場合によっては処理が終了するまでの繰り返し回数が膨大になる可能性があるので、繰り返しの上限回数を設定し、ステップ2203の判定処理で「Yes」と判定されても、繰り返し回数が上限を上回った場合にはステップ2204に進み処理を終了することにしても良い。
【００７８】
図２３は、評価値の算出に用いる図１の評価指標0125の例である。ここでは１０個の評価指標があり、それぞれ評価値を算出するための計算式が定義される。図の「使用」欄は全体評価値の算出に使う指標を指定するものである。「○」の指標だけを選択して総合評価値を計算する。この設定は図１の入力装置0130を介して再計画担当者が変更できるようにしても良い。「重み」欄は全体評価値を算出する際の各指標の重要度である。各指標の評価値に重みを掛け、それらを合計したものを全体評価値とする。
【００７９】
図２４は、図２２のステップ2202（修正解生成処理）の処理フロー図である。まずステップ2401では、計画修正手段0112が暫定解Ｘを編成毎に分割し、各編成の計画毎に評価値を算出する。次に計画修正手段0112がステップ2402からステップ2407で囲まれる一連のステップを、各編成の計画を全て処理するまで繰り返し実行する。まずステップ2403において、未処理の編成の中で計画の評価値が最も悪いものを選択し、これをＡとする。次にステップ2404に進み、Ａの計画が変化する修正操作を実行して複数の解（計画）を生成する。修正操作については後述する。次にステップ2405において、得られた解の評価値を算出してその中で評価値が最も良い解を選択し、これをＹとする。ステップ2406では、Ｙと暫定解Ｘの評価値を比較する。Ｙの方が評価値が良ければこれを修正解として処理を終了する。この処理の意味するところは、計画の中で評価値が悪い部分から順番に修正を試みることで繰り返し回数を抑えながら暫定解Ｘよりも評価値が良い解を得る、というものである。
【００８０】
修正操作は、計画をネットワーク表現し、その構造を変更する処理である。ここでのネットワーク表現とは、図９の違反解消処理における接続違反の解消（ステップ0904）等で算出する最短経路に良く似ている。すなわち、計画に含まれるトリップ（列車、行路）をノードとして、それらを時系列順にリンクで接続したものである。
【００８１】
修正操作として、少なくとも図２５に例を示す「交換」と、図２６に例を示す「追加削除」の２種類が定義される。
【００８２】
図２５の「交換」は、２つの計画の一部を互いに入れ替えるものである。この特別な場合として、計画全体を丸ごと交換することも許す。ここではどんな入れ替えも可能なわけではなく、以下に示す制限がある。まず、交換によって得られるネットワークのリンクは接続条件を満たさなければなければならない（ただし、回送を許す場合は当日の翌日を結ぶリンクが接続条件を破っても良い）。さらに、交換する部分は固定部分を含んではならない。図２４のステップ2404では、編成Ａを交換の一方とし、交換する相手と交換する部分の組合わせを変えて交換操作をおこない複数の計画を生成する。
【００８３】
図２６の「追加削除」は、計画の一部を他の編成に移動するものである。なお、計画を持たない編成への移動は予備編成の割り当てを意味する。交換と同じく、この場合もリンクは接続条件を満たすものでなければならず、移動する部分は固定部分を含んではならない。図２４のステップ2404では、編成Ａを追加削除の一方とし、相手の計画と移動する部分の組合わせを変えて操作をおこない複数の計画を生成する。なお、この追加削除は交換とは異なり、計画の当日部分だけに適用可能である。なぜなら、翌日以降は各日の行路に編成を必ずひとつずつ割当てなければならないためである。
【００８４】
以下は補足事項である。(a)修正操作を実行すると必須作業の運用パターンに違反が生じる可能性があるので、修正操作の対象となった計画に対しては図１６の運用パターン違反解消処理を実行して違反を解消する。(b)上記の機械的な「交換」「追加削除」以外に、再計画担当者の定石などをパターン化することで対象路線に合った修正操作を定義しても良い、(c)処理時間を短縮するため、駅に同時に滞在する編成が駅の番線数を超えるといったように物理的な矛盾がある、番線をきわめて長時間占有するなど実運用上ありえない、あるいはあきらかに評価値が悪くなるなど、見込みのない修正操作はおこなわず、生成する解の個数を制限しても良い。
【００８５】
以上が、第１の実施形態である統合型車両運用再計画システム0100の説明である。なお、本実施形態は、当日と翌日以降の運用計画を同時に再作成するものであるが、当日あるいは翌日以降の一方だけを対象として再計画をおこなうことも可能である。すなわち、当日だけを対象とする場合は、図１の当日計画0122だけを用いてネットワークの生成や最短経路の探索などの処理をおこなえば良いし、翌日以降だけを対象とする場合は、図１の翌日以降計画0123だけを用いて処理をおこなえば良い。このように、当日と翌日以降を合わせた車両運用の再計画だけでなく、当日もしくは翌日以降のどちらか一方のみの再計画業務に用いるシステムを提供することも可能である。また、本実施形態は、列車の運行が乱れた場合の再計画を対象としているが、計画の全体を白紙の状態から作成することも可能である。そのためには、違反を含んでも良いので手作業やランダムな割当など適当な方法でまず元になる計画を作成し、図１の当日計画0122と翌日以降計画0123にそれを格納し、本実施形態を用いて再計画を実行すれば良い。
【実施例２】
【００８６】
以下では第２の実施形態である鉄道分野における統合型乗務員運用再計画システムについて説明する。
【００８７】
乗務員運用計画とは、各乗務員（運転士、車掌）が担当する列車を定めたものである。車両運用計画と同様に、運行当日と翌日以降とでは乗務員を割当てる列車の単位が異なる。運行当日の場合は、乗務員の交代や乗り継ぎが可能な区間でひとつの列車を分割したもの（セグメントと呼ぶ）を割当の単位とする。例えば図３の列車ダイヤの例において、Ａ、Ｂ、Ｃの全ての駅で乗務員の交代・乗り継ぎが可能とすると、列車アはＡ駅からＢ駅までとＢ駅からＣ駅までの２つのセグメントに分割される。一方、翌日以降の場合は、車両と同じく複数の列車をグループ化した「行路」が割当の単位となる。ただし、ここでの行路は車両用の行路とは別途作成される乗務員専用のものである。また、乗務員は清掃や検査などの作業とは関係がないので、作業に関する情報は行路に含まない。
【００８８】
以上のように、運行当日の列車の割当単位は異なるものの、列車に対して乗務員を漏れなく割当てなければならず、またその際に時間と場所の条件（接続条件）を満足しなければならないことから、乗務員運用計画は車両運用計画と良く似ている。
【００８９】
主な相違点としては次が挙げられる。(a)資格の有無や習熟度などに応じて乗務員が乗務できる区間が制限される場合がある。これを乗務員割当条件と呼ぶ。 (b)車両における作業を対象とした運用パターンに代わるものとして、「夜勤明けの次の日は休み」といった行路の組合せ方に関する運用パターンがある。 (c)車両の分割併合や組成変更に類するものとして、勤務はしないが場所を移動するために列車に便乗することがある。分割併合・組成変更とは異なり、便乗は再計画において便乗列車を変更することが許される。(d)当日部分の計画変更にあたっては、食事時間の確保や連続乗務時間の上限といった、乗務員の労働条件を考慮しなければならない。
【００９０】
以上の考察を踏まえ、以降では実施例１との相違点を中心に本実施例を説明する。
【００９１】
まず、本実施例の機能並びに装置構成は図１と次の点が異なるが、他は同一である。(a)記憶装置0120の当日計画0122は車両ではなく乗務員の当日計画を格納する。(b)翌日以降計画0123は車両ではなく乗務員の翌日以降計画を格納する。(c)基礎情報0124には、計画作成の対象となる乗務員の定義情報、各種労働条件の定義情報、列車が停車、通過する駅の定義情報、乗務員の勤務履歴、運用パターン、が少なくとも含まれる。これらについては以降の関連箇所で必要に応じて詳しく説明する。(d)評価指標0125には車両ではなく乗務員の評価指標を格納する。
【００９２】
また、以下で説明する違反解消方法および計画修正方法に対応する各動作は、実施例１と同様、処理装置0110のCPUが、メモリに読み出して実行するプログラムによって実現される。そしてプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
【００９３】
再計画処理の全体処理は、図２と実施例１の説明において「車両」または「編成」を「乗務員」、「回送」を「乗務員の移動」に読み替えれば良い。ただし、そのサブルーチンであるステップ0202（計画に生じた違反の解消）、ステップ0203（計画修正による評価値向上）の細部が異なっている。以下では、まずステップ0202の詳細を説明し、その後にステップ0203の詳細を説明する。
【００９４】
図９はステップ0202の処理フロー図である。本実施例では、まずこの図と実施例１における説明で「車両」または「編成」を「乗務員」、「車両基地」を「乗務員区所や駅」に読み替える。そして、ステップ0901の初期化処理では、接続条件、乗務員割当条件、運用パターンの違反をチェックする。ステップ0903で複数の候補がある場合は、条件違反がある乗務員を優先的に選択する、「キャンセル」された乗務員を優先的に選択する、乗務員区所や駅で待機するものを後回しにする、あるいはそれ以外の方法など、任意のやり方に基づいておこなう。ステップ0904の相違点は以降で図１０を用いて説明する。ステップ0905の相違点は以降で図１６を用いて説明する。繰り返し処理が終了した後のステップ0910の後処理は、まず当日のセグメントに乗務員の割当漏れがあるかをチェックし、割当漏れがあれば該当するセグメントに乗務員が割当てられないことを図１の表示装置0140に参考情報として出力する。また、計画を乗務員毎にチェックし、当日の終了場所と翌日の開始場所に不一致があれば、当日の乗務終了後に場所の移動が必要な旨を表示装置に参考情報として出力する。実施例１と同様に、表示装置へ出力する他の情報として、制約条件の未充足部分や評価指標の充足度合い等を生成して出力しても良い。
【００９５】
次に、図９のステップ0904（接続違反解消）の実施例１の詳細を図１０を用いて説明する。まず図１０と実施例１における説明において、「列車」を「セグメント」、「車両」または「編成」を「乗務員」、「回送」を「乗務員の移動」に読み替え、併合に関する記述は、セグメントが複数の乗務員を必要とする場合と解釈する。
【００９６】
ステップ1001、1006のネットワークの作成処理は次の点で異なる。 (a)ネットワークのノードは、列車を分割したセグメント（当日）と行路（翌日以降）とする。すなわち、乗務員の場合の「トリップ」は、列車と行路ではなくセグメントと行路を意味する。ただし、事情によっては車両運用再計画と同様に列車を単位とする形態であってもよい。また、便乗を許すので、当日部分に関しては計画作成範囲に含まれる全てのセグメントをノードとする。
【００９７】
(b)次に、ネットワークのリンクは、当日のノード同士、翌日以降のノード同士を結ぶものについては接続条件を満たすだけでなく乗務員割当条件も同時に満たすものとする。加えて、翌日以降の部分については運用パターンの矛盾をチェックし、矛盾する場合はリンクを設定しない。運用パターンの例としては「夜勤明けの次の日は休養日とする」等があげられる。ここで「休養日」は勤務をおこなわない特別な行路として扱う。また、対象路線によっては運行当日の乗務終了場所の変更が許されないので、車両と異なり当日から翌日へのリンクを接続条件、乗務員割当条件、運用パターンを満たすものだけに制限しても良い。
【００９８】
(c)リンク長は実施例1とほとんど同じだが、実施例1では併合がある場合を除いて存在しない種類のリンクがある。それは、既に他の乗務員を割当てたノード（セグメント）を始点または終点、あるいはその両方とするリンクである。これらに対しては、なるべく便乗が発生しないことを目的とし、他のリンクよりも極端に大きな値を設定する。なお、休暇予定があるなどでトリップを部分的に固定する際のネットワークの構成方法は車両の場合と同じである。
【００９９】
次に、図９のステップ0905（運用パターン違反解消）詳細を説明する。乗務員の運用パターンの例としては、先に挙げた「夜勤明けの次の日は休養日とする」の他に、「少なくともＸ日に一回は休暇をとる」、「泊まり行路はＹ日間以上連続しない」等が挙げられる。車両の場合と同様に、運用パターンには法律などで定められた必須のものと、できれば満たしたいという必須でないものがある。
【０１００】
まず図１６は、車両における運用パターン違反解消処理の処理フロー図である。その内容は、図中と実施例１の説明における「車両」または「編成」を「乗務員」に読み替えれば良い。
【０１０１】
図１７は、車両における運用パターン１個の違反解消処理の処理フロー図である。本実施例では、図１７とその説明における「車両」または「編成」を「乗務員」に、「車両の走行履歴と作業履歴」を「乗務員の勤務履歴」、にそれぞれ読み替え、運用パターンの違反の有無の確認は、作業の実施サイクルを用いるのではなく各運用パターン固有のやり方でおこなうことにすれば良い。
【０１０２】
図１９は、車両における計画修正処理の処理フロー図である。本実施例は、ステップ1903（作業の設定処理）とステップ1904（判定処理）は不要なのでこれらを削除する。さらに、ステップ1902の繰返しの判定条件は、「第m-t日が計画作成の範囲外、もしくは第m-t日が運用パターンの範囲外、もしくはそれ以上遡っても違反解消の見込みがなくなるまで」とする。ここで「運用パターンの範囲外になるまで」の例としては、運用パターンが「少なくともＸ日に一回は休暇をとる」であるとして、第m-t日が休暇の場合が挙げられる。また「それ以上遡っても違反解消の見込みがなくなるまで」の例としては、運用パターンが「泊まり行路はＹ日間以上連続しない」であるとして、Ｙ日間遡っても違反を解消できない場合が挙げられる。
【０１０３】
図２０は、車両における第m-t日以降の計画変更処理の処理フロー図である。本実施例のステップ2003で作成するネットワークは、pが0、すなわち着目する日が当日か、もしくはpが0より大きい、すなわち着目する日が翌日以降かに応じて以下のとおり作成方法を切り替える。
【０１０４】
pが0の場合は、リンク長の設定以外は接続違反解消処理におけるネットワーク構成方法と同じである。ただし、あきらかに違反が発生するノードとリンクがあればそれらをネットワークから除外する。ここであきらかに違反が発生する例としては、満足したい運用パターンが「泊まり行路はＮ日以上連続しない」であるとして、自区所に戻らないセグメントが当日の最後の乗務とならないように、自区所に戻らないセグメントから翌日の行路へのリンクを全てカットすることが挙げられる。
【０１０５】
pが0より大きい場合（翌日以降）は、まず第m-t日より以前の計画は変更しないので、当日から第m-t-1日までのノードは全て除外する。さらに開始ノードsからのリンクを第m-t日のノードに対して設定する。そして第p日の行路は、違反解消が可能なものだけをノードとする。ここで違反解消が可能なものの例としては、運用パターンが「泊まり行路はＮ日以上連続しない」であるとして、泊まりではない行路の集合が挙げられる。
【０１０６】
リンク長の設定は、元の計画ではなく現在の計画にできるだけ近い結果が得られるように、現在の計画を経路表現した際に含まれるリンクの長さを小さくし、その他のリンクの長さを大きくする。
【０１０７】
以上が本実施例における違反解消処理の説明である。次に、図２のステップ0203（評価値向上のための計画修正処理）について説明する。
【０１０８】
まず、図２２はこの処理の全体処理フローを示すが、この図とその説明は実施例１と全く同じである。そして、図２４は、図２２のステップ2202（修正解生成処理）の処理フロー図であるが、まずこの図と実施例１の説明における「編成」を「乗務員」に読み替える。そして、ステップ2404の「Ａの計画が変化する修正操作をおこない複数の解を生成」において、実行する修正操作は、実施例１で示した「交換」（図２５）、「追加削除」（図２６）だけでなく、図２７に示す「便乗」を加える。これは便乗をおこなう乗務員を選択し、便乗経路を変更するものである。実施例１と同じく、以上の修正操作はどの部分でも可能なわけではなく、交換によって得られるネットワークのリンクが接続条件を満たさなければならず、固定部分を変更してはならず、資格の有無や習熟度といった乗務員割当条件を満足しなければならない。
【０１０９】
以下は補足事項である。(a)修正操作を実行すると必須の運用パターンに違反が発生する可能性があるので、修正操作の対象となった計画に対しては運用パターン違反解消処理を実行し違反の発生を防ぐ。(b)上記の機械的な「交換」「追加削除」「便乗」以外に、再計画担当者の定石などをパターン化することで対象路線に合った修正操作を定義しても良い、(c)処理時間を短縮するため、あきらかに評価値が悪くなるなど、見込みのない修正操作はおこなわず、生成する解の個数を制限しても良い。
【０１１０】
以上が、第２の実施形態である鉄道分野における統合型乗務員運用再計画システムの説明である。なお、本実施形態は、当日と翌日以降の運用計画を同時に再作成するものであるが、実施例１と同じく当日あるいは翌日以降の一方だけを対象とした再計画も可能である。また、これも実施例１と同じく白紙からの計画作成をおこなうこともできる。
【実施例３】
【０１１１】
以下では第３の実施形態について説明する。本実施例は、実施例１と同じく車両の運用計画を再作成する統合型車両運用再計画システム2800である。使用するデータや装置構成は第１の実施形態とほとんど同じだが、再計画の実行方法が次の点で異なる。(a)実施例１は、違反解消と評価値向上の２段階で再計画をおこなうが、本実施例は処理を二つに分けない。(b)本実施例は、最適化演算手法を用いて解を生成する過程で暫定解と最適解との評価値の差（ギャップ）がどれだけあるかを推定し、得られた計画の最適さの度合いをその数値で出力することができる。
【０１１２】
図２８は、本実施例の機能並びに装置構成を示す図である。同一の構成要素に対しては図１と同じ符号を付した。図１と異なるのは、処理装置0110の内部である。処理装置0110はCPU（図示せず）およびメモリを備え、メモリには当日と翌日以降の運用計画を合わせた形で再計画をおこなう再計画手段2801がプログラムとして格納される。これは図１の再計画手段0111とは異なるものであり、以降でその詳細を説明する。
【０１１３】
図２９は、再計画手段2801の処理フロー図である。なお、以下で説明する再計画方法に対応する各動作は、処理装置0110のCPUが、メモリに読み出して実行するプログラムによって実現される。そしてプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
【０１１４】
まずステップ2901において、再計画手段2801が図２８の記憶装置0110に格納されている情報を読込み、処理装置0110のワークエリア0113内に配置する。以降の説明では、特に断らない限り必要な情報はワークエリア0113から取得するものとする。読み込んだ情報のうち、ダイヤ変更当日の運用計画0122に、列車ダイヤに生じた変更を反映させて、計画の対象とする列車を当初の計画から変更する。次にステップ2902において、再計画手段2801が、変更した列車及び翌日以降の行路に対して車両を割り当て直す運用計画の作成問題を、以下で述べる多品種流問題とみなし、それを数式で表現した数理モデルを構築する。
【０１１５】
多品種流問題とは、ネットワーク上に複数のアイテム（品種）を流すことを考え、その流れを最適化する問題である。本実施形態においては各編成をアイテムとし、計画作成範囲の最初から最後までリンクを介してトリップをつないでいくことをアイテムを流すと捉える。この流れのことを以降ではフローと呼ぶ。
【０１１６】
ネットワークは、ノード、リンク、リンクのコストから構成される。本実施形態では、トリップ（列車と行路）をノードとし、接続条件を満たすノードの組合せに対してリンクをはりネットワークを構成する。ただし、回送を許す場合は当日のノードと翌日のノードの間に接続条件を満たさないリンクを設定しても良い。これは実施例１において各編成毎の最短経路問題を解くために用いるネットワーク（例えば図１４）とほぼ同じであり、特別なノードである開始ノードsと終了ノードtも持つ。ただし、次の３点が異なる。(1)ここでは全ての編成の計画を同時に算出することから、トリップが既に他の編成に割当られているかの区別はせず、再計画対象の全てのトリップをノードとする。(2) トリップを割当てない予備編成も同時に扱うことから、トリップを一切割当てないフローを許す必要がある。したがって、開始ノードを始点、終了ノードを終点とする特別なリンクを設定する。このリンクのことを以降では「空リンク」と呼ぶ。(3)開始ノードsから全てのノードにリンクをはる。同様に全てのノードから終了ノードtにリンクをはる。
【０１１７】
最適化とは、アイテムを流すために必要なコストを最小化することである。フローのコストは、フローに含まれるリンクのコストの合計として定義される。
【０１１８】
リンクのコストは最適化したい評価指標に応じて定義の仕方が異なる。評価指標の例として「元の計画からの変更を少なくする」が挙げられる。この場合、アイテムkをノードiからノードjへのリンクijに流すコストckijは次のように定義される。すなわち、元の計画をフローで表現し、(a)リンクijがアイテムkのフローに含まれる場合をa、(b)それ以外の場合をbとし、0 ≦ a ＜ bとする。a, bの具体的な値は、例えばa=0, b=1000である。リンクのコストをこのように定義すれば、編成kのフローが元の計画のフローに近いほどコストが小さくなる。
【０１１９】
他の評価指標の例として「接続の切替回数をできるだけ少なくする」が挙げられる。「接続の切替」とは、端末駅での列車の折り返し関係、すなわち折り返し前と折り返し後の列車の組合わせを元の計画から変えることである。折り返し関係を変更すると、例えば間合い時間が短くなり車内清掃ができなくなるといったように業務に支障をきたすことがあるため、なるべく変更しないことが望ましい。この場合のコストckijは、元の計画をフローで表現し、(a)リンクijが任意のフローに含まれる場合をa, (b)それ以外の場合をbとし、0 ≦ a ＜ bとする。a, bの具体的な値は、例えばa=0, b=1000である。
【０１２０】
他の評価指標の例として「予備の使用回数をできるだけ少なくする」が挙げられる。この場合のコストckijは、kが予備でなければ全て0、kが予備ならば、(a)リンクijが空リンクの場合をa, (b)空リンク以外の開始ノードから伸びるリンクの場合をbとし、0 ≦ a ＜ bとする。それ以外のリンクに対しては0を設定する。a, bの具体的な値は、例えばa=0, b=1000である。
【０１２１】
他の評価指標の例として「当日の終了場所の変更をできるだけ少なくする」が挙げられる。この場合のコストckijは、(a)リンクijが翌日のノード、または終了ノードにつながるもので、かつノードiの終了場所がkの元の計画における終了場所と同じ場合をa, (b)異なる場合をbとし、0 ≦ a ＜ bとする。それ以外のリンクに対しては0を設定する。a, bの具体的な値は、例えばa=0, b=1000である。
【０１２２】
他の評価指標の例として「回送をできるだけ少なくする」が挙げられる。この場合のコストckijは、(a)リンクijが当日ノードを始点、翌日ノードを終点とするもので、かつノードiの終了場所とノードjの開始場所が同じ場合をa, (b)異なる場合をbとし、0 ≦ a ＜ bとする。それ以外のリンクに対しては0を設定する。a, bの具体的な値は、例えばa=0, b=1000である。
【０１２３】
複数の評価指標を同時に扱う場合は、各評価指標のコストを合計したり線形加重和を取るなどしてひとつにまとめる。例えば上記の評価指標をまとめ、「元の計画からの変更を少なくする、変更がある場合は接続の切替回数をできるだけ少なく、予備の使用回数をできるだけ少なく、当日の終了場所の変更をできるだけ少なく、回送をできるだけ少なくする」という評価指標を扱う場合は、まずアイテムk、リンクijに対して「元の計画からの変更を少なくする」のコストを得てこれをア）とし、次に「接続の切替回数をできるだけ少なくする」のコストを得てこれをイ）とし、次に「予備の使用回数をできるだけ少なくする」のコストを得てこれをウ）とし、次に「当日の終了場所の変更をできるだけ少なくする」のコストを得てこれをエ）とし、次に「回送をできるだけ少なくする」のコストを得てこれをオ）とし、ア）、イ）、ウ）、エ）、オ）の合計をckijとする。
【０１２４】
以下では、運用計画の作成問題を多品種流問題とみなし、それを数式で表現した数理モデルについて説明する。まず、数式を記述するための各種記号を以下のとおり定義する。
【０１２５】
Vはノードの集合である。その要素数をnとする。Eはリンクの集合である。E1はEの部分集合であり、当日のノードの集合を表す。E2はEの部分集合であり、翌日以降のノードの集合を表す。ノードiを始点、ノードjを終点とするリンクをaij、または(i,j)と表記する。Rはアイテムの集合である。その要素数をmとする。sは開始ノードである。tは終了ノードである。数式定義の簡便さのため、集合Vの要素を表す添え字1とnに関し、添え字1が開始ノードs、添え字nが終了ノードtに対応するものとする。xkijは決定変数である。アイテムkのフローがリンク(i,j)を含むならばxkijは値1を、それ以外ならば値0を取る。yiも決定変数である。ノードiのトリップに必要な編成の数と実際に割当てられた数との差分、すなわち編成の不足数を表す。必要編成数は通常は1だが、当日ノードで併合がある場合は併合する編成の数に等しくなる。yi が1以上、すなわち編成の割当不足がある場合は列車の運行が不可能なので、(1)該当列車を運休する、(2)編成の追加や時刻変更などの設定変更をした上で再作成する、のいずれかの対応が必要となる。di はノードiの必要編成数である(di≧1）。ekijはリンクの選択可否を表すフラグである。アイテムkをリンク（i,j)に流すことが可能ならばekijは値1を、それ以外ならば値0を取る。これは、開始ノードs,終了ノードtと接続可能なノードを各アイテム毎に設定するためと、充当できない列車や逆に充当しなければならない列車がある場合に用いる。ckijは前述のとおりアイテムkをリンク(i,j)に流すコストである。wは編成の不足に対するコストである。運用計画作成においては、不足が生じないように編成を割当てることが最も重要なことから、wにはckijよりも十分に大きな値を設定する。すなわち、max ckij ≪ w  である。
【０１２６】
この定義の下で、運用計画作成のための多品種流問題の数理モデルは次のとおりとなる。
【０１２７】
【数１】
2010285053.tif 000003
【０１２８】
【数２】
2010285053.tif 000004
【０１２９】
【数３】
2010285053.tif 000005
【０１３０】
【数４】
2010285053.tif 000006
【０１３１】
【数５】
2010285053.tif 000007
【０１３２】
【数６】
2010285053.tif 000008
【０１３３】
【数７】
2010285053.tif 000009
【０１３４】
【数８】
2010285053.tif 000010
【０１３５】
式(１)は目的関数である。フローのコストと編成不足のコストの合計を最小化することを表す。式(2)から(8)は制約条件である。式(2)は、各アイテムのフローは開始ノードから始まることを表す。式(3)は、各アイテムのフローは終了ノードで終わることを表す。式(4)は、決定変数の値はリンクの選択可否eに従うことを表す。式(5)は、各ノードではフローの量が保存されることを表す。式(6)は、各ノードにおいてフローの量（割り当てた編成数を表す）と編成の不足数との合計は要求編成数に等しいことを意味する。式(7)は決定変数xkijが0または1をとる0-1整数変数であることを示す。式(8)は決定変数yiが0から要求編成数までの離散値を取る整数変数であることを示す。
【０１３６】
図２９のステップ2902では、再計画手段2801がダイヤ乱れにともなう列車の変更を反映後の計画に基づいて上記の数理モデルを構築し、図２８の処理装置0110のメモリに格納する。
【０１３７】
次にステップ2903では、再計画手段2801が、最適化演算手法を用いて数理モデルの解、すなわち決定変数xkijとyiの値を定める。本実施例は、最適化演算手法として数理計画法の一種であるラグランジュ緩和法を適用する。その処理内容を図３０の処理フロー図を用いて説明する。まずステップ3001において、再計画手段2801が数理モデルからラグランジュ緩和問題（の数理モデル）を構築する。なお、以降ではステップ2902で作成した数理モデルが表す問題を「主問題」と呼ぶ。
【０１３８】
ラグランジュ緩和問題とは、主問題の制約式の一部をラグランジュ乗数を用いて目的関数に組み込むことにより制約を部分的に取り除いた問題を指す。制約が取り除かれた分だけ解空間に加えられる制限が緩くなることから緩和問題と呼ばれる。どの制約式を緩和するかは主問題の数理モデルや解法設計の考え方に依存する。本実施例では式(6)の制約を緩和して以下のラグランジュ緩和問題を構成する。
【０１３９】
【数９】
2010285053.tif 000011
【０１４０】
【数２】
2010285053.tif 000012
【０１４１】
【数３】
2010285053.tif 000013
【０１４２】
【数４】
2010285053.tif 000014
【０１４３】
【数５】
2010285053.tif 000015
【０１４４】
【数７】
2010285053.tif 000016
【０１４５】
【数８】
2010285053.tif 000017
【０１４６】
これは目的関数を式(1)のかわりに式(9)とし、かつ式(6)を削除したものである。式(9)は、式(1)を拡張したものであり、式(6)とラグランジュ乗数λからなる(A)項が追加されている。λが非負であれば、この項は式(6)の違反件数に応じてペナルティλをコストに加算することと解釈できる。制約違反のない実行可能解であればこの項は0となり、目的関数の値は主問題と一致する。
【０１４７】
図３０に戻り説明を続ける。ステップ3002では、再計画手段2801がラグランジュ乗数λを初期化し、反復回数kを1に設定する。λの初期化方法は特に規定しない。ランダムに設定しても良いし、一律に定数(例えば0)を与えても良いし、他の方針に従ってリンク毎に異なる値を設定しても良い。他の方針としては、任意のリンク(q,i)のコストを、後述するアイテムkをリンク(q,i)に流す調整コストckqi ＝(ckqi-λi)で置き換えたネットワークを考え、そのネットワーク上で各アイテムの最短経路を算出すると、それらが全て元の計画に一致する、あるいはできるだけ一致するように各λiの値を定めることにしても良い。
【０１４８】
次にステップ3003において、再計画手段2801が乗数λを固定してラグランジュ緩和問題の最適解を生成する。その考え方を以下に示す。
【０１４９】
まず、ラグランジュ緩和問題の目的関数である式(9)は、適当な式変形を施すことで以下に示す形式となる。
【０１５０】
【数１０】
2010285053.tif 000018
【０１５１】
ただし、λ0とλnは式変形の便宜上定義したもので、値は常に0とする。
【０１５２】
式(10)の(C)項は定数項なので、問題を解く上で無視しても構わない。一方、(A)項の係数(ckqi-λi)をコストckqiとラグランジュ乗数λによる新たなコストとみなせば、(A)項はアイテムkのフローのコストを表している。そして、(B)項の係数(w-λi)をコストwとラグランジュ乗数λによる新たなコストとみなせば、(B)項は不足編成に対するコストの総和を表している。さらに、この問題の制約条件である式(2)(3)(4)(5)(7)(8)の中に複数のアイテムに跨るものは存在しない。以上の考察から、このラグランジュ緩和問題は、次に示すアイテムk毎の部分問題、
【０１５３】
【数１１】
2010285053.tif 000019
【０１５４】
【数１２】
2010285053.tif 000020
【０１５５】
【数１３】
2010285053.tif 000021
【０１５６】
【数１４】
2010285053.tif 000022
【０１５７】
【数１５】
2010285053.tif 000023
【０１５８】
【数１６】
2010285053.tif 000024
【０１５９】
と、変数yに関する部分問題、
【０１６０】
【数１７】
2010285053.tif 000025
【０１６１】
【数８】
2010285053.tif 000026
【０１６２】
とに分割し、それぞれを独立に解くことができる。
【０１６３】
アイテムk毎の部分問題の目的関数における決定変数の係数(ckqi-λi)をあらためて調整コストckqiとすれば、この問題はリンクの長さがckqiで与えられるネットワーク上で、開始ノードsから終了ノードtを結ぶ最短経路を求める問題に帰着できる。なお、式(14)を満足するため、ネットワークのリンクの中でekijが0のリンクは削除する。実施例１で説明した様に、ダイクストラ法を用いれば最短経路問題を容易に解くことができる。ただしダイクストラ法は、負の長さのリンクがある場合、必ずしも最短経路をみつけることができないため、これを用いて上記の問題を解くことはできない。なぜなら調整コストckqiは、ckqi <λのとき負の値を取るからである。したがって本実施例では、リンクの長さが負であっても適用可能な解法である「べき乗法」、またはべき乗法の改良版である「ベルマン-フォード法」を用いて最短経路を求める。ただし適用する解法はこれらに限定するものではなく、負の長さのリンクを含んでいる場合でも最短経路を正しく算出できるならば他のどのような手法を用いても良い。
【０１６４】
一方、変数yに関する部分問題は実質的に制約条件を持たないため、最適解を求めるのはきわめて容易である。すなわち、目的関数の決定変数の係数(w-λi)をあらためて調整コストwiとし、wi≧0のノードiに対しては変数yiを0に、wi<0のノードiに対しては変数yiをdiにすれば良い。
【０１６５】
以上よりステップ3003では、再計画手段2801が、まず適当な順番でアイテムを選択し、最短経路問題を繰返し解くことでアイテムk毎の最適解を求め、最後に変数yに関する部分問題の最適解を上記の方法で算出する。
【０１６６】
次にステップ3004では、再計画手段2801が主問題の実行可能解を生成する。変数xk1nを全て1、その他の変数xを全て0、決定変数yiを全てdiにすれば実行可能解を容易に得ることができる。ただし、これは全てのトリップに編成を割当てないことを意味するので、実際には受け容れられない計画である。そこで、ここでは図３１に示す方法を用い、各反復におけるラグランジュ乗数の値を反映した実行可能解を算出する。
【０１６７】
図３１では、まずステップ3101において各ノードiの選択回数をカウントする変数piの値を0に初期化する。次にステップ3102からステップ3108で囲まれる一連のステップを、全ての変数を選択するまで繰返し実行する。繰返しの詳細は次のとおりである。まずステップ3103において未処理のアイテムをひとつ取り出し、これをkとする。ここで複数の候補がある場合は、予備編成に該当するアイテムを後回しにする、あるいはそれ以外の方法など、任意のやり方に基づいておこなう。次にステップ3104において、調整コストckqiをリンク長とするネットワーク上で開始ノードsから終了ノードtまでの最短経路を探索する。得られた最短経路はアイテムkのフローを表しているので、ステップ3105において、これからフロー変数xkijの値を決定する。すなわち、リンク(i,j)が最短経路に含まれればxkijの値を1、それ以外は0とする。次にステップ3106に進み、最短経路に含まれるノードの選択回数を1だけ増やす。ステップ3107では、選択回数piが必要編成数diと等しくなったノードiを探し、それらをネットワークから全て削除する。当然であるが、削除したノードに接続するリンクもこのとき削除する。繰返しを終了した後はステップ3109へ進み、変数yiの値をdi-piにセットして処理を終了する。
【０１６８】
図３０に戻り説明を続ける。ステップ3005では、再計画手段2801が反復処理の終了判定をおこなう。ステップ3003で得られたラグランジュ緩和問題の最適解をAとすると、ラグランジュ緩和問題の性質より、Aの目的関数値は主問題の最適解の下界値を与える。したがってこれが最適値と等しければ緩和問題の解は主問題の最適解を与えることになる。よって理想的にはステップ3005においてAが最適解と等しいかどうかを判定し、等しい場合には反復処理を終了し、Aを最終結果として出力すれば良い。
【０１６９】
しかしながら、実際には様々な理由から緩和問題の最適値と主問題の最適値との差を0にできる保証はない。そこでステップ3004で得られた主問題の実行可能解(Bとする)を利用し、これまでの反復で得られたBのうちで目的関数値が最も小さい(すなわち最適解に最も近い)解と、同様にこれまでの反復で得られた目的関数値が最も大きいA（最適解の最良の下界値を与える）とを比較し、両者の目的関数値の差（ギャップ）があらかじめ設定した値より小さくなった時点で反復処理を終了する。また、反復をいくら繰り返しても設定値よりギャップが縮まらない可能性があるので、反復回数が規定回数に到達した場合には無条件で反復を終了する。反復を終了したらステップ3008に進み、反復で得られた最も良いBとそのギャップの値を、準最適解と、準最適解と最適解の評価値の推定値との差分情報として出力して全体処理を終了する。
【０１７０】
ステップ3005の終了判定でNoの場合はステップ0306に進む。ここでは再計画手段2801が、ラグランジュ乗数λの更新をおこなう。ラグランジュ緩和問題の解(A)は前述の通り最適解の下界値を与えることから、ここではAが最適解にさらに近づくようにλを変更する。この更新法については微分不可能最適化の分野と関連が深く、従来から様々な手法が提案されている。本実施例では劣勾配法を用いるが他の方法を用いても良い。λを更新した後はステップ3007に進み反復回数kの値を1増やす。その後は再びステップ3003へ戻り処理を繰り返す。
【０１７１】
図２９に戻り、再計画処理の説明を続ける。ステップ2903で数理モデルを最適化演算によって解き準最適な実行可能解を得た後は、ステップ2904に進む。ここでは再計画手段2801が、得られた解を運用計画に変換して図２８の表示装置0140に出力する。それと同時に変数yiが0より大きいノードを特定し、該当するトリップに編成が割当てられなかったことを示す参考情報を表示装置0140に出力する。再計画担当者はこれを受けて、 (1)該当するトリップを運休にする、(2)編成の追加や時刻変更などの設定変更をした上で再計画をおこなう、のいずれかを図２８の入力装置0130を介しておこなう。ここではさらに、得られた解と最適値の下界とのギャップの値を表示装置0140に出力する。これは再計画結果の最適さの度合いを評価する参考情報となる。また、計画を編成毎にチェックし、当日の終了場所と翌日の開始場所に不一致があれば回送の設定が必要な旨を表示装置0140に出力するための参考情報を生成する。さらには他の情報として、制約条件の未充足部分や評価指標の充足度合い等をここで生成して表示装置0140が運用計画とあわせて出力しても良い。
【０１７２】
以上が、第３の実施形態である鉄道分野における統合型車両運用再計画システム2800の説明である。なお、本実施例は、当日と翌日以降の運用計画を同時に再作成するものであるが、実施例１と同じく当日あるいは翌日以降の一方だけを対象とした再計画も可能である。また、これも実施例１と同じく白紙からの計画作成をおこなうこともできる。また、(1)まずリンクのコストckijを全て0として不足編成のコストが最小となるように再計画をおこない、編成を割当られない列車の数を最小化し、(2)次に、編成を割当てられなかった列車を除外、コストckijを目的の評価指標に基づいて設定、さらに編成不足のコストwiを全て0として再計画をもう一度おこなう、という2段階の処理により、編成がどうしても割当てられない列車を確実に特定し、割当可能な列車だけを対象として再計画をおこなうことができる。
【実施例４】
【０１７３】
以下では第４の実施形態について説明する。本実施例は、実施例２と同じく乗務員の運用計画を再作成する統合型乗務員運用再計画システムである。また、本実施例は実施例３と同じく再計画を一つの処理で実行し、その過程で暫定解と最適解との評価値の差（ギャップ）を推定するので、得られた計画の最適さの度合いを数値として出力することができる。
【０１７４】
以下では、実施例３との相違点を中心に本実施例を説明する。まず、機能並びに装置構成は図２８と全く同一である。ただし、(a)記憶装置0120の当日計画0122は車両ではなく乗務員の当日計画を格納する。(b)翌日以降計画0123は車両ではなく乗務員の翌日以降計画を格納する。(c)基礎情報0124には、計画作成の対象となる乗務員の定義情報、各種労働条件の定義情報、列車が停車、通過する駅の定義情報、乗務員の勤務履歴、運用パターン、が少なくとも含まれる。
【０１７５】
以下で説明する違反解消方法および計画修正方法に対応する各動作は、実施例３と同様、処理装置0110のCPUが、メモリに読み出して実行するプログラムによって実現される。そしてプログラムは、以下に説明される各種の動作を行うためのコードから構成されている。
【０１７６】
図２８の再計画手段2801の処理フローは、第３の実施形態（図２９）とほぼ同じである。ただし図の説明を以下のとおり修正する。(a)「車両」あるいは「編成」を「乗務員」に、「列車」を「セグメント」に、「回送」を「乗務員の移動」にそれぞれ読み替える。(b)併合に関する記述は、セグメントが複数の乗務員を必要とする場合と解釈する。(c)評価指標「接続の切替回数をできるだけ少なくする」の説明において、「接続の切替」とは、列車の乗り換えの関係、すなわち乗換え前と乗換え後のセグメントの組合わせを元の計画から変えることとする。乗換えの関係を変更すると、通告券を発行するなどしてその旨を当該乗務員に通知するといった余分な手間が必要になるため、なるべく変更しないことが望ましい。(d)多品種流問題の数理モデルは、(6)式に代えて以下の(18)式を制約式とする。
【０１７７】
【数１８】
2010285053.tif 000027
【０１７８】
この式は、各ノードの流量と乗務員の不足数との合計が要求数以上でなければならないことを意味する。(6)式との違いは比較記号にあり、(6)式は等号であったが、ここでは不等号である。これは乗務員は便乗を許すので、セグメントに割当てられる乗務員が要求数より多くても構わないためである。
【０１７９】
図２９のステップ2903における最適化演算によるモデルの解を求める処理は、第３の実施形態（図３０）とほぼ同じである。ただし図の説明を以下のとおり修正する。(a)「車両」あるいは「編成」を「乗務員」に、「列車」を「セグメント」に、それぞれ読み替える。(b)緩和問題の構成方法は同じだが、ラグランジュ乗数λはこの場合非負となる。(c)主問題の実行可能解算出法は、図３１とその説明において、「編成」を「乗務員」に読み替える。
【０１８０】
以上が、第４の実施形態である鉄道分野における統合型乗務員運用再計画システムの説明である。本実施例は、実施例１、２、３と同じく当日あるいは翌日以降の一方だけを対象とした再計画も可能である。また、これも実施例１、２、３と同じく白紙からの計画作成をおこなうこともできる。また、実施例３と同様に、評価指標を変えて再計画処理を2回おこなうことにより、乗務員が割当てられないセグメントの数をまず最小化し、未割当のセグメントを除いた上でその他の評価指標を考慮した再計画結果を得ることができる。
【符号の説明】
【０１８１】
0100  統合型車両運用再計画システム
0110  処理装置
0120  記憶装置
0130  入力装置
0140  表示装置
0111  再計画手段
0112  計画修正手段
0113  ワークエリア
0121  列車ダイヤ
0122  当日運用計画
0123  翌日以降運用計画
0124  基礎情報
0125  評価指標
【図１】
2010285053.tif 000028
【図２】
2010285053.tif 000029
【図３】
2010285053.tif 000030
【図４】
2010285053.tif 000031
【図５】
2010285053.tif 000032
【図６】
2010285053.tif 000033
【図７】
2010285053.tif 000034
【図８】
2010285053.tif 000035
【図９】
2010285053.tif 000036
【図１０】
2010285053.tif 000037
【図１１】
2010285053.tif 000038
【図１２】
2010285053.tif 000039
【図１３】
2010285053.tif 000040
【図１４】
2010285053.tif 000041
【図１５】
2010285053.tif 000042
【図１６】
2010285053.tif 000043
【図１７】
2010285053.tif 000044
【図１８】
2010285053.tif 000045
【図１９】
2010285053.tif 000046
【図２０】
2010285053.tif 000047
【図２１】
2010285053.tif 000048
【図２２】
2010285053.tif 000049
【図２３】
2010285053.tif 000050
【図２４】
2010285053.tif 000051
【図２５】
2010285053.tif 000052
【図２６】
2010285053.tif 000053
【図２７】
2010285053.tif 000054
【図２８】
2010285053.tif 000055
【図２９】
2010285053.tif 000056
【図３０】
2010285053.tif 000057
【図３１】
2010285053.tif 000058