この文書は、ＪＲの最長片道きっぷの経路を、 整数計画法と全探索の２つの方法で求めた過程をまとめたものです。 前者では厳密に、後者ではややイイカゲンに、その経路を求めることに成功し、 ２つの方法で求めた経路は一致しました。
NHK の紀行番組「列島縦断 鉄道12000kmの旅」をきっかけにこの Web ページを探し当てた方は、まず「付録２（2004年３月版）」をご覧ください。 現状の最長片道きっぷの経路や、ありそうな質問をまとめてあります。
ふと思い立って、2006年５月版の最長片道きっぷ経路図（PDF
形式、35,414 bytes）を作りました。
2004年３月版の地図との相違点はただ１点、
「富山港線を削除した」ことです（2006年２月28日廃止）。
もともと最長経路に含まれていなかった路線が廃止になっただけなので、
再計算するまでもなく、最長経路は不変です。
また、2006年５月１日、指宿枕崎線の終着駅である枕崎駅が移転し、
鹿児島中央からの営業キロ・擬制キロが0.1km短くなりました。
これも、最長経路に含まれない路線が短縮されただけですので、
最長経路には影響しません。
この文書はかなりの長文ですので、オンラインで読むのがつらい人のために、
必要なファイルをまとめたアーカイブ
（LHA (-lh5-)、482Kbytes、2005年 4月 9日 最終更新）を作成しました。
ご活用ください。
なお、アーカイブの最終更新日以降にも本文に修正・追加を行っており、
その結果はまだアーカイブに反映されていません。
「最長片道きっぷ」とは、文字どおり、片道きっぷの中で最長のものです。 いろいろな鉄道会社について最長片道きっぷを考えることができますが、 たとえば紀州鉄道の最長片道きっぷはどこからどこまでか、 というのは自明なので、ここではＪＲ６社について考えます。
紀州鉄道は日本最小の部類に属する私鉄で、路線は１本、総延長は2.7kmです。
ＪＲの普通片道乗車券は、原則として
という２つの条件を満たす任意の駅間・経路に対して発売されます。
ここで「環状線一周」とは、「ループ状の経路をたどって、
以前に通った駅にふたたび到達する」ことをさします。
かんたんにいえば「以前に通った駅に到達して、
さらにその先へ進む」という経路が後者の条件によって除外されています。
そして、発売され得る片道乗車券のうち、
発駅から着駅までの距離が最も長いものを、
俗に「最長片道きっぷ」と呼んでいます。
この「最長片道きっぷ」の経路を求めるとしたらどうすればいいんだろう？
それを考えた記録がこの文書です。
そして、考えただけで飽きたらなくなった結果が PROJECT LOP です。:-)
最長片道きっぷのルートを求めるにはいくつかの方法が考えられますが、
今回用いたのは、整数計画法（Integer Programming）
と全探索の２つです。
前者は、最適な組合せを求めるような問題で実用的に使われている、
いわば「賢い」方法です。
それに対し後者は、何も考えずにすべての組合せを列挙し、
その中から一番いいものを探そう、
というごく単純なもので、だれでも思いつく「おバカ」な方法です。
ただし、この問題をそのまま全探索で解くと、
現在のコンピュータの性能では答えが出る前に地球の寿命が来る恐れがあります。
少なくともコンピュータの寿命は来るでしょう。:-)
したがって、問題を細かく分割するなどのくふうが必要になります。
主にこのくふうが見どころです。
本編は2000年１月現在の路線図をもとに計算を行ったものです。 それ以降、最長経路が変化した場合には「付録」でお知らせし、 原則として本編には手を加えません。
この文書の著者は葛西隆也です。 研究をしたのも著者ですが、整数計画法を用いた解の導出に関しては、 宮代くんとの共同研究です（詳細は「[6] その他」を参照）。