如何用LKH求解器处理多旅行商问题（mTSP）？从参数配置到结果分析
如果你正在处理物流配送、无人机巡检或者多车辆路径规划这类问题，那么“多旅行商问题”（Multiple Traveling Salesman Problem, mTSP）很可能就是你绕不开的一个核心挑战。与经典的单一旅行商问题不同，mTSP要求将一组城市点分配给多个旅行商（或车辆），每个旅行商从同一个或不同的起点出发，各自完成一条闭合路径，并且所有城市都被访问且仅被访问一次。这个问题的复杂度随着城市数量和旅行商数量的增加而急剧上升，手动寻找最优解几乎不可能。幸运的是，我们有像LKH（Lin-Kernighan-Helsgaun）这样的世界级启发式求解器，它以其强大的寻优能力，成为了学术界和工业界解决大规模TSP/mTSP问题的首选工具之一。
然而，将LKH应用到mTSP上，并非简单地运行一个命令就能万事大吉。从理解mTSP数据文件的特殊格式，到精细调整.par参数文件中的每一个开关，再到读懂输出结果中那些Cost、Gap、Trials背后的含义，每一步都藏着影响最终方案质量和计算效率的细节。这篇文章，我将结合自己多次在真实项目中部署LKH求解mTSP的经验，为你拆解从环境搭建、数据准备、参数配置到结果解读与优化的完整流程。我们的目标不仅是让程序“跑起来”，更是让你能“调得好”，真正驾驭这个强大的工具来解决你的实际问题。
1. 理解mTSP问题与LKH求解器基础
在深入技术细节之前，我们有必要先厘清几个基本概念。多旅行商问题（mTSP）是经典TSP的泛化。想象一下，一家电商公司在某个城市有多个配送中心和一支车队，需要为成千上万的顾客送货。如何为每辆车分配一组顾客点，并规划出每条路线，使得总行驶距离（或时间、成本）最短，同时还要满足每辆车的载重、行驶距离等约束？这就是一个典型的带约束的mTSP。
LKH求解器由Keld Helsgaun教授维护和开发，是当前公认性能最强的TSP精确/启发式求解器之一。它的核心是Lin-Kernighan局部搜索算法的改进和扩展版本。简单来说，算法从一个初始解（可能很差的路径）开始，通过一系列复杂的“边交换”操作（如k-opt）来不断改进路径，试图找到全局最优或接近最优的解。对于mTSP，LKH通过引入“伪节点”（Dummy Node）或特定的数据格式，将多旅行商问题巧妙地转化为一个扩展的、但可被标准TSP算法处理的形式。
注意：LKH本身主要针对对称和非对称TSP进行了极致优化。处理mTSP时，通常需要我们将问题“编码”成它能够理解的标准TSP格式，这是成功应用的第一步，也是最关键的一步。
1.1 LKH求解器的获取与编译
LKH是开源软件，获取非常方便。官方版本通常以压缩包形式发布。虽然原始文章提到了3.0.9版本，但建议直接访问Helsgaun教授的研究主页获取最新稳定版，因为后续版本可能包含性能提升和Bug修复。
在Linux或macOS系统下，可以通过终端命令直接下载和编译：
# 下载最新版本（请替换为实际最新版本号） wget http://akira.ruc.dk/~keld/research/LKH-3/LKH-3.0.9.tgz # 解压 tar xvfz LKH-3.0.9.tgz # 进入目录 cd LKH-3.0.9 # 编译 make执行make后，会在当前目录生成一个名为LKH的可执行文件。这就是我们后续调用的求解器核心。整个过程通常很顺利，如果遇到编译错误，大概率是缺少基础的C编译环境（如gcc、make），安装即可。
对于Windows用户，虽然官方没有提供预编译的二进制文件，但可以通过Cygwin、MinGW或WSL（Windows Subsystem for Linux）环境来执行上述同样的编译步骤，这通常是更可靠的方式。
2. 准备mTSP问题数据：TSPLIB格式详解
LKH求解器遵循TSPLIB标准格式来定义问题。TSPLIB是一个广泛使用的旅行商问题数据集标准。要让LKH处理mTSP，我们必须按照特定格式准备数据文件（通常是.tsp或.atsp后缀）。
一个标准的TSPLIB文件包含两个主要部分：规格说明部分和数据部分。对于mTSP，关键在于EDGE_WEIGHT_TYPE和EDGE_WEIGHT_SECTION的设定。
2.1 关键参数解析
下表列出了定义mTSP问题时最核心的几个规格参数：
| 参数名 | 含义与取值 | mTSP场景下的注意事项 |
|---|---|---|
TYPE | 问题类型。对于标准mTSP，通常设为ATSP（非对称TSP）或TSP（对称TSP）。 | mTSP通过引入“仓库”伪节点后，常被构造为ATSP。 |
DIMENSION | 城市的数量。 | 这里的维度是转换后的问题维度。例如，有1个仓库、50个客户点、3个销售员，转换后的维度可能大于50。 |
EDGE_WEIGHT_TYPE | 边权值的计算方式。 | 这是关键！对于自定义距离矩阵的mTSP，必须设置为EXPLICIT。 |
EDGE_WEIGHT_FORMAT | 当EDGE_WEIGHT_TYPE=EXPLICIT时，指定矩阵格式。 | 常用FULL_MATRIX（完整矩阵）或UPPER_ROW（上三角矩阵）。mTSP通常用FULL_MATRIX。 |
EDGE_WEIGHT_SECTION | 显式距离矩阵数据块。 | 按照EDGE_WEIGHT_FORMAT指定的格式，列出所有点对之间的代价（距离、时间、成本）。 |
为什么mTSP常用显式矩阵（EXPLICIT）？因为在mTSP中，点与点之间的“距离”可能不是简单的欧几里得几何距离。它可能是实际道路网络的行车时间、运输成本，或者包含了不同车辆类型、交通状况的复杂权重。这些信息无法用一个简单的坐标和公式（如EUC_2D）来计算，必须预先计算好并明确给出。
2.2 数据文件结构示例
假设我们有一个极其简化的mTSP：1个中心仓库（编号0），4个客户点（编号1-4），由2个旅行商服务。我们需要构造一个包含6个节点的ATSP问题（仓库被复制成出发和返回两个虚拟节点，或采用其他编码方式）。这里为了直观，我们略去具体的编码转换细节，直接看一个EDGE_WEIGHT_TYPE=EXPLICIT的.tsp文件骨架：
NAME: my_mTSP_example TYPE: ATSP DIMENSION: 6 EDGE_WEIGHT_TYPE: EXPLICIT EDGE_WEIGHT_FORMAT: FULL_MATRIX EDGE_WEIGHT_SECTION 999 10 15 20 25 30 5 999 8 12 18 22 10 9 999 7 14 16 18 13 6 999 9 11 22 17 10 8 999 5 25 20 15 10 6 999 EOF在这个6x6的矩阵中，999通常代表无穷大或一个非常大的数，表示“禁止通行”或“自循环”。矩阵的第i行第j列的值表示从节点i到节点j的代价。构建这个矩阵，是解决实际mTSP问题中最耗时、也最需要业务知识的一步。
提示：对于大规模问题，手动编写矩阵不现实。你需要用编程语言（Python、C++等）根据你的业务逻辑计算代价，并按照TSPLIB格式生成数据文件。这是将你的实际问题“翻译”给LKH理解的核心环节。
3. 配置LKH参数文件（.par）：从默认到调优
有了问题数据文件（如my_mTSP.tsp），接下来就需要告诉LKH如何求解。这是通过一个参数文件（通常以.par结尾）来实现的。LKH自带了一些示例（如whizzkids96.par），我们可以在此基础上修改。
3.1 核心参数详解
一个典型的.par文件包含一系列参数 = 值的键值对。以下是针对mTSP求解需要重点关注和调整的核心参数：
PROBLEM_FILE = my_mTSP.tsp这是最重要的参数，指定你上一步准备好的问题数据文件的路径。RUNS = 10指定求解器独立运行的次数。每次运行从一个随机构造的初始解开始。由于LKH是启发式算法，多次运行能增加找到更好解的概率。对于复杂问题，可以适当增加（如50-100次）。MAX_TRIALS = 1000每次RUN中，局部搜索尝试改进当前解的最大次数。这个值越大，单次搜索越充分，但耗时也越长。对于DIMENSION很大的问题，需要调高。MOVE_TYPE = 5指定局部搜索中使用的k-opt移动类型。可选5, 4, 3, 2。MOVE_TYPE=5允许最复杂的边交换（5-opt），搜索能力最强，但每一步计算量也最大。通常保持默认值5即可，除非问题规模极大，为了速度可考虑降为4或3。SEED = 1234随机数生成器的种子。固定种子可以确保实验的可重复性。如果你想获得不同的求解结果进行对比，可以改变这个值或使用系统时间。OPTIMUM = 378032已知的最优解值。如果已知，填写这个值可以帮助求解器提前终止（当找到的解等于或优于该值时），并计算最优间隙（Gap）。如果未知，可以将其设为一个非常大的数，或者直接不设置此参数。TOUR_FILE = best_tour.txt求解结束后，将找到的最好路径（旅行顺序）输出到这个文件。
3.2 一个针对mTSP调优的参数文件示例
基于默认的whizzkids96.par，我们可以创建一个更适应我们需求的版本：
PROBLEM_FILE = ../data/my_complex_mTSP.atsp RUNS = 50 MAX_TRIALS = 5000 MOVE_TYPE = 5 SEED = 2024 # OPTIMUM = 已知最优解 (可选) TOUR_FILE = ../results/best_tour_for_mTSP.txt参数调优经验谈：
RUNSvsMAX_TRIALS：这是一个权衡。如果问题非常复杂，单次搜索难以深入，那么增加MAX_TRIALS可能比单纯增加RUNS更有效。我的策略是先设置一个中等大小的MAX_TRIALS（如维度*10），然后通过多次RUNS来利用随机性。- 内存与时间：LKH非常高效，但对于维度数万、且使用
FULL_MATRIX显式矩阵的问题，内存占用会很高。确保你的服务器有足够RAM。 - 并行化：LKH本身是单进程的。但你可以写一个简单的Shell脚本，用不同的
SEED同时启动多个LKH进程，最后取所有结果中的最优解，这是一种朴素的并行策略。
4. 运行求解与结果深度解读
配置好参数文件后，在终端中运行求解器就非常简单了：
./LKH my_mTSP.par求解过程会在终端输出大量迭代信息。运行结束后，我们需要重点关注两个地方的输出：一是终端屏幕最后打印的汇总统计信息，二是TOUR_FILE指定的路径文件。
4.1 理解输出统计信息
我们以原始内容中的一段输出为例，进行拆解：
Successes/Runs = 10/10 Cost.min = 378032, Cost.avg = 378032.00, Cost.max = 378032 Gap.min = 0.0000%, Gap.avg = 0.0000%, Gap.max = 0.0000% Trials.min = 1, Trials.avg = 5.8, Trials.max = 29 Time.min = 0.14 sec., Time.avg = 0.30 sec., Time.max = 0.61 sec. Time.total = 6.39 sec.Successes/Runs:10/10表示10次独立运行都“成功”了。这里的成功通常指算法正常完成搜索，并不一定代表找到了最优解。Cost系列: 这是解的质量的核心指标。Cost.min: 所有运行中找到的最好解的目标函数值（总路径成本）。这是我们最关心的数字，值越小越好。Cost.avg和Cost.max: 平均解和最差解的成本。它们反映了算法的稳定性。如果min、avg、max相差很大，说明解的质量波动大，算法可能对初始解敏感，或者问题本身有很多局部最优解。
Gap系列:最优间隙，衡量找到的解与已知最优解（OPTIMUM参数）或算法估计的下界的差距。- 计算公式通常为
(FoundCost - OPTIMUM) / OPTIMUM * 100%。 Gap.min = 0.0000%是一个理想状态，意味着至少有一次运行找到了已知的最优解（或达到了下界）。如果OPTIMUM未设置，Gap的计算可能基于其他下界，此时Gap不为0是正常的。- Gap是评估解质量的关键。在工业场景中，我们可能不追求严格的数学最优（那可能计算时间过长），而是追求一个“足够好”的解，比如Gap在1%或0.5%以内。
- 计算公式通常为
Trials系列: 每次运行中实际进行的trial（试验/迭代）次数。它反映了搜索的深度。如果Trials.avg远小于你设置的MAX_TRIALS，说明算法可能很早就收敛了，你可以尝试增大MAX_TRIALS看看能否找到更好的解。Time系列: 计算时间。Time.total是总耗时。这对于评估算法效率和进行工程排期至关重要。
4.2 分析路径输出文件
TOUR_FILE（如best_tour.txt）保存了对应Cost.min的那条最优路径。文件内容通常如下：
NAME: my_mTSP_example TYPE: TOUR DIMENSION: 6 TOUR_SECTION 1 4 2 5 3 6 -1 EOF这里的数字序列代表了节点的访问顺序。如何将这个序列解读回原始的mTSP路线？这取决于你最初是如何将mTSP编码成TSP的。如果你使用了“仓库复制”的编码方式，那么序列中的特定节点（如-1之前的节点）可能对应某个旅行商的结束。你需要根据编码规则，写一个后处理程序，将这个单一的节点序列“解码”成多个旅行商的独立路线。
例如，假设我们采用了一种常见的编码：节点1是旅行商A的起点，节点4是旅行商A的返回点/旅行商B的起点，那么上面的序列可能被解读为：
- 旅行商A路线：仓库 -> 节点2 -> 节点5 -> 仓库
- 旅行商B路线：仓库 -> 节点3 -> 节点6 -> 仓库
解码是获得最终可用方案的必要步骤，也是将LKH求解结果与你的业务系统对接的桥梁。
5. 实战：调整策略与高级技巧
当你跑通基础流程后，下一步就是针对具体问题优化求解效果。这里分享几个从实战中总结的策略。
5.1 当结果不理想时，如何调整？
- 检查
Gap：如果Gap很大（比如>5%），首先确认OPTIMUM设置是否合理。如果未知，可以尝试多次运行，观察Cost.min是否稳定。如果不稳定，大幅增加RUNS（比如到200）和MAX_TRIALS（比如到维度*50）。 - 调整
MOVE_TYPE：对于规模特别大（>10000点）的问题，将MOVE_TYPE从5降到4或3，能显著加快单次迭代速度，从而允许你在相同时间内进行更多RUNS，有时反而能通过增加随机性找到更好的解。 - 修改初始解构造策略：LKH默认使用随机初始解。你可以通过
INITIAL_TOUR_FILE参数提供一个更好的初始解（例如，用最近邻法、插入法等快速启发式算法生成的解），这能为局部搜索提供一个更高的起点。 - 审视问题编码：最大的瓶颈可能在于mTSP到TSP的编码方式。不同的编码（如基于流量的模型、复制仓库法）对LKH的求解难度影响巨大。如果可能，尝试文献中不同的编码方案。
5.2 处理带约束的mTSP
标准LKH求解的是无约束的mTSP。但实际问题总有约束，如车辆容量、时间窗、最大行驶距离等。处理这些约束，通常有两种思路：
- 惩罚函数法：在构造距离矩阵时，将违反约束的边权值设置为一个巨大的惩罚值（如前文例子中的
999），使其在优化过程中被自动避免。这种方法简单，但需要谨慎设置惩罚值，太小约束无效，太大会扭曲搜索空间。 - 两阶段法/启发式修复：先用LKH求解无约束问题，得到一个总成本较低的路径，然后设计一个后处理算法，对这个路径进行调整以满足约束（如交换客户点、拆分过长路径）。这通常需要定制化开发。
5.3 集成到应用系统中
对于需要频繁求解mTSP的生产环境（如每日配送排班），将LKH封装成服务是更佳选择。你可以参考一些开源项目，例如用C++编写一个包装器，通过管道或内存直接传递问题数据和参数，并解析返回的路径。这样避免了频繁的文件读写，效率更高。核心是理解LKH的输入输出接口，然后用你的业务逻辑去驱动它。
最后，别忘了利用好社区资源。TSPLIB官网提供了大量标准测试案例，可以用来验证你的配置是否正确。GitHub上也有不少集成LKH的项目，阅读它们的代码能给你带来很多实现上的启发。解决路径优化问题，一半是技术，一半是对业务本身的理解。LKH给了你一把锋利的剑，但如何挥剑，还得看你对自己战场的洞察。
