フューチャー技術ブログ

巡回セールスマン問題(TSP)の基本的な解き方(ILS)

SAIGアルバイトの後藤です。業務では、アルゴリズムの知識を用いた既存処理の高速化やスケジュールの自動作成による業務の効率化を行っています。

配送計画問題など、最適化問題に属する社会課題は、部分問題に巡回セールスマン問題(TSP: Travelling Salesman Problem)を含むことが少なくありません。したがってTSPの基本的なアプローチを知っていることは重要です。TSPは組合せ最適化の代表的な問題として古くから様々なアプローチが試みられており、本記事は専門家の方にとっては既知の内容だと思いますが改めて紹介します。この記事では、2/3-optの焼きなまし法(SA: Simulated Annealing)より良い解法として2/3-optの反復局所探索法(ILS: Iterated Local Search)を紹介します(競技プログラマへ: TSPは焼きなましより山登り + Kickが良いという話をします)。

TSPにおいて特に良いとされているILSには次の2つがあります[1]。

  • Lin-Kernighan heuristic ILS
  • 2/3-opt ILS

本記事では、この内の2/3-opt ILSについて紹介します。

目次

導入

巡回セールスマン問題(TSP: Travelling Salesman Problem)

TSPは次のような問題です。

個の頂点 がある。頂点 間には辺 が張られており、距離 が定められている。
このとき、巡回路(長さ の順列 を用いて と表せるような辺集合)のうち、距離の総和が最も短いものを求めよ。

巡回路は、頂点 から出発して、他のすべての頂点をただ一度だけ通り頂点 に戻ってくる経路と解釈することができます。図に表すと、次のようになります。

図1: $N = 5$の場合

丸が各頂点です。矢印が巡回路を表しています。
頂点 に戻ってこないようなバリエーションも存在しますが、同様のアプローチが有効です。

最も距離の短い解(巡回路)を愚直に求めようとすると組合せ爆発が起こり、頂点数が多くなると現実的な時間内で解を見つけることができません。そこで、なるべく総距離の短い解(近似解)を一定時間内に見つけることを考えます。このようなアルゴリズムをヒューリスティックアルゴリズムと言います。短時間でより良い解が見つかるアルゴリズムが良いヒューリスティックアルゴリズムと言えます。この記事では、TSPのヒューリスティックアルゴリズムとしてよく紹介されるアプローチを実際に用いて、検証・比較を行います。

TSPの種類

TSPは距離の制約によりいくつかの種類があります。基本的な制約は次の3つです。

  • Metric: 三角不等式 が成り立つ。
  • Symmetric: 頂点 から への距離と、頂点 から への距離が等しい。すなわち、 が成り立つ。
  • Euclidean: 頂点間の距離が2次元ユークリッド空間上の距離になっている。すなわち、が成り立つ。ただし、 は頂点 座標、 は頂点 座標を表す。

EuclideanならMetricかつSymmetricです。また、Symmetricでない場合をAsymmetricと言います。
この記事ではSymmetricが成り立つTSP、すなわちSymmetric TSPのみを考えます。なお、Asymmetric TSPは適切な変形によりSymmetric TSPに帰着することができます[2]。

現実の問題

TSPは現実では、次のような問題として現れます。

  • 郵便物配達のルート最適化
  • 作業スケジューリングの最適化

図1が郵便物配達時のルートを表しているとすると、頂点 が郵便局などの配達拠点、頂点 が配達先に該当します。頂点間の距離は移動にかかる時間などでも良く、その場合はなるべくすべての配達先を訪れてなるべく早く帰ってくるルートを探す問題になります。

作業スケジューリングの最適化は一見するとTSPには関係なさそうですが、次のような場合TSPと見なせます。

個の作業 がある。作業 を行った後に作業 を行うと、作業 の準備には, 分かかる。また、何も作業を行っていない初めの状態を作業 とし、同じく が定まっている。
このとき、作業 から始めて、すべての作業をただ一度だけ行い作業 に戻ってくる順番のうち、最も準備時間が短いものを求めよ。

