中央大学理工学部情報工学科
卒業研究論文
時空間ネットワークを用いた
貨物列車へのモーダルシフトの可能性
学籍番号 03D8104007F 河野 敬行
指導教員 田口 東 教授
2007 年 3 月
あらまし
近年，地球規模での気温上昇（地球温暖化）から，温室効果ガスの削減を求められてい る．国内貨物輸送における温暖化対策として，環境負荷の少ない鉄道や海運の活用（モー ダルシフト）が推進されている．しかし，貨物列車は旅客列車と同一軌道上を走行する頻 度が高く，輸送容量に限界があると考えられる．
本研究では，増発可能な列車数を算出し，鉄道による貨物輸送の容量を推測する．まず，
旅客列車，貨物列車それぞれの時刻表から時空間ネットワークを構築し，既存の列車の移 動を表現する．次に，構築した時空間ネットワークのもとで，増発する列車が移動可能な 空間と時間を表すネットワークを構築する．この際に，増発可能な列車数をより正確に算 出するために，複々線を考慮する．最後に，このネットワーク上で最大フロー問題を解く ことにより，増発可能な列車数を算出し，輸送容量の推測を行う．
キーワード：貨物列車，時空間ネットワーク，最大フロー問題
目次
第 1 章 序論 ...1
第 2 章 使用データ ...3
2.1 全国 JR 2005 年 1 月号...3
2.2 2006 JR 貨物列車時刻表 ...4
第 3 章 旅客・貨物輸送ネットワークの構築 ...7
3.1 時空間ネットワーク ...7
3.2 旅客ネットワークの構築 ...8
3.3 貨物輸送ネットワークの構築 ... 10
第 4 章 最大フローによる貨物列車本数の最大化... 14
4.1 最大フロー問題 ... 14
4.2 Dinic のアルゴリズム... 15
4.3 容量ネットワークの構築 ... 17
4.3.1 走行可能リンク ... 17
4.3.2 通過可能リンク ... 18
4.3.3 停車可能リンク ... 20
4.3.4 複々線を考慮したネットワークの構築 ... 21
4.4 貨物列車本数の最大化 ... 25
4.4.1 対象範囲の設定 ... 25
4.4.2 東海道線の容量ネットワーク構築 ... 25
4.4.3 結果と考察 ... 27
第 5 章 総論 ... 31
謝辞 ... 32
参考文献 ... 33
第 1 章 序論
近年，産業の発展や森林の開拓などの人間活動の活発化に伴って，大気中の温室効果ガ スの濃度が増加し，地球規模での気温上昇（温暖化）が深刻な問題となっている［12， 13］．
気候変動に関する政府間パネル（IPCC）によると，2100 年には地球の平均気温は 1.4℃か
ら 5.8℃上昇し，その結果，海水の膨張や氷河などの融解による海面の上昇，異常気象の多
発，自然生態系や生活環境，農業などへの影響が予測されている．地球温暖化防止の枠組 みとして，第 3 回気候変動枠組条約締約国会議（京都会議）において京都議定書が採択さ れ，その中で日本は 2008 年から 2012 年の間に 1990 年比で約 6%の温室効果ガス排出削減 を行うことが定められている．
日本全体の CO 2 排出量のうち，運輸部門の占める割合は約 2 割であり，排出量は年々増 加している．さらに，運輸部門の CO 2 排出量のうち約 9 割が自動車に起因するものである．
国内貨物輸送における各輸送機関のシェアは，輸送重量（トンベース）では，トラックが
約 90%，海運が約 8%，鉄道が約 1%であり，トラックが圧倒的なシェアを誇るが，輸送距
離を勘案した輸送量（トンキロベース）では，トラックが約 50%，海運が約 40%，鉄道が
約 4%である．いずれにしても，鉄道の占める割合は少ないが，陸上貨物輸送の距離帯別で
の鉄道のシェアでは，501〜1000 ㎞で約 5%，1001 ㎞以上では約 30%まで上がり，長距離 貨物輸送において鉄道の果たす役割は大きい．また，各輸送機関の CO 2 排出原単位（貨物 1 トンを 1 ㎞輸送するときに排出する CO 2 の量）をみると，トラックに対して鉄道は 8 分
の 1，海運は 4 分の 1 となり，最もシェアの大きいトラックが最も環境負荷が大きくなって
いる．
このような中で，日本政府は新総合物流施策大綱［10］を策定し，その中で環境負荷の 少ない大量輸送機関である鉄道や内航海運の活用（モーダルシフト）を推進しており，500
㎞以上の長距離雑貨輸送における鉄道・内航海運の利用率（モーダルシフト化率）を 2010
年までに 50%（2001 年は 38.6%）まで向上させることを目標としている．また，国土交通
省は荷主・物流事業者の関係者が協力して，計画的に鉄道・海運へのモーダルシフトなど の環境負荷低減策に取り組む実証実験を行う場合に，一定の効果が認められるものについ ては認定を行い，補助金を交付する助成制度も導入している．
以上のことから，今後，鉄道や内航海運の需要が高まることが予想されるが，鉄道にお ける貨物輸送を行う場合，トラック輸送と異なり輸送路が軌道上のみであることや，貨物 列車は旅客列車と同一の軌道を走行する頻度が高いことから，旅客列車との兼ね合いもあ り，輸送量に限界があると考えられる．
そこで，本研究では増発可能な列車数を算出し，鉄道による貨物輸送の容量を推測する．
まず，既存の列車の移動を把握するために，列車の移動をネットワークで表現する．そし
て，そのネットワークをもとに，増発する列車が移動可能な空間と時間を表すネットワー
クを構築する．最後に，このネットワーク上で最大フロー問題を解くことにより，増発可
能な列車数を算出し，輸送容量の推測を行う．
第 2 章 使用データ
2.1 全国 JR 2005 年 1 月号
全国 JR 2005 年 1 月号［2］は，2004 年 12 月から 2005 年 2 月の旅客営業を行っている 全国 6 社ある JR グループ各社と，第三セクター鉄道，JR 路線に乗り入れる民鉄の列車の 時刻表データである．このデータには，線区のデータや臨時停車，時間変更，運休の情報 も含まれている．
時刻表に記載されている列車は 44,109 本あり，各列車について以下の情報がある．
・ 列車番号
・ 列車名
・ 列車種別
・ 列車予約コード
・ 設備（編成）
・ 運転日
・ 走行する線区
・ 停車・通過駅
・ 発着時刻
・ 到着番線
ただし，到着番線は一部の停車駅のみに記載されている．本研究では下線で記した項目を 利用する．
線区は 290 線区あり，各線区について以下の情報がある．
・ 線区名
・ 線区内の駅
・ 各駅の起点駅からの距離
・ 鉄道事業者
JR，第三セクター鉄道，民鉄．
時刻表データの例を図 2.1，線区データの例を図 2.2 に示す．
図 2.1 時刻表データの例
図 2.2 線区データの例
2.2 2006 JR 貨物列車時刻表
2006 JR 貨物時刻表［4］は，日本貨物鉄道（JR 貨物）をはじめ，臨海鉄道，一部の私
鉄の運行する貨物列車，トラック代行便の時刻表である．記載されている時刻表は，以下 の 6 種類である．
五日市線 いつかいち Ｉｔｓｕｋａｉｃｈｉ 0 1010402 1 五日市線（拝 101
1980 1980 拝島 0 0
2000 2000 熊川 1.1 0
2001 2001 東秋留 3.5 0
2002 2002 秋川 5.7 0
2003 2003 武蔵引田 7.2 0
2004 2004 武蔵増戸 8.5 0
2005 2005 武蔵五日市 11.1 0.0;
線区名 駅名 起点駅からの距離 鉄道事業者
Apr-89 1204 0 0 0 0 0 0 0 23
0412/0000000000000000000000101100011，0501/1110000111000011000001100000110，0502/00001100001
1987 青梅 0 1242 0 0 0
1986 東青梅 1244 0 1244 0 0 0
1985 河辺 1246 0 1246 0 0 0
1984 小作 1249 0 1249 0 0 0
1983 羽村 1252 0 1252 0 0 0
1982 福生 1254 0 1254 0 0 0
1981 牛浜 1256 0 1256 0 0 0
1980 拝島 1258 0 1259 0 0 0
1979 昭島 1302 0 1302 0 0 0
1978 中神 1304 0 1304 0 0 0
1977 東中神 1305 0 1305 0 0 0
1976 西立川 1307 0 1307 0 0 0
1808 立川 1310 0 0 0 0;
駅名 着時刻
列車種別 運転日
発時刻
・ 線区別運転時刻表
JR 貨物が運行している貨物列車の時刻表．線区名は旅客線の線区名とほぼ一致する．
・ オフレールステーション時刻表
トラック代行便の時刻表．オフレールステーションとは，最寄拠点駅との間を列車 輸送に代えてトラック輸送を行うコンテナ取扱基地のことである．
・ 臨海鉄道時刻表
全国 10 社ある臨海鉄道会社が運行している貨物列車の時刻表．臨海鉄道とは，JR 貨物と自治体の共同出資で設立され，臨海工業地帯の貨物鉄道を運営している第三セ クター鉄道事業者である．
・ 私鉄貨物列車時刻表
貨物事業を行っている私鉄のうち，三岐鉄道，岳南鉄道，小坂鉄道，西濃鉄道の 4 社の貨物列車の時刻表．
・ 高速貨物列車運行表
JR 貨物が運行する高速貨物列車の時刻表．高速貨物列車とは時速 85 キロメートル 以上で運転できる列車である．ここに記載されている時刻については，線区別時刻表 にも記載されている．
・ 専用貨物列車運行表
JR 貨物が運行する専用貨物列車のうち，化成品を輸送する列車の時刻表．専用貨物 とは時速 75 キロメートルで運転する列車である．ここに記載されている時刻について は，線区別時刻表にも記載されている．
本研究では線区別運転時刻表を利用する（図 2.3）．
線区別運転時刻表では，各列車に関して以下の情報が記載されている．
・ 列車種別
高速，専用，臨時高速，臨時専用，試運転など．
・ 列車番号
・ 速度
・ 編成内容
コンテナ，石油，化学薬品，紙，セメントなど．
・ 始発・終着駅
・ 停車・通過駅
・ 発着時刻
・ 停車の種類
着発線荷役作業，連結，解放，運転上の停車．
ただし，停車・通過駅は，コンテナ取扱駅，車扱貨物取扱駅，一部のコンテナ臨時取扱 駅，車扱貨物臨時取扱駅，操車場，信号場，分岐駅についてのみ記載されている．また，
発着時刻は主要駅での停車と，その他の駅では運転上の停車以外の停車をするときのみ，
発時刻と着時刻が記載されており，多くは発時刻のみである．
本研究では，下線で記した項目を利用する．
高速 高速
2059 79 100 95
東 京
(
タ)
東 京︵ タ︶
2015 510
- -
コ ン テ ナ
コ ン テ ナ
2015 510
着 ◎2026 520
発 2056
‥ ‥
‥ ‥
12.9 ‥
(1.3) ‥
‥ ‥
‥ ‥
‥ ‥
‥ ‥
22.1 着 (2117) ‥
<18.5> 発 (2117) ‥ 札幌（タ） 川崎貨物
1916 520
61 -
発時刻
編成内容 起
点 か ら の キ ロ
0.0 東京（タ）
7.6 川崎貨物 前の記載頁
列車種別 列車番号
速度 始発駅
(0.0) 扇町
浜川崎 |
(3.5) 安善 (5.1) 大川
新鶴見（信）
終着駅 着時刻 次の記載頁
図 2.3 線区別時刻表の例
第 3 章 旅客・貨物輸送ネットワークの構築
本章では，既存の旅客・貨物列車の移動を表現するために，旅客・貨物輸送ネットワー クを構築する．
3.1 節で時空間ネットワークについて説明する．3.2，3.3 節で旅客・貨物輸送ネットワー クの構築について述べる．
3.1 時空間ネットワーク
本研究では，列車が走行していない時間帯を見つけ，できるだけ多くの貨物列車を増発 させることを考える．そこで，既存の列車の移動を把握するために，列車の移動をネット ワークで表現する．
列車の移動をネットワークで表現するためには，駅間の移動における空間の変化と，そ れに伴う時間の変化を考慮する必要がある．しかし，通常の鉄道ネットワークでは時間の 概念がないので，時間の経過を表すことができない．そこで，空間ネットワークに時間の 概念を加えた時空間ネットワークを利用して，時間の経過を表現する［6，9］．
鉄道ネットワークは，駅をノードとし，駅間にリンクをはることにより表される．時空 間ネットワークでは，駅毎にノードを定義するのではなく，列車の発着毎にノードを定義 し，鉄道ネットワークを時間方向に拡張する．
ネットワーク上で列車の移動を表現するが，列車の動きには以下のようなものがある．
・ 駅を発車する．
・ 駅に到着する．
・ 駅間を走行する．
・ 駅で停車している．
これらの動きを表すために，以下のノードとリンクを定義する．
発ノード：各駅における各列車の発車．
着ノード：各駅における各列車の到着．
走行リンク：駅間の走行．
停車リンク：駅での停車．
時空間ネットワークへの拡張の様子を図 3.1 に示す．
図 3.1 時空間ネットワークへの拡張
3.2 旅客ネットワークの構築
3.1 節で説明した時空間ネットワークをもとに，旅客列車の移動を表現した旅客ネットワ ークを構築する．旅客列車のデータは，全国 JR 2005 年 1 月号（以下，旅客時刻表）を用 いる．
旅客時刻表より得られるデータから構築した旅客ネットワークを図 3.2 に示す．図 3.2 で は，通過駅を通らず，停車駅から次の停車駅へ直接結ばれているリンクがある．旅客時刻 表には，優等列車の通過駅は記載されているが，その駅を通過する時刻は記載されていな い．そのため，ネットワーク上の優等列車は，ある駅の発ノードから次に停車する駅の着 ノードに，直接リンクで接続されているので，通過駅の情報が存在しない．その様子を図 3.3 に示す．
列車を増発する際には，各駅で列車が停車，または通過してしない時間帯を知る必要が あるので，優等列車の通過時刻を推定しなければならない．そこで，3.1 節で定義したノー ドに，列車の通過を表す通過ノード加え，その時刻を次のように決定する．
発車する駅の発時刻と，停車する駅の着時刻から，その駅間の走行時間を求める．列車 は常に平均速度で走行すると仮定し，発駅から着駅までの距離と発駅から通過駅までの距 離で比をとり，通過時刻を決定する．通過時刻決定の例を図 3.4 に示す．例えば，10km 先 の駅に 20 分後に到着する列車が 6km 先の駅を通過する場合，通過時刻は 12 分後とする．
通過時刻を決定し，通過ノードを加えた後の旅客ネットワークを図 3.5 に示す．図 3.2 で は通過駅を通らず，停車駅から次の停車駅へ直接結ばれているリンクがあるが，図 3.5 では
鉄道ネットワーク 時空間ネットワーク
：発ノード
：着ノード
：走行リンク
：停車リンク
A 駅 B 駅 C 駅
t
1時発列車 t
2時発列車
時刻
通過ノードを追加したことにより通過駅を通るため，路線に沿った形になる．
（a）全国図 （b）首都圏拡大図
図 3.2 時刻表から構築した旅客ネットワーク
図 3.3 優等列車の旅客ネットワーク上での様子
普通列車 優等列車
優等列車の通過駅
図 3.4 通過時刻決定の例
図 3.5 通過ノード追加後の旅客ネットワーク
3.3 貨物輸送ネットワークの構築
本節では，2006 JR 貨物時刻表（以下，貨物時刻表）を用いて，3.1 節で説明した時空間 ネットワークをもとに，貨物列車の移動を表す貨物輸送ネットワークを構築する．
貨物時刻表より得られるデータから構築した貨物輸送ネットワークを図 3.6 に示す．図 3.6 では，貨物時刻表の線区別時刻表に記載されている線区のうち，以下の線区を扱ってい
6㎞ 4㎞
7：00
7：20 7：12
優等列車の通過駅
追加した通過ノード
る．
・ 東海道線（東京貨物ターミナル−吹田信号場間）
・ 東海道支線・鶴見線（東京貨物ターミナル−新鶴見信号場間）
・ 東海道支線・名古屋臨海高速鉄道線（稲沢−名古屋貨物ターミナル間）
・ 中央・篠ノ井線（篠ノ井−稲沢間）
・ 関西線・紀勢線（稲沢−新宮間）
・ 日本海縦貫線（吹田信号場−青森信号場間）
2.2 節で述べたように，貨物時刻表には通過駅がコンテナ取扱駅，車扱貨物取扱駅，一部 のコンテナ臨時取扱駅，車扱貨物臨時取扱駅，操車場，信号場，分岐駅しか記載されてい ないので，通過駅を追加する必要がある．また，貨物時刻表も旅客時刻表と同様に，通過 する駅での通過時刻は記載されていないので，通過時刻も追加する必要がある．そこで，
走行する線区から通過駅を探し，通過駅の補完後に図 3.4 と同様に通過時刻を決定する．
時空間ネットワークでは，列車の発着毎にノードを作成するが，貨物時刻表には一部の 停車にしか着時刻の記載がない．図 3.6 では，着時刻がない場合，走行リンクは発ノードと 発ノードを接続しているので，実際より長い時間，駅間を走行していることになる．その ため，実際には列車を増発できる時間があっても，ネットワーク上では列車が走っている ので増発できない．貨物列車は停車時間が長いことがあり，その影響は大きい．そこで，
貨物時刻表に着時刻を追加する．
着時刻を追加するためには，各駅間の走行にかかる時間を求めなければならない．駅間 の走行にかかる時間は，線路の形状や車両の性能などから計算されるが，これらのデータ を収集するのは困難である．そこで本研究では，図 3.4 と同様の処理を行った上で，各駅間 を最短の時間で走行している貨物列車の走行時間を算出し，各駅間に必要な走行時間とす る．着時刻は，発駅の発時刻に着駅までの駅間の走行時間を加えた時刻とする．
着時刻を加えた貨物時刻表を用い，通過駅を補完し，図 3.4 と同様の処理を行って再構築 した貨物輸送ネットワークを図 3.7 に示す．
以上をまとめ，貨物輸送ネットワーク作成の手順を以下に示す．
貨物輸送ネットワーク作成の手順
Step 1 貨物時刻表より，時空間ネットワークを作成する．
Step 2 通過駅を補完し，通過時刻を求め，通過ノードを作成する．
Step 3 通過ノードが作成された時空間ネットワークから，各駅間の走行に必要な時間を求 める．
Step 4 着時刻のない停車について，各駅間の走行に必要な時間から着時刻を求め，貨物時
刻表に追加する．
Step 5 更新した貨物時刻表より，時空間ネットワークを作成する．
Step 6 通過駅を補完し，通過時刻を求め，通過ノードを作成し，終了する．
第 4 章では旅客ネットワークと貨物輸送ネットワークを同一空間上に構築することによ り統合した，旅客・貨物輸送ネットワーク（図 3.8）を利用する．
図 3.6 2006 JR 貨物時刻表から構築した貨物輸送ネットワーク
東海道線
鶴見線・東海道支線 日本海縦貫線
中央・篠ノ井線
関西線・紀勢線
名古屋臨海高速鉄道線・東海道支線
青森信号場
名古屋
東京貨物ターミナル 吹田信号場
新潟貨物ターミナル
図 3.7 着時刻，通過駅，通過時刻追加後の貨物輸送ネットワーク
図 3.8 旅客・貨物輸送ネットワーク
青森信号場
新潟貨物ターミナル
東京貨物ターミナル
名古屋
吹田信号場
第 4 章 最大フローによる貨物列車本数の最大化
本章では，第 3 章で構築した旅客・貨物輸送ネットワークをもとに，容量ネットワーク を構築し，貨物列車本数の最大化問題を最大フロー問題に定式化して解く．
4.1，4.2 節で最大フロー問題とその解法について説明する［1］．4.3 節で容量ネットワー
クの構築法について述べる． 4.4 節では東海道線を対象として，容量ネットワークを構築し て最大フロー問題を解くことにより，増発できる貨物列車の本数を求める．
4.1 最大フロー問題
有効グラフ G の各辺 e = ( v , w ) ∈ E ( G ) に正の実数の容量 cap (e ) が割り振られているネ
ットワーク N = ( G , cap , s , t ) において，入り口 s ∈ V (G ) から出口 t ∈ V (G ) への流量最大の
フローを求める問題が最大フロー問題である． N のフロー f は以下の 2 つの条件をみたす 辺集合 E (G ) から非負実数集合 R + への関数 f : E ( G ) → R + である．
（a） 任意の辺 e ∈ E (G ) に対して， 0 ≤ f ( e ) ≤ cap ( e ) ．
（b） s ， t を除く任意の点 v ∈ V (G ) に対して， ∑
−∑
+∈
=
∈
=
=
) ( ) , ( ) ( ) , (
) ( )
(
v v u e v v u e
e f e
f
δ δ
．
ここで， δ − (v ) （ δ + (v ) ）は v を終点（始点）とする N の辺の集合を表す（図 4.1）．条件
（ a ）は各辺を流れるフローの値が容量以下であることを示している．条件（ b ）は入り口・
出口を除いて，流量の保存則（流入量＝流出量）が成立していることを示している．
したがって，条件（b）は，
∑
+∑
−∈
=
∈
=
−
=
) ( ) , ( ) ( ) , (
) ( )
(
s s u e s w s e
e f e
f K
δ δ
（4.1）
とおけば，
∑
∑
− +∈
=
∈
=
−
=
) ( ) , ( ) ( ) , (
) ( )
(
t w t e t t u e
e f e
f K
δ δ
（4.2）
が成立することを意味している．すなわち， s から流出するフローの正味量 K は t に流出す
るフローの正味量と等しい．この K をフロー f の流量という．
4.2 Dinic のアルゴリズム
Dinic のアルゴリズムは，与えられたネットワーク N に対して，ゼロフローから出発し
てフロー f を更新していく．更新の際，フロー f （図 4.1 （a））の残余容量ネットワーク N ( f )
（図 4.1（b））を用いる．フロー f に関する残余容量ネットワーク N ( f ) とは，残余容量が
正の辺からなるネットワークで，以下のように定義される．各辺 e = ( v , w ) ∈ E ( G ) に対し て，辺 e = ( v , w ) の残余容量 cap f (e ) は， f ( e ) < cap ( e ) ならば cap ( e ) − f ( e ) である．
0 ) ( e >
f ならば，辺 e = ( v , w ) に沿って f (e ) 減らせるので，逆向きの仮想的な辺 e R = ( w , v )
を考える．辺 e R = ( w , v ) の残余容量は， cap f ( e R ) = f ( e ) である．
したがって，仮想的な辺の全体を E R ( G ) = { e R | e ∈ E ( G ) } とすると，フロー f に関する
残余容量ネットワーク N ( f ) = ( G ( f ), cap f , s , t ) は，
( ) { } { }
( )
( ( ) 0 )
) ( ) (
) ( )
( ) ( ) ( )
(
0 ) (
| ) ( )
( )
(
| ) ( )
(
>
=
<
−
=
>
∈
∪
<
∈
=
e f e f e cap
e cap e
f e f e cap e
cap
e f G E e e cap e
f G E e f G E
R f
f
R R
（4.3）
として定義できる．
残余容量ネットワーク N ( f ) を幅優先探索して，各点 v に対して入口 s からの距離 ]
[v
level を求めて，
{ ( , ) ( ) | [ ] [ ] 1 }
)
( f = v w ∈ E G level w = level v +
E
L（4.4）
の辺からなるレベルネットワーク N L ( f ) （図 4.1（c））を構成する． N L ( f ) 上での極大フ ロー f ′ （図 4.1（d））を求め，
( )
( )
⎩ ⎨
⎧
′ ∈
−
′ ∈
= +
) ( )
( ) (
) ( )
( ) : (
)
( R
f E e e f e f
f E e e f e e f
f
L R
L
（4.5）
と更新しながら， N ( f ) に s から t へのパスがなくなるまで繰り返して，最終的に N の最大 フローを求める．なお， N L ( f ) から f ′ ( e ) = cap f ( e ) となる辺 e をすべて除去すると， s か ら t へのパスがなくなり，フロー f ′ は N L ( f ) の極大フローとなる．
以上をまとめ，アルゴリズムを以下に示す．
Dinic のアルゴリズム Step 1 f := 0 とおく．
Step 2 （1） f に関する残余容量ネットワーク N ( f ) を作る．
（2） N ( f ) のレベルネットワーク N L ( f ) を求める．このとき N L ( f ) に s から t へ のパス P が存在しないときは f は最大フローになり終了する．
（3） N L ( f ) 上での極大フロー f ′ を求め，
( )
( )
⎩ ⎨
⎧
′ ∈
−
′ ∈
= +
) ( )
( ) (
) ( )
( ) : (
)
( R
f E e e f e f
f E e e f e e f
f
L R
L
と更新して（ a ）に戻る．
図 4.1 Dinic のアルゴリズム
( f ( e ) / cap ( e ) )
f
5 / 10
3 / 3
16 / 25
0 / 2 0 / 5 8 / 30
13 / 18
2 / 8
15 / 17 6 / 20
（a） N のフロー （ b ） 残余容量ネットワーク N ( f ) ( cap
f( e ) )
22
5
9 3
5 2
5 6
14
2 5
16
13
6
2
15
u w
v x
s t
5
9
2 22
5
2 14
（ c ） レベルネットワーク N
L( f )
5
4
2 5
2
2 7
（ d ） N
L( f ) の極大フロー f ′
u w
v x
s t
u w
v x
s t
u w
v x
s t
8
4.3 容量ネットワークの構築
最大フロー問題による定式化を行うために，第 3 章で構築した旅客・貨物輸送ネットワ ークをもとに容量ネットワークを構築する．容量ネットワークは，増発する列車が移動可 能な空間と時間を表すネットワークである．旅客・貨物輸送ネットワークは上下線を同時 に構築しているので，容量ネットワーク構築の際には，旅客・貨物輸送ネットワークから 上下線別にネットワークを取り出し，それぞれ容量ネットワークを構築する．
本節では，4.3.1，4.3.2，4.3.3 項で容量ネットワークで用いるリンクについて説明する．
4.3.4 項で複々線を考慮したネットワークの構築方法について述べる．
4.3.1 走行可能リンク
走行可能リンクは，新たに列車が走行できることを表すリンクとする．列車は同一軌道 上を走る列車を追い越すことはできない．そこで，旅客・貨物輸送ネットワークの走行リ ンク間の列車が走っていない時間に走行可能リンクを張る．各駅間において，各走行リン ク間の時間に新たに走行できる列車の本数をまとめて 1 本の走行可能リンクを張り，その 列車の本数を走行可能リンクの容量とする．走行可能リンクの作成の様子を図 4.2 に示す．
走行可能リンクを張る際に，始点と終点にノードを作成する．始点ノードは列車が発車で きる時間を表し，終点ノードは到着できる時間を表している．
走行可能リンクの容量を算出する際には，列車をできるだけ多く走らせるために，増発 する列車は，走行可能リンクを挟んでいる 2 本の走行リンクのうち，走行時間が短い列車 と平行に走ると仮定する．したがって，リンクの始点の駅を発車可能な列車数と，終点の 駅に到着可能な列車数の少ない方の値が，走行可能リンクの容量となる．発車可能な列車 数は，発車可能な時間から求める．発車可能な時間は，既存の 2 本の列車が発車する時刻 の間だが，列車と列車の間隔は一定以上時間を空けなくてはならない．この列車と列車の 間に最低限確保しなければならない時間のことを時隔という［8］．駅間ごとに時隔は異な るが，全ての時隔を算出するのは困難であるため，本研究では一律 3 分とする．よって，
発車可能な時間は，既存の 2 本の列車が発車する時刻から，時隔の分だけ間隔をあけた時
間となる（図 4.3）．発車可能な時間に，列車間隔が時隔より短くならないように発車でき
る列車数が，発車可能な列車数である．到着可能な列車数も発車可能な列車数と同様に求
める．
図 4.2 走行可能リンク作成の様子
図 4.3 発車・到着可能な時間
4.3.2 通過可能リンク
通過可能リンクは，列車が駅を通過できることを表すリンクで，各駅に到着する走行可 能リンクと発車する走行可能リンクとを接続する．通過可能リンク作成の様子を図 4.4 に示 す．図 4.4 において，リンク A，B，C，D は旅客・貨物輸送ネットワークの走行リンク，
リンク a，b，c は容量ネットワークの走行可能リンクである．走行可能リンク a を通る列
車は，走行リンク D の始点（発車）の時刻より早く駅を通過したら，次の駅間では走行可 時隔
時隔
到着可能な時間 発車可能な時間
：走行リンク
：走行可能リンク
A 駅 B 駅
走行リンクと走行リン クの間に1本張る
空いている時間帯を1
本 の 走行 可能 リ ン ク
にまとめる
能リンク c を，遅く通過したら走行可能リンク b を通ることができる．そこで，走行可能 リンク a の終点のノードから，走行可能リンク b，c の始点（発車）のノードへ通過可能リ ンクを張る．走行可能リンク a から c に張った通過可能リンクは，走行リンク D の始点ノ ードの時刻より早く，走行リンク C の終点ノードの時刻より遅く駅を通過する列車が通る ことができる．
通過可能な時間には，複数の列車が通過する可能性があるので，通過可能リンクの容量 は，その時間に通過可能な列車数とする．通過できる時間は，到着できる時間と発車でき る時間の重複部分である（図 4.5）．この時間に列車間隔が時隔より短くならないように通 過できる列車の本数が通過可能リンクの容量とする．ただし，既存の列車が駅に停車して いて，通過するスペースがない場合は容量を 0 とする．
図 4.4 通過可能リンク作成の様子
図 4.5 通過可能な時間
発車可能な時間 到着可能な時間
通過可能な時間 A
B
C a D
b
c
駅
：走行リンク
：走行可能リンク
：通過可能リンク
4.3.3 停車可能リンク
停車可能リンクは，列車が停車可能であることを表すリンクとする．各駅において，時 間順に走行可能リンクの始点を結んでいき，駅で停車できるようにする．停車可能リンク 作成の様子を図 4.6 に示す．
停車可能リンクの容量は，駅に停車できる列車数から，既存の列車が停車している数を 引いた値とする．各駅に停車できる列車数を全ての駅について調査することは困難である ため，本研究では駅を以下のように分類し，それぞれ停車できる列車数とする．
・ コンテナ取扱駅，車扱貨物取扱駅，操車場，信号場 停車できる列車数は 5 とする．
・ コンテナ臨時取扱駅，車扱貨物臨時取扱駅 停車できる列車数は 3 とする．
・ 旅客駅
停車できる列車数は 1 とする．ただし，東海旅客鉄道，西日本旅客鉄道，東日本旅 客鉄道各社の公式サイト［14，15，16］に構内図の記載のある駅は，構内図より停車 できる列車数を求める．
なお，容量ネットワークは上下線別々で構築するため，上記の停車できる数は上り線ま たは下り線の片側の値である．既存の列車が駅で停車している数は，停車可能リンクの始 点の時刻から終点の時刻までの間に変化している可能性がある．駅で停車している列車数 は，停車している列車が発車するまで減らない．また，停車可能リンクは走行可能リンク と次の時間帯の走行可能リンクの始点を接続しているため，停車可能リンクの始点の時刻 から終点の時刻までの間に，既存の列車は必ず 1 本のみ発車している．よって，その発車 している時刻での停車数が，その時間帯の極大の値となっているので，この停車数を容量 算出の際に用いる．
以上のリンクを用いて，容量ネットワークを構築する．容量ネットワーク作成の手順を 以下に示す．
容量ネットワーク作成の手順
Step 1 各駅間において，旅客・貨物輸送ネットワークの走行リンク間に走行可能リンクを 張り，容量を求めて，その始点と終点にノードを作成する．
Step 2 各駅において，通過可能リンクと停車可能リンクを張り，容量を求める．
図 4.6 停車可能リンク作成の様子
4.3.4 複々線を考慮したネットワークの構築
第 3 章で構築した旅客・貨物ネットワークから上下線別でネットワークを取り出し，そ のネットワークをもとに容量ネットワークを構築する．単一方向のみ取り出した旅客・貨 物輸送ネットワークは複々線（単一方向に軌道が 2 線）を考慮しておらず，全区間で複線
（単一方向に軌道が 1 線）である．よって，複々線区間で 2 線に分かれて軌道上を走行し ている列車も，ネットワーク上では一つの軌道上に走行している（図 4.7）．このネットワ ークをもとに容量ネットワークを構築すると，容量ネットワークも全区間複線となる．元々 複々線である区間を複線にしてしまうと，列車が過密に走行していることになる．また，
軌道も 1 線になるので，本来より増発できる列車数が減少してしまう（図 4.8）．そこで，
複線区間，複々線区間の容量ネットワークを別々に構築し，それらを結合することにより，
複々線を考慮したネットワークを構築する．その様子を図 4.9 に示す．
まず，複線区間の容量ネットワークを構築する．単一方向のみを取り出した旅客・貨物 輸送ネットワーク（図 4.9（a1））をもとに容量ネットワーク（図 4.9（a2））を構築すると 全区間複線となるので，そこから実際に複線の区間である部分のネットワークを抽出する
（図 4.9（a3））．
次に，複々線区間の容量ネットワークを構築する．複々線区間は 2 線ある軌道を 1 線ず つ見れば複線と同じなので，軌道毎に容量ネットワークを構築する．複々線区間の 2 線あ るうちの 1 線のみの容量ネットワークを構築するために，その軌道を走行する列車のみの 旅客・貨物輸送ネットワークを，単一方向のみ取り出した旅客・貨物ネットワークから抽 出する（図 4.9 （b1））．そして，そのネットワークをもとに，容量ネットワーク（図 4.9 （b2））
駅
：走行可能リンク
：通過可能リンク
：停車可能リンク
の構築し，複々線区間のみを抽出する（図 4.9（b3））．この操作をもう一方の軌道に対して も行い（図 4.9（c）），複々線区間の容量ネットワークを構築する．この方法により，全て の区間の容量ネットワークを結合した際に，複々線区間ではネットワークが二重になり，
軌道が 2 線あることを表現できる（図 4.9（d））．
全ての区間の容量ネットワークを構築し，結合した後に，フローの入口，出口になるノ ードを作成する．入口ノードから対象とする区間の起点駅にある全てのノードへ，終点駅 にある全てのノードから出口ノードへ容量無限大のリンクを張り，ネットワークが完成す る．
以上をまとめ，複々線を考慮したネットワーク作成の手順を以下に示す．
複々線を考慮したネットワーク作成の手順
Step 1 旅客・貨物輸送ネットワークから，単一方向（上り線，または下り線）のみの旅客・
貨物輸送ネットワークを抽出する．
Step 2 単一方向のみの旅客・貨物輸送ネットワークをもとに容量ネットワークを構築し，
複線区間のみを抽出する．
Step 3 各複々線区間の軌道毎に，単一方向のみの旅客・貨物輸送ネットワークから，その 軌道を走行する列車のみのネットワークを取り出して，そのネットワークをもと に容量ネットワークを構築する．構築した容量ネットワークから複々線区間のみ を抽出する．
Step 4 それぞれ構築した容量ネットワークを統合する．
Step 5 フローの入口，出口となるノードを作成し，入口ノードから起点駅にある全てのノ ードへ，終点駅にある全てのノードから出口ノードへ容量無限大のリンクを張る．
（a）複々線を考慮しない （b）複々線の考慮
図 4.7 単一方向の旅客・貨物輸送ネットワークの概略図
複線
A B
複々線 複線：軌道Aの走行リンク
：軌道Bの走行リンク
複線 複線
A B
複々線
（ a ）複々線を考慮しない（軌道は 1 線） （ b ）複々線を考慮（軌道は 2 線）
図 4.8 増発可能な列車数の比較
：増発可能な列車
駅 駅
駅 駅
駅 駅
軌道
A
軌道
B
（ d ）
（ a ）：複線区間の容量ネットワーク構築の様子
（b），（c）：複々線区間の容量ネットワーク構築の様子
（d）：各区間の容量ネットワークを統合したネットワーク
図 4.9 複々線を考慮したネットワーク構築の様子
（c1） （c2） （c3）
（b1） （b2） （b3）
（a1） （a2） （a3）
4.4 貨物列車本数の最大化 4.4.1 対象範囲の設定
東海道線の東京貨物ターミナル駅から吹田信号場間（136 駅）を対象とし，容量ネットワ ークを構築して最大フロー問題を解くことによって，増発可能な貨物列車の本数を求める．
東海道線を対象とする理由を以下に述べる．
図 4.10 は，旧日本道路公団が所有していた高速道路の平成 15 年度におけるインターチ ェンジ間の OD 交通量（O：Origin（起点），D：Destination（終点）） を，最短経路探索 法の一つである Dijkstra 法を用いて，交通量を配分した結果である．図 4.10（a）は大型
車，図 4.10（b）は特大車の交通量である．大型車，特大車共に東名高速道路と名神高速道
路の交通量が多いことが図から読み取れる．そこで，モーダルシフトの際には 2 つの高速 道路とほぼ並行して走る東海道線の貨物列車の需要が高まると推測できる．よって，本節 では東海道線を対象として，増発可能な貨物列車の本数を求める．
（a）大型車 （b）特大車 図 4.10 高速道路の交通量
4.4.2 東海道線の容量ネットワーク構築
東海道線の容量ネットワークを構築する．東海道線の東京貨物ターミナル駅から吹田信
号場間の複々線区間は，以下の 3 区間である［3，5，7］ ．なお，名古屋−稲沢間について
は，列車が 2 線あるうちのどちらの軌道を通るかについて記述している文献が見当たらな
かったため，自ら調査を行った．
・ 鶴見−小田原間
旅客線と貨物線の別線．ただし，湘南ライナーなど一部の旅客列車は貨物線を通る．
・ 名古屋−稲沢間
名古屋−清洲間では，旅客列車は旅客線のみを通り，貨物列車は旅客線と貨物線の 両方を通る．清洲−稲沢間では，旅客列車は旅客線，貨物列車は貨物のみを通り，旅 客と貨物の別線である．名古屋−清洲間で貨物列車がどちらの軌道を通るかは，行き 先（または通ってきた路線）によって決まる．稲沢から名古屋へ向かう貨物列車は，
名古屋から東海道線，中央線，関西線，あおなみ線に分かれる．東海道線を通る列車 は，名古屋−清洲間では旅客線を，中央線，関西線，あおなみ線を通る列車は貨物線 を通る．
・ 草津−茨木間
列車種別により分かれており，内側線を普通，快速列車が走行し，外側線を新快速，
優等列車，貨物列車が走行する．
なお，他の区間は全て複線である．そこで，鶴見−小田原間，名古屋−清洲間，清洲−
稲沢間，草津−茨木間とその他の複線区間でそれぞれ容量ネットワークを構築し，各区間
のネットワークを統合する．統合後にフローの入口，出口となるノードを作成し，下り線
の場合，入口ノードからは東京貨物ターミナル駅にある全てのノードへ，吹田信号場にあ
る全てのノードから出口ノードへ容量無限大のリンクを張る．上り線の場合は，起点駅と
終点駅を逆にする．図 4.11 に東京貨物ターミナル−吹田信号場間の下り線の容量ネットワ
ークを示す．
（ a ）全体図（上から）
（ b ）入口付近の拡大図（手前から）
図 4.11 東京貨物ターミナル−吹田信号場間（下り線）の容量ネットワーク
4.4.3 結果と考察
東京貨物ターミナル−吹田信号場間の上り線と下り線に対して，それぞれ容量ネットワ ークを構築して，最大フロー問題を解くと以下のような結果が得られる．
入口 出口
小田原 名古屋
草津
吹田信号場
東京貨物ターミナル
入口
鶴見
東京貨物ターミナル
茅ヶ崎
・ 下り線：流量 74
・ 上り線：流量 55
これらの流量は正確に増発可能な列車数を示すものではない．その原因はネットワークの 構造にあり，時間をさかのぼってしまうような実現不可能な列車が現れている．しかし，
増発可能な列車数の上界として，この値は有用である．最大フロー問題を解いた際のフロ ーの様子を図 4.12 に示す．図 4.12 で時間軸に平行な黒の線は，0 時から 24 時までの 3 時 間刻みの線であり，垂直な黒の線は，主要な駅の位置を表している．また，赤い線ほど流 量は多く，青い線ほど少ない．
現在，東京−大阪間を結ぶ貨物列車は下り線が 34 本，上り線が 37 本となっており，増 発後，下り線は約 3 倍，上り線は約 2.5 倍の列車数となる．そこで，増発する貨物列車がど の程度の貨物を輸送できるか推計する．
JR 貨物の列車の 1 日あたりの列車走行キロ 221 千キロ（平成 18 年 3 月ダイヤ改正時），
年間の貨物輸送量 226 億トンキロ（平成 17 年度）から，1 列車 1km あたりの平均積載ト ン数は約 280 トンと計算できる．よって，74 本増発した際には約 20,720 トン，55 本増発 した際には約 15,400 トンの貨物を新たに輸送できる．また，トラック輸送における貨物の 都道府県間流動量［11］は，東京，神奈川から大阪，京都，兵庫への流動量は１日平均で
約 36,330 トン，大阪，京都，兵庫から東京，神奈川への流動量は約 43,870 トンである．
これらのうち，鉄道へモーダルシフトが可能な輸送量の割合は，東京，神奈川から大阪，
京都，兵庫への貨物で 57%，大阪，京都，兵庫から東京，神奈川への貨物で 35%である．
起点駅を変えず，終点駅を起点駅の次の駅から 1 駅ずつずらしていくときの最大フロー
問題の結果（流量）と，各駅間の走行可能リンクの容量の和（値は終点の駅に表示）を図
4.13 に示す．図 4.13 より，流量が大幅に減っているポイントが 2 つあることがわかる．1
つ目は，起点駅を出て初めの複々線区間が終わり，複線に切り替わるときである．軌道が 1
線になるため容量が大幅に減少するので，流量の減少はやむをえないが，下り線では流量
に対して，容量に余裕があるので，既存の列車のダイヤを調整することで，流量を増やせ
る可能性があると考えられる．2 つ目は，名古屋近郊にある複々線区間の手前である．名古
屋近郊は複々線区間を除き，他の地域に比べて容量が少ないので，この地域の輸送力を改
善すれば，東京−大阪間の輸送力が改善されると考えられる．
（a）下り線 （b）上り線
図 4.12 フローの様子
鶴見小田原名古屋稲沢草津
入口出口 鶴見小田原
出口 名古屋稲沢草津
入口 距離
時間
0 100 200 300 400 500 600 700 800
川 崎 貨 物
小 田 原
沼 津
静 岡 貨 物
西 浜 松
岡 崎
名 古 屋
岐 阜 貨 物
米 原 操 車 場
草 津
梅 小 路
吹 田 信 号 場 終点駅
本 数
容量 流量
（a）下り線
0 100 200 300 400 500 600 700 800
茨 木
梅 小 路
草 津
米 原 操 車 場
岐 阜 貨 物
名 古 屋
岡 崎
西 浜 松
静 岡 貨 物
沼 津
小 田 原
東 京 貨 物
終点駅 本
数
容量 流量
