当前位置：首页 > news >正文

TSP 问题求解的最好方法 LKH

news 2025/7/14 1:00:05

目前可以查到的最好的方法求解TSP问题是 LKH，所以本篇文章介绍如何使用Matlab 调用LKH
参考文档：

用matlab调用迄今为止最强悍的求解旅行商（TSP）的算法-LKH算法_wx6333e948c3602的技术博客_51CTO博客

【LKH算法体验】用matlab调用迄今为止最强悍的求解旅行商（TSP）的算法-LKH算法_lkh3算法_果州做题家的博客-CSDN博客

使用步骤：
首先需要提前准备好matlab的环境，然后去github 下载matlab程序：
网址链接：https://github.com/unr-arl/LKH_TSP
里面除了有matlab调用程序还有python 的程序

下载之后将内部的函数放到当前文件夹的路径下

然后建立两个文件夹 LKH 和 TSPLIB

下载LKH 应用程序链接如下：

LKH (Keld Helsgaun)

LKH问价夹内放该程序

然后就是编写程序就可以了

%已知距离矩阵，求最优解
clear,clc;
fname_tsp='test';
LKHdir=strcat(pwd,'/LKH/');
TSPLIBdir=strcat(pwd,'/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';
pars_struct.CostMatrixMulFactor = 1000;
pars_struct.user_comment = user_comment;
LKH_TSP(CostMatrix,pars_struct,fname_tsp,LKHdir,TSPLIBdir)

这里需要注意一些细节：
下载下来的LKH_TSP 可能会报错，此时需要更改

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);
% writeProblemFiles(strcat(LKHdir, "/", TSPLIBdir, "/", fname_tsp),CostMatrix_tsp,pars_struct);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
endtsp_sol(end) = [];TSPsolution = tsp_sol;end

https://download.csdn.net/download/qq_34995963/87541471

查看全文

http://www.lryc.cn/news/32325.html