補５．最長片道ルート計算の高速化（その2：ラグランジュ緩和）

「その1：整数制約を緩和」では、20分程度の計算を4分程度に短縮することができた。「その2」では、「その1」とは異なるアプローチとなる「ラグランジュ緩和」を用いる方法を検討する。ベンチマークする例題は「その1」と同じである。

結論から言うと、「ラグランジュ緩和」では20分程度の計算を10分程度に短縮することができたが、「ラグランジュ緩和」からの思いつきで試みた「極めて簡単な方法」により、20分程度の計算をなんと1分程度に短縮することができた。これは、「その1」の成果をはるかに上回るものである。

「極めて簡単な方法」とは、部分巡回ルートが発生した場合に、「部分巡回禁止制約（部分巡回ルート上で使用できる枝数＜＝部分巡回ルートの全枝数−1）」ではなく、「部分巡回強制接続制約」を使用し、かつ、「部分巡回強制接続制約」を「部分巡回ルートから突き出した枝のうち通過する本数＞＝1」ではなく、「部分巡回ルートから突き出した枝のうち通過する本数＞＝2」とすることである （注1参照）。
面白いのは、「部分巡回禁止制約」ではなく、「部分巡回強制接続制約」を使用した場合、「部分巡回ルートから突き出した枝のうち通過する本数＞＝1」でも、計算時間は6分程度に短縮されるのであるが、1を2に変えるだけで、計算時間が更に大幅短縮され、1分程度になることである。

部分巡回ルートが発生した場合に「部分巡回強制接続制約」を用いることは、 巡回セールスマン問題でも既出であるから、これを用いる方が、計算が速くなることに今まで気が付かなかったのが不思議なくらいであるが、なぜこの方法の方が、計算が速いのかは、はっきりとは分かっていない。今回は、新たな分岐変数の発生をできるだけ減らすという方向性で検討するうちに、「部分巡回強制接続制約」の活用を再発見するに至ったが、この方法に辿り着きくまでの話の筋を以下に述べることで、この再発見の意義を明らかにしたい。

いずれにしても計算時間1分程度は、かなり満足できるレベルである。今後のソルバーでの計算は、「部分巡回禁止制約」よりも「部分巡回強制接続制約」を用いることを推奨したい。


（１）ラグランジュ緩和の概要と今回の適用方針

「ラグランジュ緩和」は、問題を複雑にしている制約式を削除する代わりに、罰金を課して目的関数に組み込む方法である。
例えば、部分巡回禁止制約
　　　H(a,b)＋H(b,c)＋H(c,a)＜＝2
を目的関数f(H)に組み込む場合、新しい目的関数を
　　　f(H)−λ(H(a,b)＋H(b,c)＋H(c,a)−2)
とすれば、λが大きい数値の時、H(a,b)＋H(b,c)＋H(c,a)が3以上ならば、f(H)を小さくする方向に働くので、新しい目的関数を最大化するだけで、自動的に
　　　H(a,b)＋H(b,c)＋H(c,a)＜＝2
を満たすようになるという原理である。

もともと、ラグランジュ緩和を検討することとしたのは、Ｈ（会津若松,小出）＝1に固定した時の上界を求めるのに、なんらかの条件緩和が必要となったからであった。
ところが、「その1」では、条件緩和は、むしろ、計算時間を長くしそうな新たな分岐変数の発生を回避するために用いられることとなった。
具体的には、新潟近郊の部分巡回ルートを形成しているH(m,n)のどれかが、部分巡回禁止制約を課したことで、新たに分岐変数となり、大量の分岐計算を行って、計算時間を長くしている可能性があったため、そのH(m,n)の整数制約を解除してH(m,n)が分岐変数となることを回避したのであった。
今回も、ラグランジュ緩和を、上界を求めるというより、計算時間を長くしそうな新たな分岐変数の発生を回避するために用いてみることにする。


（２）実際に適用してみる

