G-LNS: 用于基于大语言模型的自动启发式设计的生成式大邻域搜索#

2.1 自动启发式设计#

自动启发式设计（AHD）旨在自动发现组合优化问题（COP）的高性能启发式（Burke等，2013；Stützle & López-Ibáñez，2018；Chen等，2025b）。令$\mathcal{I}$表示实例空间，$\mathcal{S}$表示解空间。启发式$h \in \mathcal{H}$是离散算法空间$\mathcal{H}$内的一个映射$h: \mathcal{I} \to \mathcal{S}$。AHD的目标是找到最小化目标分布$\mathcal{D}$上期望目标值的启发式$h^*$：

$h^* = \arg \min_{h\in \mathcal{H}}\mathbb{E}_{I\sim \mathcal{D}}\left[f(h(I)\mid I)\right]. \quad (1)$

虽然AHD能够系统性地搜索算法逻辑，但搜索空间的表达能力取决于启发式的参数化方式。许多现有方法将搜索限制在预定义模板内，限制了引发搜索动态根本性变化的能力。本文致力于将设计空间从固定启发式形式扩展到结构自适应的搜索算子。

2.2 大邻域搜索#

大邻域搜索（LNS）是一种通过迭代破坏-修复操作探索解空间的元启发式方法（Shaw，1998）。给定一个解$x$，破坏算子$d$移除一部分分量（由破坏率$\epsilon$控制），产生一个部分解$x_{\mathrm{partial}} = d(x)$。然后修复算子$r$重构一个完整解$x' = r(x_{\mathrm{partial}})$。

为了平衡探索与利用，LNS通常采用模拟退火（SA）接受准则（Henderson等，2003），其中非改进解可能以随时间降低的概率被接受。LNS的性能关键取决于$d$和$r$之间的耦合：有效的算子必须引入针对性的结构破坏，同时允许高效的重构。设计这种互补的算子对仍然是一个核心挑战，并推动了自动化。

2.3 问题形式化#

我们将LNS算子的自动设计形式化为一个在离散代码空间上的优化问题。令$\Theta_{d}$和$\Theta_{r}$分别表示实现破坏和修复算子的可执行代码空间。策略$\pi = (d,r) \in \Theta_{d} \times \Theta_{r}$通过在实例$I \sim \mathcal{D}$上运行具有内在随机性$\xi$的LNS算法$\mathcal{A}$来评估。$\pi$的期望性能定义为

$J(\pi) = \mathbb{E}_{I\sim \mathcal{D},\xi}\big[f(\mathcal{A}(I,\pi ;\xi)\mid I)\big], \quad (2)$

总体目标是找到

$\pi^{*} = \arg \min_{\pi \in \Theta_{d}\times \Theta_{r}}J(\pi). \quad (3)$

2.4 相关工作#

最近的工作将大语言模型（LLM）整合到演化框架中用于自动启发式设计（Novikov等，2025；Chen等，2025a）。诸如FunSearch（Romera-Paredes等，2024）和EoH（Liu等，2024b）等方法使用LLM作为变异算子，基于先前的实现和性能反馈生成启发式代码，形成思维-代码共同演化范式，提高了在大离散算法空间中的探索效率。然而，大多数现有方法依赖固定的算法模板，专注于构造式启发式或预定义局部搜索框架内的参数调优（Ye等，2024；Zheng等，2025），因此很大程度上忽视了邻域算子的结构设计。相比之下，我们的工作目标是自动生成紧密耦合的破坏和修复算子，使LLM能够在结构层面重塑搜索过程。附录A中有进一步讨论。

3.1 G-LNS框架概述#

我们提出G-LNS，一个自动化发现大邻域搜索（LNS）中高性能破坏和修复算子的框架。G-LNS将启发式设计形式化为一个在算法结构上的演化过程，其中大语言模型（LLM）充当智能变异算子，探索超越固定启发式模板的算法逻辑空间。这种演化形式需要一个可靠的机制来评估新生成算子的质量。

为此，我们实例化LNS算法并采用受自适应大邻域搜索（ALNS）（Ropke & Pisinger，2006）启发的自适应评分机制，通过测量每个算子对优化性能的贡献来提供定量适应度信号。如图2所示，整体方法包括四个阶段：初始化、评估、种群管理和演化。

图2. G-LNS框架的整体工作流程。该框架以循环方式运行，包含四个阶段：（1）初始化，其中双种群($\mathcal{P}_d,\mathcal{P}_r$)用领域专家知识和LLM生成的算子进行种子填充；（2）评估，其中算子对通过自适应LNS过程动态选择并评分；（3）种群管理，对低性能算子进行排序和修剪；（4）演化，利用LLM执行变异和交叉策略，用新的启发式补充种群。

3.2 初始化#

为了促进这些相互依赖组件的共同演化，G-LNS建立了一个双种群架构（Potter & De Jong，1994），为破坏算子$(\mathcal{P}_d)$和修复算子$(\mathcal{P}_r)$维护独立的存储库，每个容量为$N$。初始化阶段首先注入一组紧凑的经典领域专家启发式作为种子。例如，在TSP/VRP任务中，我们对$\mathcal{P}_d$使用随机移除和最差移除，对$\mathcal{P}_r$使用贪婪插入。这些种子有双重目的：它们提供基础的搜索能力，并作为上下文示例（Brown等，2020）使LLM与特定任务逻辑对齐。为了完全填充池（当种子数量$< N$时），我们使用初始化动作（对破坏算子记为$i_1$，对修复算子记为$i_2$）。通过$i_1, i_2$，提示LLM构思新颖的算法逻辑并将其转化为可执行的Python代码，从而从一开始确保搜索空间的多样性。（关于提示工程的详细信息见附录D.1。）

同时，我们初始化三个度量结构来指导演化过程：(1) 全局适应度分数（$F = \{F^d, F^r\}$，其中$F^d, F^r \in \mathbb{R}^N$）：初始化为零，这些向量跟踪$\mathcal{P}_d$和$\mathcal{P}_r$中每个算子的累积性能，用于种群管理。(2) 协同矩阵（$\mathbf{S} \in \mathbb{R}^{N \times N}$）：初始化为零，该矩阵记录特定对$(d_i, r_j)$的协作性能，以指导联合交叉。(3) 自适应权重（$W = \{W^d, W^r\}$，其中$W^d, W^r \in \mathbb{R}^N$）：初始化为全1，这些权重仅在每个评估回合内用于调节轮盘赌选择概率。

3.3 评估阶段#

该阶段的目标有两个：量化每个算子对种群管理的个体贡献，并捕获破坏和修复算子之间对协同演化的耦合有效性。考虑到LNS的固有随机性，我们采用多回合评估机制。

