最長片道きっぷの経路を求める
[5] よくある質問と答え

このページのあらまし

 ここまでの内容を読んだ人が抱くであろう疑問、 あるいは実際に受けた質問に対する回答をここにまとめておきます。 ここを読んでも疑問が解決しない場合は筆者にメールを送るなどしてください。


目次

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

もっと長くなりそう!編

[Q] 北上→一ノ関で近道を通っているんですけど?
[A] 実際には距離は同じです。

 新幹線と在来線が並行している区間のうちの一部では、 最長ルートの計算にあたって新幹線と在来線の両方を考慮しなくてはなりません。 そのような区間では、地図に新幹線と在来線の双方を描いています。 地図では、両者の長さが異なって描かれている場合がありますが、 実際には新幹線と在来線の長さは同じです。 より正確には、「新幹線と在来線は同距離として扱う」と定められています。
 最長片道きっぷの経路のうち、 以下の区間は新幹線と在来線が別々に地図に描かれていて、かつ、 新幹線と在来線のどちらを通っても発売条件が成立します。 両者の距離は同じなので、どちらを通っても最長のルートになります。

 距離が同じ2つのルートのうち、どちらを選択するかは「ソルバーの好み」です。 深い意味はありません。

 2002年12月時点での最長経路は北上・一ノ関間を通らなくなっています。

[Q] 天王寺→京橋はもっと距離がかせげるのでは?
[A] 運賃計算の特例により、その経路は使えません。

 大阪付近の拡大図を見ると、天王寺から京橋へ行くのに鶴橋を経由しています。 距離をかせぐためには、西九条、 大阪と回って大阪環状線を3分の2周したほうがよさそうです。
 が、大阪環状線とその周辺の路線を通過する場合には、 その区間の運賃を最短経路で計算しなくてはならないという特例があるため、 天王寺・京橋間について、 「天王寺→西九条→大阪→京橋」という経路で運賃を計算することはできません。 最短経路の「天王寺→鶴橋→京橋」で運賃を計算することになります。 特例の詳細については [付録1-4] にまとめてあります。
 地図には「運賃計算経路」を示したため、 一見したところ最長でない経路が描かれていますが、 実際に運賃の計算できる経路としてはこれが最長のものです。

 実は、対象区間内の駅である尼崎をあとでかすっているので、ちょっと微妙です。 というのは、「大阪環状線とその周辺の路線を2度以上通過する場合には、 実際に乗車する経路で運賃を計算してよい」という「特例の特例」があるからです。 今回の行程では、対象区間を一度通過したのち、尼崎で「かする」ので、 2度通過という見かたもできます。
 なお、首都圏にも同様の特例がありますが、 首都圏の場合は文句なしに2度以上通過(4度通過)なので、 実際に乗車する経路で運賃を計算することができました。

 なお、同様の特例は以下の区間にもあてはまります。

 これらの特例が最適解を変えないことは確認済みです。 つまり、最長経路として経路Aが算出されたが、 この経路は運賃計算の特例に該当するために距離が短縮され、 その結果、実際には別の(特例に該当しない)経路Bが最長となる、 といった事例は存在しないことが確認されています。

[Q] 相生→東岡山間も短いほうを通っている気が…
[A] 運賃計算キロは赤穂線回りのほうが長いのです。

 最長ルートは相生・東岡山間で赤穂線を経由していますが、 地図を見る限り、この区間は山陽本線を経由したほうが長くなりそうです。 実際、営業キロは赤穂線経由より山陽本線経由のほうが長くなっています。
 しかし、運賃計算に用いる距離は赤穂線経由のほうが長い (赤穂線は地方交通線=ローカル線で、 実際の距離を1割増して運賃計算に用いる)ので、 「運賃計算キロのもっとも長い片道乗車券」を求めるという立場からは、 赤穂線経由を選ぶことになります。

 このほかにも、地図が不正確なので「わざわざ近道をしているように見える」 事例があるかもしれません。 用意した地図は、2頂点間を直線で結んだだけの単純なものなので、 地図上の距離をあまり信用してはいけません。

