最長片道きっぷの経路を求める
[2-4] 整数計画法で(戦略編)

あらまし

 このページでは、実際のJRの路線図について LOP の最適解を求めるとき、 どのようにすれば楽ができるかを考えます。 もちろん、その過程において解の厳密さを損ねないよう注意を払います。


目次

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

最長ルート大予想!

 突然ですが、いま求めようとしている「最長片道きっぷ」のルート、 だいたいどこからどこに向かうものだと思いますか?
 そう聞かれたら、たいていの人は 「北海道から九州に行くルート(あるいはその逆)じゃないかな?」 と考えるのではないでしょうか。 日本列島は南北に長いわけですから、北の端から南の端まで行くのが最長だろう、 というわけですね。 いっぱしの鉄道ファンなら、北海道と九州にはそれぞれ2000km以上のJR線があって、 合わせると全国のJR線の2割以上を占める、 だからきっと北海道と九州は通るだろう、という根拠を挙げるかもしれません。
 私たちもまさにそう考えました。 本州と北海道、本州と九州を結ぶ路線はそれぞれ1本しかありませんから、 北海道や九州と本州を往復するのは発売条件の範囲内では不可能。 さらに、本州と四国を結ぶ路線も1本だけで、四国内のJR線は1000km未満。 となると、北海道と九州をそれぞれ存分に乗り回してから本州に渡る、 「北海道−本州−九州」というルートが最長となるのではないか、と。

 実は、本州と九州の間には、 山陽本線(在来線)と山陽本線(新幹線)の2本の路線があります。 さらに、この2本を両方とも通る片道乗車券もいちおう発売し得ます (1996年1月の運賃改定にともなう制度の改定による;制度の解釈はかなり微妙だが、 現在のところ、発売できるという解釈もいちおうの妥当性を有している)。
 が、この2本の路線は小倉で合流するうえ、 小倉での折り返しは制度上認められないので、 LOP の最適解を探す場合に関しては、発着駅の一方は門司港に決定されてしまいます。 つまり「本州→九州→本州」という乗車は不可能です。 「九州→本州→九州」では、2000km以上の路線を持つ北海道を放棄せざるを得ず、 あまりお得ではありません。
 詳細は略しますが、2本を同時に用いたときが最適でないことは容易に示せます。

 私たちは、以上の予想をうまく利用して、解の厳密さを損なわずに、 しかも楽に全体の最適解を得ようと考えました。


Lee だけまじめに、あとはイイカゲンに

 以下では、前述の予想を利用して、楽に、 しかも厳密に解を求める方法を説明するのですが、 そのカギとなる手法にあらかじめふれておきます。
 これから述べる手法では、めんどうな作業をタイプ Lee に集約させる、 ということをやろうとしています。

「解き直し」、運がよければパスできる!

 前ページでふれたように、たとえばタイプ Lee に関して、 一般的な制約式を与えてソルバーを1回動かすだけでは、 タイプ Lee の最適解が出てくるとは限りませんでした。 たいていの場合には不適当な解が出てきて、それをつぶすべく、 解に即した具体的な制約式を追加して解き直す作業が何回も必要になります。 事情は他のタイプに関しても同様で、この「解き直し」がかなりめんどうです。

 ところが、この「解き直し」は、 運がよければ1つのタイプに関してやるだけで済みます。 これには、「解き直し」 によって最適解の距離が長くなることはないという事実が利用されています。
 たとえば、タイプ Lee に関して、 独立なループを含まないようになるまで「解き直し」を行って厳密に求めた最適解 (=問題全体の解になり得るもの)が12000kmだと分かったとしましょう。 そして、タイプ Pe やタイプ Pn(実際にはタイプ B もしくはタイプ B8)を、 解き直しをせずに(=ほんとうにタイプ Pe やタイプ Pn になっているかどうかを確認しないで) 一般的な制約式のみで解いたときの解がそれぞれ11000km、 10000kmだったとしましょう。
 するとこの時点で、タイプ Pe やタイプ Pn の解き直しをする必要はなくなります。 なぜなら、解き直したとしても、新たに得られる解がそれぞれ11000km、 10000kmを上回る可能性はゼロだからです。

制約式=フィルター

 ここで「解き直しても解が長くなる可能性はない」と断言できるのは、 「解き直し」という作業が「制約式を追加する」ことだからです。一般的に、 制約式を追加して最適値が改善されることはありません
 制約式は、いってみれば、 あらゆる経路の中から条件に合わないものを除去するためのフィルターのようなものです。 一度解いてみたら、 すべてのフィルターをくぐり抜けた中で最長のものが11000kmだった。 で、フィルターを新たにもう1枚追加して解き直したら、11500kmのものが出てきた。 そんなことがあり得ますか? あり得ませんよね。解き直したときに、 11500kmのものがすべてのフィルターをくぐり抜けて出てきたのであれば、 フィルターを追加する前、 つまり最初に解いたときにもすべてのフィルターをくぐり抜けているはずで、 その結果、最初に解いたときに得られる最適値も11500kmであるはずです。
 結果として、 タイプ Pe やタイプ Pn で12000kmを上回るものは存在しないということが、 解き直しをせずにいえます。つまり、タイプ Lee の12000kmという解が、 すべてのタイプを通じて最長である、ということがいえるのです。 現在の目標は「LOP の最適解を求める」ことであって、 「各タイプの中で最長のものを求める」ことではありませんから、これで十分です。


全体を解くための戦略

 以上をふまえて、私たちがとった「戦略」を説明します。