イメージとしては、作業 は作業前の片付いた状態で、その状態から作業 の準備にかかる時間が 分です。そこからすべての作業を終えて、また作業前の状態に片付けるための最適な順番を求めるのが、上記のスケジューリング問題になります。

異なるアルゴリズムの結果を比較

異なる3つのアルゴリズムで127頂点のTSPを解いたときの巡回路をビジュアライズしました。

図2: 結果の比較

左からNearest Neighbor(貪欲法)、2-opt SA、2-opt ILS(今回紹介する手法)です。それぞれの巡回路の総距離は135737, 1186034, 118282となっています。2-opt ILSの巡回路は最適解で、最も総距離が短い巡回路です。
Nearest Neighborは、頂点 (またはランダムな頂点)からまだ訪れていない頂点のうち最も近いものから訪れることを繰り返す単純な手法ですが、最後の方に余った頂点に訪れなければいけないため、明らかに効率が悪くなっている経路があります。
2-opt SAと2-opt ILSの違いは分かりにくいですが、よく見ると中央付近のルートが異なります。

アルゴリズム

2/3-opt

2-opt(3-opt)はある巡回路から2つ(3つ)の辺を削除して2つ(3つ)の辺を繋ぎ直すことを改善ができなくなるまで繰り返すアルゴリズムです。
2-optは次の図のようなイメージです。図では頂点番号を省略しています。

2-optのイメージ

左の順回路から赤い2つの辺を削除して、その後に青い辺で辺が削除された頂点を繋ぎ直しています。これにより、巡回路が効率的になっています。このような変更をどの辺の組に対して行っても改善ができなくなるまで行うのが2-optです。改善できないような組に対しては変更を行いません。3-optの場合は、3つの辺を削除し3つの辺を繋ぎ直す組み合わせをすべて試し、最も距離が短くなるような繋ぎ方に繋ぎ直します。

一般に、 個の辺を削除し 個の辺を繋ぎ直して改善することを改善ができなくなるまで繰り返すアルゴリズムを-optと言います。

ILSを紹介するにあたり、まずLSを紹介します。

現在の解 から、ある操作を行って得られる解の集合 の近傍と言います。LSは、この近傍の中から よりも良い解、すなわち となるような に遷移し続けて、遷移ができなくなるまで繰り返す手法です。2-optもLSの一種であり、近傍 は巡回路 から2本の辺を繋ぎ直して得られる巡回路の集合です。
これ以上改善が行えないような解 、すなわち となるような が存在しないような を局所解と呼びます。

1
2
3
4
5
6
7
8
9
10
11
def local_search(x):
while True:
updated = False
for x2 in sigma(x): // xの近傍をすべて見る
if score(x2) < score(x):
x = x2
updated = True
break
if not updated:
break
return x

LSでは局所解に達したときに必ずそれが最適解であるという保証は通常ありません。そこで、LSで局所最適解に到達した場合にKickまたはPerturbationと呼ばれる遷移[3]により局所解を脱出し、再びLSを適用することにより別の局所解へと遷移することを期待する手法がILSです。そのためKickはLSでまた同じ局所解へと到達しにくい遷移である必要があります。しかし一方で、できるだけ変更の小さな遷移が良いとされています。現在の比較的良い解を壊しすぎてしまうと、ランダムに解を作成してLSを適用するのと変わらなくなってしまうためです。

1
2
3
4
5
6
7
8
9
10
def iterated_local_search(x):
x_global = x
for i in range(num_iterated):
x = x_global
x = kick(x)
x = local_search(x)
if score(x) < score(x_global):
x_global = x

return x_global

Double-Bridge

TSPで近傍を2/3-optにする場合、KickはDouble-Bridgeという遷移が良いとされています[3]。
Double-Bridgeでは、次のように赤い辺を4つ削除し、青い辺で繋ぎ直します。

