リサーチ・ダイジェスト

KR-026

列車ダイヤの頑健性の評価とアルゴリズムに関する海外研究の動向調査
千葉工業大学情報科学部情報工学科教授

富井 規雄

１．はじめに
近年、特に大都市の鉄道においては、わずかな乱れであっても、それが他の列車に伝播し、結果的に多数の列車に遅延が波及することが問題となっている。そのために、鉄道会社では、たとえば、急行列車を各駅停車に格下げして混雑度の平準化を図り、乗降による遅延がなるべく発生しないようにするなどの手段をとっている。しかし、これらの手段は、経験的にあみだされてきたものであり、理論的裏付けには乏しい。
一方、近年、ヨーロッパでは、上下分離、すなわち、公的機関が保有するインフラの上で、各鉄道運営会社が商業ベースで列車を運行するという図式が定着しており、そのような環境においては、高品質の運行計画を作成することが重要な課題として認識されるようになってきた。
このような事情を背景に、EC(European Commission) では、ARRIVAL（Algorithms for Robust and online Railway optimization:
Improving the Validity and reliAbility of Large scale systems）と称する特別プロジェクトを立ち上げ、大学等に対して、運行計画の高度化アルゴリズムの研究に対する補助を盛んに行なっている。その中では、乱れに強い頑健な列車ダイヤに関する研究論文が多数発表されている。これらの多くは、確率論をはじめとする理論的モデルに基づいているのが特徴である。
本調査研究は、上記 ARRIVAL の成果として公表されている論文を中心として、ヨーロッパにおける列車ダイヤの頑健性の評価とアルゴリズムに関する最新の研究動向を調査・分析し、日本の鉄道の発展に資することを目的とする。

２．調査研究の背景
２．１

日本の事情

日本の鉄道は、世界に冠たる定時運行性をもって知られている。しかし、大都市圏においては、特にラッシュ時の列車の遅延や、直通運転が行なわれている路線区間での遅延の波及が問題になっている。
列車の遅延が問題になる背景には、次のような事情があると考えられる。
①

乗換案内情報提供システム等の普及による定時運行への強い要求の出現「えきすぱあと」、「駅前探検倶楽部」等の乗換案内情報提供システムの普及により、目的地までの経路情報が列車の時刻情報も含めて、簡単に検索できるようになった。このため、列車が時刻通りに運転されていないために案内上では接続している列車に乗れないなどの事態が発生した場合、利用者から鉄道会社に対して、強い苦情が寄せられるようになった。

②

直通運転の増加による遅延の波及度合いの増大
特に首都圏においては、複数の線区・会社線をまたがって列車が運転されるケース（直通運転）が多くなっている。直通運転は、従来からも見られた運転形態であるが、近年、その規模（距離）が大きくなる傾向がある。例えば、JR 東日本の湘南新宿ラインでは、宇都宮線・高崎線と横須賀線・
17

KR-026

リサーチ・ダイジェスト

東海道線をそれぞれ結ぶ運転が行なわれている。また、東急田園都市線中央林間から半蔵門線を経由して東武伊勢佐木線久喜駅や日光線南栗橋までに至る直通運転が行なわれている。このような長距離、3 以上の線区・会社をまたがる直通運転が増えると、事故が起こった時のダイヤ乱れの影響範囲も増加する。このような事情から、「ちょっとした事故ですぐにダイヤが乱れる」という苦情が出ている。
③

輸送力の確保を念頭においたダイヤ設定から、現実に守ることのできるダイヤ設定へとする事業者の意識の変化
従来は、混雑率をある目標値以下にするために必要な輸送力（列車本数等）を算出し、その本数の列車の運転を実現するために、それらの列車を、いわばむりやり設定するという考え方がなかったとは言えない。結果として、実際に列車を運行する場面にあっては、ちょっとしたダイヤ乱れであっても、それが多数の列車に伝播するという現象が見られることがあった。しかし、最近になって、「紙の上でのみ成立するダイヤではなく、設定された時刻通りに列車が走れるダイヤ」にしようという考えを持つ事業者が現れつつある。

このような事情から、日本の鉄道会社においては、列車ダイヤの頑健性に強い興味が持たれつつある。
２．２

ヨーロッパの事情