今回のベンチマーク問題で問題を複雑にしているのは、次に示した3本の新潟近郊の部分巡回環禁止制約であったので、とりあえずこれを制約条件から外し、目的関数に組み込むことにする。
すなわち、オリジナルの目的関数をf(H)とすると、新しい目的関数は、 となる。
α、β、γは、制約式を削除する代わりに課せられる罰金（ラグランジュ乗数）である。

まず、α＝β＝γ＝0ならば、オリジナルの問題から単に上記の3本の制約式を除いた問題となる。当然、この時の最適解f(H*)では、ΣHa＝9の部分巡回ルートが形成されることになる。
次に、α＝β＝γ＝5としてみる。これは、部分巡回ルートが形成された時に、それぞれ5qの罰金を課すことになる。もし、5qの罰金を課しても部分巡回ルートは解消されないままであれば、新しい目的関数の最適解は、 となる。この時、最適解が15qだけ小さくなったので、それだけ上界が改善されたことになる。
ところが、このケースを実際に計算してみると、新しい目的関数の最適解は、 となり、全ての部分巡回ルートが解消されていることが分かる。

たった5qの罰金で部分巡回ルートが解消されてしまうのは何かおかしい。そこで、よくよく考えてみると、次のことが分かった。


図A5-1
ΣHa＝9
図A5-1
ΣHb＝9
図A5-1
ΣHc＝8

図A5-1

まず、図A5-1を見ると、3つの部分巡回ルートは重なる部分があるので、ΣHa＝9、ΣHb＝9、ΣHc＝8が同時に成立することはないのである。
例えば、ΣHa＝9の時は、
　　　H(新潟, 吉田)＝H(長岡, 燕三条)＝H(燕三条,東三条)＝0となるので、
　　　ΣHb＝9−3＝6、ΣHc＝8−1＝7
となる。即ち、ΣHa＝9の時の新しい目的関数の最適解は、 である。つまり、ΣHa＝9の部分巡回ルートが残っている場合でも、罰金ではなく、逆にプレミアムがついてしまい、上界は改善されないのである。

また、上記のケースでは、ΣHa＝9の部分巡回ルートについても、ΣHa＝5となって、たった5qの罰金で部分巡回ルートが解消されている。これも、ΣHa＜＝7になると、罰金ではなく逆にプレミアムが付くのが原因のようである。

このようなプレミアムが付くようになると、α、β、γの設定によっては、最適解をオーバーシュートして、使用する枝数を必要以上に削減してしまう可能性がある。
例えば、α＝β＝γ＝50のケースを計算すると、 となり、新潟近郊の枝は全て0となる代わりに1150qのプレミアムが付く。これは、明らかに、使用する枝数を必要以上に削減していることが分かるだろう。

たった5qの罰金で部分巡回ルートが解消されてしまうのは、このように、
　　　ΣHa＜＝7、ΣHb＜＝7、ΣHc＜＝6
の時に罰金ではなく、プレミアムがついてしまうからであるようだ。


そこで、上記のような問題を回避するために、部分巡回ルートができると罰金がかかるが、部分巡回ルートが解消されてもプレミアムがつかないような目的関数を考える。

そのため、新しい目的関数に、ΣHa、ΣHb、ΣHcのかわりにダミー変数X、Y、Zを導入し、プレミアムがつかないようにX、Y、Zをそれぞれ8、8、7以上の値だけをとるようにする。
即ち、新しい目的関数とそれに付随する制約式は、 である。
これは一見、せっかく目的関数に組み込んだ制約式を復活させているようにも見えるが、ΣHa、ΣHb、ΣHcはそれぞれ8、8、7以上の値もとれるので、部分巡回禁止制約がかかっている訳でないことが分かるだろう。
また、上記の定式化により、部分巡回ルートが解消されると、
　　　X＝8、Y＝8、Z＝7
となるが、この時、 となるので、ラグランジュ緩和後の目的関数の最適値が、オリジナルの目的関数の最適値と一致することになる。

