補４．最長片道ルート計算の高速化（その1：整数制約を緩和）

「ＥＸＣＥＬによる最長片道ルート探索」4（1）新幹線を含む通常の最長片道ルートで述べたように、本州地区の最長片道ルートは、ＥＸＣＥＬのソルバーを用いて計算する場合、ソルバーの変数設定の上限などにより分割計算をせざるを得ない。その上、関東を含む東日本地方については、1回の計算で最大20分程度の時間が掛かっており、まだるっこしい。このような状態では、「なんとか、ぎりぎりのところで計算できている」というレベルと言わざるをえない。

ＥＸＣＥＬのソルバーを用いる以上、分割計算はやむを得ないが、東日本地方の計算はなんとか高速化を図りたい。

そこで、今回、いろいろと試したところ、芋づる式に計算高速化に効果的な手法が見つかり、「その1」の成果としては、20分程度の計算を4分程度に短縮することができた。

「その1」は、駅間の枝に設定した0,1変数H(m,n)の「整数制約を緩和」することによって、計算速度を向上させるものである。制約緩和の方法としては、他に「ラグランジュ緩和」を用いる方法も考えられ、こちらは、「その2」で検討することとした。

「その1」の手法は、まだ、制約式（特に、「接続駅においてルートに含まれる枝は0本または2本」の制約）に改善の余地があると思われる。知見のある読者の方が居られたら、是非、改善方法を教示頂きたい。


（１） ベンチマークする例題

計算が高速化したかどうかをベンチマークする例題は、「新幹線を含む通常の最長片道ルート」で計算した「東日本地方」（「富山・糸魚川−美濃太田・多治見−金山・名古屋」と「坂町・新発田−福島・郡山−いわき・岩沼」に挟まれた部分）の最長片道ルートとする。

従って、西日本地方との接続点は、
　　Ｈ（金山・名古屋）＝1
　　Ｈ（美濃太田・多治見）＝0
　　Ｈ（富山・糸魚川）＝0
東北地方との接続点は、
　　Ｈ（坂町・新発田）＝0
　　Ｈ（福島・郡山）＝0
　　Ｈ（いわき・岩沼）＝1
である。

