電車のダイヤというものを、僕は普段「何時何分に電車が来るか」を記した表としてしか見ていない。駅の掲示板に鎮座している、あの白い紙である。ところが少し数理的な目で眺めてみると、これがなかなか面白い代物なのだ。

ダイヤ作成は、発車時刻を順に並べるだけの作業ではない。線路、駅、信号、ホーム、列車種別、乗客の流れ、乗換、車両、乗務員、遅延リスク。これらを同時に睨みながら、全体として破綻しないスケジュールを誂える作業である。研究の世界では train timetabling problem や railway timetabling problem と呼ばれる。ざっくり言えば、制約付きスケジューリング問題であり、組合せ最適化問題でもある。

さしずめ、ピースの形が互いに干渉しあう巨大なパズルだ。以下、このパズルを数理最適化の問題として見るとどう整理できるのかを、自分用のメモも兼ねてまとめておく（というより、ほぼ自分用である）。

到着時刻と出発時刻を決める問題

そもそもダイヤ作成で決めたいものはなにか。利用者が知りたいのは、A駅を8:00に発車し、B駅に8:03、C駅に8:10に着く、といった情報だ。これを数理的に言い直せば、列車ごとに各駅での到着時刻と出発時刻を決める問題になる。列車を ii、駅を ss とすると、到着時刻と出発時刻は次のように表せる。

ai,s=列車 i が駅 s に到着する時刻a_{i,s} = \text{列車 } i \text{ が駅 } s \text{ に到着する時刻} di,s=列車 i が駅 s を出発する時刻d_{i,s} = \text{列車 } i \text{ が駅 } s \text{ を出発する時刻}

つまりダイヤ作成とは、すべての列車 ii と駅 ss について ai,sa_{i,s} と di,sd_{i,s} を決める問題である。もちろん、好き勝手に時刻を決められるわけではない。駅間の走行時間、駅での停車時間、前後の列車との安全間隔、単線区間でのすれ違い。ホーム容量、待避、折返し、乗換接続と、制約は山のようにある。この制約の多さこそが、鉄道ダイヤを面白くしているのだ。

走行時間と停車時間

もっとも基本になるのは走行時間の制約だ。駅 ss から次の駅 s+1s+1 までの走行時間には下限がある。列車は物理的にそれより速くは走れない。走行時間の下限と上限を [r‾i,s,r‾i,s][\underline r_{i,s}, \overline r_{i,s}] とすると、次のように書ける。

r‾i,s≤ai,s+1−di,s≤r‾i,s\underline r_{i,s} \le a_{i,s+1}-d_{i,s} \le \overline r_{i,s}

下限は最低限必要な運転時間、上限は余裕時分を含めた許容時間と考えればよい。次に、駅での停車時間がある。列車が駅に着けば、乗客の乗り降り、ドア扱い、安全確認が要る。混雑駅なら停車時間はさらに延びる。停車時間の下限と上限を [w‾i,s,w‾i,s][\underline w_{i,s}, \overline w_{i,s}] とすると、次のようになる。

w‾i,s≤di,s−ai,s≤w‾i,s\underline w_{i,s} \le d_{i,s}-a_{i,s} \le \overline w_{i,s}

停車時間は、単なるサービス上の条件ではない。ホームを占有している時間でもある。停車が長くなれば、その駅に後続列車を入れにくくなる。とりわけ高頻度運転では、駅での停車時間が全体の容量を決めてしまうこともある。

ヘッドウェイと線路容量

鉄道では、同じ線路の上を複数の列車が走る。だから前後の列車の間には安全間隔が必要で、これはよくヘッドウェイと呼ばれる。同じ区間 (s,s+1)(s,s+1) を列車 ii が先に、列車 jj が後から走るとしよう。このとき、出発時刻と到着時刻には最低間隔が課される。

