【LKH算法体验】用matlab调用迄今为止最强悍的求解TSP问题的算法-LKH算法

一、LKH算法简介

Keld Helsgaun 是丹麦 罗斯基勒大学计算机科学专业的名誉副教授。 他于 1973 年在 哥本哈根大学获得DIKU 计算机科学硕士学位。他自 1975 年以来一直在罗斯基勒大学工作。他的研究兴趣包括人工智能（问题解决和启发式）和组合优化。

在这里插入图片描述
LKH 是Lin-Kernighan解决旅行商（TSP）问题启发式的有效实现。
计算实验表明，LKH 非常有效。尽管该算法是近似的，但以令人印象深刻的高效率产生最佳解决方案。LKH 已经为我们能够获得的所有已解决问题提供了最佳解决方案；包括一个 109399 个城市的实例（最大的非平凡实例求解到最优）。此外，该算法改进了一系列具有未知最优值的大规模实例的已知解决方案，其中包括 1,904,711 个城市实例 ( World TSP )。

LKH算法是目前求解TSP问题最牛X的算法，下面我们来学习如何调用它。LKH的网址链接为：http://akira.ruc.dk/~keld/research/LKH/。网站上有K. Helsgaun的各种报告，感兴趣的小伙伴可以仔细研究研究。

二、调用LKH的matlab接口

如何用matlab调用LKH这个比较牛X的TSP solver，我们可以在github上找到一位大神写的LKH的matlab接口（网址链接：https://github.com/unr-arl/LKH_TSP），除了matlab接口还有调用LKH的python接口。下次给大家介绍Python接口。

接下来废话不说，进入正题，在github上下载完LKH的matlab接口一切都没问题的时候，接下来看看到这个接口，我们仍是一脸懵逼。