まず、ベンチマーク問題のオリジナルの定式化を以下に整理しておく。
なお、オリジナルの定式化でも、若干、制約式を節約する工夫をしている。具体的には、下記2.の「全接続駅に対して3本のみ2番目の制約式を課し、その上で、Σ全てのn H(m,n)＝1となった接続駅のみに対して、全ての枝に対する制約式を追加した。」という部分である。


  1. m駅とn駅を結ぶ枝に設定する0,1変数をH(m,n) とする。即ち、全てのm,nに対し、



  2. 全ての接続駅において、ルートに含まれる枝は2本又は0本。即ち、全てのmに対し、



  3. 部分巡回が生じた場合は、部分巡回禁止制約を追加。実際に追加した部分巡回禁止制約は以下の11本。（一見複雑であるが、@埼玉県、A房総半島、B新潟近郊の3種類の変種だけである）

    • H(大宮,熊谷)＋H(熊谷,倉賀野)＋H(倉賀野,高麗川)＋H(高麗川, 大宮)＜＝3
    • H(東京,市川塩浜)＋H(市川塩浜,南船橋)＋H(南船橋,蘇我)＋H(蘇我,成東)＋H(成東,成田)＋H(成田,佐倉)＋H(佐倉,千葉)＋H(千葉,西船橋)＋H(西船橋,錦糸町)＋H(錦糸町,東京)＜＝9
    • H(東京,市川塩浜)＋H(市川塩浜,南船橋)＋H(南船橋,蘇我)＋H(蘇我,成東)＋H(成東,成田)＋H(成田,佐倉)＋H(佐倉,千葉)＋H(千葉,西船橋)＋H(西船橋,錦糸町)＋H(錦糸町,秋葉原)＋H(秋葉原,神田)＋H(神田,御茶ノ水)＋H(御茶ノ水,代々木)＋H(代々木,品川)＋H(品川,東京)＜＝14
    • H(東京,市川塩浜)＋H(市川塩浜,南船橋)＋H(南船橋,蘇我)＋H(蘇我,成東)＋H(成東,成田)＋H(成田,佐倉)＋H(佐倉,千葉)＋H(千葉,西船橋)＋H(西船橋,錦糸町)＋H(錦糸町,秋葉原)＋H(秋葉原,御茶ノ水)＋H(御茶ノ水,代々木)＋H(代々木,品川)＋H(品川,東京)＜＝13
    • H(東京,市川塩浜)＋H(市川塩浜,南船橋)＋H(南船橋,蘇我)＋H(蘇我,成東)＋H(成東,成田)＋H(成田,佐倉)＋H(佐倉,千葉)＋H(千葉,西船橋)＋H(西船橋,錦糸町)＋H(錦糸町,秋葉原)＋H(秋葉原,日暮里) ＋H(日暮里,田端)＋H(田端,池袋)＋H(池袋,赤羽)＋H(赤羽,武蔵浦和)＋H(武蔵浦和,西国分寺)＋H(西国分寺,新宿)＋H(新宿,代々木)＋H(代々木,御茶ノ水)＋H(御茶ノ水,神田)＋H(神田,東京)＜＝20
    • H(東京,市川塩浜)＋H(市川塩浜,南船橋)＋H(南船橋,蘇我)＋H(蘇我,成東)＋H(成東,成田)＋H(成田,佐倉)＋H(佐倉,千葉)＋H(千葉,西船橋)＋H(西船橋,錦糸町)＋H(錦糸町,秋葉原)＋H(秋葉原,日暮里) ＋H(日暮里,赤羽)＋H(赤羽,武蔵浦和)＋H(武蔵浦和,西国分寺)＋H(西国分寺,新宿)＋H(新宿,代々木)＋H(代々木,御茶ノ水)＋H(御茶ノ水,神田)＋H(神田,東京)＜＝18
    • H(東京,市川塩浜)＋H(市川塩浜,南船橋)＋H(南船橋,蘇我)＋H(蘇我,成東)＋H(成東,成田)＋H(成田,佐倉)＋H(佐倉,千葉)＋H(千葉,西船橋)＋H(西船橋,錦糸町)＋H(錦糸町,秋葉原)＋H(秋葉原,日暮里) ＋H(日暮里,田端)＋H(田端,赤羽)＋H(赤羽,武蔵浦和)＋H(武蔵浦和,西国分寺)＋H(西国分寺,新宿)＋H(新宿,代々木)＋H(代々木,御茶ノ水)＋H(御茶ノ水,神田)＋H(神田,東京)＜＝19
    • H(日暮里,赤羽)＋H(赤羽,武蔵浦和)＋H(武蔵浦和,西国分寺)＋H(西国分寺,新宿)＋H(新宿,池袋)＋H(池袋,田端)＋H(田端,日暮里)＜＝6
    • H(新潟,燕三条)＋H(燕三条,吉田)＋H(吉田,柏崎)＋H(柏崎,宮内)＋H(宮内,長岡)＋H(長岡,東三条)＋H(東三条,新津)＋H(新津,新発田)＋H(新発田,新潟)＜＝8
    • H(新潟, 吉田)＋H(吉田,柏崎)＋H(柏崎,宮内)＋H(宮内,長岡)＋H(長岡, 燕三条)＋H(燕三条,東三条)＋H(東三条,新津)＋H(新津,新発田)＋H(新発田,新潟)＜＝8
    • H(新潟, 吉田)＋H(吉田,柏崎)＋H(柏崎,宮内)＋H(宮内,長岡)＋H(長岡,東三条)＋H(東三条,新津)＋H(新津,新発田)＋H(新発田,新潟)＜＝7