ヨーロッパにおいても、列車の定時運行に関して、強い興味が持たれるようになっている。その理由
は、列車の運行管理は、政府等から多額の補助金を受けているインフラ会社が担当しており、それらの会社は、列車の定時運行率等について政府等と契約を結んでいるからである。目標とされた定時運行率を達成できない場合には、ペナルティ（罰金）を科されることもある。
このような事情から、ヨーロッパ（具体的には、EC 加盟国）においては、列車の定時運行率を改善することに強い関心が持たれ、精力的に研究がなされている。

３．日本におけるこれまでの研究の概要とヨーロッパの事情との相違
３．１

ヨーロッパの事情との相違

ヨーロッパと日本には、次のような点で事情の相違がある。
①ヨーロッパでは、上下分離政策がとられており、運行管理は、政府等から補助を受けているインフラ会社が行なっている。政府等とインフラ会社との間には、定時運行率に関する契約（「α % 以上の列車の遅延をβ分以下にする」など）がある。前述のように、契約した目標に達しない場合には、罰金等のペナルティを課せられることがある。
②配線、特に、ターミナル駅周辺の配線やその使用方が日本と比較して、非常に複雑である。ターミナル駅には、多数の線路が集中し、また、ほとんどの路線では単線並列運転が可能となっている。
そのために、日本でいう交差支障（の大規模なもの）が発生することが多く、それが他の列車の遅れ（knock on delay）を誘発しやすい。
③線区あたりの列車本数、乗客の数は、日本に比べると、非常に少ない。
④一般論としては、「鉄道」では、郊外からの通勤が主（都市内は、地下鉄・トラムなど）で、日本
18

リサーチ・ダイジェスト

KR-026のように 3 つ以上の線区を乗り継いで都心まで行くという利用は、主流ではない。
⑤通勤時間帯と言えども、「着席」が基本となっている。
日本では、①については、定時運行率はもちろん重要視されている（日本では、定時運行率ではなく、平均遅延という形で表現されることが多い）が、③との関連（日本では、乗客の数が非常に多い）から、単純な遅延ではなく、利用者への迷惑をあわせて考慮する必要がある。
②については、日本でももちろん交差支障が発生する駅は少なくないが、配線は、ヨーロッパの大駅とくらべるとはるかに単純である。また、線路や番線の使用方もヨーロッパと比べるとはるかにシンプルである。   という相違がある。   ヨーロッパの研究成果を参考にするにあたっては、このような日本固有の事情を常に念頭におき、それらを踏まえた上で、日本の事情にあった研究を行なうことが重要である。
３．２

日本におけるこれまでの研究の概要

日本における、列車ダイヤの頑健性に関する研究例は、あまり多くなく、主なものは、次のみである。
[1] 武内陽子，富井規雄：「鉄道の運行計画の頑健性評価に関する考察」，電気学会交通・電気鉄道研究会，TER-03-40，2003 年 7 月 .
[2] 武内陽子，富井規雄：「鉄道の計画ダイヤの頑健性評価」，J-RAIL’2003，鉄道技術連合シンポジウ
ム講演論文集，2003 年 12 月 .
これらの研究は、日本の鉄道の事情を反映して、次のような手順で列車ダイヤの頑健性を評価しようとしている。
・確率的列車運行ネットワークと称する概念を導入し、実際の場面を考慮した時に不可欠である、ダイヤ乱れや列車運行の確率的な側面を取り扱っている。
・頑健性の評価尺度として、遅延ではなく、利用者が被った不便さ（不効用）の期待値を用いている。

４．調査対象論文の選定方法（1）対象とする論文は、EC の ARRIVAL プロジェクトにおいて報告されている論文のうち、頑健性をテーマとして扱ったものを選び出した。また、最新の話題をなるべくカバーするために、2009 年
2 月に行なわれた国際会議 RailZurich2009（Third International Seminar on Railway Operations
Modelling and Analysis）から頑健性に関する論文を選んだ。
（2）この分野の草分けである、M. Carey の 1999 年の論文を加えた。M. Carey は、鉄道の operation
分野のアルゴリズムに長らく関わってきた大御所的存在で、1999 年の論文は、調査した限りでは、
19

KR-026

リサーチ・ダイジェスト

robustness に取り組んだ最初の論文であると思われる。

