旅/JR最長経路問題･厳密解

←旅/記事目次　　訪問:

佐藤和夫>　旅>
#2024年度版 (#最新 #2024 )

JR最長経路問題･厳密解


←スマフォでこの記事閲覧

今回変更点RSS1.0

　└→ もっと見る

はじめに

　それは、つねに新しい経路(ルート)をたどりながら、稚内駅から若井駅までの総延長13900.6kmを、一筆書きで乗りつくす旅です。　数的解析の結果分かったことですが、行き止まりの路線を除きすべてのJRの乗り換え駅をたどる旅でもありました。　この記事は、その経路をどのようにして求めたかを説明するものです。
　13900.6kmは地球半周よりも更に約2800km以上長くて、日本から地球の反対側のブラジルを越えて、大西洋のど真ん中までたどり着ける距離に相当します。　日本は広いですね。　また、JRの四分の三を乗り尽くします。　我が駅、平城山(ならやま)駅も通過することになっていたので、安心しました。

1.　JRの旅へのお誘い

　途中下車をせずに、JRの異なる経路を次々と乗り継いで旅をしたら、一筆書き出来る最長経路の乗車距離は何キロメートルぐらいになるのでしょうか？　いったい何駅から乗車し、最後にどこで下車することになるのでしょうか？　また、途中にどんな情景が待ち受けているのでしょうか？　これからご案内します。
　この旅は結論から言うと、稚内駅から若井駅までの、乗車距離合計13900.6 営業キロ[参照1.1]を、途中下車することなく乗り続けることになります。　最長経路は新幹線が出来たり、新駅が出来たり、ローカル線が廃止されるたびに変化します。　新駅が出来たらなぜ最長経路は変わるのだろう？と思われるかもしれませんが、新駅が出来るとそれにより新しい経路が出来上がるので、総延長距離は増える可能性が高いのです。

タグ: #佐藤和夫ようこそ #JR最長経路問題 #JR最長経路問題･厳密解 #JR最長経路の旅 #私鉄､廃線の旅 #JR #最長経路問題 #厳密 #最適解 #鉄道ファン #一筆書き #数的解析 #ルート #計算 #ルート動画 #グラフ #最長経路 #静岡大学

2.　JR最長経路問題とは何か

　ここでは、JRの「ある経路は一度だけ通過できる」こととして、ある特定日の一筆書きできる最長経路のルート、その時の乗車距離、発駅、着駅を求めようとします。
　なお、JRには最長片道切符[参照2.1]なるものがありますが、これは「ある駅は一度だけ通過できる」という条件で、一筆書きできる最長経路のルートを求めようとするものです。　これの数的解析はすでに行われています。
　それによると、2000年当時東大大学院生であった葛西隆也は、整数計画法と全探索という数学的に厳密な二つの方法で最長切符の経路（稚内→肥前山口、11､925.9キロ）を求めた。[引用2.1]という記述があります。　
またご本人による説明もWEBに記載されています[参照][参照2.2]

3.　一筆書きJR最長経路はこれだ！


　目で見るJR最長経路2024年3月18日ダイア改正版を次に示します。　地球の3／4を走る長さの、スローな旅をお楽しみください。動画では、次々に経路を青い線でたどります。　静止画はその最終形をお見せします。
　また､いくつかの駅は実際に出かけて様子を取材してきました｡　是非､ JR最長経路の旅をご覧ください｡

なお、JRには最長片道切符[参照2.1]なるものがありますが、これは「ある駅は一度だけ通過できる」という条件で、一筆書きできる最長経路のルートを求めようとするものです。　これの数的解析とは別物です。　詳細は､2.JR最長経路問題とは何かを参照ください｡

3.1　静止画で見るJR最長経路


　各地の静止画です。
各静止画中の青線が、最長経路で通過する経路を示します。　また、緑線は複数の経路が隣接していて描ききれないときに、あたかも往復されたと見える経路を緑で示します。　新幹線と在来線が並行している場合がそれにあたります。