以上の定式化により、ＥＸＣＥＬのソルバーで計算したところ、部分巡回禁止制約を追加する度に1回の計算時間が長くなり、最終回の計算時間は20分程度であった。今回、計算時間を比べるのは、この最終回の状態である。

実際の計算手順では、部分巡回禁止制約を追加する度に再計算が必要となる。特に房総半島関係で7回も部分巡回禁止制約を追加しているので、全体では、20分×7回＝140分は掛かっていないものの、2時間程度は掛かっているはずである。
従って、20分程度/回が、4分程度/回になれば、全体の計算時間も2時間程度が25分程度に縮小されることが期待される。


（２） 素朴な手法を試してみる

商用のソルバーが、ＥＸＣＥＬのソルバーよりも計算速度が速いのは何故だか私にはよく分かっていないのであるが、その一つの理由は、分岐限定法を実行する時に、分岐変数や分岐頂点を上手く選択しているためだと思われる。
ＥＸＣＥＬのソルバーは、「ＥＸＣＥＬによる最長片道ルート探索」3.簡単な計算例で示したように、上の行から順に分岐変数を選択し、そこから生じる分岐を全て調べ終わったら、次の分岐変数を選択する、という極めて単純な方法を採っている。
この分岐変数や分岐頂点の選択順序を改良すれば、計算速度が向上することが期待されるだろう。しかし、このプログラム自体を変更することは素人には相当重荷である。

そこで、まず、「駅間の枝を長い順に並べ替える」ことにしてみた。こうすれば、ＥＸＣＥＬのソルバーは、自動的に長い枝から順に分岐を行うはずである。長い枝を分岐変数とすれば、分岐変数を0とした時に生成される子問題の最適解が、もとの問題の最適解から大きく外れ、子問題が見切られる可能性が高まるだろう。この方法は、始めの暫定解を見つけ出すのは早いかどうか分からないが、一旦、暫定解が求まれば、他の子問題を見切る速度は速そうである。

しかし、「駅間の枝を長い順に並べ替える」方法で、ベンチマーク問題を再計算したところ、残念ながら計算時間はやはり20分程度掛かってしまった。


諦めきれずに、長い順に並べた枝を眺めていると、長い枝の、0,1変数H(m,n)は、ほとんど1となっているが、100q以上の枝（全部で10本）では、会津若松-小出だけが、
　　Ｈ（会津若松,小出）＝0
となっていることが分かった。

長い枝はなるべく経路に組み込んだ方が全体の距離は長くなりやすいはずだから、会津若松-小出を最長ルートに組み込まなかったのは、よっぽどのことに違いない。始めからＨ（会津若松,小出）＝0で最長ルートを求めれば、早く最適解が見つかるのに、Ｈ（会津若松,小出）＝1を含む子問題を大量に計算した後で、Ｈ（会津若松,小出）＝0を含む子問題に取り掛かったために、計算時間が長くなってしまった可能性もあるだろう。
とすれば、Ｈ（会津若松,小出）を1番始めに分岐すれば良いのではないか？


このように考えた結果、次のような「釘付けテスト」を試すことにした。この方法は、Ｈ（会津若松,小出）を1番始めに分岐することと同じである。
まず、問題を、
　　@　Ｈ（会津若松,小出）＝0に固定
　　A　Ｈ（会津若松,小出）＝1に固定
の2つに分割して、@の問題での最適解を求める。次に、Aの問題は、@の時よりも制約式を緩和して上界を求め、この上界が、@で求めた最適解より小さいことを示す。これにより、@で求めた最適解が、全体の最適解であることが確認できる。

この「釘付けテスト」によって、@の問題を計算したところ、なんと、2分程度で最適解が求まってしまった。これは、恐るべき速さである。

後は、Aの問題からは、@の最適解以上の解は求まらないことを示せば良い。しかし、こちらは簡単そうで、なかなか上手くいかなかった。

