鉄道ダイヤ作成を数理最適化とスケジューリング問題として捉える

電車のダイヤは、普段は「何時何分に電車が来るか」という時刻表として見ている。

ただ、少し数理的に見てみると、かなり面白い。

ダイヤ作成は、単に発車時刻を並べる作業ではない。線路、駅、信号、ホーム、列車種別、乗客の流れ、乗換、車両、乗務員、遅延リスクなどを同時に見ながら、全体として破綻しないスケジュールを作る作業だ。

研究上は、こうした問題は train timetabling problem や railway timetabling problem と呼ばれる。ざっくり言えば、制約付きスケジューリング問題であり、組合せ最適化問題でもある。

この記事では、鉄道ダイヤ作成を数理最適化の問題として見るとどう整理できるのかを、自分用のメモも兼ねてまとめてみる。

鉄道ダイヤは何を決める問題なのか

まず、ダイヤ作成で決めたいものは何だろうか。

利用者から見ると、知りたいのはこういう情報だ。

A駅を 8:00 に発車
B駅に 8:03 に到着
C駅に 8:10 に到着

数理的には、これは列車ごとの各駅における到着時刻と出発時刻を決める問題だ。

列車を $i$ 、駅を $s$ とすると、到着時刻と出発時刻は次のように表せる。

a_{i,s} = \text{列車 } i \text{ が駅 } s \text{ に到着する時刻}

d_{i,s} = \text{列車 } i \text{ が駅 } s \text{ を出発する時刻}

つまり、ダイヤ作成とは、すべての列車 $i$ と駅 $s$ について、 $a_{i,s}$ と $d_{i,s}$ を決める問題だと考えられる。

もちろん、好き勝手に時刻を決められるわけではない。

駅間の走行時間、駅での停車時間、前後列車との安全間隔、単線区間でのすれ違い、ホーム容量、待避、折返し、乗換接続など、多くの制約がある。

この制約の多さが、鉄道ダイヤを面白くしている。

走行時間と停車時間

一番基本になるのは、走行時間の制約だ。

駅 $s$ から次の駅 $s+1$ までの走行時間には下限がある。列車は物理的にそれより早く走れない。

走行時間の下限と上限を $[\underline r_{i,s}, \overline r_{i,s}]$ とすると、次のように書ける。

\underline r_{i,s} \le a_{i,s+1}-d_{i,s} \le \overline r_{i,s}

下限は最低限必要な運転時間で、上限は余裕時分を含めた許容時間と考えればよい。

次に、駅での停車時間がある。

列車が駅に着いたら、乗客の乗り降り、ドア扱い、安全確認が必要になる。混雑駅なら、停車時間はさらに伸びる。

停車時間の下限と上限を $[\underline w_{i,s}, \overline w_{i,s}]$ とすると、次のようになる。

\underline w_{i,s} \le d_{i,s}-a_{i,s} \le \overline w_{i,s}

停車時間は、単なるサービス上の条件ではない。ホームを占有している時間でもある。

つまり、停車時間が長くなると、その駅に後続列車を入れにくくなる。特に高頻度運転では、駅での停車時間が全体の容量を決めることもある。

ヘッドウェイと線路容量

鉄道では、同じ線路上を複数の列車が走る。

そのため、前の列車と後ろの列車の間には安全間隔が必要になる。この間隔はよく ヘッドウェイ と呼ばれる。

たとえば、同じ区間 $(s,s+1)$ を列車 $i$ が先に走り、列車 $j$ が後から走るとする。

このとき、出発時刻や到着時刻には最低間隔が必要になる。

d_{j,s}-d_{i,s}\ge h^{\mathrm{dep}}_{ij,s}

a_{j,s+1}-a_{i,s+1}\ge h^{\mathrm{arr}}_{ij,s}

実際のモデルでは、「どちらの列車が先に走るか」も決める必要があるので、0-1変数を使って表現することが多い。

たとえば、 $x_{ij,s}=1$ なら列車 $i$ が先、 $x_{ij,s}=0$ なら列車 $j$ が先、というように置く。

d_{j,s}-d_{i,s}\ge h^{\mathrm{dep}}_{ij,s}-M(1-x_{ij,s})

a_{j,s+1}-a_{i,s+1}\ge h^{\mathrm{arr}}_{ij,s}-M(1-x_{ij,s})

ここで $M$ は十分大きな数だ。

このあたりから、鉄道ダイヤ作成はかなり組合せ最適化らしくなる。

単に「何分に出すか」を決めるだけではない。「どの列車を先に通すか」も同時に決める必要がある。

同じ線路区間を同時に使えない

もう少し一般化すると、線路、閉塞区間、分岐器、駅構内の進路などは、一定時間だけ列車に占有される資源だと見なせる。

