最近小编恰好遇到这样一个问题，如何用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 (kalexis@unr.edu)
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这个网站查看各个算例最优值的结果。发现两个值相同，小伙伴们可以继续测试其他算例，在这里小编不演示其他算例了。