Aの問題の上界を求めるに当たって、@と同じ制約式で計算したら、やはり20分程度掛かってしまうはずであるから、時間短縮のためには何らかの制約式の緩和が必要である。
もともと、計算時間が長くなってしまったのは、部分巡回禁止制約を追加していったからであるから、一番簡単な制約式の緩和は、いくつかの部分巡回禁止制約を解除してやることである。
まず、部分巡回禁止制約を埼玉県の
　　H(大宮,熊谷)＋H(熊谷,倉賀野)＋H(倉賀野,高麗川)＋H(高麗川, 大宮)＜＝3
のみにして、計算したところ、計算速度は速いが、求まった答えは、@の最適解を上回るものであった。そこで、更に、房総半島の関連の部分巡回制約7本を追加したが、これでも@の最適解を上回ってしまった。これに新潟近郊の部分巡回制約を追加したら、ほとんど制約緩和にならない。そこで、次に、部分巡回禁止制約を新潟近郊の3本のみにして計算してみた。すると、今度は、20分以上たっても答えが求まらない。これでは、全く計算時間短縮にならない。

部分巡回制約を緩和することは、ここで行き詰まってしまった。しかし、どうも新潟近郊の3本の部分巡回禁止制約が、計算時間を引き延ばしているらしい、ということが分かってきた。


部分巡回制約以外を緩和する方法として他に考えられるのは、「整数制約の緩和」と「ラグランジュ緩和」である。

「整数制約の緩和」は、各枝に設定した0,1変数H(m,n)の設定を から、 に変更するものである。こうすると、H(m,n)は小数となる可能性もあるが、分岐計算がその分なくなるので、計算速度は著しく向上することが期待できる。

「ラグランジュ緩和」は、問題を複雑にしている制約式を、罰金を課して目的関数に組み込むものである。
例えば、部分巡回禁止制約

　　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

を満たすようになるというものである。
この方法も、問題を複雑にしている制約式をなくすことができるので、計算速度を速める効果が期待できる。

そこで、まず、「整数制約の緩和」を、次に「ラグランジュ緩和」を試してみることにした。（「ラグランジュ緩和」は「その2」で検討）


（３） 整数制約を緩和してみる

今、考えようとしているのは、Ｈ（会津若松,小出）＝1に固定した時の上界を求めるのに、整数制約を緩和してみよう、ということである。

この場合、整数制約を緩和するといっても、別に全てのH(m,n)の整数制約を削除しなくてもよいだろう。
今回、問題を複雑にしているのは、新潟近郊の部分巡回禁止制約のようである。この場合、部分巡回を形成しているH(m,n)のどれかが、部分巡回禁止制約を課したことで、新たに分岐変数となり、大量の分岐計算を行って、計算時間を長くしている可能性がある。そこで、新潟近郊の部分巡回禁止制約を課した枝のH(m,n)だけ、整数制約を削除することが考えられる。
新潟近郊の部分巡回禁止制約3本は非常に似通っており、3本とも、新潟-柏崎-長岡-新発田-新潟という循環をベースに、燕三条への迂回方法をアレンジしたものになっている。そこで、この3本の中で一番長い、 に含まれる枝のH(m,n)のみ整数制約を削除することにした。こうすることで、これらのH(m,n)が分岐変数となることはなくなる。
更に、3本全てについて整数制約削除を行わず、対象を1本に絞ったことにより、整数制約を削除したH(m,n)の周囲のH(m,n)は全て整数条件が入ったままとなるため、結果として、整数条件を削除したH(m,n)も整数解となる可能性が高くなるだろう。

結果として、整数条件を削除したH(m,n)も整数解となるのなら、新潟近郊の部分巡回禁止制約に限らず、埼玉県や房総半島の部分巡回禁止制約についても、同じように整数条件を削除した方が、計算速度向上に繋がるだろう。そこで、 及び、 に含まれる枝のH(m,n)についても整数制約を削除することにした。