我们进行$K$个独立的评估回合。每个回合从一个随机初始解$x_0$开始，执行$T$次迭代。重要的是，自适应权重$W$在每个回合开始时重置为1以确保独立探索，而全局适应度$F$和协同矩阵$\mathbf{S}$在所有$K$个回合上累积统计量，以获得平滑单回合随机性的鲁棒性能度量。

自适应选择。在每个回合的每次迭代$t$中，我们根据当前权重选择破坏算子$d_i$和修复算子$r_j$。选择概率$P(d_i)$（以及类似的$r_j$）遵循轮盘赌机制：

$P(d_i) = \frac{w_i^d}{\sum_{k = 1}^N w_k^d} \quad (4)$

评分与更新。选定的对$(d_i,r_j)$应用于当前解以生成邻域解$x^{\prime}$。其接受和相应的奖励$\sigma$按层次确定。如果$x^{\prime}$改进了全局最优，则更新$x^{*}$和$x_{\mathrm{curr}}$并分配$\sigma_1$。如果$x^{\prime}$仅改进了当前解，则更新$x_{\mathrm{curr}}$并分配$\sigma_2$。对于变差的解，接受由Metropolis准则控制；如果接受，则更新$x_{\mathrm{curr}}$并给予奖励$\sigma_3$。否则，解被丢弃并分配最低奖励$\sigma_4$。形式上：