図をクリックすると拡大します｡
　北海道
北海道 画像拡大画像拡大		 　本州
本州 画像拡大画像拡大		 　九州
九州 画像拡大画像拡大		 　四国
四国 画像拡大画像拡大

3.2　動画で見るJR最長経路


　北海道から四国までの､だいたい地球の2/3を走ることになるJR最長経路を､ゆっくり青線でたどります｡

☆広告無しはこちら
mp4ビューワーが必要です｡　うまく表示されないときは､↓のYouTube版でご視聴を
　└動画:　#北海道動画2022年度版 　
　└動画:　#本州動画2020年度版 　(24年度版は今しばらく､お待ちください｡)
　└動画:　#九州動画2023年度版
　└動画:　#四国動画 　

☆YouTube動画(↑で見られないとき､あるいは回線が遅いとき)はこちら
　└動画:　#北海道動画2022年度版　 　
　└動画:　#本州動画2020年度版　 　(24年度版は今しばらく､お待ちください｡)
　└動画:　#九州動画2023年度版
　└動画:　#四国動画　 　

　なお動画青線描画中に現れる緑線は、秋田新幹線と田沢湖線のように、物理的に同じ線を走るが、JR時刻表では別の線として紹介されているものをたどる場合と、新幹線と在来線がきわめて近いところを並列に走るために、地図上では複数線として紹介しぬくいものを、往復で通過していることを表しています。
　

3.3　最長経路解


　「ある経路は一度だけ通過できる」こととして、2024年4月1日現在の、JRの一筆書きできる最長経路のルート、その時の乗車距離、発駅、着駅は、次の通りです。　2014/4/1版から計算法の改良により、計算時間は1時間程度になりました。　今回はそれと同じです｡

　稚内駅から乗車し若井駅までの総延長で、乗車距離合計13900.6営業キロです。 ここでは、北海道内と、本州→九州→本州→四国を分けて表示しました。
なお青色の駅は､実際に訪ねたレポート(JR最長経路の旅)がある駅です｡　こちらもクリックしてお楽しみ頂ければ幸いです｡

北海道内：稚内,木古内,1410.0営業キロ,
(稚内駅=*宗谷本線=筬島駅=音威子府駅=天塩川温泉駅=美深駅=名寄駅=*宗谷本線=新旭川=*石北本線=東釧路=*根室本線=新得=*石勝線=追分=*室蘭本線=沼ノ端=*千歳線=南千歳=*石勝線=追分=*室蘭本線=岩見沢=*函館本線=白石=*函館本線=桑園=*函館本線=長万部=*函館本線+北海道新幹線=木古内=*本州へ)