[Q] 全体の距離を計算したら3.6km長くなったのですが…
[A] 博多・吉塚間の往復分の距離は特例で除かれます。

 最長片道きっぷのルートの距離を計算してみたところ、 前ページに書かれた結果(11925.9km)よりも3.6km長くなった、 という人がいるかもしれません。 あのルートの距離を手計算したというだけで尊敬に値しますが(^^;
 この原因は、おそらく博多・吉塚間の往復分の距離を算入するかどうかにあります。 最長ルートは山陽新幹線で博多に至り、そこから鹿児島本線で1駅「逆行」、 吉塚から篠栗線に入っていますが、このようなルートをとる場合、博多・吉塚間 (片道1.8km)の往復分の距離は運賃計算に含まないという特例があります。 したがって、この特例を考慮した場合とそうでない場合には、 距離が3.6kmちがってきます。

 なお、この特例を適用しなければ博多で「折り返す」ことはできないため、 「新幹線→博多→吉塚→篠栗線」といったルートをとる限り、 この特例の適用は不可避であるといえます。 また、博多で「折り返さない」ルートの中で最長のものが、 (たとえ3.6kmを引き去っても)博多で「折り返す」ものに及ばない、 ということは確認済みです。

[Q] 阪和貨物線を利用すると距離が延びそうですが…
[A] 現在は旅客列車がなく、やや無理があります。

 関西本線の八尾と阪和線の杉本町を結ぶ阪和貨物線(短絡線)は、 梅田貨物線や東海道貨物線、山手貨物線のように 「近くを通る旅客線と同一線として扱う」のではなく、 独立した路線とみなされ、営業キロも設定されています。 10年ほど前までは、臨時ながら旅客列車が走っていました。
 この阪和貨物線を用いれば、確実に最長片道きっぷは長くなります。 京阪神の拡大図を見れば分かりますが、八尾から天王寺に直行するところ、 「八尾→杉本町→天王寺」というルートをとれるようになり、距離は9.9km延びます。 この路線が使えるようになったことで、他の部分に影響が出て、 さらに長くなることも考えられます。
 が、現在のところ、阪和貨物線には旅客列車がまったく走っておらず、 この路線を組み込んだ乗車券を発行することにはやや無理がありそうです。 もし、期間限定でもこの路線に旅客列車が復活するのであれば、 そのときを狙ってより長い乗車券を買うことができるのですが。

[Q] ものの本に載っていたルートとちがうんですが…
[A] たぶん私たちのほうが長いでしょう。

 最長片道きっぷのルートを載せた本はいくつか出版されていますが、 そのほとんどは、 九州内のルートが私たちと異なっているのではないかと思われます。
 九州内のルートに関しては、 新幹線の別線扱いにからむ規程の解釈によって揺れています。 考えうる妥当な解釈は2つあって、そのうちの1つにもとづくと、 私たちの算出したルートがおそらく最長であると思われます。
 その本のルートが小倉・博多間で新幹線と在来線の双方を用いていない場合には、 それはおそらく規程の解釈が異なるのだと思われます (新幹線を用いない流儀の人が算出したものであるという可能性もありますが)。 また、小倉・博多間で新幹線と在来線の双方を用いているのに、 なおかつ私たちのルートと異なっている場合には、おそらく、 より長いルート(=私たちの算出したルート)を見落としているのでしょう。 (こちらは規程の解釈とは関係ありません。私たちと異なる解釈をとるなら、 九州内で新幹線と在来線の双方を利用することはできません。)
 九州内だけなら、全探索でも容易に最長経路が求まりますので、 プログラミングのセンスがあれば、ものの数時間で「追実験」できるはずです。 興味のある人はやってみてください。

 なお、その他の箇所が異なっていて、 しかも私たちの算出したルートよりも長くなっているのであれば、 ぜひ著者までお知らせください。


制作環境編

[Q] 使ったソルバーは?
[A] CPLEX です。

 整数計画法で LOP を解く際に用いたのは、 ILOG 社の CPLEX というソルバーです。 かなりお高いしろもののようです。
 なお、フリーのソルバー「LP solve version 2.0」 (オランダ・Eindhoven 工科大学)も補助的に用いたのですが、 本州をひとまとめにしてこれに解かせるのはやや荷が重いようでした。

[Q] 使ったコンピュータは?
[A] ごくふつうのPCです。

 ソルバーを動かしたり全探索をしたりするのに使ったコンピュータは、 ごくふつうのPCです。具体的には Pentium-II 400MHz 〜 MMX-Pentium 266MHz 程度のマシンを用いました。
 なお、たまに頭数が足りなくなったときには Pentium ODP 83MHz というものまで引っぱり出してきて使っていました。

[Q] 地図はどうやって描いたの?
[A] Postscript を半ば手で書きました。

 公開している地図は Postscript 形式で用意しました。
 より正確には、「簡易 Postscript」とでもいうべき形式のファイルを Postscript に変換する、kmps というフリーウェアを用いました。 が、このツールは白黒画像しか扱えないようだったため、 地図に赤い線を入れるために Postscript をじかに修正しました。
 ちなみに、各駅の座標データは、印刷された地図をスキャナで読み取り、 画像ファイル化したものから各駅の座標を拾ってとりました。 また、そうして作った地図データから一部分を切り出したり、 拡大、縮小したり、特定の枝に色をつけたりするツールを Perl で書き、 「地図作成総合システム」(誇張度120%)を構成しています。


その他編

[Q] 「最長」の厳密な定義は?
[A] 「運賃計算経路の運賃計算キロが最長」です。

 ひとくちに「最長」といっても、実際に乗れる距離が最長なのか、 運賃が最も高額となるものを最長と呼ぶのか、いろいろ考えられます。
 今回は、計算のしやすさと自然さの2点から、 運賃計算経路の運賃計算キロが最長となるもののことを「最長」 と称することにしました。結果的には、 得られた解は「運賃が最も高額」かつ「営業キロが最も長い」 ものにもなっていると思われますが、確認はしていません。

[Q] 一見不要な頂点が地図に存在するのはなぜ?
[A] 運賃計算システムのデータを流用したからです。

 地図を見ると、「終端駅」「分岐駅」以外の駅にも、 頂点を表す黒丸がついていることがあります(たとえば神戸、札幌など)。 このような駅を頂点としてグラフに含める必要はありません。
 なのになぜ、そのような駅が含まれているかといえば、これは自作の運賃計算システム (既存)のデータを流用したからです。運賃計算システムでも、 終端駅と分岐駅以外を頂点に加える必要は原則としてないのですが、 以下のような理由で、 終端駅でも分岐駅でもない駅を頂点に加えていることがあります。

 最長経路を求めるにあたっては、 このような頂点を取り去ったほうが計算が早く済むはずですが、 整数計画法で解く際には、取り去らなくても十分早かったので、 結局ほったらかしにしてプロジェクトを完遂しました。 また、ソルバーが十分賢ければ、 こういう意味のない頂点が存在しても解答に要する時間はほとんど延びないはずです。
 いっぽう全探索では、 むだな頂点が1つ増えただけでも計算時間が大幅に延びる可能性があるため、 これらの頂点は真っ先に除去しました。

[Q] 最長片道きっぷの経路を実際に乗るつもりは?
[A] もう乗りました。:-)

 最長片道きっぷを実際に買い、そのとおりに乗車すると、 最短でも約15日ほどかかります。 このため、おいそれと出かけるわけにはいきません。学割でも70000円以上しますし。 少なくとも、この乗車券の「実証」について科研費は出ないそうです。:-)
 ところが、世の中には奇特な^H^H^Hありがたい方々が大勢いるもので、 2000年の夏、「募金するから『実証』してくるように」という声が出て、 ついに実際にきっぷを買い、乗ってきてしまいました。 その一部始終は PROJECT LOP の Web ページで公開されています。
 以前は「卒業旅行で実乗をやろうかなぁ」と言っていたので、 卒業旅行のネタがなくなってしまった、と一時は思ったのですが、 心配には及びませんでした。最長片道きっぷが四国をまったく通らなかったことから、 募金者から、「四国最長片道きっぷ」を買って乗ってくるように、 という命が下りました。これを卒業旅行にするつもりです。

[Q] 筆者の研究室はマニアの巣窟なのでしょうか?
[A] そういうわけではありません。

 筆者の所属していた情報処理工学研究室は、 文字どおり情報処理工学を研究していて、 決して最長片道きっぷだけを研究しているわけではありません。:-)
 また、全員が鉄道ファンということもありません。 実際、このプロジェクトに携わった宮代くんは鉄道ファンではありませんし、 研究室のボスであるT教授にも「成果は認めるが、 自分でやろうとは思わない」という率直な感想をいただきました。
 なお、筆者自身が鉄道ファンであることは客観的にも明らかです。:-)



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