この方法により、α＝β＝γ＝5として計算すると、 となった。つまり、部分巡回ルートは解消されていないが、5qだけ上界が改善されたことになる。これは、思った通りの答えである。

次に、α＝β＝γ＝50として計算すると、 となった。つまり、50qの罰金によって、部分巡回ルートは解消され、かつ、「罰金×目的関数に組み込んだ制約式」が全て0であるため、この時の最適解f(H##)は、オリジナルの最適解と一致するのである。

α＝β＝γ＝50のケースでの計算時間は、10分程度であった。オリジナルは20分程度だったので、所要時間は半減している。新潟近郊の部分巡回ルートを形成しているH(m,n)のどれかが、部分巡回禁止制約を課したことで、新たに分岐変数となり、大量の分岐計算を行って、計算時間を長くしている可能性があったが、上記の定式化で部分巡回禁止制約を課すことを回避したので、新たな分岐変数の発生を回避できたといえるだろう。

ただし、ダミー変数を3つ追加したため、変数増による所要時間増もあるように思われる。次節では、更に計算時間短縮を図るため、ダミー変数を減らすことを考える。


（３）ダミー変数を減らす


図A5-2
図A5-2

「部分巡回禁止制約」を課した新潟近郊の3つの部分巡回ルートは、ほとんど重なっている。図A5-2を見ると、この制約を、「部分巡回強制接続制約」に変更することで、3本の制約を1本に減らせることが分かるだろう。
即ち、3本の制約を に変更すればよい。特に今回のベンチマーク問題ではH(新発田,坂町)＝0なので、 で十分である。

これにより、（２）の定式化は次のようになり、ダミー変数も3個から1個に削減できることになる。 ここで、H(柏崎,直江津)＋H(宮内,越後川口)＋H(新津,会津若松)＞＝1は、（柏崎,直江津) (宮内,越後川口) (新津,会津若松)のどれか1区間は必ず通過するという意味であるが、図A5-2の部分巡回ルートに入ったら、必ず出なければならないので、どれか1区間ではなく、どれか2区間を必ず通過する必要がある。即ち、 である。
また、（柏崎,直江津) (宮内,越後川口) (新津,会津若松)の3区間全てを通過する場合は、図A5-2の部分巡回ルートに入って、出て、また入ることになるので、出られなくなってしまう。つまり、この制約は、 とすることができるのである。

従って、（２）の定式化はダミー変数なしで、 とできることが分かるだろう。

この定式化により、α＝50として計算すると、H(柏崎,直江津)＋H(宮内,越後川口)＋H(新津,会津若松)＝2となり、最適解は、オリジナルの最適解と一致した。
この時の計算時間は、なんと、1分程度であった。これは物凄く早いと言えるだろう （注2参照）。

ところで、ラグランジュ緩和は、制約式追加によって図A5-2の部分巡回ルートで新しい分岐変数が発生することを防止するために用いたものであり、上式では、ラグランジュ緩和によって、H（柏崎,直江津）＋H（宮内,越後川口)＋H(新津,会津若松)＝2の制約式追加による新しい分岐変数の発生を回避していることになるが、少し考えてみると、H（柏崎,直江津）＋H（宮内,越後川口)＋H(新津,会津若松)＝2の制約式の追加では、新しい分岐変数が発生する可能性は低いように思われる。
なぜなら、H(柏崎,直江津)＋H(宮内,越後川口)＋H(新津,会津若松)＝2となるのは、次の@ABの3ケースしかなく、
　@　H(柏崎,直江津)＝H(宮内,越後川口)＝1、H(新津,会津若松)＝0の時は、
　　　直江津-柏崎-吉田-燕三条-新潟-新発田-新津-東三条-長岡-宮内-越後川口
　　　が最長ルートであることが明らかであり、
同様に、
　A　H(柏崎,直江津)＝H(新津,会津若松)＝1、H(宮内,越後川口)＝0の時は、
　　　直江津-柏崎-吉田-新潟-燕三条-長岡-東三条-新津-会津若松
　B　H(宮内,越後川口)＝H(新津,会津若松)＝1、H(柏崎,直江津)＝0の時は、
　　　越後川口-宮内-柏崎-吉田-新潟-燕三条-長岡-東三条-新津-会津若松
　　　が最長ルートであることが明らかであり、小数解の入り込む余地がないからである。