dj,s−di,s≥hij,sdepd_{j,s}-d_{i,s}\ge h^{\mathrm{dep}}_{ij,s} aj,s+1−ai,s+1≥hij,sarra_{j,s+1}-a_{i,s+1}\ge h^{\mathrm{arr}}_{ij,s}

ところが実際のモデルでは、どちらの列車が先に走るかも決めなければならない。そこで0-1変数を使うことが多い。xij,s=1x_{ij,s}=1 なら列車 ii が先、xij,s=0x_{ij,s}=0 なら列車 jj が先、と置くわけだ。

dj,s−di,s≥hij,sdep−M(1−xij,s)d_{j,s}-d_{i,s}\ge h^{\mathrm{dep}}_{ij,s}-M(1-x_{ij,s}) aj,s+1−ai,s+1≥hij,sarr−M(1−xij,s)a_{j,s+1}-a_{i,s+1}\ge h^{\mathrm{arr}}_{ij,s}-M(1-x_{ij,s})

ここで MM は十分大きな数である。このあたりから、ダイヤ作成はにわかに組合せ最適化の顔をしはじめる。何分に出すかだけでなく、どの列車を先に通すかも同時に決めなければならないからだ。

共有資源としての線路

もう少し一般化してみる。線路、閉塞区間、分岐器、駅構内の進路は、一定時間だけ列車に占有される資源だと見なせる。ある資源 bb を列車 ii が [ui,bin,ui,bout][u_{i,b}^{\text{in}},u_{i,b}^{\text{out}}] の間占有するとき、別の列車 jj も同じ資源を使いたいとする。ならば、どちらかが先に抜けなければならない。

