乗務員運用計画作成システム
【課題】列車の運行に基づいて作成される行程断片を常に基地駅と結び付けて処理していくことで、実態に即した乗務員運用計画を少ない演算負荷で作成することができる乗務員運用計画作成システムを提供する。
【解決手段】列車の運行情報２１ｂ及び基地駅情報２３ａが記憶されたデータベース２からデータを読み込む読込み手段３０と、コストが最小になる基地駅を運行の仮の基地駅に設定する仮基地駅設定手段３１と、仮の基地駅が設定された運行を、仕業を作成するための行程断片に設定する行程断片設定手段３２と、行程断片同士の連結コストを計算する連結コスト算出手段３３と、連結コストが最小となる行程断片同士を連結させて新たな行程断片を作成するとともにその基地駅を設定する行程断片連結手段３４と、行程断片と便乗とによって仕業を作成する仕業作成手段３５とを備えている。
【解決手段】列車の運行情報２１ｂ及び基地駅情報２３ａが記憶されたデータベース２からデータを読み込む読込み手段３０と、コストが最小になる基地駅を運行の仮の基地駅に設定する仮基地駅設定手段３１と、仮の基地駅が設定された運行を、仕業を作成するための行程断片に設定する行程断片設定手段３２と、行程断片同士の連結コストを計算する連結コスト算出手段３３と、連結コストが最小となる行程断片同士を連結させて新たな行程断片を作成するとともにその基地駅を設定する行程断片連結手段３４と、行程断片と便乗とによって仕業を作成する仕業作成手段３５とを備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、列車の運行に対して運転士や車掌などの乗務員を割り当てる乗務員運用計画を作成するための乗務員運用計画作成システムに関するものである。
【背景技術】
【０００２】
例えば１年に一度、列車ダイヤが見直されて改正されると、それに合わせて乗務員の運用計画も作成し直す必要がある。この作業は、従来、長い日数と多大な労力をかけて手作業でおこなわれていた。これに対して、近年、コンピュータを使った乗務員の運用計画を作成する装置が開発されている（特許文献１，２参照）。
【０００３】
ところが、一つの列車ダイヤに対して考えられる乗務員運用計画（解）は無数にあるため、高性能の演算能力を備えたコンピュータが存在する今日においても、総当り的な計算では実用的に解を得ることは難しい。また、その中から最適な解を探索することはさらに困難である。このため、コンピュータ化をおこなうに際しては、様々な工夫がなされている。
【０００４】
特許文献１に開示された乗務行路計画装置は、乗務員の待ち時間の長さを基礎コストとして捉え、基礎コストの総和が小さくなる行路（仕業）が残存していくように演算を進める装置となっている。
【０００５】
また、特許文献２には、操作者がマウスを操作して修正をおこなうことが可能な乗務交番作成装置が開示されている。このような装置であれば、コンピュータで処理させ難い部分を、操作者の判断によって補うことで演算負荷を減らすことができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−１８８２２２号公報
【特許文献２】特許第２５９７０７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
このように従来からコンピュータを使って乗務員運用計画を作成するための処理の工夫がおこなわれているが、最適な処理手法が確立されているとは言い難いのが現状である。
【０００８】
また、乗務員はいずれかの機関区（「基地駅」と表現する場合もある。）に所属することになるが、列車は機関区を跨って運行されており、いずれの機関区に所属する乗務員が乗務してもいいような場合がある。そのような場合に、適切な処理がおこなわれなければ、実態に合わない解が求められたり、問題が大きくなって解けなくなったりするおそれがある。
【０００９】
そこで、本発明は、列車の運行に基づいて作成される行程断片を常に基地駅と結び付けて処理していくことで、実態に即した乗務員運用計画を少ない演算負荷で作成することができる乗務員運用計画作成システムを提供することを目的としている。
【課題を解決するための手段】
【００１０】
前記目的を達成するために、本発明の乗務員運用計画作成システムは、列車の運行に対して乗務員を割り当てる乗務員運用計画作成システムであって、列車の運行に関する運行情報及び乗務員の勤務の開始地点及び終了地点を示す基地駅に関する基地駅情報が記憶されたデータ記憶手段からデータを読み込む読込み手段と、前記読込み手段によって読み込まれた前記運行情報に対して前記基地駅とのコストを計算し、コストが最小になる基地駅を運行の仮の基地駅に設定する仮基地駅設定手段と、仮の基地駅が設定された運行をその基地駅に勤務する前記乗務員の仕業を作成するための行程断片に設定する行程断片設定手段と、所定の条件を満たす前記行程断片同士の連結による連結コストを計算する連結コスト算出手段と、前記連結コストが最小となる行程断片同士を連結させて新たな行程断片を作成するとともにその基地駅を設定する行程断片連結手段と、前記行程断片と必要に応じて付加される便乗とによって仕業を作成する仕業作成手段とを備えたことを特徴とする。
【００１１】
ここで、前記行程断片連結手段において基地駅の設定をおこなうに際して、連結する２つの行程断片の基地駅が同じ場合はその基地駅を連結後の行程断片の基地駅に設定し、連結する２つの行程断片の基地駅が異なる場合は連結後の行程断片の開始地点と終了地点の各基地駅との間のコストを計算し、コストが小さくなる方を新たな基地駅に設定する処理をおこなうことができる。また、連結する２つの行程断片の基地駅が同じ場合であっても、連結後の行程断片の開始地点と終了地点が同じ基地駅になっているときは、その開始地点と終了地点となっている基地駅を連結後の行程断片の基地駅に設定する処理をおこなうこともできる。
【００１２】
さらに、前記データ記憶手段には乗務員の労働規定情報が記憶されており、前記読込み手段によって前記データ記憶手段から読み込まれた前記労働規定情報に対して、前記仕業作成手段で作成された仕業が違反しているか否かをチェックする労働規定チェック手段を備えた構成とすることができる。
【００１３】
また、前記労働規定チェック手段によって違反がないとされた仕業間において、仕業の一部を切断して交換することで解の改善を図る解改善手段を備えた構成とすることができる。
【００１４】
さらに、前記労働規定チェック手段によって違反がないとされた仕業を組み合わせて、各基地駅の乗務員の勤務順を示す交番を作成する交番作成手段を備えた構成とすることもできる。また、前記交番作成手段によって一旦、作成された交番を評価関数によって評価し、作成される交番の評価が高くなるような改善をおこなう解改善手段を備えた構成とすることもできる。
【発明の効果】
【００１５】
このように構成された本発明の乗務員運用計画作成システムは、列車の運行を基地駅に結び付けて行程断片に置き換えていく。さらに、行程断片同士を連結した際にも新たな行程断片に基地駅を設定する。
【００１６】
このように行程断片が常に基地駅と結び付けられることで、複数の機関区で使用される駅を通る列車の乗務員運用計画問題が適切に整理されて振り分けられていく。この結果、計算が発散して解が得られなくなることがなくなり、実態に即した乗務員運用計画が少ない演算負荷で作成できるようになる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施の形態の乗務員運用計画作成システムの構成を説明するブロック図である。
【図２】列車の運行を行程断片に設定するまでの処理の流れを説明するフローチャートである。
【図３】行程断片を連結して交番を作成するまでの全体の処理の流れを説明するフローチャートである。
【図４】行程断片を連結する処理の詳細な流れを説明するフローチャートである。
【図５】仕業を作成する処理の詳細な流れを説明するフローチャートである。
【図６】仕業を改善する処理の詳細な流れを説明するフローチャートである。
【図７】運行情報を説明するための説明図である。
【図８】行程断片を連結して作成される仕業を説明するための説明図である。
【図９】運行の基地駅を設定する処理を説明するための説明図である。
【図１０】行程断片同士を連結した際に基地駅を設定する処理を説明するための説明図である。
【図１１】行程断片同士を連結した際に基地駅を設定する処理を説明するための説明図である。
【図１２】行程断片同士を連結した際に基地駅を設定する処理を説明するための説明図である。
【図１３】交番を作成する処理の詳細な流れを説明するフローチャートである。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について図面を参照して説明する。図１は、本実施の形態の乗務員運用計画作成システムとしての運転士運用計画作成システム１の構成を説明するブロック図である。
【００１９】
本実施の形態の運転士運用計画作成システム１は、データ記憶手段としてのデータベース２と、処理部３と、出力手段４とを主に備えている。ここで説明する運転士運用計画作成システム１の処理部３は、後述する各種手段を実行させるコンピュータプログラムがインストールされたコンピュータによって主に構成される。
【００２０】
そして、本実施の形態の運転士運用計画作成システム１は、列車の運行に対して乗務員としての運転士を割り当てる運転士運用計画を作成するためのシステムである。
【００２１】
この運転士運用計画作成システム１を作動させる前提として、まず、列車ダイヤ（又は列車運行計画）が作成されていることが条件となる。列車ダイヤには、走行する列車の情報が１日分となって記憶されている。
【００２２】
そして、列車番号で特定される１本の列車の情報は、停車駅間の運行情報に分割することができる。図７に示した運行ａは、ある列車の停車駅となるＡ駅とＢ駅との間の運行情報を表している。運行ａは、Ａ駅をh1:m1:s1に出発して、Ｂ駅にh2:m2:s2に到着するという情報である。
【００２３】
一方、運転士や車掌などの乗務員の情報としては、乗務員が所属する機関区の情報がある。この機関区には、勤務の開始駅（開始地点）及び終了駅（終了地点）となる基地駅がある。乗務員の勤務は、勤務の開始駅と勤務の終了駅とが同じ駅、すなわち同じ基地駅にする必要がある。このように乗務員の勤務は、基地駅による制約が強い性質を有している。
【００２４】
以上に述べた情報は、図１に示すようにデータ記憶手段としてのデータベース２に記憶される。データベース２には、ハードディスク、ＲＯＭ(Read Only Memory)などの各種記憶媒体が使用できる。
【００２５】
そして、データベース２には、列車運行データ２１、運転士データ２３、評価データ２４などが記憶される。また、列車運行データ２１には、列車番号に関する列車番号情報２１ａと運行情報２１ｂとが含まれる。
【００２６】
また、運転士データ２３には、運転士が所属する基地駅を示す基地駅情報２３ａ、労働規定情報２２などが含まれる。労働規定情報２２は、乗務員の勤務に対して定められている労働法規、就業規則、労使間で取り決められた規定や協定などの情報である。
【００２７】
この労働規定情報２２による制約は、乗務員運用計画を作成するに際して必ず守らなければならない（違反してはいけない）強い制約と、遵守すべきであるが一部であれば守られなくても計画が作成できる弱い制約とがある。
【００２８】
さらに、評価データ２４には、コスト情報２４ａ、評価関数情報２４ｂなどが含まれる。コスト情報２４ａは、後述する各種手段において処理をおこなう際の判断基準とするためのコストの情報である。何をコストとするかは処理の段階によって異なるが、基地駅までの移動時間や距離、次の乗務までの待ち時間、便乗（移動のための勤務を伴わない乗務）などがコストとなり得る。また、労働規定との関連でもコストとなり得る情報がある。例えば、深夜乗務は２時間を超えると休憩が必要なため、２時間を超えない乗務にした方がコストは安くなる。また、在宅休養時間に関する配慮から休日の前の退勤時刻や休日の後の出勤時刻には制限があり、制限が守れない場合には運転士を増やす必要があるため、早朝出勤又は深夜到着は高コストと考えられる。さらに、１回の仕業の後にその仕業と同じ時間以上の休憩が必要になるため、長すぎる仕業は高コストと考えられる。
【００２９】
一方、評価関数情報２４ｂは、コスト情報２４ａと同様に後述する各種手段において処理をおこなう際の判断基準とするための情報である。例えば、同一列車に連続して乗務させるのが好ましい、３連休は作らないようにするのが好ましい、５日勤務した後は休日を与えるなど、好ましい仕業又は交番が作成されるようにするために、好ましくない計画にペナルティが与えられるような評価関数を導入することができる。
【００３０】
処理部３は、データベース２に記憶された各種データを読み込む読込み手段３０と、各種処理手段３００と、各種処理手段３００において作成された解の改善をおこなう解改善手段３８とを主に備えている。
【００３１】
この処理部３は、上記した各種手段の演算をおこなうためのＣＰＵ(Central Processing Unit)、一時記憶領域としてのＲＡＭ(Random Access Memory)などのハード部と、各種手段を実行させるためにインストールされたコンピュータプログラム（ソフト部）とによって主に構成される。
【００３２】
各種処理手段３００は、仮基地駅設定手段３１と、行程断片設定手段３２と、連結コスト算出手段３３と、行程断片連結手段３４と、仕業作成手段３５と、労働規定チェック手段３６と、交番作成手段３７とを主に備えている。
【００３３】
仮基地駅設定手段３１では、読込み手段３０によってデータベース２から読み込まれた列車運行データ２１の運行情報２１ｂを、同じく読込み手段３０によってデータベース２から読み込まれた基地駅情報２３ａの基地駅に結び付ける処理をおこなう。
【００３４】
この基地駅に運行を結び付けるにあたっては、コストが基準になる。図７を使って説明すると、運行ａはＡ駅を出てＢ駅に到着する運行情報である。ここで、Ａ駅は基地駅でありＢ駅は基地駅ではない。このように運行の開始地点又は終了地点のいずれかが基地駅である場合は、基地駅であるＡ駅を運行ａの基地駅に設定する。
【００３５】
また、運行の開始地点と終了地点の両方が基地駅である場合は、開始時刻と終了時刻のうち望ましい方、すなわちコストが小さい方の基地駅に設定される。例えば開始時刻が早朝となる場合は出勤のためのコストが高くなる場合があるため、高いコストに設定される。一方、終了時刻が深夜となる場合は、深夜到着となってコストが高くなる場合があるため高いコストに設定される。よって、開始時刻が早朝で終了時刻が昼間の場合は、運行の基地駅は終了地点となる駅に設定される。
【００３６】
さらに、図９を使って説明すると、運行ｂはＢ駅を出てＣ駅に到着する運行情報である。ここで、Ｂ駅とＣ駅は基地駅ではない。そこで、Ｂ駅の最寄りの基地駅がＡ駅である場合に、まず、Ａ駅とＢ駅との間の列車に乗ったときの移動時間をコストＣ1として計算する。この移動時間に関する情報はデータベース２のコスト情報２４ａから読み込まれる。一方、Ｃ駅の最寄りの基地駅がＤ駅であれば、Ｃ駅とＤ駅との間の列車に乗ったときの移動時間をコストＣ2として計算する。そして、コストＣ1とコストＣ2とを比較してコストが小さくなる方の基地駅を運行ｂの基地駅に設定する。
【００３７】
なお、Ｂ駅とＣ駅の最寄りの基地駅を決める際もコストの比較をおこなえば良い。また、公知のワーシャル・フロイド法などのアルゴリズムを使って予め各駅の最寄りの基地駅を求めておき、基地駅情報２３ａとして記憶させておくこともできる。
【００３８】
また、行程断片設定手段３２では、仮基地駅設定手段３１によって仮の基地駅が設定された運行を運転士の行程断片に設定する。ここで、「行程断片」とは、運転士の仕業（１回の勤務、「行路」と呼ぶ場合もある。）を構成する単位である。一つの仕業に含まれる同一列車の連続を行程といい、行程は運転士の乗り換えが可能な駅で分割でき、その分割された行程を行程断片と呼ぶ。このため、複数の行程断片を連結していくことで一つの仕業を作成することができる。そして、列車の運行情報２１ｂは、行程断片として使用可能な単位でデータベース２に記憶されている。
【００３９】
図７，８を参照しながらさらに説明すると、仮の基地駅がＡ駅に設定された駅ＡＢ間の運行ａは、行程断片iに設定される。同様に駅ＢＣ間の運行は行程断片iiに設定され、駅ＣＡ間の運行は行程断片iiiに設定される。
【００４０】
そして、行程断片iと行程断片iiと行程断片iiiとを連結すると、基地駅Ａを開始地点として出発し、最終的に到着する基地駅Ａが終了地点となる一つの仕業が作成できる。すなわち行程断片設定手段３２では、このような仕業の構成要素となる行程断片を設定する。
【００４１】
さらに、連結コスト算出手段３３では、行程断片同士を連結した際の連結コストを計算する。まず、行程断片同士を連結する前提条件として、前にくる行程断片の到着駅と後にくる行程断片の出発駅とが同じでなければならない。また、当然の前提として、前にくる行程断片の列車が到着する時刻よりも、後にくる行程断片の列車が出発する時刻の方が、乗換え時間も考慮したうえでの後の時刻でなければならない。
【００４２】
例えば図８を使って説明すると、行程断片iの到着駅はＢ駅であるため、出発駅がＢ駅である行程断片iiとは連結することができるが、出発駅がＣ駅である行程断片iiiとは連結することができない。
【００４３】
一方、出発駅がＢ駅となる行程断片は行程断片iiの他にもある可能性があり、行程断片iに連結させる行程断片の候補が複数ある場合に、いずれを連結させるかを決めなければならない。その選択基準として、連結コスト算出手段３３によって算出された連結コストが使用される。
【００４４】
この連結コストになり得るものとしては、待ち時間の長さが挙げられる。例えば行程断片iに設定された運行ａのＢ駅に到着する時刻と、行程断片iiに設定された運行のＢ駅を出発する時刻との間に長い待ち時間があれば、その間は勤務中でありながら業務をおこなっていない時間となるためコストと考えられる。このため、待ち時間の長さを連結コストにすることで、待ち時間が短くなるような行程断片同士の連結をおこなわせることができる。
【００４５】
また、連結される行程断片が同じ列車の乗務であるか否かも連結コストとすることができる。すなわち、同一の列車に乗り続ける乗務の方が望ましいため、連結させる行程断片の列車が同一の場合は連結コストを小さくし、列車の乗換えが必要な場合は連結コストを大きくする。
【００４６】
さらに、労働規定などにも上述したように、深夜乗務、早朝出勤又は深夜到着、連結後の仕業の長さなど、連結コストとして計算可能な項目があるため、必要に応じて計算をおこなう。このように複数の種類の基準をコストとして同時に使用する場合は、コスト情報２４ａに同一基準に換算するための係数などを記憶させておき、必要に応じて読み込ませればよい。
【００４７】
そして、行程断片連結手段３４では、候補に挙がっている行程断片の中から連結コストが最小となる行程断片同士を連結させる。この行程断片連結手段３４で行程断片同士を連結させると、連結後の行程断片が新たな行程断片となり、連結前の行程断片は削除されることになる。
【００４８】
例えば図１０を参照しながら説明すると、Ａ駅を出発してＢ駅に到着する行程断片iと、Ｂ駅を出発してＣ駅に到着する行程断片iiとを連結すると、Ａ駅を出発してＣ駅に到着する行程断片が新たな行程断片iとなる。そして、連結前の行程断片iiは削除される。
【００４９】
また、行程断片連結手段３４では、連結後の基地駅の設定をおこなう。図１０に示すように連結する２つの行程断片i,iiの基地駅がいずれもＡ駅で同じとなる場合は、そのままＡ駅が新たな行程断片iの基地駅に設定される。
【００５０】
これに対して図１１に示すように、連結する２つの行程断片i,ivの基地駅が異なる場合がある。すなわち、行程断片iの基地駅はＡ駅であるが、行程断片ivの基地駅はＥ駅と異なっており、行程断片iと行程断片ivとを連結した新たな行程断片iの基地駅をいずれの駅にするかが問題となる。
【００５１】
そこで、連結後の行程断片iに対して、Ａ駅から開始するコストＣ3とＥ駅で終了するコストＣ4を計算しコストが小さい方を基地駅に設定する。ここで、コストを各基地駅（Ａ駅、Ｅ駅）から行程断片iの出発駅（Ａ駅）と到着駅（Ｄ駅）までの移動時間とすると、基地駅となるＡ駅と出発駅となるＡ駅は同じ駅であり移動時間が不要のため、新たな行程断片iの基地駅はＡ駅となる。
【００５２】
また、図１２に示すように、連結する２つの行程断片v,viの基地駅がいずれもＥ駅で同じとなる場合であっても、連結後の新たな行程断片vの開始地点と終了地点が同じ駅であり、かつその駅が基地駅のときは、上述した処理とは異なる処理をおこなう。すなわち、連結後の行程断片vは、基地駅であるＡ駅を開始地点とし、基地駅であるＡ駅を終了地点とする行程断片であるため、Ｅ駅ではなくＡ駅を基地駅に設定する。なお、この場合は、行程断片vがそのまま一つの仕業となる。
【００５３】
そして、仕業作成手段３５では、行程断片から仕業を作成する。行程断片連結手段３４により連結を繰り返した行程断片は、仕業として充分な長さになっている。
【００５４】
図１２で説明したような同じ基地駅Ａが開始地点と終了地点となる行程断片vは、それだけで一つの仕業となる。これに対して、行程断片の開始地点又は終了地点が基地駅でない場合は、便乗を付加することで仕業を完成させなければならない。
【００５５】
例えば、図１１に示した連結後の行程断片iは、開始地点は基地駅Ａであるが終了地点はＤ駅と基地駅Ａとは異なる駅であるため、Ｄ駅からＡ駅に移動する便乗を行程断片iの後に付加しなければならない。同様に、行程断片の開始地点が基地駅でない場合も、基地駅から行程断片の開始地点に移動する便乗を行程断片の前に付加する。
【００５６】
労働規定チェック手段３６は、仕業作成手段３５で作成された仕業が労働規定を満たしているかをチェックする。例えば、作成された仕業が長すぎて１日の乗務時間の制限を超えていれば、その仕業は成り立たない。また、継続して乗務することができる距離や時間に制限がある場合は、それを超える乗務を含む仕業は成り立たない。さらに、乗務時間以外の必要業務時間を加えた総労働時間が労働規定の制限を超えるような仕業も成り立たない。
【００５７】
便乗を付加した場合に仕業として成り立たない場合は、行程断片を切断して短くし、それに対して便乗を付加することによって仕業として成り立つようにする。例えば、行程断片が基地駅で開始していない場合は、切断によるコストの増加が最も少なくなるように行程断片を切断し、切断された前半部分に対して基地駅からの便乗と基地駅への便乗を付加して仕業とする。この仕業がまだ仕業として成り立たない場合は、さらに行程断片を切断して同様に処理する。一方、切断された後半部分については、他の行程断片に対する処理がすべて終わった後に、再び行程断片連結手段３４による連結の対象にする。
【００５８】
同様に、行程断片が基地駅で終了していない場合は、切断によるコストの増加が最も少なくなるように行程断片を切断し、切断された後半部分に対して基地駅からの便乗と基地駅への便乗を付加して仕業とする。この仕業がまだ仕業として成り立たない場合は、さらに行程断片を切断して同様に処理する。一方、切断された前半部分については、他の行程断片に対する処理がすべて終わった後に、再び行程断片連結手段３４による連結の対象にする。このようにして労働規定チェック手段３６では、すべての仕業が労働規定を満たして成り立つようになるまで処理を繰り返す。
【００５９】
上述したようにして仕業作成手段３５及び労働規定チェック手段３６によって作成された仕業は、解改善手段３８によって改善することができる。すなわち、作成された仕業に含まれる複数の行程断片を総合的に検討すると、コスト削減の可能性がある場合がある。例えば、行程断片vii,viii,ix,xが存在し、行程断片viiは、行程断片viii又は行程断片xとの連結が可能であるとする。また、行程断片ixは、行程断片viii又は行程断片xとの連結が可能であるとする。
【００６０】
そして、行程断片viiと行程断片viiiとを連結することによるコスト削減量が8、行程断片viiと行程断片xとを連結することによるコスト削減量が5であるとする。また、行程断片ixと行程断片viiiとを連結することによるコスト削減量が7、行程断片ixと行程断片xとを連結することによるコスト削減量が1であるとする。
【００６１】
このような条件下で最もコスト削減量が大きい行程断片同士の連結を最初にするとすれば、行程断片viiと行程断片viiiとが最初に連結されてコスト削減量が8になる。そして、行程断片viiiが連結に使用された後に残るのは行程断片xなので、行程断片ixと行程断片xとが連結されてコスト削減量の1が加算され、合計のコスト削減量は9となる。
【００６２】
これに対して行程断片viiと行程断片xとを最初に連結するとコスト削減量が5、残った行程断片viiiと行程断片ixとを連結するとコスト削減量が7となり、合計のコスト削減量は12となる。すなわち、合計のコスト削減量は、行程断片viiと行程断片xとを連結し、行程断片ixと行程断片viiiとを連結した場合の方が大きくなる。このように合計のコスト削減量が最も大きくなるように行程断片同士を連結させることで、仕業を改善する。
【００６３】
さらに仕業の改善の方法についての詳細を説明すると、例えば、仕業の一部（最小行程断片の長さ以上の部分）を切断し、他の行程断片又は他の行程断片の一部との交換をおこなう。交換後の仕業のコストが、交換前の仕業のコストよりも小さくなっていれば、解が改善されたことになる。この解改善手段３８による改善は、コストが削減されなくなるまでおこなう。
【００６４】
この行程断片（又は一部）の交換は、仕業の開始部分又は終了部分では同じ基地駅の仕業同士でおこなわなければならないが、それ以外の部分の交換は基地駅が異なる仕業間でおこなってもよい。解改善手段３８によって改善された仕業は、労働規定チェック手段３６によってチェックされ、労働規定を満たす仕業のみが改善結果として生成される。
【００６５】
また、コスト削減が可能か否かの判断は、例えば前回の交換によって算出されたコストと今回の交換によって算出されたコストとを比較して、同じ又は今回のコストが高くなったときには、これ以上のコスト削減は不可能と判断させることでおこなえる。
【００６６】
交番作成手段３７では、仕業作成手段３５により作成され又は解改善手段３８により改善され、労働規定チェック手段３６によって労働規定を満たすことが確認された仕業に基づいて交番を作成する。「交番」とは、基地駅に勤務する運転士の勤務順を示す。例えば、基地駅Ａで仕業が２０個作成されると、２０個の仕業を縦に並べた交番が作成され、２０日間単位の乗務の予定となる。
【００６７】
交番作成手段３７では、交番を実行する人数を最低必要人数から一人ずつ増やしていき、労働規定に違反しない交番が作成されるまで人数の増加を繰り返す。
【００６８】
一方、交番にも、運転士の数、仕業の並べ方の組み合わせ数などによって幾通りもの解があり、解改善手段３８による改善の余地がある。交番作成手段３７に対する解改善手段３８の処理は、評価関数を使っておこなう。
【００６９】
すなわち、作成された交番の評価を、データベース２の評価関数情報２４ｂから読み込まれたデータによっておこない、評価が高くなる（ペナルティが小さくなる）ように仕業の順番を入れ替える。この解改善手段３８による解の改善は、評価が変わらなくなるまでおこなう。
【００７０】
そして、出力手段４は、交番作成手段３７で作成された交番、又は労働規定チェック手段３６でチェックを受けた仕業などを出力させる手段であって、演算結果をデータとして記憶させる記憶媒体、紙に印刷させるプリンタ、画面に表示させるモニタのいずれの形態であってもよい。
【００７１】
次に、本実施の形態の運転士運用計画作成システム１の処理の流れについて、図２−６，１３のフローチャートを主に参照しながら説明する。
【００７２】
まず、ステップＳ１において、読込み手段３０によって列車運行データ２１に含まれる運行情報２１ｂを読み込ませる。また、ステップＳ２において、読込み手段３０によって運転士データ２３に含まれる基地駅情報２３ａを読み込ませる。
【００７３】
そして、読み込まれた運行情報２１ｂと基地駅情報２３ａとに基づいて、仮基地駅設定手段３１によって運行情報２１ｂの中の運行の各基地駅に対するコストを計算する（ステップＳ３）。
【００７４】
図９に示した図で説明すると、運行情報２１ｂの中の例えば運行ｂの基地駅として、Ａ駅とＤ駅とが候補に割り当てられていたとする。これに対して仮基地駅設定手段３１では、運行ｂの開始地点となるＢ駅と基地駅ＡとのコストＣ1を計算するとともに、運行ｂの終了地点となるＣ駅と基地駅ＤとのコストＣ2を計算する。そして、コストＣ1とコストＣ2とを比較して、小さい方に結び付けられた基地駅を運行ｂの基地駅として設定する（ステップＳ４）。
【００７５】
このように基地駅を設定していく理由としては、運転士の運用計画は基地駅ごとに作成されるため、運行を基地駅に結び付けて処理を進めていくことで、組み合わせの数を適切に削減していくことができるからである。
【００７６】
そして、ステップＳ５では、基地駅に結び付けられた運行を、行程断片設定手段３２によって運転士の行程断片に設定する。ここまでの処理で、運行情報２１ｂに含まれる運行の全てが行程断片に設定される。
【００７７】
続いて、図３−６を参照しながら、行程断片を連結して交番を作成するまでの処理について説明する。まず、全体の流れを説明すると、図３に示すように、基地駅に結び付けられた全ての行程断片を対象にして連結処理をおこなう（ステップＳ６）。続いて、ステップＳ７では連結後の行程断片から仕業を作成し、改善可能な仕業はステップＳ８で改善する。そして、各基地駅に与えられた仕業を組み合わせて交番を作成する（ステップＳ９）。
【００７８】
図４は、行程断片の連結をおこなうステップＳ６の詳細な処理の流れを説明するフローチャートである。行程断片の連結処理が開始されると（ステップＳ６１）、連結コスト算出手段３３によって行程断片同士を連結した際の連結コストを計算する。すなわち、ある行程断片に対して連結可能な行程断片は、この段階では複数、存在するため、それらの連結候補となる行程断片と連結したときの連結コストをそれぞれ計算しておく。この連結コストの算出により、連結によってコスト削減が可能となる行程断片が全て探し出される（ステップＳ６２）。
【００７９】
このステップで計算される連結コストとして、例えば待ち時間の長さを挙げることができる。例えば、行程断片iのＢ駅に到着する時刻と行程断片iiのＢ駅を出発する時刻との差が10分であれば、待ち時間10分に基づいたコストＣ(i,ii)が算出される。一方、行程断片iのＢ駅に到着する時刻と行程断片xのＢ駅を出発する時刻との差が30分であれば、待ち時間30分に基づいたコストＣ(i,x)が算出される。
【００８０】
また、同一の列車に乗務する行程断片同士の連結に対しては、予め設定されてコスト情報２４ａに記憶されている小さいコストを与え、列車の乗換えが必要となる行程断片同士の連結に対してはコスト情報２４ａに基づいて大きなコストを与える。
【００８１】
さらに、直接連結できない行程断片同士であっても、便乗を介在させることで連結できる場合がある。便乗には、前の行程断片の到着駅から後の行程断片の出発駅までを最短で結ぶ経路を選べばよい。この最短経路は、公知のダイクストラ法などのアルゴリズムを使って求めることができる。しかしながら便乗は業務をしていない時間であるため、連結コストとしてこのステップで計算する。
【００８２】
そして、コスト削減が可能な連結が存在する場合には（ステップＳ６３）、コスト削減が最大になる（連結コストが最小になる）行程断片同士を、行程断片連結手段３４によって連結させる（ステップＳ６４）。例えば、上述したコストＣ(i,ii)はコスト(i,x)よりも小さい値になるので、行程断片iは行程断片iiと連結させる。この連結によって生成された行程断片は、新たな行程断片iとなり、新たな行程断片iに含まれることになるので連結前の行程断片iiは消滅する。
【００８３】
続いて、行程断片連結手段３４では、連結によって新たに生成された行程断片iの基地駅を設定する。例えば、図１０に示すように、連結前のそれぞれの行程断片i,iiの基地駅がＡ駅で同じであれば、そのＡ駅を連結後の行程断片iの基地駅に設定する。
【００８４】
但し、図１２に示すように、連結前のそれぞれの行程断片v,viの基地駅が同じであっても、その駅を基地駅にしない場合がある。それは、連結後の行程断片vの開始地点と終了地点が同じ駅であって、その駅が基地駅である場合である。この例では、行程断片vの開始地点と終了地点とが同じＡ駅であり、Ａ駅は基地駅であるため、行程断片vの基地駅はＡ駅に設定される。
【００８５】
これに対して、図１１に示すように、連結前のそれぞれの行程断片i,ivの基地駅がＡ駅とＥ駅とで異なっている場合は、コストを比較することによって基地駅を決める。この基地駅を設定するためのコストは行程断片連結手段３４において計算される。例えば、図１１に示した連結後の行程断片iについては、開始地点であるＡ駅は基地駅であるため、移動時間に基づいたコストＣ3は０である。これに対して終了地点であるＤ駅は基地駅ではなく、Ｅ駅が最寄りの基地駅であるため、コストＣ4＞0である。このため、連結後の行程断片iには、小さい方のコストＣ3に関連付けられたＡ駅が基地駅として設定される。
【００８６】
この行程断片を連結させる処理は、コスト削減が可能な連結が存在しなくなるまで繰り返し、存在しなくなった場合はリターン（ステップＳ６５）させて、仕業を作成するステップＳ７に移行する。
【００８７】
図５は、仕業の作成をおこなうステップＳ７の詳細な処理の流れを説明するフローチャートである。仕業作成手段３５によって仕業の作成処理が開始されると（ステップＳ７０１）、まず、ステップＳ７０２において全ての行程断片ｓが集合Ｘの要素に設定される。また、空集合として集合Ｙと集合Ｚが作成される。
【００８８】
そして、Ｘループに移行する（ステップＳ７０３）。Ｘループでは、集合Ｘの要素であるすべての行程断片ｓに対して演算がおこなわれる。ステップＳ７０４では、演算対象となっている行程断片ｓについて、基地駅で開始されて基地駅で終了しているか否かの判定がおこなわれる。例えば図８に示すような行程断片i,ii,iiiを連結させて生成された行程断片ｓは、基地駅であるＡ駅から開始されてＡ駅で終了するため、そのまま仕業として成立する。このように基地駅で開始されて基地駅で終了している行程断片ｓは、集合Ｚに移されて（ステップＳ７０５）、次のＸループの処理に移行される（ステップＳ７１６）。
【００８９】
これに対して、開始又は終了の少なくとも一方が基地駅となっていない行程断片ｓに便乗を付加することによって、基地駅で開始して基地駅で終了する行程断片ｔを生成する（ステップＳ７０６）。すなわち、行程断片ｓの開始地点又は終了地点が基地駅でない場合は、基地駅から行程断片ｓの開始地点までの便乗又は行程断片ｓの終了地点から基地駅までの便乗を行程断片に付加することで仕業とすることができる。
【００９０】
そして、便乗が付加された行程断片ｔは、労働規定チェック手段３６によって労働規定に違反していないかがチェックされ（ステップＳ７０７）、労働規定を満たしていれば集合Ｚに移されて（ステップＳ７０８）、次のＸループの処理に移る。
【００９１】
これに対して行程断片ｔが労働規定を満たしていない場合は、再び行程断片ｓに戻ってステップＳ７０９以降で仕業として成り立たせるための処理をおこなう。すなわち、仕業としては完結していても労働規定に違反する仕業を運転士に割り当てることはできないので、労働規定を満たす仕業にするための処理がおこなわれる。例えば、行程断片ｓの長さが乗務時間又は労働時間の制限を超えて長すぎて仕業にできない場合がある。また、列車を降りて休憩することなく乗り続ける継続乗務に対して労働規定がある場合は、継続乗務の長さ（距離、時間）の制限を超えた行程断片ｓはそのまま仕業にすることができない。そこで、以下に説明するように行程断片ｓを切断する処理がおこなわれる。
【００９２】
ステップＳ７０９では、行程断片ｓが基地駅で開始しているか否かを判定する。行程断片ｓが基地駅で開始している場合は、行程断片ｓを切断して後半部分が基地駅からの便乗と基地駅への便乗となるようにする（ステップＳ７１０）。そして、基地駅からの便乗と基地駅への便乗となった後半部分を集合Ｚに移し（ステップＳ７１１）、前半部分を集合Ｙに移して（ステップＳ７１２）、次のＸループの処理に移る。
【００９３】
これに対して行程断片ｓが基地駅で開始していない場合は、行程断片ｓを切断して前半部分が基地駅からの便乗と基地駅への便乗となるようにする（ステップＳ７１３）。そして、基地駅からの便乗と基地駅への便乗となった前半部分を集合Ｚに移し（ステップＳ７１４）、後半部分を集合Ｙに移して（ステップＳ７１５）、次のＸループの処理に移る。
【００９４】
集合Ｘに属するすべての行程断片ｓに対してＸループの処理をおこなうと、Ｘループから抜け出してステップＳ７１７に移行し、集合Ｙが空であるか否かが判定される。
【００９５】
そして、集合Ｙに切断された行程断片の一部が格納されている場合は、ステップＳ６に移行して切断された部分を対象とした連結処理をおこなう。続いて、ステップＳ７１８では、連結結果を集合Ｘに加え、集合Ｙを空にして、再びＸループの処理（ステップＳ７０３）をおこなう。
【００９６】
これに対して集合Ｙが空となっている場合は、すべての仕業が作成されことになるので、ステップＳ７１９に進む。ここで、作成された仕業は集合Ｚの要素となっているので、リターンさせて仕業の改善をおこなうステップＳ８に移行する。
【００９７】
図６は、仕業の改善をおこなうステップＳ８の詳細な処理の流れを説明するフローチャートである。解改善手段３８によって仕業の改善処理を開始して（ステップＳ８１）、ここまでに作成された複数の仕業間の調整によるコストの削減が可能か否かを検討する。
【００９８】
例えば、便乗が非常に長い仕業や待ち時間が長い仕業がある場合、他の仕業の一部と交換することで、適切な仕業に改善できる場合がある。この解改善手段３８では、仕業間で仕業の一部（行程断片）同士を交換することによって、便乗時間を短くしたり、待ち時間を短縮したりする。仕業の一部の交換は、仕業の開始部分と終了部分を除けば、基地駅が異なる仕業の一部同士の交換であってもよい。また、仕業の一部同士の交換によって便乗のみの仕業が作成されれば、その仕業は不要な仕業であるため削除することができる。
【００９９】
ステップＳ８２では、まず、仕業間の行程断片同士を交換することでコストが削減できるものがあるか否かを探す（ステップＳ８２）。上述したように、第１の仕業が行程断片viiと行程断片viiiとを連結したもので、第２の仕業が行程断片ixと行程断片xとを連結したものである場合に、合計のコスト削減量が9であったとする。これに対して、第１の仕業を行程断片viiと行程断片xとを連結したものにし、第２の仕業を行程断片ixと行程断片viiiとを連結したものにすることで、合計のコスト削減量が12となって改善される場合がある。
【０１００】
このように仕業間の行程断片の交換によってコスト削減ができる場合は（ステップＳ８３）、仕業間で行程断片の交換を行う（ステップＳ８４）。上記した例では、第１の仕業の行程断片viiiと第２の仕業の行程断片xとを交換することによって、コスト削減量を9から12に改善させることができる。
【０１０１】
この解改善手段３８による仕業を改善する処理は、コスト削減ができる仕業間の行程断片の交換が存在しなくなるまで繰り返し、存在しなくなった場合はリターン（ステップＳ８５）させて、交番を作成するステップＳ９に移行する。
【０１０２】
図１３は、交番の作成をおこなうステップＳ９の詳細な処理の流れを説明するフローチャートである。交番作成手段３７によって交番の作成処理が開始される（ステップＳ９１）。すなわち、ここまでに作成された仕業に基づいて基地駅ごとに交番を作成する。
【０１０３】
まず、ステップＳ９２で運転士の最低必要人数を計算する。例えば、２０個の仕業が作成されていれば、運転士の最低必要人数は２０人である。続いて、ルール化が容易におこなえる労働規定を制約にしてステップＳ９３でチェックをおこなう。
【０１０４】
ここで、ルール化が容易な労働規定とは、例えば深夜乗務の回数、休日の比率、仕業間の隙間（休養時間）の最低必要時間などが挙げられる。これらは簡単に数値化できる労働規定であり、演算処理に適しているため制約としてルール化する。ここで、特定の運転士の人数で制約を満たせるかどうか、また制約を満たすための交番の作成に関する処理は、公知の制約プログラミング技法を使用して容易におこなうことができる。
【０１０５】
そして、この段階で所定の制約を満たしていなければ、ステップＳ９６に移行して運転士の人数を増やし、再度、所定の制約を満たしているか否かをチェックする。
【０１０６】
続いてステップＳ９４では、解改善手段３８によって解の改善がおこなえるか否かの検討をおこなう。このステップでの解改善手段３８による改善は、読込み手段３０によって読み込まれた評価関数情報２４ｂを使っておこなう。
【０１０７】
評価関数としては、例えば交番の中に３連休がある場合は評価関数情報２４ｂに記憶された大きさのペナルティを与える。また、５日勤務した次の日が休日ではなく勤務日になっている場合も、評価関数情報２４ｂに記憶された大きさのペナルティを与える。ペナルティの大きさは、任意に設定することができるが、例えば違反してはいけない条件に近いほど大きなペナルティとし、希望程度の条件には小さなペナルティを設定する。
【０１０８】
このように評価関数として採用されている条件に基づいて、作成された交番のペナルティを積算していく。そして、仕業の順序を入れ替えることによってペナルティが低下する場合は、改善とみなす。このような解改善手段３８による解の改善は、ペナルティの低下量が所定値以下になるまで繰り返す。
【０１０９】
続いてステップＳ９５において、改善された交番による勤務が労働規定に違反していないかをチェックする。この段階で労働規定の違反があれば、交番として成立しないため、ステップＳ９６に移行して運転士の人数を増加して、再び制約のチェックから処理をやり直す。他方、労働規定の違反がなければ、交番が完成する。
【０１１０】
次に、本実施の形態の運転士運用計画作成システム１の作用について説明する。
【０１１１】
このように構成された本実施の形態の運転士運用計画作成システム１は、列車の運行を基地駅に結び付けて行程断片に置き換えていく。さらに、行程断片同士を連結した際にも新たな行程断片に基地駅を設定する。
【０１１２】
このように行程断片が常に基地駅と結び付けられることで、複数の機関区で使用される駅を通る列車の乗務員運用計画問題が適切に整理されて振り分けられていく。この結果、計算が発散して解が得られなくなることがなくなる。すなわち、乗務員運用計画を作成する際の演算負荷は、駅の数や運行の数などの問題の大きさの２乗やそれ以上のオーダーで増加するため、問題を適切に整理して演算負荷を減すことで、解を得られやすくすることができる。
【０１１３】
また、基地駅と結び付けることで、実態に即した整理をおこなうことができる。さらに、基地駅を設定するに際して、コストが小さくなるような設定をおこなっていけば、効率的な乗務員運用計画に導いていくことができる。
【０１１４】
そして、仕業作成手段３５で作成された仕業が労働規定に違反しているか否かを労働規定チェック手段３６によってチェックし、違反がある仕業については切断などによって調整できるようにすれば、人手による修正を極力、減らすことができる。
【０１１５】
また、修正が不要な仕業が作成されれば、そのまま交番の作成に移行することができる。さらに、解改善手段３８によって評価の高い交番に改善できるようにすれば、乗務員の満足度が高い適切な乗務員運用計画を作成することができる。
【０１１６】
以上、図面を参照して、本発明の実施の形態を詳述してきたが、具体的な構成は、この実施の形態に限らず、本発明の要旨を逸脱しない程度の設計的変更は、本発明に含まれる。
【０１１７】
例えば、前記実施の形態では、データベース２と処理部３と出力手段４とを備えた運転士運用計画作成システム１について説明したが、これに限定されるものではなく、前記実施の形態で説明した処理部３の各種手段を実行させるコンピュータプログラム又はそのようなコンピュータプログラムがインストールされたコンピュータが本発明の乗務員運用計画作成システムであってもよい。
【符号の説明】
【０１１８】
１ 運転士運用計画作成システム（乗務員運用計画作成システム）
２ データベース（データ記憶手段）
２１ 列車運行データ
２１ｂ 運行情報
２２ 労働規定情報
２３ 運転士データ
２３ａ 基地駅情報
２４ 評価データ
２４ａ コスト情報
２４ｂ 評価関数情報
３ 処理部
３０ 読込み手段
３１ 仮基地駅設定手段
３２ 行程断片設定手段
３３ 連結コスト算出手段
３４ 行程断片連結手段
３５ 仕業作成手段
３６ 労働規定チェック手段
３７ 交番作成手段
３８ 解改善手段
【技術分野】
【０００１】
本発明は、列車の運行に対して運転士や車掌などの乗務員を割り当てる乗務員運用計画を作成するための乗務員運用計画作成システムに関するものである。
【背景技術】
【０００２】
例えば１年に一度、列車ダイヤが見直されて改正されると、それに合わせて乗務員の運用計画も作成し直す必要がある。この作業は、従来、長い日数と多大な労力をかけて手作業でおこなわれていた。これに対して、近年、コンピュータを使った乗務員の運用計画を作成する装置が開発されている（特許文献１，２参照）。
【０００３】
ところが、一つの列車ダイヤに対して考えられる乗務員運用計画（解）は無数にあるため、高性能の演算能力を備えたコンピュータが存在する今日においても、総当り的な計算では実用的に解を得ることは難しい。また、その中から最適な解を探索することはさらに困難である。このため、コンピュータ化をおこなうに際しては、様々な工夫がなされている。
【０００４】
特許文献１に開示された乗務行路計画装置は、乗務員の待ち時間の長さを基礎コストとして捉え、基礎コストの総和が小さくなる行路（仕業）が残存していくように演算を進める装置となっている。
【０００５】
また、特許文献２には、操作者がマウスを操作して修正をおこなうことが可能な乗務交番作成装置が開示されている。このような装置であれば、コンピュータで処理させ難い部分を、操作者の判断によって補うことで演算負荷を減らすことができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−１８８２２２号公報
【特許文献２】特許第２５９７０７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
このように従来からコンピュータを使って乗務員運用計画を作成するための処理の工夫がおこなわれているが、最適な処理手法が確立されているとは言い難いのが現状である。
【０００８】
また、乗務員はいずれかの機関区（「基地駅」と表現する場合もある。）に所属することになるが、列車は機関区を跨って運行されており、いずれの機関区に所属する乗務員が乗務してもいいような場合がある。そのような場合に、適切な処理がおこなわれなければ、実態に合わない解が求められたり、問題が大きくなって解けなくなったりするおそれがある。
【０００９】
そこで、本発明は、列車の運行に基づいて作成される行程断片を常に基地駅と結び付けて処理していくことで、実態に即した乗務員運用計画を少ない演算負荷で作成することができる乗務員運用計画作成システムを提供することを目的としている。
【課題を解決するための手段】
【００１０】
前記目的を達成するために、本発明の乗務員運用計画作成システムは、列車の運行に対して乗務員を割り当てる乗務員運用計画作成システムであって、列車の運行に関する運行情報及び乗務員の勤務の開始地点及び終了地点を示す基地駅に関する基地駅情報が記憶されたデータ記憶手段からデータを読み込む読込み手段と、前記読込み手段によって読み込まれた前記運行情報に対して前記基地駅とのコストを計算し、コストが最小になる基地駅を運行の仮の基地駅に設定する仮基地駅設定手段と、仮の基地駅が設定された運行をその基地駅に勤務する前記乗務員の仕業を作成するための行程断片に設定する行程断片設定手段と、所定の条件を満たす前記行程断片同士の連結による連結コストを計算する連結コスト算出手段と、前記連結コストが最小となる行程断片同士を連結させて新たな行程断片を作成するとともにその基地駅を設定する行程断片連結手段と、前記行程断片と必要に応じて付加される便乗とによって仕業を作成する仕業作成手段とを備えたことを特徴とする。
【００１１】
ここで、前記行程断片連結手段において基地駅の設定をおこなうに際して、連結する２つの行程断片の基地駅が同じ場合はその基地駅を連結後の行程断片の基地駅に設定し、連結する２つの行程断片の基地駅が異なる場合は連結後の行程断片の開始地点と終了地点の各基地駅との間のコストを計算し、コストが小さくなる方を新たな基地駅に設定する処理をおこなうことができる。また、連結する２つの行程断片の基地駅が同じ場合であっても、連結後の行程断片の開始地点と終了地点が同じ基地駅になっているときは、その開始地点と終了地点となっている基地駅を連結後の行程断片の基地駅に設定する処理をおこなうこともできる。
【００１２】
さらに、前記データ記憶手段には乗務員の労働規定情報が記憶されており、前記読込み手段によって前記データ記憶手段から読み込まれた前記労働規定情報に対して、前記仕業作成手段で作成された仕業が違反しているか否かをチェックする労働規定チェック手段を備えた構成とすることができる。
【００１３】
また、前記労働規定チェック手段によって違反がないとされた仕業間において、仕業の一部を切断して交換することで解の改善を図る解改善手段を備えた構成とすることができる。
【００１４】
さらに、前記労働規定チェック手段によって違反がないとされた仕業を組み合わせて、各基地駅の乗務員の勤務順を示す交番を作成する交番作成手段を備えた構成とすることもできる。また、前記交番作成手段によって一旦、作成された交番を評価関数によって評価し、作成される交番の評価が高くなるような改善をおこなう解改善手段を備えた構成とすることもできる。
【発明の効果】
【００１５】
このように構成された本発明の乗務員運用計画作成システムは、列車の運行を基地駅に結び付けて行程断片に置き換えていく。さらに、行程断片同士を連結した際にも新たな行程断片に基地駅を設定する。
【００１６】
このように行程断片が常に基地駅と結び付けられることで、複数の機関区で使用される駅を通る列車の乗務員運用計画問題が適切に整理されて振り分けられていく。この結果、計算が発散して解が得られなくなることがなくなり、実態に即した乗務員運用計画が少ない演算負荷で作成できるようになる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施の形態の乗務員運用計画作成システムの構成を説明するブロック図である。
【図２】列車の運行を行程断片に設定するまでの処理の流れを説明するフローチャートである。
【図３】行程断片を連結して交番を作成するまでの全体の処理の流れを説明するフローチャートである。
【図４】行程断片を連結する処理の詳細な流れを説明するフローチャートである。
【図５】仕業を作成する処理の詳細な流れを説明するフローチャートである。
【図６】仕業を改善する処理の詳細な流れを説明するフローチャートである。
【図７】運行情報を説明するための説明図である。
【図８】行程断片を連結して作成される仕業を説明するための説明図である。
【図９】運行の基地駅を設定する処理を説明するための説明図である。
【図１０】行程断片同士を連結した際に基地駅を設定する処理を説明するための説明図である。
【図１１】行程断片同士を連結した際に基地駅を設定する処理を説明するための説明図である。
【図１２】行程断片同士を連結した際に基地駅を設定する処理を説明するための説明図である。
【図１３】交番を作成する処理の詳細な流れを説明するフローチャートである。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について図面を参照して説明する。図１は、本実施の形態の乗務員運用計画作成システムとしての運転士運用計画作成システム１の構成を説明するブロック図である。
【００１９】
本実施の形態の運転士運用計画作成システム１は、データ記憶手段としてのデータベース２と、処理部３と、出力手段４とを主に備えている。ここで説明する運転士運用計画作成システム１の処理部３は、後述する各種手段を実行させるコンピュータプログラムがインストールされたコンピュータによって主に構成される。
【００２０】
そして、本実施の形態の運転士運用計画作成システム１は、列車の運行に対して乗務員としての運転士を割り当てる運転士運用計画を作成するためのシステムである。
【００２１】
この運転士運用計画作成システム１を作動させる前提として、まず、列車ダイヤ（又は列車運行計画）が作成されていることが条件となる。列車ダイヤには、走行する列車の情報が１日分となって記憶されている。
【００２２】
そして、列車番号で特定される１本の列車の情報は、停車駅間の運行情報に分割することができる。図７に示した運行ａは、ある列車の停車駅となるＡ駅とＢ駅との間の運行情報を表している。運行ａは、Ａ駅をh1:m1:s1に出発して、Ｂ駅にh2:m2:s2に到着するという情報である。
【００２３】
一方、運転士や車掌などの乗務員の情報としては、乗務員が所属する機関区の情報がある。この機関区には、勤務の開始駅（開始地点）及び終了駅（終了地点）となる基地駅がある。乗務員の勤務は、勤務の開始駅と勤務の終了駅とが同じ駅、すなわち同じ基地駅にする必要がある。このように乗務員の勤務は、基地駅による制約が強い性質を有している。
【００２４】
以上に述べた情報は、図１に示すようにデータ記憶手段としてのデータベース２に記憶される。データベース２には、ハードディスク、ＲＯＭ(Read Only Memory)などの各種記憶媒体が使用できる。
【００２５】
そして、データベース２には、列車運行データ２１、運転士データ２３、評価データ２４などが記憶される。また、列車運行データ２１には、列車番号に関する列車番号情報２１ａと運行情報２１ｂとが含まれる。
【００２６】
また、運転士データ２３には、運転士が所属する基地駅を示す基地駅情報２３ａ、労働規定情報２２などが含まれる。労働規定情報２２は、乗務員の勤務に対して定められている労働法規、就業規則、労使間で取り決められた規定や協定などの情報である。
【００２７】
この労働規定情報２２による制約は、乗務員運用計画を作成するに際して必ず守らなければならない（違反してはいけない）強い制約と、遵守すべきであるが一部であれば守られなくても計画が作成できる弱い制約とがある。
【００２８】
さらに、評価データ２４には、コスト情報２４ａ、評価関数情報２４ｂなどが含まれる。コスト情報２４ａは、後述する各種手段において処理をおこなう際の判断基準とするためのコストの情報である。何をコストとするかは処理の段階によって異なるが、基地駅までの移動時間や距離、次の乗務までの待ち時間、便乗（移動のための勤務を伴わない乗務）などがコストとなり得る。また、労働規定との関連でもコストとなり得る情報がある。例えば、深夜乗務は２時間を超えると休憩が必要なため、２時間を超えない乗務にした方がコストは安くなる。また、在宅休養時間に関する配慮から休日の前の退勤時刻や休日の後の出勤時刻には制限があり、制限が守れない場合には運転士を増やす必要があるため、早朝出勤又は深夜到着は高コストと考えられる。さらに、１回の仕業の後にその仕業と同じ時間以上の休憩が必要になるため、長すぎる仕業は高コストと考えられる。
【００２９】
一方、評価関数情報２４ｂは、コスト情報２４ａと同様に後述する各種手段において処理をおこなう際の判断基準とするための情報である。例えば、同一列車に連続して乗務させるのが好ましい、３連休は作らないようにするのが好ましい、５日勤務した後は休日を与えるなど、好ましい仕業又は交番が作成されるようにするために、好ましくない計画にペナルティが与えられるような評価関数を導入することができる。
【００３０】
処理部３は、データベース２に記憶された各種データを読み込む読込み手段３０と、各種処理手段３００と、各種処理手段３００において作成された解の改善をおこなう解改善手段３８とを主に備えている。
【００３１】
この処理部３は、上記した各種手段の演算をおこなうためのＣＰＵ(Central Processing Unit)、一時記憶領域としてのＲＡＭ(Random Access Memory)などのハード部と、各種手段を実行させるためにインストールされたコンピュータプログラム（ソフト部）とによって主に構成される。
【００３２】
各種処理手段３００は、仮基地駅設定手段３１と、行程断片設定手段３２と、連結コスト算出手段３３と、行程断片連結手段３４と、仕業作成手段３５と、労働規定チェック手段３６と、交番作成手段３７とを主に備えている。
【００３３】
仮基地駅設定手段３１では、読込み手段３０によってデータベース２から読み込まれた列車運行データ２１の運行情報２１ｂを、同じく読込み手段３０によってデータベース２から読み込まれた基地駅情報２３ａの基地駅に結び付ける処理をおこなう。
【００３４】
この基地駅に運行を結び付けるにあたっては、コストが基準になる。図７を使って説明すると、運行ａはＡ駅を出てＢ駅に到着する運行情報である。ここで、Ａ駅は基地駅でありＢ駅は基地駅ではない。このように運行の開始地点又は終了地点のいずれかが基地駅である場合は、基地駅であるＡ駅を運行ａの基地駅に設定する。
【００３５】
また、運行の開始地点と終了地点の両方が基地駅である場合は、開始時刻と終了時刻のうち望ましい方、すなわちコストが小さい方の基地駅に設定される。例えば開始時刻が早朝となる場合は出勤のためのコストが高くなる場合があるため、高いコストに設定される。一方、終了時刻が深夜となる場合は、深夜到着となってコストが高くなる場合があるため高いコストに設定される。よって、開始時刻が早朝で終了時刻が昼間の場合は、運行の基地駅は終了地点となる駅に設定される。
【００３６】
さらに、図９を使って説明すると、運行ｂはＢ駅を出てＣ駅に到着する運行情報である。ここで、Ｂ駅とＣ駅は基地駅ではない。そこで、Ｂ駅の最寄りの基地駅がＡ駅である場合に、まず、Ａ駅とＢ駅との間の列車に乗ったときの移動時間をコストＣ1として計算する。この移動時間に関する情報はデータベース２のコスト情報２４ａから読み込まれる。一方、Ｃ駅の最寄りの基地駅がＤ駅であれば、Ｃ駅とＤ駅との間の列車に乗ったときの移動時間をコストＣ2として計算する。そして、コストＣ1とコストＣ2とを比較してコストが小さくなる方の基地駅を運行ｂの基地駅に設定する。
【００３７】
なお、Ｂ駅とＣ駅の最寄りの基地駅を決める際もコストの比較をおこなえば良い。また、公知のワーシャル・フロイド法などのアルゴリズムを使って予め各駅の最寄りの基地駅を求めておき、基地駅情報２３ａとして記憶させておくこともできる。
【００３８】
また、行程断片設定手段３２では、仮基地駅設定手段３１によって仮の基地駅が設定された運行を運転士の行程断片に設定する。ここで、「行程断片」とは、運転士の仕業（１回の勤務、「行路」と呼ぶ場合もある。）を構成する単位である。一つの仕業に含まれる同一列車の連続を行程といい、行程は運転士の乗り換えが可能な駅で分割でき、その分割された行程を行程断片と呼ぶ。このため、複数の行程断片を連結していくことで一つの仕業を作成することができる。そして、列車の運行情報２１ｂは、行程断片として使用可能な単位でデータベース２に記憶されている。
【００３９】
図７，８を参照しながらさらに説明すると、仮の基地駅がＡ駅に設定された駅ＡＢ間の運行ａは、行程断片iに設定される。同様に駅ＢＣ間の運行は行程断片iiに設定され、駅ＣＡ間の運行は行程断片iiiに設定される。
【００４０】
そして、行程断片iと行程断片iiと行程断片iiiとを連結すると、基地駅Ａを開始地点として出発し、最終的に到着する基地駅Ａが終了地点となる一つの仕業が作成できる。すなわち行程断片設定手段３２では、このような仕業の構成要素となる行程断片を設定する。
【００４１】
さらに、連結コスト算出手段３３では、行程断片同士を連結した際の連結コストを計算する。まず、行程断片同士を連結する前提条件として、前にくる行程断片の到着駅と後にくる行程断片の出発駅とが同じでなければならない。また、当然の前提として、前にくる行程断片の列車が到着する時刻よりも、後にくる行程断片の列車が出発する時刻の方が、乗換え時間も考慮したうえでの後の時刻でなければならない。
【００４２】
例えば図８を使って説明すると、行程断片iの到着駅はＢ駅であるため、出発駅がＢ駅である行程断片iiとは連結することができるが、出発駅がＣ駅である行程断片iiiとは連結することができない。
【００４３】
一方、出発駅がＢ駅となる行程断片は行程断片iiの他にもある可能性があり、行程断片iに連結させる行程断片の候補が複数ある場合に、いずれを連結させるかを決めなければならない。その選択基準として、連結コスト算出手段３３によって算出された連結コストが使用される。
【００４４】
この連結コストになり得るものとしては、待ち時間の長さが挙げられる。例えば行程断片iに設定された運行ａのＢ駅に到着する時刻と、行程断片iiに設定された運行のＢ駅を出発する時刻との間に長い待ち時間があれば、その間は勤務中でありながら業務をおこなっていない時間となるためコストと考えられる。このため、待ち時間の長さを連結コストにすることで、待ち時間が短くなるような行程断片同士の連結をおこなわせることができる。
【００４５】
また、連結される行程断片が同じ列車の乗務であるか否かも連結コストとすることができる。すなわち、同一の列車に乗り続ける乗務の方が望ましいため、連結させる行程断片の列車が同一の場合は連結コストを小さくし、列車の乗換えが必要な場合は連結コストを大きくする。
【００４６】
さらに、労働規定などにも上述したように、深夜乗務、早朝出勤又は深夜到着、連結後の仕業の長さなど、連結コストとして計算可能な項目があるため、必要に応じて計算をおこなう。このように複数の種類の基準をコストとして同時に使用する場合は、コスト情報２４ａに同一基準に換算するための係数などを記憶させておき、必要に応じて読み込ませればよい。
【００４７】
そして、行程断片連結手段３４では、候補に挙がっている行程断片の中から連結コストが最小となる行程断片同士を連結させる。この行程断片連結手段３４で行程断片同士を連結させると、連結後の行程断片が新たな行程断片となり、連結前の行程断片は削除されることになる。
【００４８】
例えば図１０を参照しながら説明すると、Ａ駅を出発してＢ駅に到着する行程断片iと、Ｂ駅を出発してＣ駅に到着する行程断片iiとを連結すると、Ａ駅を出発してＣ駅に到着する行程断片が新たな行程断片iとなる。そして、連結前の行程断片iiは削除される。
【００４９】
また、行程断片連結手段３４では、連結後の基地駅の設定をおこなう。図１０に示すように連結する２つの行程断片i,iiの基地駅がいずれもＡ駅で同じとなる場合は、そのままＡ駅が新たな行程断片iの基地駅に設定される。
【００５０】
これに対して図１１に示すように、連結する２つの行程断片i,ivの基地駅が異なる場合がある。すなわち、行程断片iの基地駅はＡ駅であるが、行程断片ivの基地駅はＥ駅と異なっており、行程断片iと行程断片ivとを連結した新たな行程断片iの基地駅をいずれの駅にするかが問題となる。
【００５１】
そこで、連結後の行程断片iに対して、Ａ駅から開始するコストＣ3とＥ駅で終了するコストＣ4を計算しコストが小さい方を基地駅に設定する。ここで、コストを各基地駅（Ａ駅、Ｅ駅）から行程断片iの出発駅（Ａ駅）と到着駅（Ｄ駅）までの移動時間とすると、基地駅となるＡ駅と出発駅となるＡ駅は同じ駅であり移動時間が不要のため、新たな行程断片iの基地駅はＡ駅となる。
【００５２】
また、図１２に示すように、連結する２つの行程断片v,viの基地駅がいずれもＥ駅で同じとなる場合であっても、連結後の新たな行程断片vの開始地点と終了地点が同じ駅であり、かつその駅が基地駅のときは、上述した処理とは異なる処理をおこなう。すなわち、連結後の行程断片vは、基地駅であるＡ駅を開始地点とし、基地駅であるＡ駅を終了地点とする行程断片であるため、Ｅ駅ではなくＡ駅を基地駅に設定する。なお、この場合は、行程断片vがそのまま一つの仕業となる。
【００５３】
そして、仕業作成手段３５では、行程断片から仕業を作成する。行程断片連結手段３４により連結を繰り返した行程断片は、仕業として充分な長さになっている。
【００５４】
図１２で説明したような同じ基地駅Ａが開始地点と終了地点となる行程断片vは、それだけで一つの仕業となる。これに対して、行程断片の開始地点又は終了地点が基地駅でない場合は、便乗を付加することで仕業を完成させなければならない。
【００５５】
例えば、図１１に示した連結後の行程断片iは、開始地点は基地駅Ａであるが終了地点はＤ駅と基地駅Ａとは異なる駅であるため、Ｄ駅からＡ駅に移動する便乗を行程断片iの後に付加しなければならない。同様に、行程断片の開始地点が基地駅でない場合も、基地駅から行程断片の開始地点に移動する便乗を行程断片の前に付加する。
【００５６】
労働規定チェック手段３６は、仕業作成手段３５で作成された仕業が労働規定を満たしているかをチェックする。例えば、作成された仕業が長すぎて１日の乗務時間の制限を超えていれば、その仕業は成り立たない。また、継続して乗務することができる距離や時間に制限がある場合は、それを超える乗務を含む仕業は成り立たない。さらに、乗務時間以外の必要業務時間を加えた総労働時間が労働規定の制限を超えるような仕業も成り立たない。
【００５７】
便乗を付加した場合に仕業として成り立たない場合は、行程断片を切断して短くし、それに対して便乗を付加することによって仕業として成り立つようにする。例えば、行程断片が基地駅で開始していない場合は、切断によるコストの増加が最も少なくなるように行程断片を切断し、切断された前半部分に対して基地駅からの便乗と基地駅への便乗を付加して仕業とする。この仕業がまだ仕業として成り立たない場合は、さらに行程断片を切断して同様に処理する。一方、切断された後半部分については、他の行程断片に対する処理がすべて終わった後に、再び行程断片連結手段３４による連結の対象にする。
【００５８】
同様に、行程断片が基地駅で終了していない場合は、切断によるコストの増加が最も少なくなるように行程断片を切断し、切断された後半部分に対して基地駅からの便乗と基地駅への便乗を付加して仕業とする。この仕業がまだ仕業として成り立たない場合は、さらに行程断片を切断して同様に処理する。一方、切断された前半部分については、他の行程断片に対する処理がすべて終わった後に、再び行程断片連結手段３４による連結の対象にする。このようにして労働規定チェック手段３６では、すべての仕業が労働規定を満たして成り立つようになるまで処理を繰り返す。
【００５９】
上述したようにして仕業作成手段３５及び労働規定チェック手段３６によって作成された仕業は、解改善手段３８によって改善することができる。すなわち、作成された仕業に含まれる複数の行程断片を総合的に検討すると、コスト削減の可能性がある場合がある。例えば、行程断片vii,viii,ix,xが存在し、行程断片viiは、行程断片viii又は行程断片xとの連結が可能であるとする。また、行程断片ixは、行程断片viii又は行程断片xとの連結が可能であるとする。
【００６０】
そして、行程断片viiと行程断片viiiとを連結することによるコスト削減量が8、行程断片viiと行程断片xとを連結することによるコスト削減量が5であるとする。また、行程断片ixと行程断片viiiとを連結することによるコスト削減量が7、行程断片ixと行程断片xとを連結することによるコスト削減量が1であるとする。
【００６１】
このような条件下で最もコスト削減量が大きい行程断片同士の連結を最初にするとすれば、行程断片viiと行程断片viiiとが最初に連結されてコスト削減量が8になる。そして、行程断片viiiが連結に使用された後に残るのは行程断片xなので、行程断片ixと行程断片xとが連結されてコスト削減量の1が加算され、合計のコスト削減量は9となる。
【００６２】
これに対して行程断片viiと行程断片xとを最初に連結するとコスト削減量が5、残った行程断片viiiと行程断片ixとを連結するとコスト削減量が7となり、合計のコスト削減量は12となる。すなわち、合計のコスト削減量は、行程断片viiと行程断片xとを連結し、行程断片ixと行程断片viiiとを連結した場合の方が大きくなる。このように合計のコスト削減量が最も大きくなるように行程断片同士を連結させることで、仕業を改善する。
【００６３】
さらに仕業の改善の方法についての詳細を説明すると、例えば、仕業の一部（最小行程断片の長さ以上の部分）を切断し、他の行程断片又は他の行程断片の一部との交換をおこなう。交換後の仕業のコストが、交換前の仕業のコストよりも小さくなっていれば、解が改善されたことになる。この解改善手段３８による改善は、コストが削減されなくなるまでおこなう。
【００６４】
この行程断片（又は一部）の交換は、仕業の開始部分又は終了部分では同じ基地駅の仕業同士でおこなわなければならないが、それ以外の部分の交換は基地駅が異なる仕業間でおこなってもよい。解改善手段３８によって改善された仕業は、労働規定チェック手段３６によってチェックされ、労働規定を満たす仕業のみが改善結果として生成される。
【００６５】
また、コスト削減が可能か否かの判断は、例えば前回の交換によって算出されたコストと今回の交換によって算出されたコストとを比較して、同じ又は今回のコストが高くなったときには、これ以上のコスト削減は不可能と判断させることでおこなえる。
【００６６】
交番作成手段３７では、仕業作成手段３５により作成され又は解改善手段３８により改善され、労働規定チェック手段３６によって労働規定を満たすことが確認された仕業に基づいて交番を作成する。「交番」とは、基地駅に勤務する運転士の勤務順を示す。例えば、基地駅Ａで仕業が２０個作成されると、２０個の仕業を縦に並べた交番が作成され、２０日間単位の乗務の予定となる。
【００６７】
交番作成手段３７では、交番を実行する人数を最低必要人数から一人ずつ増やしていき、労働規定に違反しない交番が作成されるまで人数の増加を繰り返す。
【００６８】
一方、交番にも、運転士の数、仕業の並べ方の組み合わせ数などによって幾通りもの解があり、解改善手段３８による改善の余地がある。交番作成手段３７に対する解改善手段３８の処理は、評価関数を使っておこなう。
【００６９】
すなわち、作成された交番の評価を、データベース２の評価関数情報２４ｂから読み込まれたデータによっておこない、評価が高くなる（ペナルティが小さくなる）ように仕業の順番を入れ替える。この解改善手段３８による解の改善は、評価が変わらなくなるまでおこなう。
【００７０】
そして、出力手段４は、交番作成手段３７で作成された交番、又は労働規定チェック手段３６でチェックを受けた仕業などを出力させる手段であって、演算結果をデータとして記憶させる記憶媒体、紙に印刷させるプリンタ、画面に表示させるモニタのいずれの形態であってもよい。
【００７１】
次に、本実施の形態の運転士運用計画作成システム１の処理の流れについて、図２−６，１３のフローチャートを主に参照しながら説明する。
【００７２】
まず、ステップＳ１において、読込み手段３０によって列車運行データ２１に含まれる運行情報２１ｂを読み込ませる。また、ステップＳ２において、読込み手段３０によって運転士データ２３に含まれる基地駅情報２３ａを読み込ませる。
【００７３】
そして、読み込まれた運行情報２１ｂと基地駅情報２３ａとに基づいて、仮基地駅設定手段３１によって運行情報２１ｂの中の運行の各基地駅に対するコストを計算する（ステップＳ３）。
【００７４】
図９に示した図で説明すると、運行情報２１ｂの中の例えば運行ｂの基地駅として、Ａ駅とＤ駅とが候補に割り当てられていたとする。これに対して仮基地駅設定手段３１では、運行ｂの開始地点となるＢ駅と基地駅ＡとのコストＣ1を計算するとともに、運行ｂの終了地点となるＣ駅と基地駅ＤとのコストＣ2を計算する。そして、コストＣ1とコストＣ2とを比較して、小さい方に結び付けられた基地駅を運行ｂの基地駅として設定する（ステップＳ４）。
【００７５】
このように基地駅を設定していく理由としては、運転士の運用計画は基地駅ごとに作成されるため、運行を基地駅に結び付けて処理を進めていくことで、組み合わせの数を適切に削減していくことができるからである。
【００７６】
そして、ステップＳ５では、基地駅に結び付けられた運行を、行程断片設定手段３２によって運転士の行程断片に設定する。ここまでの処理で、運行情報２１ｂに含まれる運行の全てが行程断片に設定される。
【００７７】
続いて、図３−６を参照しながら、行程断片を連結して交番を作成するまでの処理について説明する。まず、全体の流れを説明すると、図３に示すように、基地駅に結び付けられた全ての行程断片を対象にして連結処理をおこなう（ステップＳ６）。続いて、ステップＳ７では連結後の行程断片から仕業を作成し、改善可能な仕業はステップＳ８で改善する。そして、各基地駅に与えられた仕業を組み合わせて交番を作成する（ステップＳ９）。
【００７８】
図４は、行程断片の連結をおこなうステップＳ６の詳細な処理の流れを説明するフローチャートである。行程断片の連結処理が開始されると（ステップＳ６１）、連結コスト算出手段３３によって行程断片同士を連結した際の連結コストを計算する。すなわち、ある行程断片に対して連結可能な行程断片は、この段階では複数、存在するため、それらの連結候補となる行程断片と連結したときの連結コストをそれぞれ計算しておく。この連結コストの算出により、連結によってコスト削減が可能となる行程断片が全て探し出される（ステップＳ６２）。
【００７９】
このステップで計算される連結コストとして、例えば待ち時間の長さを挙げることができる。例えば、行程断片iのＢ駅に到着する時刻と行程断片iiのＢ駅を出発する時刻との差が10分であれば、待ち時間10分に基づいたコストＣ(i,ii)が算出される。一方、行程断片iのＢ駅に到着する時刻と行程断片xのＢ駅を出発する時刻との差が30分であれば、待ち時間30分に基づいたコストＣ(i,x)が算出される。
【００８０】
また、同一の列車に乗務する行程断片同士の連結に対しては、予め設定されてコスト情報２４ａに記憶されている小さいコストを与え、列車の乗換えが必要となる行程断片同士の連結に対してはコスト情報２４ａに基づいて大きなコストを与える。
【００８１】
さらに、直接連結できない行程断片同士であっても、便乗を介在させることで連結できる場合がある。便乗には、前の行程断片の到着駅から後の行程断片の出発駅までを最短で結ぶ経路を選べばよい。この最短経路は、公知のダイクストラ法などのアルゴリズムを使って求めることができる。しかしながら便乗は業務をしていない時間であるため、連結コストとしてこのステップで計算する。
【００８２】
そして、コスト削減が可能な連結が存在する場合には（ステップＳ６３）、コスト削減が最大になる（連結コストが最小になる）行程断片同士を、行程断片連結手段３４によって連結させる（ステップＳ６４）。例えば、上述したコストＣ(i,ii)はコスト(i,x)よりも小さい値になるので、行程断片iは行程断片iiと連結させる。この連結によって生成された行程断片は、新たな行程断片iとなり、新たな行程断片iに含まれることになるので連結前の行程断片iiは消滅する。
【００８３】
続いて、行程断片連結手段３４では、連結によって新たに生成された行程断片iの基地駅を設定する。例えば、図１０に示すように、連結前のそれぞれの行程断片i,iiの基地駅がＡ駅で同じであれば、そのＡ駅を連結後の行程断片iの基地駅に設定する。
【００８４】
但し、図１２に示すように、連結前のそれぞれの行程断片v,viの基地駅が同じであっても、その駅を基地駅にしない場合がある。それは、連結後の行程断片vの開始地点と終了地点が同じ駅であって、その駅が基地駅である場合である。この例では、行程断片vの開始地点と終了地点とが同じＡ駅であり、Ａ駅は基地駅であるため、行程断片vの基地駅はＡ駅に設定される。
【００８５】
これに対して、図１１に示すように、連結前のそれぞれの行程断片i,ivの基地駅がＡ駅とＥ駅とで異なっている場合は、コストを比較することによって基地駅を決める。この基地駅を設定するためのコストは行程断片連結手段３４において計算される。例えば、図１１に示した連結後の行程断片iについては、開始地点であるＡ駅は基地駅であるため、移動時間に基づいたコストＣ3は０である。これに対して終了地点であるＤ駅は基地駅ではなく、Ｅ駅が最寄りの基地駅であるため、コストＣ4＞0である。このため、連結後の行程断片iには、小さい方のコストＣ3に関連付けられたＡ駅が基地駅として設定される。
【００８６】
この行程断片を連結させる処理は、コスト削減が可能な連結が存在しなくなるまで繰り返し、存在しなくなった場合はリターン（ステップＳ６５）させて、仕業を作成するステップＳ７に移行する。
【００８７】
図５は、仕業の作成をおこなうステップＳ７の詳細な処理の流れを説明するフローチャートである。仕業作成手段３５によって仕業の作成処理が開始されると（ステップＳ７０１）、まず、ステップＳ７０２において全ての行程断片ｓが集合Ｘの要素に設定される。また、空集合として集合Ｙと集合Ｚが作成される。
【００８８】
そして、Ｘループに移行する（ステップＳ７０３）。Ｘループでは、集合Ｘの要素であるすべての行程断片ｓに対して演算がおこなわれる。ステップＳ７０４では、演算対象となっている行程断片ｓについて、基地駅で開始されて基地駅で終了しているか否かの判定がおこなわれる。例えば図８に示すような行程断片i,ii,iiiを連結させて生成された行程断片ｓは、基地駅であるＡ駅から開始されてＡ駅で終了するため、そのまま仕業として成立する。このように基地駅で開始されて基地駅で終了している行程断片ｓは、集合Ｚに移されて（ステップＳ７０５）、次のＸループの処理に移行される（ステップＳ７１６）。
【００８９】
これに対して、開始又は終了の少なくとも一方が基地駅となっていない行程断片ｓに便乗を付加することによって、基地駅で開始して基地駅で終了する行程断片ｔを生成する（ステップＳ７０６）。すなわち、行程断片ｓの開始地点又は終了地点が基地駅でない場合は、基地駅から行程断片ｓの開始地点までの便乗又は行程断片ｓの終了地点から基地駅までの便乗を行程断片に付加することで仕業とすることができる。
【００９０】
そして、便乗が付加された行程断片ｔは、労働規定チェック手段３６によって労働規定に違反していないかがチェックされ（ステップＳ７０７）、労働規定を満たしていれば集合Ｚに移されて（ステップＳ７０８）、次のＸループの処理に移る。
【００９１】
これに対して行程断片ｔが労働規定を満たしていない場合は、再び行程断片ｓに戻ってステップＳ７０９以降で仕業として成り立たせるための処理をおこなう。すなわち、仕業としては完結していても労働規定に違反する仕業を運転士に割り当てることはできないので、労働規定を満たす仕業にするための処理がおこなわれる。例えば、行程断片ｓの長さが乗務時間又は労働時間の制限を超えて長すぎて仕業にできない場合がある。また、列車を降りて休憩することなく乗り続ける継続乗務に対して労働規定がある場合は、継続乗務の長さ（距離、時間）の制限を超えた行程断片ｓはそのまま仕業にすることができない。そこで、以下に説明するように行程断片ｓを切断する処理がおこなわれる。
【００９２】
ステップＳ７０９では、行程断片ｓが基地駅で開始しているか否かを判定する。行程断片ｓが基地駅で開始している場合は、行程断片ｓを切断して後半部分が基地駅からの便乗と基地駅への便乗となるようにする（ステップＳ７１０）。そして、基地駅からの便乗と基地駅への便乗となった後半部分を集合Ｚに移し（ステップＳ７１１）、前半部分を集合Ｙに移して（ステップＳ７１２）、次のＸループの処理に移る。
【００９３】
これに対して行程断片ｓが基地駅で開始していない場合は、行程断片ｓを切断して前半部分が基地駅からの便乗と基地駅への便乗となるようにする（ステップＳ７１３）。そして、基地駅からの便乗と基地駅への便乗となった前半部分を集合Ｚに移し（ステップＳ７１４）、後半部分を集合Ｙに移して（ステップＳ７１５）、次のＸループの処理に移る。
【００９４】
集合Ｘに属するすべての行程断片ｓに対してＸループの処理をおこなうと、Ｘループから抜け出してステップＳ７１７に移行し、集合Ｙが空であるか否かが判定される。
【００９５】
そして、集合Ｙに切断された行程断片の一部が格納されている場合は、ステップＳ６に移行して切断された部分を対象とした連結処理をおこなう。続いて、ステップＳ７１８では、連結結果を集合Ｘに加え、集合Ｙを空にして、再びＸループの処理（ステップＳ７０３）をおこなう。
【００９６】
これに対して集合Ｙが空となっている場合は、すべての仕業が作成されことになるので、ステップＳ７１９に進む。ここで、作成された仕業は集合Ｚの要素となっているので、リターンさせて仕業の改善をおこなうステップＳ８に移行する。
【００９７】
図６は、仕業の改善をおこなうステップＳ８の詳細な処理の流れを説明するフローチャートである。解改善手段３８によって仕業の改善処理を開始して（ステップＳ８１）、ここまでに作成された複数の仕業間の調整によるコストの削減が可能か否かを検討する。
【００９８】
例えば、便乗が非常に長い仕業や待ち時間が長い仕業がある場合、他の仕業の一部と交換することで、適切な仕業に改善できる場合がある。この解改善手段３８では、仕業間で仕業の一部（行程断片）同士を交換することによって、便乗時間を短くしたり、待ち時間を短縮したりする。仕業の一部の交換は、仕業の開始部分と終了部分を除けば、基地駅が異なる仕業の一部同士の交換であってもよい。また、仕業の一部同士の交換によって便乗のみの仕業が作成されれば、その仕業は不要な仕業であるため削除することができる。
【００９９】
ステップＳ８２では、まず、仕業間の行程断片同士を交換することでコストが削減できるものがあるか否かを探す（ステップＳ８２）。上述したように、第１の仕業が行程断片viiと行程断片viiiとを連結したもので、第２の仕業が行程断片ixと行程断片xとを連結したものである場合に、合計のコスト削減量が9であったとする。これに対して、第１の仕業を行程断片viiと行程断片xとを連結したものにし、第２の仕業を行程断片ixと行程断片viiiとを連結したものにすることで、合計のコスト削減量が12となって改善される場合がある。
【０１００】
このように仕業間の行程断片の交換によってコスト削減ができる場合は（ステップＳ８３）、仕業間で行程断片の交換を行う（ステップＳ８４）。上記した例では、第１の仕業の行程断片viiiと第２の仕業の行程断片xとを交換することによって、コスト削減量を9から12に改善させることができる。
【０１０１】
この解改善手段３８による仕業を改善する処理は、コスト削減ができる仕業間の行程断片の交換が存在しなくなるまで繰り返し、存在しなくなった場合はリターン（ステップＳ８５）させて、交番を作成するステップＳ９に移行する。
【０１０２】
図１３は、交番の作成をおこなうステップＳ９の詳細な処理の流れを説明するフローチャートである。交番作成手段３７によって交番の作成処理が開始される（ステップＳ９１）。すなわち、ここまでに作成された仕業に基づいて基地駅ごとに交番を作成する。
【０１０３】
まず、ステップＳ９２で運転士の最低必要人数を計算する。例えば、２０個の仕業が作成されていれば、運転士の最低必要人数は２０人である。続いて、ルール化が容易におこなえる労働規定を制約にしてステップＳ９３でチェックをおこなう。
【０１０４】
ここで、ルール化が容易な労働規定とは、例えば深夜乗務の回数、休日の比率、仕業間の隙間（休養時間）の最低必要時間などが挙げられる。これらは簡単に数値化できる労働規定であり、演算処理に適しているため制約としてルール化する。ここで、特定の運転士の人数で制約を満たせるかどうか、また制約を満たすための交番の作成に関する処理は、公知の制約プログラミング技法を使用して容易におこなうことができる。
【０１０５】
そして、この段階で所定の制約を満たしていなければ、ステップＳ９６に移行して運転士の人数を増やし、再度、所定の制約を満たしているか否かをチェックする。
【０１０６】
続いてステップＳ９４では、解改善手段３８によって解の改善がおこなえるか否かの検討をおこなう。このステップでの解改善手段３８による改善は、読込み手段３０によって読み込まれた評価関数情報２４ｂを使っておこなう。
【０１０７】
評価関数としては、例えば交番の中に３連休がある場合は評価関数情報２４ｂに記憶された大きさのペナルティを与える。また、５日勤務した次の日が休日ではなく勤務日になっている場合も、評価関数情報２４ｂに記憶された大きさのペナルティを与える。ペナルティの大きさは、任意に設定することができるが、例えば違反してはいけない条件に近いほど大きなペナルティとし、希望程度の条件には小さなペナルティを設定する。
【０１０８】
このように評価関数として採用されている条件に基づいて、作成された交番のペナルティを積算していく。そして、仕業の順序を入れ替えることによってペナルティが低下する場合は、改善とみなす。このような解改善手段３８による解の改善は、ペナルティの低下量が所定値以下になるまで繰り返す。
【０１０９】
続いてステップＳ９５において、改善された交番による勤務が労働規定に違反していないかをチェックする。この段階で労働規定の違反があれば、交番として成立しないため、ステップＳ９６に移行して運転士の人数を増加して、再び制約のチェックから処理をやり直す。他方、労働規定の違反がなければ、交番が完成する。
【０１１０】
次に、本実施の形態の運転士運用計画作成システム１の作用について説明する。
【０１１１】
このように構成された本実施の形態の運転士運用計画作成システム１は、列車の運行を基地駅に結び付けて行程断片に置き換えていく。さらに、行程断片同士を連結した際にも新たな行程断片に基地駅を設定する。
【０１１２】
このように行程断片が常に基地駅と結び付けられることで、複数の機関区で使用される駅を通る列車の乗務員運用計画問題が適切に整理されて振り分けられていく。この結果、計算が発散して解が得られなくなることがなくなる。すなわち、乗務員運用計画を作成する際の演算負荷は、駅の数や運行の数などの問題の大きさの２乗やそれ以上のオーダーで増加するため、問題を適切に整理して演算負荷を減すことで、解を得られやすくすることができる。
【０１１３】
また、基地駅と結び付けることで、実態に即した整理をおこなうことができる。さらに、基地駅を設定するに際して、コストが小さくなるような設定をおこなっていけば、効率的な乗務員運用計画に導いていくことができる。
【０１１４】
そして、仕業作成手段３５で作成された仕業が労働規定に違反しているか否かを労働規定チェック手段３６によってチェックし、違反がある仕業については切断などによって調整できるようにすれば、人手による修正を極力、減らすことができる。
【０１１５】
また、修正が不要な仕業が作成されれば、そのまま交番の作成に移行することができる。さらに、解改善手段３８によって評価の高い交番に改善できるようにすれば、乗務員の満足度が高い適切な乗務員運用計画を作成することができる。
【０１１６】
以上、図面を参照して、本発明の実施の形態を詳述してきたが、具体的な構成は、この実施の形態に限らず、本発明の要旨を逸脱しない程度の設計的変更は、本発明に含まれる。
【０１１７】
例えば、前記実施の形態では、データベース２と処理部３と出力手段４とを備えた運転士運用計画作成システム１について説明したが、これに限定されるものではなく、前記実施の形態で説明した処理部３の各種手段を実行させるコンピュータプログラム又はそのようなコンピュータプログラムがインストールされたコンピュータが本発明の乗務員運用計画作成システムであってもよい。
【符号の説明】
【０１１８】
１ 運転士運用計画作成システム（乗務員運用計画作成システム）
２ データベース（データ記憶手段）
２１ 列車運行データ
２１ｂ 運行情報
２２ 労働規定情報
２３ 運転士データ
２３ａ 基地駅情報
２４ 評価データ
２４ａ コスト情報
２４ｂ 評価関数情報
３ 処理部
３０ 読込み手段
３１ 仮基地駅設定手段
３２ 行程断片設定手段
３３ 連結コスト算出手段
３４ 行程断片連結手段
３５ 仕業作成手段
３６ 労働規定チェック手段
３７ 交番作成手段
３８ 解改善手段
【特許請求の範囲】
【請求項１】
列車の運行に対して乗務員を割り当てる乗務員運用計画作成システムであって、
列車の運行に関する運行情報及び乗務員の勤務の開始地点及び終了地点を示す基地駅に関する基地駅情報が記憶されたデータ記憶手段からデータを読み込む読込み手段と、
前記読込み手段によって読み込まれた前記運行情報に対して前記基地駅とのコストを計算し、コストが最小になる基地駅を運行の仮の基地駅に設定する仮基地駅設定手段と、
仮の基地駅が設定された運行をその基地駅に勤務する前記乗務員の仕業を作成するための行程断片に設定する行程断片設定手段と、
所定の条件を満たす前記行程断片同士の連結による連結コストを計算する連結コスト算出手段と、
前記連結コストが最小となる行程断片同士を連結させて新たな行程断片を作成するとともにその基地駅を設定する行程断片連結手段と、
前記行程断片と必要に応じて付加される便乗とによって仕業を作成する仕業作成手段とを備えたことを特徴とする乗務員運用計画作成システム。
【請求項２】
前記行程断片連結手段において基地駅の設定をおこなうに際して、連結する２つの行程断片の基地駅が同じ場合はその基地駅を連結後の行程断片の基地駅に設定し、連結する２つの行程断片の基地駅が異なる場合は連結後の行程断片の開始地点と終了地点の各基地駅との間のコストを計算し、コストが小さくなる方を新たな基地駅に設定する処理をおこなうことを特徴とする請求項１に記載の乗務員運用計画作成システム。
【請求項３】
連結する２つの行程断片の基地駅が同じ場合であっても、連結後の行程断片の開始地点と終了地点が同じ基地駅になっているときは、その開始地点と終了地点となっている基地駅を連結後の行程断片の基地駅に設定する処理をおこなうことを特徴とする請求項２に記載の乗務員運用計画作成システム。
【請求項４】
前記データ記憶手段には乗務員の労働規定情報が記憶されており、
前記読込み手段によって前記データ記憶手段から読み込まれた前記労働規定情報に対して、前記仕業作成手段で作成された仕業が違反しているか否かをチェックする労働規定チェック手段を備えていることを特徴とする請求項１乃至３のいずれか一項に記載の乗務員運用計画作成システム。
【請求項５】
前記労働規定チェック手段によって違反がないとされた仕業間において、仕業の一部を切断して交換することで解の改善を図る解改善手段を備えたことを特徴とする請求項４に記載の乗務員運用計画作成システム。
【請求項６】
前記労働規定チェック手段によって違反がないとされた仕業を組み合わせて、各基地駅の乗務員の勤務順を示す交番を作成する交番作成手段を備えたことを特徴とする請求項４又は５に記載の乗務員運用計画作成システム。
【請求項７】
前記交番作成手段によって一旦、作成された交番を評価関数によって評価し、作成される交番の評価が高くなるような改善をおこなう解改善手段を備えたことを特徴とする請求項６に記載の乗務員運用計画作成システム。
【請求項１】
列車の運行に対して乗務員を割り当てる乗務員運用計画作成システムであって、
列車の運行に関する運行情報及び乗務員の勤務の開始地点及び終了地点を示す基地駅に関する基地駅情報が記憶されたデータ記憶手段からデータを読み込む読込み手段と、
前記読込み手段によって読み込まれた前記運行情報に対して前記基地駅とのコストを計算し、コストが最小になる基地駅を運行の仮の基地駅に設定する仮基地駅設定手段と、
仮の基地駅が設定された運行をその基地駅に勤務する前記乗務員の仕業を作成するための行程断片に設定する行程断片設定手段と、
所定の条件を満たす前記行程断片同士の連結による連結コストを計算する連結コスト算出手段と、
前記連結コストが最小となる行程断片同士を連結させて新たな行程断片を作成するとともにその基地駅を設定する行程断片連結手段と、
前記行程断片と必要に応じて付加される便乗とによって仕業を作成する仕業作成手段とを備えたことを特徴とする乗務員運用計画作成システム。
【請求項２】
前記行程断片連結手段において基地駅の設定をおこなうに際して、連結する２つの行程断片の基地駅が同じ場合はその基地駅を連結後の行程断片の基地駅に設定し、連結する２つの行程断片の基地駅が異なる場合は連結後の行程断片の開始地点と終了地点の各基地駅との間のコストを計算し、コストが小さくなる方を新たな基地駅に設定する処理をおこなうことを特徴とする請求項１に記載の乗務員運用計画作成システム。
【請求項３】
連結する２つの行程断片の基地駅が同じ場合であっても、連結後の行程断片の開始地点と終了地点が同じ基地駅になっているときは、その開始地点と終了地点となっている基地駅を連結後の行程断片の基地駅に設定する処理をおこなうことを特徴とする請求項２に記載の乗務員運用計画作成システム。
【請求項４】
前記データ記憶手段には乗務員の労働規定情報が記憶されており、
前記読込み手段によって前記データ記憶手段から読み込まれた前記労働規定情報に対して、前記仕業作成手段で作成された仕業が違反しているか否かをチェックする労働規定チェック手段を備えていることを特徴とする請求項１乃至３のいずれか一項に記載の乗務員運用計画作成システム。
【請求項５】
前記労働規定チェック手段によって違反がないとされた仕業間において、仕業の一部を切断して交換することで解の改善を図る解改善手段を備えたことを特徴とする請求項４に記載の乗務員運用計画作成システム。
【請求項６】
前記労働規定チェック手段によって違反がないとされた仕業を組み合わせて、各基地駅の乗務員の勤務順を示す交番を作成する交番作成手段を備えたことを特徴とする請求項４又は５に記載の乗務員運用計画作成システム。
【請求項７】
前記交番作成手段によって一旦、作成された交番を評価関数によって評価し、作成される交番の評価が高くなるような改善をおこなう解改善手段を備えたことを特徴とする請求項６に記載の乗務員運用計画作成システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１３−１１９７５（Ｐ２０１３−１１９７５Ａ）
【公開日】平成２５年１月１７日（２０１３．１．１７）
【国際特許分類】
【出願番号】特願２０１１−１４３２３３（Ｐ２０１１−１４３２３３）
【出願日】平成２３年６月２８日（２０１１．６．２８）
【出願人】（５９３２３０２０２）株式会社エヌ・ティ・ティ・データ・セキスイシステムズ (9)
【出願人】（０００２３０６９６）日本貨物鉄道株式会社 (14)
【Ｆターム（参考）】
【公開日】平成２５年１月１７日（２０１３．１．１７）
【国際特許分類】
【出願日】平成２３年６月２８日（２０１１．６．２８）
【出願人】（５９３２３０２０２）株式会社エヌ・ティ・ティ・データ・セキスイシステムズ (9)
【出願人】（０００２３０６９６）日本貨物鉄道株式会社 (14)
【Ｆターム（参考）】
[ Back to top ]