つまり、計算時間が短縮されたのは、ラグランジェ緩和したためではなく、H(柏崎,直江津)＋H(宮内,越後川口)＋H(新津,会津若松)＝2の制約式を用いたからである可能性が高い。

そこで、ラグランジェ緩和はせず、つまり目的関数はオリジナルのままで、「部分巡回禁止制約」（3本）を「部分巡回強制接続制約」（1本：H(柏崎,直江津)＋H(宮内,越後川口)＋H(新津,会津若松)＝2）に置き換える作業のみで、計算してみることにした。この結果、やはり1分程度で最適解を求めることができた。予想通り、計算時間の短縮は、ラグランジェ緩和よりも「部分巡回強制接続制約」の効果であることが確認できたことになる。


（４）部分巡回強制接続制約の適用拡大

前節で、「部分巡回禁止制約」よりも「部分巡回強制接続制約」の方が、計算が速そうなことが分かったので、これを新潟近郊以外にも適用拡大して、全面的に「部分巡回禁止制約」を見直してみる。

新潟近郊では部分巡回ルートから突き出した枝が3本しかなかったので、 とできたが、一般的には、「部分巡回ルートに入って、出て」が1単位となるので、部分巡回ルートから突き出した枝を偶数本通過することが必要な条件となる。つまり、部分巡回ルートから突き出した枝が4本以上ある場合は、 というように「＝」を「＞＝」にする必要がある。

従って、新潟近郊の制約式も、 に直しておくことにした。

次に、これを房総半島に適用してみる。房総半島は「部分巡回禁止制約」では7本の制約式が必要であった。これを「部分巡回強制接続制約」にすると、次の3本となった。 埼玉県の「部分巡回禁止制約」 は、「部分巡回強制接続制約」に変更すると となるが、「部分巡回禁止制約」の方が、使用している変数の数が少なく簡潔なので、「部分巡回禁止制約」をそのまま使用することにした。

以上を整理すると、部分巡回ルートについて全て「部分巡回禁止制約」を適用していたオリジナルの制約式（13本）は、次の5本の制約式とすることができる。 この制約式により計算するとやはり1分程度で最適解を求めることができた。

この手法によると面白いほど計算が速くなるので、ベンチマーク問題以外の問題も試してみることにした。
具体的には、本州循環型最長片道ルートの東日本地方を最適解となる
　　　Ｈ（金山・名古屋）＝1
　　　Ｈ（美濃太田・多治見）＝1
　　　Ｈ（富山・糸魚川）＝0
　　　Ｈ（坂町・新発田）＝01
　　　Ｈ（福島・郡山）＝0
　　　Ｈ（いわき・岩沼）＝1
で計算してみたところ、2分程度で最適解を求めることができた。本州循環型最長片道ルートの東日本地方もオリジナルの計算では20分程度の時間がかかっていたので、これも大幅な計算時間短縮となった。なお、この時用いた部分巡回ルートについての制約式は以下の通りである。 はじめの4本は通常の最長片道ルートの東日本地方ベンチマーク問題と同じである。新潟近郊の制約式は不要となり、代わりに残りの4本の制約式が必要となった。

ところで、巡回セールスマン問題では、部分巡回ルートを解消する際の「部分巡回強制接続制約」は、 というように、「＞＝2」ではなく「＞＝1」を用いている。
（３）でも、はじめは、この「＞＝1」を用いて としていた。
ラグランジェ緩和への適用を考えるうちに、計算速度向上の観点から「＞＝2」を用いた方がよいことが分かったが、「＞＝2」と「＞＝1」では、計算速度にどの位の差があるだろうか。