double-bridge

一見、2-optを2回適用することで同じ遷移ができるような気がしますが、途中で巡回路を2つに分離してしまうため、2回では不可能です。また、辺を変える本数も4本と2/3-optにない遷移の中で最低の本数であるため、元の解からの変更は最小限です。そのため、2/3-optのKickとしてDouble-Bridgeは適しているとされています。(本来Double-Bridgeはこの記事では紹介しないLin-Kernighan heuristicの近傍に含まれないような最小の変化から来ています)[3]。

焼きなまし法(SA: Simulated Annealing)

SAは確率的に近傍から解 を選びます。 である場合は に遷移し、の場合はスコアの悪化具合と実行時間やループ回数に応じて確率的に遷移します。スコアが悪化するほど遷移する確率は低く、実行時間が長い/ループ回数が多いほど遷移する確率は低くなります。
記事にある2/3-opt SAは、近傍を2/3-optの近傍にしたものです。2-opt(3-opt)で削除する辺を2つ(3つ)ランダムで選び辺を繋ぎ直して遷移をします。

温度などSAの詳しいことについてはこの記事では説明しません。

SAの擬似コードです。

1
2
3
4
5
6
7
8
def simulated_annealing(x):
temp = start_temp // 初期温度の設定
while elapsed() < time_limit: // 一定の時間ループを回す
x2 = choose_from_sigma(x) // 近傍からランダムで遷移先を選ぶ
diff = score(x2) - score(x)
if diff < 0 or prob(diff, temp):
x = x2
temp = update_temp(elapsed(), time_limit) // 温度の更新

2-opt ILS

今回紹介する手法は、2-opt ILSです。LS部分を2-optにして、KickをDouble-Bridgeにします。
今回の手法ではランダムに選んだ4本の辺を使ってDouble-Bridgeを行います。この時、選ぶ4辺に制約や遷移後の解の総距離による遷移の制限はありません。完全にランダムで1度だけDouble-Bridgeを行ってから2-optによるLSを行うことを繰り返します。

擬似コードは次の通りです。

1
2
3
4
5
6
7
8
9
10
def iterated_local_search(x):
x_global = x
for i in range(num_iterated):
x = x_global
x = double_bridge(x)
x = two_opt(x)
if score(x) < score(x_global):
x_global = x

return x_global

2-optの実装上の工夫

頂点が 個の場合、削除できる辺が 個ありそこから2つ選ぶので、2-optの近傍は全部で 個あります(同一視の仕方にもよります)。しかし、スコアが改善できる解 があるかどうかを調べるのに、実はすべての近傍を見る必要はありません。この工夫により、2-opt ILSの性能は飛躍的に良くなります。

今、巡回路中に および があるとします( は相異なります)。

改善結果

このとき、2-optで2つの辺 を繋ぎ変えてスコアが良くなるには、次の条件を満たしている必要があります。

この条件は次の条件を2つとも満たしている場合、成り立ちません。

各不等式の和を取ると になるからです。

したがって、2-optで2つの辺 を繋ぎ変えてスコアが良くなるには、次の条件のどちらかを満たしている必要があります(十分でない)。(条件1)

以上から、2つの条件のどちらかを満たしている辺をすべて調べ上げれば、現在の巡回路から2-optで改善できるかどうかが分かります。
具体的には次の通りです。

今、辺 を削除する1つ目の辺とします。この時、削除する2つ目の辺の候補として次の条件のうちどちらかを満たす を調べれば十分です。


1つ目の式は になる場合、2つ目の式は になる場合です。2つ目の式ではSymmetricであることを使いました。
つまり、 よりも から近い頂点が の候補に、 よりも から近い頂点が の候補になります。 のどちらかが決まればもう一方も決まることに注意してください。

これを巡回路中の全ての辺に対して行えば、条件1を満たす全ての辺の組を探索できます。

