容量约束下的车辆路径规划问题（CVRP）
在无向图G=(V,E)上，V={0,1,...,n}表示n+1个顶点的集合，E是边集，顶点0表示仓库，V_c=V\{0}表示客户节点集合。边(i,j)∈E的非负权重d_ij表示运输成本。每个客户节点i∈V_c有非负需求q_i，仓库需求q_0=0,使用m辆容量为Cap的车辆满足客户需求，且要求q_i≤Cap。CVRP的目标是找到一组m条路径，使得边权之和最小，每条路径是一个无节点重复的闭环，由顶点的循环序列表示。
自适应局部迭代搜索算法（AILS）
AILS的主要步骤包括扰动（Perturbation）和局部搜索（Local Search）。在扰动阶段，通过某种策略对当前解进行修改，以增加解的多样性。然后，在局部搜索阶段，从扰动后的解开始，进行局部搜索以找到局部最优解。
此外，AILS还可能采用一些其他的策略来进一步提高算法的性能，比如与其他启发式算法或策略相结合，如路径重连（Path - Relinking）等。
AILS-II 算法
（1）整体框架
受 AILS 启发，AILS-II 具有两个阶段，每个阶段都包含扰动和局部搜索步骤。
阶段一：与原始 AILS 类似，通过接受准则确定参考解。首先创建空的精英集 并构建初始解 ，然后进行局部搜索得到局部最优解，将其赋值给变量 作为第一阶段的参考解。在主循环中，根据随机选择的顶点移除启发式 对参考解进行扰动，生成新解 ，再进行局部搜索。如果新解优于当前最优解，则更新最优解。同时，根据扰动度相关的调整规则调整扰动度 ，并检查收敛速度。如果收敛速度低且第二阶段未激活，则激活第二阶段。如果第一阶段正在运行，还需检查接受准则，根据结果更新第一阶段的参考解或接受准则。
阶段二：以 50%的概率从第一阶段切换到第二阶段。从精英解集中随机选择一个新的参考解，然后进行扰动和局部搜索。精英解集用于存储搜索过程中找到的最佳解，以加强搜索。
（2）扰动策略
具体操作：从给定解中移除 个顶点，然后将它们重新插入到路径的其他位置。
移除启发式：
同心移除 ：随机选择一个中心节点，移除一组以该节点为中心的同心顶点。
顺序移除 ：从一条路径中随机选择一个起始点，移除连续的 个顶点。如果在移除过程中路径上的所有元素都被移除，则在另一条路径中选择新的起始点并重复该过程。
插入启发式：
成本插入 ：将顶点插入到导致成本最低的位置。计算顶点插入后与相邻顶点形成的边的成本变化，选择成本变化最小的位置插入。
距离插入 ：将顶点插入到与其最近邻居相邻的位置。
（3）可行性和局部搜索
可行性策略：使用多种移动操作来使当前解可行，包括路线间的移动（Shift1、Swap*、Cross）和路线内的移动（Shift1、Swap1、2 - opt）。这些移动操作通过改变顶点在解中的位置来减少车辆容量约束的违反。
局部搜索：与可行性策略类似，但目标是优化解的值，仅应用于可行解。采用最佳改进策略，选择能最大程度优化解质量和可行性的移动操作。
（4）精英集更新
更新策略：精英集 存储搜索过程中找到的最佳解。当找到一个新解 时，根据其与精英集中解的距离和质量来决定是否将其加入精英集。具体而言，如果新解与精英集中某些解的距离小于等于 ，且满足一定条件（如未达到精英集的最大容量或新解质量优于精英集中最差的解），则将新解加入精英集，并从精英集中移除不符合条件的解。
作用：通过存储和利用高质量的解，在第二阶段加强搜索，提高算法找到更好解的能力。
（5）扰动度控制
四种机制：
固定值 ：为 AILS-II 定义一个固定的 值，所有启发式都使用相同的固定值。
相对值 ： 值与实例规模成正比，即 ，其中 是元启发式参数。
随机值 ：在每次迭代中，从范围 中随机选择一个 值。
距离值 ：根据解 与参考解 的距离来调整 的值。通过计算两个解中不同边的数量来衡量距离，使用公式 。如果距离大于 ，则减小 ；如果距离小于 ，则增大 。
（6）接受准则
七种准则及其特点：
阈值准则 ：通过设定一个阈值 来控制接受解的质量。其中， 是当前解的目标函数值， 是通过局部搜索得到的解的平均质量， 是一个参数，用于确定平均质量与最佳解之间的百分比。
流量准则 ：控制接受解的流量，通过调整 值来实现理想的流量。
距离准则 ：根据接受解与参考解之间的平均距离来调整阈值。
收敛准则 ：在搜索过程中采用收敛行为，开始时采用较宽松的准则，随着搜索的进行逐渐变得更严格。
相对阈值准则 ：设定一个阈值 ，其中 是当前找到的最佳解的目标函数值， 是一个参数。
k - best 准则 ：使用最近 次迭代中找到的最佳解来更新参考解。
最佳准则 ：仅当新解的质量等于或高于当前找到的最佳解时，才更新参考解。
（7）实验结果
接受准则评估：在不同的接受准则中，收敛准则 在 AILS - II 中表现最佳，能够在搜索初期提供合理的多样性，使算法能够逃离局部最优，在后期引导更集中的搜索。
扰动度机制评估：基于距离的扰动度机制 在 AILS - II 中取得了最好的结果，能够根据解的距离动态调整扰动度，有效地平衡了搜索的多样性和集中性。
参数调优：对 AILS - II 的五个参数（、、、）进行了调优，通过在一组实例上优化平均解的间隙来确定最佳参数值。
实验对比：
在小规模和中等规模实例上（Uchoa 等人提出的 100 个实例），AILS - II 与 AILS - PR 和 HGS 相比具有竞争力。AILS - II 在 71%的实例中取得了更好或相等的平均间隙，在 88%的实例中找到了最佳解。
在大规模实例上（Arnold 等人提出的 10 个实例），AILS - II 明显优于 AILS - PR 和 HGS。AILS - II 在所有实例中都取得了更小的平均间隙和更好的最佳解。
AILS-II An Adaptive Iterated Local Search Heuristic for the.pdf
