ＥＸＣＥＬによる最長片道ルート探索
4. ＪＲ最長片道ルートの計算
（１）新幹線を含む通常の最長片道ルート
次に、この手法を実際のＪＲ最長片道ルートの計算に適用してみる。以下では本州のみを取り扱う。
まず、新幹線を含む通常の最長片道ルートを求めるため、起点を北海道への入口である青森、終点を九州への入口である幡生とする。即ち青森、幡生を通る枝の数は1という制約を課すこととする。また事前の処理として行き止まり路線は全て削除するのは勿論として、途中に分岐点を含まない2地点間を結ぶルートが複数あれば、最長ルートのみを残し他は削除することとした。これにより、青森・秋田間は五能線経由のみ、盛岡・新花巻間は山田線、釜石線経由のみ、蘇我・大網間は内房線−安房鴨川−外房線経由のみ、横浜・大船間は根岸線経由のみ、相生・東岡山間は山陽本線経由のみ、福山・三原間は山陽本線経由のみ、三原・広島間は呉線経由のみ、広島・新山口間は山陽本線経由のみ、また新山口・厚狭間は山陽本線−宇部−宇部線−居能−小野田線経由のみとなる。各区間の距離としては、全て営業キロを採用した。
こうして本州全ての区間を入力していくと、北海道や九州の最長ルートを計算した時と同じように、ルートの選択肢が2通りや3通りしかない地点で、計算を分割できそうなことが分かる。まず、ルートの選択肢が2通りしかないのは、加古川・姫路−福知山・和田山（図21）と、新山口・厚狭−益田・長門市の2ヵ所が見つかる。
図21 図22
例として図21での計算分割の方法を考える。まず、@加古川・姫路のみ通過するケース、A福知山・和田山のみ通過するケース、B全て通過するケースに分ける。ここで、通常の片道最長ルートは北海道から九州まで一本道となることから、Bのケースが最長ルートになることはありえないことが分かる。どちらかのルートで一度西へ向かうと、再度そこを東へ向かうにはもう一方を通らなければならず、次に西へ向かう際のルートがなくなってしまうからである。従って、@Aの2ケースについて、分割したエリア毎に最長ルートを算出、足し合わせた距離の長い方が最長ルートとなる。
次に、ルートの選択肢が3通りしかないのが、富山・糸魚川−美濃太田・多治見−金山・名古屋（図22）（富山・糸魚川−塩尻・多治見−金山・豊橋でも可）、坂町・新発田−福島・郡山−いわき・岩沼、一ノ関・北上−新庄・横手−余目・秋田の3ヶ所である。
ルートの選択肢が3通りとなる図22でも同様に、@富山・糸魚川のみ通過するケース、A美濃太田・多治見のみ通過するケース、B金山・名古屋のみ通過するケース、C富山・糸魚川と美濃太田・多治見のみ通過するケース、D富山・糸魚川と金山・名古屋のみ通過するケースE美濃太田・多治見と金山・名古屋のみ通過するケース、F全て通過するケースに分ける。ここでも、ルートの選択肢が2通りの場合と同様に、3ルート中の2ルート通過となるCDEのケースが最長ルートになることはありえないことが分かる。つまり実際に計算しなければならないのは、@ABFの4通りだけである。
更に、ここで面白いことが分かる。Fのケースは、行って、戻って、もう一度行くということが可能であるので、ありうるパターンではあるが、戻って来ないルートが@ABの3通りあるのに対し、戻って来るルートはFの1通りしかないから、偶々それが最長ルートとなる確率は大雑把に言って1/4程度しかないと考えられる。ちなみに、ルートの選択肢が4通りあると、戻って来ないルートが4通り、戻って来るルートが4通りとなり確率は1/2に急上昇する。
つまり、最長片道ルートが羊腸たるルートを取る傾向があるといっても、事実上、ルートの選択肢が2、3通りの区間に分断されており、その間を跨いで行ったり来たりすることは殆どないと考えられるのである。
例えば、宮脇俊三の最長片道切符の旅では、「豊橋から会津若松まで引返す、という私の思い及ばなかったルートがそこに示されていた。（中略）目的地の枕崎に背を向けて二日間乗りつづけるのだから、最長片道切符ならではだ。しかし阿呆らしさもここまでくると、かえって厳粛な趣を呈してくるかに私は思うのだが。」と述べているが、良く見ると「豊橋から会津若松」の区間は富山・糸魚川−美濃太田・多治見−金山・名古屋（富山・糸魚川−塩尻・多治見−金山・豊橋でも可）と、坂町・新発田−福島・郡山−いわき・岩沼で区切られた区域の中だけを使ったルート選択であり、その区域からは一度も逸脱していないことが分かる。一応理論的にはこの区域を出入りするFのケースも考えられるのであるから、豊橋から会津若松まで引返すというルートはそれほど驚くに値しないのかもしれない。
さて、葛西氏は高性能なソルバーを使用しているので、日本全国を全て纏めて計算しているが、ＥＸＣＥＬのソルバーは本州全区間を一度に計算しようとすると変数が多すぎてエラーが出てしまう。そこで、上記の区分を利用して計算を分割することを考える。
まず、ルートの選択肢が2通りしかない地点で分割を行いブロック毎に計算を行うことを考えたが、加古川・姫路−福知山・和田より東側が変数が多すぎてエラーとなってしまった。次にルートの選択肢が3通りしかない地点で分割を行いブロック毎に計算を行うと、最もブロックが大きくなる、関東を含む部分が、1回の計算で最大20分程度時間が掛かるものの、なんとか計算を実施することができた。
分割は、坂町・新発田−福島・郡山−いわき・岩沼より北を東北地方（東北地方は小さいので、一ノ関・北上−新庄・横手−余目・秋田で分割しなくても纏めて計算可能であった）、富山・糸魚川−美濃太田・多治見−金山・名古屋より西を西日本地方、その間を東日本地方とし、接続部の区間は全て東日本地方に含めて計算することにした。
まず、東北地方は坂町・新発田−福島・郡山−いわき・岩沼が東日本地方との接続部となるため、次の4ケースについてそれぞれ最大値を求める。
| Ｈ（坂町・新発田） | Ｈ（福島・郡山） | Ｈ（いわき・岩沼） | 最大値 | ルート |
|---|
| ケース@ | 1 | 0 | 0 | 1316.9 | 図23
参照 |
| ケースA | 0 | 1 | 0 | 1430.0 |
| ケースB | 0 | 0 | 1 | 1491.4 |
| ケースC | 1 | 1 | 1 | 1369.0 |
次に、西日本地方についても、東日本地方との接続部を上記と同様に次の4ケースに分け、それぞれ最大値を求める。
| Ｈ（富山・糸魚川） | Ｈ（美濃太田
・多治見） | Ｈ（金山・名古屋） | 最大値 | ルート |
|---|
| ケース@ | 1 | 0 | 0 | 3202.5 | 図24
参照 |
| ケースA | 0 | 1 | 0 | 3283.1 |
| ケースB | 0 | 0 | 1 | 3329.6 |
| ケースC | 1 | 1 | 1 | 3131.1 |
最後に東日本地方については、東北地方との接続の組み合わせ4通り×西日本地方との接続の組み合わせ4通り＝16通りの組み合わせを計算する必要がある。
| 西日本地方 |
東
北
地
方 |
ケース名
最大値
（暫定最大値候補との差） |
ケース@ | ケースA | ケースB | ケースC |
3202.5
(-127.1) | 3283.1
( -46.5) | 3329.6
( 0.0) | 3131.1
(-198.5) |
| ケース@ | 1316.9
(-174.5) | ○ | ○ | ○ | ○ |
| ケースA | 1430.0
( -61.4) | ○ | ○ | ○ | ○ |
| ケースB | 1491.4
( 0.0) | ○ | ○ | 3533.6 | ○ |
| ケースC | 1369.0
(-122.4) | ○ | ○ | 3572.5
以下 | ○ |
ここで、16通り全ての最大値を求めるのは手間が掛かるため、以下のように簡略化し、計算回数を削減する。
まず、東北地方の最大値となるケースBと西日本地方の最大値となるケースBの組み合わせで東日本地方の最大値を求める。これが暫定的な全体最大値の候補となる。これが本当に最大値であれば、他の組み合わせは、最大値を計算する途中で、この値より小さくなるはずである。例えば、東北地方のケースAと西日本地方のケースAの組み合わせを考える場合、随時、部分巡回禁止制約を追加していく過程で、暫定的な全体最大値の候補である3533.6と比較した差が107.9(=東北地方61.4+西日本地方46.5)よりも小さくなったら、即ち、3641.5 (=3533.6+107.9)より小さくなった時点で、このケースは全体で現在の候補値よりも小さくなることが確定するため、部分巡回ルートを残したまま、計算を中断できることが分かるだろう。
次に、接続部をひとつひとつ特定して計算する前に、接続部の枝数によって16ケースを下表のように4つの範囲に分け、それぞれの最大値を計算して、さらに個別計算する必要のある範囲を絞り込むことを考える。下表は部分巡回禁止制約のない無制約最大値を計算した結果である。これにより上表の○部分は個別計算不要であることが分かる。
接続部の枝数
(東北、西日本) | (1,1) | (1,3) | (3,1) | (3,3) |
該当ケース
(東北、西日本) | 右記以外
（9ｹｰｽ） | (@,C) (A,C)
(B,C) | (C,@) (C,A)
(C,B) | (C,C) |
最大値
(3533.6との差) | 3567.4
以下
(33.8) | 3552.5
以下
(18.9) | 3660.2
以下
(126.6) | 3635.1
以下
(101.5) |
結局、残ったのは東北地方ケースC、西日本地方ケースBの組合せのみである。この組合せについて個別計算を行う。すると、岩沼−福島−郡山−いわき−岩沼の部分巡回ルートを禁止する制約式Ｈ（郡山,いわき）＝0を入れることで値が3572.5まで減少した。ここで、3572.5＜3533.6＋122.4であることから、このケースは暫定最大値候補より小さくなることが分かる。ただし、この部分巡回ルートは、東日本地方側で禁止するのではなく、東北地方側で禁止することも考えられる。そこで、東北地方の最大値をＨ（福島,岩沼）＝0の制約を追加して再計算してみると1318.0となった。これは、オリジナルの1491.4から173.4も減少している。接続部の枝数（3,1）の最大値3660.2＜3533.6＋173.4より、やはり暫定最大値候補より小さくなることが分かる。
以上により、東北地方ケースB、西日本地方ケースBとしたルートが最長片道ルートであることが示された。この場合の東日本最長片道ルートを図25に示しておく。
図23
図24
図25
更新記録
- 2005年7月17日
ＥＸＣＥＬワークシートにつき、下記のデータ訂正を行い、再計算した（川口氏の指摘による）。再計算により距離は変更となったが、ルートは変更なかった。
* 豊橋-辰野 195.8km→195.7km(2001年4月1日：天竜川治水工事に関連する川路駅移設の反映漏れ)
* 富山-敦賀 190.2km→190.1km(2002年10月21日：北陸新幹線建設に伴う東金沢駅移設の反映漏れ)
* 鳥取-伯耆大山 88.0km→87.9km(誤記修正)
* 広島-新山口 91.4km→154.5km(誤記修正)
なお、再計算に当たり、日暮里−尾久−赤羽と品川−西大井−鶴見を特定運賃計算キロから営業キロに置き換えた。
←前のページ 目次 次のページ→
Copyright(c) 2005 KONDO Hideaki All rights reserved.
初版： 2005年2月12日 最終更新： 2005年7月17日