ーチ--乗務員と車両に対するスケジューリング
著者
今泉 淳
雑誌名
経営論集
号
72
ページ
43-55
発行年
2008-11
URL
http://id.nii.ac.jp/1060/00004577/
Creative Commons : 表示 - 非営利 - 改変禁止 http://creativecommons.org/licenses/by-nc-nd/3.0/deed.ja鉄道における資源の使用計画に対する最適化アプローチ
―乗務員と車両に対するスケジューリング―
今 泉 淳
１ はじめに ２ 鉄道における計画立案・スケジューリング問題の分類 2.1 計画の階層構造 2.2 これら計画立案の性格の違い 2.3 乗務員と車両に対するスケジューリング 2.4 その他の計画立案 ３ 乗務員のスケジューリング 3.1 基本計画における乗務員のスケジューリング 3.1.1 過去の経緯 3.1.2 分枝価格法の実装 3.2 運転整理における乗務員のスケジューリング 3.2.1 背景 3.2.2 CRP の定式化と解法 ４ 車両のスケジューリング 4.1 背景 4.2 通勤路線に対する車両運用計画 4.2.1 車両運用計画の難しさ 4.2.2 車両運用計画に対する二段階アプローチ ５ おわりに１ はじめに
運輸業では、保有する各種資源のマネジメントの善し悪しが経営効率に直結するため、これら資 源に対するより良い使用計画の立案が必要となる。筆者は、過去数年間にわたり国内の鉄道会社の 事例に基づく「資源の時間的割り当ての計画」であるスケジューリング問題、とりわけ乗務員スケ ジューリング問題に対する研究を行ってきた。その一方で、鉄道には最適化によるアプローチが問 題解決に繋がり易いスケジューリング問題が乗務員スケジューリング以外にも多数ある。 ところで、地球温暖化の影響を受けモーダルシフトが進む中、鉄道輸送の重要性が旅客・貨物を 問わずますます重要になるものと考えられ、これをうけて鉄道業における資源の効率的利用に対する要請はさらに増すものと予想される。 そこで本稿ではこのような背景のもとで、鉄道において重要な資源と考えられる乗務員や車両の スケジューリング問題に対して、筆者が属するグループの研究の進展やその成果に関する報告をし つつ、関係する数理モデルにも言及する。 具体的には、乗務員のスケジューリングに関しては従来から取り組んできた事前の計画系の問題 に加えて、列車遅延時における乗務員のスケジュールの修正の問題に対する取り組みについて言及 する。車両に関しては、事前の計画系の問題に対するアプローチならびにその結果の概要を報告す る。また、これらの周辺の数理モデルに関しても触れる。
２ 鉄道における計画立案・スケジューリング問題の分類
2.1 計画の階層構造 鉄道分野にはそこで使われる資源に対する数々の使用計画の立案の問題やスケジューリングの問 題が存在し[1][2][3]、最適化手法が活用できる可能性がある。その中でも乗務員や車両などのス ケジューリングはその段階に応じて分類が可能であり、富井[1]によれば、 • ダイヤ改正毎に作成される「基本計画」 • 季節に応じた基本計画の一部変更に対応して必要になる「実施計画」 • 列車遅延によりダイヤが乱れた場合に、元のダイヤを変更し、各種資源の使用計画を一時的 に修正する「運転整理」 の三段階に分類できる。 基本計画は、文字どおり運行のための基本となるものであり、基本計画の内容が日々繰り返され ることを原則として立案される。しかし実際には、たとえば季節によって需要が多くなる場合に臨 時に列車を運転することなどが行われるが、その際には基本計画の一部を変更することになり、こ れが実施計画となる。 これに対して運転整理は、事故などによって列車の遅延が生じた場合、一時的なダイヤの変更を 行い、この変更されたダイヤに対応するように各種資源に対する基本計画や実施計画の一部を変更 する作業のことを指す。 実務における計画立案は問題の範囲の限定が難しく[1][3]、問題の切り分け方によっては、ある 計画立案の結果に応じて他の計画を変更しなければならないなどのこともあり得る。しかし、その ようなことを含めて数理的に扱うには技術的な意味での進展度がまだ不十分であり、本稿ではある 計画立案を独立した数理的な問題として扱う立場から論じる。 もちろん、ダイヤ策定においてはより高い視点の計画が存在することはいうまでもない。2.2 これら計画立案の性格の違い これら三つは、単に計画の段階が異なるのみならず、それを立案する上での周囲の状況や求めら れることに違いがある。 すなわち、基本計画は原則的に繰り返し使われる計画であり、事前に定まっているダイヤに対し て時間的な余裕をもって立案できる。実施計画は、日々の運行内容の基本計画からの違いに対応し て必要となる計画であるが、その大部分が基本計画に基づいており、また基本計画からの変更内容 も前もって予定されていることも多く、これも計画立案には時間的な余裕があると考えられる。 またこれらの計画では、可能なかぎり効率的な資源の使用を実現することが第一目標となる。す なわち、乗務員や車両の数が限られているなかで、できる限り無駄なくこれら資源を使用する計画 を立案したい。したがって、計画立案に時間がかかってもできる限り良い計画が要望されると考え られる。これは、たとえば基本計画が原則として次のダイヤ改正までに使われる計画であることか らも当然のことといえよう。 しかし運転整理は、ダイヤが乱れた場合に行われる作業であり、そこで立てられた資源の使用計 画は一度きりしか使われない性格を持ち、また修正されたダイヤ（もちろん本来のダイヤとは違 う）が決まったらばできる限り短時間で各種資源の使用計画を立てる（修正する）必要がある。す なわち、計画立案の制限時間に関しては、運転整理は他のふたつに比べて遥かに厳しい状況にある。 もちろん、資源が有限である制約はここでも考慮しなければならないが、基本計画に比べて運転整 理では計画立案にかかる時間が計画の質に比べて重視されるといえる。 これらのことは、解法やアルゴリズムの設計や開発の上でのある種の指針を与える。すなわち、 解の質を重視するのか計算時間を重視するかによって、どのような枠組を用いるかの戦略に影響を 与えるからである。 2.3 乗務員と車両に対するスケジューリング 乗務員と車両の両者は、表面上類似する点が多い。たとえば、基本計画では、１日（場合によっ ては２日）単位のスケジュールと、それらを並べた結果の数週間程度の長さのスケジュールを考え る意味での問題の構造的な類似点がある[4]。 しかし、乗務員と車両それぞれに課される使用条件の細かい違いが数理モデルやアプローチ全体 に影響を与え、計画立案のための共通な枠組のようなものは今のところ存在しない。よって、現状 では個別に問題解決を行っているのが実際のところである。
2.4 その他の計画立案 前節では乗務員と車両のみに言及していたが、資源の使用計画という意味では、たとえば駅構内 や車両基地内における車両の移動スケジュールである「構内作業計画」も必要となる。 具体的には、車両運用にしたがって駅で車両の折り返しなどが起こる際、その駅に到着したとき と出発するときで別のホームを使う場合には、車両を移動させる作業を必要とする。これ以外にも、 車両の切り離しや連結、点検や清掃作業など構内で発生する各種作業のために車両を特定の場所に 移動させる必要がある場合がある。しかし、駅構内や車両基地内の車両を留めておく場所（留置 線）の本数や長さは有限であるため前もってその使用計画を車両の移動スケジュールとともに立て ておく必要があり、これを構内作業計画と呼ぶ。 この構内作業計画は列車ダイヤや車両運用に対応する形で駅ごとに基本計画として作られるが、 実施計画が必要であることや、運転整理が発生すれば当然それに引き起こされる形で計画の修正が 必要となるのは、乗務員や車両の場合と同様である。
３ 乗務員のスケジューリング
本節では、基本計画と運転整理における乗務員のスケジューリングに関して述べる。 3.1 基本計画における乗務員のスケジューリング 基本計画では、すでに述べた通り答を求める時間よりも得られる答の質に重点がある。もちろん、 計算時間が短いほうがより望ましいものの、その計画が日々の運用に使われることを考えると、多 少計算時間がかかっても得られる答の品質が良いことが望まれると考えて良い。 3.1.1 過去の経緯 基 本 計 画 に お け る 乗 務 員 の ス ケ ジ ュ ー リ ン グ で あ る 「 乗 務 員 ス ケ ジ ュ ー リ ン グ 」（Crew Scheduling Problem, 以下 CSP）は、数理モデルとしては集合被覆問題もしくは集合分割問題、あ るいはその派生形での定式化が一般的である。この場合、定式化における行が乗務員の仕事の最小 単位である「乗務」に、列がある乗務員が基地から出発しその基地に戻るまでの行程である「行 路」に相当する。 それに対するアプローチとしては、上記の集合被覆問題などの定式化を前提に、事前に列（行 路）を用意しておく「事前列挙型」と、必要に応じて列を作り出す「列生成型」のふたつに分類す ることができる。■事前列挙型 事前列挙型に関して筆者が属するグループは、ラグランジュ緩和をベースにした解 法の評価を既に行い[5][6]、実装の容易さや実行速度の面から有望であることを確認したが、これ らが近似解法であることや全ての行路を対象にできないがゆえの弱味が残る。 ■列生成型 一方で列生成型に関しては、近似解法としての位置づけになる列生成ヒューリス ティックとして、植田ら[7]や Imaizumi et al.[8]は集合被覆問題として定式化してヒューリス ティック解法の基本性能を確認し、加藤ら[9]は集合被覆問題の拡張型として定式化し便乗を抑制 する対策を提示した。これらはいずれも列生成型ではあるものの事前列挙形との折衷案的方法とも 解釈でき、また解法の性格上、本来の意味での最適解を算出する保証はない。しかし、実装は厳密 解法の分枝価格法に比べて遥かに容易であり、下界値による実行可能解の評価も可能である。また、 実用上十分な精度の実行可能解を算出できることも数値実験から分かっている。なお、この場合の 列生成子問題は、ネットワークにおける資源制約つきの最短路問題になる。 3.1.2 分枝価格法の実装 列生成型の延長上に残るのは厳密解法としての分枝価格法であり、これに対して、CSPの集合被 覆問題としての定式化に対する分枝価格法の実装を試みた[10]。 分枝価格法は、分枝限定法に列生成のメカニズムを組み込んだ解法である。具体的には、「列が 一部しかない問題の連続緩和問題を、必要な列を生成しながら解く」ものであり、これを分枝限定 法の分枝計算に組み込んだのが分枝価格法である。分枝限定法に関しては強力な商用パッケージが 存在するが、分枝価格法は基本的には問題に依存した実装を必要とする。 分枝価格法の解法上のポイントは、i）分枝の方法、ii）分枝に伴う主問題や列生成子問題の修 正などにある。特に後者は、分枝した内容に応じてこれらの修正をする必要があり、ここが実装に おいて必要とされる部分である。そこで、i）については Ryan and Foster[11]に基づく「follow-on 分枝」を採用し、ii）は Barnhart et al.[12]のやり方を参考にしながら独自の方法で修正をしてい る。その実装による数値実験の結果の一部を表１に示す。 表１内の、「初期列数」は「LP 最適値」（下界値）を算出するまでに生成された列数、「分枝限定 法」は列生成法で LP 最適値を算出するまでに生成された列のみからなる問題に対する10,000秒時 表１ CSP に対する分枝価格法と分枝限定法の比較 乗務数 488 501 503 526 初期列数 2622 3121 3191 3219 LP 最適値 114.3 116.7 119.9 123.4 分枝限定法 119 120 126 130 分枝価格法 117 119 124 128
点での暫定値（XPRESS MP を使用）、「分枝価格法」は500,000秒時点での暫定値である（C++で実 装を行い、LP 最適化は CPLEX で行っている）。なお、いずれも Pentium 4 3.2GHz、メモリ2GB のパーソナルコンピュータ上での結果である。 アルゴリズムの上では分枝価格法は最適解が算出できるはずだが、実験の範囲内では最適解を得 るには至っておらず、計算時間に関する改善の余地が大きい。これは、実装上の問題もさることな がら、計算の高速化に対する各種の工夫の積み重ねが必要であると考えられる。 3.2 運転整理における乗務員のスケジューリング 3.2.1 背景 ダイヤが乱れ乗務員が所定のスケジュールを守れないときに乗務員のスケジュールを修正する問 題（Crew Recovery Problem, 以下 CRP）は、航空を中心に海外では盛んに研究が行われている （例えば文献[13]）。 しかし、鉄道分野においてはベテランの経験と勘に頼って手作業で乗務員のスケジュールを修正 しているのが現状であり、ベテランに頼ることなく短時間でスケジュールの修正が可能になること が望まれる。 CRP が緊急時のスケジューリングであることをふまえると、もちろん解の最適性よりも短時間 で実用に耐える実行可能スケジュールを算出することが重要であることはすでに述べたとおりであ る。これに加えて、「何が良いスケジュールであるか」の定義が必ずしも明確ではなく、また存在 する要因を全てモデルに取り込むことは事実上極めて困難な状況がある。さらに、修正が及ぶ乗務 員の範囲や修正による変更内容などが得られたスケジュールの採否に影響を与えるため、一つのス ケジュールのみを算出するのではなく、複数の異なるスケジュールを生成し、それらから最終的に 人間が判断を行って選択せざるを得ない部分もある。 すなわち、スケジュールの善し悪しを測るなんらかの指標のもとでモデル化および最適化を行い、 複数のスケジュールを生成してそれらから最終的に意思決定者が選択できるような仕組みを提供す ることが望ましいと考えられる。このことを踏まえて構築した解法を次節で示す。 3.2.2 CRP の定式化と解法 ■ 概要 上記のようなことを踏まるとともに理論的な扱いの試みとして、i）列生成法に基づき、 ii）修正の範囲を徐々に拡大させていく、という方針で、最終的に全体として最適あるいは最適に 近い解を得つつ、そのプロセスを通じ複数の解を提示する方法を試みた[14]。 定式化は、行を乗務に、列を行路に対応させた集合被覆問題の変形である。なお、所定の乗務員
だけでは全列車を被覆できない場合もあるのでその際は予備乗務員を使っても良いが、その場合の コストは非常に高いものとする。また、修正された行路のコストは、その乗務員の所定行路の退勤 時刻に対する超過量（時間）とする他、各種の条件は、緊急時であることからそれを厳密に守るこ とが難しいため、乗り継ぎ可能条件のみ考慮している。このことで、列生成子問題は単純な最短路 問題として解くことができる。 解法全体は反復的な手順から成り、ある反復時点での「対象の乗務員の集合」（初期状態では、 遅延の影響を受けた乗務員群）に対して、それで定まる問題の線形緩和問題を列生成法で修正行路 （列）を生成しながら解く。LP 最適値が求まり下界値が得られたら、その時点までに生成された 列に基づき定まる整数計画問題を解いて実行可能スケジュールを得る。そして、それまで対象外 だった乗務員の集合から新たな乗務員を一定の手順に基づき選び、それを「対象の乗務員の集合」 に加えて新たな集合が定まったらば、再度上記のプロセスを繰り返す。この一連の手順は、対象外 の乗務員の集合が空になるまで繰り返される。 ■数値実験 数値実験は、乗務数872、行路数198の実在する線区のデータを用い、以下のふたつの シナリオに基づいて実験を行った。 シナリオ１ ６列車、全27乗務が遅延の影響を受け、最大で2時間の遅れが生じた シナリオ２ ４列車、全12乗務が遅延の影響を受け、５乗務が運休になり、最大で６時間の 遅れが生じた 実装は C++で行い、ある時点までに生成された列からなる整数計画問題やその線形緩和問題は CPLEX で解いている。また、数値実験は Pentium 4 3.2GHz、メモリ2GB のパーソナルコン ピュータ上で行った。そして、表２にシナリオ１の、表３にシナリオ２の結果を示す。なお、「変 更行路数」は変更された所定行路の数であり、「生成行路数」はその時点までに生成された行路の 総計である。 表２ CRP：シナリオ1に対する結果 反復回数 1 2 23 対象の乗務員数 20 21 42 変更行路数 17 19 35 生成行路数 579 628 772 超過時間（分） 432 9 0 予備乗務員数 0 0 0 計算時間（秒） 10.5 11.7 21.3
表３ CRP：シナリオ2に対する結果 反復回数 1 2 30 57 対象の乗務員数 10 11 39 66 変更行路数 9 10 31 48 生成行路数 332 372 529 698 超過時間（分） 667 1126 687 191 予備乗務員数 1 0 0 0 計算時間（秒） 4.9 6.2 19.3 32.8 シナリオ１、シナリオ２とも、対象の乗務員の数を増加させることで、所定退勤時刻に対する超 過時間が減少し、また結果として複数の異なるスケジュールを算出することにも成功している。ま た、シナリオ２の反復回数１では予備乗務員を使用するスケジュールが算出されているが、反復回 数２以降の結果からもわかるように、遅延の影響を受けなかった乗務員の行路を修正することで所 定の乗務員だけで全乗務を遂行できるスケジュールが得られた。なお、シナリオ２における反復回 数２の所定退勤時刻に対する超過時間が反復回数１に比べて増加しているのは、予備乗務員が遂行 した乗務を他の所定の乗務員が行ったことが原因である。 実務的には変更する行路数を低く抑えたいが、本解法で最初から全乗務員を対象にするよりも、 徐々に乗務員数を多くしたほうが、変更する行路数を抑制できることも確認されている。
４ 車両のスケジューリング
4.1 背景 車両のスケジューリングも、基本計画系の問題（通常「車両運用計画」と称する）と運転整理系 の問題に分類することができる。前者は、ダイヤ上の各列車に対する割り当て可能な車両形式が所 与の前提下で、なるべく効率的な車両運用を行うことが目的で、乗務員のそれと類似する。後者は、 すでに触れた乗務員のそれと同様に類似し、ダイヤ乱れ時における車両割り当ての一時的な変更を 行うものである。前者の計画系の問題に対する海外の研究としては Alfieri et al.[15]の車両循環モデルや Cordeau et al.[16][17]などの研究がある他、日本国内の研究として趙ら[18]や福村ら[19]などがある。し かし、車両の運用ポリシーが国によって違うなどの事情もあり、諸外国の類似の問題に対する研究 成果を単純に日本のケースに適用することはできない。 たとえば、「検査」は一定周期で行う必要がある点検作業であり、これは諸外国の鉄道にももち ろん同様の概念がある。しかし、この検査を車両運用計画にどのように取り込むかに相違があり、 そのため Alfieri et al.[15]のモデルでは検査は考慮していない。よって、これら外国の研究成果は 日本の場合の基本計画の立案に適用できないが、実際の車両運用を決めるのではなくもう少し高い
レベルから車両の循環効率などを分析する上で活用できるのではないかと考えられる。 本稿では、基本計画系の問題に対する筆者の属するグループの成果の一部を紹介する。 4.2 通勤路線に対する車両運用計画 4.2.1 車両運用計画の難しさ 車両運用計画問題は、ダイヤが所与の下で、所有する車両の列車に対する効率的な割り当てを見 つける問題であり、検査を考えなければ巡回セールスマン問題に帰着できる。すなわち、点を列車 として、接続可能な列車間に枝を張った上で、枝の始点に対応する列車の到着時刻と枝の終点に対 応する列車の出発時刻の差（一般には停車・待機時間）を枝の重みとして与えれば良い。しかし実 際には、 • 検査を考慮する必要がある • 回送列車を設定する必要があるかもしれない といった問題がある。 後者は、ダイヤには営業列車しか与えられていない段階で問題を解く必要があるためであるが、 これについては、可能な回送列車とその所要時間を仮に与えれば取りあえずの計画立案（計算）を 行えるので、それほど深刻ではない。しかし、前者の検査に関しては、これが可能な場所において 一定の周期（おおむね数日間隔）で行う必要があり、このことが単純な巡回セールスマン問題とし てモデル化することを妨げる要因である。 また、乗務員スケジューリングでは１日ないし２日にまたがる行路によって全乗務が被覆される ような計画を目指していたが、実際にはそれら行路をどのように巡るか（「交番」と称する）まで を決める必要があり（これも文献[20]のような研究がある）、乗務員の場合は前者と後者それぞれ の段階が個別に研究の対象となっている。しかし車両運用計画問題では、各車両編成の１日単位の スケジュール（仕業）と、それらを巡回するスケジュール（交番）の両者を同時に決定する必要が ある。 4.2.2 車両運用計画に対する二段階アプローチ 「巡回路を作る」という発想に基づくのがすでに述べた趙ら[18]や福村ら[19]だが、これに対し て、筆者の属するグループは通勤路線を対象にその問題の性質に着目した分割アプローチを試みた [21]。これは、乗務員のスケジューリングでは、上述のように１日ないし２日の行路群を求めてか らそれらの巡回内容を決める二段階のアプローチが採用されているのに倣うと同時に、検査を行う 場所と時間ならびにダイヤの特性に着目することで決定変数を削減している点に特徴がある。
■基本的な考え方 通勤路線では朝のピーク時間帯にもっとも多くの車両を必要とし、昼間に閑散 の時間帯を迎え、夕方に向かってダイヤ上の列車密度が再び高くなる。したがって、昼間は車両運 用上の余裕が比較的あることになる。 一方、通勤路線の場合における検査可能な場所は、その線区上にひとつないしふたつ程度ある車 両基地であることが通例で、検査可能な時間帯もおおむね朝のラッシュアワーが終った時間から夕 方までに設定されている。また、各基地で同時に検査可能な車両数はさほど多くなく、その意味で 基地側の資源制約は小さくない。 すなわち、検査の場所や時間に関しての自由度は元々さほど大きくなく、各基地で検査を行う時 間（スケジュール）を所与とすることにはさほど大きな不自然さはない。また、所要の車両数は列 車が最大数運行されている時間帯のそれを検出すればおおむね判明し、検査周期の関係からその日 に行うべき車両の検査数もあらかじめ分かる。 そこで本アプローチでは、以下のように二段階にわたって問題を解くことを考える。 フェーズ１: 仕業を求める まず以下のようなネットワークを考える。 • 列車を点とし、接続可能な列車間にはそれらの点の間に枝を張る • 検査可能な場所における検査スケジュールを所与とし、その日に必要な検査数分だけのスケ ジュール（時間帯）を設定し、これも上記と同様の点として扱う このネットワーク上で、所要の車両数に一致する本数の、ネットワークの始点から終点（それぞれ が、一日の運用である仕業の開始と終了を表す）までのパスで、始点と終点以外の全ノードを一度 だけ被覆する部分グラフを見つける問題（輸送問題）を解く。 フェーズ２: 交番を求める フェーズ１によって仕業が見つかったらば、回送を最小にするように それらを繋ぎそれらを一巡する交番を求める整数計画問題を解く。そのとき、検査を含む仕業とそ うでない仕業を、検査周期を満足するように並べることが制約条件となる。 ■数値実験 数値実験は、実際の通勤路線の時刻表データに基づく他、各種条件は表４のように与 え、結果としての各線区のフェーズ１とフェーズ２の回送時間と計算時間（最適解の場合は終了時 間、そうでない場合はその解が見つかった時間）も同時に表４に示した。各フェーズの計算時間の 上限は１時間とし、表４の回送距離合計はフェーズ１とフェーズ２の回送を足し合わせた数値であ り運用計画全体の回送距離を表す。 表４から分かるように、フェーズ１ではすべての線区において数秒で最適値を得ることができた。 フェーズ１で得られた仕業群は線区４以外ではすべての基地・駅において仕業開始数と仕業終了数
表 4 車両運用計画の問題例と結果 線区 1 2 3 4 列車数 429 506 640 471 車両形式数 1 2 1 1 基地数 1 2 1 2 検査周期（日） 5 5 5 3 回送距離 300.7* 24.0* 67.8* 95.4* フェーズ1 計算時間 1.81 3.69 5.59 2.59 回送距離 0* 0* 0* 42.8 フェーズ2 計算時間 93.0 487.0 29.8 315.0 回送距離合計（km） 300.7 24.0 67.8 138.2 計算時間の単位は秒、*は最適値 が一致しているために、交番作成の段階では回送なしで運用計画を策定できる可能性がある。しか し、線区４ではそれらが一致していないために、交番作成の段階でも回送が発生する。 フェーズ１では留置場所などの条件を満たすために必然的に発生する回送を最小化し、また最適 解が求まっているので、フェーズ２で最適値０を得ることができた三つの線区に関しては回送距離 が最小の運用計画を策定できたことになる。一方、フェーズ２で最適値を得ることができなかった 線区４では交番作成の段階で多くの回送が発生していることから、フェーズ１で生成された仕業群 では回送距離が少ない運用計画を策定することができない。また、線区４は他の線区よりも検査周 期が短いため、仕業を並べるときの自由度が小さいというインスタンスの性質が、このような結果 につながった可能性もある。 ■考察 冒頭で述べたように通勤路線は、ピーク時間帯と昼間帯とで列車密度が異なり、一日内で 比較的短い距離を何度も往復し、検査可能な基地もさほど広く分散してはおらずまた数も多くない ため、このようなアプローチによって十分満足できる答が得られたと考えられる。その一方、長距 離列車に充当される車両の場合や検査可能な場所が地理的に分散しまた多数存在する場合には本ア プローチの適用は難しいと考えられ、そのようなケースに対する解法の開発が次の課題となろう。
５ おわりに
本稿では、鉄道における各種資源の使用計画問題すなわちスケジューリング問題に対する筆者の 属するグループの試みを紹介するとともに、それらに関連する研究やモデルにも言及した。 鉄道における最適化の応用は近年盛んになりつつあるが、それでもなお未解決の問題も多い。ま た、実務的な要請に応えるためには富井[1]が述べるような課題も克服する必要がある。その前提 として、既存の問題に対しても常により良いアプローチを模索することが必要だと考える。また、基本計画は計算時間に関して運転整理に比べて余裕が多少あるとはいえ、今泉[4]が指摘するよう な What-if 分析のような用い方も考えられるため計算時間の短縮も当然のことながら目指すべきで あろう。またこれらと同時に、富井[3]が述べるような経営的視点に立った戦略的計画に寄与し得 るモデルの提案も次に控える重要な研究テーマである。 いずれにせよ、このような研究の積み重ねが実務における計画立案や意思決定に対する寄与につ ながることを筆者は願ってやまない。 参考文献 [1] 富井規雄. 鉄道スケジューリングアルゴリズム–現状と今後の課題–. オペレーションズ・リサーチ, Vol.49, No.1, pp.33–39, 2004. [2] （財）鉄道総合技術研究所運転システム研究室. 鉄道のスケジューリングアルゴリズム. NTS, 2005. [3] 富井規雄. 鉄道のスケジューリング問題:難しさと面白さ. オペレーションズ・リサーチ, Vol.53, No.8, pp.427-432, 2008. [4] 今泉淳. 鉄道の運用計画問題に対する整数計画法によるアプローチ. オペレーションズ・リサーチ, Vol.53, No.8, pp.439-445, 2008. [5] 今泉淳, 鷲見亮, 斎藤秀和, 森戸晋, 富井規雄, 福村直登. 鉄道乗務員運用計画へのバックトラック法 による行路候補列挙と集合被覆問題の近似解法. 統計数理研究所共同研究リポート168 最適化:モデリン グとアルゴリズム17,pp.172-179.統計数理研究所,2004. [6] 三浦礼, 福村直登, 森戸晋, 今泉淳. 乗務員運用計画の集合被覆問題に対する Wedelin 解法の適用. 日 本オペレーションズ・リサーチ学会 2005年春季研究発表会 アブストラクト集,2005. [7] 植田達広, 森戸晋, 今泉淳, 福村直登. 乗務員運用計画問題の列生成子問題に対する Pull 型ラベリング 解法と性能評価. 日本オペレーションズ・リサーチ学会 2005年秋季研究発表会 アブストラクト集, 2005.
[8] J. Imaizumi, H. Arai, K. Ogawa, S. Morito and N. Fukumura. Column generation approaches to scheduling problems in logistics. International Journal of Logistics and SCM Systems, Vol.1, No.1, pp.7–13, 2006.
[9] 加藤怜, 植田達広, 森戸晋, 福村直登. 乗務員運用計画問題に対する便乗削減の定式化と解法. オペ レーションズ・リサーチ学会 2006年春季研究発表会 アブストラクト集, 2006.
[10] 今泉淳, 福村直登, 森戸晋. 鉄道におけるスケジューリング問題に対する最適化アプローチ. スケ ジューリング・シンポジウム2007 講演論文集,2007.スケジューリング学会.
[11] D. Ryan and B. A. Foster. An integer programming approach to scheduling. In A.Wren, editor, Computer Scheduling
of Public Transport Urban Passenger Vehicle and Crew Scheduling, pp.269-280. North-Holland, 1981.
[12] C. Barnhart, E. L. Johnson, G. L. Nemhauser and P. H. Vance. Crew scheduling. In R.W. Hall, editor, Handbook of
Transportation Science, pp.493-521. Kluwer, 1999.
[13] G. Wei, G. Yu and M. Song. Optimization model and algorithm for crew management during airline irregular operations. Journal of Combinatorial Optimization, Vol.1, pp.305–321, 1997.
ションズ・リサーチ学会 2007年春季研究発表会 アブストラクト集, 2007.
[15] A. Alfieri, R. Groot, L. Kroon and A. Schrijver. Efficient circulation of railway rolling stock. Transportation Science, Vol.40, No.3, pp.378-391, 2006.
[16] J.-F. Cordeau, F. Soumis and J. Desrosiers. A Benders decomposition approach for the locomotive and car assignment problem. Trasportation Science, Vol.34, No.2, pp.133-149, 2000.
[17] J.-F. Cordeau, F. Soumis and J. Desrosiers. Simultaneous assignment of locomotives and cars to passenger trains.
Operations Research, Vol.49, No.4, pp.531-548, 2001.
[18] 趙鵬, 富井規雄, 福村直登, 坂口隆. 確率的局所探索に基づく鉄道車両運用計画作成アルゴリズム. 電 気学会 交通・電気鉄道研究会, TER-01-54, 2001.
[19] 福村直登, 坂口隆, 富井規雄, 中村達也, 西森進矢, 登坂安彦. 鉄道における車両運用計画作成問題. 日本オペレーションズ・リサーチ学会 2004年春季研究発表会 アブストラクト集, 2004.
[20] A. Caprara, P. Toth, D. Vigo and M. Fischetti. Modeling and solving the crew rostering problem. Operations Research, Vol.46, No.6, pp.820-830, 1998.
[21] 山岸雄樹, 今泉淳, 森戸晋, 福村直登. 数理計画による鉄道車両運用計画の策定. 日本オペレーション ズ・リサーチ学会 2007年春季研究発表会 アブストラクト集, 2007.