ある資源 $b$ を列車 $i$ が $[u_{i,b}^{\text{in}},u_{i,b}^{\text{out}}]$ の間占有するとする。

このとき、別の列車 $j$ が同じ資源を使うなら、どちらかが先に通過しなければならない。

u_{j,b}^{\text{in}} \ge u_{i,b}^{\text{out}}+\tau_b \quad \text{or} \quad u_{i,b}^{\text{in}} \ge u_{j,b}^{\text{out}}+\tau_b

これはかなり直感的だ。

同じ線路区間、同じ進路、同じホームを、同時に複数列車が使うことはできない。

鉄道ダイヤは、時間軸上でこうした共有資源をどう割り当てるかの問題でもある。

単線区間はさらに難しい

単線区間では、上下列車が同じ線路を逆方向に使う。

そのため、どちらか一方が区間を抜けてからでないと、もう片方は入れない。

上下列車 $i$ と $k$ が同じ単線区間 $\ell$ を使うとき、二値変数 $y_{ik,\ell}$ を使うと、次のように書ける。

\text{enter}_{k,\ell} - \text{leave}_{i,\ell} \ge \tau_\ell - M(1-y_{ik,\ell})

\text{enter}_{i,\ell} - \text{leave}_{k,\ell} \ge \tau_\ell - M y_{ik,\ell}

単線では、交換駅や信号場の位置がかなり重要になる。

どこで列車を行き違いさせるかによって、ダイヤ全体の形が大きく変わるからだ。

普段、時刻表だけを見ていると分かりにくいが、単線区間のダイヤはかなり繊細なパズルになっている。

ホーム容量と駅の詰まり

線路上だけでなく、駅もボトルネックになる。

たとえば、ある駅にホームが2本しかなければ、同時に扱える列車数には限界がある。

時刻 $t$ にプラットフォーム $p$ を同時に使う列車数が容量 $C_{s,p}$ を超えない、という制約は次のように書ける。

\sum_{i} \mathbf{1}\{i \text{ occupies } p \text{ at } t\} \le C_{s,p}

高頻度運転では、線路そのものより駅の処理能力が先に詰まることもある。

駅で列車が長く停まると、そのホームが空かない。ホームが空かないと、次の列車を入れられない。すると、後続列車にも遅れが波及する。

つまり、鉄道容量は「線路が何本あるか」だけでは決まらない。

信号、閉塞、ホーム、分岐器、停車時間、列車種別の混在まで含めて決まる。

急行と各停が混ざると何が起きるか

鉄道ダイヤで面白いのが、急行と各駅停車の混在だ。

各停は多くの駅に停まるので、どうしても所要時間が長くなる。一方、急行は途中駅を通過するので速い。

同じ線路上でこの2種類を走らせると、速い列車が遅い列車に追いついてしまう。

そこで必要になるのが、待避や追越しだ。

たとえば、各停が先に走り、その後ろから急行が来る場合、待避設備のある駅で各停を停め、急行を先に通す。

数理的には、これは列車の順序が途中の駅で入れ替わることだ。

区間 $(s-1,s)$ では各停が先だったのに、駅 $s$ で待避して、区間 $(s,s+1)$ では急行が先になる。

このような順序反転を許せる駅が待避駅になる。

逆に、待避設備がない場所では順序反転はできない。

つまり、急行と各停の違いは、単なる所要時間差ではない。列車同士の順序制約を増やす差でもある。

急行を増やせば速達性は上がるが、そのぶん各停の待避が増えたり、線路容量を食ったりする。

ここにもトレードオフがある。

乗換接続も制約になる

ダイヤでは、乗換接続も重要だ。

たとえば、列車 $i$ から列車 $j$ へ乗り換えさせたい駅 $s$ があるとする。

乗換に必要な最低時間を $\tau^{\text{tr}}_{ij,s}$ とすれば、次の制約になる。

d_{j,s}-a_{i,s}\ge \tau^{\text{tr}}_{ij,s}

つまり、列車 $j$ は、列車 $i$ が到着してから乗換に必要な時間が経過したあとでないと出発できない。

地方路線や終電では、この接続がかなり重要になる。

一方で、接続を守るために列車を待たせると、その列車の遅れが後続へ波及することもある。

接続を守るか、定時性を守るか。

これもダイヤ作成の難しいところだ。

目的関数：何を良いダイヤとするか

制約を満たすダイヤは一つとは限らない。

そこで、「何を良いダイヤとするか」を目的関数として決める必要がある。

たとえば、次のような目的が考えられる。