通常の最長片道ルートの東日本地方ベンチマーク問題の5本の制約式のうち、埼玉県の「部分巡回禁止制約」を除く、4本の制約式について、「＞＝1」を用いて計算したところ、6分程度で最適解を求めることができた。これは、全て「部分巡回禁止制約」を用いたオリジナルの20分程度からは大幅短縮となっているが、「＞＝2」を用いた場合の1分程度と比べると、6倍程度の所要時間となっている。

また、本州循環型最長片道ルートの東日本地方の計算では、所要時間の差は更に顕著で、「＞＝2」を用いた場合は2分程度で計算できるが、「＞＝1」を用いた場合は、20分程度かかってしまうことが分かった。

「＞＝2」と「＞＝1」で、これ程の差が生じる理由ははっきり分かっていない。しかし、その一因は、「＞＝1」の方が「＞＝2」よりも分岐しなければならない変数が多くなる可能性が高いことにあると思われる。


図A5-3
「＞＝2」で計算した場合
図A5-3
「＞＝1」で計算した場合

図A5-3

図A5-3は、新潟近郊の整数制約を解除して、「＞＝2」と「＞＝1」で計算した結果を比べてみたものである。
赤線は整数制約を解除した区間であり、太線はH変数が1となった区間、細線はH変数が0となった区間、点線はH変数が0.5となった区間を表わしている。
この図を見ると、「＞＝2」で計算した場合は、整数制約を解除した区間も全て整数解となっているが、「＞＝1」で計算した場合は、整数制約を解除した区間に小数解が含まれていることが分かる。
従って、全ての区間に整数制約を課して計算した場合、「＞＝2」では、特に追加の分岐は必要ないが、「＞＝1」では、これらの小数解の区間を新たな分岐変数として、追加の分岐を行う必要が生じることになる。このため、追加した分岐変数についての分岐計算の分だけ、「＞＝1」の方が、計算時間が長くなってしまうのである。


（５）まとめ


表A5-4
表A5-4

表A5-4は、これまでに計算高速化のために検討した手法について、その計算時間を整理したものである。
この表によると、「部分巡回強制接続制約」を「＞＝2」で用いるのが、圧倒的に計算が速いことが分かる。
「部分巡回強制接続制約」を用いるときは、注2で記したように最後に追加の確認計算が必要である。これが煩雑であるため、アルゴリズムとしては「部分巡回禁止制約」を用いる方が簡単である。
しかし、計算速度の観点からは、「部分巡回強制接続制約」を「＞＝2」で用いるのが、断然優勢であり、煩雑さを補って余りある効果があると言えるだろう。
結論としては、ＥＸＣＥＬのソルバーを使用する場合は、「部分巡回強制接続制約」を「＞＝2」で用いることを推奨したい。


（注1）

図A5-5
図A5-5

図A5-5のような部分巡回ルートが発生した時を例に、「部分巡回禁止制約」と「部分巡回強制接続制約」を次のように定義しておく。
「部分巡回禁止制約」とは、
　　　H(A,B)＋H(B,C)＋H(C,D)＋H(D,A)＜＝3
のように、
「部分巡回ルート上で使用できる枝数＜＝部分巡回ルートの全枝数−1」という考え方で部分巡回ルートを排除する制約式のことである。
「部分巡回強制接続制約」とは、
　　　H(A,E)＋H(B,G)＋H(C,F)＋H(D,E)＞＝1
または、
　　　H(A,E)＋H(B,G)＋H(C,F)＋H(D,E)＞＝2
のように、
「部分巡回ルートから突き出した枝のうち通過する本数＞＝1」
または、
「部分巡回ルートから突き出した枝のうち通過する本数＞＝2」
という考え方で部分巡回ルートを排除する制約式のことである。

（注2）
「部分巡回強制接続制約」を使用する場合は、最適解が求まった後で、最適解が部分巡回ルートを放棄するケースよりも大きくなることを確認する必要がある。