５．調査結果のまとめ
V ほとんどの研究で、現実のデータ（線形や列車ダイヤなど）を用いており、いわゆる実験室的な単純な状況を対象とした研究はほとんど見られない。このことから、研究を進めるにあたって実現可能性が強く意識されていることがうかがわれる。また、鉄道会社の積極的な協力があることを感じさせる。
列車の駅での着発の実績時刻データはもちろんであるが、列車の駅間での動きを GPS を用いてとV

らえ、それを用いて頑健性を検討しようとする研究がある。このことは、単に駅での着発だけではなく、駅間の動きまでもコントロールして頑健性を議論しようとする、これまでになかった動きを感じさせる。
頑健性の評価尺度としては、遅延を用いるものが多い。一方、利用者の利便性の低下を直接扱ってVいる論文は見られない。
単にシミュレーションして頑健性の評価をして終わるというよりは、対象とする問題を組み合わせV最適化問題の範疇の問題ととらえて、頑健性を改善するためのダイヤを作るなどといった構成的な研究が目立つ。
列車が駅でどの番線を使用するのかが頑健性に与える影響、鉄道のネッV 列車を増発する時の頑健性、トワークとしての頑健性など、一口に「頑健性」といっても、多岐にわたって、さまざまな研究がなされている。

６．調査対象論文一覧
各論文の概要については、報告書の本編に記す。
1） Ex ante heuristic measures of schedule reliability, Malachy Carey, Transportation ResearchPart B, Vol.33, pp.473-494, (1999).
2） On the Interaction between Robust Timetable Planning and Delay Management, Serafino
Cicerone, Gianlorenzo D’Angelo, Gabriele Di Stefano, Daniele Frigioni, Alfredo Navarra, 2nd
Annual International Conference on Combinatorial Optimization and Applications (COCOA'08),
St. John’s, Newfoundland, Canada, August 21-24, 2008.
3） Robust Train Routing, Leo Kroon, Gábor Maróti, Technical Report of ARRIVAL-TR-0123, 2008.
4） Stochastic Improvement of Cyclic Railway Timetables, Leo Kroon, Rommert Dekker, GáborMaróti, Transportation Research Part B: Methodological, Vol. 42, No.6, Pages: 553-570, 2008.
5） Computing Delay Resistant Railway Timetables, Christian Liebchen Michael Schachtebeck,Anita Schöbel Sebastian Stiller André Prigge, Technical Report of ARRIVAL -TR-0071, 2007.
6） Recoverable Robustness, Christian Liebchen, Marco Lübbecke, Rolf H. Möhring, SebastianStiller, Technical Report of ARRIVAL - TR-0066, 2007.
7） Evaluating Robustness of a Urban Railway Network, Alicia De-Los-Santos, Juan A. Mesa,20

リサーチ・ダイジェスト

KR-026

Federico Perea (Departamento de Matemática Aplicada II. Universidad de Sevilla. Sevilla.
Spain), Third International Seminar on Railway Operations Modelling and Analysis:RailZurich2009.
8） Recoverable-Robust Timetables for Trains on Single-Line Corridors, Gianlorenzo D’Angelo,
Gabriele Di Stefano, Alfredo Navarra, Department of Electrical and Information Engineering,
University of L’
Aquila., Department of Mathematics and Informatics, University of Perugia.
Third International Seminar on Railway Operations Modelling and Analysis: RailZurich2009.
9） Finding Robust Train Paths in Dense Corridors, Holger Flier Thomas Graffagnino Marc
Nunkesser, ETH Zürich, Institute of Theoretical Computer Science, Switzerland, SBB AGBern, Infrastruktur/Trassenmanagement, Switzerland, Third International Seminar on
Railway Operations Modelling and Analysis: RailZurich2009.
10）Recovery-Robust Platforming by Network Buffering, Alberto Caprara, Laura Galli, SebastianStiller, Paolo Toth, Third International Seminar on Railway Operations Modelling and Analysis:RailZurich2009.
11）Railway Timetable Stability Analysis Using Stochastic Max-Plus Linear Systems Rob M.P.
Goverde, Bernd Heidergott, Glenn Merlet, Delft University of Technology, Department
Transport & Planning, Third International Seminar on Railway Operations Modelling andAnalysis: RailZurich2009.
12）Stochastic micro-simulation as a timetable robustness estimation tool Daniel Huerlimann,Giovanni Longo and Giorgio Medeossi, OpenTrack Railway Technology Ltd, Zurich, Third
International Seminar on Railway Operations Modelling and Analysis: RailZurich2009.

21