上の条件を満たす頂点を効率的に探すには、あらかじめ各頂点から近い順に他の頂点のリストを持っておけばよいです。これは、構築時に で処理することが可能です。

同様の工夫を3-optに対して行うことも可能です。

[4]のHow to Make 2-Opt and 3-Opt Run Quicklyに条件1のうち片方だけ見れば良いと書いていたので、片方だけ見る実装も実験に加えました。しかし、条件を片方だけ見れば良いというのは嘘で、例えば1つ目の条件だけを見ていると次のようなケースを見逃します(もし間違いであればご指摘お願いします)。

反例

その他の工夫

その他にも、頂点 から最も近い 点のみを探索する、辺を削除した頂点の近くの頂点のみを探索するなどの高速化方法がありますが[4]、今回は実装していません。

実験方法

比較方法

比較するアルゴリズムは次の通りです。実行時間と発見した解の総距離を比較します。

  • Nearest Neighbor
  • 2-opt LS (実装上の工夫なし)
  • 3-opt LS (実装上の工夫なし)
  • 2-opt SA
  • 3-opt SA
  • 2-opt ILS (実装上の工夫なし)
  • 3-opt ILS (実装上の工夫なし)
  • Improved 2-opt ILS (実装上の工夫あり)
  • Improved 2-opt ILS one-side (実装上の工夫あり) (条件1のうち片方の条件のみを見る)

LSは局所解に達するまで実行し局所解に達したときの時間を実行時間としています。
SA/ILSは10秒間実行した時の解を出力します。Kick + LSの実行が終わったタイミングで時間制限を過ぎていた場合、そこまでに発見した解を出力とします。したがって、実行時間が10秒を過ぎる場合があります。

使用したテストケース

TSPLIBSymmetric TSPインスタンスの中から、EDGE_WEIGHT_TYPEがEUC_2DかEXPLICITであり頂点数が5000以下のものをすべて選び実験を行いました。EDGE_WEIGHT_TYPEはグラフの辺の重みの指定の仕方です。EUC_2Dは各頂点の位置が2次元ユークリッド空間上の点として与えられ、頂点間の距離はユークリッド距離を整数に丸めたものです。EXPLICITは頂点間の距離が明示的に与えられます。EDGE_WEIGHT_TYPEは他にもありますが、今回の実験ではこの2つのみを使用しました。理由は、インスタンスを読み込むプログラムを作る時間的コストと使用できるインスタンスの個数の兼ね合いです。頂点数の制約は実行時間から来ています。特に、3-optは破滅的な時間がかかります。

使用した言語

Javaを使って実験を行いました。

備考

巡回路は、頂点番号の動的配列として表現しました。この場合、2-optや3-optでは区間反転操作を行う必要が出てきますが、線形時間かけて愚直に行っています。
SAの温度管理には、頂点間の距離の平均を とおき、初期温度を 、最終温度を とする指数スケジューリングを用いています。

実験結果

最も良いスコアを太字にしています。最もスコアが良い手法が複数ある場合は、その中で計算時間が最も少ない手法のスコアと計算時間を太字にしています。また、optimumはそのインスタンスの最適解であり、見つかった解が最適解である場合はoptimumの列を太字にしています。
また、3-optなど実行が10秒以内に終わらなかったものは太字にする処理の対象外としています。機械的に実行時間が11000msより大きい場合は対象外としています。

