运筹优化元启发式算法详解自适应大邻域搜索算法-Adaptive-Large-Neighborhood-Search,ALNS-案例讲解代码实现
【运筹优化】元启发式算法详解：(自适应)大邻域搜索算法（( Adaptive) Large Neighborhood Search，(A)LNS）+ 案例讲解&代码实现
文章目录
一、介绍
在过去的15年中，基于大邻域搜索(LNS)和变异自适应大邻域搜索(ALNS)的启发式算法已经成为解决各种运输和调度问题的一些最成功的范例。
大邻域搜索方法通过使用试探法来探索复杂的邻域（交替地破坏和修复解来逐渐改进初始解）。
使用大邻域使得在每次迭代中找到更好的候选解成为可能，并因此遵循更有希望的搜索路径。
本博客从大邻域搜索的一般框架出发，深入研究了自适应大邻域搜索，讨论了该框架的设计思想和性质。讨论了大邻域搜索方法在路由和调度中的应用。我们在本章结束时介绍了超大规模邻域搜索（VLSN）的相关框架，并讨论了与LNS的相似之处，然后得出了一些关于利用大邻域的算法的结论。
然而，搜索大的邻域是耗时的，因此使用各种过滤技术来限制搜索。在VLSN算法中，邻域通常被限制为能够被有效搜索的解的子集。在LNS中，邻域由用于破坏和修复现有解决方案的方法(通常是启发式方法)隐式定义。
两个相似的术语LNS和VLSN可能会引起混淆。我们一贯使用VLSN算法来搜索非常大的邻域和LNS，以获得基于破坏和修复邻域的特定元启发式算法
1.1 示例问题
在这一章中，我们将提到两个示例问题：旅行商问题(TSP)和一个一般化的有容量限制的车辆路径问题(CVRP)。
TSP和CVRP的解的例子如图4.1所示。
1.2 邻域搜索
在本节中，我们正式引入术语：邻域搜索。
我们假设组合优化问题是一个极小化问题，假设
X X
X 是该问题的所有可行解集合，
c ( x ) c(x)
c
(
x
) 为该问题的目标函数。
定义一个解
x ∈ X x \in X
x
∈
X 的邻域为
N ( x ) N(x)
N
(
x
) ，如果
c ( x ) ≤ c ( x ′ ) , ∀ x ′ ∈ N ( x ) c(x) \le c(x’),\forall x’ \in N(x)
c
(
x
)
≤
c
(
x
′
)
,
∀
x
′
∈
N
(
x
) ，则称解
x x
x 是一个局部最优解。
邻域搜索算法以一个初始解
x x
x 为输入，在
x x
x 的邻域进行搜索，以寻找可能存在的更优解，每次找到一个更优解，就用它替换当前解，直到达到局部最优解（找不到任何更优解）。该算法被称为最佳改进算法，因为它总是选择邻域中的最佳解。
TSP邻域的一个简单例子是2-opt邻域，2-opt邻域中的解
x x
x 的邻域是通过删除
x x
x 中的两条边并添加另外两条边以重新连接旅程，可以从
x x
x 到达的解的集合。
CVRP邻域的一个简单示例是重定位邻域，在这个邻域中，
N ( x ) N(x)
N
(
x
) 被定义为可以通过重新定位单个客户从
x x
x 创建的解决方案的集合。可以将客户移动到其当前路线中的另一个位置或另一条路线。
我们定义特定实例
I I
I 的邻域
N ( ⋅ ) N(·)
N
(
⋅
) 的大小为：
m a x { ∣ N ( x ) : x ∈ X ( I ) ∣ } max{ |N(x):x\in X(I)| }
ma
x
{
∣
N
(
x
)
:
x
∈
X
(
I
)
∣
} 。令
P ( n ) \mathscr{P}(n)
P
(
n
) 是所研究问题的所有
n n
n 个实例的集合(可能是无限的)。
然后我们可以将邻域的大小定义为实例大小
n n
n 的函数：
f ( n )
m a x { ∣ N ( x ) ∣ : I ∈ P ( n ) , x ∈ X ( I ) } f(n)=max{ |N(x)|:I\in \mathscr{P}(n),x\in X(I) }
f
(
n
)
=
ma
x
{
∣
N
(
x
)
∣
:
I
∈
P
(
n
)
,
x
∈
X
(
I
)}
在下文中，基于大小为
f ( n )
O ( n k ) f(n) = O(n^k)
f
(
n
)
=
O
(
n
k
) 的邻域针对低
k k
k 值(比如
k ≤ 3 k ≤ 3
k
≤
3 )的试探法被表示为 小邻域搜索(SNS)试探法 。
二、大邻域搜索
大邻域搜索(LNS)元启发式算法的思想类似于破坏和重建方法。
大多数邻域搜索算法明确地定义了邻域，就像前面描述的重定位邻域一样。
在LNS元启发式算法中，邻域由销毁和修复方法隐式定义。
销毁方法销毁当前解决方案的一部分，而修复方法重建被销毁的解决方案。
销毁方法通常包含随机元素，因此每次调用该方法时都会销毁解决方案的不同部分。然后， **解
x x
x 的邻域
N ( x ) N(x)
N
(
x
) 被定义为通过首先应用破坏方法然后应用修复方法可以达到的解集** 。
为了说明销毁和修复概念，考虑CVRP。在当前解决方案中，CVRP的销毁方法可能会移除15%的客户，从而缩短客户被移除的路线。一个非常简单的销毁方法是随机选择要删除的客户。修复方法可以通过使用贪婪启发式算法插入被移除的客户来重建解决方案。
这种试探可以简单地扫描所有空闲客户，插入插入成本最低的客户，并重复插入，直到所有客户都完成。破坏和修复步骤如图4.2所示。
由于destroy方法可能会破坏大部分解，因此邻域通常包含大量解。对于每个移除选择，有许多方法来修复解决方案，但是不同的移除选择当然可以在修复之后产生相同的解决方案。
我们现在更详细地介绍LNS启发式算法。启发式算法的伪代码如算法1所示。
该算法维护三个变量。变量
x b x^b
x
b 是在搜索期间观察到的最佳解决方案，
x x
x 是当前解决方案，
x t x^t
x
t 是可以被丢弃或提升到当前解决方案状态的临时解决方案。函数
d ( ) d()
d
(
) 是销毁方法，而
r ( ) r()
r
(
) 是修复方法。
更具体地说，
d ( x ) d(x)
d
(
x
) 返回
x x
x 的一个被部分破坏的解决方案副本。应用
r ( ) r()
r
(
) 对不完整的解决方案进行修复，也就是说，它返回从被破坏的解决方案构建的可行解决方案。
在第2行，全局最优解被初始化。
在第4行，启发式算法首先应用销毁方法，然后应用修复方法来获得新的解
x t x^t
x
t 。
在第5行中，评估新的解决方案，并且试探确定该解决方案是否应该成为新的当前解决方案(第6行)或者是否应该被拒绝。
accept函数可以用不同的方式实现。最简单的选择是只接受改进的解决方案。请注意，本节稍后将描述更复杂的方法。
第8行检查新的解决方案是否优于已知的最佳解决方案。这里
c ( x ) c(x)
c
(
x
) 表示解决方案
x x
x 的目标值。如果需要，在第9行更新最佳解决方案。
在第11行，检查终止条件。由实现者来选择终止标准，但是对迭代次数的限制或时间限制将是典型的选择。
在第12行，返回找到的最佳解决方案。从伪代码中可以看出，LNS元启发式算法并不搜索解的整个邻域，而只是对这个邻域进行采样。
LNS启发式算法背后的主要思想是，大的邻域允许启发式算法容易地在解空间中导航，即使实例受到严格的约束。这是与小邻域搜索试探法相反的，小邻域搜索会使得探索解决方案空间的遥远部分变得更加困难。
在最初的LNS论文中，accept方法只允许改进解决方案(我们将这种accept方法称为爬山法)。后来的论文，使用了从模拟退火借用的接受标准。如果采用这样的接受标准，LNS试探法可以被视为具有复杂邻域定义的标准模拟退火试探法。
destroy方法是LNS试探法的重要组成部分。实现销毁方法时最重要的选择是销毁的程度：如果只有一小部分解被破坏，那么启发式搜索可能在探索搜索空间时有困难，因为失去了大邻域的影响。如果解决方案的很大一部分被破坏，那么LNS启发式算法几乎退化为重复的重新优化。这可能是耗时的或者产生质量差的解决方案，这取决于如何修复部分解决方案。
于是有学者提出逐渐增加破坏程度，也有学者通过从依赖于实例大小的特定范围中选择程度，在每次迭代中随机选择破坏程度。
destroy方法还必须允许到达整个搜索空间，或者至少是搜索空间中期望找到全局最优解的感兴趣的部分。
因此，它不能总是专注于破坏解决方案的某个特定部分，而必须有可能破坏解决方案的每个部分。
在选择LNS实现的修复方法时有很大的自由度。第一个决定是，在从部分解决方案构建最佳可能的完整解决方案的意义上，修复方法是否应该是最佳的，或者它是否应该是启发式的，假设人们对从部分解决方案构建的良好解决方案感到满意。
最佳修复操作将比启发式操作慢，但可能在几次迭代中产生高质量的解决方案。然而，从多样化的角度来看，最佳修复操作可能并不吸引人：只会产生改进的或相同成本的解决方案，并且很难在搜索空间中留下谷，除非在每次迭代中解决方案的大部分被破坏。修复方法可以基于特定问题的试探法、精确方法、通用混合整数规划(MIP)或约束规划求解器。
值得注意的是，LNS试探法通常在不可行解和可行解之间交替：销毁操作创建不可行解，修复试探法将该不可行解恢复为可行形式。
破坏和修复方法也可以被视为修复/优化操作：修复方法(对应于破坏方法)将解决方案的一部分修复为其当前值，而其余部分保持自由；优化方法(对应于修复方法)尝试在考虑固定值的同时改进当前解决方案。如果使用MIP或约束编程解算器来实现修复方法，则这种启发式解释可能更自然。
三、自适应大邻域搜索
自适应大邻域搜索(ALNS)试探法通过允许在同一搜索过程中使用多种破坏和修复方法来扩展LNS试探法。每个破坏/修复方法被分配一个权重，该权重控制在搜索期间尝试该特定方法的频率。
随着搜索的进行，权重被动态地调整，以便启发式算法适应手边的实例和搜索的状态。
使用邻域搜索术语，可以说ALNS通过在同一搜索中允许多个邻域扩展了LNS。使用邻域的记录性能来动态控制要使用的邻域的选择。
算法2 中显示了ALNS启发式算法的伪代码。当我们与算法1中的LNS伪代码进行比较时，我们注意到以下变化。添加了第4行和第12行，修改了第2行。
破坏和修复方法分别表示为
Ω − \Omega^-
Ω
− 和
Ω + \Omega^+
Ω
。
第2行引入了两个新变量：
ρ − ∈ R ∣ Ω − ∣ ρ^-∈R^{|\Omega^-|}
ρ
−
∈
R
∣
Ω
−
∣ 和
ρ + ∈ R ∣ Ω + ∣ ρ^+∈R^{|\Omega^+|}
ρ
∈
R
∣
Ω
∣ ，分别存储每个销毁和修复方法的权重。
最初，所有方法都具有相同的权重。在第4行中，权重向量
ρ − ρ^-
ρ
− 和
ρ + ρ^+
ρ
用于利用轮盘赌原理选择破坏和修复方法。该算法计算选择第
j j
j 个销毁方法的概率
ϕ j − \phi_j^{-}
ϕ
j
−
，如下所示
ϕ j −
ρ j − ∑ k
1 ∣ Ω − ∣ ρ k − \phi_j^{-}=\frac{\rho_j^{-}}{\sum_{k=1}^{\left|\Omega^{-}\right|} \rho_k^{-}}
ϕ
j
−
=
∑
k
=
1
∣
Ω
−
∣
ρ
k
−
ρ
j
−
并以同样的方式确定选择修复方法的概率。
基于每个破坏和修复方法的记录性能，动态调整权重。这发生在第12行：当ALNS试探的迭代完成时，使用以下公式计算在最后一次迭代中使用的破坏和修复方法的得分
ψ ψ
ψ ：
其中
ω 1 ω_1
ω
1
、
ω 2 ω_2
ω
2
、
ω 3 ω_3
ω
3
和
ω 4 ω_4
ω
4
为参数。高
ψ ψ
ψ 值对应于成功的方法。通常情况下，
ω 1 ≥ ω 2 ≥ ω 3 ≥ ω 4 ≥ 0 ω_1 ≥ ω_2 ≥ ω_3 ≥ ω_4 ≥ 0
ω
1
≥
ω
2
≥
ω
3
≥
ω
4
≥
0 。
设
a a
a 和
b b
b 分别是在算法的最后一次迭代中使用的破坏和修复方法的索引。
ρ − ρ^-
ρ
− 矢量和
ρ + ρ^+
ρ
矢量中与所选破坏和修复方法相对应的分量使用以下等式进行更新：
其中
λ ∈ [ 0 , 1 ] λ ∈ [0,1]
λ
∈
[
0
,
1
] 是控制权重对破坏和修复方法的性能变化的敏感程度的衰减参数。请注意，当前迭代中未使用的权重保持不变。自适应权重调整的目的是选择适合正在求解的实例的权重。
我们鼓励将搜索向前推进的试探法，即
( 4.1 ) (4.1)
(
4.1
) 中的
ω 1 ω_1
ω
1
、
ω 2 ω_2
ω
2
和
ω 3 ω_3
ω
3
参数。我们不鼓励导致许多被拒绝的解决方案的试探法，因为粗略地说，导致被拒绝的解决方案的迭代是浪费的迭代。这可以通过为
ω 4 ω_4
ω
4
分配一个较低的值来实现。
在上面的演示中，我们为每种破坏和修复方法分配了单独的权重。如果一种特定的销毁方法与一种修复方法配合得很好，而与另一种修复方法配合使用时会产生不感兴趣的解决方案，那么这种方法可能不合适。在这种情况下，将权重分配给成对的(销毁、修复)方法而不是每个单独的方法是有意义的。
到目前为止所描述的ALNS试探法倾向于支持复杂的修复方法，与较简单的修复方法相比，复杂的修复方法更经常达到高质量的解决方案。
如果复杂和简单的修复方法同样耗时，这没什么，但事实可能并非如此。如果一些方法比其他方法慢得多，可以用相应启发式方法的时间消耗的度量来标准化一个方法的分数
ψ ψ
ψ 。这确保了时间消耗和解决方案质量之间的适当平衡。
3.1 设计ALNS算法
前面提到的在LNS试探法中选择销毁和修复方法的注意事项也适用于ALNS试探法。然而，ALNS框架提供了一些额外的自由，因为允许多种销毁/修复方法。
在纯LNS试探法中，我们必须选择一种销毁和修复方法，这种方法有望在各种情况下都能很好地工作。在ALNS试探法中，我们可以包括仅在某些情况下适用的破坏/修复方法——自适应权重调整将确保这些试探法在无效的情况下很少使用。
因此，对破坏和修复方法的选择可以转化为对既擅长多样化又擅长集约化的方法的探索。
下面，我们将讨论一些典型的破坏和修复方法。在讨论中，我们将假设我们的解决方案由一组决策变量表示。
术语变量应该以一种相当抽象的方式来理解。
破坏方法的多样化和强化可以如下实现：为了使搜索多样化，可以随机选择应该被破坏的解决方案的部分(随机破坏方法)。为了加强搜索，可以尝试移除
q q
q 个“关键”变量，即具有大成本的变量或破坏解的当前结构的变量(例如欧几里德TSP中的相互交叉的边)。这被称为最坏破坏或临界破坏。
我们也可以选择一些相关变量，这些变量在保持解决方案可行性的同时易于互换。对于CVRP，可以定义每对客户之间的关联度。该度量可以简单地是客户之间的距离，并且也可以包括客户需求(具有相似需求的客户被认为是相关的)。因此，相关销毁方法将选择一组具有高相互关联性度量的客户。这个想法是，应该很容易交换类似的客户。
最后，可以使用基于历史的销毁，根据一些历史信息选择
q q
q 变量。例如，历史信息可以计算给定变量(或变量集)的设置导致不良解决方案的频率。然后，可以根据历史信息尝试删除当前被赋予不正确值的变量。
集合
Ω + \Omega^+
Ω
中的修复方法通常基于针对给定问题的特定的性能良好的试探法。这些试探法可以利用贪婪范式的变体，例如，在每个步骤中执行局部最佳选择，或者在每个步骤中执行最不坏的选择。探索小邻域的传统改进算法（SNS试探法），可用作修复方法的一部分，以提高贪婪算法的输出。
修复方法也可以基于近似算法或精确算法。精确算法可以放宽，以解决质量为代价获得更快的解决时间。如前所述，通过惩罚耗时的方法，可以混合耗时和快速的修复方法。使用MIP解算器来执行修复步骤变得越来越合适，因为这些解算器随着每个新版本的发布变得越来越强大。MIP方法的优点是可以快速实现复杂应用程序的修复方法。一个潜在的缺点是需要特别注意破坏的程度，否则修复方法会变得非常慢。
图4.3以抽象的方式展示了ALNS启发式算法中的许多邻域。图上的每个邻域都可以被认为是破坏和修复方法的独特组合。
3.2 ALNS框架的属性
ALNS框架有几个优点。对于大多数优化问题，我们已经知道了许多性能良好的试探法，它们可以构成ALNS算法的核心。
由于较大的邻域和邻域的多样性，ALNS算法将以结构化的方式探索解空间的大部分。所得到的算法变得非常健壮，因为它可以适应个体实例的各种特征，并且它很少陷入局部最优。
ALNS算法的校准非常有限，因为自适应层自动调整所使用的每个邻域的影响。仍然需要校准用于搜索破坏和修复邻域的各个子试探法，但是可以单独校准这些子试探法，或者甚至使用现有算法的参数。
在大多数局部搜索算法的设计中，研究人员必须在许多可能的邻域中进行选择。在ALNS，问题不是“非此即彼”，而是“兼而有之”。事实上，我们的经验是，ALNS启发式算法使用的(合理的)邻域越多，它的性能就越好。
3.3 与其他元启发式算法的关系
LNS和ALNS与可变邻域搜索(VNS)元启发式算法有相似之处。
VNS试探可以用LNS术语理解如下：第5行中的摇动步骤对应于LNS中的销毁方法，而第6行中的局部搜索步骤对应于修复步骤。在这个意义上，LNS和ALNS可以被看作是VNS的推广。可用于摇动步骤的多个邻域类似于ALNS中的多个邻域，但是在基本VNS中没有邻域的自适应选择。
另一个相关的概念是超启发式。Burke等人将超试探法描述为选择试探法的试探法，即主试探法在几个子试探法之间进行选择的算法。因此，ALNS试探法可以被视为一种超试探法：自适应组件从一组破坏和修复方法(通常是试探法)中进行选择。
3.4 并行
文献中已经提出了利用并行处理的(A)LNS试探法的实现示例。
已经有关于使用图形处理单元(GPU)实现(A)LNS的出版物。GPU是大规模并行处理单元，与普通CPU相比，理论上每秒可以进行更多的计算。
然而，为了充分利用GPU的优势，必须理解新的内存模型和程序部分的执行规则。
Campeotto等人提出了应用于约束编程的大邻域搜索的GPU实现，而Bach等人在简短摘要中提出了用于求解距离约束的CVRPs的ALNS的GPU实现。
四、LNS和ALNS的应用
LNS试探法最初主要用作解决车辆路径问题的试探法。但是，近年来，将启发式应用于其他问题类型的论文数量有所增长。在下面的部分中，我们回顾了一些针对VRP和非VRP应用程序提出的of (A)LNS启发式算法。
4.1 车辆路径应用
4.2 其他应用
五、超大规模邻域搜索
通过考虑一类基于大规模邻域搜索的相关算法来结束这一个博客。LNS属于VLSN算法类，因为它搜索非常大的邻域。然而，LNS的邻域通常由破坏和修复试探法隐式定义，而VLSN算法通常具有邻域的显式定义。
根据Altner等人的说法，如果搜索算法搜索的邻域随着实例大小呈指数增长，或者如果邻域太大而不能显式搜索，则该搜索算法属于VLSN算法类。显然，VLSN算法的种类相当广泛。
Altner等人将VLSN分为三类：
- (1) 可变深度方法
- (2) 基于网络流的改进方法
- (3) 基于复合移动或变量固定的其他方法。
搜索一个非常大的邻域应该比搜索一个小的邻域直观地导致更高质量的解决方案。
然而，在实践中，如果嵌入元启发式框架，小邻域可以提供相似或更好的质量，因为它们通常可以更快地被搜索到。因此，VLSN算法不是“灵丹妙药”。
但是，对于正确的应用，它们可以提供出色的结果。
5.1 可变深度方法
较大的邻域通常导致更好质量的局部解，但是搜索更耗时。因此，每次搜索陷入局部最小值时，自然的想法是逐渐扩大邻域的大小。
一个典型的例子是1-交换邻域
N 1 N_1
N
1
，其中一个变量/位置被改变。类似地，2-交换邻域
N 2 N_2
N
2
交换两个变量/位置的值。一般来说，k-交换邻域
N k N_k
N
k
改变
k k
k 个变量。可变深度搜索方法是部分搜索k-交换邻域的技术，因此减少了用于搜索邻域的时间。
5.2 基于网络流量的改进算法
这一系列改进算法使用各种网络流算法来搜索邻域。一般来说，它们可以分为以下三类，但不一定是截然不同的类别：
- (1) 最小成本循环法
- (2) 基于最短路径的方法
- (3) 基于最小成本分配的方法。
在下文中，我们对这些方法进行了简要概述。
5.2.1 由循环定义的邻域
循环交换邻域由在一系列子集之间传递的元素序列组成。Thompson 展示了如何通过在构建的改进图中找到负成本循环来在循环交换邻域中找到改进的邻居。在改进图中寻找负成本子集不相交环是NP难的，但是存在有效的启发式搜索图。
Thompson和Psarafitis 以及Gendreau等人应用循环邻域来求解VRP。Ahuja等人使用循环交换来解决容量受限的最小生成树问题。
5.2.2 由路径定义的邻域
路径交换是交换邻域的推广。大规模邻域可以通过聚合任意数量的所谓独立交换操作来定义。通过求解为此目的构建的改进图中的最短路径问题，可以在
O ( n 2 ) O(n^2)
O
(
n
2
) 时间内找到该聚集交换邻域的TSP旅行的最佳邻居。
对于单机分批问题，Hurink 应用了聚合交换邻域的特殊情况，其中仅允许相邻对交换。通过求解改进图中的最短路径问题，可以在
O ( n 2 ) O(n^2)
O
(
n
2
) 时间内找到改进的邻居。
考虑到单机调度问题，Brueggemann和Hurink 提出了相邻成对交换邻域的扩展，可以通过计算改进图中的最短路径在二次时间内搜索该邻域。
5.2.3 由赋值和匹配定义的邻域
Sarvanov和Doroshko 首先为TSP提出了分配邻域。它是通过在改进图中寻找最小成本分配而获得的指数邻域结构。
对于TSP，分配邻域基于k个节点的移除，由此构建二分图。在此图中，左侧的节点是删除的节点，右侧的节点是剩余的节点。每次分配的成本是在两个现有节点之间插入一个节点的成本。Sarvanov和Doroshko 考虑了k = n/2且n为偶数的情况。Punnen 将这种方法推广到任意k和n。
使用相同的想法，Franceschi 等人对距离受限的CVRP获得了有希望的结果。Brueggemann和Hurink 提出了当加权平均完成时间最小化时，在并行机上调度独立作业的问题的指数大小的邻域。
5.3 其他VLSN算法
VLSN算法也可以基于聚合或复合独立移动。其思想是同时执行两个或更多的移动，当它们对目标函数的影响可以独立评估时。Ergun 等人和Gendreau等人聚合独立移动来解决VRP，Brueggemann等人将这一概念应用于最小完工时间平行机调度问题。
另一种方法是通过固定决策变量的子集来解决诱导的MIP子问题。Danna 等人提出的RINS算法解决了一个诱导的MIP子问题，其中一些变量被固定为以前在任解决方案中经常获得的值。Davenport 等人使用约束编程来搜索大的邻域。
六、结论
本博客对LNS和ALNS进行了深入的描述，并简要解释了VLSN的核心概念。在过去十年中，利用大邻域的算法已经显示出非常有前途的结果。
LNS试探法的一个主要优点是，试探法可以从现有的组件中快速组合起来：现有的构造试探法或精确方法可以转变为修复试探法，并且基于随机选择的销毁方法易于实现。因此，在开发更复杂的方法时，我们看到了使用简单的LNS试探法进行基准测试的潜力。
值得注意的是，与使用较小的邻域相比，较大的邻域并不能保证找到更好的解决方案。邻域搜索复杂度的增加意味着局部搜索算法可以执行更少的迭代。
Gutin和Karapetyan 通过实验比较了多维分配问题的许多大小邻域，包括它们的各种组合。
已经证明，小邻域和大邻域的一些组合提供了最好的结果。这可能表明混合邻居可能是未来研究的一个有前途的方向。
未来另一个有趣的研究课题是调查机器学习和人工智能技术是否可以用于改善ALNS的自适应层。很可能破坏和修复方法的更聪明的动态选择可以改进启发式算法，并且让算法中的其他参数适应手边的实例可能是有趣的，例如控制解决方案接受的参数。