巡回セールスマン問題のソルバー「LKH-3」の使い方を詳しく解説

LKH-3は、巡回セールスマン問題（TSP）の近似解を高速に求める強力なソルバーです。しかしながら、ドキュメントファイルは用意されているものの、具体的な使用方法は詳しく説明されていないため、初めて使う人にとっては分かりにくい面があります。本記事では、LKH-3を初めて触る人向けに、インストールから基本的な使い方を実際にTSP問題の設定ファイルを例に解説します。

LKH-3とは

K. HelsgaunによるLin-Kernighan-Helsgaun法(LKH法)の実装です。LKH法は、有名な巡回セールスマン問題（TSP、Travelling Salesman Problem）を解くアルゴリズムで、これをソフトウェアとして実装したものになります。

巡回セールスマン問題は、セールスマンが複数の都市を巡回して最短距離で一度ずつ訪問し、出発点に戻るための最適なルートを求めるという問題です。計算機科学や最適化問題の分野で非常に有名な問題で、この問題のソルバーは生産計画、配送計画などに応用できます。

ホームページを見ると、Version 3.0.9（June 2023）となっており、現在も更新されていることがわかります。

ライセンスについて

ホームページの最後の方に、以下のように書かれています。

“The code is distributed for academic and non-commercial use. The author reserves all rights to the code.”

学術と商用利用以外で利用可能（商用利用不可）ということです。

LKHの特徴

公式に書かれているわけではありませんが、実際に使用した上での特徴になります。

高速

巡回セールスマンのソルバーとして高速です。Googleが開発しているOR-Toolsなどと比較しても高速に近次解を求めることができます。高速だからといって、解の精度が低いわけでもありません。

慣れるまで、若干使いにくいですが、高速性はかなり魅力です

巨大な問題に対応できる

訪問先が数千を超える大規模な問題にも対応できます（実際に使用実績あり）。思った以上に大規模な問題にも適用できたので、驚いています。

kaggleで使うこともあります。

色々な問題を解ける

単純なTSPだけでなく、TSPの派生問題を解くことができます。以下は公式ページに記載されている問題の一覧ですが、並べると非常に多くの種類があることが分かります。

知らないものも多いです

今回は、基本的なTSPについて使い方を解説します。

インストール

ダウンロード

LKH-3は、ダウンロード後にコンパイルしなければなりません。

C/C++の開発環境が必要となりますので、まずばC/C++の開発環境を用意する必要があります。各プラットフォーム（windows/macOS/linux）での開発環境の構築については、ここでは説明しません（windowsは実行ファイルが存在しますので開発環境は必要ありません）。

その後、LKH-3.0.9.tgzをダウンロードします。Windowsの場合は、実行ファイルがこちらからダウンロード可能です。

ダウンロードしたら、以下のコマンドを使って.tgzファイルを展開します。

% tar xxvf LKH-3.0.9.tgz

make

展開されたディレクトリに移動して、makeコマンドを実行します。

% cd LKH-3.0.9
% make

エラーが出なければLKHというファイルが生成されているはずです。

% ls
DOC              LKH              Makefile         README.txt       SRC              pr2392.par       pr2392.tsp       whizzkids96.atsp whizzkids96.par

動作確認

正常に動作するか確認します。以下のコマンドを実行してください。

% ./LKH whizzkids96.par

正常にインストールされていれば以下のような実行結果が出力されます。

　：
（略）
　：
* 40: Cost = 1244_4933, Gap = 5.1564%, Time = 0.37 sec.
* 57: Cost = 1244_4899, Gap = 5.1564%, Time = 0.54 sec.
* 84: Cost = 1244_4823, Gap = 5.1564%, Time = 0.75 sec.
* 92: Cost = 1244_4797, Gap = 5.1564%, Time = 0.77 sec.
* 96: Cost = 1238_4882, Gap = 4.6492%, Time = 0.80 sec.
* 109: Cost = 1238_4872, Gap = 4.6492%, Time = 0.87 sec.
* 134: Cost = 1198_4748, Gap = 1.2680%, Time = 0.99 sec.
* 139: Cost = 1198_4738, Gap = 1.2680%, Time = 1.01 sec.
* 154: Cost = 1198_4724, Gap = 1.2680%, Time = 1.12 sec.
* 331: Cost = 1198_4708, Gap = 1.2680%, Time = 2.08 sec.
* 2272: Cost = 1197_4750, Gap = 1.1834%, Time = 12.81 sec.
* 2275: Cost = 1193_4746, Gap = 0.8453%, Time = 12.83 sec.
* 2340: Cost = 1191_4744, Gap = 0.6762%, Time = 13.21 sec.
* 2411: Cost = 1183_4715, Gap = 0.0000%, Time = 13.73 sec.
Population:
  1: 1183_4715, Gap = 0.0000%
Run 1: Cost = 1183_4715, Gap = 0.0000%, Time = 13.73 sec.