本州→九州→本州→四国：木古内,若井,12490.6営業キロ,
本州
(木古内=*北海道新幹線=新青森=*奥羽本線=川部=*五能線=十二湖駅=*五能線=東能代駅=*奥羽本線=秋田駅=*秋田新幹線=大曲=*秋田新幹線=盛岡=*東北本線=花巻=*東北本線=北上=*東北本線=一ノ関=*東北本線=小牛田=*石巻線=前谷地=*仙石線=多賀城駅=*仙石線=仙台=*東北本線=小牛田=*陸羽東線=古川=*陸羽東線=新庄=*山形新幹線=天童=*奥羽本線=新庄=*奥羽本線=横手=*北上線=北上=*東北新幹線=新花巻=*東北新幹線=盛岡=*田沢湖線=大曲=*奥羽本線=秋田駅=*羽越本線=余目=*羽越本線=坂町=*米坂線=米沢=*奥羽本線=福島=*山形新幹線=米沢=*奥羽本線=山形=*山形新幹線=天童=*奥羽本線=南出羽=*奥羽本線=羽前千歳=*仙山線=仙台=*東北新幹線=福島=*東北新幹線=郡山駅=*東北本線=福島=*東北本線=岩沼=*常磐線=いわき=*常磐線=日立駅=*常磐線=水戸駅=*水郡線=安積永盛=*東北本線=新白河=*東北本線=黒磯=*東北本線=那須塩原=*東北本線=宇都宮=*東北新幹線=小山=*東北新幹線=大宮=*川越線=高麗川=*八高線=倉賀野=*高崎線=熊谷=*上越新幹線=大宮=*東北新幹線=上野=*山手線=秋葉原=*山手線=神田=*中央本線=御茶ノ水=*中央本線=代々木=*山手線=大崎=*山手線=品川=*横須賀線=武蔵小杉=*南武線=尻手=*鶴見線=鶴見=*横須賀線=武蔵小杉=*南武線=府中本町=*武蔵野線=西国分寺駅=*武蔵野線=武蔵浦和=*埼京線=大宮=*京浜東北線=南浦和=*武蔵野線=武蔵浦和=*埼京線=北赤羽=*埼京線=赤羽=*京浜東北線=田端=*山手線=池袋=*山手線=新宿=*中央本線=西国分寺駅=*中央本線=国立駅=*中央本線=立川=*青梅線=拝島=*八高線=八王子=*中央本線=甲府=*見延線=富士=*東海道本線=静岡=*東海道新幹線=豊橋=*東海道新幹線=三河安城=*東海道本線=豊橋=*東海道本線=静岡=*東海道新幹線=三島=*東海道本線=沼津=*御殿場線=国府津=*東海道本線=小田原駅=*東海道新幹線=三島=*東海道本線=小田原駅=*東海道新幹線=新横浜=*横浜線=橋本=*相模線=茅ヶ崎=*東海道本線=大船=*根岸線=横浜=*東海道本線=東神奈川=*横浜線=新横浜=*東海道新幹線=東京=*京葉線=市川塩浜=*京葉線=西船橋=*武蔵野線=新松戸=*武蔵野線=三郷=*武蔵野線=南浦和=*京浜東北線=赤羽=*東北本線=日暮里=*山手線=上野=*東北新幹線=東京=*総武線=錦糸町=*総武本線=西船橋=*武蔵野線=南船橋=*京葉線=蘇我=*外房線=大網=*内房線=蘇我=*内房線=千葉=*総武本線=佐倉=*総武本線=成東=*総武本線=成田=*総武本線=我孫子=*常磐線=友部=*水戸線=小山=*東北本線=大宮=*高崎線=熊谷=*上越新幹線=高崎=*上越新幹線=越後湯沢=*上越線=渋川=*上越線=新前橋=*両毛線=小山=*東北本線=自治医大=*東北本線=宇都宮=*東北新幹線=那須塩原=*東北新幹線=新白河=*東北新幹線=郡山駅=*磐越西線=会津若松=*磐越西線=喜多方=*磐越西線=新津=*羽越本線=新発田=*白新線=新潟駅=*信越本線=新津=*信越本線=東三条=*信越本線=長岡=*上越新幹線=燕三条=*上越新幹線=新潟駅=*越後線=吉田=*越後線+信越本線=宮内=*信越本線=長岡=*上越新幹線=浦佐=*上越新幹線=越後湯沢=*上越線=浦佐=*上越線=小出=*上越線=越後川口=*飯山線=飯山=*北陸新幹線=糸魚川=*大糸線=松本=*篠ノ井線=姨捨(おばすて)駅=*篠ノ井線=長野=*北陸新幹線=佐久平駅=*八ヶ岳高原線=小淵沢=*中央本線=岡谷=*中央本線=辰野=*中央本線=塩尻=*中央本線=多治見=*中央本線=金山=*東海道本線=三河安城=*東海道新幹線=名古屋=*関西本線=桑名=*関西本線=亀山=*紀勢本線=和歌山=*阪和線=天王寺=*関西本線=久宝寺=*関西本線=王寺=*和歌山線=高田=*桜井線=奈良=*関西本線=平城山(ならやま)駅=*関西本線=木津=*関西本線=柘植=*草津線=草津=*東海道本線=米原=*北陸本線=近江塩津=*湖西線=山科=*東海道本線=京都=*東海道本線=新大阪=*山陽新幹線=西明石=*山陽本線=尼崎=*JR東西線=京橋=*大阪環状線=大阪=*東海道本線=新大阪=*東海道新幹線=京都=*東海道新幹線=米原=*東海道新幹線=名古屋=*東海道本線=岐阜=*高山本線=美濃太田=*高山本線=富山=*北陸新幹線=敦賀=*小浜線=綾部=*山陰本線=京都=*奈良線=木津=*片町線=放出=*片町線=鴫野=*片町線=京橋=*大阪環状線=天王寺=*大阪環状線=大阪=*山陽本線=尼崎=*福知山線=谷川=*加古川線=加古川=*山陽本線=西明石=*山陽新幹線=姫路=*播但線=和田山=*山陰本線=鳥取=*山陰本線=伯耆大山=*山陰本線=宍道=*木次線=備後落合=*芸備線=備中神代=*伯備線=新見=*伯備線=総社=*吉備線=岡山=*山陽新幹線=新倉敷=*山陽本線=福山=*山陽本線=三原=*呉線=海田市=*山陽本線=三原=*山陽新幹線=広島=*山陽新幹線=徳山=*山陽新幹線=新山口=*山陽新幹線=厚狭=*山陽本線=新下関=*九州へ=幡生=*山陽本線=新下関=*山陽新幹線=厚狭=*美祢線=長門市=*山陰本線=益田=*山口線=新山口=*山陽本線=宇部=*山陽本線=小野田=*小野田線=居能=*宇部線=新山口=*山陽本線=徳山=*山陽本線=櫛ヶ浜=*岩徳線=岩国=*山陽本線=広島=*芸備線=塩町=*福塩線=福山=*山陽新幹線=新倉敷=*山陽本線=倉敷=*山陽本線=岡山=*山陽新幹線=相生=*山陽本線=東岡山=*赤穂線=相生=*山陽本線=姫路=*姫新線=東津山=*姫新線=津山=*津山線=岡山=*四国へ)

