路由与波长分配（Routing and Wavelength Assignment with Minimum Wavelength,RWA）问题,是指在给定的波分复用光网络中为指定的所有业务寻找一条从业务起点到业务终点的路径,并为每个业务分配特定的波长,同时必须满足通信互不干扰约束,即两个经过相同链路的业务不得分配相同的波长。而最少波长数路由与波长分配（min-RWA）为RWA问题的变种,要求网络使用的波长数尽可能少,该问题是波分复用光网络中的经典NP难问题,在工业界与学术界均有大量的研究与应用,对于提升波分复用光网络整体的利用率具有重大意义,因此对于该问题的研究兼具挑战性和重要性。首先算法通过优化转判定的方法将该问题转换成一系列判定子问题（k-RWA）,并通过求解这些k-RWA问题来求解原问题,并针对路径规划和波长分配互相影响的问题提出了一个新的邻域动作,名叫Shift-Shaking（SS）,该动作实际为一个组合动作,包含一个上层的简单移动（Shift）动作和底层的基于弹射链（Ejection Chain）的抖动（Shaking）动作,这两个动作的作用分别为改变一个特定业务的波长和寻找受该业务影响的相关业务的最优路径,这个新的邻域被嵌入到一个简单的迭代局部搜索算法中,称为SS-ILS,用于求解该子问题;同时针对邻域搜索太过笨重的问题,提出了四个加速策略:邻域精简、两层评估策略、增量评估技术以及cache加速技术,提高了算法的效率。实验结果表明,算法在113个经典实例中改进了22个算例的历史最优解,同时在其它算例上均得到了持平历史最优解的结果,表明了新提出方法的有效性。另外通过禁用加速策略构建了四个SS-ILS的简化版本,与SS-ILS进行对比,实验结果表明了这些策略的有效性。总而言之,SS-ILS算法采用求解子问题的方式对原问题进行求解,同时结合了本文提出的Shift-Shaking邻域动作以及四个加速策略,相比前人算法有较大改进,且后续可通过结合种群算法的方式进行进一步优化。