instance optimum Nearest Neighbor score 2-opt score 2-opt SA score 2-opt ILS score 3-opt score 3-opt SA score 3-opt ILS score Improved 2-opt ILS score Improved 2-opt ILS score one-side Nearest Neighbor time [ms] 2-opt time [ms] 2-opt SA time [ms] 2-opt ILS time[ms] 3-opt time [ms] 3-opt SA time [ms] 3-opt ILS time [ms] Imporved 2-opt ILS time [ms] Imporved 2-opt ILS time one-side [ms]
0 a280 2579 3157 2724 2603 2579 2680 2695 2626 2579 2579 6 25 10000 5364 1785 10002 10531 278 156
1 bayg29 1610 2005 1685 1610 1610 1610 1610 1610 1610 1610 0 0 3365 1 1 3445 3 0 0
2 bays29 2020 2258 2078 2020 2020 2070 2020 2020 2020 2020 0 0 2939 0 1 2902 2 2 2
3 berlin52 7542 8980 8785 7542 7542 7986 7542 7542 7542 7542 0 1 4335 26 5 4674 14 11 6
4 bier127 118282 135737 123709 118604 118657 121145 120692 118282 118282 118282 1 14 10000 10000 92 10000 8623 506 75
5 brazil58 25395 30774 27390 25395 25395 25622 25395 25395 25395 25395 0 2 5475 19 8 5569 12 3 2
6 brg180 1950 12360 2030 2660 1950 1950 2610 1950 1950 1950 0 3 10000 220 82 10000 560 28 24
7 ch130 6110 7579 6502 6136 6128 6248 6167 6124 6110 6128 1 15 10007 10000 94 10001 10012 4584 10000
8 ch150 6528 8191 6725 6549 6528 6730 6528 6549 6528 6528 0 56 10000 2067 282 7128 10008 5115 724
9 d1291 50801 60214 56979 55971 53619 53268 102240 52598 51369 51159 2 14319 10014 10054 634815 10014 189314 10000 10010
10 d1655 62128 74033 69805 68047 67427 65530 136592 65217 63273 63715 17 30100 10008 10157 875332 10006 933608 10002 10010
11 d198 15780 18240 16153 15842 15805 15939 15833 15788 15783 15783 0 40 10000 10000 617 10002 10204 10000 10000
12 d2103 80450 86653 85621 93519 87720 83675 224084 85176 82690 83063 17 7060 10011 10168 2046086 10006 944512 10000 10007
13 d493 35002 41665 37463 35560 35937 36519 37722 36012 35223 35183 1 1324 10009 10006 9975 10013 14634 10000 10001
14 d657 48912 61627 52206 50029 50982 50349 58431 50721 49234 49186 0 1529 10009 10015 98604 10014 27628 10000 10002
15 dantzig42 699 956 699 699 699 699 699 699 699 699 0 0 3550 0 0 4055 0 0 0
16 eil101 629 803 690 638 630 651 638 629 629 629 0 8 10003 10000 43 10009 5670 35 9
17 eil51 426 511 444 426 426 432 426 426 426 426 0 9 4187 4259 4 4671 6357 4 5
18 eil76 538 642 562 538 538 557 543 538 538 538 0 3 4432 77 4 10004 266 16 6
19 fl1400 20127 27447 21914 21453 20863 20789 32998 20453 20321 20386 14 36529 10014 10062 619434 10000 372016 10003 10013
20 fl1577 22249 27996 25103 24470 23909 22729 51493 22724 22346 22437 15 10437 10001 10129 962587 10011 580440 10002 10009
21 fl3795 28772 35285 30934 47278 32506 30345 155618 30349 29602 29285 11 714219 10003 13374 26571284 10000 13728554 10007 10046
22 fl417 11861 15013 12683 11963 11920 12048 12590 11925 11866 11865 0 331 10010 10003 8843 10000 10750 10001 10006
23 fnl4461 182566 229963 198781 250850 202601 190748 754112 190417 194962 194105 32 584440 10011 11222 49703258 10014 50845165 10049 10015
24 fri26 937 1112 1016 937 937 937 937 937 937 937 0 0 2825 0 1 3130 1 1 0
25 gil262 2378 3208 2503 2399 2381 2519 2452 2411 2395 2380 0 267 10013 10001 1272 10010 10017 10000 10009
26 gr120 6942 9351 7341 7005 6961 7146 6967 6956 6942 6942 1 19 10000 10000 92 10000 10000 489 728
27 gr17 2085 2187 2095 2085 2085 2085 2085 2085 2085 2085 0 0 1504 0 0 1776 0 1 1
28 gr21 2707 3333 2877 2707 2707 2707 2707 2707 2707 2707 0 0 2299 0 0 2156 1 0 0
29 gr24 1272 1553 1286 1272 1272 1314 1272 1272 1272 1272 0 1 2531 1 0 2504 0 0 0
30 gr48 5046 6098 5107 5046 5046 5138 5075 5046 5046 5046 0 1 4558 5 3 10000 29 4 6
31 hk48 11461 13181 12441 11461 11461 11805 11461 11461 11461 11461 0 1 4310 4 2 4442 17 11 3
32 kroA100 21282 27807 22844 21388 21282 21305 21282 21282 21282 21282 0 10 10000 258 44 6892 185 18 22
33 kroA150 26524 33633 28094 26701 26525 27909 26961 26524 26524 26524 0 25 10010 10000 140 10000 7624 3243 580
34 kroA200 29368 35859 31269 29882 29368 30230 30035 29606 29368 29368 0 117 10010 7508 681 10007 10260 2949 5096
35 kroB100 22141 29158 22927 22284 22141 22304 22276 22141 22141 22141 0 9 10011 444 77 10001 805 82 37
36 kroB150 26130 34499 27568 26279 26132 27135 26228 26141 26141 26130 0 43 10000 10001 72 10000 10005 10000 2651
37 kroB200 29437 36980 31267 29673 29448 30209 29853 29586 29437 29438 0 105 10015 10000 715 10002 10212 4537 10000
38 kroC100 20749 26227 21369 20852 20749 20852 20749 20749 20749 20749 0 9 10009 163 47 6806 508 22 26
39 kroD100 21294 26947 22279 21294 21294 21929 21294 21294 21294 21294 0 10 5539 453 46 7953 3199 6641 328
40 kroE100 22068 27460 23383 22160 22106 22160 22100 22068 22121 22121 0 10 10000 10000 73 10015 190 10000 10005
41 lin105 14379 20356 15893 14379 14379 14577 14379 14379 14379 14379 0 10 5832 228 38 6611 98 58 9
42 lin318 42029 54019 44849 42972 42524 43070 43600 42992 42029 42163 0 212 10007 10001 3410 10005 11100 6317 10011
43 nrw1379 56638 68964 62111 60591 60395 58703 101318 58844 57757 57592 7 20903 10005 10088 617046 10013 447405 10004 10003
44 p654 34643 43457 37110 35835 34843 35233 42008 35135 34669 34681 2 1696 10003 10011 26871 10005 20144 10003 10011
45 pa561 2763 3422 3151 2853 2838 2876 3170 2898 2785 2784 1 381 10000 10002 15822 10000 14348 10000 10000
46 pcb1173 56892 71978 62512 60083 60960 59366 97467 59151 57691 58107 11 6665 10001 10004 235688 10000 234567 10000 10003
47 pcb3038 137694 176310 150588 164337 152590 143486 438703 143891 144821 143379 12 118397 10000 10025 9706220 10000 5242701 10019 10004
48 pcb442 50778 61979 57171 51491 52176 52606 54374 52786 50956 51127 0 386 10008 10005 9063 10005 10449 10000 10013
49 pr1002 259045 331103 281036 270069 273466 270183 381306 273080 262842 263929 4 1501 10003 10010 130736 10001 73284 10003 10001
50 pr107 44303 46680 46485 44387 44303 44617 44522 44303 44303 44303 0 6 10004 226 55 10001 2176 119 80
51 pr124 59030 69297 65668 59608 59030 59076 59548 59030 59030 59030 0 12 10009 58 100 10005 602 110 26
52 pr136 96772 120769 105133 97232 96772 99635 97251 98464 96772 96772 0 29 10011 3937 133 10010 10052 1776 3503
53 pr144 58537 61652 61847 58600 58537 58763 58590 58537 58537 58537 0 9 10012 144 125 10003 2366 26 4
54 pr152 73682 85699 75410 74084 73682 74017 73880 73818 73682 73682 0 9 10007 3631 140 10001 10047 18 291
55 pr226 80369 94683 86065 81341 80369 82150 81307 80369 80369 80369 0 9 10002 1829 859 10013 4199 694 422
56 pr2392 378032 461170 378032 429248 378032 378032 1093433 378032 378032 378032 19 58 10013 0 112692 10014 0 780 752
57 pr264 49135 58023 57512 50134 49135 50339 50258 49203 49135 49135 0 37 10000 4465 1822 10010 10219 138 1550
58 pr299 48191 59890 52667 48556 48749 48793 49522 48991 48224 48191 0 76 10006 10000 1690 10010 10119 10000 7776
59 pr439 107217 131281 116275 111723 107880 111457 115361 110894 107250 107292 0 165 10006 10001 11019 10014 10670 10001 10011
60 pr76 108159 153462 118343 109125 108159 112130 108159 108159 108159 108159 0 1 10007 304 17 6099 183 6 12
61 rat195 2323 2752 2484 2355 2323 2390 2374 2356 2328 2328 0 9 10000 8148 457 10000 10024 10000 10000
62 rat575 6773 8605 7471 7052 7074 7083 7923 7066 6811 6863 1 205 10005 10011 28656 10002 20744 10002 10004
63 rat783 8806 11054 9480 9252 9353 9172 11676 9126 8921 8942 15 2519 10008 10025 56809 10014 65418 10001 10004
64 rat99 1211 1554 1321 1214 1211 1265 1222 1211 1211 1211 0 8 10003 722 35 10005 333 145 12
65 rd100 7910 9938 8523 7910 7910 8047 7949 7910 7910 7910 0 11 5855 288 27 10010 78 338 51
66 rd400 15281 19183 16376 15696 15538 15933 16129 15855 15428 15287 0 807 10015 10006 7920 10008 10187 10000 10005
67 rl1304 252948 335779 285536 274109 270205 262659 546642 269500 258063 256374 16 23056 10011 10019 573347 10013 455686 10003 10007
68 rl1323 270199 332103 294672 288616 286293 280884 566533 277973 272076 272432 17 32391 10006 10091 573562 10004 510171 10005 10006
69 rl1889 316536 389270 342694 356890 342276 331589 896820 331915 324475 323870 10 105024 10000 10312 2517344 10004 2389999 10007 10011
70 si1032 92650 94571 93022 93063 92717 93025 103572 93294 92650 92650 1 1831 10000 10001 137112 10000 85388 4049 2174
71 si175 21407 22263 21638 21431 21415 21557 21445 21407 21407 21414 0 14 10000 10000 417 10000 5126 940 10000
72 si535 48450 50144 49013 48541 48503 48662 49348 48650 48472 48469 1 499 10000 10003 18432 10000 12577 10001 10000
73 st70 675 830 708 675 675 684 675 675 675 675 4 15 4618 840 66 5710 307 5 484
74 swiss42 1273 1630 1370 1273 1273 1273 1273 1273 1273 1273 0 0 3689 2 3 3880 2 1 1
75 ts225 126643 152493 134187 127245 126643 133282 132056 126643 126643 126643 2 10 10000 1442 653 10000 2992 327 830
76 tsp225 3916 5030 4082 4002 3919 4076 3992 3948 3948 3916 3 54 10000 10001 1150 10000 10106 10000 636
77 u1060 224094 308980 247073 235187 235853 233363 339920 232942 226448 227283 2 782 10000 10031 251737 10000 167394 10000 10003
78 u1432 152970 188807 169528 165706 167363 160736 278953 160727 156596 156710 3 1827 10000 10130 596566 10000 870417 10001 10000
79 u159 42080 54675 42981 42460 42080 42396 42479 42080 42080 42080 1 1 10000 388 187 10000 2279 12 33
80 u1817 57201 72030 64249 64413 62567 60268 142201 60686 58465 59107 4 5337 10000 10105 1132689 10000 1094623 10000 10002
81 u2152 64253 79260 72582 74327 71186 67741 179530 68455 66889 66404 7 10063 10000 10072 3140315 10000 2968500 10013 10004
82 u2319 234256 278765 254330 247570 250419 240484 511622 241262 239887 239019 7 9642 10000 10111 4725590 10000 3403010 10015 10000
83 u574 36905 50459 39266 38279 38397 38510 43293 38573 37383 37080 5 54 10000 10005 33905 10000 17362 10001 10000
84 u724 41910 52943 45531 43246 43735 43553 53371 43106 42176 42235 1 3821 10000 10021 75655 10000 48134 10001 10000
85 vm1084 239297 301477 263051 257955 252752 252136 412136 250971 241329 240870 2 16012 10000 10032 365833 10000 288922 10004 10001
86 vm1748 336556 408102 363517 367307 362314 352835 817011 353231 341702 345219 6 79973 10000 10190 1829514 10000 1372701 10004 10031