九州
(新下関=*山陽新幹線=小倉=*鹿児島本線=西小倉=*鹿児島本線=折尾=*鹿児島本線=香椎=*香椎線=長者原=*篠栗線=吉塚=*鹿児島本線=博多=*九州新幹線=新鳥栖=*長崎本線=鳥栖=*鹿児島本線=久留米=*鹿児島本線=筑後船小屋=*鹿児島本線=熊本=*九州新幹線=新八代=*九州新幹線=川内=*鹿児島本線=鹿児島中央=*日豊本線=隼人=*肥薩線=吉松=*えびの高原線=都城=*日豊本線=南宮崎=*日豊本線=大分=*阿蘇高原線=熊本=*九州新幹線=筑後船小屋=*九州新幹線=久留米=*ゆふ高原線=夜明=*ゆふ高原線=大分=*日豊本線=別府駅=*日豊本線=城野=*日田彦山線=田川後藤寺=*後藤寺線=新飯塚=*筑豊本線=桂川=*筑豊本線=原田=*鹿児島本線=博多=*山陽新幹線=小倉=*鹿児島本線=幡生)

四国
(岡山=*瀬戸大橋線=宇多津=*高徳線=佐古=*徳島線=佃=*土讃線=多度津=*予讃線=若井駅)

注）
  1. データはJTB時刻表2024年3月号、2024年3月1日発行に依ります。
  2. 「経路」とは、この時刻表索引地図P4〜P21の経路図に表示されたものを指します。
    • ここでは、実際には物理的に別線であるものが、一つの経路として記入されている例、たとえば横須賀線の大船横浜間がありますが、経路図通りに一つの経路として入力しています。
    • 逆に実際には物理的に一つの路線であるものが、二つの経路として記入されている例、たとえば秋田新幹線と田沢湖線がありますが、経路図通りに二つの経路として入力しています。
    • また、この経路図には、新子安から品川間が横須賀線であり、新子安に停車するかのように表示されていますが、その通りに新子安と品川間を一つの経路として扱っています。
    • 他にも類似の例がありますが、すべて経路図通りに経路を入力しています。
    • 貨物線に乗り入れる場合として､二重線での表記が登場しています｡　たとえば､府中本町から鶴見がそれに当たります｡　特急列車が貨物線を利用しているようです｡　これについては､今回経路として入力していません。
  3. 一部の区間で一つの経路に複数の路線が乗っている場合、たとえば山手線と京浜東北線の日暮里〜品川間がありますが、便宜上片方のみを経路名として使用しました。
  4. JTB時刻表2001年5月号当時の最長経路は2007/1/14版　JR最長経路問題･厳密解3章をご覧ください 。

