在来線乗務員運用計画への数理最適化の適用と検証_2026OR春季大会

在来線乗務員運用計画への数理最適化の適用と検証 非会員 東海旅客鉄道株式会社 *北村 望 KITAMURA Nozomu 非会員 東海旅客鉄道株式会社 齋藤 竜平 SAITO Ryohei 非会員 株式会社 Jij 宮脇 悠 1. はじめに 鉄道の乗務員（運転士・車掌）の運用計画は、ダイヤ改正の たびに手作業により作成しており、大規模な線区では、作業量 MIYAWAKI Yu が発生することもあるが、便乗は非効率であり、できるだけ減 らすことが望ましい。 3-3．目的関数及び制約条件について が膨大になり、担当者の負担が大きい。また、専門の担当者が 本問題では、出面数と便乗数の最小化を目的とする。これを 担っており、技術が暗黙知になりやすく、その継承が難しいと 表す目的関数は式(1)のとおりで、第 1 項が出面の総数、第 2 いう課題を抱える。 項が便乗の総数にペナルティ β を掛けた値であり、表 1 に係 2. 研究目的 数や変数の詳細を記載する。 数理最適化を用いて乗務員運用計画の自動化・高度化を図り、 𝑚𝑖𝑛 暗黙知を形式知化することを目的とする。これにより、作成負 ∑ 𝑐𝑗 𝑥𝑗 + ∑ 𝛽 (∑ 𝑎𝑖𝑗 𝑥𝑗 − 𝑤𝑖 ) 担を軽減し、持続可能な乗務員運用計画の作成体制の構築を目 𝑗∈𝑁 𝑖∈𝑀 指す。本研究では、車掌の運用計画（車掌行路）を対象とする。 表 1：定数や変数の詳細 (1) 𝑗∈𝑁 3.車掌スケジューリング問題の数理モデル概要 記号 説明 3-1．背景 N 提案された行路の集合。各要素 j は 1 行路（日勤行 路または 2 日行路）を表す。 乗務の集合。各要素 i は 1 つの乗務を表す。 車掌の運用計画を作る際、さまざまなプロセスを経て完成に 至る。最初に行われるのは一般的に平日ダイヤでの行路作成で M ある。したがって、本研究で扱う問題は平日ダイヤにおける車 xⱼ 掌の運用計画とした。このような乗務員運用計画問題は、各営 業列車の乗務に少なくとも 1 名の車掌を割り当てつつ、選択す る行路集合の総コストを最小化する集合被覆問題として定式 化可能であることが広く知られている。本研究でもこの枠組み を採用し、問題の定式化と解法の検討を行う。 3-2．数理モデルの考え方 本問題は、各車掌が複数の乗務を順次乗り継いで構成される cⱼ aᵢⱼ wᵢ β 行路 j を採用するなら 1、採用しないなら 0 のバイ ナリ決定変数。 行路 j のコスト（必要な車掌出面数）係数。日勤行 路なら 1、2 日行路なら 2。 行路 j が乗務 i を含むとき 1、含まないとき 0 とな る決定変数。 乗務 i の種別を表す定数。営業乗務なら 1、それ以 外の乗務なら 0。 便乗に対するペナルティ係数。 勤務スケジュール（行路）を決定する計画問題である。最も重 要な目的は、1 日に必要となる車掌の総数（出面）の最小化で 本数理モデルでは、明文化された規則（労働・休憩（食事時 ある。車掌の行路には「日勤行路」と「2 日行路」の 2 種類が 間含む） 、設備条件（例：泊地ベッド数上限） 、駅別の運用ルー ある。前者は、午前中に乗務を開始し、その日の夜までに業務 ル（例：休憩・宿泊・出退勤ができる駅の限定）に加え、暗黙 を終える 1 日完結の行路であるが、後者は、ある日に乗務を開 知として蓄積されてきた運用ノウハウ（乗継地点では、可能な 始して途中宿泊し、翌日にもいくつか乗務して業務を終える行 限り車両の運用に合わせて担当車掌が同じ列車の運用を続け 路である。そのため、出面の数え方は、 「日勤行路」の場合は て乗務できるようにすること、車両運用と乗務員行路を連動さ 1、 「2 日行路」の場合は 2 となる。 せる運用、遅延時の柔軟性確保、教育・育成上の配慮）を形式 また、目的関数を検討する上で重要な要素に便乗数の最小化 知化して統合し、解の実用性を向上させる。実装した制約を以 がある。便乗とは、車掌が業務に従事せず、次の乗務の開始地 下に示す。 点、あるいは出退勤に伴い所属箇所と乗務開始・終了地点との ・業務開始・終了：乗務員の所属箇所の最寄駅で開始・終了 間で位置調整のために列車へ乗車して移動する行為をいう。基 ・休憩・宿泊駅：休憩・宿泊は指定駅に限定 本的に営業列車には常に 1 人の車掌の乗務が必要である。一方 ・乗務員数要件：回送列車・ワンマン列車は車掌不要、特定列 で、回送列車やワンマン列車では運転士のみで運行できるため、 車は 2 名乗務 車掌は不要である。したがって、営業列車に 2 人の車掌が同時 ・連続純運転時間：連続純運転時間は所定上限以内とする に乗務している場合や、回送列車に車掌が乗務している場合は、 ・食事の確保：定められた時間帯における昼食・夕食の所要時 それらは便乗に該当する。乗り継ぎの都合上、避けがたい便乗 間確保

