ＥＸＣＥＬによる最長片道ルート探索
1. 巡回セールスマン問題
最長片道ルート問題は世間で広く研究はされていないが、それと共通点を持っている巡回セールスマン問題は世界中で研究されており、関連する図書がたくさんある。巡回セールスマン問題がこれほど研究されているのは、その問題設定の単純さに対して、完全な解法がなく、ゆえに解法に工夫の余地が多いからである。
問題設定は、「決められた複数の都市を一筆書きで巡回する最短経路を求めよ」というものである。
図15
例えば、図15のＡ〜Ｆの6都市を一筆書きで巡回する最短経路を考えてみる。この場合、都市を結ぶ枝は6C2=15本であり、6都市を巡回するためにはその枝から6本を選択する必要があるので、その組み合わせは15C6=5005通りあることになる。この問題の一番単純な解法は、この5005通りの中から巡回ルートになっているものを選び出し、その距離を全て計算して、最短のものを求めることである。しかし、このような単純列挙法は都市数が増加すると組合わせ爆発を起こして直ぐに破綻することになる。都市数100の場合、100C2=4950、4950C100=1.1305×10211となるが、1.1305×10211通りを全て計算するには1020回/秒（ちなみに3GHz 32bit ＣＰＵの動作回数は約1.3×1019回/秒）の速度で計算しても、10183年（ちなみに地球の年齢は約40億年＝4×109年）以上かかる計算量なのである。
そこで、発想を変えて、これをＥＸＣＥＬのソルバーなどにより簡単に解を求めることができる整数計画問題に持ち込むことが、巡回セールスマン問題の最適解を求める際の1つのアイディアである。
これを整数計画問題にするために、まず、都市a、都市bを結ぶ枝に対して、その枝を通る場合は1、通らない場合は0を取る変数H（a,b）を設定し、
T = 3H(A,B)+2H(A,C)+9H(A,D)+7H(A,E)+13H(A,F)+5H(B,C)+4H(B,D)+7H(B,E)+9H(B,F)+7H(C,D)+3H(C,E)+12H(C,F)+8H(D,E)+3H(D,F)+7 H(E,F)
を最小化することを考える。例えば、Ａ→Ｂ→Ｃ→Ｄ→Ｅ→Ｆ→Ａの順番に回るとH(A,B)、 H(B,C)、H(C,D)、H(D,E)、H(E,F)、H(A,F)が1となり、それ以外のH(a,b)は0となるから、T＝3×1+2×0+9×0+7×0+13×1+5×1+4×0+7×0+9×0+7×1+3×0+12×0+8×1+3×0+7×1＝43である。
このTを「一筆書き」という条件の下で最小化すれば良い。問題は、この「一筆書き」という条件を定式化することであり、整数計画問題にするためにはこれを線形制約式にする必要があるのである。
巡回セールスマン問題では、「一筆書き」という条件を、「全ての都市において、ルートに含まれる枝は必ず2本である」という条件に置き換えて取り敢えず問題を解いてしまうという手法を用いている。この条件緩和が「一筆書き」を定式化する際の非常に重要なポイントである。この条件に置き換えた場合、線形制約式で表現することは容易であり、上図の例では、
A : H(A,B)+H(A,C)+H(A,D)+H(A,E)+H(A,F) = 2
B : H(A,B)+H(B,C)+H(B,D)+H(B,E)+H(B,F) = 2
C : H(A,C)+H(B,C)+H(C,D)+H(C,E)+H(C,F) = 2
D : H(A,D)+H(B,D)+H(C,D)+H(D,E)+H(D,F) = 2
E : H(A,E)+H(B,E)+H(C,E)+H(D,E)+H(E,F) = 2
F : H(A,F)+H(B,F)+H(C,F)+H(D,F)+H(E,F) = 2
の6本となる。ここで、ＥＸＣＥＬのソルバーに目的関数Tとこの6本の線形制約式を入力すれば、一旦、暫定的な解を求めることができる。
勿論、このようにして求めた解はより緩い条件で計算したものであったから必ずしも一筆書きになるとは限らない。「全ての都市において、ルートに含まれる枝は必ず2本である」という条件だと、図16の様に複数の部分巡回ルートが形成される可能性があるのである。
図16 （部分巡回路）
巡回ルートが1つの固まりにならず、このような部分巡回ルートが解になってしまった場合、制約条件を追加して再計算する必要がある。部分巡回ルートを解消するには、部分巡回ルート同士を繋ぐどれかの枝、即ち、AC、AE、AF、BC、BE、BF、CD、DE、DFの何れかが必ずルートに含まれるようにすればよい。これは、H(A,C)+H(A,E)+H(A,F) +H(B,C)+H(B,E)+H(B,F)+H(C,D)+H(D,E)+H(D,F)=＞1という線形制約式で表わすことができる。或いは、この線形制約式は太線ルートを禁止する制約、即ち、H(A,B) +H(B,D)+H(A,D)=<2又はH(C,E)+ H(C,F)+H(E,F)=<2でもよい。
（補5注1でそれぞれ「部分巡回禁止制約」「部分巡回強制接続制約」と定義した。）
このように、部分巡回ルートを解消する線形制約式を追加して再計算を繰り返し、求めたルートから部分巡回ルートがなくなれば、それが求める一筆書きの最短ルートとなるのである。
つまり、「一筆書き」の定式化は、@「全ての都市において、ルートに含まれる枝は必ず2本である」という条件への置きかえ、A部分巡回路の排除、によって達成されるということである。
実際には「全ての都市において、ルートに含まれる枝は必ず2本である」という緩和条件はかなり有効で、それほど多くの追加条件を必要としない。この緩和条件設定の発想がなかったらおそらく最長片道ルートを求めることは相当困難になっていたと思われる。
更新記録
・ 2005年6月21日 ： 「部分巡回禁止制約」「部分巡回強制接続制約」についての注記追加。
←前のページ 目次 次のページ→
Copyright(c) 2005 KONDO Hideaki All rights reserved.
初版： 2005年2月12日 最終更新： 2005年6月21日