日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-B-8

基本行路パターンを用いた乗務員運用計画作成アルゴリズム
011115001.

(公財) 鉄道総合技術研究所

はじめに

ۢॶ

%Ӽ

&Ӽ

図 1: 列車ダイヤの例
$Ӽ
ۢॶ

%Ӽ

&Ӽ

乗務員運用計画と基本行路パターン

乗務員運用計画は，所与の列車ダイヤで設定されているすべての列車に対し，1 人の乗務員を割り当てることで作成する．各乗務員の 1 回の勤務を「行路」（日勤行路と 2 日にまたがる泊行路がある）と呼び，各行路は，拘束時間（開始から終了までの時間）の上限などの条件を満たす必要がある．
これまでの数理最適化による計画作成の考え方
は，各列車を乗務員交代駅で分割した最小単位を「乗務」と定義し，複数の乗務をつなぎ合わせることで行路を作成するものであった [1]．しかし，乗務数は列車数，乗務員交代駅数に依存するため，これらが多い路線では組合せが膨大になり，現実的な計算時間での求解が困難であった．
そこで本稿では，「基本行路パターン」と呼ばれる複数列車の乗務パターンを用いる．これは，A駅→ B 駅→ A 駅といった乗務員の乗務経路を示し，休憩から次の休憩までの乗務集合とする．そのう
えで，1M(A 駅→ B 駅)，2M(B 駅→ A 駅) に乗務といった基本行路パターンに合致する「基本行路」を作成し，複数の基本行路を組合せることで行路を作成する，といったアプローチをとる．基本行路は，複数の列車から構成されるため，組合せ数を抑制することができ，また現実的な基本行路パ

KATO Satoshi$Ӽ

鉄道事業者は，ダイヤ改正時には，乗務員の勤務スケジュールを示す乗務員運用計画を作成している．これまで，数理最適化による運用計画作成アルゴリズムを開発してきたが，従来の列車乗務の最小単位を組み合わせて計画を作成する方法では，列車本数が多い路線では組合せが膨大になってしまい，現実的な時間での作成が困難であった．
そこで，列車本数の多い大規模な路線に対しても，現実的な計算時間で計画を自動作成することを目的として，基本行路パターンと呼ばれる複数列車の乗務パターンを最小単位とし，その組合せにより計画を作成する手法を開発したので，その概要を紹介する．

2.

*加藤 怜

ߨ࿑ ೖ‫ߨ ۊ‬࿑ ഩ ߨ࿑ ഩ‫خ‬ຌߨ࿑Ϗνʖϱ
 $ˢ&ˢ$ $ˢ&ˢ% %ˢ&ˢ$

図 2: 乗務員運用計画の例
ターンを準備することで，実用的な運用計画作成も可能となる．
図 1 に列車ダイヤの例，図 2 には対応する乗務員運用計画の例を示す．この例では 3 つの行路を作成しており，基本行路パターンは (1)〜(3) の 3種類を用いている．従来の「乗務」の考え方によると，各列車が最小単位となり，それで組み合わせることになるが，基本行路パターンを用いることで，複数列車の集合が最小単位となるため，組合せ数を減らすことができる．

3.
3.1.

基本行路パターンを用いたアルゴリズム
基本的な考え方

まず，入力となる列車ダイヤ，車両運用と基本行路パターンから，基本行路パターンに合致する運用をすべて抽出する．この運用を「部分行路」と呼ぶ．また，各部分行路の端点で元の車両運用を切断したそれぞれを「運用単位」と呼ぶ．よって，部分行路は，1 つ以上の運用単位を包含している．
本稿では，集合被覆問題としてモデル化し，列生成法を適用する [2]．ここで，集合被覆問題における行（被覆するもの）は運用単位となる．

3.2.

重み

主問題

使用する記号として，I を運用単位 i の集合，Jを行路 j の集合，dj を行路 j の勤務日数，ej を行路 j の拘束時間，aij を行路 j が運用単位 i を含む
場合 1，さもなければ 0 とする．主問題の定式化を以下に示す．

min.

∑(αdj + βej )xj + γ

j∈Js.t.

∑

表 1: 実験結果∑yi(1)∀i ∈ I(2)i∈I

aij xj − yi = 1,xj ∈ {0, 1},∀j ∈ J∀i ∈ I

便乗数51442

基本行路数1039799

計算(秒)
49.0
56.7
65.3

結果と考察

以下の重みパラメータの組合せで実験する．

(3)
(4)

拘束時間(秒)
1,377,560
1,309,820
1,304,110

端・終端となる駅）が 4，乗務員区所数が 1，列車本
数が 271 本，基本行路パターン数が 19 の路線である．実験には，Windows 10 Pro, Core i7-8700K,64GB メモリの PC を用いて，数理最適化問題の求解には Google OR-Tools v6.6 を用いる．

4.2.

j∈J

yi ≥ 0,(1)
(2)
(3)

勤務
日数373738(1) α = 1, β = 0, γ = 0(2) α = 1, β = 0.00001, γ = 0

目的関数 (1) 式の第 1 項は行路のコスト（勤務日数および拘束時間）と便乗数のコストの合計値である．α は行路コスト，β は拘束時間（単位は秒），γ は便乗数に対する重みである．(2) 式は全運用単位に対し，いずれかの行路が割り当てられる（2 つ以上割り当てられた場合は便乗）ことを示す．(3)，(4) 式は，変数のとり得る値の制限を示している．

3.3.

列生成子問題

列生成子問題では，以下の目的関数を最小にする列 j （すなわち行路) を求める．
∑min. αdj + βej −πi aij(5)i∈I

ここで，πi は (2) 式の双対変数である．列生成子問題は，部分行路をノード，部分行路の接続関係をアークとしたネットワーク上の制約付き最短路問題に帰着できる．ノード i, j 間のアークのコス∑
トは β(gj − gi ) − k∈Kj πk となる．ここで，gi は部分行路 i の終了時刻，Kj は部分行路 j が含む運用単位の集合である．
また，整数実行可能解の算出には，収束後に LP解を切り上げ列生成を繰り返す手法 [3] を用いる．

4.
4.1.

数値実験
路線データ

上記で述べたアルゴリズムの性能を検証するため，実在路線を基にしたデータを用いて数値実験を行う．対象路線データは，駅数（基本行路の始(3) α = 1, β = 0.00001, γ = 1
表 1 に，各パラメータでのアルゴリズム適用結果を示す．表 1 をみると，重みを大きくするとその項目の数値が低減されることを確認できる．特に便乗についてはその傾向が顕著であり，実用的な計画を作成するには，重みの付与がほぼ必須といえる．計算時間については，いずれも 1 分程度と比較的短時間で求解できている．

5.

まとめ

本稿では，乗務員運用計画作成に対し，基本行路パターンを用いた計画作成アルゴリズムを提案した．従来の列車乗務の最小単位に基づく方法に比べ，問題規模を縮小し，計算時間を短縮できると期待できる．今後は，より列車本数や乗務員交
代駅数の多い路線にも適用し検証を進め，本アルゴリズムの活用可能性を検討していく．

参考文献[1] (財) 鉄道総合技術研究所運転システム研究室:
鉄道のスケジューリングアルゴリズム, エヌ・ティー・エス (2005)[2] 今泉ら: 鉄道の乗務員運用計画作成問題に対する列生成法の適用, オペレーションズ・リサー
チ, Vol.56, No.2, pp.104-109 (2011)[3] 西ら: 実乗務制約を有する鉄道乗務員運用計画問題に対する列生成法の適用, 電気学会論文誌
C, Vol.131, No.6, pp.1199-1208 (2011)