$\sigma = \left\{ \begin{array}{ll}\sigma_1, & \mathrm{if} f(x^{\prime})< f(x^{*})\\ \sigma_2, & \mathrm{if} f(x^{\prime})< f(x_{\mathrm{curr}})\\ \sigma_3, & \mathrm{if} x^{\prime} \mathrm{is accepted by SA}\\ \sigma_4, & \mathrm{otherwise} \end{array} \right. \quad (5)$

基于$\sigma$，我们执行三个不同的更新：

1. 自适应权重更新：为了指导当前回合内的搜索方向，使用平滑因子$\lambda$动态更新所选算子的权重：

$w_i^d\leftarrow \lambda w_i^d +(1 - \lambda)\sigma ,\quad w_j^r\leftarrow \lambda w_j^r +(1 - \lambda)\sigma \quad (6)$

2. 全局适应度累积：为了评估算子在后续种群管理阶段的整体质量，我们将奖励累积到全局适应度分数$F$中：

$F(d_i)\leftarrow F(d_i) + \sigma ,\quad F(r_j)\leftarrow F(r_j) + \sigma \quad (7)$

3. 协同记录：为了识别高性能的结构耦合，我们更新协同矩阵中相应的条目：

$\mathbf{S}_{ij}\leftarrow \mathbf{S}_{ij} + \sigma \quad (8)$

$\mathbf{S}_{ij}$中的高值表示破坏算子$i$和修复算子$j$具有互补逻辑，这将在协同联合交叉阶段中被利用。

3.4 种群管理#

随着演化过程的推进，算子池$\mathcal{P}_d$和$\mathcal{P}_r$不可避免地会积累次优或冗余的启发式。保留这些低效算子限制了种群容纳新的、可能更优逻辑的能力。因此，在每$K$个评估回合完成后，我们根据累积的全局适应度$F$对两个种群中的算子进行排序。系统然后从每个池中修剪底部的$M$个算子，从而为后续LLM驱动的演化阶段腾出种群槽位，同时保留高性能的精英。

3.5 LLM驱动的演化机制#

该阶段利用LLM的代码推理能力来补充管理期间空出的种群槽位。我们将其框架化为算法空间内的启发式搜索过程。为了填充$M$个空槽，我们从三种有针对性的演化策略中随机抽样，确保局部改进和结构重组的多样化组合。

• 变异（局部利用）$(m_{1},m_{2})$：变异通过修改从精英池中采样的单个父代算子来专注于局部算法空间内的微调。具体动作根据父代排名自适应调整，以平衡稳定性和创新性：逻辑演化$(m_{1})$应用于排名较低的精英以产生新的探索机制；中间精英随机分配；参数校准$(m_{2})$应用于排名最高的精英以调整超参数（例如随机化比率）以保证稳定性。

• 同质交叉（特征重组）$(c_{1})$：此策略促进同一类型算子之间的信息交换。基于适应度$F$通过适应度比例抽样选择两个父代。提示LLM融合两个父代的逻辑优势，合成一个继承混合特征的新算子（例如，将空间聚类与随机扰动相结合）。

• 协同联合交叉（结构耦合）$(c_{2})$：解决破坏和修复动作之间固有耦合是G-LNS的核心创新。我们选择具有最高累积协同分数$\mathbf{S}$的破坏-修复对。通过基于破坏逻辑条件化修复生成，LLM将该对作为一个统一实体演化，确保修复算子专门为重构破坏算子引入的结构缺陷而定制，从而最大化其协同性能。

鲁棒性保证。为了减轻LLM幻觉的风险，我们实现了预评估过滤器（Chen，2021）。所有生成的算子都在小规模实例集上进行合理性检查（Romera-Paredes等，2024）。只有无错误且满足时间复杂度约束的算子才被接纳进入种群；否则触发重新生成过程。

状态重置。一旦种群完全补充完毕，全局适应度分数$F$和协同矩阵$\mathbf{S}$被重置为零。这确保了新生成的算子在随后的评估周期中与幸存精英处于平等起点，防止历史偏差主导搜索。

4.1 实验结果#

在合成留出实例上的性能。如表1（上半部分）所示，在所有LLM驱动的方法中，G-LNS（我们的方法）在TSP任务的所有问题规模上始终实现最低的最优性差距。对于大规模实例如TSP100和TSP200，我们的框架显著优于Evo-MCTS和迭代MCTS-AHD(ACO)，有效克服了现有AHD方法通常导致超过$10\%$差距的可扩展性挑战。这种卓越性能得益于演化了状态依赖的破坏和修复逻辑，使G-LNS能够优于标准ALNS（详见附录E）。具体来说，它为TSP识别了自适应连续段移除和多样性感知插入，为CVRP识别了渐进式随机-最差移除与上下文感知贪婪插入。与静态规则不同，这些算子基于实时解状态动态调整破坏程度和探索噪声，从而更优地摆脱局部最优。

在CVRP任务上（表1，下半部分），G-LNS在面对复杂的容量约束时表现出卓越的可扩展性和鲁棒性。这些约束通常对传统的构造式启发式构成重大挑战，后者由于其顺序决策的不可逆性而容易陷入局部最优。虽然G-LNS在小规模实例上的表现略低于最优参考解，但随着问题复杂度的增加，其优势变得更加明显。在最大实例（CVRP100/200）上，G-LNS不仅优于所有基于LLM的基线（后者通常显示超过$10\%$的最优性差距），而且还找到了优于OR-Tools求解器提供的解。在约束解空间中的导航能力表明，学到的破坏-修复算子能够成功纠正构造方法无法处理的结构缺陷。（OVRP的详细信息见附录F.1。）

G-LNS在实现卓越解质量的同时，表现出比基准方法显著更高的计算效率。在CVRP实验中，OR-Tools基线为评估批次（64个实例，每个实例5秒）使用320秒的固定预算，而G-LNS在所有问题规模上所需时间显著更少：其500次迭代的总推理时间从CVRP10的仅3.23秒到CVRP200的280.91秒不等。相比之下，另一种迭代方法MCTS-AHD需要更大的计算负担，CVRP10为84.16秒，CVRP200为2407.14秒，使得G-LNS快一个数量级以上。这些结果表明，G-LNS能够找到比标准求解器（后者未能在时间限制内完全收敛，留下$1.27\% - 2.09\%$的差距）和昂贵的迭代启发式都更高质量的解，同时消耗更小的计算预算。

对真实世界基准的鲁棒泛化能力。为了进一步评估G-LNS的跨分布泛化能力，我们将评估扩展到广泛认可的标准基准，包括TSPLib（Reinelt，1991）和CVRPLib（Uchoa等，2017）。这些数据集具有多样的问题分布和规模，与演化中使用的随机实例显著不同。

如附录F.2详述，G-LNS相比最先进的AHD方法（包括强基线EoH-S（Liu等，2025））表现出优越的泛化性能。G-LNS在所有评估数据集上始终实现最低的最优性差距。值得注意的是，在具有挑战性的CVRPLib Set F上，我们的方法将最优性差距从$40.1\%$（EoH-S）降低到$15.9\%$。类似地，在TSPLib上，G-LNS保持了$2.8\%$的低差距，显著优于在未见分布上挣扎的基线。这些结果证实，G-LNS演化的破坏-修复算子捕获了组合问题的内在结构性质，而不仅仅是过拟合训练分布。

4.2 消融研究#

为了验证G-LNS框架中每种演化策略和组件的必要性，我们在TSP50和CVRP50数据集上进行了消融研究。我们将完整的G-LNS作为基线，并与四个退化变体进行比较：

• w/o Mut.（无变异）：排除局部改进策略（即逻辑演化和参数校准）。演化完全依赖于交叉操作，评估微调单个算子的影响。
• w/o Homo.（无同质交叉）：移除融合同一类型算子的机制。新算子仅通过变异或协同配对生成，测试在同一算子类内重组高层逻辑特征的好处。
• w/o Syn.（无协同联合交叉）：解耦破坏和修复算子的演化。它不基于协同矩阵$\mathbf{S}$演化互补对，而是独立处理种群。
• w/o Adapt.（无自适应权重）：在评估阶段禁用自适应LNS评分机制，其中算子以均匀概率选择，以验证动态资源分配的重要性。

此外，为了评估自适应机制的鲁棒性，我们对评分向量$\sigma = \{\sigma_{1},\sigma_{2},\sigma_{3},\sigma_{4}\}$进行了敏感性分析，该向量控制算子权重更新。我们将默认设置与平坦配置（$\{1,1,1,0.1\}$，其中不同成功级别的奖励无法区分）和激进配置（$\{10,5,2,0\}$，放大奖励方差）进行比较，以验证分层奖励系统的必要性。

表2显示G-LNS实现了最低的差距，验证了我们的演化策略。(1) 演化组件：w/o Mut.和w/o Homo.中的显著下降突出了逻辑微调和特征重组的重要性。w/o Syn.中的退化确认了破坏和修复算子之间的结构耦合；独立演化破坏了它们的协同性。(2) 评分机制：w/o Adapt.中的下降验证了反馈循环的价值。值得注意的是，平坦向量比完全移除自适应性表现更差，证明无法区分的奖励会误导搜索。同时，激进设置不如默认设置，证实了平衡的分层奖励系统的必要性。

表2. G-LNS关键组件的消融研究。 每个变体移除一个组件——变异（Mut.）、同质交叉（Homo.）、协同交叉（Syn.）或自适应权重（Adapt.）——以评估其对TSP50和CVRP50解质量的影响。最佳结果以粗体突出。

4.3 收敛性分析#

图3展示了G-LNS的双重性能特征：演化过程中算子质量的逐步提升（图3a）以及最终演化算子在评估期间的快速收敛（图3b）。

演化效率。图3(a)描绘了200代中精英算子的验证性能。我们观察到初始阶段（0-50代）质量快速提升，表明LLM从种子示例中迅速掌握了破坏-修复操作的基本逻辑。随后，曲线表现出稳定的改进趋势（50-200代），框架微调算子逻辑以摆脱局部最优。缩小的方差（阴影区域）表明种群收敛到一组鲁棒的高性能启发式。

求解收敛性。图3(b)比较了G-LNS与代表性基线在CVRP100实例上的收敛行为。可以得出几个关键观察结果：(1) 优越的收敛速度：与标准ALNS和MCTS-AHD(ACO)相比，G-LNS在早期迭代中表现出显著更陡的下降。这表明LLM生成的破坏算子具有更强的结构扰动能力，使搜索能够快速识别解空间中的有希望区域。(2) 超越求解器：G-LNS在前50次迭代内就超过了构造基线的解质量。更重要的是，它最终收敛到优于OR-Tools求解器的解（目标值约13.8对比约14.1）。(3) 计算效率：G-LNS在大约70秒内达到最先进性能，这不仅是分配给OR-Tools的320秒预算的4.5倍快，而且比需要1110秒的MCTS-AHD(ACO)高效一个数量级以上。这种计算开销的大幅减少突显了我们演化的启发式在时间关键应用中的实用价值。

4.4 案例研究#

图4展示了G-LNS在CVRP50实例上演化过程中单次优化迭代的代表性快照。迭代开始时，解陷入局部最优（成本=11.26，图4a），特征为交叉边和低效路线。

在破坏阶段（图4b），应用破坏率$\epsilon = 0.2$，演化的PSWR算子（附录E.2）表现出有针对性的策略。它专门识别并移除涉及最纠缠区域的节点，有效地拆解次优结构以促进重新优化。随后，ACAGI修复算子（图4c）重构解。关键是，这个过程不仅仅是重新排序原始路径内的节点。如从(b)到(c)的过渡所示，算子动态地将客户重新分配到不同的路线，纠正次优的节点-车辆分配。这种聚类和排序的同步优化成功解开了交叉，将成本显著降低到9.96。

A.1 AHD#

自动启发式设计（AHD），通常称为超启发式（Burke等，2013），旨在自动化发现优化算法。形式上，不是解空间$\mathcal{S}$中搜索最优解，而是在算法空间$\mathcal{H}$中搜索高质量的启发式算法$h$。目标是识别出能在目标问题实例分布上良好泛化的启发式，而不是过拟合单个实例。

历史上，演化计算（EC）一直是AHD的主要搜索策略。在各种EC方法中（López-Ibáñez等，2016；Blot等，2016；Burke等，2018），遗传编程（GP）（Koza，1994；O’Neill，2009）长期以来被认为是主流方法。在GP范式中，启发式通常表示为语法树，通过子树交叉和点突变等遗传操作进行演化，以优化其在训练实例上的性能（Mei等，2022）。

尽管取得了成功，传统的基于GP的AHD面临一个重大瓶颈：依赖于手工设计的遗传算子。突变和交叉算子通常需要大量的领域专业知识，以确保修改后的启发式保持语法有效和语义有意义（Duflo等，2019）。这种对人工设计的依赖限制了搜索过程的灵活性，推动了最近向更智能、生成式算法发现方法的转变。

A.2 神经组合优化（NCO）#

神经组合优化（NCO）已成为解决传统精确求解器计算困难问题的一个有前景的范式。NCO的核心动机是从数据中离线学习启发式，从而能够在实时推理中生成高质量的近似解（Bello等，2016；Bengio等，2021）。

序列到序列建模。早期的NCO方法将解的构造形式化为序列到序列（Seq2Seq）预测任务，类似于神经机器翻译（Sutskever等，2014）。然而，标准的Seq2Seq模型在处理组合问题时遇到困难，因为输出词汇（例如要访问的具体城市）随每个输入实例而变化，不同于翻译任务中固定的词汇（Vinyals等，2015）。为了克服这一限制，Vinyals等（2015）引入了指针网络（Ptr-Net），它使用指针机制通过注意力分数直接选择输入元素作为输出。

从监督学习到强化学习。虽然Ptr-Net奠定了基础，但通过监督学习优化它们被证明是不切实际的，因为为大规模实例获取最优标签的成本很高（Bello等，2016）。因此，该领域转向强化学习（RL），将生成过程视为一个马尔可夫决策过程（Nazari等，2018）。Bello等（2016）提出了一个Actor-Critic框架，其中神经网络充当策略，以最小化路径长度，使用负路径长度作为奖励信号。他们还引入了主动搜索，通过在推理期间采样多个轨迹来寻找最佳候选解来改进解（Bello等，2016）。

对称感知Transformer（POMO）。现代NCO方法已经发展到利用Transformer架构进行更好的特征提取和长程依赖建模（Kool等，2018；Bresson & Laurent，2021）。值得注意的是，POMO（Kwon等，2020）解决了先前构造策略中固有的起始节点偏差问题。通过利用路由问题的旋转对称性，POMO并行生成多样化的轨迹（每个起始节点一个），并使用平均奖励作为低方差的共享基线（Kwon等，2020）。这种方法显著稳定了训练，并在构造性NCO方法中达到了最先进的性能。

局限性与向AHD的转变。尽管推理速度快，NCO模型本质上作为黑盒运行，通常泛化能力差（Bengio等，2021）。当应用于训练中未见的问题规模或分布时，它们的性能通常会显著下降（分布偏移）（Joshi等，2020；Fu等，2021）。这些在可解释性和可扩展性方面的局限性促使了最近基于LLM的自动启发式设计的兴起，其目标是演化出显式的、可泛化的算法代码，而不是不透明的神经权重（Romera-Paredes等，2024；Liu等，2024b）。

A.3 用于组合优化的LLM#

最近的进展促使了大语言模型（LLM）应用于组合优化（CO）的范式转变。我们将现有的方法分为两个不同的流派：LLM作为求解器和LLM作为设计者。

表3. 用于组合优化的基于LLM的方法比较。 我们的G-LNS在针对LNS算子的结构设计方面是独特的。

LLM作为求解器（直接与迭代优化）。这种范式将LLM视为黑箱优化器，提示它们基于问题描述直接输出解。早期的尝试使用零样本或少样本提示来求解小规模实例（Guo等，2023）。为了提高性能，Yang等（2023）引入了OPRO，其中LLM使用自然语言反馈和优化轨迹作为上下文信息迭代地优化解。其他工作探索专门针对CO任务微调LLM，以增强它们对约束的理解（Jiang等，2024）。

然而，LLM作为求解器的范式面临固有的局限性。首先，LLM难以处理高精度坐标的标记化和数值推理，通常将数字视为语言标记而非数学值（Wu等，2024）。其次，正如Kambhampati等（2024）所指出的，LLM作为想法生成器比作为可靠规划器效果更好；它们缺乏NP难问题所需的严格回溯能力。因此，这些方法容易产生幻觉，并且由于有限的上下文窗口，难以扩展到大规模实例。

LLM作为设计者（自动启发式设计）。认识到直接推理的局限性，该领域已转向基于LLM的AHD，将LLM重新用于生成可执行代码。这种范式通过将执行卸载到标准Python解释器来确保正确性和可扩展性。像FunSearch（Romera-Paredes等，2024）和EoH（Liu等，2024b）这样的开创性框架建立了基础的“思维-代码”演化范式，将LLM视为变异算子，用于演化构造式启发式的种群（Huang等，2025）。

高级搜索策略。为了克服标准基于种群的方法易于陷入局部最优的倾向，最近的工作引入了更复杂的搜索机制。ReEvo（Ye等，2024）整合了反思式演化机制，模仿人类思维，回顾性地分析历史性能以指导更有效的代码突变。此外，MCTS-AHD（Zheng等，2025）和Evo-MCTS（Wang & Zeng，2025）将蒙特卡洛树搜索（MCTS）引入演化过程。通过在树结构中组织启发式，这些方法平衡了探索与利用，允许全面开发那些标准种群可能过早丢弃的暂时表现不佳的启发式。

启发式集演化。为了解决单个启发式无法覆盖多样实例分布的泛化瓶颈，EoH-S（Liu等，2025）提出了自动启发式集设计（AHSD）的概念。EoH-S不是优化单一的算法，而是演化一个互补的启发式集，确保每个问题实例被集合中至少一个有效策略覆盖，从而实现卓越的跨分布性能。

与LLM驱动的启发式邻域搜索的区别。将我们的方法与最近提出的LHNS（Xie等，2025）区分开来至关重要。LHNS将邻域搜索的逻辑应用于算法空间本身——迭代地扰动启发式代码块以找到更好的函数。虽然LHNS使用类似LNS的概念来指导代码搜索过程，但输出仍然是标准的启发式函数。

总结：框架中的范式转变。如表3总结，与先前的工作相比，我们的G-LNS不仅仅是演化一个更好的评分函数或局部引导规则；它从根本上改变了算法框架。通过明确要求LLM设计结构性的破坏和修复算子，G-LNS使求解器能够对解执行复杂的拓扑变换。这代表了从在固定骨架内优化参数/规则到自动化设计求解器结构组件的转变，这一能力超出了先前AHD方法的范围。

A.4 大邻域搜索（LNS）#

起源与演化。大邻域搜索（LNS）范式最初由Shaw（1998）为解决车辆路径问题而提出，利用“破坏与重建”原则来逃离局部最优。与依赖小移动（如2-opt）的局部搜索方法不同，LNS重新排列解结构的很大一部分（Gendreau等，2010）。一个关键的进展是自适应LNS（ALNS）（Ropke & Pisinger，2006），它维护一个算子组合，并根据历史性能动态调整它们的选择概率。这种自适应机制使LNS成为一个鲁棒的框架，能够处理各种约束而无需大量的参数调优（Pisinger & Ropke，2007）。

应用与鲁棒性。由于其灵活性，LNS已成为解决广泛NP难组合优化问题的主要元启发式方法。在物流领域，它已成功应用于带时间窗口的取送货问题（Ropke & Pisinger，2006）和电动汽车路径问题（Wen等，2016）。在路由之外，LNS在调度任务中表现出色，特别是作业车间调度问题（Beck等，2011）。

数据驱动和LLM增强的LNS。最近的进展将机器学习与LNS相结合，特别是对于混合整数线性规划（MILP）。诸如Song等（2020）的通用LNS框架和Ye等（2025）的LLM-LNS框架等方法采用基于学习的技术——从模仿学习到LLM推理——来自动化邻域选择过程。这些方法专注于学习一个策略来选择变量的子集进行优化，通常依赖现成的求解器（例如Gurobi）来解决产生的子问题。相比之下，我们的G-LNS利用LLM的生成能力来显式编写特定领域的破坏和修复算子的代码，从而在独立于外部求解器的情况下演化底层的算法逻辑。

B.1 旅行商问题#

旅行商问题（TSP）（Matai等，2010）是一个典型的NP难组合优化问题，作为启发式算法的标准基准。给定一组$N$个城市，目标是找到访问每个城市恰好一次并返回起点的最短可能闭合路径。

形式上，TSP实例可以建模为一个完全无向图$\mathcal{G} = (\mathcal{V},\mathcal{E})$，其中$\mathcal{V} = \{v_{1},\ldots ,v_{N}\}$是$N$个节点（城市）的集合，$\mathcal{E}$表示连接每对节点的边。每条边$(i,j)\in \mathcal{E}$关联一个距离$d_{ij}$，其中节点$i$由坐标向量$\mathbf{x}_i\in \mathbb{R}^2$表示，成本$d_{ij} = \| \mathbf{x}_i - \mathbf{x}_j\| _2$对应于城市$i$和$j$之间的欧氏距离。

令$\pi = (\pi_{1},\pi_{2},\ldots ,\pi_{N})$表示节点索引$\{1,\ldots ,N\}$的一个排列，代表访问城市的顺序。优化目标是找到一个排列$\pi^{*}$，最小化总路径长度：

$\min_{\pi}\mathcal{J}(\pi) = \sum_{i = 1}^{N - 1}d_{\pi_{i},\pi_{i + 1}} + d_{\pi_{N},\pi_{1}} \quad (9)$

LNS应用示例。为了将LNS框架应用于TSP，搜索过程通过破坏和修复阶段迭代，以逃离局部最优（Wouda & Lan，2023）。与执行小边交换的局部搜索方法（如$k$-opt）不同，LNS结构性地分解解：

• 破坏阶段（毁坏）：给定一个完整路径$\pi$，破坏算子$d(\cdot)$移除一个子集$k$个城市（记为$\mathcal{V}_{rem}\subset \mathcal{V}$），留下一个部分路径$\pi_{partial}$。例如，随机移除算子可能随机选择$k$个节点移除，而段移除算子移除一个连续的城市序列以破坏特定的子路径。
• 修复阶段（重建）：修复算子$r(\cdot)$接收部分路径$\pi_{partial}$和移除的城市集$\mathcal{V}_{rem}$作为输入，将节点重新插入到路径中形成一个新的可行解$\pi^{\prime}$。一个经典的例子是贪婪插入，它迭代地将每个节点$v\in \mathcal{V}_{rem}$插入到$\pi_{partial}$中使增量成本$\Delta d = d_{\pi_{i},v} + d_{v,\pi_{i + 1}} - d_{\pi_{i},\pi_{i + 1}}$最小的位置$(i,i+1)$。

通过这种机制，LNS可以在搜索空间中进行大范围移动，有效地重塑路径结构以找到更优的全局解。

B.2 带容量约束的车辆路径问题#

带容量约束的车辆路径问题（CVRP）（Toth & Vigo，2002；2014）是TSP的推广，也是物流和运输领域的一个基本问题。与TSP不同，CVRP涉及多辆车服务一组客户，受车辆容量约束。目标是设计一组最优路线，在满足客户需求的同时最小化总行驶成本。

形式上，CVRP实例定义在图上$\mathcal{G} = (\mathcal{V},\mathcal{E})$，其中$\mathcal{V} = \{v_{0},v_{1},\ldots ,v_{N}\}$。这里，节点$v_{0}$代表中心车场，$\mathcal{V}_{c} = \{v_{1},\ldots ,v_{N}\}$代表$N$个客户的集合。每个客户$v_{i}$有一个正的需求$q_{i}$，车场的需求$q_{0} = 0$。我们有一队相同的车辆，每辆的最大容量为$Q$。

一个解由一组路线$\mathcal{S} = \{R_{1},R_{2},\ldots ,R_{K}\}$组成，其中每条路线$R_{k}$从车场$v_{0}$开始并结束。令$d_{ij}$表示节点$i$和$j$之间的行驶距离（成本）。目标是最小化所有路线的总距离：

$\min \sum_{k = 1}^{K}\mathrm{Cost}(R_{k}) = \min \sum_{k = 1}^{K}\sum_{(i,j)\in R_{k}}d_{ij} \quad (10)$

受以下约束：

1. 覆盖：每个客户$v_{i} \in \mathcal{V}_{c}$必须恰好被一辆车访问一次。
2. 容量：任何单条路线$R_{k}$中服务的客户总需求不得超过车辆容量，即$\sum_{v_{i} \in R_{k}} q_{i} \leq Q$。

B.3 开放式车辆路径问题#

开放式车辆路径问题（OVRP）（Li等，2007）是经典CVRP的一个独特变体。根本区别在于路线结构：在OVRP中，车辆在服务完其路线上的最后一个客户后不需要返回车场。这种问题形式通常出现在第三方物流场景中，车辆被租用用于单程旅行，或者司机使用个人车辆在最后一次送货后直接回家。

形式上，问题定义在与CVRP相同的图$\mathcal{G} = (\mathcal{V},\mathcal{E})$上，有一个车场$v_{0}$和一个客户集$\mathcal{V}_{c}$。关于客户覆盖和车辆容量$Q$的约束与CVRP相同。然而，OVRP中的一条路线$R_{k} = (v_{0},v_{k_{1}},v_{k_{2}},\ldots ,v_{k_{m}})$形成一条哈密顿路径而不是一个环。

目标是最小化开放路径的总行驶距离。数学上，这可以表示为最小化活动路线中边权之和，不包括返回车场的弧：

$\min \sum_{k = 1}^{K}\left(\sum_{j = 0}^{m_{k} - 1}d_{v_{k_{j}},v_{k_{j} + 1}}\right) \quad (11)$

其中$v_{k_{0}} = v_{0}$是车场，$v_{k_{m}}$是车辆$k$访问的最后一个客户。与CVRP不同，成本项$d_{v_{k_{m}},v_{0}}$被省略。因此，OVRP寻求找到一组覆盖所有客户的路径，总长度最小，终点在任意客户节点。

C.1 数据集生成与基准#

数据集设置。遵循MCTS-AHD（Zheng等，2025）中建立的实验协议，我们采用一致的数据生成机制以确保严格比较。我们严格区分用于发现算子的数据集和用于最终评估的数据集。

• 训练集（算子发现）：高质量LNS算子的搜索在一个紧凑的训练集上进行，该训练集由16个固定问题规模$N = 50$的实例组成。将训练限制在特定规模和少数实例上，确保发现的算子捕获可泛化的逻辑，而不是过拟合大数据集。

• 测试集（性能评估）：学到的启发式随后在留出的测试集上进行评估，以评估其性能和可扩展性。该测试集包含每个问题规模$N \in \{10, 20, 50, 100, 200\}$的64个实例，使我们能够验证在$N = 50$上训练的算子是否能有效泛化到更小和更大的实例。

实例特征。实例生成的具体参数配置如下：

• TSP：节点坐标从单位正方形$[0, 1]^2$均匀采样。
• CVRP：与标准NCO设置一致，节点坐标从$[0, 1]^2$采样，车场固定在$(0.5, 0.5)$。客户需求是从$[1, 9]$均匀采样的整数，车辆容量设为$Q = 50$。
• OVRP：实例设置与CVRP相同。

为了进一步评估跨分布泛化能力，我们将评估扩展到标准的TSPLib（Reinelt，1991）和CVRPLib（Uchoa等，2017）基准（详见F.2）。

C.2 实现细节#

对于基线方法，我们严格遵守其官方开源实现，以保证结果的可靠性：

• LKH-3：我们使用官方可执行文件（Helsgaun，2017）和默认参数。
• 深度学习基线（POMO）：我们使用原作者提供的预训练模型，并进行贪婪解码（批次大小=1）以测量原始推理速度，不使用增强。
• ALNS：我们基于Pisinger & Ropke（2007）提出的经典框架实现了自适应大邻域搜索。算子组合包括多样化的移除（随机、最差和关联移除）和插入（贪婪和后悔-k插入）启发式。为了确保有竞争力的基线，我们采用了原始工作中调优的自适应权重调整和模拟退火接受准则的标准参数设置。这确保ALNS的性能反映其鲁棒的通用能力，而不是次优的实现。
• 基于LLM的AHD：对于EoH和MCTS-AHD等方法，我们使用相同的LLM后端（DeepSeek-V3.2）和各自论文中描述的提示工程设置重现了演化过程，确保性能差异源于算法结构而不是语言模型能力。

C.3 评估预算与效率#

为了证明G-LNS优越的样本效率，我们对计算预算施加了比标准基线更严格的约束。

LLM交互预算。现有的基于LLM的AHD方法通常依赖于广泛的试错，需要1000代（或交互）的相当大的预算以确保收敛。相比之下，G-LNS配置的预算显著减少，仅为200代。

效率分析。尽管仅使用了基线方法所需交互预算的20%，G-LNS仍取得了如表1和表4所示的优越性能。LLM查询的5倍减少直接转化为显著更低的令牌消耗和运营成本。这表明演化高层的结构算子（破坏和修复）使搜索过程能够比演化低层的构造规则更高效地导航算法空间，避免了大量暴力采样的需要。

D.1 G-LNS动作的提示#

G-LNS采用不同的演化动作来发现高性能启发式。接下来，我们描述每个动作的含义和提示工程。为了确保鲁棒性和标准化输出，这些提示严格包含任务背景、作为上下文的现有启发式参考、函数标识、输入/输出规范以及根据特定优化任务的逻辑约束。我们通过这些结构化提示执行LLM调用，以获得算法设计思想及其可执行的Python实现。本子节其余部分提供了提示示例，其中我们以不同颜色突出显示功能组件：

• 初始化动作 i1（破坏初始化）：动作i1表示在领域专家种子不足时，直接获得设计有效破坏算子的想法和Python实现以填充启发式池。

  算子 i1（破坏初始化）的提示

  任务是为大邻域搜索（LNS）框架设计一个新颖的破坏算子。给定一个完整的解序列（TSP的城市路径）和要移除的目标元素数量（destroy_cnt），函数必须决定移除哪些元素。目标是开发一种能有效扰动当前解的移除策略。这使得后续的修复算子能够以有助于逃离局部最优并最小化总成本的方式重构解。

  您是启发式优化算法的专家，特别是自适应大邻域搜索（ALNS）。您的任务是为以下问题设计一个新的“破坏算子”（移除算子）：

  问题描述：{task_description} 现有破坏算子（参考）：{operators_str}

  要求：

  1. 首先，用一句话描述您的新算法和主要步骤。描述必须放在大括号内。接下来，在Python中将其实现为一个名为destroy的函数。
  2. 该函数必须接受3个输入：‘current_solution’, ‘destroy_cnt’, ‘distance_matrix’。
  3. 该函数必须返回2个输出：‘removed_elements’, ‘partial_solution’。
  4. 逻辑应严格不同于提供的参考中的现有算子，以增加种群多样性。
  5. 不要给出额外的解释。

• 初始化动作 i2（修复初始化）：动作i2专注于初始化修复算子种群$(P_{r})$。它提示LLM设计一个构造策略，用于将移除的元素重新插入到部分解中，确保重构的路径最小化总成本。

  算子 i2（修复初始化）的提示

  任务是为大邻域搜索（LNS）框架设计一个新颖的修复算子（插入算子）。给定一个部分解partial_solution（其中一些元素已被移除）和一个移除元素列表removed_elements，函数必须确定将这些元素重新插入以恢复完整解的最佳位置。目标是以最小化总成本的方式重构解。

  您是启发式优化算法的专家，特别是大邻域搜索（LNS）。您的任务是为以下问题设计一个新的“修复算子”（插入算子）：

  问题描述：{task_description}

  要求：

  1. 首先，用一句话描述您的新算法和主要步骤。描述必须放在大括号内。接下来，在Python中将其实现为一个名为repair的函数。
  2. 该函数必须接受3个输入：partial_solution, removed_elements, distance_matrix。
  3. 该函数必须返回1个输出：complete_solution。
  4. 逻辑应具有创新性，并与参考算子不同，以确保多样化的重建路径。
  5. 不要给出额外的解释。

• 变异动作 m1 & m2（自适应细化）：动作m1和m2专注于微调单个父代算子。具体的变异策略根据算子在种群中的性能排名自适应选择：排名最高的算子触发参数校准（m2）以巩固成果，排名最低的算子触发逻辑演化（m1）以逃离局部最优，而中间算子随机分配策略。

  变异动作（m1 & m2）的提示

  您是一个算法优化器。我们为LNS有一个{operator_type}算子。

  问题描述：{task_description} 策略：{advice}

  （{advice}槽根据排名动态填充为以下严格指令之一：）

  • m1（逻辑演化）：“生成新颖的算法机制或公式来替换现有的逻辑组件。”
  • m2（参数校准）：“调整当前的参数设置（例如，随机化程度或贪婪阈值）以优化算子行为。”

  当前代码：{operator_code}

  任务：基于上述策略改进并优化此算子代码。

  1. 严格按照上述提供的策略改进并优化此算子。
  2. 如果您需要辅助函数，请在主函数内部定义它们。
  3. 不要给出额外的解释。

• 同质交叉（c1）：促进同一算子类型内的特征重组。为了确保高质量特征的传播，基于历史适应度分数使用轮盘赌选择从种群中选择两个父代算子。然后提示LLM合成一个混合算子，保留父代2的结构形式，同时整合父代1的高层逻辑见解。

  动作 c1（同质交叉）的提示

  您是启发式优化专家。您的任务是通过结合两个父代算子的思想/逻辑来创建一个新的{operator_type}算子。

  问题描述：{task_description} 父代1代码（灵感来源）：{parent1_code} 父代2代码（结构基础）：{parent2_code}

  任务：请创建一个与父代2具有相似形式并受父代1启发的新算法。新算法…

  要求：

  1. 首先，列出父代1中可能带来良好性能的共同思想。
  2. 其次，基于这些共同思想，用一句话描述新算法的设计思想和主要步骤。
  3. 接下来，在Python中实现它。

  要求： 4. 新算子必须严格遵守标准LNS {operator_type}签名。 5. 在主函数内部定义所有辅助函数。 6. 不要给出额外的解释。

• 协同联合交叉（c2）：解决破坏和修复动作之间固有的结构依赖，是G-LNS的核心创新。该策略不是孤立地演化算子，而是基于协同分数（在评估阶段累积）使用轮盘赌选择选择一个耦合的破坏-修复对。明确提示LLM将这些算子作为一个统一实体共同演化，确保修复机制是为重构破坏机制引入的特定拓扑缺陷而量身定制的。

  动作 c2（协同联合交叉）的提示

  您是启发式优化专家。我们正在采用“协同联合交叉（结构耦合）”策略来演化LNS算子。

  问题描述：{task_description} 选定的高协同对：

  • 父代破坏算子：{destroy_code}
  • 父代修复算子：{repair_code}

  任务：将此对作为一个统一实体演化，创建一个新的破坏-修复对。目标是解决破坏和修复动作之间的固有耦合。具体来说，确保生成的修复算子专门为重构生成的破坏算子引入的结构缺陷而定制，从而最大化其协同性能。

  要求：

  1. 设计一个新的破坏算子和一个新的修复算子。
  2. 新的破坏算子应创建特定的结构缺陷。
  3. 新的修复算子必须被设计为高效地修复这些特定缺陷。
  4. 两者都必须严格遵守标准LNS签名。
  5. 在主函数内部定义所有辅助函数。
  6. 返回一个包含新破坏算子和新修复算子的代码块。
  7. 不要给出额外的解释。

D.2 主框架算法#

算法1 G-LNS：用于基于LLM的自动启发式设计的生成式大邻域搜索

1: 输入: 任务$\mathcal{I}$；最大代数$G_{\mathrm{max}}$；种群大小$N$；评估回合数$K$；内部步数$L = 100$；破坏率$\epsilon = 0.2$；初始温度$T_0 = 100$；冷却率$\alpha = 0.97$；权重更新$\lambda = 0.5$；奖励$\Psi = \{\sigma_1,\ldots ,\sigma_4\}$；修剪数量$M$。 2: 输出: 最优解$x^{*}$和优化后的算子种群$\mathcal{P}_d^*,\mathcal{P}_r^*$。 3: 初始化: $\mathcal{P}_d,\mathcal{P}_r$用种子填充；权重$W^d,W^r\gets 1$；适应度$F\gets 0$；协同$S\gets 0$；$x^{*}\gets \mathrm{Init}(\mathcal{I})$；$g\gets 1$。 4: while $g\leq G_{\mathrm{max}}$ do 5: // 阶段1：评估（自适应LNS回合） 6: 初始化回合：$x_{\mathrm{curr}}\gets \mathrm{RandomSolution}(\mathcal{I})$；$T\gets T_0$；$W^d,W^r\gets 1$。 7: for $l = 1$ to $L$ do 8: 通过轮盘赌选择（$p\propto w$）选择$d_i\in \mathcal{P}_d$和$r_j\in \mathcal{P}_r$。 9: 生成$x^{\prime}\gets r_j(d_i(x_{\mathrm{curr}},\epsilon))$。 10: // 评分与接受 11: if $f(x^{\prime})< f(x^{*})$ then 12: $x^{*}\gets x^{\prime}$；$x_{\mathrm{curr}}\gets x^{\prime}$；$\sigma \gets \sigma_{1}$（全局最优）。 13: else if $f(x^{\prime})< f(x_{\mathrm{curr}})$ then 14: $x_{\mathrm{curr}}\gets x^{\prime}$；$\sigma \gets \sigma_{2}$（更优）。 15: else if $\exp (-(f(x^{\prime}) - f(x_{\mathrm{curr}})) / T) > \mathrm{rand}(0,1)$ then 16: $x_{\mathrm{curr}}\gets x^{\prime}$；$\sigma \gets \sigma_{3}$（被接受）。 17: else 18: $\sigma \gets \sigma_{4}$（被拒绝）。 19: end if 20: 更新度量：使用$\sigma ,\lambda$更新$W^d,W^r,F$和$S_{ij}$。 21: $T\gets T\cdot \alpha$。 22: end for 23: // 阶段2和3：演化（每$K$代/回合触发一次） 24: if $g$ (mod $K) = 0$ then 25: 管理：按适应度$F$排序$\mathcal{P}_d,\mathcal{P}_r$；修剪底部的$M$个算子。 26: 重置适应度$F,S\gets 0$以实现公平竞争。 27: while $|\mathcal{P}_d|< N$ or $|\mathcal{P}_r|< N$ do 28: 采样策略$s\in$ {变异，同质交叉，联合交叉}。 29: if $s =$ 变异 then 30: 选择父代$op$；$op_{\mathrm{new}}\gets \mathrm{LLM}(\mathrm{Prompt}_{\mathrm{mut}}(op))$。 31: else if $s =$ 同质交叉 then 32: 选择$op_a,op_b$；$op_{\mathrm{new}}\gets \mathrm{LLM}(\mathrm{Prompt}_{\mathrm{homo}}(op_a,op_b))$。 33: else if $s =$ 联合交叉 then 34: 通过协同分数$S_{ij}$选择$(d_i,r_j)$；$(d',r')\gets \mathrm{LLM}(\mathrm{Prompt}_{\mathrm{joint}}(d_i,r_j))$。 35: end if 36: 验证：对生成的代码进行合理性检查；如果有效则添加算子。 37: end while 38: end if 39: $g\gets g + 1$。 40: end while 41: 返回 $x^{*}$和精英算子。

E.1 为TSP发现的算子#

对于TSP，G-LNS演化出一对复杂的算子，利用状态依赖自适应来导航搜索空间。我们称它们为自适应连续段移除（ACSR）和多样性自适应概率插入（DAPI）。

机制分析。ACSR算子实现了一个大小依赖的策略：对于中等扰动，它精确识别并移除单个最昂贵的连续段以细化局部连接；对于激进破坏，它自动切换到多段碎片化以防止结构锁定。协同地，DAPI算子超越了固定参数逻辑，通过监控实时解多样性。它动态调整其Softmax选择机制的温度——当解变得聚集时增加探索（高温），当多样性高时专注于利用（低温）。

（代码略，见原文）

E.2 为CVRP发现的算子#

对于CVRP，G-LNS演化出更复杂的逻辑，以处理容量约束和车辆间的耦合。我们将识别出的算子称为渐进式随机-最差移除（PSWR）和自适应上下文感知贪婪插入（ACAGI）。

机制分析。PSWR算子引入了一个渐进式随机化方案，在迭代过程中动态调整破坏的“贪婪性”。它根据当前的解状态，在最差移除（针对高成本节点）和随机移除（针对探索）之间自适应地转换。这种适应性允许PSWR在需要时产生有针对性的破坏，同时在陷入局部最优时触发随机性。相应地，ACAGI算子超越了简单的贪婪插入。它在重新插入客户时，显式地建模每个车辆的当前负载和路线长度。这种上下文感知使修复操作能够同时优化聚类（哪个车辆）和排序（在路线内的位置），正如案例研究（图4）所示，导致车辆分配的根本性重组。

（代码略，见原文）

F.1 OVRP详情#

开放式车辆路径问题（OVRP）。需要强调的是，与标准CVRP相比，OVRP通常对启发式设计构成更大的挑战，特别是对于构造式方法。在标准CVRP中，返回车场的要求强制路线形成闭环。这自然防止算法创建过长的路径，因为返回车场的成本有效地限制了车辆可以走多远。相比之下，OVRP移除了这一返回要求。由于不需要闭合回路，顺序构造式启发式（如基线所采用的）通常无法维持紧凑的路线结构。它们倾向于贪婪地将路径扩展到最近邻，而不考虑全局形状，导致松散、碎片化的路线，难以优化。

遵循附录C.1中描述的实验设置，我们将G-LNS与严格的OR-Tools求解器（配置了与CVRP设置一致的时间限制）和基于LLM的AHD方法进行比较。定量结果总结在表4中。

表4. 开放式车辆路径问题（OVRP）在五个问题规模上的性能比较。 差距是相对于所有方法中找到的最佳解计算的。最佳结果以粗体突出。

性能分析。在小到中等规模实例（$N \in \{10, 20, 50, 100\}$）上，OR-Tools的精确求解器逻辑仍然非常有效，达到最优或接近最优的解。在这个范围内，G-LNS表现出稳健的竞争力，始终保持低于$0.8\%$的最优性差距。然而，G-LNS优越的可扩展性在大规模实例（$N = 200$）上变得明显。当OR-Tools在计算时间限制下开始挣扎——产生$2.05\%$的次优差距——G-LNS成功找到显著更优的解，将目标成本从15.19（OR-Tools）降低到14.88，从而建立了新的最佳已知前沿（差距$0.00\%$）。

相比之下，构造式的基于LLM的基线未能适应开放路线结构。正如预期的那样，它们对顺序决策的依赖导致性能不佳，在$N \geq 50$的实例上最优性差距超过$30\%$。这种显著的性能差异突显了LNS范式的关键优势：通过显式演化破坏和修复算子来迭代重塑现有拓扑，而不是逐步构建它们，G-LNS有效地避免了困住构造方法的局部最优。

F.2 基准详情#

在本子节中，我们提供在标准TSPLib和CVRPLib基准上的全面结果。我们将G-LNS与基于LLM的AHD方法（包括EoH、ReEvo和最先进的启发式集方法EoH-S）进行比较。

结果总结。表5给出了每个类别中所有实例的平均最优性差距。G-LNS在所有基准集上优于所有基线。

实验设置。我们直接采用EoH-S（Liu等，2025）的评估配置。与他们的协议一致，所有基线方法都使用映射到$[0, 1]^2$范围的归一化节点坐标进行评估。缩放因子来自每个实例的最大空间范围：

$\mathrm{Scaling~factor} = \max (x_{\mathrm{max}} - x_{\mathrm{min}},y_{\mathrm{max}} - y_{\mathrm{min}}) \quad (12)$

这种归一化步骤对于构造式启发式来说是标准的，以确保数值稳定性。此外，按照这些基线中的标准协议，报告的最优性差距是相对于LKH-3求解器获得的最佳已知解计算的。

相比之下，我们提出的G-LNS直接操作原始的、未归一化的实例数据。这种区别突显了G-LNS演化的算子捕获了路由问题的内在拓扑逻辑，而不是依赖于特定的坐标尺度。

详细结果。详细的最优性差距如下：

• TSPLib：表6报告了对称TSPLib实例上的结果。
• CVRPLib：表7（集合A、B、E、F、M、P）和表8（集合X）报告了带容量约束的车辆路径问题基准上的结果。

（表6-8的数据见原文，此处略）