(57)【要約】【課題】  乗務員運用変更計画を自動的に作成すること。【解決手段】  乗務案作成部１１０は、運転整理ダイヤを構成する各列車を乗り継ぎ可能駅で分割した列車乗務単位の何れかを組合せることによって、当該乗務員が乗務可能な運用変更行路を乗務案として作成するとともに、各乗務案にそれぞれコストを設定する。乗務員運用変更計画作成部１２０は、各乗務員用に作成された乗務案の中からそれぞれ１つずつ選択した乗務案の組合せのうち、列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを探索し、当該組合せを構成する乗務案をそれぞれ該当する乗務員の運用変更行路とすることで、乗務員運用変更計画を作成する。【選択図】図２
2006056282.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、所与の運転整理ダイヤに対する所与の人数の乗務員による乗務員運用変更計画のデータを作成させるためのプログラムであって、
前記運転整理ダイヤを構成する各列車の運転情報を乗り継ぎ可能駅で分割することにより、発着時刻及び発着駅で定義される複数の列車乗務単位に分割する分割手段、
前記分割された複数の列車乗務単位の何れかを組合せることにより前記各乗務員それぞれの乗務可能な行路を乗務案として作成する乗務案作成手段、
前記作成された乗務案の中から、前記各乗務員それぞれの乗務案を１つずつ選択し、前記複数の列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを求める取得手段、
前記取得手段により求められた乗務案の組合せに基づいて乗務員運用変更計画のデータを作成する計画作成手段、
として前記コンピュータを機能させるためのプログラム。
【請求項２】
請求項１に記載のプログラムであって、
前記各乗務員の乗務起点駅及び乗務終点駅を入力する入力手段として前記コンピュータを更に機能させ、
前記乗務案作成手段が、前記各乗務員それぞれの乗務可能な行路として、当該乗務員について前記入力された乗務起点駅を発駅とする列車乗務単位と、乗務終点駅を着駅とする列車乗務単位とを含む列車乗務単位の組合せを作成するように前記コンピュータを機能させる、
ためのプログラム。
【請求項３】
請求項１又は２に記載のプログラムであって、
前記乗務案作成手段により作成された各乗務案のコストを、所定のコスト評価条件に従って算出する乗務案コスト算出手段として前記コンピュータを機能させ、
前記取得手段が、前記複数の列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを複数求めるように前記コンピュータを機能させ、
前記計画作成手段が、前記取得手段により求められた複数の組合せのうち、乗務案の総合コストに基づいて選択した組合せに従って乗務員運用変更計画のデータを作成するように前記コンピュータを機能させる、
ためのプログラム。
【請求項４】
請求項３に記載のプログラムであって、
前記運転整理ダイヤの運転整理前の列車ダイヤに対する前記各乗務員それぞれの行路を記憶する乗務員運用計画記憶手段として前記コンピュータを機能させ、
前記乗務案コスト算出手段が、前記乗務案作成手段により作成された各乗務案のコストとして、当該乗務案の行路と前記乗務員運用計画記憶手段により記憶されている行路との差異に応じた行路比較コストを算出する行路比較コスト算出手段を有するように前記コンピュータを機能させる、
ためのプログラム。
【請求項５】
請求項３又は４に記載のプログラムであって、
前記各乗務員の基準帰着時刻を記憶する基準帰着時刻記憶手段として前記コンピュータを機能させ、
前記乗務案コスト算出手段が、前記乗務案作成手段により作成された各乗務案のコストとして、当該乗務案の帰着時刻と、対応する乗務員の前記基準帰着時刻との時間差に応じた帰着時刻コストを算出する帰着時刻コスト算出手段を有するように前記コンピュータを機能させる、
ためのプログラム。
【請求項６】
請求項３〜５の何れか一項に記載のプログラムであって、
前記乗務案コスト算出手段が、前記乗務案作成手段により作成された各乗務案のコストとして、当該乗務案中に所定の休憩時間が含まれるか否かに応じた休憩時間コストを算出する休憩時間コスト算出手段を有するように前記コンピュータを機能させるためのプログラム。
【請求項７】
請求項３〜６の何れか一項に記載のプログラムであって、
前記取得手段が、前記乗務案コスト算出手段により算出されたコストが所定の条件を満たす乗務案のみで乗務案の組合せを求め、前記所定の条件を所定のタイミングで変更するように前記コンピュータを機能させるためのプログラム。
【請求項８】
請求項３〜７の何れか一項に記載のプログラムであって、
前記取得手段により求められた複数の組合せそれぞれのコスト偏差を、当該組合せに含まれる各乗務案の前記乗務案コスト算出手段により算出されたコストの偏差に基づいて算出するコスト偏差算出手段として前記コンピュータを機能させ、
前記計画作成手段が、前記取得手段により求められた複数の組合せの中から、乗務案の総合コストと、前記コスト偏差算出手段により算出された当該組合せのコスト偏差とに基づいて一の組合せを選択し、選択した一の組合せに従って乗務員運用変更計画のデータを作成するように前記コンピュータ機能させる、
ためのプログラム。
【請求項９】
所与の運転整理ダイヤに対する所与の人数の乗務員による乗務員運用変更計画のデータを作成する乗務員運用変更計画作成装置であって、
前記運転整理ダイヤを構成する各列車の運転情報を乗り継ぎ可能駅で分割することにより、発着時刻及び発着駅で定義される複数の列車乗務単位に分割する分割手段と、
前記分割された複数の列車乗務単位の何れかを組合せることにより前記各乗務員それぞれの乗務可能な行路を乗務案として作成する乗務案作成手段と、
前記作成された乗務案の中から、前記各乗務員それぞれの乗務案を１つずつ選択し、前記複数の列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを求める取得手段と、
前記取得手段により求められた乗務案の組合せに基づいて乗務員運用変更計画のデータを作成する計画作成手段と、
を備える乗務員運用変更計画作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乗務員運用変更計画を作成するためのプログラム及び乗務員運用変更計画作成装置に関する。
【背景技術】
【０００２】
従来から、鉄道では、ダイヤ改正の際等において、計画された列車の運行スケジュール（計画ダイヤ）を実現するための種々の計画を定めている。例えば、車両運用計画と呼ばれる車両の運用に関する計画や、乗務員運用計画と呼ばれる運転士及び車掌等の業務に従事する列車の乗務員の運用に関する計画等である。車両運用計画は、車両の使用順序や、車両に対する保守管理を含む車両の運用スケジュールを定めたものであり、また乗務員運用計画は、計画ダイヤを構成する全ての列車に対して必要な乗務員を割り当てた乗務員の運用スケジュールを定めたものである。
【０００３】
また、従来から、前述の車両運用計画や乗務員運用計画を自動的に作成する技術が知られている。例えば、特許文献１には、計画ダイヤを構成する各列車に車両を割り当てて車両の運用パスを作成し、各車両の運用パス間で列車の交換を繰り返すことによって、車両運用計画を自動的に作成する手法が開示されている。またこの特許文献１では、車両を列車の乗務員に置き換えることにより、前述の手法を用いて乗務員運用計画を作成することが可能な旨が記載されている。
【特許文献１】特開２００３−３０６１４７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところで、事故等の影響で突発的にダイヤの乱れが発生し、計画ダイヤの変更計画（以下、「運転整理ダイヤ」という。）が作成された場合には、運転整理ダイヤをもとに上記した車両運用計画や乗務員運用計画を修正・変更する作業が行われるが、このうち、乗務員運用計画の変更計画（乗務員運用変更計画）は、作成者の知識や経験等に基づいて手作業で行われているのが現状である。しかしながら、その作成段階においては、例えば偏りなく各乗務員に均等に乗務させたいといった要望や、乗務員運用計画で定めていた乗務終点駅に各乗務員を帰着させるといった制約等、様々な制約を考慮する必要がある。また、迅速に作成しなければならないため、規模の大きさ等によってその作成は極めて複雑且つ困難な問題となり、作成者の負担が大きいという問題が生じていた。
【０００５】
本発明は、上記した従来の問題点に鑑みてなされたものであり、乗務員運用変更計画を自動的に作成することを目的とする。
【課題を解決するための手段】
【０００６】
以上の課題を解決するための第１の発明は、コンピュータに、所与の運転整理ダイヤに対する所与の人数の乗務員による乗務員運用変更計画のデータを作成させるためのプログラムであって、
前記運転整理ダイヤを構成する各列車の運転情報を乗り継ぎ可能駅で分割することにより、発着時刻及び発着駅で定義される複数の列車乗務単位に分割する分割手段（例えば、図２に示す乗務案作成部１１０）、
前記分割された複数の列車乗務単位の何れかを組合せることにより前記各乗務員それぞれの乗務可能な行路を乗務案として作成する乗務案作成手段（例えば、図２に示す乗務案作成部１１０）、
前記作成された乗務案の中から、前記各乗務員それぞれの乗務案を１つずつ選択し、前記複数の列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを求める取得手段（例えば、図２に示す乗務員運用変更計画作成部１２０）、
前記取得手段により求められた乗務案の組合せに基づいて乗務員運用変更計画のデータを作成する計画作成手段（例えば、図２に示す乗務員運用変更計画作成部１２０）、
として前記コンピュータを機能させるためのプログラムである。
【０００７】
また、第９の発明は、所与の運転整理ダイヤに対する所与の人数の乗務員による乗務員運用変更計画のデータを作成する乗務員運用変更計画作成装置であって、
前記運転整理ダイヤを構成する各列車の運転情報を乗り継ぎ可能駅で分割することにより、発着時刻及び発着駅で定義される複数の列車乗務単位に分割する分割手段（例えば、図２に示す乗務案作成部１１０）と、
前記分割された複数の列車乗務単位の何れかを組合せることにより前記各乗務員それぞれの乗務可能な行路を乗務案として作成する乗務案作成手段（例えば、図２に示す乗務案作成部１１０）と、
前記作成された乗務案の中から、前記各乗務員それぞれの乗務案を１つずつ選択し、前記複数の列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを求める取得手段（例えば、図２に示す乗務員運用変更計画作成部１２０）と、
前記取得手段により求められた乗務案の組合せに基づいて乗務員運用変更計画のデータを作成する計画作成手段（例えば、図２に示す乗務員運用変更計画作成部１２０）と、
を備えるものである。
【０００８】
この第１又は第９の発明によれば、各列車の運転情報を乗り継ぎ可能駅で分割した複数の列車乗務単位の何れかを組合せることにより、各乗務員それぞれの乗務可能な行路を乗務案として作成することができる。そして、作成した乗務案の中から各乗務員それぞれの乗務案を１つずつ選択し、前記複数の列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを求めることによって、乗務員運用変更計画を作成することができる。これにより、運転整理ダイヤを構成する全ての列車に乗務員が割り当てられた乗務員運用変更計画であって、各乗務員が乗り継ぎ可能駅で乗り継ぎ可能な乗務員運用変更計画を自動的に作成することができる。
【０００９】
第２の発明は、第１の発明のプログラムであって、
前記各乗務員の乗務起点駅及び乗務終点駅を入力する入力手段（例えば、手入力であってもよいし、記憶媒体から読み込むこととしてもよい）として前記コンピュータを更に機能させ、
前記乗務案作成手段が、前記各乗務員それぞれの乗務可能な行路として、当該乗務員について前記入力された乗務起点駅を発駅とする列車乗務単位と、乗務終点駅を着駅とする列車乗務単位とを含む列車乗務単位の組合せを作成するように前記コンピュータを機能させる、
ためのプログラムである。
【００１０】
この第２の発明によれば、各乗務員が各々乗務起点駅を発駅とし、乗務終点駅を着駅とした行路に乗務可能な乗務員運用変更計画を作成することができる。
【００１１】
第３の発明は、第１又は第２の発明のプログラムであって、
前記乗務案作成手段により作成された各乗務案のコストを、所定のコスト評価条件に従って算出する乗務案コスト算出手段（例えば、図２に示す乗務案作成部１１０）として前記コンピュータを機能させ、
前記取得手段が、前記複数の列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを複数求めるように前記コンピュータを機能させ、
前記計画作成手段が、前記取得手段により求められた複数の組合せのうち、乗務案の総合コストに基づいて選択した組合せに従って乗務員運用変更計画のデータを作成するように前記コンピュータを機能させる、
ためのプログラムである。
【００１２】
この第３の発明によれば、所定のコスト評価条件に従って算出された各乗務案のコストを算出することができる。そして、前記複数の列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを複数求め、これらのうち、乗務案の総合コストに基づいて選択した組合せに従った乗務員運用変更計画を作成することができる。
【００１３】
第４の発明は、第３の発明のプログラムであって、
前記運転整理ダイヤの運転整理前の列車ダイヤに対する前記各乗務員それぞれの行路を記憶する乗務員運用計画記憶手段（例えば、図２に示す乗務員運用計画データ８３０）として前記コンピュータを機能させ、
前記乗務案コスト算出手段が、前記乗務案作成手段により作成された各乗務案のコストとして、当該乗務案の行路と前記乗務員運用計画記憶手段により記憶されている行路との差異に応じた行路比較コストを算出する行路比較コスト算出手段（例えば、図２に示す乗務案作成部１１０）を有するように前記コンピュータを機能させる、
ためのプログラムである。
【００１４】
この第４の発明によれば、乗務案のコストとして、当該乗務案が示す行路と、運転整理ダイヤの運転整理前の列車ダイヤに対する該当する乗務員の行路との差異に応じた行路比較コストを算出することができ、各乗務員の行路変更が少ない乗務員運用変更計画を作成することができるようになる。
【００１５】
第５の発明は、第３又は第４の発明のプログラムであって、
前記各乗務員の基準帰着時刻を記憶する基準帰着時刻記憶手段（例えば、図２に示す乗務員スケジュールデータ８４０）として前記コンピュータを機能させ、
前記乗務案コスト算出手段が、前記乗務案作成手段により作成された各乗務案のコストとして、当該乗務案の帰着時刻と、対応する乗務員の前記基準帰着時刻との時間差に応じた帰着時刻コストを算出する帰着時刻コスト算出手段（例えば、図２に示す乗務案作成部１１０）を有するように前記コンピュータを機能させる、
ためのプログラムである。
【００１６】
この第５の発明によれば、乗務案のコストとして、当該乗務案の帰着時刻と、対応する乗務員の基準帰着時刻との時間差に応じた帰着時刻コストを算出することができ、時間差の少ない乗務案を当該乗務員の行路とした乗務員運用変更計画を作成することができるようになる。
【００１７】
第６の発明は、第３〜第５の何れかの発明のプログラムであって、
前記乗務案コスト算出手段が、前記乗務案作成手段により作成された各乗務案のコストとして、当該乗務案中に所定の休憩時間が含まれるか否かに応じた休憩時間コストを算出する休憩時間コスト算出手段（例えば、図２に示す乗務案作成部１１０）を有するように前記コンピュータを機能させるためのプログラムである。
【００１８】
この第６の発明によれば、乗務案のコストとして、当該乗務案中に所定の休憩時間が含まれるか否かに応じた休憩時間コストを算出することができる。
【００１９】
第７の発明は、第３〜第６の何れかの発明のプログラムであって、
前記取得手段が、前記乗務案コスト算出手段により算出されたコストが所定の条件を満たす乗務案のみで乗務案の組合せを求め、前記所定の条件を所定のタイミングで変更するように前記コンピュータを機能させるためのプログラムである。
【００２０】
この第７の発明によれば、設定されたコストが所定の条件を満たす乗務案のみで乗務案の組合せを求めることができる。そして、所定のタイミングにおいて、前記所定の条件を変更することができる。
【００２１】
第８の発明は、第３〜第７の何れかの発明のプログラムであって、
前記取得手段により求められた複数の組合せそれぞれのコスト偏差を、当該組合せに含まれる各乗務案の前記乗務案コスト算出手段により算出されたコストの偏差に基づいて算出するコスト偏差算出手段（例えば、図２に示す乗務案作成部１１０）として前記コンピュータを機能させ、
前記計画作成手段が、前記取得手段により求められた複数の組合せの中から、乗務案の総合コストと、前記コスト偏差算出手段により算出された当該組合せのコスト偏差とに基づいて一の組合せを選択し、選択した一の組合せに従って乗務員運用変更計画のデータを作成するように前記コンピュータ機能させる、
ためのプログラムである。
【００２２】
この第８の発明によれば、前記取得手段により求められた複数の組合せの中から、乗務案の総合コストと、当該組合せのコスト偏差とに基づいて選択した組合せに従った乗務員運用変更計画を作成することができる。
【発明の効果】
【００２３】
本発明によれば、各列車の運転情報を乗り継ぎ可能駅で分割した複数の列車乗務単位の何れかを組合せることにより、各乗務員それぞれの乗務可能な行路を乗務案として作成することができる。そして、作成した乗務案の中から各乗務員それぞれの乗務案を１つずつ選択し、前記複数の列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを求めることによって、乗務員運用変更計画を作成することができる。これにより、運転整理ダイヤを構成する全ての列車に乗務員が割り当てられた乗務員運用変更計画であって、各乗務員が乗り継ぎ可能駅で乗り継ぎ可能な乗務員運用変更計画を自動的に作成することができる。
【発明を実施するための最良の形態】
【００２４】
以下、図面を参照して、本発明を適用した乗務員運用変更計画作成装置について詳細に説明する。尚、以下では、１台のパーソナル・コンピュータ（以下、パソコンという。）で乗務員運用変更計画作成装置を構成することとして説明するが、これに限定されるものではない。
【００２５】
［乗務員運用変更計画について］
本実施形態の乗務員運用変更計画作成装置は、列車の遅延が発生した際に乗務員運用計画の変更計画（乗務員運用変更計画）を自動的に作成するものである。尚、以下では、「乗務員」を例えば運転士とし、運転士の運用計画の変更計画を作成する場合を例にとって説明する。
【００２６】
乗務員運用計画とは、上記したように、計画ダイヤを構成する全ての列車に対して必要な乗務員を割り当てた乗務員の運用スケジュールを定めたものである。図１（ａ）は、計画ダイヤに対する乗務員運用計画の一例を示す図である。図１（ａ）では、横軸を時刻、縦軸を駅Ｓ１，Ｓ２，Ｓ３として、駅Ｓ１及び駅Ｓ３の駅間を運行する列車番号Ｔ１〜Ｔ９が割り当てられた各列車を列車スジにより表しており、各列車スジは、乗務員運用計画として作成された乗務員の運用行路（以下、「運用計画行路」という。）に基づく接続線で接続されている。
【００２７】
各運用計画行路は、乗務員の一日分の運用行路を示しており、例えば運用計画行路１は、乗務員が、駅Ｓ３から列車Ｔ１に乗車して駅Ｓ２まで乗務し、次いで、駅Ｓ１まで列車Ｔ２に乗務し、駅Ｓ１で折り返して列車Ｔ４、列車Ｔ６に順次乗務して駅Ｓ３で降車し、さらに列車Ｔ７に乗務して駅Ｓ２で乗務終了となることを意味する。乗務員運用計画は、全ての列車スジが何れかの運用計画行路に含まれるように作成されるものであり、図１（ａ）に示す乗務員運用計画においては、２人の乗務員が運用計画行路１及び２に従ってそれぞれ列車に乗務することにより計画ダイヤを実現している。
【００２８】
ところで、列車の遅延が発生して、例えば列車Ｔ４及びＴ５の運転を中止とした運転整理ダイヤが作成された場合には、当該日に運用計画行路１に乗務する乗務員（仮に運転士Ｍ１とする）が駅Ｓ２から運転される列車Ｔ６に乗務できない、或いは運用計画行路２に乗務する乗務員（仮に運転士Ｍ２とする）が駅Ｓ１から運転される列車Ｔ８に乗務できない、という事態が生じる。このような事態に対処するため、鉄道では、上記したように、運転整理ダイヤをもとに乗務員運用変更計画を作成する作業が行われる。
【００２９】
図１（ｂ）は、運転整理ダイヤに対する乗務員運用変更計画の一例を示す図である。詳細には、図１（ａ）に示す列車Ｔ４及びＴ５を運休とした運転整理ダイヤに対する乗務員運用変更計画の一例を示す図であり、図１（ｂ）において、各列車スジは、乗務員運用変更計画として作成された乗務員（運転士Ｍ１，Ｍ２）の運用変更行路（以下、単に「運用変更行路」という。）に基づく接続線で接続されている。この乗務員運用変更計画によれば、図１（ａ）に示す運用計画行路１に従って列車に乗務する予定であった乗務員（運転士Ｍ１）は運用変更行路１に従って列車に乗務し、図１（ａ）に示す運用計画行路２に従って列車に乗務する予定であった乗務員（運転士Ｍ２）は運用変更行路２に従って列車に乗務することとなる。
【００３０】
実際には、この乗務員運用変更計画は、以下に示す制約を守るように作成されなければならない。先ず、第１に、運転整理ダイヤを構成する全ての列車に対して必要な乗務員を割り当てなければならない。第２に、乗務員同士による乗務の交代は、予め定められた乗務員の乗り継ぎが可能な駅（乗り継ぎ可能駅）で行わなければならない。第３に、乗務員が列車を乗り継ぐ際には、前後の列車の着時刻と発時刻との間に、乗り継ぎに必要な最小限の時間を確保する必要がある。加えて、列車を乗り継ぐ際、前後の列車で着駅と発駅とが異なる場合には、当該乗務員を他の乗務員が乗務する列車に乗車させる等して乗り継ぎ先の列車の発駅まで輸送する必要がある。第４に、各乗務員が、それぞれ所定の乗務終点駅（或いは乗務終了基地）で乗務を終了できるように運用変更行路を作成しなければならない。
【００３１】
また、乗務員運用変更計画は、前述の制約を守るとともに、以下に示すような事項を満足するように作成されることがより望ましい。
【００３２】
すなわち、各乗務員が、食事時間等の休憩時間を確保できることが望ましい。そして、連続して列車に乗務する時間が極端に長くならないこと、当初の予定からの超過勤務時間が極端に長くならないことが望ましい。また、各乗務員の列車への乗務時間になるべく不公平が生じないことが望ましい。さらに、乗務員への行路変更の情報伝達に係る手間やこれに伴う伝達ミスを考慮すれば、当該日に各乗務員が乗務する予定であった運用計画行路からの変更がなるべく少ないことが望ましい。
【００３３】
本実施形態では、運転整理ダイヤを構成する各列車を乗り継ぎ可能駅で分割した列車乗務単位で列車を乗り継ぐ乗務案を乗務員毎に複数作成し、各乗務員用の乗務案の中からそれぞれ１つずつ選択した組合せのうち、上記制約を守り、且つ上記要望をなるべく満足するような乗務案の組合せを探索し、探索された組合せを構成する乗務案をそれぞれ該当する乗務員の運用変更行路とすることで、乗務員運用変更計画を自動的に作成するものである。
【００３４】
［機能構成］
次に、乗務員運用変更計画作成装置１０の機能構成について説明する。図２は、乗務員運用変更計画作成装置１０の機能構成の一例を示すブロック図である。図２に示すように、乗務員運用変更計画作成装置１０は、ＣＰＵ１００、ＲＯＭ２００、入力装置３００、表示装置４００、通信装置５００、ＲＡＭ６００、記憶装置７００、記憶媒体８００により構成され、記憶媒体８００以外の各部はバス９００により接続されている。
【００３５】
ＣＰＵ１００は、乗務員運用変更計画作成装置１０を構成する各機能部への指示やデータの転送等を行って乗務員運用変更計画作成装置１０を統括的に制御する。具体的には、ＣＰＵ１００は、入力装置３００を介して入力される操作信号等に応じて、ＲＯＭ２００や記憶装置７００が備える記憶媒体８００内に格納された各種プログラムを読み出してＲＡＭ６００に展開し、当該プログラムに従って処理を実行する。そして、処理結果をＲＡＭ６００に格納するとともに、当該処理結果を表示するための表示信号を表示装置４００に出力する。さらに、ＲＡＭ６００内に格納した処理結果の一部或いは全てを、記憶媒体８００へ保存する。
【００３６】
このＣＰＵ１００により種々の機能が実現されるが、特に、乗務案を作成する機能部を乗務案作成部１１０、乗務員運用変更計画を作成する機能部を乗務員運用変更計画作成部１２０と呼び、以下説明する。尚、この乗務案作成部１１０、及び乗務員運用変更計画作成部１２０の各機能部は、別個独立したＣＰＵ等によって実現してもよい。
【００３７】
乗務案作成部１１０は、乗務案作成プログラム８１０に従って乗務案作成処理を実行する。具体的には、乗務案作成部１１０は、運転整理ダイヤを構成する各列車を乗り継ぎ可能駅で分割した列車乗務単位の何れかを組合せることによって、当該乗務員が乗務可能な運用変更行路を乗務案として作成するとともに、各乗務案にそれぞれコストを設定する。
【００３８】
ここで、図３を参照して乗務案作成処理について説明する。図３（ａ）は、計画ダイヤに対する乗務員運用変更計画の一例を示す図である。ここで、例えば、列車スジＬ１及びＬ２で表される列車を運休とした運転整理ダイヤが作成されたとし、当該日の運転士の乗務スケジュールとして、運転士Ｍ１０に運用計画行路１０が、運転士２０に運用計画行路２０が、運転士３０に運用計画行路３０が、それぞれ割り当てられていたとする。
【００３９】
先ず、乗務案作成部１１０は、運転整理ダイヤを構成する各列車を、乗り継ぎ可能駅で分割することで列車乗務単位に分割する。例えば、図３（ａ）において、駅Ｓ１０，Ｓ１２，Ｓ１４の各駅が乗り継ぎ可能駅であった場合には、当該運転整理ダイヤを構成する各列車は、図３中“１”〜“１２”の各番号が付された各列車乗務単位に分割される。
【００４０】
続いて、乗務案作成部１１０は、運用変更行路を割り当てる乗務員（運転士Ｍ１０〜Ｍ３０）毎に、それぞれ以下の処理を実行する。すなわち、乗務案作成部１１０は、前述のように分割した列車乗務単位の何れかを組合せることにより、当該乗務員に割り当てる運用変更行路の候補となる乗務案を作成する。
【００４１】
詳細には、当該乗務員の乗務起点駅が発駅となり、乗務終点駅が着駅となるような列車乗務単位の組合せを作成する。より詳細には、この列車乗務単位の組合せは、乗り継がれる前後の列車乗務単位において、乗り継ぎ駅への着時刻と、当該乗り継ぎ駅からの発時刻との間に乗務員の乗り継ぎに必要な最小限の時間が確保されるように、且つ、当該組合せが示す運用変更行路の発時刻が、該当する乗務員が当該日に乗務する予定であった運用計画行路の乗務起点駅からの発時刻以降となるように作成される。このようにして列車乗務単位の組合せを作成することで、各乗務案が表す運用変更行路は、それぞれ上記第２〜第４の各制約を満足した運用変更行路となる。
【００４２】
図３（ｂ）は、図３（ａ）に示す“１”〜“１２”の各列車乗務単位を組合せることで作成された各乗務員用の乗務案を示す図である。例えば、運転士Ｍ１０に着目すれば、図３（ａ）の乗務員運用計画で示すように、当該運転士Ｍ１０の乗務起点駅及び乗務終点駅は駅Ｓ１０であり、乗務員Ｍ１０の各乗務案である運用変更行路は、発駅及び着駅が駅Ｓ１０となるような列車乗務単位の組合せにより表される。
【００４３】
続いて、乗務案作成部１１０は、作成した各乗務案にそれぞれコストを設定する。ここで、コストの算出方法について説明する。
【００４４】
（ａ）行路比較コスト
行路比較コストとは、当該乗務案が示す運用変更行路と、該当する乗務員が当該日に乗務する予定であった運用計画行路との差異に応じて算出される値であり、差異が大きくなる程算出される値は大きくなる。列車乗務単位毎に算出・加点される具体例としては、例えば、当該乗務案が示す運用変更行路に含まれる列車乗務単位であって、該当する乗務員の運用計画行路に含まれない列車乗務単位を対象に“＋１”、当該乗務案が示す運用変更行路に含まれない列車乗務単位であって、該当する乗務員の運用計画行路に含まれる列車乗務単位を対象に“＋２”というように加点値が予め定められており、乗務案作成部１１０は、この加点値に従って当該乗務案の行路比較コストを算出する。このように行路比較コストを算出することにより、当該乗務案に対して、該当する乗務員が乗務する予定であった運用計画行路からの変更度合いに基づくコストを設定することができる。
【００４５】
（ｂ）帰着時刻コスト
帰着時刻コストとは、当該乗務案が示す運用変更行路の乗務終点駅への帰着時刻と、該当する乗務員が当該日に乗務する予定であった運用計画行路の乗務終点駅への帰着時刻（基準帰着時刻）との時間差に応じて加算される値であり、時間差が大きくなる程算出される値は大きくなる。具体例としては、前述の時間差が３０分以上の乗務案を対象に“＋１”、１時間以上の乗務案を“＋２”というように加点値が予め定められており、乗務案作成部１１０は、この加点値に従って当該乗務案の帰着時刻コストを算出する。このように帰着時刻コストを算出することにより、当該乗務案に対して、該当する乗務員が乗務する予定であった運用計画行路による乗務終了時刻からの超過勤務時間に基づくコストを設定することができる。
【００４６】
（ｃ）休憩時間コスト
休憩時間コストとは、当該乗務案中に食事時間等の所定の休憩時間が含まれない場合に加算される値であり、休憩時間が含まれないと算出される値は大きくなる。具体例としては、例えば、午前６時から午前１０時までの朝食時間帯、午前１１時から午後４時までの昼食時間帯、午後６時から午後１０時までの夕食時間帯、といった各食事時間帯において、列車乗務単位間の乗り継ぎが無い場合、及び有ったとしてもその乗り継ぎ時間が所定時間未満となる場合に“＋１”というように加点値が予め定められており、乗務案作成部１１０は、この加点値に従って当該乗務案の休憩時間コストを算出する。このように休憩時間コストを算出することにより、当該乗務案に対して、該当する乗務員が取得できる休憩時間の有無及びその期間に基づくコストを設定することができる。
【００４７】
乗務案作成部１１０は、（ａ）〜（ｃ）で説明した行路比較コスト、帰着時刻コスト、及び休憩時間コストの各値をもとに、当該乗務案のコストを以下の数式（１）に従って算出する。
【数１】
2006056282.tif 000003
尚、ｎ＝３とし、ｃ1を行路比較コスト、ｃ2を帰着時刻コスト、ｃ3を休憩時間コストの各値、そしてｗ1〜ｗ3をそれぞれのコストに対する重みとする。このそれぞれのコストに対する重みは、固定値であってもよいし、事故等の状況に応じて各コストの重要度を適宜判断し、その都度設定される値であってもよい。
【００４８】
乗務員運用変更計画作成部１２０は、乗務員運用変更計画作成プログラム８２０に従って乗務員運用変更計画作成処理を実行する。具体的には、乗務員運用変更計画作成部１２０は、各乗務員用に作成された乗務案の中からそれぞれ１つずつ選択した乗務案の組合せのうち、列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを探索し、当該組合せを構成する乗務案をそれぞれ該当する乗務員の運用変更行路とすることで、乗務員運用変更計画を作成する。
【００４９】
ここで、図４を参照して乗務員運用変更計画作成処理について説明する。図４は、図３（ｂ）に示した各運転士Ｍ１０，Ｍ２０，Ｍ３０用の乗務案をもとに、列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを探索する際の処理工程を説明するための図である。先ず、乗務員運用変更計画作成部１２０は、各乗務員用に作成された乗務案の中から、それぞれコストの値が最も小さい乗務案を選択した組合せを初期解として作成する。例えば、図４（ａ）に示すように、図３（ｂ）に示す各乗務員用の乗務案の中からコストの値が最も小さい乗務案がそれぞれ選ばれて初期解（候補解）が作成される。
【００５０】
次に、乗務員運用変更計画作成部１２０は、作成した乗務案の組合せを参照して、乗務員が割り当てられていない列車乗務単位の中から一の列車乗務単位を選択し、当該選択した列車乗務単位を含む一の乗務案を選択する乗務案選択処理を行う。そして、候補解変更処理として以下の処理を行う。すなわち、先ず、前記乗務案選択処理によって選択した一の乗務案の乗務員を判定する。次いで、当該時点での候補解を構成する前記判定された乗務員の乗務案を、前記乗務案選択処理によって選択した乗務案に変更して候補解を更新する。尚、乗務案を選択する際の条件として、設定されたコストの値が予め設定されたコスト閾値（例えば、初期値を“１０”とする）以下の乗務案が選択対象とされる。
【００５１】
例えば、図４（ａ）に示す乗務案の組合せをもとにして乗務案選択処理が行われることで、何れの乗務案にも含まれない列車乗務単位“５”が選択されたとする。そして、当該列車乗務単位“５”を含む乗務案として、コスト閾値（例えば、“１０”）以下のコストが設定された運転士Ｍ２０の乗務案（ロ）が選択された場合には、図４（ｂ）に示すように、候補解は、運転士Ｍ２０の乗務案を当該選択した乗務案（ロ）とした解に変更される。
【００５２】
そして、乗務員運用変更計画作成部１２０は、乗務案選択処理及び候補解変更処理を繰り返し実行することにより、列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを探索する。
【００５３】
例えば、図４（ｂ）に示す乗務案の組合せをもとにして再度乗務案選択処理が行われることにより、何れの乗務案にも含まれない列車乗務単位“６”が選択されるとともに、当該列車乗務単位“６”を含む乗務案として、コスト閾値以下のコストが設定された運転士Ｍ２０の乗務案（ハ）が選択された場合には、図４（ｃ）に示すように、候補解は、運転士Ｍ２０の乗務案を当該選択した乗務案（ハ）とした解に変更される。
【００５４】
尚、前述のように乗務案選択処理及び候補解変更処理を所定回数繰り返し実行しても、列車乗務単位すべてに１以上の乗務員が割り当てられた乗務案の組合せが探索されなかった場合には、乗務員運用変更計画作成部１２０は、前述のコスト閾値に所定値（例えば、“３”）を加算してコスト閾値を変更した後、再度乗務案選択処理及び候補解変更処理を繰り返し実行することにより、列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを探索する。
【００５５】
そして、乗務員運用変更計画作成部１２０は、各列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せが探索された際には、当該候補解の評価値を以下の数式（２）に従って算出する。
評価値＝総合コスト＋α  ・・・（２）
尚、総合コストを、当該候補解を構成する乗務案に設定されたコストの合計値とし、αを、総合コストの標準偏差（コスト偏差）とする。
【００５６】
このように上記（２）の式に従って候補解の評価値を算出することにより、各乗務員の列車への乗務時間に不公平が生じているかを評価基準として、評価値を算出することができる。
【００５７】
例えば、図４（ｄ）に示すように、“１”〜“１２”の各列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せが探索された際には、当該乗務案の組合せが最良解となる。このようにして、乗務員運用変更計画作成部１２０が、乗務案作成部１１０により分割された列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを探索することにより、上記第１の制約を満足した乗務員運用変更計画を作成することができる。尚、一の列車乗務単位に複数の乗務員が割り当てられている場合には、当該列車乗務単位に対応する列車に複数の乗務員が乗務する（すなわち、複数の運転士が当該列車に乗務する）こととなるが、この場合には、一の運転士が列車を運転し、他の運転士は、当該一の運転士が乗務する列車に便乗して次回の乗り継ぎ駅まで移動することとなる。
【００５８】
さらに、本実施形態では、乗務員運用変更計画作成部１２０は、上記した各列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを探索する処理を複数回繰り返し実行することにより、より評価の高い（すなわち、評価値の小さい）乗務案の組合せを探索する。尚、新たに乗務案の組合せを探索する際には前述のコスト閾値は、初期値にリセットされる。
【００５９】
具体的には、乗務員運用変更計画作成部１２０は、得られた最良解を候補解とし、この候補解をもとに以下の処理を実行する。すなわち、先ず、乗務員運用変更計画作成部１２０は、乗務員を選択する。選択の仕方としては、例えばコストの値が最も大きい乗務案の乗務員を選択することとしてもよいし、ランダムに乗務員を選択することとしてもよい。次いで、乗務員運用変更計画作成部１２０は、当該選択した乗務員の乗務案を他の乗務案に変更する。変更する際の選択の仕方は、コストの値が最も小さい乗務案を選択することとしてもよいし、ランダムに乗務案を選択することとしてもよい。そして、乗務員運用変更計画作成部１２０は、候補解を、該当する乗務員の乗務案を選択した乗務案に変更した解に変更する。
【００６０】
そして、乗務員運用変更計画作成部１２０は、変更された候補解をもとに前述の乗務案選択処理及び候補解変更処理を繰り返し実行することにより、列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを新たに探索する。
【００６１】
例えば、図４（ｄ）に示す乗務案の組合せに従い、コストの値が最も大きい乗務員である運転士Ｍ１０が選択され、当該運転士Ｍ１０の乗務案として、コスト閾値以下のコストが設定された乗務案の中から例えば当該運転士Ｍ１０の乗務案（イ）が選択された場合には、図４（ｅ）に示すように、候補解は、運転士Ｍ１０の乗務案を当該選択した乗務案（イ）とした解に変更される。
【００６２】
ＲＯＭ２００には、各種初期設定、ハードウェアの構成、又は必要なプログラムのロード等を行うための初期プログラムが格納される。
【００６３】
入力装置３００は、カーソルキー、テンキー、各種ファンクションキー等を備えたキーボード、及びマウス等のポインティングデバイス等により実現されるものであり、これらが操作された場合には、その操作に応じた操作信号をＣＰＵ１００に出力する。
【００６４】
表示装置４００は、例えば、ＬＣＤ（Liquid Crystal Display）やＥＬＤ（Electronic Luminescent Display）等の表示装置であり、ＣＰＵ１００から入力される表示信号に基づく各種画面を表示する。
【００６５】
通信装置５００は、装置内部で利用される情報を通信回線を介して外部とやりとりするための装置であり、他の装置との通信を行うための制御を行う。
【００６６】
ＲＡＭ６００は、ＣＰＵ１００の作業用メモリとして用いられる半導体メモリであり、ＣＰＵ１００が実行するプログラムや、これらプログラムの実行に係るデータ等を一時的に保持するメモリ領域を備える。特に、本実施形態を実現するため、候補解及びその総合コストを保持する候補解格納領域６１０と、暫定解及びその総合コストを保持する暫定解格納領域６２０と、最良解及びその評価値を保持する最良解格納領域６３０と、コスト閾値を保持するコスト閾値格納領域６４０とを備える。
【００６７】
記憶装置７００は、磁気的、光学的記憶媒体、或いは半導体メモリ等で構成される記憶媒体８００を備え、記憶媒体８００からのデータの読み出しや記憶媒体８００へのデータの書き込みを行う。
【００６８】
記憶媒体８００は、記憶装置７００に固定的に設けたもの、或いは着脱自在に装着するものであり、各種処理プログラムや、これらの処理プログラムにより処理されたデータ等が格納される。特に、本実施形態を実現するため、ＣＰＵ１００を乗務案作成部１１０として機能させるための乗務案作成プログラム８１０と、乗務員運用変更計画作成部１２０として機能させるための乗務員運用変更計画作成プログラム８２０とが格納される。
【００６９】
また、記憶媒体８００には、データとして、乗務員運用計画データ８３０と、乗務員スケジュールデータ８４０と、運転整理ダイヤデータ８５０と、列車乗務単位一覧テーブル８６０と、乗務案データ８７０と、乗務員運用変更計画データ８８０とが格納される。
【００７０】
乗務員運用計画データ８３０は、ダイヤ改正の際等において計画ダイヤに基づいて作成された乗務員運用計画のデータを記憶する。図５は、乗務員運用計画データ８３０の一例を示す図である。図５に示すように、乗務員運用計画データ８３０には、乗務員運用計画を更生する運用計画行路のデータが格納される。各運用計画行路データには、運用計画行路の行路番号と対応付けて、列車乗務単位での乗り継ぎ順序が定義されている。
【００７１】
乗務員スケジュールデータ８４０は、列車に乗務する乗務員のスケジュールを日毎に蓄積記憶する。図６は、１日分の乗務員スケジュールデータ８４０のデータ構成例を示す図である。図６に示すように、乗務員スケジュールデータ８４０は、乗務員毎に、当該日の乗務員の担当行路と、乗務開始時刻と、乗務終了時刻とがそれぞれ設定されている。この乗務員スケジュールデータ８４０は、運転整理の対象となった列車に乗務する乗務員や、当該乗務員の乗務起点駅及びその時刻、乗務終点駅及びその時刻等を特定するために参照される。
【００７２】
運転整理ダイヤデータ８５０は、列車遅延の発生に応じて作成された運転整理ダイヤを構成する各列車の列車データを記憶する。この列車データには、例えば、当該列車の列車番号や列車種別、当該列車が着発する各駅における着発時刻といった情報が含まれる。図７（ａ）は、運転整理ダイヤデータ８５０に格納される列車データのデータ構造の一例を示す図である。図７（ａ）に示すように、列車データには、列車番号と対応付けて、当該列車番号の列車が着発する着発駅毎のダイヤデータが格納される。各ダイヤデータには、当該列車の着発時刻が定義される。図７（ｂ）は、運転整理ダイヤデータ８５０のデータ構成例を示す図であり、当該運転整理ダイヤを構成する全ての列車データが蓄積される。
【００７３】
列車乗務単位一覧テーブル８６０は、運転整理ダイヤを構成する各列車を乗り継ぎ可能駅で分割した列車乗務単位の一覧を記憶する。この列車乗務単位は、当該列車乗務単位の発着駅及び発着時刻により定義される。図８は、列車乗務単位一覧テーブル８６０のデータ構成例を示す図である。図８に示すように、列車乗務単位一覧テーブル８６０は、各列車乗務単位に割り振られた列車乗務単位番号と対応付けて、該当する列車番号と、発駅情報と、着駅情報とが格納される。発駅情報としては当該列車乗務単位の発駅及び発時刻が設定され、着駅情報としては当該列車乗務単位の着駅及び着時刻が設定される。この列車乗務単位一覧テーブル８６０は、運転整理ダイヤデータ８５０をもとに乗務案作成部１１０によって作成される。
【００７４】
乗務案データ８７０は、乗務員毎に作成された乗務案の一覧を記憶する。図９は、乗務案データ８７０のデータ構成例を示す図である。図９に示すように、乗務案データ８７０には、乗務案番号と対応付けて、それぞれ各乗務員用に作成された乗務案の一覧が、コストの値が小さいものから順に格納される。この乗務案データ８７０は、乗務員運用計画データ８３０、乗務員スケジュールデータ８４０、及び列車乗務単位一覧テーブル８６０をもとに乗務案作成部１１０によって作成される。
【００７５】
乗務員運用変更計画データ８８０は、本乗務員運用変更計画作成装置１０により作成され最良解となった乗務員運用変更計画のデータを記憶する。詳細には、乗務員運用変更計画データ８８０には、運用変更行路の番号と対応付けて、当該運用変更行路を示す列車乗務単位での列車の乗り継ぎ順序と、当該運用変更行路に従って列車に乗務する担当乗務員とが設定される。
【００７６】
［処理の流れ］
次に、本実施形態におけるＣＰＵ１００の処理の流れについて、図１０に示すフローチャートを参照して説明する。尚、ここで説明する処理は、ＣＰＵ１００が乗務案作成プログラム８１０及び乗務員運用変更計画作成プログラム８２０を読み出して実行することにより実現される。
【００７７】
先ず、乗務案作成部１１０が、運転整理ダイヤデータ８５０を参照し、運転整理ダイヤを構成する各列車を乗り継ぎ可能駅で分割することで列車乗務単位に分割する（ステップｓ１０）。またこの際、乗務案作成部１１０は、分割した列車乗務単位に番号を割り振るとともに、運転整理ダイヤデータ８５０から、該当する列車番号、発駅及びその発時刻、着駅及びその着時刻を読み出し、これらを対応付けて列車乗務単位一覧テーブル８６０に設定する。
【００７８】
次に、乗務案作成部１１０は、各乗務員用の乗務案を作成する（ステップｓ２０）。具体的には、乗務案作成部１１０は、運用変更行路を割り当てる各乗務員を処理対象として、それぞれ以下の処理を実行する。
【００７９】
すなわち、先ず、乗務案作成部１１０は、運転整理ダイヤデータ８５０及び当該日の乗務員スケジュールデータ８４０を参照し、現在時刻をもとに処理対象の乗務員の乗務起点駅を特定するとともに、担当行路の乗務終点駅を特定する。そして、乗務案作成部１１０は、特定した乗務起点駅が発駅となり、乗務終点駅が着駅となるような列車乗務単位の組合せを作成する。より詳細には、乗務案作成部１１０は、乗り継がれる前後の列車乗務単位において、乗り継ぎ駅への着時刻と、当該乗り継ぎ駅からの発時刻との間に乗務員の乗り継ぎに必要な最小限の時間が確保されるように、且つ、当該組合せが示す運用変更行路の発時刻が、該当する乗務員が当該日に乗務する予定であった運用計画行路の乗務起点駅からの発時刻以降となるように、列車乗務単位の組合せを作成する。このステップｓ２０で作成された乗務案は、乗務員毎に乗務案データ８７０に格納される。
【００８０】
次に、乗務案作成部１１０は、作成した各乗務案にそれぞれコストを設定する（ステップｓ３０）。具体的には、乗務案作成部１１０は、上記したように、行路比較コスト、帰着時刻コスト、及び休憩時間コストの値をそれぞれ算出する。そして、乗務案作成部１１０は、上記した数式（１）によって当該乗務案のコストを算出し、該当する乗務案と対応付けて乗務案データ８７０に格納する。
【００８１】
続いて、乗務員運用変更計画作成部１２０が、各乗務員用に作成された乗務案の中から、それぞれコストの値が最も小さい乗務案を選択した組合せを初期解として生成し、当該初期解を構成する各乗務案の総合コストを算出する（ステップｓ４０）。またこの際、乗務員運用変更計画作成部１２０は、当該生成した初期解及びその総合コストを候補解格納領域６１０及び暫定解格納領域６２０に格納して初期化する。
【００８２】
次に、乗務員運用変更計画作成部１２０は、コスト閾値を初期値（例えば、“１０”）にリセットしてコスト閾値格納領域６４０を更新する（ステップｓ５０）。
【００８３】
次に、乗務員運用変更計画作成部１２０は、候補解が示す乗務案の組合せを参照し、乗務員が割り当てられていない列車乗務単位を検出する（ステップｓ６０）。そして、検出された場合には（ステップｓ６０：ＹＥＳ）、乗務員運用変更計画作成部１２０は、コスト閾値を変更するか否かを判定する（ステップｓ７０）。
【００８４】
具体的には、ステップｓ６０において、候補解を構成する各乗務案の何れにも含まれない列車乗務単位が連続して検出された回数が所定回数となった場合にコスト閾値を変更すると判定し（ステップｓ７０：ＹＥＳ）、現時点でのコスト閾値に所定値を加算して、コスト閾値格納領域６４０を更新する（ステップｓ８０）。例えば、ステップｓ６０〜ステップｓ１３０の処理を所定回数繰り返しても、候補解を構成する各乗務案の何れにも含まれない列車乗務単位が検出される場合には、コスト閾値に所定値（例えば、“３”）を加算することで、列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを探索され易くする。
【００８５】
次に、乗務員運用変更計画作成部１２０は、候補解格納領域６１０を参照し、候補解格納領域６１０に格納されている候補解を構成する何れの乗務案にも含まれない列車乗務単位の中から、一の列車乗務単位をランダムに選択する（ステップｓ９０）。
【００８６】
次いで、乗務員運用変更計画作成部１２０は、前記選択した列車乗務単位を含む一の乗務案であって、設定されているコストの値が現時点でのコスト閾値以下の乗務案の中から、一の乗務案を選択する（ステップｓ９５）。
【００８７】
具体的には、乗務員運用変更計画作成部１２０は、先ず、乗務案データ８７０を参照し、前記選択した列車乗務単位を含む乗務案であって、コストの値が現時点でのコスト閾値以下の乗務案を抽出する。続いて、乗務員運用変更計画作成部１２０は、抽出した各乗務案についてそれぞれ以下の処理を行う。すなわち、先ず、当該乗務案の乗務員を判定する。次いで、当該時点での候補解を構成する前記判定した乗務員の乗務案を、当該乗務案に変更した場合の解の総合コストを算出する。これを抽出した各乗務案について行い、総合コストが最も小さくなる乗務案を選択する。尚、ここでは、前記抽出した乗務案のうち、得られる解の総合コストが最も小さくなる乗務案を選択することとしたが、以下のようにしてもよい。すなわち、各解について、それぞれ当該解を構成する乗務案の何れにも含まれない列車乗務単位の数を計数し、この数を考慮して乗務案を選択する（例えば計数した数が少ない乗務案を選択する）こととしてもよい。
【００８８】
そして、乗務員運用変更計画作成部１２０は、ステップＳ９５で選択した乗務案の乗務員を判定し、判定した乗務員の乗務案をステップＳ９５で選択された乗務案に変更して候補解を更新する（ステップ１００）。またこの際、乗務員運用変更計画作成部１２０は、更新した候補解の総合コストを算出して、候補解格納領域６１０に格納する（ステップｓ１００）。
【００８９】
次に、乗務員運用変更計画作成部１２０は、候補解の総合コストと暫定解の総合コストとを比較判定する。そして、乗務員運用変更計画作成部１２０は、候補解の総合コストが暫定解の総合コストより小さい場合には（ステップｓ１１０：ＹＥＳ）、候補解及びその総合コストで暫定解格納領域６２０を更新して（ステップｓ１２０）、ステップｓ６０に戻る。一方、候補解の総合コストが暫定解の総合コストより大きい場合には（ステップｓ１１０：ＮＯ）、暫定解及びその総合コストで候補解格納領域６１０を更新して（ステップｓ１３０）、ステップｓ６０に戻る。
【００９０】
一方、ステップｓ６０において、乗務員が割り当てられていない列車乗務単位が検出されなかった場合、すなわち、全ての列車乗務単位が何れかの乗務案に含まれている場合には、乗務員運用変更計画作成部１２０は、上記した数式（２）によって当該候補解の評価値を算出する（ステップｓ１４０）。またこの際、乗務員運用変更計画作成部１２０は、現時点での最良解の評価値よりも算出した候補解の評価値の方が小さければ、算出した候補解及び算出した評価値で最良解格納領域６３０を更新する。
【００９１】
続いて、乗務員運用変更計画作成部１２０は、最良解を確定するか否かを判定する（ステップｓ１５０）。具体的には、乗務員運用変更計画作成部１２０は、ステップｓ６０において乗務員が割り当てられていない列車乗務単位が検出されないと判定された回数が所定回数（例えば、１０回）となった場合には、最良解を確定すると判定し（ステップｓ１５０：ＹＥＳ）、最良解格納領域６３０に保持されている最良解を構成する各乗務案（運用変更行路）の組合せを乗務員運用変更計画として確定し、乗務員運用変更計画データ８８０として記憶媒体８００に格納して、本処理を終了する。
【００９２】
一方、最良解を確定しないと判定した場合には（ステップｓ１５０：ＮＯ）、乗務員運用変更計画作成部１２０は、最良解及びその総合コストで候補解格納領域６１０を更新した後、一の乗務員を選択する。そして、乗務員運用変更計画作成部１２０は、候補解を、当該選択した乗務員の乗務案を他の乗務案に変更した解に変更し、当該候補解の総合コストを算出して、候補解格納領域６１０を更新する（ステップｓ１６０）。そして、乗務員運用変更計画作成部１２０は、ステップｓ５０に戻って上記した処理を実行する。
【００９３】
以上説明したように、本実施形態によれば、先ず、運転整理ダイヤを構成する各列車を乗り継ぎ可能駅で分割した列車乗務単位とする。次いで、分割した列車乗務単位の何れかを組合せることによって、各乗務員の運用変更行路を乗務案として作成する。次いで、各乗務員用に作成された乗務案の中からそれぞれ１つずつ選択した乗務案の組合せのうち、列車乗務単位総てに１以上の乗務員が割り当てられた乗務案の組合せを探索する。そして、探索された乗務案の組合せを、当該乗務員が乗務する予定であった運用計画行路からの変更度合い、当該乗務員の超過勤務時間、該当する乗務員が取得できる休憩時間の有無といった項目を評価基準として評価し、最も評価の良い組合せを採用して当該組合せを構成する乗務案をそれぞれ該当する乗務員の運用変更行路とすることで、乗務員運用変更計画を作成する。
【００９４】
したがって、上記した乗務員運用変更計画の作成に係る第１〜第４の制約を守り、且つ乗務員運用変更計画に対する要望をなるべく反映するような乗務員運用変更計画を自動的に作成することができる。
【００９５】
尚、上記した実施形態では、乗務員運用計画データ８３０、乗務員スケジュールデータ８４０、及び運転整理ダイヤデータ８５０は、記憶媒体８００内に保存されていることとして説明したが、例えば、通信装置５００及び通信回線を介してこれらが格納されるデータベースとデータ通信を行い、該当するデータをダウンロードすることとしても勿論構わない。
【００９６】
最後に付記するが、市販のパソコンを用い、乗務員運用計画データ、及び運転整理ダイヤデータを設定して以上説明した実施形態を適用した実験を行った。具体的には、２４時間分（総列車本数：１１３１本）の計画ダイヤをもとに、例えば午後１０時００分に発生した事故によって列車に約６０分の遅延と運休が生じた場合を想定して運転整理ダイヤデータを作成し、これもとに上記した実施形態を適用した実験を１０回行った。実験の結果、各種制約を満足する乗務員運用変更計画を得ることができた。
【００９７】
図１１は、実験結果を示す図である。図１１において、最終的に得られた最良解の評価値と、変更となった乗務員の運用行路の数を示す変更行路数とを示している。ここで、当該日に列車に乗務する全乗務員の行路数は１９２、このうち変更の候補となった乗務員の行路数は５３であった。また、列車乗務単位の数は１９００、作成された乗務案の総数は約２７０００であった。また、この乗務員運用変更計画を作成するのに要した処理時間は数分であった。
【図面の簡単な説明】
【００９８】
【図１】（ａ）は乗務員運用計画の一例を示す図、（ｂ）は乗務員運用変更計画の一例を示す図。
【図２】乗務員運用変更計画作成装置の機能構成の一例を示すブロック図。
【図３】乗務案作成処理を説明するための図。
【図４】乗務員運用変更計画作成処理を説明するための図。
【図５】乗務員運用計画データのデータ構成例を示す図。
【図６】乗務員スケジュールデータのデータ構成例を示す図。
【図７】運転整理ダイヤデータのデータ構成例を示す図。
【図８】列車乗務単位一覧テーブルのデータ構成例を示す図。
【図９】乗務案データのデータ構成例を示す図。
【図１０】本実施形態におけるＣＰＵの処理の流れの一例を示すフローチャート。
【図１１】本実施形態を適用した実験の実験結果を示す図。
【符号の説明】
【００９９】
１０            乗務員運用変更計画作成装置
１００        ＣＰＵ
１１０      乗務案作成部
１２０      乗務員運用変更計画作成部
２００        ＲＯＭ
３００        入力装置
４００        表示装置
５００        通信装置
６００        ＲＡＭ
６１０      候補解格納領域
６２０      暫定解格納領域
６３０      最良解格納領域
６４０      コスト閾値格納領域
７００        記憶装置
８００        記憶媒体
８１０      乗務案作成プログラム
８２０      乗務員運用変更計画作成プログラム
８３０      乗務員運用計画データ
８４０      乗務員スケジュールデータ
８５０      運転整理ダイヤデータ
８６０      列車乗務単位一覧テーブル
８７０      乗務案データ
８８０      乗務員運用変更計画データ
【図１】
2006056282.tif 000004
【図２】
2006056282.tif 000005
【図３】
2006056282.tif 000006
【図４】
2006056282.tif 000007
【図５】
2006056282.tif 000008
【図６】
2006056282.tif 000009
【図７】
2006056282.tif 000010
【図８】
2006056282.tif 000011
【図９】
2006056282.tif 000012
【図１０】
2006056282.tif 000013
【図１１】
2006056282.tif 000014