表題番号：2013A-6268 日付：2014/04/11
研究課題大規模乗務員運用計画問題に対する制約統合を用いた列生成法
研究者所属（当時） 資格 氏名
（代表者） 理工学術院 教授 森戸　晋
研究成果概要
　筆者の研究室では，10年ほど前から，鉄道乗務員運用計画作成問題（Crew Scheduling Problem, 以下CSP）の研究を進めてきた。CSPとは，ダイヤが定められた特定の線区を対象に，すべての列車を乗務員が乗換可能な駅で分割した最小単位である乗務に分解した上で，すべての乗務が少なくともいずれかの乗務員で運行できるように，乗務を乗務員に割り当て，「行路」と呼ばれる乗務員の一回の勤務スケジュールを作成する問題である。行路には満たすべき様々かつ一部複雑な制約があり，行路は一暦日内に勤務が完了する日勤と，夜間の仮眠を含み二暦日にわたる夜勤とからなり，JR各社では通常，乗務員の総勤務日数を最小化する計画を考えている。CSPは，集合被覆問題（SCP）と呼ばれる0-1整数計画問題として定式化が可能であるが，SCPの変数にあたる行路の候補数が容易に数千万～数億に達するため，大規模な0-1計画問題となり，必要に応じて行路（列）候補を生成する列生成法を用いても多大な時間を要する難問である。
　本研究では，列生成法を用いてSCPを解くことを前提とするが，列生成法の計算時間はSCPの線形緩和問題や列生成子問題の計算時間に大きく依存し，乗務数が数千を超える大規模なCSPは依然として求解が困難な難問である。大規模な問題の最適解を規模の小さな問題を繰り返し解くことによって求める方法には制約分解，制約統合という2つのアプローチが知られているが，本研究では動的な制約統合(dynamic constraint aggregation)により，求解速度を速めることを考える。制約統合法は，連続する乗務を統合することによって乗務の数，すなわち，SCPの行数を減らすことでSCPの線形緩和問題をより効率よく解こうとする。Elhallaoui et al.(OR 2005)が提案した動的制約統合法は，欧米のエアーラインのCSPで応用があるが，これまでのところ鉄道への応用はない。また，乗務数が2000を超える大規模CSPの求解事例は，筆者の知る限り国内では当研究室の2011年度の修士論文（小池）しか存在しない。また，Elhallaouiらの提案は，SCPそのものを解く訳ではなく，SCPの線形緩和問題の解法に留まっており，本来のSCPの解を算出するメカニズムを追加する必要がある。
　そこで，本研究では，Elhallaouiらの動的制約統合を我が国の鉄道のCSPに適用するとともに，CSPの高い精度の解を効率よく算出する方法を開発することを目的とする。実験にあたっては，乗務数2000以上の国内の実際の線区のデータに基づいた乗務員運用計画の作成を目指す。