用matlab调用迄今为止最强悍的求解旅行商（TSP）的算法-LKH算法

最近小编恰好遇到这样一个问题，如何用matlab调用比较牛X的TSP solver，小编费劲千辛万苦终于在github上找到一位大神写的LKH的matlab接口（网址链接：​​https://github.com/unr-arl/LKH_TSP​​），除了matlab接口还有调用LKH的python接口。

可能各位小伙伴对LKH算法还不太了解，不过没关系，大家只要记住LKH算法是目前求解TSP问题最牛X的算法，然后会调用它就可以了。LKH的网址链接为：​​http://akira.ruc.dk/~keld/research/LKH/​​。网站上有K. Helsgaun的各种报告，感兴趣的小伙伴可以仔细研究研究。

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

1function TSPsolution = LKH_TSP(CostMatrix,pars_struct,fname_tsp,LKHdir,TSPLIBdir)
 2%
 3%   Syntax:
 4%   TSPsolution = LKH_TSP(CostMatrix,pars_struct,fname_tsp,LKHdir,TSPLIBdir)
 5%
 6%   This functions solves TSP problems using the Lin-Kernighan-Helsgaun
 7%   solver. It assumes that a compiled executable of the LKH solver as
 8%   found at: http://www.akira.ruc.dk/~keld/research/LKH/ is available at
 9%   the LKHdir directory. Furthermore a TSPLIB directory is assumed.