例えば、新潟近郊について「部分巡回強制接続制約」を適用した場合、最適解は3530.8qであるが、これが、部分巡回ルートを放棄するケースよりも大きいことは、次のように確認することができる。

まず、
部分巡回ルートを放棄するケースの最大値　＜＝　部分巡回ルートについての制約を全く課さない場合の最大値　−　新潟近郊の部分巡回ルートの最小値
であるから、部分巡回ルートについての制約を全く課さない場合の最大値と　新潟近郊の部分巡回ルートの最小値を求める。

ここで、部分巡回ルートについての制約を全く課さない場合の最大値については、 ＥＸＣＥＬによる最長片道ルート探索4.（１）で、接続部をひとつひとつ特定して計算する前に部分巡回禁止制約のない無制約最大値を計算した表を見ると、接続部の枝数を（1,1）とした場合の最大値が、3572.4qであることが分かる。
また、新潟近郊の部分巡回ルートで最短となる「新潟-吉田-柏崎-宮内-長岡-東三条-新津-新発田-新潟」については、その距離を計算すると、221.9qとなる。

従って、
部分巡回ルートを放棄するケースの最大値　＜＝　接続部の枝数を（1,1）とした場合の最大値−「新潟-吉田-柏崎-宮内-長岡-東三条-新津-新発田-新潟」の距離　＝　3572.4q−221.9q　＝　3350.5q　＜　3530.8q
であり、部分巡回ルートを放棄するケースが最適解よりも小さくなることが確認できた。

なお、 補3．1961年の東大旅研最長片道切符旅行は最長ではなかった？で述べたように、実際には、部分巡回ルートを放棄するケースの方が最適解となるケースは極めて稀であると考えられるので、これらの検証作業は、念のための確認程度と考えておけばよいだろう。


追記１(2005/6/26)
掲示板で川口氏より「部分巡回禁止制約」によると非常に時間がかかる事例として指摘あった以下の例題について、「部分巡回強制接続制約」を「＞＝2」を用いて計算してみたので以下に計算結果を示しておく。
なお、今回は、「日暮里−尾久−赤羽」と「品川−西大井−鶴見」は特定運賃計算キロではなく、営業キロ使用して計算した。

例題1：現在長期不通区間となっている「高山線　飛騨古川〜猪谷」を除く最長片道ルート

通常の最長片道ルートの計算に追加する条件は
　　　H（美濃太田,富山）＝0
である。
この条件を追加して西日本地方を再計算したところ、東日本地方との接続部が
　　　H（金山・名古屋）＝1
　　　H（美濃太田・多治見）＝1
　　　H（富山・糸魚川）＝1
のケースが最長となった。
このように接続部の枝数が3つとなる場合、
　　　@金山−名古屋−(西日本地方)−美濃太田−多治見−(東日本地方)−金山
　　　A多治見−美濃太田−(西日本地方)−富山−糸魚川−(東日本地方)−多治見
　　　B金山−名古屋−(西日本地方)−富山−糸魚川−(東日本地方)−金山
の部分巡回ルートを回避しなければならないが、この時、西日本地方側で制約式を追加するケースと東日本地方側で制約式を追加するケースに場合分けしなければならない。
そこで、西日本地方側で制約式を追加するケース、即ち、
　　　(1)美濃太田・名古屋接続型（上記ABの部分循環を西日本地方側で回避）
　　　(2)美濃太田・富山接続型（上記@Bの部分循環を西日本地方側で回避）
　　　(3)名古屋・富山接続型（上記@Aの部分循環を西日本地方側で回避）
の3通りを事前に計算しておくことにした（東北地方についても同様の措置をとった）。

計算結果は表A5-6の通り、最長片道ルートは図A5-7の通りである。

図A5-6
表A5-6

図A5-7-1
図A5-7-1
図A5-7-2
図A5-7-2
図A5-7-3
図A5-7-3