ここで、ふと、これなら問題をもとに戻しても大丈夫なのではないか？との考えが思いついた。結果として、整数制約を削除したH(m,n)も整数解となるのなら、特にＨ（会津若松,小出）＝1に固定した時に限定せず、問題を「釘付けテスト」以前に戻して、オリジナルの定式化から上記の「整数制約の緩和」だけ行って計算すれば、上界ではなく、最適解になるはずである。計算速度は、Ｈ（会津若松,小出）＝1に固定しようが、しまいが、ややこしい分岐変数を排除できる分、オリジナルの定式化より向上することが期待できるだろう。

そもそも、Ｈ（会津若松,小出）を「釘付けテスト」の対象に選定したのは、最適解がＨ（会津若松,小出）＝0になると分かったから選定できたのであって、最適解が分からない段階では、Ｈ（会津若松,小出）を選定することはほとんど不可能だろう。それなら、はじめから「釘付けテスト」など行わず、「整数制約の緩和」だけ行った方が良い。

以上の考えから、最終的には、オリジナルの定式化の内、上記のH(m,n)（新潟近郊9個、埼玉県4個、房総半島21個、合計34個）のみ整数制約を削除して計算することにした。

この結果、5分程度で最適解が求まった。予想通り、整数制約を削除したH(m,n)も整数解となり、小数解に悩まされることもなかった。34個のH(m,n)について整数制約を削除したという、たったそれだけのことで、20分程度かかる計算が5分程度になったのだから、成果は大きいと言えるだろう。


（４） 更に整数制約を緩和してみる

今回ベンチマークする問題のH(m,n)変数は全部で132個ある。前章では、この内、34個について整数制約を削除して、かなり大きな成果を上げた。しかし、整数制約を課している変数はまだ、132−34＝98個残っている。そこで、前章の方針を更に推し進め、整数制約を課す変数の数をできるだけ少なくすることを考えてみる。

このための一番単純な方法は、まず、全てのH(m,n)の整数制約を削除して計算し、小数解となったH(m,n)にのみ整数制約を課して再計算するものであろう。こうすれば、整数制約無しでも整数解となるH(m,n)には、整数制約は課されない。

今回は、基本的にはこの方法を用いるが、巡回セールスマン問題に使われている、次のような工夫を加えることで、更に整数制約を削減することを目指す。

本文では触れなかったが、実は、巡回セールスマン問題では、H(m,n)の小数解を、整数制約を使わず、「線形制約」のみで排除する方法が知られている。

この「線形制約」は「櫛制約」と呼ばれているもので、例えば、「最適化の手法」（茨木俊秀・福島雅夫著、共立出版、1993年）では、この制約について次のように説明されている。

くし制約(comb inequality)