uj,bin≥ui,bout+τborui,bin≥uj,bout+τbu_{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

式は物々しいが、言っていることはごく直感的だ。同じ線路区間、同じ進路、同じホームを、複数の列車が同時に使うことはできない。鉄道ダイヤとは、時間軸の上でこうした共有資源をどう割り当てるかの問題でもあるのだ。

単線区間になると、話はさらに難しくなる。単線では上下の列車が同じ線路を逆向きに使う。片方が区間を抜けてからでないと、もう片方は入れない。上下列車 ii と kk が同じ単線区間 ℓ\ell を使うとしよう。二値変数 yik,ℓy_{ik,\ell} を使えば、こう書ける。

enterk,ℓ−leavei,ℓ≥τℓ−M(1−yik,ℓ)\text{enter}_{k,\ell} - \text{leave}_{i,\ell} \ge \tau_\ell - M(1-y_{ik,\ell}) enteri,ℓ−leavek,ℓ≥τℓ−Myik,ℓ\text{enter}_{i,\ell} - \text{leave}_{k,\ell} \ge \tau_\ell - M y_{ik,\ell}

単線では、交換駅や信号場の位置がきわめて重要になる。どこで行き違わせるかで、ダイヤ全体の形ががらりと変わるからだ。時刻表だけを眺めていてもまず気づかない。単線区間のダイヤは、パズルの中でもとりわけ繊細な一角なのである。

駅という詰まりどころ

線路の上だけでなく、駅もボトルネックになる。ある駅にホームが2本しかなければ、同時に扱える列車の数には限りがある。そこで、時刻 tt にプラットフォーム pp を同時に使う列車数が、容量 Cs,pC_{s,p} を超えないようにする。

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

高頻度運転では、線路そのものより先に駅の処理能力が詰まることもある。駅で列車が長く停まれば、ホームが空かない。ホームが空かなければ次の列車を入れられず、後続へと遅れが波及していく。

要するに、鉄道の容量は線路が何本あるかだけでは決まらない。信号、閉塞、ホーム、分岐器、停車時間、列車種別の混在まで含めて、ようやく決まるのである。線路の本数だけ数えて安心するのは、いささか早計というわけだ。

急行と各停の混在

鉄道ダイヤでとりわけ面白いのが、急行と各駅停車の混在だ。各停は多くの駅に停まるので、どうしても所要時間が長くなる。一方の急行は途中駅を通過するので速い。この2種類を同じ線路で走らせれば、案の定、速いほうが遅いほうに追いついてしまう。

そこで必要になるのが待避や追越しである。各停が先を走り、後ろから急行が来るなら、待避設備のある駅で各停を停めて急行を先に通す。数理的には、列車の順序が途中の駅で入れ替わることを意味する。区間 (s−1,s)(s-1,s) では各停が先だったのに、駅 ss で待避した結果、区間 (s,s+1)(s,s+1) では急行が先になるわけだ。

こうした順序反転を許せる駅が待避駅であり、待避設備のない場所では順序を入れ替えられない。したがって急行と各停の違いは、単なる所要時間の差にとどまらない。列車同士の順序制約を増やす差でもあるのだ。急行を増やせば速達性は上がるが、そのぶん各停の待避が増え、線路容量も食う。ここにもトレードオフが潜んでいる。

乗換接続

乗換接続もまた、制約の一つになる。駅 ss で列車 ii から列車 jj へ乗り換えさせたいとしよう。乗換に必要な最低時間を τij,str\tau^{\text{tr}}_{ij,s} とすれば、次の制約になる。

dj,s−ai,s≥τij,strd_{j,s}-a_{i,s}\ge \tau^{\text{tr}}_{ij,s}

列車 jj は、列車 ii が到着してから乗換に必要な時間が経つまで出発できない、ということだ。地方路線や終電では、この接続がとりわけ重要になる。かといって、接続を守るために列車を待たせれば、その遅れが後続へ波及することもある。接続を守るか、定時性を守るか。これもダイヤ作成の悩ましいところである。

良いダイヤとはなにか

制約を満たすダイヤは一つとは限らない。そこで、なにをもって良いダイヤとするかを目的関数として定める必要がある。旅客の総待ち時間や乗換待ち時間、総移動時間は小さくしたい。必要車両数や運行コストも抑えたい。

混雑は平準化したいし、遅延には強くしたい。既存ダイヤからの変更量も、なるべく小さくしたい。候補はいくらでも出てくる。我ながら欲張りな注文書である。

しかし、これらは同時に満たせるとは限らない。本数を増やせば待ち時間は減るかもしれないが、車両や乗務員のコストは嵩む。急行を増やせば速達性は上がる反面、各停の待避が増えて全体としてはかえって不便になることもある。余裕時分を増やせば遅延には強くなるが、所要時間は延び、線路容量も圧迫される。

あちらを立てればこちらが立たない、というやつだ。思い切り単純化すれば、目的関数は次のように書ける。

min⁡  α⋅旅客時間+β⋅運行コスト+γ⋅遅延・脆弱性+δ⋅既存ダイヤからの変更量\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では、各イベント ii に周期 TT 内の時刻 πi\pi_i を与え、活動 (i,j)(i,j) ごとに次の制約を満たすようにする。

lij≤πj−πi+Tpij≤uijl_{ij}\le \pi_j-\pi_i + T p_{ij}\le u_{ij}

ここで lij,uijl_{ij},u_{ij} は最小・最大の時間差、pijp_{ij} は周期をまたぐことを許す整数変数である。

周期ダイヤのありがたいところは、1時間や30分といった1周期ぶんを設計すれば、それを一日に展開できることだ。毎時同じ分に列車が来るダイヤは利用者にとって分かりやすく、接続もそろえやすい。もっとも、需要が時間帯で大きく変わるなら、完全な周期ダイヤはかえって非効率になることもある。そのため現実には、周期的なパターンをベースにしつつ、ピーク時だけ増発する形が多い。

ダイヤの外側

ダイヤを作ればめでたく終わり、とはいかない。実務では、ダイヤは車両運用や乗務員運用の入力になる。ある列車が終点に着いたあと、同じ車両が次の列車として折り返すことがある。折返しに必要な時間を τij,uturn\tau^{\text{turn}}_{ij,u} とすれば、次の制約が加わる。

dj,u−ai,u≥τij,uturnd_{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