TER-18-039 PHS-18-014
混合整数計画法に基づくグラフの最小費用流求解による
列車待避を考慮した高頻度運転区間の効率的設備増強策
粟木一輝 古関隆章（東京大学）
Optimized infrastructure design for frequent mixed urban train service ― as a cost-flow minimization based on mixed integer linear programing
Kazuki Awaki, Takafumi Koseki (The University of Tokyo)
To reduce congestion and travel time in urban railways, a fundamental solution by enhancing infrastructure is necessary. In this paper, we propose a method for infrastructure enhancement and operation plan with taking refuge of local trains by expanding the minimum cost flow problem on a rectangle diagram presenting difference of traveling time of slower trains between slow and rapid trains. Furthermore, we evaluate the proposed method through case study of urban railroad.
キーワード：高頻度運転, 運行計画, 設備計画, 都市鉄道, 最小費用流問題, 混合整数計画法
(High frequency operation, Operation plan, Infrastructure plan, Urban railways, Minimum cost-flow problem, Mixed integer programming)
1. はじめに 都市鉄道において，慢性的な混雑が課題となっている(１)。 本研究では，駅間を含めて区間的に設備を増設することで， 高頻度運行の実現および急行の導入による高速化を実現す る都市鉄道計画法を考える。 従来の手法(２)では全区間の工事が必要であり建設時間や 費用がかさむという課題がある．さらに，一度に多区間で設 備増強を行うことは困難である．一方，列車計画を考慮せず 順次設備増強を行うと，列車計画上のボトルネックを残し たまま建設が進み，部分建設を行った後の利便性の向上が 少なくなるという課題が生じる。 そこで，本論文では，高頻度運転区間に急行列車を導入す るための列車時刻計画およびこれを実現する最小設備計画 の手法を論ずる。以前の研究では，緩行および急行が全ての 駅を最速で発車するという条件のもと，急行の停車駅を決 定する手法を提案した(３)。しかし，この手法では，列車の停 車時分の調整が行われない．そのため，旅客の利便性が高い 停車駅において，設備費用が高い区間を回避できずにこの 計画が選択されないという問題があった。 本論文では，急行の停車駅が決まっているという条件下 で，緩行の停車時分および急行の駅間走行時間を調整する 具体的方法論を記述する。この手法を用いることで，利便性 の高い急行の停車駅を増やすことなく，設備増強区間の調 整を行うことが可能である。 2. 効率のよい計画に向けた前提条件と評価指標 〈2･1〉 設計する計画の前提条件 本手法では，利用率 の低い設備や運行上のボトルネックとなる箇所が生じない ように，設備および列車計画に制約を課す。 設備増強は，駅・駅間の単位で行うという制約を課す。駅間 において一方向の線数を増やす場合，その箇所において転 轍機を敷設する必要がある。この転轍機を分岐側に移動す る場合には速度制限が生じる．これによって，後続列車との 間隔が他の箇所より短くなる。このように，駅間での転轍機 は列車計画上のボトルネックとなる。一方，駅付近では分岐 側に移動する列車はすでに減速しているため，この影響が 少ない。そこで，転轍機は駅前後のみに設置するため，設備 増強は駅単位で行う必要がある。 列車時刻には，急行と緩行を1:1 で計画し，これを 1 周期 𝑇𝑐𝑖𝑟𝑐𝑙𝑒とする列車計画を行うという制約を課す。これによ り，急行と緩行の追越が周期ごとに同じ区間において発生 する。そのため，多種別による運行と比較して，追越設備の 利用率を高めることが可能である。 〈2･2〉 旅客不効用の定義 旅客不効用𝑇𝑐𝑜𝑠𝑡は，旅客が 移動の際に感じる不便さを時間に換算した評価値である。 この値としては，移動時間，乗換による不便さ，混雑による 不快さの3 つを用いる。 移動時間𝑇𝑡𝑟𝑎𝑣𝑒𝑙は，全旅客の移動時間の和である。乗換によ る不便さ𝑇𝑡𝑟𝑎𝑛𝑠𝑓𝑒𝑟は，乗換1 回につき𝜔 [分]として，乗換回 数に乗じて計算する。混雑による不効用𝑇𝑐𝑜𝑛𝑔𝑒𝑠𝑡𝑖𝑜𝑛は，混雑 率𝑟によって乗車時間 1 分に感じる不効用を表す混雑不効用
これらを用い，旅客不効用は 𝑇𝑐𝑜𝑠𝑡= 𝑇𝑡𝑟𝑎𝑣𝑒𝑙+ 𝑇𝑡𝑟𝑎𝑛𝑠𝑓𝑒𝑟+ 𝑇𝑐𝑜𝑛𝑔𝑒𝑠𝑡𝑖𝑜𝑛 (1) と定義される。評価においては，全旅客に生じる不効用の和 の１分あたりの平均値を𝑡𝑐𝑜𝑠𝑡[人・分/分]によって表現する。 つまり，旅客不効用の集計対象とした時間を𝜏とすると， 𝑡𝑐𝑜𝑠𝑡= 𝑇𝑐𝑜𝑠𝑡/𝜏である。 〈2･3〉 旅客の経路選択方法 旅客不効用を求めるため には，各旅客の移動方法を考慮する必要がある。本研究で は，駅に到着した時刻において，その旅客の移動時間𝑇𝑡𝑟𝑎𝑣𝑒𝑙 と乗換不効用𝑇𝑡𝑟𝑎𝑛𝑠𝑓𝑒𝑟の和が最も少なくなる移動経路を取 るとした。 移動経路の選択においては，混雑不効用は考慮しない。これ は，旅客は，未来の列車の混雑率の余地はできないためであ る。通勤客が普段の混雑を記憶し，回避する行動をとる可能 性はあるが，全旅客がこのような行動をすると仮定するこ とは現実的ではない。このため，目的関数からは除外した。 〈2･4〉 設備費用の定義 設備費用𝐶𝑖𝑛𝑓𝑟𝑎は，必要とな る最小な設備を建造するための費用を示す評価指標であ る。全ての区間を独立に設備増強を行った場合の費用の合 計が全設備増強費用と等しいと仮定し，この和を評価値と して用いる。設備費用は，ある駅𝑠での費用を𝑐𝑠𝑡𝑎𝑡𝑖𝑜𝑛(𝑠),駅𝑠 から𝑠 + 1の区間での費用を𝑐𝑠𝑒𝑐𝑡𝑖𝑜𝑛(𝑠)としたときに，これら の和によって計算される。さらに，転轍機の費用として線路 増強を行う区間の前後において費用𝑐𝑐𝑟𝑜𝑠𝑠を加算する。その ため，建造が必要な駅の集合を𝐒𝐭𝐚，区間の集合を𝐒𝐞𝐜とし， 転轍機数を𝑛𝑐𝑟𝑜𝑠𝑠とすると，設備費用𝐶𝑖𝑛𝑓𝑟𝑎は 𝐶𝑖𝑛𝑓𝑟𝑎= ∑ 𝑐𝑠𝑡𝑎𝑡𝑖𝑜𝑛(𝑖) i∈𝐒𝐭𝐚 + ∑ 𝑐𝑠𝑒𝑐𝑡𝑖𝑜𝑛(𝑖) 𝑖∈𝐒𝐞𝐜 + 𝑛𝑐𝑟𝑜𝑠𝑠𝑐𝑐𝑟𝑜𝑠𝑠 (2) となる。 3. 損失時間表示ダイヤと最小設備計画 〈3･1〉 損失時間表示ダイヤ(４) 本計画では，曽根によ って提案された，損失時間表示によるダイヤ(４)を用いて列 車計画を行う。このダイヤでは，列車が駅に停車することに より，その駅を通過した場合と比較して必要となる移動時 間や，駅で列車を待つために生じる待ち時間といった損失 時間に着目した列車時刻の設計法である。ある駅に停車し た場合とその駅を通過した場合の所要時間の差を停車損失 時間𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠と呼ぶ。一方，列車間において最低限必要とな る時間間隔を𝑇𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙と呼ぶ。都市鉄道においては，𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠 と𝑇𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙はおよそ 1 分程度で等しいことが知られている (５)。そこで，損失時間を横軸，駅数を縦軸とし，𝑇 𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠と 1 駅ごとにマス目を区切ることによって，図 1 のように方 眼紙上で列車計画が可能である。 〈3･2〉 損失ダイヤ表示を用いた最小設備計画(３) こ の計画において，設備増強が必要となる区間は，列車間隔が 𝑇𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙未満となった場合である。方眼紙上でダイヤを考慮 した場合，このようになるのは，列車ダイヤ同士が図 2 の ように重なりを持つ場合のみである。そこで，このような重 なりを持つ箇所において，図 2 に対応する設備を増強する ことによって，設備計画を行う。 〈3･3〉 損失時間表示ダイヤ上における旅客不効用(３) 旅客の移動時間𝑇𝑡𝑟𝑎𝑣𝑒𝑙は，損失時間ダイヤ上に表示される損 失時間𝑡𝑙𝑜𝑠𝑠と，損失時間ダイヤにおいて差し引いた最短移動 時間𝑡𝑚𝑜𝑣𝑒の2 つの和として考慮することが可能である。こ こで，最短移動時間𝑡𝑚𝑜𝑣𝑒は各列車の停車駅や停車時分によ らない定数となる。そのため，旅客の移動経路や旅客不効用 の最適化という観点からは除外できる。そこで，損失時間ダ イヤ上において損失時間と乗換不効用の和が最小となるよ うな経路を求めることで，旅客の移動経路を求められる。 〈3･4〉 駅間での急行減速の考慮 連続した駅で設備費 用が高額となる場合，急行導入による旅客不効用の改善を 設備費用が上回る場合がある。そこで，文献(５)を参考に， 先行列車により駅間の走行時間が1 ⋅ 𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠延長すること を許容する。この減速の表現には，方眼紙上で斜めに線を引 くことで表現する。ただし，急行の減速は，その区間の前後 の駅において設備増強が生じない場合に限る。この制約下 では，急行が減速する区間での設備増強は生じない。 4. 最小費用流問題応用による緩行列車時刻調整法 緩行の列車時刻の設計問題は，損失時間表示ダイヤ上にお いて，候補となる複数の縦線からどの線を選択するかとい う問題とみなすことができる。そこで，本章では，損失時間 表示ダイヤを一部の辺が消去可能な有向グラフとして表 図 2 損失時間ダイヤの交差パターンと必要設備 (文献(３)より転載)
Fig. 2. Crossing patterns of diagram and their graphical diagram
図 1 一般的なダイヤ(左)と
損失時間表示によるダイヤ(右)の比較(文献(３)より転載)
Fig. 1. Comparison of normal diagram (left) and diagram with loss time (right)
Loss time S ta ti o n 𝑡𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠
す。このグラフ上では，削除可能な辺が緩行の時刻の候補を 表す。このグラフ上で，辺の選び方を変化させ，旅客不効用 および設備費用を最適化することで，最適な緩行の時刻を 選択する手法を示す。 〈4･1〉 最小費用流問題と総費用計算 最小費用流問題 とは，辺に重みが設定されているグラフ上において，頂点間 を一定の流量が移動する際に，流量×重みを最小とする流 れ方を求める問題である。本研究では，この問題を拡張し， 一部の辺を削除可能なグラフにおいて，一定の制約を満た しながら目的関数が最小となるように一部の辺を削除する 条件を追加することで，緩行の時刻を計算する。 旅客流動の計算面では，各旅客は移動時間および乗換不効 用を最小とするようにして移動する。この移動方法の評価 関数は，他の旅客の移動方法にかかわらず定まる。そこで， 損失時間表示ダイヤ上において，各々の格子点を頂点，方眼 を辺としてグラフを設計すると，旅客の人数を流量，横方向 に移動する損失時間および乗換不効用を重みとして設定 し，最小費用流を計算することで，最小な旅客不効用を満た す移動方法を計算できる。 設備条件の計算面では，駅間線増の条件は，駅間において急 行との並走を示す辺が存在する場合に費用を加算する計算 可能である。一方で，駅の条件は，緩行の待避の場合を考慮 すると，単純に辺の費用を考慮したのみでは計算できない。 そこで，本研究では，目的関数の計算について，旅客流動を 計算するためのグラフと，設備費用を計算するためのグラ フに分け，これらを一度に最適化することで，最適な緩行の 時刻を求めた。 この最適化においては，１軸的な評価関数を設定する必要 がある。そこで，一定期間の旅客不効用を考慮し，これを金 銭換算することで，費用軸に合わせて直接計算することと とした。1 人の旅客に 1 分損失が生じた場合の 1 年あたり の不効用を𝑝とする。計画に考慮する年数を𝑌[年]とすると， 目的関数を𝑌年の総費用と呼び， 𝐶𝑖𝑛𝑓𝑟𝑎+ 𝑌 ⋅ 𝑝 ⋅ (𝑡𝑐𝑜𝑠𝑡− 𝑡𝑐𝑜𝑛𝑔𝑒𝑠𝑡𝑖𝑜𝑛) (3) と定義する。なお，この目的関数において旅客不効用から混 雑不効用𝑡𝑐𝑜𝑛𝑔𝑒𝑠𝑡𝑖𝑜𝑛を引く。これは，混雑不効用を目的関数 として入れると，混雑不効用をも最小とする経路が選択さ れるためである．最終的な評価では混雑不効用を加える。 Y年の総費用が最小となる点は，図3 において傾き−𝑌の直 線が最も左下で触れる点となる。𝑌を変化させながら最適化 を行うことで，線で結んで示したような最適計画の候補を 取得することが可能である。 なお，本グラフの設計にあたり，急行との時間差が重要とな る。そのため，急行との時刻差を用いて時刻を表記する。 〈4･2〉 旅客流動グラフ 旅客流動グラフは，ある時刻 に出発駅を発ち，到着駅へと向かう旅客の最小損失時間+乗 換不効用で移動することが可能な経路を求めるグラフであ る。全体のグラフを図4 に示す。移動中の旅客は，次の 6 状 態を考慮し，それぞれ頂点として表現する： 1. [始発ノード]始発駅をある時刻に発つ前の状態 2. [終着ノード]終着駅に到着した状態 3. [発ノード]緩行の出発を待機する状態 4. [着ノード]緩行で駅に到着した状態 5. [急行発ノード]急行の出発を待機する状態 6. [急行着ノード]急行の到着を待機する状態 このうち，1,3,4 は各駅，時刻に頂点を設定する。一方，2 は 各駅に1 つ，5 と 6 は各駅の急行との時間差が 0 の点にの み設定する。 これらの頂点は，旅客の遷移を考慮して次のようにそれぞ れ接続する。 まず，出入りする旅客流動の辺の設定を行う。始発駅から出 発する旅客の流動として，重み 0 の辺で始発ノードと発ノ ードを接続する。急行停車駅では，各始発駅ノードと急行発 ノードを待ち時間に応じた重みで接続する。終着駅に到着 した旅客の流動として，着ノード・急行着ノードを重み0 の 辺で接続する。 次に，駅における旅客流動の辺を設定する。駅における旅客 の待機流動として，発ノードを次の時刻の発ノードに重み1 の辺で接続する。パターンダイヤを考慮するため，周期の最 後の頂点の場合には，最初の頂点に重み1 の辺で接続する。 乗換のために，急行停車駅においては発ノードと急行発ノ ードを双方向に重み𝜔の辺で接続する。駅に緩行で到着した 旅客については必ず1 分の待機が必要となるため，急行通 過駅では着ノードと，次の時刻の発ノードを重み 1 の辺接 続する。急行停車駅では，着ノードと，同じ時刻の発ノード 図3 式(3)における目的関数で選択される点および 𝑌の値による変化
Fig. 3. A point selected by the objective function (3) and its change by parameter 𝑌
図4 旅客流動グラフの表現
急行着ノードと急行発ノードを重み0 でつなぐ。 最後に，駅間の列車の動きを考慮する。緩行の駅間移動は， 急行が減速しない場合には，損失ダイヤ上では鉛直な線で 表されることから，各時刻𝑡発駅𝑑の発ノードと着駅𝑑 + 1の 着ノードを重み0 の削除可能辺𝑙𝑜𝑐𝑎𝑙𝑡𝑟𝑎𝑖𝑛𝑑,𝑡でつなぐ。急行 が遅延する場合には，緩行は時間を1 分遡る．そこで，2 ≤ 𝑡 ≤ 𝑇𝑐𝑖𝑟𝑐𝑙𝑒− 1となる各時刻𝑡について，発駅𝑑の時刻𝑡の発ノ ー ド と 着 駅 𝑑 + 1 の 時 刻 𝑡 − 1 の 着 ノ ー ド を 削 除 可 能 辺 𝑓𝑎𝑠𝑡𝑒𝑟𝑙𝑜𝑐𝑎𝑙𝑡𝑟𝑎𝑖𝑛𝑑,𝑡でつなぐ。緩行の設定は1 周期に 1 本で あることから，これらの辺から1 本の辺を選択する。 急行の駅間移動は，急行遅延を考慮しない駅においては，急 行発ノードと次駅の急行着ノードを重み0 の辺で接続する。 一方，急行遅延を考慮する場合には，急行が低速で走行する 場合の重み 1 の辺と，低速走行が必要ない場合の削除可能 な重み 0 の辺を設定する。後者の辺は，同じ駅において 𝑓𝑎𝑠𝑡𝑒𝑟𝑙𝑜𝑐𝑎𝑙𝑡𝑟𝑎𝑖𝑛𝑑,𝑡が1 本でも存在する場合に削除するとい う条件を設定する。 旅客の流量は，それぞれの始発ノードから終着ノードの組 合せについてこの区間の1 分あたりの旅客数を𝑝𝑐とすると， 𝑌𝑝 ⋅ 𝑝𝑐/𝑇𝑐𝑖𝑟𝑐𝑙𝑒とする。 〈4･3〉 設備費用グラフ 設備費用の計算のために，建 造費用を重み，建造するか否かを流量とするグラフを設計 する。これには，同じ頂点間に費用の異なる辺が 2 本以上 設定されている場合，最も費用が少ない辺にのみ流量が流 れるという特徴を用いる。設備費用グラフの概形を図 5 に 示す。この図において，辺の上の文字は辺の重み，辺の下の 文字はその辺が存在する条件を示す。 グラフの設計に向け，まず駅𝑠において費用が発生する場合 を考慮する。駅費用の計算のために，重みが𝑐𝑠𝑡𝑎𝑡𝑖𝑜𝑛(𝑠)とな る辺を設定する。転轍機費用の計算のために，この駅費用計 算の辺の前後に重みが𝑐𝑐𝑟𝑜𝑠𝑠となる辺を設定する．これらの 辺には，前後の区間に設備増強が行われている場合には転 轍機費用を迂回するように費用 0 の辺を作成する。駅間費 用の計算は，𝑙𝑜𝑐𝑎𝑙𝑡𝑟𝑎𝑖𝑛𝑑,0を選択した場合に費用𝑐𝑠𝑒𝑐𝑡𝑖𝑜𝑛(𝑠) が発生するよう設定することで計算する。 次に，駅𝑠において設備増強が不要となる条件を求める．緩 行が急行との時間差𝑡𝑎に到着し𝑡𝑑に出発したとすると，急 行通過駅では， 1 ≤ 𝑡𝑎 < 𝑡𝑑 ≤ 𝑇𝑐𝑖𝑟𝑐𝑙𝑒− 1となればよい。急行 停車駅では，2 ≤ 𝑡𝑎 ≤ 𝑡𝑑 ≤ 𝑇𝑐𝑖𝑟𝑐𝑙𝑒− 2ならよい。これらの条 件に対応するグラフが，図 6 である。この図中の辺は全て 費用0 である。これを図 5 における駅設備不要条件にとす ることで，設備費用の計算が可能となる。 〈4･4〉 最小費用流問題の混合整数計画問題への置き換え 混合整数計画問題とは，整数制約のある変数および実数の 変数を用い，1 次不等式で表される制約条件を満たしながら 1 次式で表される目的関数を最小化または最大化する問題 である。本節では，グラフや辺の選択問題による費用最小化 を，グラフの性質を混合整数計画問題へと置き換えること で表現する。 前処理として，設定されているフローを，流出側の頂点によ ってまとめる。ここでは，下記の条件を満たすグラフの形状 が同じグラフを作成することを，グラフを複製するという： ・2 つのグラフの対応する辺は，両方を必ず同時に削除 ・対応する辺の重みは等しい ・対応する辺の費用の合計は複写前のグラフに等しい 各フローの終点毎にグラフを複写し，このグラフ上で，この 頂点における流量の流入と流出を設定することで，多品種 流の最適化を行うことが可能となる． 次に，混合整数計画問題への置き換えを行う。ここで，最適 化のために与えるグラフを G(V,E)と書く。ある頂点𝑣につ いて，その頂点に入る辺の集合をEin(𝑣)，その頂点から出る 辺の集合をEout(𝑣)と書くとする。頂点𝑣に設定された入出力 流量をflow(𝑣)とする。辺𝑒を流れるフローを表す実数変数を 𝑓𝑒，重みを定数𝑤𝑒，存在するかを示す0/1 変数を𝑥𝑒，費用を 𝑐𝑒と書く。𝑀を十分大きな定数とする。このとき，目的関数 は， ∑𝑒∈𝐄(𝑥𝑒𝑐𝑒+ 𝑤𝑒𝑓𝑒) (4) である．制約条件としては， 各頂点に流入する流量と流出する流量は同じ：
∑𝑒∈Eout(𝑣)𝑓𝑒− ∑𝑒∈Ein(𝑣)𝑓𝑒− flow(𝑣) = 0 (5) 削除辺には流量を流せない： 𝑓𝑒≤ M ⋅ 𝑥𝑒 (6) N 本の辺𝑒1, … , 𝑒𝑁から1 本の辺を選択： ∑ 𝑥𝑒𝑖 𝑁 𝑖=1 = 1 (7) ある辺𝑒1が存在する時，もう一方の辺𝑒2も必ず存在： 𝑥𝑒1= 𝑥𝑒2 (8) 複数の辺𝑒1… 𝑒𝑁の1 本以上が存在する場合辺𝑒𝑠を削除： 1 ≤ ∑ 𝑥𝑒𝑖 𝑁 𝑖=1 + M𝑥𝑠≤ M (9) 5. ケーススタディによる評価 〈5･1〉 モデル路線の概要 本手法による計画の有用性 図6 駅費用不要条件のグラフ表現
Fig. 6. The graph to detour station cost edges 図5 設備費用グラフの表現
の評価のために，本稿では駅1～駅 26 の 26 駅を持つ都市 路線をモデルとして用いる。各駅の 1 分あたりの乗降人員 は，図8 に示す値を用いて計算を行った。この値は，モデル 路線における定期券旅客数から推計した値である。本路線 の特徴としては，途中の駅において旅客が多く乗降し，旅客 の入れ替わりが発生することである。そのため，終着駅まで 通して乗車する旅客数は少なく，多くの旅客が途中駅にお いて降車する。1 分あたりの OD 表は，図 8 を文献(７)によ って変換した値を用いた。駅間距離および最速走行時分は 実路線を参考として設定した。 路線単価は，周辺の地価および駅間距離を用いて簡易的に 設定した。駅間の費用は周囲の路線単価を参考にした単価 [円/m2]×駅間の距離[m]×10[m]，駅の費用は，現状駅周辺 に用地がない駅では周囲の路線単価を参考にした単価[円 /m2]×300[m]×10[m]+500[百万円]，その他の駅では一律に 500[百万円]とした。転轍機の費用は 100[百万円]とした。 駅における停車損失時間𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠は1 分とした。これは，路 線における最高速度を 75km/h，加減速度を 0.7m/s/s で固 定した場合に，停車時間を30.2s となるように設定すること で実現することができる。 列車間隔𝑇𝑐𝑖𝑟𝑐𝑙𝑒は2𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠, 3𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠, 4𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠の3 つを用い た。このうち，3𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠, 4𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠は，文献(３)の方法によっ て求められた急行停車駅1,7,10,14,16,20,21,26 を用い，𝑌 = 1,5,15,25,50,75として計画を行った．一方，2𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠の場合 には，駅で緩行の待避を行うと，本研究で考慮していない3 線以上の線増が必要となる．そこで，2𝑇𝑠𝑡𝑜𝑝𝑙𝑜𝑠𝑠のケースで は，文献(３)における急行停車駅の全探索法を用い，その結 果のうち旅客不効用-設備費用グラフにおいて左下となる計 画を用いた。 乗換1 回の不効用𝜔は，5 分とした。本研究において考慮す る線増方式では急行と緩行が対面で乗り換えられるとし た．そのため，𝜔は，文献(６)で示される 10 分の半分の値を 採用した。各列車の定員は924 名とした。混雑不効用関数 は，文献(６)で示される関数を用いた。 〈5･2〉 緩行停車時分最適化結果 それぞれの列車間隔 について計算を行った結果を図 9 に示す。このグラフのう ち，代表的な点を 7 つとり，旅客不効用が大きいものから (a)～(g)と呼ぶことにする。これらの計画において生成され た列車時刻を図10 に，設備計画を図 11 に示す。(a)は線増 を行わない条件下で，緩行のみを走行させた場合である．(b) は列車周期が同じで，急行導入のみを行った場合である。こ の場合，設備増強は駅にのみとなった。この計画から列車頻 度を増加させると(c)となる。この計画でも，駅における線増 のみを行っている，さらに，駅24～25 の区間では，急行を 駅間で減速させることにより駅25 における駅の建造が回避 されている。このように，設備費用が少ない場合は，主に駅 のみにおいて線増が行われる計画が有利となる。 さらに費用の増加を考慮することによって，駅間における 設備増強計画が選択されるようになる。費用が少ない計画 (d)では駅 2~3 と 11~12，費用が多い計画(e)では駅 2~3，駅 8~9，駅 17~18 において設備増強が行われた。このように， 設備費用によってどの設備増強を優先的に行うのがよいか という指標が得られた。さらに列車間隔を減らし，三線運行 と同等としたものが(f),(g)である。これらは，停車駅のパタ ーンに応じてP5,P1 と番号を付けた。 図9 上で，このような特徴毎に丸で囲みグループ分けを行 った。この図において，従来の複線の計画は(a)，三線運行は 図8 ケーススタディにおける各停車駅の 1 分あたり乗降客数
Fig. 8. Number of passengers for each station of the case study
図7 ケーススタディにおける各駅・区間の費用
Fig. 7. Cost for each stations and sections
図9 最適計画候補の設備コストと平均旅客不効用
Fig. 9. Optimized infrastructure cost VS average passenger loss time
「三線」で示すデータ点である。この図において，求められ た駅線増・駅間線増のそれぞれの計画が，複線よりも旅客不 効用が少なく，三線運行よりも設備費用が少ない。本研究の 目標である複線と三線運行との中間となる設備費用・旅客 不効用となる列車・設備計画が可能となったといえる。 6. まとめ 本研究では，高頻度運転路線において最小限の設備を増 強し，急行列車を導入するための手法を扱った。与えられた 急行停車駅に対し，緩行の待避や急行の低速走行を考慮し て最適化することで，設備費用の削減と旅客不効用の上昇 のトレードオフ関係において，バランスの良い計画を行う ことが可能となった．緩行の停車時分調整について，旅客流 動および設備費用を，流量に対する重み付きのグラフとし てそれぞれ表現し，このグラフ上で最小費用となる辺を選 択することによって，最適な緩行の時刻を求めた。 ケーススタディにより，区間的線増を行った図10，図 11 上の(e)では，複線において緩行のみの計画と比較し旅客不 効用が16.4%削減された。一方で，三線による運行方式(f)と 比較し，半分の費用で建設可能な設備計画が計算された。さ らに，旅客不効用と設備計画の間の重み付けを変化させた 複数の計画を比較することによって，予算が少ない場合に どの区間を優先的に建造するべきかを考慮した計画を行う ことも可能である。 現在の計画方法では，設備費用の大きい計画と設備費用 の小さい計画で建造する区間は完全には重ならず，段階的 設備増強が表現されていない。最終的により不効用が少な い設備計画に向けて建造を行うことの検討するためには， 本論文の手法を用いる中で，その建造制約を明示的に与え， グラフ上に追加の設備制約として実装することにより，建 設順序の計画や，列車計画法をどのように行うかを計画す ることが出来るようになるだろう。今後の課題として，この ような段階的設備増強の計画方法を検討する必要がある。 文 献 (１) 国土交通省：「東京圏における主要区間の混雑率」， https://www.mlit.go.jp/common/001099727.pdf (2016) (２) 勝田 敬一・古関 隆章・曽根 悟：「複々線同等の高速・高密度運 行を可能にする駅間3 線運行方式」，電気学会論文誌Ｄ, Vol. 121, No. 6，pp. 705-712 (2001) (３) 粟木 一輝・古関 隆章：「高頻度運転区間に最小の設備増強で優等 列車を効果的に導入する利便性向上策の提案」 TER-17-053, LD-17-062 (2017) (４) 曽根 悟：「新しい列車ダイヤと運行管理の手法について」，社会科 学論集，No. 99・100， pp. 19-54 (2000) (５) 小川 浩・曽根 悟：「都市近郊型路線ダイヤの合理的作成法」， TER-93-45 (1993) (６) 国 土 交 通 省 ：「 鉄 道 プ ロ ジ ェ ク ト の 評 価 手 法 マ ニ ュ ア ル 」， http://www.mlit.go.jp/tetudo/tetudo_fr1_000040.html. (2012) (７) 長崎 祐作：「乗客行動推定機能を持った運転整理支援システム」東 京大学修士論文(2004) 図10 最適計画候補の損失時間ダイヤ
Fig. 10. Loss time diagram of candidates for optimal plan
図11 各周期の停車駅および設備増強箇所