Step 1. 3島をまず解く

 まず、北海道、四国、九州の3島内について、 本州と出入りできる経路のうち最長のものを求めておきます。
 島内の最長経路を求めるには、 これまで説明してきた整数計画法を用いることもできますが、 実は全探索でも一瞬(1秒以内)で解けてしまいます。 「解き直し」がいらないぶん、全探索のほうがむしろ楽です。 3島と本州とを結ぶ路線はそれぞれ1本しかないため、 「本州と出入りできる」という条件をつけると島内の経路は片端が固定されます。 したがって、それほど選択肢がないのです。 長さのわりには路線網が複雑でないというのもきいています。

 結果をちょっと先取りして書いてしまうと、求めた結果は以下のようになりました。 本州と3島の境界駅はそれぞれ長万部、宇多津、小倉としました。 北海道と本州の境界が長万部なのは一見すると意外ですが、 これは長万部から本州までの経路が自明であることによります。

 ここで、タイプPになったのが九州だけだったのは幸運でした。 もし北海道と九州の最長経路がともにタイプPで、 全体として「北海道発九州着」「九州発北海道着」が最適であると分かったら、 北海道か九州のどちらかを1駅短縮してやらないと、 全体として発売条件を満たさなくなる(タイプBになってしまう)ところでした。

 「九州はタイプPだけど、どうやって整数計画法でこれを求めたの?」 という疑問はもっともですが、これもタイプ Pe をタイプ Lee に帰着して解きました。詳細は略しますが、気になる方はお問い合わせください。 (ヒント:鳥栖発、長崎方面着の最長経路をまず求めておく。)

Step 2. グラフの3島部分を1本の枝に置き換える

 次に、JR全線に対応するグラフのうち3島内に対応する部分を、 1本の枝で置き換えた新たなグラフ(以下、 これを「グラフ JH」とします)を作ります。 ここで、新たに加えた「1本の枝」の距離は、 先に求めておいた各島内の最長経路の距離にします。
 たとえば北海道に関しては、JRの路線図から長万部以東をすっかり取り去り、 そのかわりに、長万部から長さ1438.0kmの枝を1本出します(図21)。 「もしも LOP の最適解が北海道を通るなら、 道内部分は長万部から稚内に至る1438.0kmの経路になる」 ということが分かっているのですから、 道内の他の路線はもはやいらないわけです。

図21図21 この作業、言いかえれば、 最長経路で使わない北海道内の枝を落とすようなイメージ。 実際の路線図でぐねぐねしていても、グラフとしてはたった1本の枝になります。

 九州に関しては最長経路がタイプ Pe でしたが、 これもかまわず1本の枝にしてしまいます。 九州内の経路の可能性はもはや1つに絞られたので、 その形状がどうであろうと関係ありません。 九州を通るか通らないか、選択肢はそれだけです。

 自明なのでここまで特に書きませんでしたが、北海道、九州、 四国の各島内で完結するような経路が LOP の最適解になることはあり得ません。 3島のうちで最も長い路線を持つ北海道でもたかだか2500km程度で、 2500kmを超える経路などすぐに作れます。 たとえば、稚内から枕崎までは最短ルートで行っても3000km近くになります。

Step 3. グラフ JH でタイプ Lee をまじめに解く

 こうしてできたグラフ JH について、 タイプ Lee のうち最長の経路を「まじめに」求めます。 「まじめに」というのは、前述のとおり、 ちゃんとタイプ Lee の解が出てくるまで何度でも解き直しをする、 という意味です。
 もしも「LOP の最適解は北海道と九州を必ず通る」という前述の予想が正しければ、 出てくる結果は、発着駅の一方が「北海道の枝」の端、 もう一方が「九州の枝」の端になるはずです。 そして、ここで得られた解が、結果的には LOP の最適解になっているはずです。

Step 4. タイプ Pe、タイプ Pn の可能性を否定する

 最後に、グラフ JH について、タイプ Pe、 タイプ Pn の最長経路を「いいかげんに」求めます
 そして、その結果が Step 3で求めたものより短ければしめたもの。 前述のとおり、いいかげんに解いた結果がすでにタイプ Lee を下回っていれば、 まじめに解き直してもタイプ Lee を上回れないことが分かっています。 ですから、タイプ Pe、タイプ Pn の解き直しは不要になります。

で、どうだった?

 最終結果は次のページで紹介しますが、この戦略がどうだったかだけを先に言うと、 見事にもくろみどおりの結果が出ました。 すなわち、タイプ Pe、タイプ Pn の解き直しは不要でした。
 具体的には、タイプ Lee の最長経路が11920kmを超えるということが Step 3により判明しました。そして、 その他のタイプについて「いいかげん」に解いた結果は以下のようになりました。

 このように、「いいかげん」に解いた段階で、 どれもタイプ Lee を上回れませんでした。 ということは、もはやこれらのタイプについて考える必要はありません。 タイプ B8 はかなりきわどいように見えますが、 これは制約式が非常に甘いせいで、 タイプ B8 の厳密な解はずっと小さいはずです。
 このうち、タイプ Pn を変形したタイプ B およびタイプ B8 については、 発駅側で「1駅短縮」してタイプ Pn に戻してやる必要があるのですが、 その「1駅短縮」は明らかに距離を縮める作業ですから、 タイプ B やタイプ B8 に望みがない以上、 タイプ Pn にはますますもって望みがありません。

所要時間

 ちなみに、解答に要する時間は、タイプ Lee に関してはだいたい「1回約2分」でした。 つまり、答えを一つ出すのに2分、 ループを除去してもう一度解くのにまた2分、といった具合です。
 また、他のタイプの可能性を否定するのには以下の時間がかかりました。



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