10%   For the definition of the TSPLIB and the compilation of the LKH code
11%   check the aforementioned url. 
12%
13%   Inputs:
14%   CostMatrix      : the Cost Matrix of the (asymmetric) TSP. [e.g. it can be an NxN matrix of distances]
15%   pars_struct     : parameters structure with
16%                   : -> CostMatrixMulFactor (value that makes Cost Matrix
17%                        almost integer. [eg. pars_struct.CostMatrixMulFactor = 1000; ]
18%                     -> user_comment (a user comment for the problem) [optional]
19%   fname_tsp       : the filename to save the tsp problem
20%   LKHdir          : the directory of the LKH executable
21%   TSPLIBdir       : the directory of the TSPLIB files
22%   
23%   Outputs:
24%   TSPsolution     : the TSP solution
25%   
26%   Authors:
27%   Kostas Alexis ([email protected])
28%
29
30CostMatrix_tsp = pars_struct.CostMatrixMulFactor*CostMatrix;
31CostMatrix_tsp = floor(CostMatrix_tsp);
32user_comment = pars_struct.user_comment; 
33
34fileID = writeTSPLIBfile_FE(fname_tsp,CostMatrix_tsp,user_comment);
35
36disp('### LKH problem set-up...');
37%%  Solve the TSP Problem via the LKH Heuristic
38disp('### Now solving the TSP problem using the LKH Heuristic...');
39copy_toTSPLIBdir_cmd = ['cp ' LKHdir fname_tsp '.txt' ' ' TSPLIBdir];
40
41start_lkh_time = cputime;
42lkh_cmd = [LKHdir 'LKH' ' ' TSPLIBdir fname_tsp '.par'];
43[status,cmdout] = system(lkh_cmd,'-echo');
44end_lkh_time = cputime;
45
46copy_toTSPLIBdir_cmd = ['cp ' LKHdir fname_tsp '.txt' ' ' TSPLIBdir];
47[status,cmdout] = system(copy_toTSPLIBdir_cmd);
48disp('### ... done!');
49solution_file = [fname_tsp '.txt']; 
50tsp_sol_cell = importdata(solution_file);
51
52rm_solution_file_cmd = ['rm ' LKHdir fname_tsp '.txt'];
53[status,cmdout] = system(rm_solution_file_cmd);
54
55tsp_sol = [];
56for i = 1:length(tsp_sol_cell.textdata)
57    if ~isempty(str2num(tsp_sol_cell.textdata{i}))
58        tsp_sol(end+1) = str2num(tsp_sol_cell.textdata{i});
59    end
60end
61tsp_sol(end) = [];
62
63TSPsolution = tsp_sol;
64
65end
66

可能是小编的理解能力有点差劲，到现在也没看明白怎么调用，不过小编发现下面这两行代码才是最有用的：

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

可能各位小伙伴刚开始看有点没看懂，没关系，下面小编解释一下：LKHdir就是在​​http://akira.ruc.dk/~keld/research/LKH/​​这个网站上下载的LKH.exe的存储位置。LKH.exe在小编画红线的地方下载。

TSPLIBdir 就是存放.par文件的路径，小编先给出TSPLIB的网址链接​​https://wwwproxy.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/​​，打开之后应该是这样

然后下载第一个ALL_tsp.tar.gz（是一个合集），里面既有数据集又有各个算例的最优解。

fname_tsp 就是.tsp的文件名。

在这里有一个注意事项：尽量把各文件夹都放在根目录下，以小编为例，小编新建一个LKH文件夹

然后把TSPLIB和LKH.exe文件都放在这个目录下，

然后再把.par文件和.tsp文件都放在TSPLIB目录下：

之前忘记说一件事就是.par文件其实是执行LKH.exe的参数。

a280.tsp的.par文件长这样

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

比如说我要测试ali535.tsp文件，则第一步一定是先自己写好ali535.par文件，怎么写：小编的做法是先创建一个ali535.txt文件，然后把文件类型改为.par，这样就可以在matlab中打开ali535.par文件。打开之后一定是空的，然后把之前的a280.par文件中的内容复制粘贴过去。

这是需要把划红线的文件名称修改成ali535.tsp，就大功告成。

接下来附上小编修改后的调用LKH的matlab代码。

1clear
 2clc
 3
 4fname_tsp='a280';
 5LKHdir='C:/LKH/';
 6TSPLIBdir='C:/LKH/TSPLIB/';
 7lkh_cmd = [LKHdir 'LKH' ' ' TSPLIBdir fname_tsp '.par'];
 8
 9%status 为零表示命令已成功完成。MATLAB 将在 cmdout 中返回一个包含当前文件夹的字符向量
10[status,cmdout] = system(lkh_cmd,'-echo');
11
12%% 先用strfind函数好到id和_iso的位置，
13%然后再根据这两个位置直接提取字符串中在这两个位置之间的字符串就是你所需要的数字
14%strfind(s1,s2)--or strfind(s1,pattern),因此其意思在s1中搜索pattern
15
16first=strfind(cmdout,'Cost.min = ');
17last=strfind(cmdout,', Cost.avg');
18minCost=str2num(cmdout(first+11:last-1));

12行以后的代码是小编为了提取当前算例的最优值。

以a280.tsp为例测试调用结果，从命令行窗口可以看到Cost.min就是最优值。LKH求解a280.tsp的最优值为2579，我们再去​​https://wwwproxy.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/STSP.html​​这个网站查看各个算例最优值的结果。发现两个值相同，小伙伴们可以继续测试其他算例，在这里小编不演示其他算例了。

各位小伙伴也注意到了“请按任意键继续...”，调用LKH.exe结束后，需要各位在命令行窗口手动继续，然后才能结束该程序。目前小编还没想到什么好的办法能解决这个问题，如果小伙伴有想法的话，欢迎与小编交流。

代码链接（后台回复“LKH”提取代码）：​

链接：​​https://pan.baidu.com/s/1WPde4811WyGUDghxxdcpOA​​

提取码：jv9e

ALL_tsp文件夹是在​​https://wwwproxy.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/​​上下载的数据集。

LKH_TSP-master文件夹是在​​https://github.com/unr-arl/LKH_TSP​​上下载的原始接口。

LKH文件夹是小编改写的接口。

LKH文件夹里面的内容如下：

友情提示

代码的有效期只有7天，如需代码，请微信公众号后台联系小编，或者微博私信小编，微博ID：随心390。小编会第一时间回复您。

微博：随心390

长按识别二维码关注我们