最長片道きっぷの経路を求める
Index & Overview

あらまし

 この文書は、JRの最長片道きっぷの経路を、 整数計画法と全探索の2つの方法で求めた過程をまとめたものです。 前者では厳密に、後者ではややイイカゲンに、その経路を求めることに成功し、 2つの方法で求めた経路は一致しました。


トピックス

 NHK の紀行番組「列島縦断 鉄道12000kmの旅」をきっかけにこの Web ページを探し当てた方は、まず「付録2(2004年3月版)」をご覧ください。 現状の最長片道きっぷの経路や、ありそうな質問をまとめてあります。

 ふと思い立って、2006年5月版の最長片道きっぷ経路図(PDF 形式、35,414 bytes)を作りました。
 2004年3月版の地図との相違点はただ1点、 「富山港線を削除した」ことです(2006年2月28日廃止)。 もともと最長経路に含まれていなかった路線が廃止になっただけなので、 再計算するまでもなく、最長経路は不変です。
 また、2006年5月1日、指宿枕崎線の終着駅である枕崎駅が移転し、 鹿児島中央からの営業キロ・擬制キロが0.1km短くなりました。 これも、最長経路に含まれない路線が短縮されただけですので、 最長経路には影響しません。


全文をダウンロードできます

 この文書はかなりの長文ですので、オンラインで読むのがつらい人のために、 必要なファイルをまとめたアーカイブ (LHA (-lh5-)、482Kbytes、2005年 4月 9日 最終更新)を作成しました。 ご活用ください。
 なお、アーカイブの最終更新日以降にも本文に修正・追加を行っており、 その結果はまだアーカイブに反映されていません。


最長片道きっぷとは?

 「最長片道きっぷ」とは、文字どおり、片道きっぷの中で最長のものです。 いろいろな鉄道会社について最長片道きっぷを考えることができますが、 たとえば紀州鉄道の最長片道きっぷはどこからどこまでか、 というのは自明なので、ここではJR6社について考えます。

 紀州鉄道は日本最小の部類に属する私鉄で、路線は1本、総延長は2.7kmです。

 JRの普通片道乗車券は、原則として

という2つの条件を満たす任意の駅間・経路に対して発売されます。 ここで「環状線一周」とは、「ループ状の経路をたどって、 以前に通った駅にふたたび到達する」ことをさします。 かんたんにいえば「以前に通った駅に到達して、 さらにその先へ進む」という経路が後者の条件によって除外されています。
 そして、発売され得る片道乗車券のうち、 発駅から着駅までの距離が最も長いものを、 俗に「最長片道きっぷ」と呼んでいます。
 この「最長片道きっぷ」の経路を求めるとしたらどうすればいいんだろう?  それを考えた記録がこの文書です。

 そして、考えただけで飽きたらなくなった結果が PROJECT LOP です。:-)


2つのアプローチ

 最長片道きっぷのルートを求めるにはいくつかの方法が考えられますが、 今回用いたのは、整数計画法(Integer Programming) と全探索の2つです。
 前者は、最適な組合せを求めるような問題で実用的に使われている、 いわば「賢い」方法です。
 それに対し後者は、何も考えずにすべての組合せを列挙し、 その中から一番いいものを探そう、 というごく単純なもので、だれでも思いつく「おバカ」な方法です。 ただし、この問題をそのまま全探索で解くと、 現在のコンピュータの性能では答えが出る前に地球の寿命が来る恐れがあります。 少なくともコンピュータの寿命は来るでしょう。:-) したがって、問題を細かく分割するなどのくふうが必要になります。 主にこのくふうが見どころです。


本編の目次

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

 本編は2000年1月現在の路線図をもとに計算を行ったものです。 それ以降、最長経路が変化した場合には「付録」でお知らせし、 原則として本編には手を加えません。


付録1(2002年12月版)の目次

  1. 付録1:経路編
  2. 付録1:計算編
  3. 付録1:新戦略編
  4. 付録1:特例編

付録2(2004年3月版)の目次

  1. 付録2:経路編
  2. 付録2:質問編
  3. 付録2:質問編九州版

付録3(2005年4月版)の目次

  1. 付録3:数式編
  2. 付録3:普及編

著者

 この文書の著者は葛西隆也です。 研究をしたのも著者ですが、整数計画法を用いた解の導出に関しては、 宮代くんとの共同研究です(詳細は「[6] その他」を参照)。



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