c オペレーションズ・リサーチ
要約■

■学生論文賞受賞論文

バス乗務員スケジューリング問題に対する列生成アプローチ
澤井 佑樹
名古屋大学大学院情報科学研究科計算機数理科学専攻（現：（株）デンソー）
指導教員：柳浦睦憲 名古屋大学教授，橋本英樹 東京海洋大学准教授

1.

はじめにの組合せを仕業という．仕業時間内で業務を行っていない時間のことを休憩という．ただし，ダイヤ間ある

バス乗務員スケジューリング問題は，与えられたすべ

いはダイヤと回送間が 10 分未満の場合は，休憩ではてのダイヤを実行するという条件の下で，乗務員数を最なく業務とみなす．次に，本研究で扱う問題における小化する問題である．1 人の乗務員が 1 日に受け持つ仕業に対する制約を示す．

ダイヤの組合せを仕業と呼ぶ．仕業は乗務員の労働条

1. 仕業は車庫から出発し車庫に戻る．

件などのさまざまな制約を満たす必要がある．この問

2. 一つの仕業の開始から終了までは 590 分以内．

題に対して可能な仕業を全列挙したのち対応する集合

3. 一つの仕業の開始から終了までが 6 時間を超える被覆問題を厳密に解けば最適解を得られるが，計算量が場合は 45 分以上，8 時間を超える場合は 60 分以最悪の場合には指数時間となり現実的でない．そこで上の休憩が必要である（労働基準法による制約）．

本研究では列生成法 [1] を用いるアプローチを提案する．

4. 任意の連続する 270 分以内に 30 分以上の休憩が列生成法の内部では，現在の仕業集合に対応する集必要である．

合被覆問題の線形緩和問題（主問題）に対する双対問

これらすべての制約を合わせて仕業制約と呼ぶ．仕業題から得られる双対価格をダイヤの重みとし，双対価制約を満たす仕業すべての集合を Nall とする．その中格の重み和を最大とするダイヤの組合せを発見する問から全ダイヤを含むように仕業集合 N ⊆ Nall を選び，題（価格付け問題）を解く．得られた有効な仕業を仕仕業数 |N | を最小化（すなわちのべ乗務員数を最小化）業集合に追加するという操作を主問題の目的関数値をすることが本問題の目的である．

改善できなくなるまで繰り返す．最後に生成された仕ここで本問題を解くため，集合被覆問題に基づいた定業集合に対して集合被覆問題を解き，本問題の解を得式化を行う．各仕業 j ∈ Nall に含まれるダイヤの集合る．価格付け問題を解く手法として，休憩時間に対すを M の部分集合 Sj とする．aij を，仕業 j がダイヤ i

る制約を緩和して定式化した問題を動的計画法によりを含むなら 1，そうでなければ 0 と定める．xj ∈ {0, 1}

厳密に解くことで得られる双対価格の和を上界とし，を，仕業 Sj がスケジュールに含まれるなら 1，そうそれをもとに探索を行う手法を提案した．

でなければ 0 となる変数とみなせば，バス乗務員スケ実験では企業から提供された現実のデータである，ダイヤ数約 2000 の問題例を扱う．実験結果より，提ジューリング問題は，minimize

案アルゴリズムが，企業のエキスパートによって作成された解よりも乗務員数を削減する解を出力すること

問題定義と定式化

xj(1)j∈Nallsubject to

aij xj ≥ 1∀i ∈ M(2)∀j ∈ Nall(3)

j∈Nallを確認した．

2.

xj ∈ {0, 1}と定式化できる．式 (1)–(3) で表されるこの問題を出発地点からバス停を複数経由し，到着地点まで運BSP(Nall ) と呼ぶ．実世界の問題例ではすべての実行する一連の業務をダイヤという．ここで，与えられ行可能な仕業 Nall を列挙することは非現実的である．

る地点の中には車庫が含まれる．各ダイヤには出発時

そのため次節で提案する方法により生成した N ⊆ Nall

刻，到着時刻，出発地点，到着地点が与えられる．ダを用いて BSP(N ) を解く．

イヤの集合を M = {1, 2, . . . , m} とする．あるダイヤの到着地点と次のダイヤの出発地点が異なる場合に行

3. 提案アルゴリズム

う移動を回送といい，各地点間の回送にかかる時間が3.1 列生成法与えられる．1 人の乗務員が 1 日に行うダイヤと回送

列生成法でははじめに初期仕業集合 N0 を生成し，c by ORSJ. Unauthorized reproduction of this article is prohibited.
798（70）Copyright 