旅客の総待ち時間を小さくする
乗換待ち時間を小さくする
総移動時間を小さくする
必要車両数や運行コストを小さくする
混雑を平準化する
遅延に強くする
既存ダイヤからの変更量を小さくする

これらは同時に満たせるとは限らない。

本数を増やせば待ち時間は減るかもしれないが、車両や乗務員のコストは増える。

急行を増やせば速達性は上がるかもしれないが、各停の待避が増えて、全体としては不便になることもある。

余裕時分を増やせば遅延には強くなるが、所要時間は長くなり、線路容量も圧迫する。

かなり単純化すれば、目的関数は次のように書ける。

\min\; \alpha \cdot \text{旅客時間} +\beta \cdot \text{運行コスト} +\gamma \cdot \text{遅延・脆弱性} +\delta \cdot \text{既存ダイヤからの変更量}

ここで、 $\alpha,\beta,\gamma,\delta$ はそれぞれの目的をどれくらい重視するかを表す重みだ。

この重みの置き方によって、「速達性を重視するダイヤ」「コストを抑えるダイヤ」「遅延に強いダイヤ」など、性格の違うダイヤになる。

Event-Activity Network と周期ダイヤ

鉄道ダイヤの研究でよく出てくる表現に、Event-Activity Network がある。

これは、ダイヤをイベントとアクティビティのネットワークとして表す方法だ。

イベントは、たとえば次のようなものだ。

列車Aが駅Xに到着する
列車Aが駅Xを出発する
列車Bが駅Yに到着する

アクティビティは、イベント間の関係を表す。

駅間を走る
駅で停車する
乗換する
前後列車の安全間隔を保つ

この表現を使うと、走行時間、停車時間、乗換、ヘッドウェイなどを、すべて「イベント間の時間差制約」として扱える。

周期ダイヤでは、これが Periodic Event Scheduling Problem (PESP) に接続される。

PESPでは、各イベント $i$ に周期 $T$ 内の時刻 $\pi_i$ を与え、活動 $(i,j)$ ごとに次の制約を満たすようにする。

l_{ij}\le \pi_j-\pi_i + T p_{ij}\le u_{ij}

ここで、 $l_{ij},u_{ij}$ は最小・最大時間差、 $p_{ij}$ は周期をまたぐことを許す整数変数だ。

周期ダイヤの嬉しいところは、1時間や30分などの1周期を設計すれば、それを一日に展開できることだ。

毎時同じ分に列車が来るダイヤは、利用者にとって分かりやすい。接続もそろえやすい。

ただし、需要が時間帯で大きく変わる場合、完全な周期ダイヤは非効率になることもある。

そのため現実には、周期的なパターンをベースにしつつ、ピーク時だけ増発するような形も多い。

ダイヤの外側にある問題

ダイヤを作れば終わり、ではない。

実務では、ダイヤは車両運用や乗務員運用の入力になる。

たとえば、ある列車が終点に着いたあと、その同じ車両が次の列車として折り返すことがある。

このとき、折返しに必要な時間を $\tau^{\text{turn}}_{ij,u}$ とすると、次の制約になる。

d_{j,u} - a_{i,u} \ge \tau^{\text{turn}}_{ij,u}

時刻表だけ見ると成立していても、実際の車両が足りなければ運行できない。

乗務員も同じだ。

運転士や車掌には、勤務時間、休憩、交代場所、始業・終業場所などの制約がある。

列車本数を増やせば、車両も乗務員も必要になる。

折返し時間を短くすれば車両効率は上がるが、遅延への余裕は減る。

このように、ダイヤ、車両運用、乗務員運用は強く結びついている。

ただし、全部を一体で最適化しようとすると問題サイズが一気に大きくなる。

そのため実務では、ダイヤ、車両、乗務員を逐次的に計画したり、必要な部分だけ統合最適化したり、人間が確認・修正したりすることが多い。

遅延に強いダイヤ

ダイヤには、ある程度の余裕が必要だ。

最小走行時間や最小停車時間だけで詰め込むと、少しの遅れがすぐに後続へ伝播する。

そこで、buffer time や recovery time と呼ばれる余裕時分を入れる。

これは遅延波及を防ぐためには重要だが、入れすぎると所要時間が長くなり、線路容量も減る。

つまり、効率と頑健性はトレードオフになる。

余裕が少ない:
  所要時間は短いが、遅延に弱い

余裕が多い:
  遅延には強いが、所要時間が長くなり、容量も圧迫する

このバランスをどう取るかも、ダイヤ作成の重要な設計判断だ。

どんな最適化手法が使われるのか

鉄道ダイヤ問題では、さまざまな最適化手法が使われる。

代表的なのは Integer Programming や Mixed Integer Linear Programming だ。

列車の順序、番線選択、接続維持、経路選択のような離散的な決定を 0-1 変数で表しやすいからだ。