>4.　JR最長経路問題の数的解析は大変

↑クリックすると､別ページへ飛びます｡

5.　JR最長経路問題・残る課題とその解決

・計算結果は、行き止まり経路を除く、通過できるすべての駅を通過しています。　福知山駅は通過していませんが、これは通過できない駅です。　したがって、JR定理1の適用が可能です。
なぜ福知山駅だけが通過できないかについての詳細な説明は､JR最長経路の旅>福知山駅をご覧ください｡

・いただいたご質問への回答を用意しました｡

・藩を整理し合併させることにより、おそらく1時間程度で計算出来るようになる気がします。　次回やってみようと思います。
・上では計算に2ヶ月必要だったと書きましたが、JR定理1「若井が必ず着駅だと分かったこと」を執筆の途中で発見したことにより、四国を含めた再計算では、それまで2ヶ月要していたものが、1ヶ月弱になりました。　更に、最新の計算では8日間に短縮されました。
・現状では多大な計算時間が必要です。　計算時間短縮のためには、整数計画法の採用が有効と思われますが、必ず解けると言うわけではないようです。　今回、ループ解は最長経路解となり得ないという証明ができましたので、この採用にある程度の見通しが出てきました。
・また、今回採用した全探索についても、　現状のプログラムでは、ループ解も求められるし、発駅、着駅はどこでも良いと言ったアルゴリズムを採用しています。　が、今回発見したJR定理1を前提としたアルゴリズム、たとえば発駅、着駅が固定できる場合の、連結グラフにおける迷路の解法を採用すれば、飛躍的に計算時間が短縮できると思います。　多分1日程度になるのもわりとすぐではないでしょうか。
　今回の追記：連結グラフにおける迷路の解法で今回解いてみましたが、予想と異なり逆に遅くなる結果となりました。　このあたり常識とは異なりますが、なぜそういう結果になるのかは、書き残しておくと後世のためになると思いますので、後で加筆します。

参照､引用

　　[参照1.1]営業キロ､ウィキペディア
　　[参照2.1][引用2.1]最長片道切符､ウィキペディア
　　[参照2.2][引用2.2]最長片道きっぷの経路を求める[参照]、葛西隆也
　　[参照4.1] 整数計画法､ウィキペディア
　　[参照4.2] モンテカルロ法、ウィキペディア
　　[参照4.3] 連結グラフにおける迷路の解法、ウィキペディア　リンク切れ
　　[参照4.4] グラフ理論、ウィキペディア
　　[参照4.5] オイラーの一筆書き定理、ウィキペディア　リンク切れ
　　[参照5.1] 竜飛海底駅､ウィキペディア
　　[引用5.2] 開業・廃止予定線一覧[引用5.2]､鉄道の旅・情報館
　　[引用5.3] 山田線､ウィキペディア
　　[参照5.4] 上野東京ライン､ウィキペディア
　　[引用5.5] 留萌本線､ウィキペディア
　　[参照5.6] 三江線､ウィキペディア
　　[参照5.7] おおさか東線､ウィキペディア
　　[参照5.8] 石勝線､ウィキペディア
　　[参照5.9] 日高線､ウィキペディア

謝辞

　執筆にあたり、次の方々に貴重なご助言をいただきました。　感謝いたします。　なお、敬称は省略させて頂きました。　また､肩書きは2006年当時のものです｡

改訂履歴






















>詳細目次