混合整数計画法による旅客の視点を考慮した運転整理アルゴリズム (指導教員富井規雄教授) 富井研究室 1281025 田村啓現れ，計算時の処理時間の短縮へと繋がっている。 1 はじめに鉄道において，事故等によって列車の定時運転が妨げられたとき， o,d zt,r ≤ 「運転整理」と呼ばれる列車ダイヤの調整業務が行われる。運転整理案の作成業務は，設備や安全運行上の厳しい制約を満たした複雑な調整案を速やかに作成することを要求されるため，鉄道事業者にとって大きな負担となっている。そのため，計算機による運転整理 dor t ∀b ∈ B∀(o, d) ∈ Sb2 ∀t ∈ T ∀r ∈ Rb 上記の式 (2) に相当するものは既存研究 [5] にも見られるものだが、各旅客が自身の出現時刻以前に発車してしまう列車には乗車できないことを表している。本研究で作成した数理モデルにはこのような物理的制約を表す式が多数あり，同一番線の使用間隔を空ける案作成の支援が強く望まれている。運転整理案の作成にあたっては，利用者の視点からの評価が重要である。従来，列車の遅延に着目した運転整理案が提案されていたが，遅延は，列車を運休すれば 0 になるなど，利用者の視点からの評価指標としては適切ではない。運転整理案の作成アルゴリズムについては，これまで多くの研究成果が報告されている [1]。それらは，メタヒューリスティクスを用いるもの [2][3]，混合整数計画法に基づくもの [4][5] に大別される。しかし，メタヒューリスティクスを用いる研究では，得られた運転整理案が最適解であるという保証がないだけでなく，最適解にどの程度近いか（遠いか）も不明であるという問題がある。また，混合整数計画法によるアルゴリズムには，処理時間を要するという問題がある。特に，旅客の行動を扱おうとすると問題が複雑になる。そのため，文献 [4] では，旅客の行動について強い仮定が置かれている。また，文献 [5] は，上りと下りの線路が完全に分離した路線の片方向のみを対象としているため列車の折り返し運転を再現することができない，旅客が列車を乗り換える回数を 1 回に限定しているため旅客が列車を複数回乗り換える経路を再現することはできない，実現可能な運転整理手段が限定されているなどの点で課題を残している。制約や，車両を列車へと割り当てる制約などがこれにあたる。 o,d zt,r ≤ 1 − lr,e ∀b ∈ B∀(o, d) ∈ Sb2 ∀t ∈ T ∀r ∈ Rb ∀e ∈ E (3) 上記の式 (3) は各旅客が自身の目的駅へと到達する経路を持たない列車には乗車しないことを表している。この式と先ほど述べた式 (1) の制約を同時に加味することで，本研究の数理モデルは，全ての旅客がそれぞれ自身の目的駅へと到達できる列車を 1 つ選択する動作を表現することができる。このように本研究で作成した数理モデルは，制約式を組み合わせることで物理的制約を守った運転整理案の導出や，無駄を削減することで処理時間を考慮した効率の良い計算が可能となっている。 4 目的関数本研究の数理モデルで使用した目的関数について説明する。 (乗車時間) + α ∗ (駅での待ち時間) + β ∗ (乗り換え回数) 本研究では，旅客の感じる不便度を文献 [7] で定められている式から求め，旅客 1 人あたりの損失を遅延発生時の不便度から平常時における不便度を差し引いた値とし，下限値を 0 としている。ここで，遅延発生時の不便度を直接旅客 1 人あたりの損失とせず， 2 研究目的本研究は，旅客の損失を最小化することを目的として，最適性が保証された運転整理案を生成するアルゴリズムを導入することを目的とする。鉄道モデルを旅客の視点と列車の折り返し運転を考慮した数理モデルで表現し，混合整数計画法で解くことで，既存研究 [5] では実現されていない列車の折り返し運転を含むダイヤに対して，旅客のデマンドを反映した運転整理案を作成する。平常時の不便度との差を旅客 1 人あたりの損失としている理由は，遅延発生時の運転整理ダイヤによっては普段よりも不便度が減少する旅客が発生するからである。本研究の目的は，列車の遅延の影響を受けて旅客が被る損失を最小化することであるため，下限値を 0 とすることで，遅延によりかえって得をした旅客は評価の対象外としている。本研究の数理モデルにおける目的関数は，出現時刻・出現駅・目的 o,d 駅を同じとする旅客の人数を表す Pt 3 鉄道モデルの数理モデル化たりの各列車に乗った場合の損失本研究で作成した数理モデルについて，旅客行動を表す制約式の中から式を抜粋して説明する。なお，他の式の詳細な説明は紙面の minimize 都合上省略する (詳細な説明は文献 [6] を参照)。 ∑ ∑ o,d yt,r ∑ とそれに対応する旅客 1 人あを用いて式 (4) で表される。 Pto,d ( b∈B (o,d)∈Sb2 t∈T ∑ o,d zt,r =1 (2) ∀b ∈ B∀(o, d) ∈ Sb2 ∀t ∈ T (1) r∈Rb 上記の式 (1) は各旅客が最初に乗る列車をそれぞれ１つしか選択できないことを表している。ここで各旅客が選択する対象を経路ではなく列車と表現した理由は，本研究で作成した数理モデルでは，旅客が選択する対象は最初に乗る列車のみであるという体をとっているからである。それ以降の列車の乗り換えなどの経路選択については，各列車から見た各駅への最短経路 (乗り換え含む) を参照させこのような無駄の削減は数理モデル上では変数の削減といった形で o,d yt,r ) (4) r∈Rb この式 (4) は発生した遅延により旅客の被る不便度を最小にすることを意味する。以降，本稿において式 (4) の目的関数で作成したダイヤを旅客損失最小ダイヤと呼び，この式 (4) を旅客損失総和最小化 (PDP) と呼ぶ。また，本研究の数理モデルは，入力として単純に列車の (到着) 遅延の総和を最小化したダイヤが必要である。本研究では，この入力として式 (5) を目的関数として計画ダイヤにおける着時刻と遅延時の時刻の差が最小化されたダイヤを得る。ることにより，同じ駅を目的駅とする同じ列車に乗り合わせた複数の旅客の経路をそれぞれ個別に選択させるような無駄を省いている。 ∑ minimize ∑ ∑ ∑ (asr − Asr ) (5) b∈B r∈Rb s∈S\Sbstart 以降，本稿において式 (5) の目的関数で作成したダイヤを列車遅れ最小ダイヤと呼び，この式 (5) を遅延総和最小化 (DMP) と呼ぶ。 5 計算手順本研究では，旅客損失を最小にする運転整理の解法として，次の手順で運転整理案を作成する。 • Step1：(計画ダイヤにおける旅客不便度計算) 所定ダイヤと旅客の出現時刻から平常時における旅客の不便度を計算する。 • Step2：(遅延最小化) ダイヤ乱れ情報を数理モデルに入力として与え，(DMP) を解くことで，列車遅れ最小ダイヤを得る。 • Step3：(旅客損失最小化) 列車遅れ最小ダイヤで得られた着発時刻に許容変更幅 IM ax を図2 足した値を着発時刻の上限値として新たに数理モデルの制約と列車遅れ最小ダイヤ (DMP) して加え，(PDP) を解くことで，旅客損失最小ダイヤを得る。 6 計算機実験本研究で作成した数理モデルを仮想のダイヤに適用して，その有用性を検証した。実験には，CPU が Core i7-3930K, メモリが 16GB, OS が 64it 版 Windows7 の計算機を用いて，混合整数計画ソルバとしては Gurobi Optimizer 5.5.0 を使用した。 2 時間弱の規模のダイヤを対象として実験を行う。図 1 に計画ダイヤを示す。太線が快速列車，細線が普通列車をそれぞれ表す。また、旅客の OD ペアと出現時刻の組は 569 組である。この所定ダイヤに対して，何らかの理由で列車 2 の A 駅出発が 30 分遅れる場合を考え，(DMP) と，IM ax = 1…15 についての (PDP) を解く。旅図 3 旅客損失最小ダイヤ (PDP) 客不便度のパラメータは文献 [7] に従い α = 2, β = 10 とした。図 2 に (DMP)，図 3 に IM ax = 15 のときの (PDP) の解を示す。 (DMP) の最適解では，A 駅における列車 2 と列車 3，4 の列車との発車順序を入れ替えることで，列車 2 の遅延が後続列車に伝播することを防いでいる。また，E 駅において折り返しを行う列車を変 7 まとめ本研究では，旅客の損失を最小化することを目的として，旅客の視点と折り返し運転を考慮した数理モデルを作成し混合整数計画法更することで折り返し列車への遅延の伝播も防いでいる。しかし，で解くことで，仮想のダイヤや現実の路線を対象に旅客のデマンド DMP ダイヤでは平常時において E 駅から普通列車を利用していた旅客にとっては，列車 13 以降は列車 17 を待つ他なく，不便なダイヤとなっている。(PDP) の最適解では，列車 15 の種別を普通列車のまま走らせることで，平常時において E 駅から普通列車を利用しを反映した運転整理案を作成することができた。ていた旅客のデマンドに対応し，ダイヤ全体の旅客損失を低下させている。実験の結果，旅客損失最小ダイヤでは，列車遅れ最小ダイヤでは見られない旅客の視点を考慮した運転整理がダイヤから見て取れた。それぞれのダイヤの旅客損失を式 (1) で数値化すると，列車遅れ最小ダイヤでは 4501 であったのに対し，旅客損失最小ダイヤでは 3522 となり，本研究で定義した旅客損失の総和の最小化が確認できた。また，最適解の証明も含めて 454 秒で解くことができた。また，他にも駅数 8，列車本数 21，OD と出現時刻の組数 1511 組のダイヤを対象として同様の実験を行い，有用性を確認できた。今後の課題として列車の混雑率を考慮する必要がある。参考文献 [1] J. T¨ornquist: Computer-based decision support for railway traﬃc scheduling and dispatching: A review of models and algorithms, ATMOS 2005 (2005) [2] 富井規雄他: 利用者の不満を最小にする列車運転整理アルゴリズム，情処論. 数理モデル化と応用 46(TOM11), (2005). [3] A. D’Ariano and M. Pranzo: An advanced real-time train dispatching system for minimizing the propagation of delays in a dispatching area under severe disturbances, Proceedings of RailHannover07, Hannover (2007) [4] A. Sch¨obel: Optimization in Public Transportation. Springer (2006) [5] 千種健二，佐藤圭介，古関隆章：「混合整数計画法に基づく列車運行乱れ時の旅行時間増大量に主眼を置いた運転整理最適化」，図1 所定ダイヤ電学論Ｄ，Vol.132，No2，pp170-177 [6] K.Tamura，N.Tomii，K.Sato：An optimal rescheduling algorithm from passengers’viewpoint based on mixed integer programming formulation，5th International Seminar on Railway Operations Modelling Analysis，(2013) [7] 国土交通省鉄道局 (監修)，鉄道プロジェクトの評価手法マニュアル 2012 改訂版，運輸政策研究機構，東京，2012 [8] 田村啓，佐藤圭介，富井規雄：「混合整数計画法による旅客損失を最小化する鉄道の運転整理と計算時間短縮式」，信学論 D Vol.J97-D,No.3,Mar. 2014.(掲載決定)