次に2-opt SAとImproved 2-opt ILSで見つかった解が最適解の何倍であるかをプロットした図を示します。

散布図

横軸が頂点数、縦軸が見つかった解の総距離/最適解の総距離です。点がグラフの下にプロットされているほど最適解に近く、良い解が見つかっています。

Improved 2-opt ILSの条件を2つとも見た場合と1つだけ見た場合の比較です。

比較した散布図

頂点数が多いインスタンスでは、片方の条件のみを見た方が良い解が見つかる傾向にありそうです。これは制限時間10秒では、片方の条件を見ずに多少改善を見逃すことよりも、多くの回数のKick + LSを行った方が良いからだと考えられます。

さいごに

多くの場合に単純な2-opt SAより2-opt ILSの方が時間内に良い解を出せることが実験から分かりました。
自分でTSPやTSPに類似した問題のソルバを書かなければならない場合はこの知識が役に立つかと思います。しかし、自分で書く必要がなくライセンス条件を満たす場合は既存のヒューリスティックソルバ[5]を使ったほうが圧倒的に性能が良く、手間もかかりません。
また、厳密に解くソルバも存在します。TSPを厳密に解くのは数十頂点ですら難しいと思われがちですが、このソルバで厳密に解けている数万頂点の問題もあります[6]。各インスタンスの最適解がどうして分かるのか疑問に思った方もいると思いますが、このような厳密に解くソルバによって最適解が求まっています。

