(57)【特許請求の範囲】
【請求項１】
列車運行ダイヤの各列車運行区間を乗務員の仕業単位に割り付けて所定期間の乗務員の運用計画を作成する乗務員運用計画作成システムにおいて、
前記列車運行の休止を反映した列車運行データに基づいて乗務員の日毎の行程断片を生成する列車運行置換手段と、
この行程断片をその開始時刻でソートする行程断片ソート手段と、
ソートされた行程断片を時系列的に重複しない行程断片同士で順々に一対一の仮連結する仮連結処理を行う仮連結手段と、
前記仮連結ごとに所定の評価を行ったときの評価値が、所定の評価基準値を超えるか否かを判断し、超えた場合には所定の評価基準値を当該評価値に置き換える連結評価手段と、
前記仮連結処理後に得られる評価基準値の仮連結を本連結して、より長い行程断片又は仕業を生成する本連結手段と、を備えたことを特徴とする乗務員運用計画作成システム。
【請求項２】
前記仮連結手段は、仮連結する対象の日の範囲を維持しつつ一日ずつずらしながら仮連結処理を行い、
前記連結評価手段は、
既行の仮連結処理の評価基準値に基づいて連結打切基準値を算定し、
現行の仮連結処理後の評価基準値が連結打切基準値を上回っているか否かについて判断し、
前記評価値が前記連結打切基準値より上回っている場合に前記本連結させることを特徴とする請求項１に記載の乗務員運用計画作成システム。
【請求項３】
前記仮連結手段は、前記ソートされた行程断片を仮連結する際に、任意に選択した一の行程断片と、この行程断片との開始時刻差が２４時間以下の他の行程断片とを抽出して、仮連結をすること特徴とする請求項１又は２に記載の乗務員運用計画作成システム。
【請求項４】
既出の仮連結の評価値と同じ評価値の仮連結が現れた場合、それ以降の少なくとも一部の仮連結を省略するバイパス手段を備えたことを特徴とする請求項１〜３いずれか１項に記載の乗務員運用計画作成システム。
【請求項５】
毎日運行した場合の列車の運転率を１００％とした場合に各列車運行の運転率を算出する運転率算出手段と、
運転率が基準値以上の列車運行グループと基準値未満の列車グループとに分ける列車グループ化手段とを備え、
運転率が基準値未満の列車グループについて、日別に乗務員運用計画を作成することを特徴とする請求項１〜４いずれか１項に記載の乗務員運用計画作成システム。
【請求項６】
基準乗務時間に対する各乗務員の乗務時間の割合である乗務割合を算出する乗務割合算出手段と、
この乗務割合が基準値以上の乗務員グループと基準値未満の乗務員グループとに分ける乗務員グループ化手段と、
前記基準値以上の乗務割合の乗務員グループを、前記基準値以上の運転率の列車グループに割り付け、
前記基準値未満の乗務割合の乗務員グループを前記基準値未満の運転率の列車グループに割り付けるグループ紐付手段とを備え、前記列車の運転率が基準値以上の列車グループについて交番割を作成することを特徴とする請求項５に記載の乗務員運用計画作成システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、列車の乗務員の運用計画表を作成するに際して、需要の増減等によって既に作成された列車運行ダイヤが変化することに対応して日ごとに乗務員運用計画を作成することができる乗務員運用計画作成システムに関するものである。
【背景技術】
【０００２】
従来、貨物列車や旅客列車等の運転士や車掌といった乗務員の運用計画作成において、乗務員が１回の出勤でこなす勤務内容の単位を仕業とした場合に、例えばこの仕業を３０日分作成して１つの交番表を作成し、複数の乗務員が１つのグループ（交番組）を形成し、ローテーションで各仕業を順にこなしていく交番割による運用が行われている（特許文献１参照）。
【０００３】
特許文献１では、横方向の実線で乗務員の乗務が示され、破線は乗務員の休憩時間を示している。そして、これらを繋ぎ合わせた一本の線が乗務員の１日の勤務内容（仕業）を示し、いくつかの仕業で１つの交番割が作成されている。
【０００４】
特許文献１の発明は、列車運行ダイヤにみだれが発生した場合に、ダイヤみだれに対応した整理ダイヤを作成し、この整理ダイヤに乗務員を再割当するものである。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−７９４４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１に開示された乗務員運用整理案作成装置は、一つの交番組がローテーションで各仕業を順にこなしていく交番割の運用計画を作成するものであり、日々の計画を作る手間や、勤務条件を一人ずつ考える手間が省けるというメリットがあるが、交番組がローテーションで各仕業を順にこなしていくため、１日単位で発生する需要の変動に柔軟に対応することができない。
【０００７】
また、特許文献１のものは、ダイヤみだれが発生したときに、その日に予定されていた仕業を切り出し、これに対して乗務員を再割当しているものであり、日別の需要を反映したものではない。
【０００８】
一般的な旅客列車や貨物列車の運用の場面では、土曜日、休日、祝日の場合には平日とは異なる列車運行ダイヤが用いられる。さらに、例えば冬場には石油列車による需要が日別に変動し、ゴールデンウィーク、お盆等の長期休暇の場合には工場等が閉まって原料製品の需要が低下し、突然の震災等による列車の増発や休止等で、１日単位で需要が変動する。
【０００９】
しかし、このような場合でも、交番割によって運用計画を作成する場合、例えば１年間を通して全ての列車が運行されることを前提に乗務員運用計画を作成して運用に必要な最低限の乗務員を割り付けておく必要がある。しかしながら、前述のように輸送量には波動があり、その運転された列車が運転されなければ、計画上割当があっても実際には勤務が発生しない場合があり、仮に最適化する計画ができたとしても、日々の休止の発生により非効率となることを免れない。
【００１０】
そこで、１日単位で計画を作成することが考えられるが、この場合、例えば連日繰り返される仕業であっても、日ごとに異なる仕業と捉えるため、例えば３０日分（約１ヶ月分）の計画を作成しようとした場合、計画作成対象のデータは約３０倍となり、例えば計算量がデータ量の二乗に比例するような組み合わせ最適化アルゴリズムを使用した場合、約９００倍の時間がかかることになってしまう。このため、運用計画作成の解を得るのに時間がかかったり、解が得られない場合がある。
【００１１】
そこで、本発明は、上記事情に鑑みて、たとえ計画の作成規模が大きくなっても１日単位で乗務員の運用計画を作成することができる乗務員運用計画作成システムの提供をすることを目的としている。
【課題を解決するための手段】
【００１２】
（１）前記目的を達成するために、本発明に係る乗務員運用計画作成システムは、列車運行ダイヤの各列車運行区間を乗務員の仕業単位に割り付けて所定期間の乗務員の運用計画を作成する乗務員運用計画作成システムにおいて、前記列車運行の休止を反映した列車運行データに基づいて乗務員の行程断片を生成する列車運行置換手段と、この行程断片をその開始時刻でソートする行程断片ソート手段と、ソートされた行程断片を時系列的に重複しない行程断片同士で順々に一対一の仮連結する仮連結処理を行う仮連結手段と、前記仮連結ごとに所定の評価を行ったときの評価値が、所定の評価基準値を超えるか否かを判断し、超えた場合には所定の評価基準値を当該評価値に置き換える連結評価手段と、前記仮連結処理後に得られる評価基準値の仮連結を本連結して、より長い行程断片又は仕業を生成する本連結手段と、を備えたことを特徴とする。
【００１３】
（２）また、前記仮連結手段は、仮連結する対象の日の範囲を維持しつつ一日ずつずらしながら仮連結処理を行い、前記連結評価手段は、既行の仮連結処理の評価基準値に基づいて、連結打切基準値を算定し、現行の仮連結処理後の評価基準値が連結打切基準値を上回っているか否かについて判断し、前記評価値が前記連結打切基準値より上回っている場合に前記本連結させることを特徴とすることとしてもよい。
【００１４】
（３）さらに、前記仮連結手段は、前記ソートされた行程断片を仮連結する際に、任意に選択した一の行程断片と、この行程断片との開始時刻差が２４時間以下の他の行程断片とを抽出して、仮連結をしてもよい。
【００１５】
（４）また、既出の仮連結の評価値と同じ評価値の仮連結が現れた場合、それ以降の少なくとも一部の仮連結を省略するバイパス手段を備えていてもよい。
【００１６】
（５）さらに、本発明に係る別の乗務員運用計画作成システムは、上記いずれかの乗務員運用計画作成システムにおいて、毎日運行した場合の列車の運転率を１００％とした場合に各列車運行の運転率を算出する運転率算出手段と、運転率が基準値以上の列車運行グループと基準値未満の列車グループとに分ける列車グループ化手段とを備え、運転率が基準値未満の列車グループについて、日別に乗務員運用計画を作成することを特徴とする。
【００１７】
（６）さらに、このシステムが、基準乗務時間に対する各乗務員の乗務時間の割合（乗務割合）を算出する乗務割合算出手段と、この乗務割合が基準値以上の乗務員グループと基準値未満の乗務員グループとに分ける乗務員グループ化手段と、前記基準値以上の乗務割合の乗務員グループを、前記基準値以上の運転率の列車グループに割り付け、前記基準値未満の乗務割合の乗務員グループを前記基準値未満の運転率の列車グループに割り付けるグループ紐付手段とを備え、前記列車の運転率が基準値以上の列車グループについて交番割を作成することとしてもよい。
【００１８】
なお、本出願において、「行程」とは、例えばA→B→C駅の３駅を停車駅とする一の列車運行がある場合にA駅からC駅までの列車運行をいい、「行程断片」とは、上記の例でA−B駅間やB−C駅間の列車運行を担当する乗務員の乗務単位をいう。さらに、「仕業」とは、複数の「行程」からなる乗務員の約１日の乗務内容をいう。
【００１９】
また、「乗務割合」とは、基準乗務時間に対する各乗務員の乗務時間の割合を意味する。
【発明の効果】
【００２０】
このように構成された本発明の乗務員運用計画作成システムによれば、組み合わせ最適化問題として通常得ることが難しい又は得られない行程断片の連結解をより早く確実に得ることができるようになる。
【００２１】
この結果、解が得られる時間が格段に短くなり、各乗務員の日々の仕業を１日毎の別々の予定として作成することができる。そのため、交番のように決められた仕業を順番にこなしていくだけのシステムでは対応が困難な事象、例えば需要の増加による増発、突然の震災による休止が発生した場合など、需要の変化にも柔軟に対応することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明に係る実施の形態の乗務員運用計画作成システムの構成を説明するブロック図である。
【図２】1日の列車運行ダイヤを示した図である。
【図３】本発明に係る実施の形態の乗務員運用計画作成システムの全体的な処理の流れを説明するフローチャートである。
【図４】図３の行程断片の連結処理の主な流れを説明するフローチャートである。
【図５】図４の行程断片の部分連結処理の主な流れを説明するフローチャートである。
【図６】図５の行程断片の仮連結処理の流れを説明するフローチャートである。
【図７】図３の仕業の改善の処理の主な流れを説明するフローチャートである。
【図８】図７の行程断片の部分交換処理の主な流れを説明するフローチャートである。
【図９】図８の行程断片の仮交換処理の主な流れを説明するフローチャートである。
【図１０】図２の１日の列車運行ダイヤから日々の休止を反映して作成した日別の列車運行ダイヤを示す図である。
【図１１】図１０の日別の列車運行ダイヤに基づいて生成された行程断片のプールを示す図である。
【図１２】図１１の行程断片を時系列的に並べて日別に示した図である。なお、ここでの日付は列車運行数が最少となる時刻（図２，図１０の白抜矢印参照）を日付変更としている。
【図１２Ａ】（ａ）〜（ｃ）は、乗務員運用計画作成システムによる連結処理の具体例を説明する図である。
【図１３】時刻と列車運行数との関係を示す一般例を示し、列車運行数が最少となる時刻を日付変更とする処理を説明するための図である。
【図１４】日別の乗務員運用表を示す図である。
【図１５】本発明に係る実施例の乗務員運用計画作成システムの構成を示すブロック図である。
【図１６】（ａ）各列車の運転率と、運転率により分けた各列車グループを示す。（ｂ）乗務員の乗務割合と、乗務割合により分けた各乗務員グループを示す。
【図１７】実施例の乗務員運用計画作成システムにより乗務員運用表を作成する全体的な処理の流れを説明するフローチャートである。
【図１８】図１７の列車のグループ分け処理の流れを説明するフローチャートである。
【図１９】図１７の乗務員のグループ分け処理の流れを説明するフローチャートである。
【発明を実施するための形態】
【００２３】
以下、本発明の実施の形態について図面を参照して説明する。図１では、本実施の形態の乗務員運用計画作成システム１の構成を説明している。
【００２４】
乗務員運用計画作成システム１は、列車運行データ２ａと乗務員データ２ｂが記憶されたデータベース２と、データベース２に記憶された情報を以下に説明する各手段により処理して乗務員運用計画を作成する処理部３と、作成した乗務員運用計画を出力する出力手段４を有している。
【００２５】
この乗務員運用計画作成システム１は、処理部３の読込手段２１により需要を反映した日別の列車運行ダイヤを読込み、これに基づいて「行程断片」を複数作成し、これらを好適に連結して各乗務員の仕業を日別に作成することにより、日別の乗務員運用計画表を作成するものである。
【００２６】
ここで、上述したように「行程断片」とは、乗務員の乗務単位をいう。例えば、図２に示す列車運行N１からは、A駅からB駅に列車運行N１を行う乗務内容の行程断片n１が生成される。
【００２７】
ここで、図示していないが、仮にA駅からC駅の列車運行であってB駅にて停車する列車運行があるとすると、Ａ駅からＣ駅までの行程にはA−B駅間とB−C駅間との２つの行程断片が含まれることとなる。
【００２８】
図２の列車運行ダイヤは、運行される貨物列車を時刻別（横軸参照）に示し、列車運行ダイヤの縦軸は各駅名及び駅間距離を簡略的に示している。符号Ｍ１，Ｍ２，Ｎ１，Ｎ２，Ｑ１，Ｑ２，Ｘ１，Ｙ１は列車運行を示し、往路と復路で「列車」が異なるため、異なる列車運行「Ｍ１」、「Ｍ２」、・・・となっている。
【００２９】
図２に示す一般的な１日の列車運行ダイヤは、時刻別に運行される全ての列車を示しているが、例えば６月１２日は列車運行Ｑ１，Ｑ２が休止というように当初運行する設定であった列車であっても、需要の減少により列車が運行しない場合がある。
【００３０】
そのため、日別に運用計画を作成する場合には、図１０に示すように、休止情報を反映させた日別の列車運行ダイヤを生成する必要がある。図１０の日別の列車運行ダイヤは、図２に示す１日の列車運行ダイヤを休止情報を反映して日別に横に展開したものである。本システムにおいては、この日別の列車運行ダイヤは、列車運行データ２ａに含まれているものとする。
【００３１】
以下、乗務員運用計画作成システム１の処理部３について説明する。
【００３２】
処理部３は、日別の列車運行ダイヤを読み込むための読込手段２１と、日別の各列車運行を行程断片に置き換える列車運行置換手段２２と、置換した乗務員の行程断片をその開始時刻でソートする行程断片ソート手段２３と、ソートされた行程断片を仮連結する仮連結手段２４と、各仮連結の削減コスト量を評価する連結評価手段２５と、最大の削減コスト量となる最良の仮連結を本連結する本連結手段２６と、仮連結処理において既出の最良の仮連結と同じ評価値の行程断片が出現した場合に、その後の仮連結処理の少なくとも一部をバイパスするバイパス手段２７と、行程断片に必要な便乗を付加して仕業にする仕業作成手段２８と、仕業内の行程断片を交換して仕業を改善する仕業改善手段２９と、行程断片および仕業が労働規定に違反していないかどうかをチェックする労働規定チェック手段３０とを主に備えている。
【００３３】
ここで、「仮連結」とは、行程断片同士を一対一で仮に連結することをいい、実際に行程断片同士を連結した場合に人件費等のコストがどの程度削減されるか評価するために行われるものである。
【００３４】
また「本連結」とは、仮連結を実際に連結して、より長い行程断片を生成することをいう。さらに、「仮連結処理」とは、複数の行程断片同士を総当りで仮連結させる処理をいう。
【００３５】
＜列車運行置換手段＞
列車運行置換手段２２は、日別の列車運行を行程断片に置き換えるものである。この置換により生成される各行程断片は、少なくとも開始時刻の情報を伴った形で生成される（図１１参照）。
【００３６】
＜日付変更時刻＞
貨物列車の運行は深夜に行われることが多いので、日付変更時刻を２４時（午前０時）に合わせた場合、日を跨いだ列車の運行が不自然に分割される場合がある（例えば、Ａ駅を出発してＢ駅に午後１１時に着き、翌日の午前１時にＢ駅から出発してＣ駅に着くような列車があった場合、Ａ−Ｂ駅間の運行と、Ｂ−Ｃ駅間の運行が別々に分割された計画作成対象となってしまう)。
【００３７】
そこで、運行列車数が最少の時間帯を日付変更時刻として設定するのが望ましい。例えば、図１３に示す一般例では設定した時刻（白抜矢印）が日付変更時刻となる。これにより運行列車数が多い時間帯が同一日付として探索範囲になるため、連結対象が見つかるのが早くなる効果がある。該当時刻に列車が運行されている場合もあるが、本システムは連続した日付同士を併せて探索範囲にする仕組みを有し、結局は本連結されるため問題とはならない。
【００３８】
日付変更時刻は、列車運行数が最少の時刻であればよく、夜間に限らず日中に設定することもできる。また、貨物列車に限らず他の乗務員運用計画について本システムにより計画を作成する場合でも同様に日付変更時刻を設定することができる。
【００３９】
＜行程断片ソート手段＞
行程断片ソート手段２３は、生成された各行程断片のプール（図１１参照）につき、各行程断片の開始時刻を指標にして各行程断片を時系列的に並び替えるソートを行うものである。図１２にソートされた日付別の行程断片を示す。なお、図１２の各行程断片は、図１１と同様に、図１０の各列車運行に対応した小文字のアルファベットで示されている。
【００４０】
＜仮連結手段＞
仮連結手段２４は、１回の仮連結処理で対象とする連続日分（例えば連続３日分、図１２の探索範囲参照）の行程断片を、図１２に示すように日別に展開された行程断片の中から抽出し、さらに、そのうちの一の行程断片を基礎断片として選択し、基礎断片と時系列的に重複しない他の行程断片とで仮連結を行うものである。
【００４１】
仮連結手段２４は、基礎断片の開始時刻の前後２４時間以内の時点を開始時刻とする他の行程断片を抽出して仮連結する。これは、開始時刻差が２４時間を越える行程断片との連結が労働規定等により制約されることによる。この例では、１回の仮連結処理の対象を連続３日分としている。これは一日の途中から始まる２４時間の仕業を作成するためには２日間を探索対象にする必要があること、列車運用の周期性を利用するためにはさらにもう一つの仕業が入る範囲を対象とする必要があるためである。
【００４２】
しかし、乗務員が連泊で行う等の仕業を考慮して２４時間を越える行程断片と仮連結するようにしてもよく、この場合、１回の仮連結処理の対象とする連続日分（探索範囲）を連続４日分以上としてもよい。
【００４３】
＜連結評価手段＞
連結評価手段２５は、仮連結手段２４による一対一の仮連結で得られる行程断片についての評価値が所定の評価基準値を超えるか否かを仮連結ごとに判断するものである。例えば、この評価値は仮連結した場合の評価基準値を削減コスト量とすることができる。
【００４４】
この場合、図１２に示す例では、３日目の行程断片ｑ１,ｑ２と１日目の行程断片ｎ１,ｎ２を比較すると行程断片ｑ１,ｑ２の方が行程断片同士の間隔が狭くコスト削減されることから、仮連結時の評価値が高いものとなる。したがって、１〜３日目を仮連結処理する場合、３日目の行程断片ｑ１,ｑ２の仮連結が最良の仮連結ということになる。
【００４５】
また、連結評価手段２５は、一連の仮連結を試行している最中は、仮連結の評価基準値としての、その時点での連結時最良削減コストを常に更新し続ける。そして、一連の仮連結が終了した時点で、連結時最良削減コストの情報、つまり最もコスト削減がされた最良の仮連結と、その評価値の情報を後述の本連結手段２６に渡す。
【００４６】
また、連結評価手段２５は、本連結手段２６に渡した評価値が、既に行なった仮連結処理における最高の評価値から計算された、連結打切基準値としての連結打切用削減コストより上回っているか否かについても判断し、上回っていない場合には後述の本連結をさせないようにする。
【００４７】
これは、最もコスト削減される仮連結であっても、連結打切用削減コストを上回っていなければ、十分なコスト削減が達成されていないものとして、本連結の対象から除くものである。これにより、コスト削減の低い行程断片同士を本連結せず、他の探索範囲内にある行程断片との連結ができるようにする。
【００４８】
＜本連結手段＞
本連結手段２６は、最良の仮連結を本連結して、より長い行程断片又は仕業を作成するものである。本連結された行程断片は、新たな行程断片として再び仮連結処理に供される。
【００４９】
＜バイパス手段＞
バイパス手段２７は、既に本連結された仮連結と同じ条件の仮連結が出現した場合に、それ以降に予定されている仮連結を省略して、その現在試行している１回分の仮連結処理を終了させるものである。
【００５０】
具体的には、一の基礎断片と他の行程断片について一対一の仮連結を行っている最中に、既に本連結された最良の仮連結の削減コスト量と同じ仮連結が現れた場合、既出の仮連結と同じ条件のものと判断して、それ以降の仮連結は行わないようにするものである。
【００５１】
＜仕業作成手段＞
仕業作成手段２８は、上記条件を満たす本連結をそれ以上することができない本連結後の行程断片について解析を行い、仕業が基地駅で開始および終了しているか否かを判断する。仕業が基地駅で開始していない、あるいは、基地駅で終了していない場合には、基地駅から開始して基地駅に戻る仕業となるように本連結後の行程断片に対して旅客便乗を付加したり適切な位置で切断を行ったりする。
【００５２】
仕業の基地駅については、任意の手段で決めることとしてもよいが、どの基地駅に仕業が所属するものであるかは仕業作成時に決定されている必要がある。
【００５３】
基地駅が一つの場合には基地駅は自明であるが、二以上の基地駅がある場合、各仕業について基地駅を決定する必要がある。基地駅を決定する方法としては、例えば業務ルールとして定めたり、行程断片の駅に近い基地駅を選択することができる。
【００５４】
Ａ駅が基地駅である乗務員の場合、同じ基地駅Ａを開始地点と終了地点とする行程断片は、何ら修正をしなくとも、それだけで一つの仕業となる。これに対して、行程断片の開始地点又は終了地点が同じ基地駅Aでない場合は、便乗や行程断片を付加することで基地駅Aに戻る仕業に修正しなければならない。
【００５５】
＜仕業改善手段＞
仕業改善手段２９は、仕業同士で一部行程断片を仮交換して評価値が改善できる場合に、本交換を行うものである。
【００５６】
ここで「仮交換」とは、対象とする複数の仕業にそれぞれ含まれる行程断片同士を異なる仕業間で、一対一で仮に交換することをいい、実際に行程断片同士を交換した場合に人件費等のコストがどの程度削減されるか評価するために行われるものである。
【００５７】
また「本交換」とは、仕業同士間で実際に行程断片を組換える交換をして新たな仕業を再生成することをいう。さらに、「仮交換処理」とは、複数の行程断片同士を総当りで仮交換させる処理をいう。
【００５８】
仕業改善手段２９は、仮交換する前の各仕業の評価値の和と仮交換した後の各仕業の評価値の和を比較し、交換の前後で評価値の合計が改善される場合には本交換を行う。
【００５９】
また、仕業改善手段２９は、仮連結処理と同様、所定の連続日分（例えば連続3日分）を探索範囲として仮交換処理することで、仮交換対象を時系列に限られた範囲に限定することができる。
【００６０】
加えて、一の仮交換処理中に、既出の最良の仮交換時の評価値と同値の評価値が出現した場合には、前記バイパス手段２７によって、それ以降の仮交換を省略させてもよい。
【００６１】
＜労働規定チェック手段＞
労働規定チェック手段３０は、仮連結手段２４で仮連結された行程断片、仕業作成手段２８で作成された仕業、仕業改善手段で行程断片の仮交換が行われた仕業が労働規定を満たしているかをチェックする。
【００６２】
例えば、作成された仕業が長すぎて１回の乗務時間の制限を超えていれば、その仕業は成り立たない。また、継続して乗務することができる距離や時間に制限がある場合は、それを超える乗務を含む仕業は成り立たない。さらに、乗務時間にその他の必要業務時間を加えた労働時間が制限を超えるような仕業も成り立たない。
【００６３】
このような仕業あるいは行程断片は、労働規定チェック手段３０により検出され、コストの削減が不可能と判断されたり、交換の候補から外したりされる。
【００６４】
＜出力手段＞
出力手段４は、乗務員運用計画作成システム１の処理部３によって生成された乗務員運用表を出力する処理を行う。この出力手段４は、記録媒体にデータを書き込む手段、プリンター又はモニタなどのいずれの構成であってもよい。
【００６５】
＜行程断片の連結処理＞
次に、図３〜図６のフローチャートを参照しながら、本実施の形態の乗務員運用計画作成システム１の処理の流れについて説明する。
【００６６】
ステップＳ１−１において、処理部３の読込手段２１により日別の列車運行のデータを有する列車運行データ２ａの読込みを行う。
【００６７】
上述したように、この列車運行データ２ａは、需要の増減等により予定が変わることにより、日々異なったものとなっている。
【００６８】
図２の１日の列車運行ダイヤ中の列車運行Ｍ１，Ｍ２，Ｎ１，Ｎ２，Ｑ１，Ｑ２，X１，Y１の全列車が日々繰り返し運行される予定であった場合に、図１０の日別の列車運行ダイヤに示すように、例えば６月１２日では列車運行Ｎ１，Ｎ２，Ｑ１，Ｑ２，X１，Y１が休止して列車運行Ｎ１，Ｎ２のみが運行するように、日々異なったものとなっている。
【００６９】
ステップＳ１−２では、日別の列車運行ダイヤの列車運行に対応した、日別の行程断片を生成する。具体的には、図１０に示す６月１２日の列車運行Ｎ１に基づいて、６月１２日の行程断片ｎ１（図１１、図１２参照）が生成されるというように、それぞれ行程断片が生成される。
【００７０】
これにより、運用表の作成対象期間の日付分の行程断片によりなる行程断片のプールが作成される（図１１参照）。図１１に示すプールに含まれる各行程断片は、外見上は同じような行程断片があるが、それぞれの行程断片は、少なくとも異なる開始時刻を有しているため、互いに異なる行程断片となる。
【００７１】
図３を参照して、ステップＳ１−３では、行程断片のプールに含まれる行程断片同士を、具体的に後述するサブステップＳ２〜Ｓ４系（図４〜図６参照）により、時系列的に重複しないように好適に連結させて乗務員の仕業を生成する。
【００７２】
ステップＳ１−４では、行程断片から各乗務員の仕業を生成する。上述したように、便乗を付加等して乗務員の発駅と着駅を同じ基地駅とする処理を行う。
【００７３】
ステップS１−５では、生成した乗務員の仕業のそれぞれに含まれる行程断片を相互に交換して仕業の改善を行う。この具体的な処理は、ステップS５〜S７（図７〜図９参照）にて後述するが、仕業に含まれる行程断片を他の仕業の行程断片と仮交換及び本交換することにより、仕業の改善を行うものである。
【００７４】
ステップS１−６では、改善された仕業に各列車運行を割り付けるとともに、さらにステップS１−７にて乗務員を各仕業に割り付ける。
【００７５】
ステップS１−８では、割り付けて生成した乗務員運用表を出力手段４により出力する（図１４参照）。なお、乗務員「高橋」と「中田」の基地駅はA駅であり、乗務員「江藤」と「馬込」の基地駅はB駅である。
【００７６】
＜行程断片の連結処理＞
図４〜図６を参照しながら、行程断片の部分連結処理について以下に説明する。
【００７７】
ステップＳ２−１では、図１１に示す行程断片のプールに含まれる行程断片を、その開始時刻を指標にして日別の各群（日別リスト）に仕分けする。
【００７８】
ステップＳ２−２では、行程断片の部分連結処理を行う。ここで示す例では、図１２に示すように、連続する３つの群（連続３日分の行程断片）を部分連結処理の対象としている（図１２の「探索範囲」参照）。
【００７９】
この部分連結処理は、主として後述の仮連結から本連結までの一連の連結処理を内容とするものである（図５，図６参照）。この部分連結処理により、処理対象の複数群に含まれる行程断片のうち、最も高い削減コスト量であり且つ既出の仮連結の最高の評価値から計算された連結打切用削減コストを上回る仮連結が本連結されることとなる。
【００８０】
続いて、ステップＳ２−３では、ステップＳ２−２の部分連結処理において本連結があったか否かを判断し、本連結があった場合（Yes）はステップＳ２−４に進む。逆に、本連結がなかった場合（No）はステップS２−７に進む。
【００８１】
ステップS２−４では、本連結情報を「有」に設定する。ここで、「本連結情報」とは、例えば３０日分の計画を作成する場合に、当該３０日分の部分連結処理において、少なくとも１回、本連結がなされたか否かの情報を示すものである。
【００８２】
これにより、もし３０日分の部分連結処理が終了した時点で「本連結情報」が「有」であれば、条件を満たす部分連結がさらになされる余地があるということが分かる。一方、「本連結情報」が「無」であれば、それ以上、条件を満たす部分連結がなされる余地がないことが分かる。
【００８３】
ステップＳ２−５では、部分連結前の行程断片を日別リストから削除する。これは、部分連結処理で生成した新たな行程断片と部分連結前の２つの行程断片とが重複することを避けるために行う。
【００８４】
ステップＳ２−６では、部分連結処理で生成した新たな行程断片を日別リストに追加して日別リストを更新する。
【００８５】
ステップＳ２−７では、運用計画を作成する対象の期間（例えば３０日分）について、部分連結に関する一連の処理が完了したか否かを判断し、完了した場合（Yes）はステップS２−１０に進む。
【００８６】
一方、計画対象期間（例えば３０日分）の部分連結処理が完了していない場合（No）は、本連結情報を「無」に設定し（ステップS２−８）、部分連結処理の対象を１日分ずらす探索範囲の変更処理（ステップS２−９）をしてステップＳ２−２に戻る。
【００８７】
ステップS２−１０では、上述した「本連結情報」が「有」であると判断された場合には、さらに条件を満たす部分連結がなされる余地があると判断して、本連結情報を「無」に設定し（ステップS２−８）、部分連結処理の対象を１日分ずらす探索範囲の変更処理（ステップS２−９）をしてステップＳ２−２に戻る。
【００８８】
一方、「本連結情報」が「有」でないと判断された場合（No）は、それ以上、条件を満たす部分連結がなされる余地がないものと判断して、メインルーチンに戻ってステップＳ１−４に進む（図３参照）。
【００８９】
＜部分連結処理＞
図５，６に部分連結処理のフローチャートを示す。
【００９０】
部分連結処理は、仮連結処理と本連結処理とからなり、例えば３０日分の乗務員運用計画を作成する場合、部分的な連続３日分（例えば１〜３日目）の範囲に含まれる行程断片（例えば図１２の行程断片ｎ１，n２，ｎ１，n２，x１，ｑ１，ｑ２）について、仮連結処理を試行する。この仮連結処理では、行程断片同士が連結した場合の評価値（ここでは削減コスト量）を算出するために行程断片同士を仮に連結し、実際の連結（本連結）は行わない。
【００９１】
このうち一の行程断片（例えば１日目の行程断片ｎ１）を固定して、他の行程断片（この例では行程断片n２（１日目），ｎ１，n２，x１（２日目），ｑ１，ｑ２（３日目））と順に一対一の仮連結していく。その後、固定する行程断片を交換して同様に仮連結し、結果として総当りの仮連結を行なう。そして、各仮連結の削減コスト量を算出し、削減コスト量が最も多い最良の仮連結（例えば３日目の行程断片ｑ１とｑ２の仮連結）を返す（ここまでが１回分の仮連結処理となる）。
【００９２】
そして、この最良の仮連結によって既出の仮連結の最高の評価値から計算された連結打切用削減コストを超えるコスト削減が可能であるとき、これを本連結する。その後、本連結により行程断片が１つ減少した状態で、再び仮連結処理からの試行を繰り返す。この一連の処理より、一定の条件を満たしたより長い行程断片が作成される。
【００９３】
前述の削減コスト量は、所定の評価関数に基づいて算出されるものであり、この評価関数を構成する要素としては、例えば、行程断片同士の開始時刻の時間差（時間差が大きいほど削減コスト量小）や、便乗数（便乗を伴うほど削減コスト量小）などのコストに纏わるものである。
【００９４】
以下、図５を参照しながら、３日単位で行う部分連結処理Ｓ３系の各ステップについて説明する。なお、スタートの段階では、後述の削減コスト量および連結時最良削減コストが「−１」の値にリセットされる。
【００９５】
ステップＳ３−１では、行程断片のプールに含まれる各行程断片の開始時刻を指標にして行程断片を開始時刻の順にソートする。
【００９６】
この開始時刻は、行程断片同士を仮連結する際（後述のステップＳ４−３）に用いられ、一の行程断片に対する連結対象を限定するために用いられる。
【００９７】
ステップＳ３−２では、ステップＳ３−１でソートしたもののうち、連続日分（ここでは連続３日分）の行程断片同士の仮連結処理を行う。仮連結処理では、上述したように削減コスト量が最も高い仮連結を最良の仮連結として返すとともにその削減コスト量を返す。
【００９８】
ステップＳ３−３では、この削減コスト量が正の値であるか、つまり、最良の仮連結によりコスト削減されるか否かを判断する。正の値であってコスト削減される場合（Ｙｅｓ）は、ステップＳ３−４へ進む。逆にコスト増で負の値となる場合（Ｎｏ）は、リターンしてステップＳ２−３へ進む。
【００９９】
なお、ステップS３−３で示す「削減コスト」は、図６に示す仮連結処理からリターンした時点の「連結時最良削減コスト」と同じ値である。
【０１００】
この削減コスト量については隣接する行程断片との開始時刻の差が大きくコスト増となって負の値となる場合もある（例えば、図１２の行程断片n２とｑ１参照）。
【０１０１】
ステップＳ３−４では、削減コスト量の連結打切用削減コストが設定されているか否かを判断し、設定されていない場合（Ｎｏ）はステップＳ３−６に進み、設定されている場合（Ｙｅｓ）はステップＳ３−５に進む。
【０１０２】
この連結打切用削減コストは、ステップＳ３−６で算定される基準の値である。最初の段階では、どの程度コスト削減できるか不明であるため、一回目の仮連結処理（図１２では、１〜３日目の行程断片n１，n２（１日目），n１，n２，x１（２日目），ｑ１，ｑ２（３日目）の総当りの仮連結）を行い、そこで得られた最良の仮連結の削減コスト量を用いて連結打切用削減コストを定める。
【０１０３】
ステップＳ３−６では、削減コスト量の連結打切用削減コストの算定を行う。例えば、最良の仮連結の削減コスト量に０．９５を乗じて得た値を連結打切用削減コストとして定める。この連結打切用削減コストの設定を低く設定すると、削減コスト量が少ない行程断片同士が本連結されやすくなるために調節する必要がある。
【０１０４】
一方、ステップＳ３−５では、２回目以降の仮連結処理で得られた最良の仮連結の削減コスト量が、ステップＳ３−６で設定した削減コスト量の連結打切用削減コストより高いか否かを判断する。連結打切用削減コストより高い場合（Ｎｏ）は、隣接する他の探索範囲にある行程断片との接続と比べて十分にコスト削減される最良の仮連結と判断して、ステップS３−７に進む。
【０１０５】
逆に、削減コスト量の連結打切用削減コストより低い場合（Ｙｅｓ）は、十分なコスト削減がなされない最良の仮連結と判断し、リターンしてステップＳ２−３に進む。
【０１０６】
ステップＳ３−７では、各部分連結処理において「初回の」仮連結処理で出現した削減コスト量を後述するステップＳ４−９のバイパス連結用削減コストとして設定する。このバイパス連結用削減コストについては、ステップＳ４−９にて後述する。
【０１０７】
ステップS３−８では、ステップS３−２で返された最良の仮連結となる２つの行程断片を本連結して新たな行程断片を生成する。
【０１０８】
ステップS３−９では、本連結する前の２つの行程断片を削除する。
【０１０９】
ステップS３−１０では、本連結した新たな行程断片を、ステップS３−１で開始時刻順にソートした他の行程断片の時系列的に正しい位置に挿入する。
【０１１０】
以下、図６を参照しながら仮連結処理について具体的に説明する。
【０１１１】
ステップＳ４−１では、ステップＳ３−１でソートされた行程断片の中から基礎断片としての一の行程断片を選択する。この基礎断片の選択は、ステップＳ４−１に来るごとに開始時刻でソートされている行程断片のプールを一つずつ移動する（また、最後に到達した場合は最初に戻る）。これにより時刻順に仮連結処理が行われ、周期性を利用した探索を行うことができる。
【０１１２】
ステップＳ４−２では、行程断片のプールの中から他の一の行程断片を選択する。
【０１１３】
ステップＳ４−３では、ステップＳ４−１で選択した一の行程断片とステップＳ４−２の他の一の行程断片との開始時刻差が２４時間以内か否か判断する。
【０１１４】
２４時間を超えている場合は、他の一の行程断片の選択を打ち切ってよい。これは、行程断片は開始時刻でソートされており、以降の選択では必ず２４時間を超えることが分かるためである。２４時間という値は、労働規定等に基づいて任意に設定することができる。
【０１１５】
ステップＳ４−４では、一の行程断片と他の一の行程断片の仮連結を行い、次いでステップＳ４−５では、この仮連結について、本連結したとしたならば削減される削減コスト量を評価値として所定の評価関数により算出する。
【０１１６】
この削減コスト量については、労働規定チェック手段３０でチェックを行った結果、違反が検出された場合にはコスト増すなわち負の値を用いる。また、用いる評価関数にもよるが、開始時刻が極端に離れているような行程断片同士を仮連結した場合には、コスト増となって負の値となる場合もある。
【０１１７】
ステップＳ４−６では、この削減コスト量が現行の仮連結処理において最も高い削減コスト量（連結時最良削減コスト）を超えるか否かを判断する。超える場合（Ｙｅｓ）はステップＳ４−７に進み、超えない場合（Ｎｏ）はステップＳ４−８に進む。
【０１１８】
ステップＳ４−７では、ステップＳ４−５で算出した削減コスト量を連結時最良削減コストに設定又は更新する。また、同時にそのときの仮連結の情報（行程断片の情報等）を保存する。このようにすることで、より高い削減コスト量の情報とその時の仮連結の情報が更新・保持される。
【０１１９】
ステップＳ４−８では、ステップＳ４−１で選択した一の行程断片に対して、連結対象に含まれる、その他の行程断片との一連の仮連結が完了したか判断する。完了した場合（Ｙｅs）はステップＳ４−９に進み、未完の場合（Ｎｏ）はステップＳ４−２に戻る。
【０１２０】
ステップＳ４−９では、現在の連結時最良削減コストが、ステップＳ３−７で設定したバイパス連結用削減コストと同値か否かを判断する。同値の場合（Ｙｅｓ）は周期性があると判断してＳ４−１〜Ｓ４−９のループを脱してリターンし、ステップＳ３−３に進む。異値の場合（Ｎｏ）はステップＳ４−１０に進む。
【０１２１】
バイパス連結用削減コストは、上述したように連続日分（ここでは連続３日分）の現行回より前に行った本連結時のコスト削減量である。
【０１２２】
例えば、図１２に示すように１〜３日目の行程断片について仮連結処理する場合、１日目の行程断片ｎ１と行程断片ｎ２とが最良の仮連結がなされて、この値がバイパス連結用削減コストに設定されたと仮定した場合、その後に２日目の行程断片ｎ１を基礎断片として固定して他の行程断片と仮連結をしていくとき、２日目の行程断片ｎ２との仮連結の削減コスト量がバイパス連結用削減コストと同値となる。このように、もともと交番で実施されていたような行程断片の周期性を利用して仮連結処理の一部を省略するものである。
【０１２３】
ステップＳ４−１０では、連続日分（ここでは連続３日分）の行程断片それぞれについて仮連結を行ったか否かを判断する。行った場合（Yes）は、最良の仮連結の情報とその削減コスト量をリターンしてステップＳ３−３に進み、行っていない場合（Ｎｏ）は、ステップＳ４−１に戻る。
【０１２４】
以下、ステップS１−５における仕業改善処理（図３参照）について、図７〜図９を参照しながら説明する。
【０１２５】
ここで、「仕業改善処理」とは、既に生成された仕業に含まれる行程断片を他の仕業に含まれる行程断片と交換することにより、より良い条件の（ここでは、よりコスト削減された）仕業を生成する処理をいう。
【０１２６】
まず、ステップS５−１では、ステップS１−４で生成した各仕業を日別に分ける処理をする。
【０１２７】
そして、ステップS５−２では、各仕業に含まれる行程断片について部分交換処理を行う。この部分交換処理は基本的に既に説明した部分連結処理（図５参照）と似た処理の流れとなる（図８参照）。
【０１２８】
ステップS５−３では、ステップS５−２の行程断片の部分交換処理で本交換があったか否かを判断し、本交換があった場合（Yes）はステップS５−４へ進む。逆に本交換がなかった場合（No）は、ステップS５−７へ進む。
【０１２９】
ステップS５−４では、本交換情報を「有」に設定する。この「本交換情報」は、既に説明した「本連結情報」と似た情報であり、計画作成対象期間について部分交換処理を行なった後に、少なくとも１回本交換された場合には「有」に設定される。
【０１３０】
ステップS５−５では、本交換前の行程断片を日別リストから削除し、ステップS５−６にて本交換後の行程断片を日別リストに追加する。
【０１３１】
ステップS５−７では、改善対象の計画期間について処理が完了したか否かを判断する。例えば仕業の改善対象が３０日分であれば、その３０日分について部分交換処理を主とする一連の処理が完了したか否かを判断して、完了した場合（Yes）はステップS５−１０に進む。
【０１３２】
未完の場合（No）はステップS５−８にて、本交換情報を「無」に設定するとともに、ステップS５−９にて部分交換対象を１日分ずらす探索範囲の変更処理を行なってステップS５−２に戻る。
【０１３３】
一方、ステップS５−１０にて本交換情報が「有」と判断された場合（Yes）は、条件を満たす、さらなる仕業の改善の余地があるものと判断して、上記同様にステップS５−８、S５−９を介してステップS５−２に戻る。逆に、本交換情報が「有」でないと判断された場合には、これ以上、条件を満たす仕業の改善の余地がないと判断してリターンし、ステップS１−７に進む（図３参照）。
【０１３４】
以下、ステップS５−２の行程断片の部分交換処理について、図８を参照しながら説明する。
【０１３５】
ステップＳ６−１では、各仕業を開始時刻でソートする。
【０１３６】
ステップＳ６−２では、ソートした各仕業に含まれる行程断片について仮交換処理を行い、最良の行程断片の仮交換についての情報と、その際の削減コスト量の情報を得る。
【０１３７】
ステップＳ６−３では、最良の仮交換の削減コスト量が正の値か判断する。削減コスト量が正の値であってコスト削減される場合（Ｙｅｓ）は、ステップＳ６−４へ進む。逆にコスト増で負の値となる場合（Ｎｏ）は、リターンしてステップＳ５−３へ進む。
【０１３８】
なお、ステップS６−３で示す「削減コスト」は、図９に示す仮交換処理からリターンした時点の「交換時最良削減コスト」と同値である。
【０１３９】
ステップＳ６−４では、削減コスト量の交換打切用削減コストが設定されているか否かを判断し、設定されていない場合（Ｎｏ）はステップＳ６−６に進み、設定されている場合（Ｙｅｓ）はステップＳ６−５に進む。
【０１４０】
なお、この交換打切用削減コストは、ステップＳ６−６で算定される値である。
【０１４１】
最初の段階では、どの程度コスト削減できるか不明であるため、一回目の仮交換処理を行い、そこで得られた最良の仮交換の削減コスト量を用いて交換打切用削減コストを定める。
【０１４２】
ステップＳ６−６では、削減コスト量の交換打切用削減コストの算定を行う。例えば、最良の仮交換の削減コスト量に０．９５を乗じて得た値を交換打切用削減コストとして定める。この交換打切用削減コストの設定を低く設定すると、削減コスト量が少ない行程断片同士が本交換されやすくなるために調節する必要がある。
【０１４３】
一方、ステップＳ６−５では、２回目以降の仮交換処理で得られた最良の仮交換の削減コスト量が、ステップＳ６−６で設定した削減コスト量の交換打切用削減コストより高いか否かを判断する。交換打切用削減コストより高い場合（Ｎｏ）は、隣接する他の探索範囲にある行程断片との交換と比べて十分にコスト削減される最良の仮交換と判断して、ステップS６−７に進む。
【０１４４】
逆に、削減コスト量の交換打切用削減コストより低い場合（Ｙｅｓ）は、十分なコスト削減がなされない最良の仮交換と判断し、リターンしてステップＳ５−３に進む。
【０１４５】
ステップＳ６−７では、初回の仮交換処理で出現した削減コスト量を後述するステップＳ７−９で使用されるバイパス交換用削減コストとして設定する。このバイパス交換用削減コストについては、ステップＳ７−９にて後述する。
【０１４６】
ステップS６−８では、ステップS６−２で返された最良の仮交換となる２つの行程断片を本交換して新たな仕業をそれぞれ生成する。
【０１４７】
以下、ステップS６−２の仮交換処理について図９を参照しながら説明する。
【０１４８】
ステップS７−１では、仕業の一を基礎仕業として選択する。この基礎仕業の選択は、ステップＳ７−１に来るごとにステップS６−１において開始時刻でソートされている仕業のプール（図示省略）を一つずつ移動する（また、最後に到達した場合は最初に戻る）。これにより時刻順に仮交換処理が行われ、周期性を利用した探索を行うことができる。
【０１４９】
ステップＳ７−２では、仕業プールの中から他の一の仕業を選択する。
【０１５０】
ステップＳ７−３では、ステップＳ７−１で選択した一の仕業とステップＳ７−２の他の一の仕業との開始時刻差が２４時間以内か否か判断する。２４時間を超えている場合については、ステップＳ４−３と同様である。
【０１５１】
ステップＳ７−４では、一の仕業と他の一の仕業の交換可能な行程断片の仮交換を行い、次いでステップＳ７−５にて仮交換の削減コスト量を所定の評価関数により算出する。ただし、交換可能かどうかは労働規定チェック手段３０でチェックする。
【０１５２】
ステップＳ７−６では、削減コスト量が現行の仮交換処理において最も高い削減コスト量（交換時最良削減コスト）を超えるか否かを判断する。超える場合（Ｙｅｓ）はステップＳ７−７に進み、超えない場合（Ｎｏ）はステップＳ７−８に進む。
【０１５３】
ステップＳ７−７では、ステップＳ７−５で算出した削減コスト量を交換時最良削減コストに設定又は更新する。また、同時にそのときの仮交換の情報（行程断片の情報等）を保存する。このようにすることで、より高い削減コスト量の情報とその時の仮交換の情報が更新・保持される。
【０１５４】
ステップＳ７−８では、ステップＳ７−１で選択した一の仕業に対して、探索範囲に含まれる、その他の仕業との仮交換が完了したか判断する。完了した場合（Ｙｅs）はステップＳ７−９に進み、未完の場合（Ｎｏ）はステップＳ７−２に戻る。
【０１５５】
ステップＳ７−９では、現在の交換時最良削減コストが、ステップＳ６−７で設定したバイパス交換用削減コストと同値か否かを判断する。同値の場合（Ｙｅｓ）は周期性があると判断してステップＳ７−１〜Ｓ７−９のループを脱してリターンし、ステップＳ６−３に進む。異値の場合（Ｎｏ）はステップＳ７−１０に進む。
【０１５６】
バイパス交換用削減コストは、上述したように連続日分（ここでは連続３日分）の現行回より前に行った本交換時のコスト削減量である。
【０１５７】
ステップＳ７−１０では、連続日分（ここでは連続３日分）の仕業それぞれについて仮交換を行ったか否かを判断する。行った場合（Yes）は、最良の仮交換の情報とその削減コスト量をリターンしてステップＳ６−３に進み、行っていない場合（Ｎｏ）は、ステップＳ７−１に戻る。
【０１５８】
以下、本発明に係る乗務員運用計画作成システムの効果を説明する。
【０１５９】
本発明に係る乗務員運用計画作成システムによれば、組み合わせ最適化問題として通常得ることが難しい又は得られない行程断片の連結解を、少なくとも以下の構成（１）とすることにより得ることができる。このため、日々異なる需要に対応して日ごとに異なる乗務員運用計画を作成することができる（図１４参照）。
【０１６０】
その結果、日々の需要の変動を考慮した日別の乗務員運用計画を作成することができる。また、従来手法の交番割の乗務員運用計画で発生していた計画の見直しにかかる手間が大幅に削減されることで、計画作成業務の効率化も図ることができる。
【０１６１】
（１）最も有利な連結から順に行程断片を連結していくため、連結処理が迅速となる。
行程断片同士を仮連結していき、それぞれの仮連結について有利な連結となるかどうかその都度評価する。そして、それらの仮連結の中で最も削減コスト量が多い有利な仮連結を最良の仮連結として本連結を行う。この本連結した行程断片を含めて同じ処理を繰り返すことにより最も削減コスト量が多いものから順に行程断片の連結が行われ、削減コスト量が低い行程断片同士を手当たり次第に連結するよりも、連結処理が適正且つ迅速となる。
【０１６２】
さらに、以下の構成（２）〜（６）とすることで、上記連結解をさらに早く確実に得ることができるようになる。
【０１６３】
（２）仮連結処理の対象日の範囲を限定（ここでは連続３日分に限定）するので、一の行程断片と連結される可能性が高い、時系列に近接した行程断片との間で仮連結処理がなされ、連結処理が迅速となる。
【０１６４】
さらに、削除コスト量の連結打切用削減コスト（ステップＳ３−６参照）の存在により、対象日範囲内の最良の仮連結であっても連結打切用削減コストを超えなければ本連結されないので、当該最良の仮連結を構成する行程断片と、隣接する対象範囲外の行程断片であって前記連結打切用削減コストを超えるものとの仮連結や本連結の可能性が奪われず、より適正な連結がなされる。
【０１６５】
具体的な例として、図１２A（ａ）の１〜３日目に含まれる各行程断片についての仮連結処理を考える。まず、連結処理がある程度進み、１日目と２日目のｎ１とｎ２がそれぞれ連結された行程断片、３日目のｑ１とｑ２が連結された行程断片となっているとする。また、２日目にｘ１、４日目にｙ１という行程断片があり、それぞれ３日目の行程断片（ｑ１とｑ２が連結されたもの）に連結可能であると仮定する。
【０１６６】
連結打切用削減コストを考慮しない場合、探索範囲１（１〜３日目）では２日目の行程断片ｘ１と３日目の行程断片（ｑ１とｑ２が連結されたもの）は連結可能であり、わずかでもコスト削減が可能であれば連結が行われる（図１２Ａ（ｂ）参照）。
【０１６７】
この後、連結の範囲が探索範囲２に移動しても４日目の行程断片ｙ１は３日目の行程断片（ｘ１、ｑ１、ｑ２が連結されたもの）と連結されることはない。これは行程断片の開始時刻が２４時間以上離れている、あるいは労働規程違反（仕業は２４時間以下の長さでなければならない）という理由による。
【０１６８】
連結打切用削減コストを導入すると、探索範囲１（１〜３日目）では２日目の行程断片ｘ１と３日目の行程断片（ｑ１とｑ２が連結されたもの）は連結可能であるもののコスト削減はわずかである。連結打切用削減コストよりコスト削減が少なければ、この連結は行われずに連結の範囲が探索範囲２に移動する。この結果、よりコスト削減が可能である連結が行われ、３日目のｑ１とｑ２、４日目のｙ１が連結された行程断片を作成することができる（図１２（c）参照）。
【０１６９】
（３）仮連結する際に、一の行程断片と、この行程断片と開始時刻差が２４時間以下の他の行程断片とを抽出して仮連結対象とするため、連結処理が迅速となる。
【０１７０】
もともと労働規定等の制約で開始時刻差が２４時間を越える行程断片同士の連結はできない場合に、あらかじめ条件から外れるものを連結対象からはずすことで処理が迅速となる。
【０１７１】
（４）上記の連結打切用削減コストを超え且つ最良の仮連結時の評価値と同値となる行程断片が再び現れたとき、既に行われた最良の仮連結と同条件の行程断片として捉えて、残りの行程断片との一対一の仮連結をバイパスするため処理が迅速となる。
【０１７２】
具体的な例としては、図１２に示すように１〜３日目の各行程断片について仮連結処理をしていくとき、１日目の行程断片ｎ１，ｎ２同士の仮連結が最もコスト削減されたとした場合、この削減コスト量がステップＳ３−７でバイパス連結用削減コストとして保存される。
【０１７３】
その後の仮連結処理にて、２日目の行程断片ｎ１について仮連結処理をする際に、２日目の行程断片ｎ１，ｎ２の仮連結の削減コスト量がバイパス連結用削減コストと同値となるため、この２日目の行程断片n１，ｎ２が１日目の行程断片n１，ｎ２と同条件の行程断片と判断されて、それ以降の仮連結はスキップされ、連結処理が迅速となる。
【実施例】
【０１７４】
次に、本発明に係る別の乗務員運用計画作成システムについて説明する。
【０１７５】
日々の需要の変化は、全ての列車運行で一律に発生するわけではなく、列車運行ごとに異なる。それらの列車運行に対して、日別に乗務員運用計画を作成することによって、効率よく運転率と乗務割合とを結びづけることが可能となる。
【０１７６】
このようにすることで、交番割で対応可能な乗務員運用計画部分について日別に作成するよりも、より迅速な処理が可能となる。
【０１７７】
図１５に実施例の乗務員運用計画作成システム１０の構成を示し、図１６にグループ分けした結果の表を示す。
【０１７８】
乗務員運用計画作成システム１０は、図１５に示すように、読込手段３Ａを有している。この読込手段３Ａは、既に説明した乗務員運用計画作成システム１の処理部３に加えて、各乗務員の乗務割合を算出する乗務割合算出手段３１と、各列車運行の運転率を算出する運転率算出手段３２と、運転率により列車運行をグループ化する列車グループ化手段３３と、乗務員を前記乗務割合により列車グループと同数のグループに分ける乗務員グループ化手段３４と、列車グループと乗務員グループとを紐付けするグループ紐付手段３５とを有しているものである。
【０１７９】
＜乗務割合算出手段＞
乗務割合算出手段３１は、基準乗務時間に対する各乗務員の乗務時間の割合を算出する手段である。例えば、乗務割合＝各乗務員が１箇月間に乗務する時間／正社員Aの乗務員が１箇月間に乗務する時間×１００（％）とすることができる。
【０１８０】
＜運転率算出手段＞
運転率算出手段３２は、毎日運行する列車の運転率を１００％とした場合の各列車の運転率を計算するものである。
＜列車グループ化手段＞
列車グループ化手段３３は、運転率算出手段３２により算出された各列車の運転率を指標にして、各列車を所定の運転率範囲の列車グループにそれぞれ仕分けする手段である。
【０１８１】
＜乗務員グループ化手段＞
乗務員グループ化手段３４は、乗務割合算出手段３１により算出された各乗務員の乗務割合を指標にして、各乗務員を所定の乗務割合の範囲の乗務員グループにそれぞれ仕分けする手段である。
【０１８２】
＜グループ紐付手段＞
グループ紐付手段３５は、列車の運転率により列車グループを運転率の順にソートするとともに、乗務員の乗務割合により乗務員グループを乗務割合の順にソートして、列車グループと乗務員グループとを当該ソート順で対応するように関連付ける手段である。
【０１８３】
以下、実施例の乗務員運用計画作成システム１０について詳述する。
【０１８４】
まず、運転率算出手段３２により、各列車運行Ｒ１，Ｒ２，Ｕ１，Ｕ２，Ｔ１，Ｔ２に対して、毎日運転された場合を１００％とした場合の各列車運行の運転率を計算する（図１６（ａ）参照）。
【０１８５】
そして、列車グループ化手段３３により、列車運行の運転率に応じて列車をグループ分けする（図１６（ａ）参照）。
【０１８６】
一方、乗務員についても、乗務割合算出手段３１により各乗務員の乗務割合を算出し、乗務員グループ化手段３４により、乗務割合に応じたグループ分けを実施する（図１６（b）のグループＩ〜ＩＩＩ参照）。
【０１８７】
そして、既に実施の形態で説明した各手段によって、運転率が所定未満の列車のグループＢ，Ｃについて、日別の乗務員運用計画を作成し、グループ紐付手段３５により、乗務割合が所定未満の乗務員グループＩＩ，ＩＩＩをそれぞれ同順でグループＢ，Ｃに紐付ける。
【０１８８】
一方、運転率が所定以上の列車のグループＡについては、従来の循環する交番割を適用して部分的な乗務員運用計画を作成し、勤務における乗務の割合が所定以上のグループＩの乗務員をグループＡに紐付ける。
【０１８９】
このようにすることで、需要が変化しやすく交番割では対応不可能な列車についてのみ日別に計画が作成され、人員配置の効率化も図ることができ、計画作成処理もより迅速化する。
【０１９０】
以下、乗務員運用計画作成システム１０の処理の流れについて、図１７〜図１９のフローチャートを参照しながら説明する。
【０１９１】
ステップＳ８−１では、読込手段２１により列車運行データ２ｃと乗務員データ２ｄを読み込む。この列車運行データ２ｃには、運用計画を作成する対象期間の休止情報が反映された日別の列車運行ダイヤが含まれている。また、乗務員データ２ｄには乗務員の氏名や乗務時間等の情報（図１６（ｂ）参照）が含まれている。
【０１９２】
ステップＳ８−２では、当初運行予定の各列車の運転率を計算し、この運転率に基づいて各列車を２以上の列車グループに分ける。運転率の計算とグループ化については、後述のステップＳ９系で説明する。
【０１９３】
ステップＳ８−３では、乗務員データに記録されている乗務員の乗務時間から、各乗務員の乗務割合を計算し、この乗務割合に基づいて列車グループと同数の２以上の乗務員グループに分ける。乗務割合の計算とグループ化については、後述のステップＳ１０系で説明する。
【０１９４】
ステップＳ８−４では、列車グループと乗務員グループとをそれぞれ紐付けする。この紐付けでは、列車グループを運転率で降順にソートするとともに乗務員グループを乗務割合で降順にソートし、降順に対応するように列車グループと乗務員グループが紐付けられる。
【０１９５】
ステップＳ８−５では、運転率が所定未満の列車グループについて、実施の形態で説明したように日別の乗務員運用計画を作成する。
【０１９６】
この例では、運転率が９０％以下の列車グループＢ，Ｃについて日別の乗務員運用計画を作成している（図１６（ａ）参照）。
【０１９７】
ステップＳ８−６では、運転率が所定以上の列車グループについて、列車運行データ２ｃに基づいて、従来の通りに循環する交番割を適用して乗務員運用計画を作成する。基本的には、１日分の列車ダイヤから交番割を作成する（図示省略）。
【０１９８】
ステップＳ８−７では、ステップＳ８−５およびＳ８−６で作成した乗務員運用表を合成出力する（図示省略）。
【０１９９】
以下、図１８を参照して運転率により列車のグループ分けをする処理を説明する。
【０２００】
ステップＳ９−１では、列車運行データ２ｃから列車別に所定期間（ここでは１年間）の運転日数を導出する。
【０２０１】
ステップＳ９−２では、各列車の運転率を算出する。この運転率は、運転日数／３６５（閏年は３６６）×１００（％）により算出する。
【０２０２】
ステップＳ９−３では、各列車をグループに分けるための運転率の閾値を設定する。この閾値は、ユーザにより設定できるようになっている。また、この閾値の設定により、日別に作成される運用計画の対象列車が決まるので、設定により最終的な乗務員の運用コストが変化する。従って、最終的な乗務員の運用コストとの兼ね合いで閾値を決定することが望ましい。
【０２０３】
この例では、
グループＡの運転率（％）＞９０
９０≧グループＢの運転率（％）＞５０
５０≧グループＣの運転率（％）＞  ０
となるように閾値を設定している。
【０２０４】
ステップＳ９−４では、導出した運転率と設定した閾値に基づいて各列車をグループに分ける。その後、リターンしてステップＳ８−３（S１０−１）に進む。
【０２０５】
この例では、図１６（ａ）に示すように、運転率１００％の列車運行Ｒ１，Ｒ２はグループＡに分類され、運転率８５％の列車運行Ｕ１，Ｕ２はグループＢに分類され、運転率４３％の列車運行Ｔ１，Ｔ２はグループＣに分類されている。
【０２０６】
以下、図１９を参照して、乗務割合により乗務員をグループ分けする処理を説明する。
【０２０７】
ステップＳ１０−１では、乗務員データ２ｄから、基準乗務時間として、乗務割合１００％の正社員Ａについて、計画作成対象とする１箇月間の勤務時間を算出するとともに、各乗務員の同勤務時間を算出する。
【０２０８】
ここでの、勤務時間は運転士としての業務を行なっている時間とする。
【０２０９】
ステップＳ１０−２では、各乗務員についてそれぞれ乗務割合を算出する。
【０２１０】
この乗務割合は、各乗務員の１箇月間に乗務する時間／正社員Aの乗務員が１箇月間に乗務する時間×１００（％）により算出する。
【０２１１】
ステップＳ１０−３では、乗務員をグループ分けするための乗務割合の閾値を設定する。この閾値により各乗務員がグループ分けされる。この乗務割合の閾値についても削減コスト量を決定する一要素としてユーザにより設定できるようになっている。
【０２１２】
この例では、
グループＩの乗務割合（％）＞８０、
８０≧グループIIの乗務割合（％）＞４０
４０≧グループIIIの乗務割合（％）＞０
となるように閾値を設定している。
【０２１３】
ステップＳ１０−４では、導出した乗務割合と設定した閾値に基づいて各乗務員を各グループに分ける。その後、リターンしてステップＳ８−４に進む。
【０２１４】
この例では、図１６（ｂ）に示すように、正社員Ａで乗務割合１００％の「狭山」と「鈴木」がグループＩに分類され、正社員Bで乗務割合７１％の「高橋」と「中田」がグループＩＩに分類され、正社員Cで乗務割合２８％の「馬込」と「江藤」がグループIIIに分類される。
【０２１５】
グループIの乗務員である「狭山」又は「鈴木」がグループAの列車運行R1，R2に乗務し、グループIIの乗務員である「高橋」又は「中田」がグループBの列車運行U１，U2に乗務し、グループIIIの乗務員である「馬込」又は「江藤」がグループCの列車運行T1，T2に乗務することとなる。
【０２１６】
以下、本発明に係る実施例の乗務員運用計画作成システム１０の効果を説明する。
【０２１７】
列車の運転率に応じて日別の運用計画を作成する対象の列車を限定するので、作成対象が減少して、計画作成の処理が迅速となる。
【０２１８】
さらに、運転率が低い列車について日別の運用計画を作成することができることから、乗務割合別に乗務員を割り付けることが可能となり、従来の交番割では非常に達成が困難な勤務体系の乗務員が混在した乗務員運用計画を作成することができる。例えば、育児等の短縮勤務への適用も可能である（図１６（b）の正社員B，C参照）。
【０２１９】
以上、本発明に係る乗務員運用計画作成システムについて、実施の形態及び実施例に基づき説明してきたが、具体的な構成については、これらの実施の形態や実施例に限られるものではなく、特許請求の範囲の各請求項に係る発明の要旨を逸脱しない限り、設計の変更や追加等は許容される。
【０２２０】
例えば、日別の列車運行ダイヤは、基本の運行ダイヤに加えて休止情報や臨時列車の情報といった差分の情報を用いて列車運行置換手段２２によって生成されることとしてもよい。
【符号の説明】
【０２２１】
１，１０      乗務員運用計画作成システム
２     データベース
２１   読込手段
２２   列車運行置換手段
２３   行程断片ソート手段
２４   仮連結手段
２５   連結評価手段
２６   本連結手段
２７   バイパス手段
２８   仕業作成手段
２９   仕業改善手段
３０   労働規定チェック手段
３１   運転率算出手段
３２   乗務割合算出手段
３３   列車グループ化手段
３４   乗務員グループ化手段
３５   グループ紐付手段
２ａ，２ｃ    列車運行データ
２ｂ，２ｄ    乗務員データ
３，３Ａ      処理部
４     出力手段
n１，n２，n１，n２，ｑ１，ｑ２            行程断片
Ｎ１，Ｎ２，Ｍ１，Ｍ２，Ｑ１，Ｑ２ 列車運行
Ｒ１，Ｒ２，Ｕ１，Ｕ２，Ｔ１，Ｔ２ 列車運行
【図１】
0005718742.tif 000002
【図２】
0005718742.tif 000003
【図３】
0005718742.tif 000004
【図４】
0005718742.tif 000005
【図５】
0005718742.tif 000006
【図６】
0005718742.tif 000007
【図７】
0005718742.tif 000008
【図８】
0005718742.tif 000009
【図９】
0005718742.tif 000010
【図１０】
0005718742.tif 000011
【図１１】
0005718742.tif 000012
【図１２】
0005718742.tif 000013
【図１２Ａ】
0005718742.tif 000014
【図１３】
0005718742.tif 000015
【図１４】
0005718742.tif 000016
【図１５】
0005718742.tif 000017
【図１６】
0005718742.tif 000018
【図１７】
0005718742.tif 000019
【図１８】
0005718742.tif 000020
【図１９】
0005718742.tif 000021