西日本地方で接続部の枝数が3つとなるケースが暫定最大値候補となるので、通常の最長片道ルートを計算したときよりも、東日本地方で計算しなければならない組合せが増加している。
この暫定最大値候補が、最終的な最長ルートとなったが、この組合せを計算する際の部分巡回ルートについての制約式は表A5-8の通りであり、全ての制約式を課した時の計算時間は2分程度であった。
制約式の数は、通常の最長片道ルートの時は5本（埼玉県：1本、房総半島：3本、新潟近郊1本）であったが、今回はそれらに9本追加した14本となっている。川口氏の指摘通り制約式の数はかなり増えている。しかし、「部分巡回強制接続制約」を「＞＝2」を用いて計算することで、それほど計算時間を要することはなかった（それでも、追加の5本は事前に制約式が分からないので、制約式が見つかる度に繰り返し計算する必要があり、2分×5回＝10分程度は掛かった）。
また、暫定最大値候補にかなり肉薄している「(西日本)全区間(2) または(西日本)全区間(3)−岩沼」の組合せは、暫定最大値候補より小さいことを示すのに、部分巡回ルートを完全に排除するまで繰り返し計算が必要であった。この時の部分巡回ルートについての制約式は表A5-9の通りであり、全ての制約式を課した時の計算時間はやはり2分程度であった。
【表A5-8】
（埼玉県：1本）

  • H(大宮,熊谷)＋H(熊谷,倉賀野)＋H(倉賀野,高麗川)＋H(高麗川, 大宮)＜＝3
（房総半島：3本）

  • H(東京,品川)＋H(東京,神田)＋H(秋葉原,錦糸町)＋H(西船橋,新松戸)＋H(我孫子,成田)＞＝2

  • H(品川,川崎)＋H(品川,鶴見)＋H(品川,新横浜)＋H(代々木,新宿)＋H(秋葉原,日暮里)＋H(西船橋,新松戸)＋H(我孫子,成田)＞＝2

  • H(東京,品川)＋H(品川,代々木)＋H(西国分寺,府中本町)＋H(西国分寺,立川)＋H(武蔵浦和,大宮)＋H(武蔵浦和,南浦和)＋H(南浦和,赤羽)＋H(日暮里,新松戸)＋H(西船橋,新松戸)＋H(我孫子,成田)＞＝2
（新潟近郊：1本）

  • H(柏崎,直江津)＋H(宮内,越後川口)＋H(新津,会津若松)＞＝2
（東海地方-本州循環型最長片道ルートで使用したもの：4本）

  • H(金山,多治見)＝0

  • H(豊橋,静岡)＋H(岡谷,小淵沢)＋H(塩尻,松本)＞＝2

  • H(豊橋,静岡)＋H(小淵沢,甲府)＋H(拝島,高麗川)＋H(西国分寺,立川)＋H(西国分寺,府中本町)＋H(品川,新横浜)＋H(品川,川崎)＋H(品川,鶴見)＞＝2

  • H(豊橋,静岡)＋H(小淵沢,甲府)＋H(拝島,高麗川)＋H(西国分寺,立川)＋H(西国分寺,府中本町)＋H(品川,代々木)＋H(品川,東京)＞＝2
（追加：5本）

  • H(糸魚川,直江津)＋H(長野,豊野)＋H(小出,越後湯沢)＋H(会津若松,郡山)＞＝2

  • H(糸魚川,松本)＋H(長野,豊野)＋H(小出,越後湯沢)＋H(安積永盛,郡山) ＋H(いわき,水戸)＞＝2

  • H(いわき,水戸)＋H(安積永盛,郡山)＋H(小出,越後湯沢)＋H(高崎,佐久)＋H(甲府,小淵沢)＋H(豊橋,静岡)＞＝2

  • H(糸魚川,直江津)＋H(長野,豊野)＋H(小出,越後川口)＋H(会津若松,新津)＞＝2

  • H(糸魚川,松本)＋H(長野,豊野)＋H(高崎,佐久)＋H(甲府,小淵沢)＋H(豊橋,静岡)＞＝2

