最長片道きっぷの経路を求める
[4] これが最長ルートだ!

このページのあらまし

 整数計画法を用いて、 あるいは全探索を用いて最長片道きっぷのルートを求めた結果、 どのようなルートが求まったかを示します。
 ちなみに、どちらの方法で求めても同じ結果が得られました。


目次

  1. 問題の分析
  2. 整数計画法で
  3. 全探索で
  4. これが最長ルートだ!
  5. よくある質問と答え
  6. その他

最長ルートの概要

 求まった最長ルートは、北海道の北端、稚内を起点とし、 九州は佐賀県、肥前山口に至るというものでした。運賃計算キロは11925.9km。 JRの路線網は全体で約20000kmですから、一気に約6割も乗れるわけです。
 なお、九州内の最長ルートを求めたときに書いたとおり、 九州内はタイプPになっています。つまり肥前山口駅を2度通ります。 このため、逆方向の「肥前山口発稚内着」は片道乗車券になりません。


書き下してみると…

 まず、手っ取り早く文字で最長ルートを表してみましょう。 実は、この文書の筆者は MS-DOS で動くJRの運賃計算システムも作っていて、 それに最長片道きっぷのねだんを計算させた結果、以下のような出力となりました。

---- - ---- - ---- - ---- - ---- - ---- - ---- - ---- - ----
稚内 → 肥前山口

経 由:宗谷,石北,釧網,根室,富良野,函館,[岩見沢],室蘭,千歳,函館,
        江差,海峡,津軽,東北,花輪,奥羽,[川部],五能,[東能代],奥羽,
        羽越,米坂,奥羽,田沢湖,山田,釜石,東北,大船渡,気仙沼,石巻,
        陸羽東,東北新幹線,[(北)福島],東北,[岩沼],常磐,磐越東,
        磐越西,信越1,[長岡],上越新幹線,越後,[柏崎],信越1,上越,
        飯山,信越1,北陸,大糸,篠ノ井,信越1,北陸新幹線,
        上越新幹線,[越後湯沢],上越,両毛,東北,水郡,常磐,武蔵野,
        東北,[赤羽],埼京,山手2,東北,総武2,総武,[佐倉],成田,
        [松岸],総武,東金,外房,[安房鴨川],内房,京葉,東北,中央東,
        武蔵野,埼京,高崎,八高,青梅,南武,東海道,[品川],東海道3,
        [鶴見],東海道,[横浜],根岸,[大船],東海道,[国府津],御殿場,
        [沼津],東海道,身延,中央東,横浜,新幹線,[小田原],東海道,
        [三島],新幹線,[静岡],東海道,飯田,中央2,[岡谷],中央東,
        中央西,東海道,関西,紀勢,和歌山,桜井,関西,[天王寺],
        大阪環状,片町,関西,草津,東海道,湖西,北陸,東海道,高山,
        北陸,小浜,舞鶴,山陰,東海道,[新大阪],新幹線,[西明石],
        山陽,東海道,福知山,山陰,因美,姫新,山陽,[相生],赤穂,
        [東岡山],山陽,津山,姫新,伯備,山陽,福塩,芸備,伯備,山陰,
        三江,芸備,山陽,[岩国],岩徳,[櫛ヶ浜],山陽,山口,山陰,美祢,
        山陽,鹿児島,[小倉],新幹線,[博多],鹿児島,篠栗,香椎,鹿児島,
        [西小倉],日豊,吉都,肥薩,日豊,[鹿児島],鹿児島,久大,
        日田彦山,後藤寺,筑豊,[原田],鹿児島,長崎,佐世保,大村,長崎

      JR線営業キロ:11514.4km   運賃計算キロ:11925.9km
  JR北海道営業キロ: 1601.5km   運賃計算キロ: 1685.1km
    JR九州営業キロ: 1198.8km   運賃計算キロ: 1226.0km

普通片道運賃   :大人 93870円  小児 46930円  学割 75090円
---- - ---- - ---- - ---- - ---- - ---- - ---- - ---- - ----

 詳しい人なら、これを見ただけでルートが把握できるでしょう。 ただ、そうでない人はこれだけ見てもわけが分かりませんし、 詳しい人にしても、全体を見渡してみてはじめておもしろみが分かるものです。


地図で味わう最長ルート

 というわけで、最長ルートを地図にしてみました。この地図は LOP 算出プロジェクト用に自作したプログラムによって出力されたものです。 ソルバーの出力する解を入力するとそれを地図にして出力することもできるので、 ループ除去作業には威力を発揮しました。
 地図はかなり大きな画像なので、ここでは本州の地図の縮小版だけを示します。 全国版のフルサイズの地図は PDF 形式および Postscript 形式で用意してありますので、興味があればダウンロードしてご覧ください。

最長片道きっぷ(本州)

地図のダウンロード

 Postscript のソースは美しくないので、あんまり見てほしくないかも…



(c) SWA / KASAI TakayaSWA へメールを送る
最終更新: 2000年 2月29日
簡易包装にご協力ください。