・睡眠の確保：2 日行路における所要睡眠時間の確保 Step 2-3： 固定した行路群を主問題に制約として追加し、実行 ・日勤行路の上限・下限設定：総労働時間・拘束時間の所定の 可能性を確認。実行可能解が得られないならば、𝑥𝑗 = 1に固定 範囲内および出勤・最終到着時刻の基準の遵守 ・2 日行路の上限・下限設定：総労働時間・拘束時間の所定の 範囲内、深夜乗務の程度に応じた上限の調整 した行路を保持したまま Step 2-1 に戻り、列生成を継続する。 実行可能解が得られた場合は終了し、Step3 へ。 Step 3（ポストプロセス） ：得られた結果から、同じ駅から同 ・休憩の最低確保：労働時間に応じた休憩時間の最低確保 じ駅に向かう乗務群のうち、全てが便乗で構成されている乗務 ・設備容量：休養室のベッド使用数は上限を超過しない 群を取り除く。 ・車両・乗務員運用の連動：車両の運用に合わせ、可能な限り 担当車掌が同じ列車の運用を連続して乗務することとする。 ・乗務可能区間：所属箇所ごとの乗務可能区間を考慮 ・主要駅の乗り継ぎ下限：主要駅における乗り継ぎ時間下限の 設定による遅延耐性の確保 4. アルゴリズムの詳細 車掌運用計画を集合被覆問題として解く際に一般的に用いら れるのは列生成法である[1]。 しかし、列生成法をそのまま適 用しても、実用規模では短時間で良い計画を得ることが難しい。 加藤らは、列生成法で得られた行路のうち目的関数の改善に資 する行路を段階的に固定していくアルゴリズムを提案し、人手 の計画に近い品質を現実的な時間で作成することに成功した ［2］ 。本研究では、現場の問題特性に合わせてヒューリスティ クスな工夫を追加し、さらに改善を図った。具体的には、ダイ ヤが疎な部分（本数が少ない区間・時間帯）から優先的に行路 を作る工夫や、作成後の行路から不要な往復便乗を取り除く後 処理（ポストプロセス）を組み込んでいる。アルゴリズムの手 順は次のとおりである。 Step 1：初期解を準備する。 しかし、実運用に適した車掌運用計画に仕上げるためには、最 終的な人手による微修正が不可欠である。これは実際の運用計 画には細かな遵守が望ましい制約（現場の慣例、食事や休養時 間や教育・育成を目的とした細かい配慮など）が多く、数理モ デルだけで完全に調整することが難しいためである。さらに、 本数理モデルで扱うデータは、計算時間の高速化のため、実際 のダイヤよりも粗く乗務を区切っている。例えば、本来は途中 駅から降りられる区間でも分割せず、乗り換えが発生する可能 性が高い駅まで意図的に 1 つの乗務として扱っている。その結 果、非効率な行路が混ざることがあり、最終的な人手による微 修正が必要となる。 5 結果 2024 年 3 月ダイヤ改正時点の当社中央本線 （名古屋〜塩尻） の列車ダイヤデータに基づき試算を実施した。実運用に必要な 一部制約が未反映であるため、結果は条件付きと位置付けるが、 人手で作成した運用計画と同等以上の効率性を確認した。詳細 は発表時に示す。 6 今後の課題 本研究では中央本線の平日ダイヤを対象に、乗務員運用を計 Step 2：以下のプロセスを繰り返す。 画する数理モデルとアルゴリズムを構築した。しかし、ダイヤ Step 2-1：以下（2-1-1 から 2-1-3）を、所定回数、もしくは 2- は毎年更新されるため、異なる時期のダイヤに対しても一貫し 1-3 で被約費用が負の行路が 5 回連続で生成されなくなる た品質でスケジュールを作成できる、汎用性と頑健性の高い数 まで繰り返す。 理モデル・アルゴリズムへの拡張が求められる。 2-1-1：主問題の緩和問題の双対問題を解く。 2-1-2：子問題に特定の制約を基本制約として追加する。 追加する制約は反復（iteration）ごとに調整するが、 初期の反復ではダイヤが疎で乗務の選択肢が少ない 部分の乗務を選びやすくする制約を加える。 2-1-3：2-1-1 で解いた双対問題の解を用いて、子問題で行 また、行路の適否は、当該行路を用いて交番を作成し、実行 可能解が得られるかどうかで最終的に判断される。本研究では 交番による検証を実施していないため、今後は交番作成まで含 めた統合的な数理モデルへ発展させる必要がある。 謝辞 本研究の遂行にあたり、公益財団法人鉄道総合技術研究所 信号技術研究部 運転システム研究室 加藤怜氏の多大なご支 路を 1 つ以上生成する。探索の多様性を確保するた 援ならびに技術的助言に感謝する。記して謝意を表する。 め、子問題の最小の目的関数値から誤差 50%以内の 参考文献 行路も列として追加する。 [1] 西竜志，室井裕喜，乾口雅弘，高橋理，片岡健司：実乗務 Step 2-2：2-1 のプロセスが終わったら以下を実施する。 制約を有する鉄道乗務員運用計画問題に対する列生成法の適 2-2-1：主問題の緩和問題を解き、行路 j を選ぶかどうかの 用，電気学会論文誌 C，Vol.131，No.6，pp.1199-1208，2011 変数𝑥𝑗 = 1となっている行路のうち、最も労働時間 [2] 加藤怜,中東太一,小久保達也:要員数最小化を目的とした が長い行路を選ぶ。𝑥𝑗 = 1の行路がない場合は、1 に 乗務員運用計画の自動作成手法,鉄道総研報告 Vol.39，No.3， 最も近い小数値の𝑥𝑗 を持つ行路を𝑥𝑗 = 1に固定する。 2025.