ＥＸＣＥＬによる最長片道ルート探索
by 近藤 英明
■更新履歴
2012年5月14日更新
デスクトップ鉄氏のリンク先の変更を反映しました
■掲示板 … 疑問点、間違い等ありましたらこちらへどうぞ
「最長片道切符」とは、同じ駅を二度通らずになるべく遠回りする一筆書き切符で最長ルートのもののことである。
このサイトでは、最長片道ルートの探索方法を次のT・U・Vの３つに分けて紹介したいと思う。
T．ブロック分割による手計算での最長片道ルート探索
1．北海道
2．九州
U．ＥＸＣＥＬによる最長片道ルート探索
1.巡回セールスマン問題
2.最長片道ルート問題
3.簡単な計算例
4.ＪＲ最長片道ルートの計算
(1)新幹線を含む通常の最長片道ルート
(2)新幹線を含まない最長片道ルート
(3)本州循環型最長片道ルート
(4)東京近郊区間循環型最長片道ルート
V．ＥＸＣＥＬによる最長片道ルート探索：東京メトロ編
1.問題を解く際のルール
2.「枝」の設定と駅・区間の絞込み
3.ソルバーの制約式
(1)起点駅・終点駅にダミー変数を導入
(2)最低運賃区間の判定
(3)ラッチ外乗換え制約
(4)ＥＸＣＥＬシートのレイアウト例
4.最低運賃区間行列の作成
5.「東京メトロ大回り乗車」の最長ルート
○ 補遺
補1．東京近郊区間130円切符の最長大回りルート
補2．東京近郊区間150円切符の最長大回りルート
補3．1961年の東大旅研最長片道切符旅行は最長ではなかった？
補4．最長片道ルート計算の高速化（その1：整数制約を緩和）
補5．最長片道ルート計算の高速化（その2：ラグランジュ緩和）
補6．2010年3月版最長片道ルート
○ ＥＸＣＥＬワークシートのダウンロード
フリー百科事典『ウィキペディア（Wikipedia）』によると、最初に国鉄の最長片道切符旅行を行ったのは、東京大学旅行研究会の会員4名で、1961年7月に鹿児島県海潟駅から北海道広尾駅に至る12,145.3キロを旅行したものだという。
この時の最長ルートの探索は、全国を地域ブロックに分割し、各ブロックの最長ルートを求め、これを合算するという手法がとられたという。北海道と九州は、本州から切り離して計算し、また本州も列島方向に走る鉄道線が少ない地域で切断し、4ブロックに分割したらしい。
手計算で、少し複雑な最長片道ルート探索を行う場合、「ブロック分割」の考え方は必須のものであると思われる。しかし、実際に、探索過程と結果を示したものを私は見たことがない。
宮脇俊三氏の「最長片道切符の旅」（新潮文庫）では、電卓だけで最長片道ルート探索に挑戦しており、その時の様子について、「こういうのを順列組合せというのかどうかも知らないが、やってみると単位数が二倍になると組合せ数はその二乗くらいに増えるようであった。だから単位が九個しかない四国など簡単で一瞬にできてしまうし、四六個の北海道も六二個の九州もさしてむずかしくはない。（中略）けれども、国電区間が多く、線路の錯綜した東京付近から関東、中部にかけてはあまりに組合せが多すぎて、可能性のすべてを探るには一週間や一〇日でやれることではなかった。」と記している。
そこで、「ブロック分割による手計算での最長片道ルート探索」では、「さしてむずかしくはない」とされている北海道と九州の最長片道ルート探索について、実際の探索過程と結果を示すこととしたい。
2000年1月、当時東大大学院生であった葛西隆也氏は、整数計画法と全探索法によって最長ルート探索を行った。この結果は「最長片道きっぷの経路を求める」という表題でインターネット上に公開されており、これがおそらく最長ルート探索について最も丁寧に解説したものである。2004年5月のＮＨＫ番組「列島縦断 鉄道12000キロの旅−最長片道切符でゆく42日−」も彼の手法を使って東大鉄道研究会が行ったとのことである。
「ＥＸＣＥＬによる最長片道ルート探索」では、ＥＸＣＥＬの「ソルバー」によって、整数計画法を実行し、最長ルート探索する方法を示す。葛西隆也氏は整数計画法を高性能ソルバーで実行しているが、これでは一般人にはなかなか手が届かない
（追記1参照）。ＥＸＣＥＬで計算できるのなら、一般人でも追試可能だろう。ここでは、通常の最長片道ルートに加え、新幹線を使わない最長片道ルート、本州循環型の最長片道ルート、東京近郊区間循環型最長片道ルートなどいくつかの応用例を示す（追記3参照）。
ＪＲの最長片道ルートの探索の類似問題として、「東京メトロ大回り乗車」の最長ルートを計算するというものがある。これは、「東京メトロの乗車ルートは同一駅を通過しない限り最短経路で計算する」というルールを活用して初乗り運賃の切符でどこまで長い距離を乗車できるかという遊びのことである。
「ＥＸＣＥＬによる最長片道ルート探索：東京メトロ編」は、これを整数計画法によって解いたものである。これを解くためには、@「任意の初乗り運賃区間」に対して最長距離を求める必要があること、Aラッチ外乗換えする場合は起点から当該駅までの運賃が初乗り運賃であること、などの制約をクリアーしなければならない。ここでは、この具体的な方法と結果を示す（追記4参照）。
なお、今回の計算では、ＪＲは2004年3月の九州新幹線新八代-鹿児島中央開業、上越新幹線本庄早稲田駅開業まで、東京メトロは2003年3月の半蔵門線押上延長開業までを反映している。
また、ＪＲ最長片道ルートを計算する際に必ず問題となることに、運賃計算の特例により運賃計算キロと営業キロが異なるという現象があるが、今回は、時刻表記載の営業キロの最長を求めることに専念している。
しかし結果として、日暮里−尾久−赤羽と品川−西大井−鶴見だけは特定運賃計算キロを使用することになってしまった。日暮里−尾久−赤羽であれば、上野−尾久を東北本線下りページから、尾久−赤羽を東北本線上りページからキロ数を算出し、足し合わせた後、京浜東北線のページから算出した上野−日暮里のキロ数を引き算すれば正確な営業キロが求まるのであるが、最後の最後にそのことに気付いたので、時刻表記載の特定運賃計算キロを使用したままにしている(追記2参照)。
追記1（2005/5/22）
葛西隆也氏のウェブページに、新たに「2005年4月版（普及編）」が2005年4月9日付で掲載されていました。フリーのソフトウェアだけで、本州を分割することなくＪＲ全線を対象とした最長経路を求めることが可能になった、とのことです。「孤立ループが出現した場合、それを除去するための制約式を自動的に追加する」プログラムも準備されているところなど、さすがだと思いました。
追記2（2005/7/17）
ＥＸＣＥＬワークシートのデータ訂正を行ったのを機に、U.4.(1)(2)(3)は営業キロで再計算した結果を記載した。
また、本文中で注記しているが、補2.追記3、補5.追記1も営業キロで計算している。
追記3（2006/6/9）
ＥＸＣＥＬの「ソルバー」による最長片道ルート探索の決定版というべき「最長片道切符の変遷1961-2006」がデスクトップ鉄氏のウェブページに掲載された。これは、過去４５年間の国鉄・JRのネットワーク変遷の厳密な記録である同氏の「鉄道路線データベース」を駆使して、同氏自らがＥＸＣＥＬの「ソルバー」で計算したもので、その膨大な計算をこなし、最長片道切符変遷の全貌を纏めたことは驚嘆に値するといえよう。
ルートの変遷は、変更点を示した４３個の図を一つ一つ追いかけることによって味わうことができるが、その中でも見所の一つは、1997年3月22日の磐越西線磐梯熱海−上戸の改キロ（-0.7キロ）によって、東日本のルートが大幅に変更となり、豊橋−辰野−岡谷−小淵沢−小諸−高崎−小出−会津若松のルートが復活したことであろう（ただし、わずか半年後の1997年10月1日の長野新幹線開業時に同ルートは消滅）。
また、計算結果の考察がいろいろと報告されており、東日本ブロックと東北ブロックの接続駅のパターンが路線の改廃によって大きく変動していることなどは興味深い。東北新幹線開業前の東北ブロックは非常に移ろいやすいルート選定だったようである。
追記4（2006/6/9）
本編の応用例として、デスクトップ鉄氏の「メトロ･都営ラッチ外接続駅全制覇260円最長ルート」がある。難しそうな問題であるが、発着駅の絞込みに工夫を凝らすことで、意外と簡単に解を求めることができるようである。
次のページ→
Copyright(c) 2005-2012 KONDO Hideaki All rights reserved.
初版： 2005年2月12日 最終更新： 2012年5月14日
