乗務員運用計画の集合被覆問題に対するWedelin解法の適用

日本オペレーションス。リサーチ学会 2005年春季研究発表会

瑠一匠−2

乗務最運用計画⑳集合被覆問題打≡謝する閣毎舶且畳m解法の適用

申請中 早稲田大学

01205890（財）鉄道総合技術研究所

01603200 早稲田大学

01012600 東洋大学

三浦礼 MIURARei

福相直登 FUKUMURANaoto

森戸晋

MORITOSnsⅦmu

今泉淳 IMAIZUMIJun

且 研究の背景と悶的

欧米ではパイロットや運転士のクルースケジューリ ングに関する研究ならびに応用が盛んに進められている （たとえば、BarnhartandCohen［3］参照）のに対して、 国内では関連する手法の研究。適用は限られている。 クルースケジューリング問題は、通常、集合被額問 題（SCP）または集合分割問題（SPP）に定式化され、解 法は、（1）最適解法／近似解法、（2）列をあらかじめ列挙 しておく事前列挙／必要に応じて列を生成しながら問題 を解く列生成、の2つの観点から分類できる。真の意味 での最適解法は現在のところ列生成に基づく分枝価格法 に限られるのに対して、最適解を保証しない解法として、 （a）事前に列挙された列から構成される大規模SCp／SPP に対する最適解法の適用、（b）ラグランジュ緩和に基づく 解法、（c）メタ解法、などがある。 ここでは、短時間でよい近似解を得るという観点か ら、SCP定式化に対するラグランジュ緩和法の適用を考 える。ラグランジュ緩和アプローチには、C叩raraら〔4】 の解法とWedelinの解法［1］がある。本研究では後者を 放り上げ、主に事前列挙型問題に対して、実際の国内鉄 道データをもとにWedelin解法の性能を評価するととも に、列生成型への展開について検討する。

男 衆務最運用計画問題

2。且 乗務D行路の定義と問題の提示

ダイヤは所与という仮定の下で、ダイヤ上の列車を束 換可能駅で分割したものを乗務、乗務員の且回の勤務を 構成する一連の乗務の集合を行路と呼ぶ。スケジュール の評価 はダイヤを運行するのに必要な乗務員の総勤務日 数とし、日勤（夜勤）行路のコストを1（2）とする。 このとき、乗務員運用計画問題とは、すべての乗務を 被存する、総勤務日数最小の行路の集合を求める問題で ある。行路には、勤務時間。乗務時間等に関する多数の 制約が存在し（詳細省略）、これらの条件をすべて満足す る行路案が事前に列挙されているものとする。また、こ こでは、2人以上の乗務員が同じ乗務に携わる便乗を許 すものとする。

2。2 集合被覆問題（SCp）による定式化

（SCP） mh z＝∑cj諾ノ

ブ∈Ⅳ （1）

s・t・∑α硝≧1，∀i∈〟（2）

j∈」Ⅳ 諾ブ∈（0，1）， ∀j∈Ⅳ （3）

3「汎毎de且鼠m解法

3こ孔 基本的考え方 ラグランジュ乗数汀＝（汀1，…，汀l叫）を用い制約（2） を緩和して、以下のラグランジュ双対問題を考える。 讐Ⅹエ（汀） ．■ノ C ． ﹁ノ．ニーJ n ． m 二 ︶ 汀 ︵ rム

∑岬擁＋∑訂‘

i∈Jば i∈〟 S・t・（3），訂i≧0， ∀壷∈〟 Wede血解法の特徴はラグランジュ緩和を下界値算出 の手段とは考えずに、上界催すなわち実行可能解算出の 手段と考えるところにあり、直接、ラグランジュ双対問 題の最適化を目指す訳ではない。乗数の更新は、劣勾配 法を用いず、訂の特定の要素汀iに関する1次元探索を、 各壷∈Ⅳに対して繰り返すことにより更新するととも に、実行可能解が出やすいように被約費用に修正を加え る（3・2参照）。 ここで重要な点は、ま番目の制約に対応する乗数汀‘を 汀i＋9と更新した緩和問題の解が、元の問題のよ番目の 制約を満たす場合にエ（汀＋9ei）が9に関して最大値をと る（eiは第i要素を1とする単位ベクト′レ）、すなわち、打 の1次元探索の最大値を与える9が盲番目の制約を満た す9の値と一致する点である（証明略）。以上をもとに、 ラグランジュ乗数を以下の手順で更新する。 S呵P皿行iを含む列を被約費用の小さい順に並べる S軸2被約費用の小さい順にγ【1】，γ【2】とする S七ep39＝（γ【1】＋γ【2】）／2を計算する S七ep4汀iを叫＋9に更新する Wedebm解法の問題点は、最適性の判定できない点、 被約費用を修正しているために元の解法のままでは一般 に−卜界値を提供しない点、事前に最適なパラメータの値 を見つけられない点が挙げられる。