参考

[1] Hong, Inki, Andrew B. Kahng, and Byung-Ro Moon. 1997. “Improved Large-Step Markov Chain Variants for the Symmetric TSP.” Journal of Heuristics 3 (1): 63–81. https://doi.org/10.1023/a:1009624916728.

[2] Johnson, David S., Gregory Gutin, Lyle A. McGeoch, Anders Yeo, Weixiong Zhang, and Alexei Zverovitch. 2007. “Experimental Analysis of Heuristics for the ATSP.” In The Traveling Salesman Problem and Its Variations, edited by Gregory Gutin and Abraham P. Punnen, 445–87. Boston, MA: Springer US. https://doi.org/10.1007/0-306-48213-4_10.

[3] Martin, Olivier, Steve W. Otto, and Edward W. Felten. 1992. “Large-Step Markov Chains for the TSP Incorporating Local Search Heuristics.” Operations Research Letters 11 (4): 219–24. https://doi.org/10.1016/0167-6377(92)90028-2.

[4] Johnson, D., and L. A. McGeoch. 1995. “The Traveling Salesman Problem: A Case Study in Local Optimization.” https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.7639&rep=rep1&type=pdf.

[5] K. Helsgaun. 2019. “LKH-3” http://webhotel4.ruc.dk/~keld/research/LKH-3/

[6] “Concorde TSP Solver” https://www.math.uwaterloo.ca/tsp/concorde.html