先交代一下背景。我这次调研的起因很实际某仓储项目里需要给一台搬运机器人规划一条能覆盖十几个拣货点的最优路径一开始我下意识就想到用来求解器硬解结果发现规模稍微涨一点就失控。后来索性把多点路径规划算法这条路从精确解一路梳理到神经组合优化顺手把整个选型思路和踩坑过程整理成了一份内部笔记。今天这篇文章就是把那份调研笔记重新写成一份可以照着用的完整版适合正在做路径规划、任务调度或者打算用深度学习来解组合优化问题的人参考。1. 这次调研想回答的三个问题多点路径规划本质上就是著名的旅行商问题TSP以及它的各种变体给定一批点找一条经过所有点且每个点只经过一次的最短回路。别看问题描述简单它却是典型的NP-hard问题规模稍大就没办法暴力枚举。工程上更常见的其实是带约束的变体比如带时间窗、带容量限制、有多个机器人同时调度这类问题在快递配送、仓储搬运、巡检路线、芯片制造流程里到处都是。调研围绕的核心是三件事。第一不同规模的问题到底用什么算法。n20、n100、n1000这三档规模看起来只是数字不同实际对应的解法完全不是一个物种。第二求解速度和最优性之间怎么权衡。有些场景要求每日亿级查询实时响应有些场景则允许离线算一晚上两者对算法的需求截然不同。第三神经组合优化到底能不能打。最近几年这个方向几乎是顶会常客标题动辄逼近最优解但真实工程里它离可用还有多远必须亲手跑过才有体感。我会先梳理精确解家族这部分是后面所有方法的对标基准。然后过渡到启发式方法它们才是工程界真正的主力。最后重点拆解神经组合优化的原理和实战表现。读完这篇文章你应该能直接给一个具体项目选择合适的算法组合。2. 精确解路线从动态规划到分支切割的能力边界2.1 先确保所有最优都有可对照的基准精确解的定义是不靠运气、不靠随机给出严格最优解。它最大的价值不是实际工程里大规模使用而是给所有近似算法提供一个离最优有多远的标尺。很多人在调研初期忽略这一步直接拿启发式算法互相比较结果根本无法判断哪个方法质量更好因为连最优解都不知道。我在调研里维护了一张小规模的基准表从随机生成的点集里取n10到n100的若干组分别用精确解、启发式、神经方法跑出路径长度再统一比差距。这张表后面所有算法的评估都依赖它。2.2 状态压缩动态规划n24以下的最优答案经典的状态压缩DP思路是设dp[S][i]表示已经走过的点集合为S当前停在点i时的最短路径长度转移时枚举下一个点j只要j不在S里就尝试更新dp[S|1j][j]。初始状态是dp[1start][start]0目标是min(dp[(1n)-1][i]dist[i][start])。这个算法的时间和空间复杂度都是O(2^n * n^2)n20时大概需要上千万次运算内存勉强能塞进几GBn30时状态数就到十亿量级单纯靠状态压缩DP基本没戏了。所以在调研中我把DP定位为小规模标尺它确实能给出严格的TSP最优路径但仅适合做基准验证和玩具场景。不过这个DP思路本身很有价值后面的神经组合优化里很多模型借鉴了它逐步构造解的思想。DP把问题看成步骤间的状态转移这个视角对理解自回归策略网络非常有帮助。2.3 分支切割与整数规划求解器中规模的主力军当n来到50到500这一档精确解的主流方案是分支切割branch-and-cut。它把TSP建模成整数规划先解线性松弛再逐步加入割平面把非整数解排除掉配合分支定界不断收紧上下界。工业级求解器对这一套做了大量优化包括预处理、启发式初始解、切割池管理等。我用某测试集做了实验n50的随机均匀点集求解器通常几秒内出最优解n100大概需要十几分钟n200时时间不可控偶尔能收敛、偶尔卡住几小时。这说明求解器作为精确工具的能力边界大致在n200以内具体取决于点集分布——有聚类结构的问题更容易切割反而比均匀随机点好解。这一层的结论是精确解可以直接用于中小规模的离线规划也适合作为评估基准但不要指望它在实时场景或大规模任务里承担主要计算负载。2.4 精确解的隐性成本建模能力和问题变化有一点容易被忽略求解器的效率高度依赖建模质量。同样是带时间窗的问题不同的变量定义和约束写法能让求解时间差出几十倍。甚至同一个数学形式上等价的模型仅仅改了变量上下界分支切割的裁剪效率就可能完全不同。我实际体验是完全不调优直接用求解器解n150的带时间窗TSP经常跑到超时但只要调整一下变量定义、加两条有效不等式很多实例秒出最优。这个细节让精确解方法在实际工程里的门槛变得更高不是调个包就行而是需要懂一些整数规划的建模技巧。3. 启发式方法工程界真正的主力军3.1 为什么精确解够好却不够用精确解质量当然好但它有两个工程上致命的弱点一是规模天花板明显实时或者近实时场景根本等不起二是对问题变化敏感换个约束重写模型又要重新调。启发式方法虽然不保证最优但胜在速度快、实现简单、适用范围广。我调研早期常犯一个错任由求解器跑一两个小时总觉得多等一会儿就能出最优。后来发现在很多普通工程场景里一个优秀启发式算法跑3秒给出比最优差0.5%的解价值远超两小时给出的最优解。关键问题变成如何在时间预算内把解的质量尽量推高。3.2 从贪心到2-opt再到分层优化最简单的贪心最近邻算法复杂度只有O(n^2)但解的质量波动很大对初始起点敏感。真正让解质量有质变的是局部搜索。经典的2-opt操作是检查路径中两条边(i,i1)和(j,j1)如果交换端点能缩短总长就翻转中间这一段路径。复杂度是O(n^2)的边对枚举每次翻转后继续直到没有可改进的2-opt邻域为止。实际中2-opt对随机初始解能带来巨大质量提升大约能把初始路径缩短到最优的10%到20%以内。接着再跑3-opt或者Or-opt这类更大范围的邻域搜索又能进一步逼近最优。一个非常实用的模式是贪心生成初始解 2-opt加3-opt迭代改进 其他扰动操作跳出局部最优。3.3 LKH经典算法为什么至今无人能完全替代讨论TSP的启发式方法就绕不开LKH它是Lin-Kernighan启发式的改进版至今仍是许多标准测试集上的冠军级选手。它的核心是动态改变搜索邻域的大小通过一系列变换的组合来决定是否接受新解同时用了很聪明的候选边集合减少搜索量。我拿标准测试集里的几个实例做过对比LKH在n1000的随机均匀问题上通常几秒到几十秒内给出和已知最优解差距在0.1%以内的路径。这个表现至今让大多数新方法都很难直接正面击败它。不过LKH也不是万能药。它需要调参数比如runs、max_candidates、initial_period它的代码风格也比较传统二次开发和嵌入到现代系统里都有适应成本而且它的优秀依赖TSP问题特定的搜索结构换到带复杂约束的变体上效果会明显下降。即便如此我仍然建议每个做路径规划的人好好研究它它内部那套候选边和链式移动机制对设计自己的局部搜索算法很有启发。3.4 元启发式大礼包模拟退火、遗传算法、蚁群算法怎么选元启发式提供了一个更高层面的框架怎么从局部最优的陷阱里逃出来。几种常见选择我横向对比过模拟退火思路最简单温度高时以较大概率接受差解温度降下来后趋于稳定。它的超参数只有初温、末温、降温速率、内循环次数实现起来几乎不挑语言我建议作为默认起步方法。遗传算法通过编码路径、交叉、变异来搜索解空间效果很大程度上取决于编码设计TSP里常用的路径编码交叉操作实现起来并不容易很容易产生非法路径。适合问题本身已经有成熟编码表达的情况。蚁群算法用信息素浓度引导后续蚂蚁构建解很适合并行加速但收敛速度和参数敏感性都让它在某些问题上显得很别扭。我的建议是如果没有特别理由先用模拟退火作为兜底在这个基础上叠加局部搜索真正需要考虑复杂的约束、多目标、动态变化时再研究遗传算法那一套。不要一上来就选最复杂的元启发式调度问题最怕过度设计。4. 神经组合优化把解题策略交给网络自己学4.1 一个直觉问题为什么深度网络能参与解TSP第一次听到用神经网络解TSP的人几乎都会有同样的疑惑TSP是离散的组合优化问题神经网络擅长的是连续函数拟合这两者怎么会有关系答案藏在把解题顺序建模成序列生成这件事上。一个TSP回路可以看成一条点的序列而生成一个序列恰好是自回归模型最擅长的事。你可以把输入视作一张点集图每个节点带有坐标特征神经网络通过编码器把所有节点信息压缩进向量表示再由解码器一步步决定下一步应该访问哪个节点。网络本身没在优化路径长度它是在学习一种如何根据当前状态选下一个节点的策略。这套思路最早可以追溯到用指网络做凸包问题之后很快迁移到TSP。核心观点是与其手工设计复杂的搜索规则不如让网络从大量求解实例里归纳一种通用的构造策略。4.2 图编码器为什么GNN比MLP天然适合TSP早期工作直接把坐标拼成向量丢进循环网络或全连接网络效果一般。后来大家发现TSP的点集天然是图结构——点的相对位置、点之间的相互作用对决策至关重要而图神经网络正好能通过消息传递机制让每个节点聚合邻居的特征信息和空间关系。我用真实数据对比过同样规模下图注意力编码器比单纯的MLP编码器泛化能力强很多尤其是在训练时没见过的规模上。原因在于图网络具有置换等变性点集顺序打乱后图表示基本保持一致这非常贴合TSP路径与点的编号顺序无关的对称性。另一个关键因素是注意力机制。TSP里当前在哪、还有哪些点没去这两个信息需要被高效整合自注意力能让每个节点根据全图信息自行调整表示权重。现在主流模型基本都以Transformer架构作为编码器主干。4.3 自回归解码与REINFORCE训练一个完整的训练闭环解码阶段通常采用自回归方式编码器给出所有节点的特征表示后解码器维护一个当前部分解每一步从还没访问的节点集合中采样一个节点加入路径。这个选择的过程可以看成在未访问节点上做一个带掩码的多分类输出概率训练目标就是最小化路径长度的期望。用强化学习训练这类模型是当前主流做法。以REINFORCE为例它对一个实例采样若干条完整路径计算它们的长度作为奖励信号然后通过策略梯度更新网络参数。如果直接用监督学习需要先跑很多精确解或优秀启发式解来构造标签成本高且上限受制于教师解的质量强化学习只要给出路径长度作为代价就能自我进化一步步靠近最短路径。我复现过这类训练流程最大的体感是训练稳定性需要精心维护。基线设计很关键——常见做法是用一个贪心解码出的路径长度作为基线或者用指数移动平均长度否则方差太大会导致训练崩溃。还有一个坑是掩码逻辑解码过程中忘记屏蔽已访问节点模型就学会了原地重复绕圈。4.4 当前的研究分支学习搜索、扩散模型与大模型辅助纯粹的自回归构造式方法只能说是神经组合优化的第一代。最近的调研让我觉得有几个方向更值得关注。第一个是学习式搜索。不是让网络直接从零构造路径而是让它作为局部搜索或扰动策略的辅助工具。比如用网络决定如何破坏并重建解配合大邻域搜索框架把人的启发式规则替换成学出来的破坏/修复策略这类方法在带约束问题上往往比纯构造式方法质量更高。第二个是扩散模型。扩散模型的从噪声逐步去噪的过程天然有点从模糊到精确的味道最近已经有人把它用到TSP等离散组合问题上可以通过多次扩散迭代逐步细化解。第三个是大语言模型辅助。不是直接让大模型解TSP而是让它做问题理解、启发式规则生成、解的解释与验证。比如面对一个带复杂业务约束的路径规划任务先让大模型帮忙把约束变成伪代码再交给传统优化引擎求解。这个分工在工程上更现实也是我认为短期内最可能落地的方向。4.5 神经方法的真实局限泛化、约束与训练成本再漂亮的模型也有落不了地的时候。神经组合优化目前最大的两个硬伤第一是泛化能力。训练时用n50的数据模型在n50上表现不错但直接丢到n100解质量通常会明显下降n200基本就不太能用。虽然有一些办法如注意力掩码、多尺度训练图拉近差距但依然没有彻底解决。第二是约束处理。TSP只有每个点只走一次这个简单约束神经方法相对容易学。一旦加上时间窗、容量、多车协同等复杂约束模型要么需要大量定制化设计要么直接靠惩罚函数硬来效果都不理想。训练成本也不能忽视。训练一个能稳定解n100的模型普通显卡上跑几十个小时是常态还需要精心调各种超参数。相比之下LKH只要下载编译就能在几分钟内给出质量极高甚至更好的解。这让我对神经方法是否会在近期取代传统精确或启发式方法持保留态度。这并不是说神经方法没有价值。它在很多场景里的核心价值不是解质量更好而是推理速度快。一个训练好的模型只需要一次前向传播就能生成路径在需要毫秒级响应的动态调度场景里非常有吸引力。同时模型的表示能力可以直接复用——学会了n50的几何关系迁移到相似分布但规模稍大的问题上是有希望的只是目前做不到无损迁移。5. 选型决策与工程落地实践5.1 一张按需求和规模维度整理的选型参考表调研到这一步我把得到的结论整理成了一张决策表。它不追求面面俱到但可以成为绝大多数项目开始时的起点场景特征首选方案备选方案备注n≤20需要严格最优状态压缩DP求解器做基准测试时的黄金标准20n200离线计算求解器分支切割LKH建议给求解器设定时间上限n200离线计算LKH自定义大邻域搜索质量与速度的平衡点实时/在线决策神经方法局部搜索精修带时间预算的模拟退火神经模型前向推理速度快复杂约束多用元启发式框架内嵌局部搜索LKH变体惩罚项不建议直接用纯深度模型硬解需要尽量接近最优解LKH多次运行取最优求解器限时逼近可以用并行进程提升效率这张表不是说某种算法一定优于另一种而是提醒选型前先想清楚场景的约束和实时性。路径规划的第一原则是先确定问题边界再考虑算法。5.2 一个贯穿始终的混合方案构造改进精确冲刺工程上我强烈推荐一种混合策略它几乎适用于大多数中等规模问题。第一步用贪心或最近的插入法快速构造一条初始路径第二步用2-opt和3-opt做局部改进直到收敛第三步有时间余量时再把当前解喂给求解器作为初始上界让分支切割在更紧的上下界里继续冲刺最优。这个三段式方案看起来简单却非常有效。原因是它把算法各自的优势集中了起来贪心快但不精局部改进能在极短时间内把解质量拉到很高水平精确求解器在上界很好时切割效率显著提升。我在多个实验中都观察到一个现象不提供初始解时求解器可能卡在几十分钟没有进展给了高质量初始解后很多问题几分钟内就收敛了。5.3 我踩过的几个坑以及怎么避开这一路调研下来我总结了不少经验挑几个最痛的说说。第一个坑是无脑调大求解器超时上限。一开始我以为只要给足时间精确解一定能出最优结果发现n300以上的很多实例限时24小时还是打不通。后来改为设一个可接受的gap阈值比如要求最优性差距在1%以内求解器能迅速给出高质量上界实用价值高得多。第二个坑是神经模型训练和评估分布不一致。我第一次训练时只用了均匀随机分布的点上线后发现实际业务里的点经常聚成几个簇模型在簇状分布上表现骤降。后来我在训练数据里混合了均匀、聚类、带少量异常点的多种分布泛化能力才有明显改善。如果你的数据分布是长尾的千万别把所有训练数据合成同一个简单分布。第三个坑是忽视约束对搜索空间的影响。我之前在某个模拟项目里把时间窗约束直接变成惩罚项丢给LKH参数调了好几天结果还是经常违反硬约束。后来改成用专门的约束处理方法把时间窗检查嵌入到解的评估函数中违反约束的路径不只给惩罚还直接禁止部分明显无效的移动效果才稳定下来。处理组合优化问题时约束最好是硬编码进搜索逻辑而不是指望惩罚项力挽狂澜。第四个坑是把神经方法当成银弹。我见过不止一个项目花了两周训练深度学习模型解质量还是不如跑3秒的LKH最后老老实实回到传统启发式加工程优化。神经方法适合的场景是需要极快推理速度、问题分布相对稳定、约束相对简单。如果这三个条件不满足优先考虑传统方法。5.4 如果从零开始做一次算法调研我会怎么做复盘整个调研流程我认为最有价值的不是学会某个具体算法而是实验设计的系统性。以后的任何相关调研我大概率还会沿用下面这套流程先把问题写成规范的形式化定义包括目标函数、约束条件、输入输出和性能指标接着确定基准测试集覆盖多种规模、多种分布、多种约束密度然后用精确求解器建立最优性标杆再筛选两到三个有代表性的启发式方法作为基线最后测试神经组合优化方法重点看它们和基线的差距而不只看模型论文里的数字。另外强烈建议把实验代码和结果结构化地记录在同一个仓库里包括随机种子、运行时间、超参配置和每次运行的最优值。没有这套实验纪律多个算法之间很难公平比较。6. 留给后来者的几条实用建议如果这篇文章只能留下几句话我希望是下面这些在真实项目中反复验证过的经验。第一先跑通一个小规模基准再谈复杂算法。n20时跑一遍DP和一遍LKH你就知道最优长什么样子、近似算法差距在哪里后面所有判断都有了锚点。第二不要一上来就放弃经典算法。LKH和求解器这类工具在质量和稳定性上仍然非常能打大多数项目的需求它们都能覆盖。神经组合优化的价值要在充分理解问题后才能判断否则很容易陷入模型运行得很好但不知道好在哪、也不知道为什么好的窘境。第三工程上绝大多数业务约束才是主要矛盾。同样的点集加上时间窗、多车、容量限制后问题的复杂度会成倍增长。算法本身的改进通常只带来几个百分点的提升而正确建模约束、设计候选择策略往往带来数量级的改进。第四如果真要上神经方法先从构造式模型入手。不要直接追最新的扩散模型或大模型方案先把图编码器加自回归解码加REINFORCE这条链路跑通你才会真正理解这类方法的优势和天花板在哪里之后要改造成搜索辅助或扩散模型也有完整的技术底子。第五保持对解的怀疑。任何算法给出的最优都只是在这个算法视角下的最优换一个随机种子、换一种点分布结论可能就变了。多跑几次、多看分布、多检验约束满足情况才能真正确认一套方案是否可靠。我在实际项目里最后落地的方案通常不是某一种单一算法而是LKH做离线批量优化 神经网络做在线快速预测 求解器定期校准最优基准这种三层组合。每次有人问我到底哪个算法最好我都会反问一句你的场景允许跑多久你的点分布稳定吗你的约束硬不硬把这三个问题想清楚算法选型其实已经完成了一大半。