3。2 被約費用の修正と解法の流れ

次のラグランジュ乗数れ＋1を更新した際に、それに よる緩和問題の解が元の問題の五番目の制約式を満たさ ない可能性があるため、以下の可変パラメータ勒を用 いることで被約費用を修正する。 乗務の集合 行路案の集合 行路ブ∈Ⅳのコスト 乗務j∈〟が行路ブに含まれるとき1，さもな くば0 行路ブを選択するとき1，さもなくば0 Jば Ⅳ Cメ 叫メ り ー96 − © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

づ＝勺−∑昭（メ）（拘＋汀‘）

使用する鉄道データは、被約費用の値の差が比較的小

さいためpij＝t／hに変更することでWedelirL解法を適 用した【2］。終了判定基準は、上界値が一定時間更新され ない、もしくは反復回数￡がパラメータんを上回った時 点で終了とする。 Stepl壱：＝1 Step2ラグランジュ緩和問題を解き（γ；が負なら訂j＝ 1、正ならば諾j＝0）、汀i：＝打巨十9、鞘＝±ま／んと する Step3解が制約を満たしていたら、上界値を算出 Step4i：＝i＋1、i≦IMlならばStep2に戻る Step5終了判定基準を満たせば終了、さもなくばStep lに戻る（1反復終了）

4 計算実験による性能評価

4．1 実験のねらい

実験は、4種類の実在線区のデータ（乗務数488，501， 503，526）を用いる。実験目的は以下の通り：

1．／ミラメータ値により解の精度・計算時間に影響を与

えることが予想されるため、鉄道データにおけるパ ラメータ分析、Wedehn解法の特徴を調べる 2．分枝限定法の結果と比較することでWedelin解法の 性能を評価する

（使用マシン：Pentium43．20dHz2GBRAM）

4．2 Ⅵ毎delin解法の実験結果

4．2．1 パラメータ感度分析 パラメータ九を変化させたときの最良値・計算時間 の変化を図1に示す。右下がりの変化をしているのが最 良値であり、右上がりの変化は計算時間である。 表1：行路数による最適パラメータ値の変化 行路数 パラメータん 最良値 計算時間 1611 100000 142 59 106830 5000000 141 281 795607 10000 137 890 4．2．2 分枝限定法との比較 表2：Wedekn解法と分枝限定法の性能比較 表2は、列数10フブ程度の問題に対する分枝限定法（商 用パッケージ）とWedelin解法の計算時間を比較してい る。Wedelin解法は、分枝限定法の高々1割程度の時間 で「最適値」を算出している。これら4データではすべ て最適解が算出されていることに注目したい。これは、 Wedelin解法が分枝限定法の分枝操作の代わりに、被約 費用を修正することで状況に応じた最適な列を選択して いるためと考えられる。また、表1の最後の行のように、 分枝限定法で解を出せなかった問題においても、目的関 数値をさらに改善する解が得られている。 4．2．3 Ⅵ毎deじn解法による解の更新状況 表3はWedelin解法の解の更新状況をまとめている。 改善率（％）＝（初期値一最良値）／最良値×100 表3：Wedelin解法の暫定解の変化（ん＝50000） 488 3 1．6 5187 5189 CG 501 3 1．5 4861 4865 503 2 2．2 5617 5617 526 3 2．9 5649 5651 改善率に関しては、バックトラック（BT）・列生成（CG） ともに低く、初期解算出時点で良い値が得られている。CG では初期解と最良解との差がほとんど見られず、初期解 算出後に数秒の間に暫定解が複数算出されている。

5 結論と今後の課題

本研究では、実際の国内鉄道データをもとにWedelin 解法を適用し、より大規模な問題においても短時間で精 度の良い実行可能解算出に成功した上 また、今後の課題 として列生成型Wedelin解法への展開を検討する。

参考文献

［1］D・Wedelin，AnnalsofOR，Vol．57，Pp．283−301，1995． ［2】A．J．Mason，AnnalsofOR，Vol．108，Pp．239−276，2001． ［3］C．Barnh揖tandM．Colm，M＆SO〟，Vol．6，pP．3− 22，2004． ［4】A．Caprara，M．Fischetti，and P．Toth，Opns．Res．， Vbl．47，pp．730−743，1999． 100 500 1000 500010000 ∼000（〉100000 5α）m00 パラメータIl 図1：最良値・計算時間の変化 一般にパラメータんを大きく設定することで良い解 が得られるが、一方で計算時間がかかる。〔かし、九を 大きくしすぎると逆に解が悪化する可能性もある。なお、 今回の実験では4データともバックトラック法で生成し た行路（10万弱）を使用した（表1，2も同様）。 また、パラメータんの最適な値は行路数（列数）一によっ ても変化する（表1参照）。行路数が増えるとんの最適な 値が低下する傾向があるのは興味深く、行路数が膨大で も適正なパラメータ値を設定すれば比較的短時間で最良 値算出が可能である∩ −97− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.