Successes/Runs = 1/1
Penalty.min = 1183, Penalty.avg = 1183.00, Penalty.max = 1183
Gap.min = 0.0000%, Gap.avg = 0.0000%, Gap.max = 0.0000%
Trials.min = 2411, Trials.avg = 2411.0, Trials.max = 2411
Time.min = 13.73 sec., Time.avg = 13.73 sec., Time.max = 13.73 sec.
Time.total = 13.79 sec.
  Size.min = 28, Size.max = 33, Penalty = 1183
  Cost.min = 1173, Cost.max = 1183, Cost.sum = 4715
Best ATSP solution:
  Cost = 1183_4715

簡単な使い方

パラメータファイルとプロブレムファイル

LKHで巡回セールスマン問題を解く場合、パラメータファイルをプロブレムファイルを作成する必要があります。

• パラメータファイル
  各種パラメータを設定するファイルです
• プロブレムファイル
  解きたい問題の内容を記述するファイルです

パラメータファイルの詳しい説明は、LKHのdocフォルダにあります。

• doc/LKH-2_USER_GUIDE.pdf
• doc/LKH-3_PARAMETERS.pdf

また、プロブレムファイルはTSPLIBと共通のようです。

LKHのドキュメントにリンク先が書かれていますが、そのリンク先には現在プロブレムファイルのフォーマットのドキュメントがないみたいです。調べたところ、以下にありましたので、そちらを参照してください。

パラメータファイルの書き方

パラメータ一覧は、LKH起動時に表示されます。

下記は、whizzkids96.parを実行した時に表示されるパラメータです。

これをコピペして、パラメータの意味を調べながら書き換えても良いですし、付属のpr2392.parやwhizzkids96.parをベースに編集しても良いと思います。

パラメータの説明は省略します。自分も基本は、まずは動かしてみて、あとはドキュメントを見ながら必要そうなものを追加している感じで使っています。

PARAMETER_FILE = whizzkids96.par
Reading PROBLEM_FILE: "whizzkids96.atsp" ... done
ASCENT_CANDIDATES = 50
BACKBONE_TRIALS = 0
BACKTRACKING = NO
# BWTSP =
# CANDIDATE_FILE =
CANDIDATE_SET_TYPE = ALPHA
# DISTANCE =
DEPOT = 1
# EDGE_FILE =
EXCESS = 0.0322581
EXTERNAL_SALESMEN = 0
EXTRA_CANDIDATES = 0
EXTRA_CANDIDATE_SET_TYPE = QUADRANT
GAIN23 = NO
GAIN_CRITERION = YES
INITIAL_PERIOD = 124
INITIAL_STEP_SIZE = 1
INITIAL_TOUR_ALGORITHM = WALK
# INITIAL_TOUR_FILE =
INITIAL_TOUR_FRACTION = 1.000
# INPUT_TOUR_FILE =
K = 0
KICK_TYPE = 4
KICKS = 1
# MAX_BREADTH =
MAKESPAN = NO
MAX_CANDIDATES = 6
MAX_SWAPS = 0
MAX_TRIALS = 10000
# MERGE_TOUR_FILE =
MOVE_TYPE = 5 SPECIAL
MTSP_MIN_SIZE = 1
MTSP_MAX_SIZE = 247
MTSP_OBJECTIVE = MINMAX
# MTSP_SOLUTION_FILE =
# NONSEQUENTIAL_MOVE_TYPE = 5
OPTIMUM = 1183
# OUTPUT_TOUR_FILE =
PATCHING_A = 1
PATCHING_C = 0
# PI_FILE =
POPMUSIC_INITIAL_TOUR = NO
POPMUSIC_MAX_NEIGHBORS = 5
POPMUSIC_SAMPLE_SIZE = 10
POPMUSIC_SOLUTIONS = 50
POPMUSIC_TRIALS = 1
POPULATION_SIZE = 10
PRECISION = 100
PROBLEM_FILE = whizzkids96.atsp
RECOMBINATION = IPT
RESTRICTED_SEARCH = YES
RUNS = 1
SALESMEN = 4
SCALE = 1
SEED = 1
# SINTEF_SOLUTION_FILE =
STOP_AT_OPTIMUM = YES
SUBGRADIENT = YES
# SUBPROBLEM_SIZE =
# SUBPROBLEM_TOUR_FILE =
SUBSEQUENT_MOVE_TYPE = 5 SPECIAL
SUBSEQUENT_PATCHING = YES
# TIME_LIMIT =
# TOTAL_TIME_LIMIT =
# TOUR_FILE =
TRACE_LEVEL = 1
VEHICLES = 4

プロブレムファイルの書き方

この記事では、２つの記述パターンでプロブレムファイルの書き方を例示しますが、プロブレムファイルの書き方はサンプルを見ながら学習するのが良いと思います。

公式ページでは、それぞれの問題名がリンクになっていて、それぞれサンプルファイルをダウンロードすることができます。そちらを見ながら、書き方を確認するのが一番早いです。

２次元マップの座標で入力する方法

