← 図13 駅の数だけ頂点を作ると、グラフは頂点でいっぱい。
このページでは、LOP の最適解を求める問題を整数計画問題として定式化する際に、 どのように変数を定義するか、 ＪＲの路線図をどのようなグラフに直すのかについて説明しています。 具体的な制約式はこの次のページで扱っています。
「準備編」では、「グラフって何？」「それは路線図のようなものだよ」
という話がありました。
路線図の駅のことを「頂点」、駅と駅を結ぶ線路のことを「枝」と呼ぶのでした。
ここでは、実際に問題を解くうえで使うグラフは具体的にどのようなものか、
考えてみます。
まず、「駅＝頂点」という規則にしたがって、 ＪＲの路線図を正直にグラフにしたらどうなるでしょう。 ＪＲ全体では駅の数は5000ほどありますから、頂点が5000個ほどできます。 とすると枝もほぼ同数以上はあるでしょう。これはかなり巨大なグラフです（図13）。
← 図13 駅の数だけ頂点を作ると、グラフは頂点でいっぱい。
しかし、LOP の最適解を考えるうえで、これら5000個の頂点をすべて使うか、
というとそうではないでしょう。具体的には、
分岐駅、分岐駅の隣接駅、終端駅のいずれでもない駅は考慮する必要がありません。
たとえば京葉線の葛西臨海公園駅は分岐駅、分岐駅の隣接駅、
終端駅のいずれでもありません。
もしこの駅がなかったら、LOP の最適解が変わる可能性はあるでしょうか？
答えは「ＮＯ」ですよね。ここから別の路線が分岐しているわけではないし、
この駅自体は最適解の発着駅になり得ないのですから、
この駅がかりに存在しなくても、
最長片道きっぷの経路には何の影響も及ぼしません。
結局、LOP の最適解を解くためには、頂点としてグラフに加える駅は分岐駅、
分岐駅の隣接駅、終端駅だけでよいことになります。
分岐駅と終端駅を合計するとだいたい300強ですから、
隣接駅も含めると頂点数は1000程度でしょうか。
だいぶ規模が小さくなりました。
← 図14 分岐駅とその隣接駅、終端駅だけを頂点にすると、
グラフはずいぶんすっきり。
しかし実際には、さらに頂点を削って、 分岐駅と終端駅だけを頂点として与えたグラフを用いて問題を解きました。 これだと頂点数は300そこそこです。 「分岐駅の隣接駅」を考慮する必要があるのはタイプ Pn のみですから、 タイプ Lee とタイプ Pe に関してはこのグラフで十分です。 以下ではこのグラフを前提として話を進めます。
← 図15 さらにすっきり。
じゃあタイプ Pn はどうするの？という疑問が生じますが、 これについてもちゃんと考えてあります。具体的には後述します。
それでは、いよいよ LOP を整数計画問題として記述します。 この作業のことを定式化と呼びます。
整数計画問題では、制約の範囲内で自由に動ける変数がいくつかあって、
その変数から成る式を最大化ないしは最小化するのでした
（この場合は経路全体の距離を最大化します）。
この変数をグラフにおける何と対応づけるかをまず考えます。
今回、私たちは、頂点と頂点を結ぶ枝に対して0-1変数を定義しました。
「0-1変数」というのは文字どおり「値が０か１のどちらか」という変数です。
考えている経路がある１本の枝を通るときには、その枝に対応する変数の値を１、
そうでないときには変数の値を０にします。
具体的には、i 番の枝に対する0-1変数を li と定義しました（図16）。
← 図16 赤い枝を通るとすると、
各枝に対する変数の値はこのようになります。
逆に、各枝の変数の値がこうなると、ルートは赤い線で示されたようになります。
この li は0-1変数ですから、 当然ながら以下のような制約式を満たしている必要があります。
| すべての i に対して li ≦ 1、li は整数 |
(1) |
変数は負でない（非負である）ことを暗黙のうちに仮定しています。JIS の線形計画法の定義にも「通常、変数は非負」という一節が入っているそうです。
やや抽象的な話になったので、実例を挙げます。
たとえば本州の路線図をグラフ化すると、枝の数は約400です。
ここでは、きりがいいのでちょうど400本だとしましょう。
すると、l1 から l400 まで400個の変数が定義され、
それぞれが０か１かの値をとります。
400個の変数の値が全部決まれば、
どの枝を通ってどの枝を通らないか決まるので、経路が１つ決まります。
(l1, l2, …, l400) という400個の変数の組が、
この場合は本州全体の経路に対応するわけです。
このことから単純に考えると、
経路のバリエーションは本州内だけで２の400乗通りあることになります。
２の400乗といえばだいたい10進数にして120ケタぐらいの数ですから、
単純に列挙するのはどう考えても無謀ですね。
１秒に何億通り、何兆通りが試せたとしても、
地球が寿命を迎えるまでにはまず終わりません。
しかし、この天文学的どころではない個数の組合せの中から、
発売条件を満たすもののうちで最長のものを、
わずか数分で見つけ出してしまうのが整数計画法なのです。
実は、そのものズバリ「組合せ爆発的」という表現もあるそうです。 数の大きさとしては「天文学的 << 組合せ爆発的」です。
閑話休題、このように枝に対して変数を定義すると、 おのずと目的関数（最大化したい関数）も決まります。 いま、経路全体の距離が最大になるようにしたいのですから、 その「経路全体の距離」が目的関数になります。 i 番の枝の距離（運賃計算キロ）を di とすれば、 これは次のように書けます。
| (目的関数) ＝ Σi（di ・ li） | (2) |
もし、いま考えている経路が i 番の枝を通るなら、 li ＝ 1 なので di ・ li ＝ di となり、i 番の枝の距離 di が合計距離に加算されます。 もし通らなければ li ＝ 0 なので、 di ・ li ＝ 0 となり、di は加算されません。 したがって、式 (2)は「いま考えている経路が通る枝の距離の合計」、 すなわち「いま考えている経路全体の距離」になっています。
以上のように、それぞれの枝に対して変数を定義すれば定式化はできるのですが、
式の書きやすさの点から、頂点、
つまり路線図における駅に対しても変数を定義することにしました。
ただ、これは、枝に対する変数 l
の値が決まれば自動的に値が決まってしまう従属変数です。
具体的には、i 番の頂点に対する変数を si とし、
si は i 番の頂点に接続するすべての枝に関する変数 l
の和と定義しました。
たとえば i 番の頂点に p 番、q 番、r 番の３本の枝が接続しているとすれば、
si ＝
lp ＋ lq ＋ lr となります。
この変数 si の値は「現在の経路で、i
番の頂点に接続する枝が何本使われているか」を表します。
具体的には以下のような意味になります。
もし si が４以上の値をとっていたとしたら、 その経路は確実に発売条件を満たしていません。
ここで念のため、今後の方針について確認しておきます。
以上のように、路線に対して変数を定義しただけでは、
それぞれの変数は（０か１のどちらかではあるにせよ）まったく独立に、
自由な値をとることができます。
ですから、路線図中のすべての路線を用いる（すべての l が１になる）こともでき、
このとき明らかに目的関数が最大になります（全路線を使えば、
経路全体の距離が最長になる！）。
したがって、ソルバーに「変数の値を適当に操作して、
目的関数を最大にせよ」と命令すれば、
この「全部１」という答えが最適解として出てきます。
しかし、そんな解が得られてもちっともうれしくありませんよね。
「全国の路線すべてを通る」なんて経路は明らかに発売条件を満たしません。つまり、
現状では発売条件を満たさない経路が解として出てくる可能性があるのです。
このままでは LOP の最適解を求めるのにまったく使いものになりません。
そこで以下では、
発売条件を満たさない経路が出てこないように制約式を入れていきます。
たとえば「ある駅に接続する枝を同時に３本以上使わない」であるとか、
「終端駅を３回以上使わない」であるとか、
発売条件を満たさない経路を締め出すような制約をどんどん加えるのです。
そして、それらの制約をすべて満たすうちで最長の経路が発売条件を満たせば、
それは LOP の最適解といえます。
次ページでは、実際に使える解を得るにはどんな制約式を入れたらいいのか、 ということをタイプ別に考えます。