近二十年来,局部搜索算法在各个领域的应用非常广泛,特别是针对一些比较复杂的优化问题.局部搜索算法的主要优点在于它是一种比较通用的优化算法,可以比较方便地应用于具体的优化问题.而且局部搜索算法的运行时间和优化程度可以由用户通过参数来控制.但是传统的局部搜索算法也存在着一些明显缺陷,最主要的就是传统的局部搜索算法在优化过程中容易陷入局部最优.尽管一些局部搜索算法采用了一些特殊的策略来避免陷入局部最优,但是当问题规模,复杂度比较大的情况下这些算法还是会不可避免地陷入局部最优.易于陷入局部最优这一缺点使得传统的局部搜索算法一般很难实现高效的优化.本文正是针对传统局部搜索算法的缺点,创新地将多邻域搜索的思想加入传统的局部搜索算法中,即在算法的搜索过程中按照一定策略,在多个不同的邻域结构内进行不断的切换,这样不仅可以避免在一个邻域结构内易于陷入局部最优的情况,而且还可极大地提高局部搜索算法在解空间内的搜索能力.我们将这种新的局部搜索算法称为基于多邻域的局部搜索算法(MNBLS),根据多邻域搜索和传统局部搜索算法结合方式的不同,基于多邻域的局部搜索算法可以分为两大类:内嵌式多邻域局部搜索算法和混合式多邻域局部搜索算法.内嵌式多邻域局部搜索算法又可分为:单路内嵌式多邻域局部搜索算法和多路内嵌式多邻域局部搜索算法;混合式多邻域局部搜索算法也可再细分为:非交换型混合多邻域局部搜索算法和交换型混合多邻域局部搜索算法.为了测试基于多邻域的局部搜索算法的优化性能,我们引入时间表问题作为我们的测试对象.首先我们将各种传统的单邻域局部搜索算法,比如爬山法、模拟退火算法、禁忌搜索算法应用于时间表问题;接着将上述各种基于多邻域的局部搜索算法应用于时间表问题,试验结果表明基于多邻域的局部搜索算法的优化性能远远优于传统的单邻域局部搜索算法;最后分析了产生优化性能差异的原因以及各种基于多邻域的局部搜索算法的并行方案.在本文的最后,我们系统地介绍了基于多邻域的局部搜索算法中需要继续研究的一些内容,这些内容既涉及理论方面也涉及应用方面.