オペレーションズ・リサーチ

N0 を N に代入する．各反復では，BSP(N ) の制約式
(3) を xj ≥ 0 に置き換えた線形緩和問題 P(N ) を解表1

提案手法と企業の解との比較

くことで，最適解に対応する各ダイヤの双対価格 πi∗問題例 ダイヤ数(i ∈ M ) を得る．ここで，列の追加によって P(N )の最適値を下げるためには， i∈M aiρ πi∗ > 1 を満た

平日 1す列 ρ ∈ Nall \ N を N に追加することが必要であ

土曜 1
日曜2312
2016
1914

提案手法
企業解
|N |
P(N ) BSP(N )22567 149.605
150
16222136 123.736
124
133
18993 118.053
119120る．この左辺を最大化する問題を価格付け問題と呼び，

∗i∈M aiρ πi と定式化できる．価格付けによって与えられる．

問題を解き，得られる ρ を N に追加し P(N ) を解く

しきい値 U に対して

maxρ∈Nall \N∗i∈M aiρ πi が U を超えるパスことを，価格付け問題の最適値が 1 を超えなくなるまを，q(β, t) > U を満たす状態 (β, t) から始め，深さ優先で繰り返すことで，仕業集合 N を生成する．

探索の探索順で，動的計画法の計算とは逆の向きに状態3.2 グラフの生成を辿ることで得る．その際，(β, t) から現在探索中の状

価格付け問題を解くため，ダイヤをグラフの頂点と態 (i, t ) までのパス（仕業の後部に相当する部分）上の対応づける．ダイヤ i を運行した直後に運行可能なダ双対価格の合計と q(v, t ) (ただし t = t − (gi − gv ))イヤの集合を Vi+ とする．v ∈ Vi+ に対して，iv 間にの和が U を超える v ∈ Vi− のいずれかを選ぶ．得られ有向辺 eiv を引く．またすべての頂点 i ∈ M が，頂点たパスを仕業候補として，仕業制約を満たすか否かを

α からの有向辺 eαi と，頂点 β への有向辺 eiβ をもつ判定する．仕業制約を満たすのであれば，仕業候補をよう，ダミー頂点 α と β をグラフに追加する．生成し仕業集合 N に追加し，さらに探索を続ける．条件を満たグラフを用いることで，価格付け問題は α から β へたす仕業が一つも発見されなかった場合は， P(N ) のと向かう仕業制約を満たすパス上の双対価格の合計を最適値が得られているため，列生成法を終える．

最大化する問題と言い換えることができる．

4. 計算実験とまとめ

3.3 価格付け問題を解くための提案手法
動的計画法の設計について，i 番目のダイヤ終了時に3 節で示した提案手法の有効性を検証するため，計おける仕業の総時間が丁度 t (0 ≤ t ≤ 590) 分である算実験を行った．実験では企業から提供された現実の時の，双対価格の合計の最大値を q(i, t) と定義する．

データである，ダイヤ数約 2000 の問題例を扱う．列生

また Vi− を，i 番目のダイヤの直前に運行可能なダイ成を行う制限時間を 3600 秒とする．実験結果を表 1 にヤの集合と定義すると，ダイヤ i の開始時刻 fi とその示す．列生成終了後の仕業数を欄 |N | に，問題 P(N )到着時刻 gi ，およびダイヤ i 運行直後に運行可能なダの最適値と問題 BSP(N ) に対して得られた解の目的関イヤ j への有向辺 eij がもつ回送時間 hij を用いて，数値をその右 2 列に記す．企業のエキスパートが生成

q(i, t) は漸化式
0(t = 0)q(α, t) =−∞ (t = 0)q(i, t) = max q(α, t − hαi − (gi − fi )),した解を 企業解 に示す．表 1 より，提案アルゴリズ

maxv∈Vi− \{α}

ムが企業解よりも乗務員数を削減する解を出力するこ(4)とを確認した．また別の実験により，ダイヤ数 1500 程度までの問題例に対しては，提案手法によって現実的q(v, t − (gi − gv ))な時間内で最適値までの誤差が 1.5％以内の評価値が+ πi∗得られることを確認した．

(i = α, β)q(β, t) = max q(v, t − hvβ )v∈Vβ−2016 年 11 月号

(5)

参考文献

(6)

[1] G. Desaulniers, J. Desrosiers and M. M. Solomon(eds.), Column Generation, Springer, 2005.

c by ORSJ. Unauthorized reproduction of this article is prohibited. （71）
Copyright 799