これは把手(handle)とよばれる集合H⊆Vと歯(tooth)とよばれる集合Ti⊆V(i＝1,2,…,k)が条件
　(a)　Ti∩Tj＝φ (i≠j) 　(筆者注：TiとTjは都市を共有しない)
　(b)│H∩Ti│>=1 (i＝1,2,…,k) 　(筆者注：HとTiは1つ以上の都市を共有）
　(c)│Ti−H│>=1 (i＝1,2,…,k) 　(筆者注：TiはHと共有しない都市がある）
　(d)k：奇数
を満たすとき、

　x(E(H))＋Σ(i=1→k)　x(E(Ti))　<= │H│＋Σ(i=1→k)　(│Ti│−1)−(k+1)/2
　　(筆者注：E(H)はHに含まれる全ての枝、x　(・)　はその枝の数）

によって与えられる。特に、k=1、│H│＝1の場合、この条件は

　x(E(T1))　<= │T1│−1

つまり、部分巡回路除去制約となる。また、すべての歯Tiが

　│Ti│＝2

を満たすとき、特に2-マッチング制約(2-matching inequality)とよぶ。(筆者注：ここで用いられている集合Hと筆者が用いている変数H(m,n)は全く別物である)


図A4-1
図A4-1

図A4-1のように、H、T1、T2、T3の集合がある場合、櫛制約の右辺は、│H│＝5（Hに含まれる都市は5つ）、│T1│＝│T2│＝│T3│＝2（T1、T2、T3に含まれる都市はそれぞれ2つ）、k＝3（歯はT1、T2、T3の3つ）であるから、5+(2-1)+(2-1)+(2-1)-(3+1)/2＝6となる。一方、櫛制約の左辺は、x(E(H))＝3（Hに含まれる枝は3本）、x(E(T1))＝x(E(T1))＝x(E(T1))＝1（T1、T2、T3に含まれる枝はそれぞれ1本）であるから、3+1+1+1＝6となり、櫛制約を満たしていることが分かる。

図A4-2
図A4-2

しかし、図A4-2のような場合、櫛制約の左辺は、x(E(H))＝3.5（Hに含まれる枝は3.5本）、x(E(T1))＝x(E(T1))＝x(E(T1))＝1（T1、T2、T3に含まれる枝はそれぞれ1本）であるから、3.5+1+1+1＝6.5となり、櫛制約を満たしていない。
このように、櫛制約は、図A4-2のような小数解を排除することができるのである。

櫛制約は一読しただけでは、何を言っているのか分かりにくい。そこで、今回のベンチマーク問題を計算する時に、実際に現れる例に置き直して考えてみることにしたい。



図A4-3
図A4-3

図A4-3を見ると、三角形の頂点（岡谷、辰野、塩尻）から3本の角が突き出したような格好をしている。
三角形の辺のH(m,n)を全て0.5と置くと、3本の角のH(m,n)を全て1としても、岡谷、辰野、塩尻におけるH(m,n)の合計は2となっており、「接続駅においてルートに含まれる枝は2本又は0本」の制約が満たされていることが分かる。

片道ルートにするためには、あるループに入る枝と出る枝の合計は偶数になるはずだから、3本の角が三角形ループから出ているのはおかしい。なるべく多くの枝を通過する片道ルートは、次のようになるはずである。


図A4-4
図A4-4

まず、三角形ループに出入りする枝の合計が2本の場合は、図A4-4のように、三角形の2辺を通り、角は2本となるはずである。つまり、図全体の枝の合計は4本である。

図A4-5
図A4-5

また、三角形ループに出入りする枝の合計が4本の場合は、図A4-5のように、三角形の1辺を通り、角は3本＋図に含まれない1本となるはずである。つまり、図全体の枝の合計はやはり4本である。

従って、片道ルートにするためには、これらの三角形と角に対して、 が成立している必要があることが分かる。

ところが、最初の図A4-3の枝の合計は4.5であり、上記の条件を満たしていない。つまり、上記の制約式を課すことで、図A4-3のような小数解を排除することができるのである。



図A4-6
図A4-6

次に、図A4-6は、ループ部分が四角形となっている例である。これも3本の角が突き出している。
これを、なるべく多くの枝を通過する片道ルートにするためには、三角形の時と同様に次のように考えられる。

図A4-7
図A4-7

まず、ループに出入りする枝の合計が2本の場合は、図A4-7のように、四角形の3辺を通り、角は2本となるはずである。つまり、図全体の枝の合計は5本である。

図A4-8
図A4-8

また、四角形の対角線を使う場合も、図A4-8のように、図全体の枝の合計は5本となる。四角形に含まれる辺をいくつ通過できるかは、図上の辺の数ではなく、頂点の数に依存しているので当然といえば当然である。

図A4-9
図A4-9

次に、ループに出入りする枝の合計が4本の場合は、図A4-9のように、四角形の2辺を通り、角は3本＋図に含まれない1本となるはずである。つまり、図全体の枝の合計はやはり5本である。

従って、片道ルートにするためには、これらの四角形と角に対して、 が成立している必要があることが分かる。

ところが、最初の図A4-6の枝の合計は5.25であり、上記の条件を満たしていない。やはり、上記の制約式を課すことで、小数解を排除することができるのである。

ここで、図A4-6の田端のH(m,n)の合計は1.5であり、「接続駅においてルートに含まれる枝は2本又は0本」の制約が満たされていないことに注意すべきである。
これは、オリジナルの「接続駅においてルートに含まれる枝は2本又は0本」の制約式 が、小数解を許容する場合に有効に働かないからである。
つまり、ある接続駅のΣ全てのn H(m,n)を半分にして0〜1の範囲に圧縮し、それを、その接続駅の全ての枝の値と比較する時、全ての枝が0または1であれば、Σ全てのn H(m,n) /2が1/2になった時は、その接続駅のどれかの枝が1であるので、Σ全てのn H(m,n) /2＝＞ 1が成立しなくなり、Σ全てのn H(m,n) /2＝1のケースが排除されるのであるが、今回の田端駅の場合は、最大値をとる枝であるH(池袋,田端)が0.75なので、 が成立してしまい、Σ全てのn H(m,n)が0または2以外となるケース（今回は1.5）を排除できないのである。

しかし、この場合でも、上記の制約式 は有効なのである。


図A4-10
図A4-10

ところが、図A4-10のように、田端のH(m,n)の合計が1以下となると、小数解を含んでいるにも関わらず、図全体の枝の合計は5となるため、上記制約式を満たしてしまうことになる。
このように、「接続駅においてルートに含まれる枝は1本以下」となってしまう場合は、上記制約式を用いることはできない。この場合は、代わりに、例えば、 の制約を課す必要がある。


最後に、ループ部分が五角形となっている例を見ておく。図A4-11では、五角形から5本の角が突き出ている。

図A4-11
図A4-11

これを、なるべく多くの枝を通過する片道ルートにするためには、三角形や四角形の時と同様に次のように考えられる。

図A4-12
図A4-12

まず、ループに出入りする枝の合計が2本の場合は、図A4-12のように、五角形の4辺を通り、角は2本となるはずである。つまり、図全体の枝の合計は6本である。

図A4-13
図A4-13

次に、ループに出入りする枝の合計が4本の場合は、図A4-13のように、五角形の3辺を通り、角は4本となるはずである。つまり、図全体の枝の合計は7本である。

図A4-14
図A4-14

次に、ループに出入りする枝の合計が6本の場合は、図A4-14のように、五角形の2辺を通り、角は5本＋図に含まれない1本となるはずである。つまり、図全体の枝の合計はやはり7本である。

従って、片道ルートにするためには、これらの五角形と角に対して、 が成立している必要があることが分かる。

ところが、最初の図A4-11の枝の合計は7.5であり、上記の条件を満たしていない。やはり、上記の制約式を課すことで、小数解を排除することができるのである。

図A4-15
図A4-15

ここで、図A4-11を少し変形して、図A4-15のような、四角形に4本の角が突き出ているケースを考えてみることにする。4本の枝が突き出ている場合は、「ループを出入りする枝数は偶数」の条件は満たされており、角が3本や5本の時のような矛盾はない点に注意が必要である。

図A4-16
図A4-16

この場合、なるべく多くの枝を通過する片道ルートは、図A4-16のように、図全体の枝の合計は6となる。しかし、小数解を含む図A4-15の図全体の枝の合計も6となるので、角が奇数の時のような不等式制約は有効でなくなってしまう。これが、櫛制約で「k：奇数」としている理由である。

従って、このように「ループから突き出している角が偶数」である場合は、代わりに、例えば、 の制約を課す必要がある。


以上を整理すると、小数解が発生した場合、次のような制約追加を行っていけばよいことになる。
  1. 「接続駅においてルートに含まれる枝は1本以下」となってしまう場合は、原因となる枝のどれか1本に整数制約を追加する。
  2. 「ループから突き出している角が偶数」である場合は、原因となる枝のどれか1本に整数制約を追加する。
  3. 上記以外の場合は、櫛制約を追加する。
この手続きに基づき、制約を追加しながら、繰り返し再計算したところ、最終回の計算は、4分程度で最適解を得ることができた。表A4-17に示す通り、最終時点での櫛制約は6個、整数制約は14個であった。
前回は、整数制約98個で、計算時間が5分程度、今回は、整数制約14個で4分程度だから、整数制約を大幅に削減した割には、計算時間の速度が向上していない。

しかし、今回の方法は、まだ改善の余地があると思われる。それは、上記手続きの内、@「接続駅においてルートに含まれる枝は1本以下」となってしまう場合に、今は無条件に整数制約を追加してしまっているが、もし小数解に対しても有効な「接続駅においてルートに含まれる枝は0本または2本」の制約が見つかれば、整数制約をほとんど使わないで済みそうだからである。

整数制約を削減することは、計算時間の短縮に直結するので、少し無理をしても削減する価値があると思われる。例えば、整数制約を今回の半分の7個以内に収めれば、分岐の回数は最悪でも、27＝128回に過ぎない。128回なら2分程度で計算できるだろうし、最適解は、多分それよりかなり速く（おそらく数十秒で）求まるだろう。

新しい制約式を見つけることは簡単ではなさそうであるが、検討に値する今後の課題と言えよう。


【表A4-17】
（櫛制約：6個）

  • H(岡谷,辰野)＋H(辰野,塩尻)＋H(塩尻,岡谷)＋H(岡谷,小淵沢)＋H(辰野,豊橋)＋H(塩尻,多治見)＜＝4

  • H(赤羽,池袋)＋H(池袋,田端)＋H(田端,日暮里)＋H(日暮里,赤羽)＋H(赤羽,田端)＋H(赤羽,武蔵浦和)＋H(池袋,新宿)＋H(日暮里,秋葉原)＜＝5

  • H(南浦和,赤羽)＋H(赤羽,田端)＋H(田端,日暮里)＋H(日暮里,新松戸)＋H(新松戸,南浦和)＋H(赤羽,日暮里)＋H(南浦和,大宮)＋H(赤羽,武蔵浦和)＋H(田端,池袋)＋H(日暮里,秋葉原) ＋H(新松戸,我孫子)＜＝7

  • H(川崎,尻手)＋H(尻手,鶴見)＋H(鶴見,川崎)＋H(川崎,品川)＋H(尻手,府中本町)＋H(鶴見,東神奈川)＜＝4

  • H(赤羽,田端)＋H(田端,日暮里)＋H(日暮里,赤羽)＋H(赤羽,武蔵浦和)＋H(田端,池袋)＋H(日暮里,秋葉原)＜＝4

  • H(八王子,拝島)＋H(拝島,立川)＋H(立川,八王子)＋H(八王子,甲府)＋H(拝島,高麗川)＋H(立川,府中本町)＜＝4
（整数制約：14個）
　　・　H(豊橋,辰野)＝整数
　　・　H(小出,会津若松) ＝整数
　　・　H(会津若松,新津) ＝整数
　　・　H(小淵沢,佐久)＝整数
　　・　H(小淵沢,岡谷) ＝整数
　　・　H(東神奈川,茅ヶ崎) ＝整数
　　・　H(新潟,吉田) ＝整数
　　・　H(我孫子,成田)＝整数
　　・　H(新発田,新潟) ＝整数
　　・　H(新津,東三条) ＝整数
　　・　H(長岡,燕三条) ＝整数
　　・　H(西船橋,千葉)＝整数
　　・　H(品川,川崎) ＝整数
　　・　H(御茶ノ水,代々木) ＝整数



更新記録
　・　2005年6月21日　：　「部分巡回」「部分循環」を「部分巡回」に用語統一。


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

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