1 邻域搜索及局部搜索

对于邻域搜索以及局部搜索的概念一直没有做系统的学习,在我看来邻域搜索即是对某一个当前解进行邻域操作之后产生的解空间进行的搜索操作,而局部搜索同样是对当前解进行类似交叉算子的操作,若进行多次交叉操作之后,其本质就是根据当前解产生了新的邻域,更详细的了解还需要看一下离散优化的课程

根据阅读的文献^[1]有一些话能帮助理解邻域搜索及局部搜索的区别，该文章采用VNS求解MDVRPTW问题：

在VNS算法中，执行Shaking过程的主要目的是扩展当前解的搜索空间，减小算法陷入局部最优的可能性，使得算法能够求得较好的解。Shaking过程首先从当前解的邻域结构集合中选取一个邻域结构，然后根据这个邻域结构对当前解做相应的改变生成新的解。

Shaking过程首先从当前解中随机选出两条路径，然后从这两条路径中各随机选取一段子路径，最后采用特定的交换算子将这两段子路径进行交换从而得到两条新的路径。Shaking过程类似于遗传算法中的交叉操作。

这篇文献采用了多个邻域结构，当前解包含了多个车场的车辆路径信息，邻域结构之间不同处在于参与路径交换的车场数以及子路径的最大长度不同（由于MDVRPTW存在多个车场，用于路径交换的两条路径既可以从同一车场内选取，也可以分别从不同的车场中选取）。但是这种交换子路径的操作很可能生成两个不可行解。

Local Search过程

Local Search过程将对Shaking过程中生成的两条新的路径分别进行局部搜索，并求得各自的局部最优解，采用的算子有2-opt、Or-opt和3-opt。

可以看到作者的表述意思是对某一条路径进行的局部搜索，类似于遗传算法中的单亲遗传，但是本质上也是通过2-opt等算子产生了新的邻域，再进行邻域搜索。

1. [1]王征,张俊,王旭坪.多车场带时间窗车辆路径问题的变邻域搜索算法[J].中国管理科学,2011,19(02):99-109. ↩