２次元のマス目上に、点が配置されている場合は、各点の座標を設定したプロブレムファイルを作成します。例えば、下図のように6つの点が指定されている場合、プロブレムファイルは以下のようになります。

パラメータの説明です。

DIMENSIONは点の数です。EDGE_WEIGHT_TYPEは辺の重みのタイプを指定するもので、２次元の距離なので、EUC_2Dとなります。

最後のNODE_COORD_SECTIONがそれぞれの点の座標で、（点の番号、ｘ座標、ｙ座標）の組みを並べます。

NAME : test001
COMMENT : test001 tsp
TYPE : TSP
DIMENSION : 6
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
1 2 2
2 3 5
3 7 3
4 7 7
5 9 5
6 4 6
EOF

次に、パラメータファイルを作成します。とりあえず、pr2392.parをコピーして、必要ない部分をカットし、OUTPUT_TOUR_FILEを追加しました。

OUTPUT_TOUR_FILEを指定しないと結果が出力されません

PROBLEM_FILE = test.tsp
OUTPUT_TOUR_FILE = result.txt
MOVE_TYPE = 5
PATCHING_C = 3
PATCHING_A = 2
RUNS = 10

./LKH test.parで実行すると以下のresult.txtが出力されます。

NAME : test001.18.tour
COMMENT : Length = 18
COMMENT : Found by LKH-3 [Keld Helsgaun] Fri Dec 8 14:25:53 2023
TYPE : TOUR
DIMENSION : 6
TOUR_SECTION
1
2
6
4
5
3
-1
EOF

Length=18なので、距離が18のルートを見つけたようです。TOUR-SECTIONが巡回経路で、これを図示すると以下のようになります。

マトリクスで入力する方法

２D上にマップできない問題などは、マトリクスで入力します。ここでは、以下の図の問題を例に説明します。

これを、表にすると以下のようになります。

一行目は、１から１、２、３、４への距離が０、６、５、５であることを表しています。

このような感じで全ての点から点への距離を表にします。

これをプロブレムファイルにすると以下のようになります。

EDGE_WEIGHT_TYPEにEXPLICITを、EDGE_WEIGHT_FORMATにFULL_MATRIXを設定し、EDGE_WEIGHT_SECTIONに、上の表の値を書きます（最後にEOFを入れるのを忘れないように）

点の数が1000などになると、EDGE_WEIGHT_SECTIONがかなり大きくなります。ファイルをプログラムで生成させるなどの工夫をした方がよいです（1000×1000のマトリクスを手動で埋めるのは現実的ではないです）。

ファイルサイズが大きくなって読み込めないかと心配しましたが、数千までは読み込み、実行ができました。

NAME : test002
TYPE : TSP
DIMENSION : 4
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: FULL_MATRIX 
EDGE_WEIGHT_SECTION
0 6 5 5
6 0 7 4
5 7 0 3
5 4 3 0
EOF

パラメータファイルも用意します。

PROBLEM_FILE = test2.tsp
OUTPUT_TOUR_FILE = result2.txt
MOVE_TYPE = 5
PATCHING_C = 3
PATCHING_A = 2
RUNS = 10

./LKH test2.parで実行すると以下のresult.txtが出力されます。

NAME : test002.18.tour
COMMENT : Length = 18
COMMENT : Found by LKH-3 [Keld Helsgaun] Fri Dec  8 14:15:28 2023
TYPE : TOUR
DIMENSION : 4
TOUR_SECTION
1
2
4
3
-1
EOF

結果を図に書き込むと以下のようになります。ちなみに、これは最短経路です。

「繋がってない経路は、どう表現するれば良いのか？」

繋がっていないパスは、すごく大きな値を設定してください。例えば1と2の経路がつながっていない場合には、1と2の距離を1000とか、10000とか十分大きな値にしておきます。

その他TIPS

初期ツアーファイルが設定できる

パラメータファイルにINITIAL_TOUR_FILEを設定することで、初期の巡回路を設定することができます。ツアーファイルのフォーマットは、OUTPUT_TOUR_FILEで出力されるファイルと同じフォーマットです。

例えば、以下のようになります。この例では１→２→４→３→１の順番で巡回することを指定しています。

TYPE : TOUR
DIMENSION : 4
TOUR_SECTION
1
2
4
3
-1
EOF

初期の巡回路を設定した方が、収束が早くなったり、最適解に近づいたりします。ある程度効率のよいパスがあらかじめわかっているのであれば、設定しておいても良いです。

まとめ

巡回セールスマンのソルバー、LKHについて解説しました。

このソルバーですが、kaggleのサンタコンペでお世話になっています。年に1回しか使わないので使い方含め毎回調べているので、ブログにまとめてみました。

ソルバーとしてはかなり優秀です。巡回セールスマンの近似解を求めたい場合に活用してみてくはどうでしょうか。

ある/Aru

IT＆機械学習エンジニア/ファイナンシャルプランナー（CFP®)

XContact

専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中