一方で、複雑な制約を満たす実行可能解を探す場面では Constraint Programming も相性がよい。

また、Event-Activity Network、時空間ネットワーク、代替グラフのようなグラフ表現もよく使われる。

大規模な実務問題では、厳密最適解をそのまま求めるのが難しい。

そこで、列生成、ラグランジュ緩和、分解法、ヒューリスティクス、メタヒューリスティクスなどが使われる。

これは少し意外かもしれない。

「数理最適化」と聞くと、モデルを書いてソルバーに投げれば最適解が出る、という印象がある。

しかし鉄道ダイヤのような実務サイズの問題では、制約も目的も大きく、例外も多い。

最終的には、人間が案を作り、システムが評価し、必要に応じて修正する、というループが現実的なのだと思う。

まとめ

鉄道ダイヤは、表面的にはただの時刻表に見える。

しかし数理的に見ると、かなり複雑な最適化問題だ。

一言で言えば、鉄道ダイヤは次のような問題だと思う。

時間軸つきグラフ上で、
複数の列車が線路・駅・ホーム・車両・乗務員という共有資源を争いながら、
安全間隔、接続、容量、折返し、遅延耐性を満たすように、
旅客利便性・運行コスト・頑健性を最適化する問題。

普段は「何時何分に電車が来るか」としか見ていない時刻表の裏側には、走行時間、停車時間、ヘッドウェイ、単線交換、待避、乗換、車両、乗務員、遅延回復といった制約が折り重なっている。

そう考えると、鉄道ダイヤはかなり巨大なパズルだ。

そして、そのパズルを現実の安全性・利便性・コストの中で成立させるところに、鉄道スケジューリングの面白さがある。

参考文献・出典URL

今回読んだ中で、特に参考になった資料を残しておく。

Serafini, P.; Ukovich, W. A Mathematical Model for Periodic Scheduling Problems (1989). https://doi.org/10.1137/0402049
Peeters, L. Cyclic Railway Timetable Optimization (PhD thesis, 2003). https://repub.eur.nl/pub/429/EPS2003022LIS_9058920429_PEETERS.pdf
Caprara, A.; Fischetti, M.; Toth, P. Modeling and Solving the Train Timetabling Problem (2002). https://doi.org/10.1287/opre.50.5.851.362
Cordeau, J.-F.; Toth, P.; Vigo, D. A Survey of Optimization Models for Train Routing and Scheduling (1998). https://doi.org/10.1287/trsc.32.4.380
Caimi, G. et al. Periodic Railway Timetabling with Event Flexibility (2007). https://drops.dagstuhl.de/storage/01oasics/oasics-vol007-atmos2007/OASIcs.ATMOS.2007.1173/OASIcs.ATMOS.2007.1173.pdf
Liebchen, C.; Möhring, R. The Modeling Power of the Periodic Event Scheduling Problem (2007). https://depositonce.tu-berlin.de/bitstreams/c616b6de-1dc6-4bf3-8c3b-ba9a8f2de60d/download
Bešinović, N. et al. Review of railway timetabling developments, planning phases, goals and future directions (2021). https://doi.org/10.1080/01441647.2021.1904543
Caimi, G.; Kroon, L.; Liebchen, C. Models for railway timetable optimization: Applicability and applications in practice (2016). https://doi.org/10.1016/j.jrtpm.2016.11.002
Harrod, S. A tutorial on fundamental model structures for railway timetable optimization (2012). https://doi.org/10.1016/j.sorms.2012.08.002
Petering, M.; Heydar, M.; Bergmann, D. Mixed-Integer Programming for Railway Capacity Analysis and Cyclic, Combined Train Timetabling and Platforming (2015). https://doi.org/10.1287/trsc.2015.0652
Castillo, E. et al. Timetabling optimization of a single railway track line with sensitivity analysis (2009). https://doi.org/10.1007/s11750-008-0057-0
Brännlund, U. et al. Railway Timetabling Using Lagrangian Relaxation (1998). https://doi.org/10.1287/trsc.32.4.358
Cacchiani, V.; Caprara, A.; Toth, P. A column generation approach to train timetabling on a corridor (2008). https://doi.org/10.1007/s10288-007-0037-5
Cacchiani, V. et al. An overview of recovery models and algorithms for real-time railway rescheduling (2014). https://doi.org/10.1016/j.trb.2014.01.009
König, E. A review on railway delay management (2020). https://doi.org/10.1007/s12469-020-00233-1
Yan, F.; Bešinović, N.; Goverde, R. Multi-objective periodic railway timetabling on dense heterogeneous railway corridors (2019). https://doi.org/10.1016/j.trb.2019.04.004