【表A5-9】
（埼玉県：1本）

  • H(大宮,熊谷)＋H(熊谷,倉賀野)＋H(倉賀野,高麗川)＋H(高麗川, 大宮)＜＝3
（房総半島：3本）

  • H(東京,品川)＋H(東京,神田)＋H(秋葉原,錦糸町)＋H(西船橋,新松戸)＋H(我孫子,成田)＞＝2

  • H(品川,川崎)＋H(品川,鶴見)＋H(品川,新横浜)＋H(代々木,新宿)＋H(秋葉原,日暮里)＋H(西船橋,新松戸)＋H(我孫子,成田)＞＝2

  • H(東京,品川)＋H(品川,代々木)＋H(西国分寺,府中本町)＋H(西国分寺,立川)＋H(武蔵浦和,大宮)＋H(武蔵浦和,南浦和)＋H(南浦和,赤羽)＋H(日暮里,新松戸)＋H(西船橋,新松戸)＋H(我孫子,成田)＞＝2
（新潟近郊：1本）

  • H(柏崎,直江津)＋H(宮内,越後川口)＋H(新津,会津若松)＞＝2
（東海地方-本州循環型最長片道ルートで使用したものの内、後半2本）

  • H(豊橋,静岡)＋H(小淵沢,甲府)＋H(拝島,高麗川)＋H(西国分寺,立川)＋H(西国分寺,府中本町)＋H(品川,新横浜)＋H(品川,川崎)＋H(品川,鶴見)＞＝2

  • H(豊橋,静岡)＋H(小淵沢,甲府)＋H(拝島,高麗川)＋H(西国分寺,立川)＋H(西国分寺,府中本町)＋H(品川,代々木)＋H(品川,東京)＞＝2
（追加：3本）

  • H(糸魚川,直江津)＋H(長野,豊野)＋H(小出,越後湯沢)＋H(会津若松,郡山)＞＝2

  • H(いわき,水戸)＋H(安積永盛,郡山)＋H(小出,越後湯沢)＋H(高崎,佐久)＋H(甲府,小淵沢)＋H(豊橋,静岡)＞＝2

  • H(糸魚川,直江津)＋H(長野,豊野)＋H(小出,越後川口)＋H(会津若松,新津)＞＝2


例題2：「高山線　飛騨古川〜猪谷」に加え、「福知山線　宝塚〜尼崎」をも除いた場合の最長片道ルート

通常の最長片道ルートの計算に追加する条件は
　　　H（美濃太田,富山）＝0
　　　H（尼崎,谷川）＝0
である。
この条件を追加して西日本地方を再計算したところ、例題1と同様、東日本地方との接続部が
　　　H（金山・名古屋）＝1
　　　H（美濃太田・多治見）＝1
　　　H（富山・糸魚川）＝1
のケースが最長となった。

例題1と同様の方法で計算したところ、計算結果は表A5-10の通りとなった。

図A5-10
表A5-10

例題1の時よりも、西日本地方の最大値候補が他候補と肉薄しており、表A5-10で青色部分を追加計算する必要があった。
また、今回は暫定最大値候補より、「(西日本)全区間(3)−岩沼」の組合せの方が全体での距離が長くなり、こちらが最終的な最長ルートとなる。このルートについての計算自体は、例題1を計算する過程で実施済なので、追加計算は不要である。ルート図を図A5-11に示しておく。
結果的には、例題2は、例題1が計算済ならば、西日本地方の再計算と東日本地方の2箇所の追加計算のみで解が求まるので簡単であった。西日本地方の再計算は1分以内/回、東日本地方の追加計算は2分程度/回なので、時間はそれほど掛からなかった。

図A5-11-1
図A5-11-1
図A5-11-2
図A5-11-2
図A5-11-3
図A5-11-3



更新記録

←前のページ　目次　次のページ→

Copyright(c) 2005　KONDO Hideaki　All rights reserved.
初版： 2005年6月21日　最終更新： 2005年7月17日