function TSPsolution = LKH_TSP(CostMatrix,pars_struct,fname_tsp,LKHdir,TSPLIBdir)
%
%   Syntax:
%   TSPsolution = LKH_TSP(CostMatrix,pars_struct,fname_tsp,LKHdir,TSPLIBdir)
%
%   This functions solves TSP problems using the Lin-Kernighan-Helsgaun
%   solver. It assumes that a compiled executable of the LKH solver as
%   found at: http://www.akira.ruc.dk/~keld/research/LKH/ is available at
%   the LKHdir directory. Furthermore a TSPLIB directory is assumed.
%   For the definition of the TSPLIB and the compilation of the LKH code
%   check the aforementioned url. 
%
%   Inputs:
%   CostMatrix      : the Cost Matrix of the (asymmetric) TSP. [e.g. it can be an NxN matrix of distances]
%   pars_struct     : parameters structure with
%                   : -> CostMatrixMulFactor (value that makes Cost Matrix
%                        almost integer. [eg. pars_struct.CostMatrixMulFactor = 1000; ]
%                     -> user_comment (a user comment for the problem) [optional]
%   fname_tsp       : the filename to save the tsp problem
%   LKHdir          : the directory of the LKH executable
%   TSPLIBdir       : the directory of the TSPLIB files
%   
%   Outputs:
%   TSPsolution     : the TSP solution
%   
%   Authors:
%   Kostas Alexis (kalexis@unr.edu)
%

CostMatrix_tsp = pars_struct.CostMatrixMulFactor*CostMatrix;
CostMatrix_tsp = floor(CostMatrix_tsp);
user_comment = pars_struct.user_comment; 

fileID = writeTSPLIBfile_FE(fname_tsp,CostMatrix_tsp,user_comment);

disp('### LKH problem set-up...');
%%  Solve the TSP Problem via the LKH Heuristic
disp('### Now solving the TSP problem using the LKH Heuristic...');
copy_toTSPLIBdir_cmd = ['cp ' LKHdir fname_tsp '.txt' ' ' TSPLIBdir];

start_lkh_time = cputime;
lkh_cmd = [LKHdir 'LKH' ' ' TSPLIBdir fname_tsp '.par'];
[status,cmdout] = system(lkh_cmd,'-echo');
end_lkh_time = cputime;

copy_toTSPLIBdir_cmd = ['cp ' LKHdir fname_tsp '.txt' ' ' TSPLIBdir];
[status,cmdout] = system(copy_toTSPLIBdir_cmd);
disp('### ... done!');
solution_file = [fname_tsp '.txt']; 
tsp_sol_cell = importdata(solution_file);

rm_solution_file_cmd = ['rm ' LKHdir fname_tsp '.txt'];
[status,cmdout] = system(rm_solution_file_cmd);

tsp_sol = [];
for i = 1:length(tsp_sol_cell.textdata)
    if ~isempty(str2num(tsp_sol_cell.textdata{i}))
        tsp_sol(end+1) = str2num(tsp_sol_cell.textdata{i});
    end
end
tsp_sol(end) = [];

TSPsolution = tsp_sol;

end

我们发现下面这两行代码才是最有用的：

lkh_cmd = [LKHdir 'LKH' ' ' TSPLIBdir fname_tsp '.par'];
[status,cmdout] = system(lkh_cmd,'-echo');

解释一下：LKHdir就是在http://akira.ruc.dk/~keld/research/LKH/这个网站上下载的LKH.exe的存储位置。LKH.exe可以在画红色箭头的位置下载。

在这里插入图片描述
TSPLIBdir 就是存放.par文件的路径，fname_tsp 就是.tsp的文件名。

在这里有一个注意事项：尽量把各个文件夹都放在同一目录下，自己可以新建一个“LKH”文件夹。

然后把TSPLIB和LKH.exe文件都放在这个目录下，然后再把.par文件和.tsp文件都放在TSPLIB目录下，.par文件其实是执行LKH.exe的参数。
在这里插入图片描述

如：pr2392.tsp的.par文件长这样
在这里插入图片描述

小伙伴在调用LKH.exe之前，一定要把参数信息先写好，否则无法调用成功，其实把这几行复制一下，然后改一下第一行即可，改成相对应.tsp文件的路径+.tsp文件名。

比如说我要测试某个文件(如:Tnm52.tsp)，则第一步一定是自己先写好Tnm52.par文件，怎么写？可以先创建一个Tnm52.txt文件，然后把文件类型改为.par，这样就可以在matlab中打开Tnm52.par文件。打开之后一定是空的，然后把之前的pr2392.par文件中的内容复制粘贴过去，做一下对应修改。

接下来，编写如下调用LKH的matlab代码。

 %%已知城市各点坐标，求最优解
clear,clc;
fname_tsp='pr2392';
LKHdir=strcat(pwd,'/LKH/');
TSPLIBdir=strcat(pwd,'/LKH/TSPLIB/');
lkh_cmd=[LKHdir 'LKH' ' ' TSPLIBdir fname_tsp '.par'];
 
%status 为零表示命令已成功完成。MATLAB 将在 cmdout 中返回一个包含当前文件夹的字符向量
[status,cmdout]=system(lkh_cmd,'-echo');

%%先用strfind函数设置好id和_iso的位置，
%然后再根据这两个位置直接提取字符串中在这两个位置之间的字符串就是你所需要的数字
%strfind(s1,s2)--or strfind(s1,pattern),其意思在s1中搜索pattern

first=strfind(cmdout,'Cost.min = ');
last=strfind(cmdout,', Cost.avg');
minCost=str2num(cmdout(first+11:last-1));

以pr2392.tsp为例测试调用结果，从命令行窗口可以看到Cost.min=378032就是最优值。
在这里插入图片描述

三、应用举例

使用LKH算法，求解”运动比赛项目排序问题“：

在各种运动比赛中，为了使比赛公平、公正、合理的举行，一个基本要求是：在比赛项目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。下表是某个小型运动会的比赛报名表。有14个比赛项目，40名运动员参加比赛。表中第1行表示14个比赛项目，第1列表示40名运动员，表中数值为“1”表示运动员参加此项比赛，数值为“0”表示运动员不参加此项比赛。建立此问题的数学模型，并且合理安排比赛项目顺序,使连续参加两项比赛的运动员人次尽可能的少。

运动员 / 项目 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 0 1 0 0 0 0 1 1 0 0 0 1 0 0
2 0 0 0 0 1 0 0 0 1 0 0 0 0 1
3 0 1 0 0 0 1 0 0 0 0 0 0 1 0
4 0 0 0 0 1 0 0 1 0 0 0 0 0 1
5 1 0 0 0 0 0 0 0 1 0 0 1 0 0
6 0 0 1 0 0 0 0 0 0 0 1 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 1 0 1
8 1 0 0 0 0 0 0 0 0 0 0 0 1 0
9 0 1 0 0 0 1 0 0 1 0 0 0 1 0
10 0 1 0 1 0 1 0 0 0 1 0 0 0 0
11 1 0 0 0 0 1 0 0 0 0 0 1 0 0
12 0 0 0 0 1 0 0 0 0 0 0 0 1 0
13 1 0 0 0 0 0 0 0 0 0 1 0 1 0
14 0 0 0 0 1 1 0 1 0 0 0 0 0 0
15 0 0 0 0 1 0 0 1 0 0 0 0 0 1
16 0 0 0 0 0 0 1 0 1 0 0 0 0 1
17 1 0 1 0 0 0 0 0 0 0 0 0 0 0
18 0 0 0 0 0 0 0 0 0 1 0 0 0 1
19 0 0 0 0 0 0 0 1 0 0 0 0 1 0
20 0 0 0 1 0 1 0 0 0 0 0 0 0 0
21 1 0 0 0 0 0 1 0 0 0 0 0 0 0
22 0 1 0 0 0 0 0 0 0 0 1 0 0 0
23 0 0 0 0 0 0 0 0 0 1 0 0 0 1
24 1 0 0 0 1 0 0 0 0 1 0 1 0 0
25 0 1 0 1 0 0 0 0 0 0 0 0 1 0
26 1 0 0 0 0 0 0 0 0 0 1 0 0 0
27 0 0 1 0 0 0 0 0 1 0 0 0 0 0
28 0 1 0 0 1 0 0 0 0 0 0 0 0 0
29 0 0 0 1 0 0 0 0 1 0 0 0 0 1
30 0 0 0 0 0 1 0 0 0 0 1 0 0 0
31 0 0 1 0 1 0 0 0 0 0 0 0 0 1
32 0 0 0 0 0 0 0 0 0 1 0 0 1 0
33 0 0 1 0 0 1 0 0 0 0 0 0 0 0
34 1 0 0 1 0 0 0 1 0 0 0 1 0 0
35 0 0 1 0 0 0 0 0 0 0 1 0 0 1
36 0 0 0 0 0 1 0 0 0 1 0 0 0 0
37 0 0 0 1 0 0 1 0 0 0 0 0 1 0
38 1 0 1 0 1 0 0 0 0 0 0 0 1 0
39 0 0 0 0 1 0 1 0 0 0 1 1 0 0
40 0 0 1 0 0 0 1 0 0 1 0 1 0 0

求解过程：

（1）构造距离矩阵

%构造距离矩阵方法如下：
%若项目i和j相邻，计算同时参加这两个项目人数，
%作为i和j距离d(i,j)。则问题转化为求项目1到项目14的一个排列
%使相邻距离和最小。我们采用TSP问题求解。
%将Excel表中0-1表，拷贝到数据文件table1.txt中。
%但由于开始项目和结束项目没有连接，可考虑引入虚拟项目15
%该虚拟项目与各个项目的距离都为0。这样让链和圈等价。成功转换为TSP问题。
clear,clc;
load table1.txt;
a=table1;
[m,n]=size(a);
d=zeros(n+1,n+1); %定义距离矩阵;
for i=1:n
    for j=1:n
        for k=1:m
            d(i,j)=d(i,j)+a(k,i)*a(k,j);
            %计算不同项目之间距离
        end
    end
end
for i=1:n+1
    d(i,i)=0;
end
%输出文件
fid=fopen('dist.txt','w');
for i=1:n+1
    for j=1:n+1
        fprintf(fid,'%1d ',d(i,j));
    end
    fprintf(fid,'\n');
end
fclose(fid);

得到如下距离矩阵：
在这里插入图片描述

（2）编写接口参数文件sports.par与数据文件sport.tsp。

sports.par内容如下：

PROBLEM_FILE = sports.tsp
OPTIMUM 378032
MOVE_TYPE = 5
PATCHING_C = 3
PATCHING_A = 2
RUNS = 10
TOUR_FILE = sports.txt

sport.tsp内容如下:

COMMENT : a comment by the user
TYPE : TSP
DIMENSION : 15
EDGE_WEIGHT_TYPE : EXPLICIT
EDGE_WEIGHT_FORMAT: FULL_MATRIX
EDGE_WEIGHT_SECTION
0 0 2 1 2 1 1 1 1 1 2 4 3 0 0
0 0 0 2 1 3 1 1 1 1 1 1 3 0 0
2 0 0 0 2 1 1 0 1 1 2 1 1 2 0
1 2 0 0 0 2 1 1 1 1 0 1 2 1 0
2 1 2 0 0 1 1 3 1 1 1 2 2 4 0
1 3 1 2 1 0 0 1 1 2 1 1 2 0 0
1 1 1 1 1 0 0 1 1 1 1 3 1 1 0
1 1 0 1 3 1 1 0 0 0 0 2 1 2 0
1 1 1 1 1 1 1 0 0 0 0 1 1 3 0
1 1 1 1 1 2 1 0 0 0 0 2 1 2 0
2 1 2 0 1 1 1 0 0 0 0 1 1 1 0
4 1 1 1 2 1 3 2 1 2 1 0 0 1 0
3 3 1 2 2 2 1 1 1 1 1 0 0 0 0
0 0 2 1 4 0 1 2 3 2 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
EOF

(3)调用LKH算法

%运动会比赛项目排序问题
%已知距离矩阵，求最优解
clear,clc;
fname_tsp='sports';
LKHdir=strcat(pwd,'/LKH/');
TSPLIBdir=strcat(pwd,'/LKH/TSPLIB/');
lkh_cmd=[LKHdir,'LKH',' ',TSPLIBdir,fname_tsp,'.par'];
%距离矩阵
D=[0 0 2 1 2 1 1 1 1 1 2 4 3 0 0 
0 0 0 2 1 3 1 1 1 1 1 1 3 0 0 
2 0 0 0 2 1 1 0 1 1 2 1 1 2 0 
1 2 0 0 0 2 1 1 1 1 0 1 2 1 0 
2 1 2 0 0 1 1 3 1 1 1 2 2 4 0 
1 3 1 2 1 0 0 1 1 2 1 1 2 0 0 
1 1 1 1 1 0 0 1 1 1 1 3 1 1 0 
1 1 0 1 3 1 1 0 0 0 0 2 1 2 0 
1 1 1 1 1 1 1 0 0 0 0 1 1 3 0 
1 1 1 1 1 2 1 0 0 0 0 2 1 2 0 
2 1 2 0 1 1 1 0 0 0 0 1 1 1 0 
4 1 1 1 2 1 3 2 1 2 1 0 0 1 0 
3 3 1 2 2 2 1 1 1 1 1 0 0 0 0 
0 0 2 1 4 0 1 2 3 2 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];
CostMatrix=D;
user_comment='a comment by the user';
writeTSPLIBfile_FE(fname_tsp,CostMatrix,user_comment,TSPLIBdir); 
targetPath='.\';
copyfile([TSPLIBdir,fname_tsp,'.tsp'],targetPath)
system(lkh_cmd,'-echo');

结果如下：
在这里插入图片描述
最优解为1（即：连续参加两项比赛的运动员人次），打开生成的sports.txt查看最优路径：
在这里插入图片描述
即最优路径为：

1->2->3->8->10->9->11->4->5->7->6->15->12->13->14->1

去掉增加的虚拟运动项目15，即得比赛项目安排顺序为：

12->13->14->1->2->3->8->10->9->11->4->5->7->6

这个结果比较好，与我用遗传算法求得的结果完全一致！不错，LKH算法计算效率很高。

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！
在这里插入图片描述

# matlab # 算法 # 开发语言
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

基于华为云码道，多轮提示开发简易在线通讯录Web应用

avatar 2048 AI社区
cover

SQL优化及实战分享

avatar 2048 AI社区
cover

MCP实现+原理+源码+鉴权

avatar 2048 AI社区