Ravindra K. Ahuja
工业与系统工程系
佛罗里达大学
Gainesville，佛罗里达 32611，美国
Özlem Ergun
运筹学研究中心
麻省理工学院
剑桥，马萨诸塞州 02139，美国
James B. Orlin
斯隆管理学院
麻省理工学院
剑桥，马萨诸塞州 02139，美国
Abraham P. Punnen
数学，统计与计算机科学系
新不伦瑞克大学
圣约翰，新不伦瑞克，加拿大 E2L 4L5
（1999年7月22日）
（2000年10月11日修订）
Ravindra K. Ahuja， Özlem Ergun， James B. Orlin， Abraham P. Punnen
摘要
很多实际的最优化问题是计算复杂的。因此，解决这样问题的实际方法是运用启发式算法（近似值），这样可以在合理的计算时间内找到一个近似最优解。改进型算法通常是一个启发式算法，它通常是从一个可行解开始，并重复寻找更好的解。邻域搜索算法（又叫局部搜索算法）是一类改进型算法，算法的每一步迭代是通过搜索当前解的邻域得到一个改进的解。设计邻域搜索算法的一个关键是邻域结构的选择，即邻域的定义方式。根据经验，邻域越大，局部最优解的质量越好，最后得到的解越精确。同时，邻域越大，每一步迭代的时间越长。因此，除非可以用很有效的方法搜索很大的邻域，大规模邻域搜索技术不一定能产生一个有效的启发式算法。本文关注于输入数据和有效搜索邻域很大的大规模邻域的搜索技术。我们调查了３大类大规模邻域搜索技术：（1）深度变量法：应用启发式算法搜索大规模邻域；（2）大规模邻域搜索：应用网络流技术或动态规划搜索邻域；(3)通过限制在多项式时间解决原问题引入大规模邻域。
１.简介
很多实际的最优化问题是计算复杂的。因此，解决这样问题的实际方法是运用启发式算法（近似值），这样可以在合理的计算时间内找到一个近似最优解。研究启发式算法的文献可以分成两大类：构造型算法与改进型算法。构造型算法是通过给一个或多个决策变量赋值试凑构建一个解。改进型算法通常是从一个可行解开始，并重复寻找更好的解。邻域搜索算法（又叫局部搜索算法）是一类改进型算法，算法的每一步迭代是通过搜索当前解的邻域得到一个改进的解。本文关注于相对输入数据的邻域很大的大规模邻域的搜索技术。对于大规模邻域问题的例子，精确搜索邻域是不现实的，只能搜索邻域的一小部分或开发有效的模糊邻域搜索算法。
邻域搜索算法设计中的一个关键问题是邻域结构的选择，即邻域是如何确定的。选择方式大体上就确定了这个邻域搜索算法是否能得到高精度的解，还是仅仅得到比较差的局部最优解。据粗略的计算，邻域越大，得到的局部最优解越好，而得到的最终解的精确度越高。同时，邻域越大，每步迭代的时间越长。由于人们常常从不同的起始点多次运行邻域搜索算法，较长的执行时间将使单位时间的运行次数降低。因此除非可以以一种更加有效的方法进行搜索，一个较大的邻域不一定能够产生一个更有效的启发式算法。
运筹学领域中的很多成功和被广泛应用的方法可以被看作是很大规模的邻域搜索技术。例如，若将解线性规划问题的单纯型法视为一种邻域搜索算法，则列变换就是一种很大规模邻域的搜索方法。同样的，用于解决网络流问题的增量技术也可以归于很大规模邻域的搜索方法。解决最小费用流问题取消负费用回路的算法，以及解决指派问题的增广路径技术就是两例。
在本调查中我们将很大规模邻域搜索算法分成互相重叠的3种。我们研究的第一种邻域搜索算法是深度变量方法。该方法邻域成指数级增大，并利用启发式算法局部搜索这些邻域。第二类包括基于改进算法的网络流理论。该邻域搜索算法使用网络流技术确定改善的相邻解。最后，在第三类中我们将要讨论由子类或者在多项式时间内可解问题的约束引起的NP难题。尽管我们通过解线性规划问题的单纯型法，以及解决网络流问题的增量技术介绍了大
规模邻域搜索算法的概念，我们将不再论述线性规划问题。我们的问卷调查是将重点放在应用很大规模邻域搜索算法解决NP难题的优化问题上。
本文结构如下。在第2部分，简要介绍局部搜索。第3部分讨论深度变量方法。第4部分讨论基于网络流技术的很大规模邻域搜索算法。第5部分，给出一些可有效解决的NP难题的组合优化问题特例，以及基于这些特例的很大规模邻域搜索算法。第6部分，将描述对给定邻域进行局部搜索算法可能有所帮助的邻域指标。最后第7部分，介绍前面部分中一些算法的计算性能。
2.局部搜索：简述
首先，我们介绍一个组合优化问题以及邻域的概念。组合优化问题有不同的表述方式，这都依靠可行解集的表示方法。这里，我们将可行解集表示为一个有限集的子集。形式化表述如下：
令E={1，2，…，m}表示一个有限集合。一般地，对于集合S，令|S|表示集S的势。令其中2E表示集合E的全部子集的集合。F的元素叫做可行解。令f: F→R。函数 f 叫F⊆2E，
做目标函数。那么一个组合优化问题(COP)的例子可以表示为：
Minimize {f (S): S∈F}
假定F族没有将其元素完全列举出来，而是通过m次多项式的形式表示的。一个组合优化问题的例子可用(F，f )表示。对于我们考虑的大多数问题，费用函数为线性，即有一个向量f1，f2，…fm使所有可行集S，f (S)=∑i∈Sfi。
假定是(F，f )表示一个组合优化问题。邻域函数是建立映射N: F→2E的点。在该函数下，每个S∈F都有对应的E的子集N(S)。不失一般性，假定S∈N(S)，那么集合N（S）叫做解S的邻域。解S*∈F叫做对于邻域函数N的局部最优解，若对于所有S∈N(S)都有*f(S*)≤f(S)。若| N(S)|随着m的增加呈指数增长，邻域N(S)为指数邻域。在本文中，我们将把重点放在指数邻域上，同时我们也讨论由于太大实际中不能精确搜索的邻域。例如，随着m的增加（如大于100万），实际上并不能搜索有m3个元素的全部邻域。我们将应用很大规模邻域搜索算法等邻域搜索技术。
对于两个解集S和T，令S-T表示在S而不在T中的元素的集合。定义距离d(S，T)=|S-T|+|T-S|，即E中仅仅属于S或者T中的元素个数。有时，我们允许邻域含有不可行解。例如，对于旅行销售员问题，可以允许邻域中含有删除一条边的路径。为了强调邻域中比实际路径数量更多，我们常常在搜索中给出不可行解的一个组合描述。我们将这些不可行组合结构叫做参考结构。例如，一条Hamiltonian路径可能就是一个参考结构。
邻域搜索算法（最小费用问题）可以用下面的3部分概念组成：
1) 根据具体问题定义的一个邻域图NG，NG为有向图，其每个节点对应于一个可行解
（并且/或者是非可行参考结构的例子），图的一条弧(S，T)满足T∈N(S)。
2) 每步迭代搜索邻域图的方法。
3) 确定在步骤2中选择邻域图中下一个节点的方法。我们称该节点为基解。
当S为给定邻域内的一个局部最优解，结束算法。（详情参见文献[1]）
接下来，根据距离定义两个邻域。第一个邻域为Nk(S)={T∈F:d(S，T)≤k}。我们称该邻域为k距离邻域。
对于某些问题，任意两个可行解都有相同的势。旅行销售员问题就是如此，其中每个可行解S代表了n个城市完全图的一条路径和n条弧（关于TSP详情见文献[48]）。一般的，若|S-T|=|T-S|=1，可以通过一次交换得到T；若S-T|=|T-S|=k，可以通过k步交换得到T。定义S的k步交换邻域为{T: |S-T|=|T-S|≤k}。若任意两个基本可行解都有相同的势，那么S的k步交换邻域等于N2k(S)。旅行销售员问题的一个标准k步交换邻域为2步交换邻域，又称作2步最优邻域。该问题2步最优邻域图中的任意节点为一个路径，若一个路径可以通过2步交换从另一个路径获得，则可称两者相邻。搜索邻域的方法是很详尽的（或者有捷径），下一个基本解将是一个改善了的解。
由于Nm(S)=F，则当k增大时，搜索k距离邻域将会十分困难。通常，当k不固定时，邻域呈指数增长，当原问题为NP难题时，在邻域获得最优解（或者一个改善解）也是NP难题。
3.深度变量方法
对于k=1或2，k步交换邻域（或者k距离邻域）的搜索通常十分有效，但是平均而言，结果的局部最优比较差。当k比较大时，k步交换邻域将获得更好的局部最优解，但是花费的搜索精力会太大。深度变量搜索方法是局部搜索k步交换邻域的技术。该局部搜索的目标是在大量减少搜索时间的情况下寻找目标函数与全局最优解接近的解。通常，他们并不能保证是局部最优。在很大规模邻域搜索算法中，我们对搜索部分k步交换邻域的几种算法很感兴趣。在该部分中，我们将介绍解旅行销售员问题的Lin-Kernighan算法[50]，以及解决不同组合优化问题的k步交换邻域的其他启发式深度变量算法。在下一个部分，我们将介绍当k不确定时，在多项式时间内隐搜索指数性k步交换邻域的子集的其他方法。
在介绍Lin-Kernighan算法前，先介绍一些符号。接下来，我们要介绍如何将Lin-Kernighan算法推广到解决组合最优化问题的启发式深度变量方法（和喷出链）。假定T与T’为E的子集，但是并不一定可行。从T到T’的一条路径为序列T=T1，…，Tk=T’使对于j=1到 k-1，d(Tj，Tj+1)=1。
深度变量方法依靠有下面特点的移动子程序：
1. 在每步迭代中，子程序Move创建了一个子集Tj，以及根据某些搜索准则从（Sj-1，
Tj-1）得到了一个可能的可行子集Sj。子集Tj可能可行或者不可行。这个操作用
Move（Sj-1，Tj-1）=（Sj，Tj）来表示。
2. 对于j=1到k-1，d(Tj，Tj+1)=1。
3. 根据深度变量方法，Tj通常满足其他的性质。
令T代表当前旅行销售员问题的路径，不失一般性，假定T按照顺序1，2，3…n访问各个城市。T的一个2步交换邻域可以定义为用两条边(i，k)(j，l)或(j，l)(j，k)代替(i，j)(k，l)构成另一种路径T’。注意d(T，T’)=4。2步交换邻域可以用4步操作规范描述，其中第一步从T中删除边(i，j)，第二步操作插入边(i，k)，第三步删除边(k，l)，最后加入边(j，l)。
…，vn代表G的一条n个节点的Hamiltonian令G=(N，A)代表有n个节点的无向图。令P=v1，
路。径与环（术语参见文献Glover[30]）是指可以通过向Hamiltonian路加入弧(i，j)得到的含有n条弧的生成子图，其中i是路径的末端节点。注意若i是路径的末端节点，j是路径的另一末端节点，则径与环结构为Hamiltonian回路，也等价于一条路径。若T为路径或者径与环结
构，我们用f(T)代表其总长度。
在从路径S到T路径的转移中，Lin-Kernighan启发式算法允许更换n条边，即武断地说d(S，T)等价于k=2n。算法开始时，从原路径T1删除一边得到一条Hamiltonian回路T2。此后，T2的一个末节点保持不变，直到迭代结束。选择另一个末节点开始进行搜索。偶数次操作插入一边进入Hamiltonian回路T2j，该回路与不固定的径与环T2j+1的末端节点相近。迭代的奇数次操作从当前径与环T2j-1删除一边得到一条Hamiltonian回路T2j。从任意Hamiltonian回路T2j，通过加入2个末节点可以暗中得到一个可行路S2j。在Lin-Kernighan算法结束时，得到了一个新的基本路径Si，使对于所有j都有f(Si)=f(S2j)。
下面我们将更加详细地描述Lin-Kernighan算法的步骤。在偶数次操作中加入的边是接近不固定末端节点的最短边，当且仅当f(S)－f(S2j+1)>0时加入Hamiltonian回路T2j。Lin-Kernighan [50]也给出了一种边的优化选择方法。加入Hamiltonian回路T2j的边通过最大化f(T2j)－f(T2j+2)进行选择。另一方面，在奇数次操作中删除的边由前面操作得到的径与环T2j-1唯一决定，这样将会得到的T2j是一条Hamiltonian回路。当选择要加入的边时，要考虑其他的约束。研究者考虑了不同的约束组合如先前删除的边不能够再次加入或者前面加入的边在后面的操作中不能够删除等等。最后，当考虑了所有初始固定节点的可能依然没有改善的路径时，Lin-Kernighan算法以局部最优解结束。
下面我们用一个数字例子解释Lin-Kernighan算法。考虑图１(a)中10节点的旅行路径。算法首先删除弧(1，2)得到图１(b)所示的Hamiltonian路。然后加入弧(2，6)，给出如图１(c) 所示的径与环。
图１ Lin-Kernighan算法说明
(a)10节点路径 (b)Hamiltonian路 (c)径与环
从本结构中删除边(6，5)得到一条Hamiltonian路，加入边(5，8)，得到另一个径与环。在Lin-Kernighan启发式算法中的插入边的迁移要根据累计受益的费用标准，并且删除边的迁移唯一地生成了该路结构。当考虑了所有起始节点的可能而不能形成改善解，Lin-Kernighan算法得到了一个局部最优解。
Lin-Kernighan启发式算法有几种变形可以得到质量更好的启发式解。这些算法应用一些改进如2步最优，3步最优，以及特别的4步最优操作（文献[29][41][42][50][51][52][64]）以得到基本Lin-Kernighan操作不能得到的路径。同样，运用有效的数据结构刷新路径以确保计算效率和解的质量([24][42])。Papadimitriou[54]指出根据Lin-Kernighan算法计算确定的局部最优是完全的局部搜索问题。
现在我们根据以下Lin-Kernighan启发式算法的通用过程定义旅行销售员问题的深度变量法。该过程先取一个可行路径S作为输入，之后运用前面定义的Move函数。在每步迭代中，Move函数创建一对(Tj，Sj)，其中子集Tj是可行集或者一参考结构的不可行例子。子集Sj是可行集。Move函数被调用执行r次迭代，其中r根据合适的参考规则决定。最后，深度变量搜索过程返回含有当前的最优目标函数值的可行子集Sk。
procedure Variable-Depth-Search（S）;
begin
S1:=T1:= S;
For j:=2 to r do (Tj，Sj)=Move(Sj-1，Tj-1);
选择集合Sk使Minimize(f(Sj):1≤j≤r);
end;
这种特殊的深度变量搜索依靠一种做Move的启发式算法，它从初始解开始系统地形成解的路径。该框架具有相当的柔性，有很多不同的设计程序Move的方法。如何设计Move程序的细节是一个成功的启发式算法与不太成功算法的不同之处。
在上面提到的程序中，我们假定Move每步创建了一个单一可行解。事实上，每步创建多个可行解([31][61])是可能的，或者每步均无可行解（[30][58]）。
许多深度变量法要求中间解Tj满足特定的拓扑（或结构）性质。例如，在Lin-Kernighan算法中，我们要求对于任意奇数j，Tj是一个径与环。我们同时要求对于任意偶数j，Tj是一个Hamiltonian路。我们将在下面的章节中看到Tj满足额外的非结构性的性质的例子。例如，额外性质可能要依靠指标的顺序。
Glover[30]扩展与推广了Lin-Kernighan的思想，考虑了基于经典变换路径方法的一种结构化的深度变量方法，叫做喷出链。Glover写道“粗略地看，喷出链由选择一组元素进行状态变化引起（例如，占据新位置并且或接受新的值）。变化的结果会辩识出另一个集合，他们具有以下性质，即至少有1个元素要从当前状态中被删除。状态变化步骤与删除步骤交替进行，并且每一次选择是依据前面步骤的累积效果（通常受最近的前面步骤影响，但非必然）。
喷出链的术语一般是建议性的而在有些情况下，一连串的操作可能表现出多米诺骨牌效应。
不是限制性的，这提供了一种统一的思路，连接了一系列探索过程，而不是建立一个排斥其
（这里用斜体字。） 他分类形式的狭隘的成员资格。
本文中，我们将使用下面的更严格的喷出链定义。我们将深度变量法叫做喷出链，若
I. |T1|=|T3|=|T5|=…=n，并且
II. |T2|=|T4|=|T6|=…=n+1（或n-1）
对于任意偶数j，若|Tj|=|S|-1，那么Tj可以通过从Tj-1删除一个元素得到。否则，若|Tj|=|S|+1，那么Tj+1可以通过从Tj删除一个元素得到。本文中的许多深度变量法可以视作喷出链。特别是这些方法包括不同参考结构的构建和一个规则集，以从中得到一些不同的可行解。根据我们的认识，本文中考虑的解决旅行销售员问题的所有深度变量法都可看作喷出链。
我们可以想象基于Lin-Kernighan邻域的邻域图的节点构成的路和径-环。（注意路径也是径-环的例子。）邻域图每条边的末端点将连接一个径-环。搜索技术将会是由Lin和Kernighan提出的算法[44]，选择程序将会选择已发现的最佳路径。因此喷出链的参考结构应该是在喷出链技术中邻域图的节点。若下一轮基本解比当前基本解距离更远，则该技术可以叫做深度变量法。喷出链是一种深度变量法，该方法的一个邻域是另一邻域子集（因此在从大到小的变化中，删除出一个元素）。
在上面叙述的方法中，深度变量法依靠Move函数。也可以创建使用网络流搜索的Nk的指数性子集。在这些邻域中，任何邻域都可以通过一系列适当定义的邻域图的移动得到。注意对于Lin-Kernighan算法，邻域规模为多项式级大小，正是通过搜索求得与基本解不同的解。我们将在下面的章节中介绍这些基于网络流的技术。若在喷出链（添加与删除的交互系列）与邻域元素之间有任何的天然联系，那么可以将这些技术视为喷出链技术[30][31][58]
[21]。
深度变量算法与基于喷出链的算法的应用已经成功的给出了一些组合最优化问题的优良解。Glover[30]、Rego[61]、Zachariasen&Dum[83]、Johnson&McGeoch[42]、Mak&Morton[51]、Pesch& Glover考虑了旅行销售员问题的这些算法。Rego& Roucairol[63]和Rego[62]研究了交通工具路径问题。Dondorf&Pesch[13]提出了使用喷出链的聚类算法。Yagiura等考虑了解决一般分配问题的深度变量法[80]和修订喷出链[79]。此外，Laguna[47]等将短喷出链算法应用于多层次一般分配问题。这些技术也应用于统一图的分割问题[16][20][44][53]，分类分配问题[3]，渠道分配问题[17]，以及护理日程[14]。Sourd[70]应用了一个很普通的大邻域改善程序，其中两个邻域的距离根据不相关机器的日程任务而变化。根据当前解和启发式搜索，产生局部但是较大的枚举树可以得到这些邻域。
4. 基于网络流的改进型算法
在本部分中，我们在基于网络流的算法搜索的邻域内研究局部改进型算法。用于改善邻域的网络流技术可以分为3部分：（1）寻找最低费用回路的方法；（2）最短路或者基于动态规划的方法；以及（3）基于寻求最低费用分配和匹配的方法。根据回路定义的邻域可以看作2步交换邻域的一般形式。基于分配的邻域可以看作插入式邻域的一般形式。在下面的3小节中，我们给出指数性邻域的一般定义以及应用于寻找改善邻域的网络流算法。对于很多问题，可以在一个相关图上应用网络流算法确定一个改善邻域，我们将其叫做改善图。
4.1基于回路定义的邻域
在本部分中，我们将首先定义一个一般的分割问题。然后定义2步交换邻域和循环交换邻域。
令A={a1，a2，a3，…an}表示有n个元素的集合。若每个集合Sj非空，集合之间互不相交，他们的并为A，那么{S1，S2，S3，…Sn}定义了A的一个分割。对于A的任意子集S，令d[S]
表示S的费用。那么集合分割问题就是要找到A的一个最多有K个子集的集合使
小。 ∑kd[Sk]最
设{S1，S2，S3，…Sk}为任意可行分割。若可以在不同子集交换2个元素得到{T1，T2，T3，…Tk}，那么可以称{T1，T2，T3，…Tk}为{S1，S2，S3，…Sk}的2步交换邻接点。{S1，S2，S3，…Sk}的2步交换邻域包含了所有2步交换邻接点。若按照一定次序在S的k≤K个子集
T2，T3，…Tk}，那么可以称{T1，T2，T3，…Tk}为{S1，S2，S3，…Sk}中交换单个元素可得到{T1，
的一个循环交换邻接点。令(Sh1，Sm2，Sn3，…Spk)表示k个子集的这样一种次序，要求h=p，
我们把元素的这种交换叫做循环交换。我们用表2解释循环交换。即最后的子集要与Sh1相同。
在本例中，节点9从子集S1传递到子集S4。节点2从子集S4传递到子集S5。节点3从子集S5传到S3。最后，节点14从子集S3传递到S1，循环交换结束。也可以以任意相似的方式定义一个邻接点路径。从数学上看，通过加入合适的虚节点把一个路径交换变为循环交换是很容易的。
一般的，循环邻接点的数目远大于2步邻接点的数量。当有O(n2)个2步邻接点时，固定K不变，有O(nK)个循环邻接点。若K可以随n变化，则可能有指数个循环邻接点。
Thompson[75]，Thompson与Orlin[76]， Thompson与Psaraftis[77]介绍了如何通过在一个改善图中找到一个负成本互不相交子集回路，确定循环交换邻域中的改善邻接点。下面我们将叙述一下如何构建一个改善图。令A={a1，a2，…an}表示原集分割问题中元素集合，令S[i]表示含有元素ai的子集。图G=(V，E)，若V={1，2，…n}节点集合与原问题中A的元素次序相对应，则称为改善图。令E={(i，j)：S[i]≠S[j]}，其中弧(i，j)对应于节点i从S[i]传到S[j]，并把j从S[j]中删除。对于任意弧(i，j)∈E，令c[i，j]=d[{i}∪S[j]\{j}]-d[S[j]]，即当加入i删除j时S[j]的成本增加。若对于W的任意节点对i和j，S[i]≠S[j]，即对应于W中节点的A的元素都在不同的子集中，我们可以将G中的回路W叫做互不相交子集。分割问题的循环交换与改善图的互不相交子集回路有成本保留上的一一对应的关系。特别的，对于任意负成本循环交换，改善图中有一条负成本互不相交子集回路。不幸的是，确定改善图中是否存在互不相交子集回路是NP完全问题，确定一条负成本互不相交回路是NP难题。（参考，例如，Thompson[75]，Thompson与Orlin[76]， Thompson与Psaraftis[77]）
尽管确定一条负成本互不相交回路是NP难题，存在有效的启发式算法对图进行搜索。（参考，例如，Thompson与Psaraftis[77]与Ahuja等[2]）
循环交换邻域搜索已成功应用于一些特定分割问题的组合优化问题上。Thompson与Psaraftis[77]，Gendreau等[25]和Fahrion与Wrede[19]应用循环交换邻域搜索解决了交通工具路径问题。Frangioni等[23]应用循环交换解决了最小化机器生产间隔的日程安排问题。Ahuja等[2]用循环交换得到了一种解决最小能力生成树的最佳的方法，被作为基准广泛应用。
通过确定改善图中的负成本回路确定改善解的思想也见诸其他的一些文献中。Talluri[74]通过确定相关网络中的负成本回路，确定了日常飞行分配问题中飞行支架设备类型成本节约的变化。飞行分配问题可以用多日用品流整数规划模型表示，其中约束为每种日用品表示一次飞行。Talluri考虑了仅有2种飞行班次约束下的解，并探索了可以通过交换2种航班的一些飞行次数得到改善解。他发展了一个相关联的改善图，并且证明了改善的邻接点对应于改善图中的负成本回路。Schneur与Orlin[68]及Rockafellar[65]运用重复检测和沿负成本回路发送流的方法解决线性多日用品流问题。他们的技术已经延展到基于回路的多日用品流整数规划模型的启发式优化算法。Wayne在文献[81]中给出了解决一般的最小费用流问题的回路消去算法。Firla等[22]介绍了任意2个整数规划交集的改善图。该网络中路径与回路与优化的可行解相对应。此外，该网络形成了赋权的b匹配问题的算法。Glover&Punnen[28]与Yeo[78]讨论的算法构建了优于指数性路径的旅行销售员路径。这些算法也可以看作计算隐性特别层网络的最小费用回路。我们将在5部分更加详细的讨论启发式算法。
4.2路径定义邻域（或者动态规划定义）
我们将讨论3中不同的基于最短路或者动态规划的邻域搜索算法。关于这些方法的讨论将在旅行销售员问题中进行。当应用旅行销售员问题时，可以将这些邻域搜索方法看作：（1）顺序添加和删除边，（2）当通过互换路径中2城市的当前顺序定义交换时，允许类似的多步交换，（3）在当前路径中进行循环移动。我们将详细讨论这些邻域。
4.2.1 通过顺序添加和删除弧建立新的邻接点
我们首先讨论一类通过从当前路径交替添加和删除边得到邻域的最短路算法。这些方法完全的搜索3部分中有附加约束边的喷出链邻域的子集。为了简单，我们假定路径S要按照顺序1，2，3….，n，1通过城市。利用3部分中介绍的术语，令T表示S的一个k步交换邻接点，且从S到T的顺序为S=T1，…，Tk=T。这些邻域对应于Punnen&Glover[58]在其他几个邻域中描述的奇数和偶数步路创建的试验解以及从不同路径结构构建的试验解。由奇数路径生成试验解是Firal等[21]独立提出的。下面解释，由奇数或偶数步路径产生试验解通常要考虑下面的算法：
（1） 删除边（n，1）得到Hamiltonian路T2，从节点1加入边（1，i）到节点i（其中
i>2）得到径与环T3。
当前路的末节点为节点i。删除边（i，i-1），对于i
建立Hamiltonian路，然后建立径与环结构。
检查终止标准是否符合。若是，进入步骤（4），否则，令i=j返回步骤（2）。
删除边（j，j-1）加入最后边（j-1，n）完成路径。 （2） （3） （4）
(a)
图3. 解释交替路径变换
图3解释了9节点路S=(1，2，…，9，1)的处理过程。该路径交换步骤首先删除边(n，1)，并加入边(1，4)。然后删除边(3，4)，加入边(3，7)。最后删除边(6，7)，加入边(6，9)得到新的路径T。在图3(a)中，我们用粗线表示加入的边，要删除的边在边上加入破折号。图3(b)解释了路径交换后的得到的新路径。
Firla等[21]，Glover[30]与Punnen&Glover[58]指出，通过在改善图中寻找一条奇数或者偶数长度的最短路径，该邻域中的一个改善解可以在O(n2)次操作中得到。这里，我们描述一个通过确定奇数或偶数个节点的最短路而确定路径的最佳邻接点的改善图。注意S=(1，2，3，...，n，1)是当前有n个节点的旅行销售员路径。改善图为图G=(V，E)，其中V={1，2，…，
（这样2
对应于删除边（n，1）和添加边（1，j），弧(i，j)∈E（这样1
此外，由奇数和偶数路径产生的试验解，新路径结构如断路和产生不同试验解与参考结构的逆向路可参见文献[58]。奇数和偶数路径单独产生的邻域数目为Ω(n2n)。即使是非指数性邻域，搜索邻域的加速技术也是很重要的。例如，在一个有向非循环改善图中使用最短路算法，Glover [31]在O(n2)次操作中得到了一类4步最优解。
4.2.2复合交换构建新邻域
由路径交换定义的第二类局部搜索算法是交换邻域的推广。考虑n个节点履行销售员路径T=(1，2，3，…，n，1)，通过交换节点i与j的位置(1≤i≤j≤n)得到交换邻域。例如令i=3，j=6，T’=(1，2，6，4，5，3，7，…，n，1)为交换操作下的邻域。2个交换操作交换了节点i与节点j，若max{i，j}max{k，l}，那么称节点k与l独立。那么路径T的一个大规模邻域可以通过混合（联合）任意的一些独立交换操作来定义。 (b)
Congram等[9]，Potts&Van de Velde[57]把该混合交换邻域分别应用在独立机器总负重缓慢日程安排问题和旅行销售员问题上。他们把这种方法叫做动态搜索。在他们的文献中，
并且给出了在O(n3)时间内确定出最优邻接点的动Congram等[9]证明了邻域的大小为O(2n-1)，
态规划递归表达式。Hurink[40]在单机器批量问题上应用合成交换邻域的一个特殊例子，其中只有相邻的对才可以交换，并且指出通过在合适的改善图中确定一条最短路，可以在O(n2)时间内得到一个改善邻接点。
下面我们描述一个改善图，协助搜索混合交换邻域。令T=(1，2，3，…n，1)表示n个节点的旅行销售员路径。改善图为图G=(V，E)，其中（（i））V={1，2，…，n，1’，2’，…n’}是对应于原问题节点及其复制节点的节点集，（2）E为有向弧（i，j’）∪（j’，k）的集合，其中弧（i，j’）对应于节点i和j交换，弧（j’，k）表明节点k将会是下一步交换的第一个节点。例如，G中一条有3个弧(i，j’)，(j’，k)， (k，l’)的路径表示互换节点i与j，节点k与l的2步交换操作。要构建弧集合E，要考虑V中任意对（i，j’）和(j’，k)的节点，当且仅当j>i>1时，弧（i，j’）加入E中。当且仅当j=1而且k>j时，或j>1而且k>j+1时，弧（j’，k）加入E中。对于任意弧(i，j’)∈E，我们有等于删除边(i-1，i)，(i，i+1)，(j-1，j)， (j，j+1)，加入边(i-1，j)，(j，i+1)，(j-1，i)， (i，j+1)后，旅行销售员问题最优费用净增加的相关成本c[i，j’]。换言之，若d[i，j]为原问题中从节点i到j的费用，且d[n，n+1]=d[n，1]，那么
对于j’=i+1，c[i，j’]=(-d[i-1，i]-d[i，j]-d[j，j+1]+(d[i-1，j]+d[j，i]+d[i，j+1])并且
对于j’>i+1，c[i，j’]=(-d[i-1，i]-d[i，i+1]-d[j-1，j]-d[j，j+1])+(d[i-1，j]+d[j，I+1]+d[j-1，i]+d[i，j+1])。
所有边（j’，k）的费用为0。
现在确定混合交换邻域路径的最佳旅行销售员邻接点等价于在该改善图上确定最短路，因此需要时间为O(n2)。注意由于旅行销售员问题是循环问题，其中的一个节点要在变动过程保持不变。在上面的改善图构建中，不失一般性，我们假定节点1不能够移动，因此可以通过确定从节点1’到节点n或n’的最短路搜索邻域。当应用于旅行销售员问题时，Congram等[9]给出的搜索邻域的动态规划递归式也会花费O(n2)时间。上面给出的最短路算法应用于总负重缓慢日程安排问题时要花费O(n3)时间因为要花费O(n3)时间计算弧费用。
4.2.3用循环移动方式创建一个新邻接点
本部分中最后一类局部搜索算法建立在一种循环移动金字塔路径（Carlier& Villon[8]）上。若路径从城市1开始，然后按照递增顺序一直到城市n，最后按照递减顺序通过剩余城市回到城市1，那么该路径叫做金字塔式路径。令T(i) 表示路径T中第i个位置的城市。路径T’叫做路径T的金字塔式邻接点，若存在整数 p使：
（1） 0
T(ip) 其中，i1
T(jn-p) 其中，j1>j2>…>jn-p （3） T’(p+1)=T(j1)，T’(p+2)= T(j2)，…， T’(n)=
例如，若路径T=(1，2，3，4，5，1)那么T’=(1，3，5，4，2，1)为金字塔式邻接点。注意该邻接点的一个缺点是边(1，2)与边(1，n)属于所有路径。为了避免如此，Carlier & Villon[8]考虑了给定路径的n次旋转。该邻域的大小为θ(n2n-1)，并且在改善图中运用n次最短路算法，在O(n3)时间内可以搜索完毕。
下面我们将要描述一个对于旅行销售员问题中可以通过解最短路得到最佳金字塔邻域的改善图。令T=(1，2，3，…，n，1)为n个节点的旅行销售原路径。改善图为图G=(V，E)，其中（i）
V={1，2，…n，1’，2’，…n’}对应于原问题的节点及其复制节点。（2）E为有向弧（i，j’）∪（j’，k）的集合，其中弧（i，j’）对应于节点i到j成连续顺序，弧（j’，k）指跳过节点j+1到节点k-1并把它们按照相反的顺序添加在路径的末尾。要构建弧集合E，要考虑V中任意对（i，j’）和(j’，k)的节点。当且仅当i≤j时，弧（i，j’）加入E中。当且仅当j
c[i，j’]= d[j+1，i-1]，
c[j’，k]=-d[j，j+1])-d[k-1，k]+d[j，k].
注意在计算有末节点1，1’，n，n’的边的费用时，要特别小心。现在邻域可以通过确定从节点1到节点n或n’的最短路搜索，Carlier& Villon [8]也指出若一条路为上述邻域的局部最优，那么它是2步交换邻域的局部最优。
除了这3类邻域，对于一些特殊的旅行销售员问题也可以应用动态规划确定最优解。Simonetti和Balas[69]运用动态规划的方法在特定程序约束下的时间窗口内解决了旅行销售员问题。Burkard等[6]证明了可以用PQ树表示的特殊结构路径集中运用动态规划方法，可以在多项式时间内解决旅行销售员问题。他们也指出，金字塔路径集合可以用PQ树表示，同时存在一种O(n2)算法可以计算最短金字塔路径。这些结果将在第5部分中详细讨论。
4.3 由分配和匹配定义的邻域
在该部分中，我们要讨论通过确定改善图中的最小费用分配定义的指数性邻域结构。我们将在旅行销售员问题中解释邻域。同样，我们也指出分配邻域可以用确定非双向改善图中最小费用匹配进行广义定义。我们在集和分割问题上已经证明了这种广义性。
旅行销售员问题的分配邻域可以看作由路径中删除一个节点并将其重新最优化的插入定义的简单邻域的推广。考虑n个节点的路径T=(1，2，3，…n，1)，若从城市i到城市j的成本为d[i，j]，那么搜索分配邻域的第一步是建立一个双向改善图，步骤如下：
（1） 对于某些k=[n/2]，选择并从当前路径T删除k个节点。令删除的节点为V={v1，
v2，…vk}并且剩余的节点为U={u1，u2，…，un-k}。
（2） 构建一个子路T’=(u1，u2…，un-k，u1)。令qi表示对于i=1到n-k-1每个(ui，ui+1)
的边，令qn-k表示边(un-k，u1)。
（3） 现在构建一个完全双向图G=(N，N’，E)使N={qi:i=1到n-k}，N’=V，每条边(qi，
vj)的权为c[qi，vj]=d[ui，vj]+d[vj，ui+1]-d[uj，ui+1]。
T的一个邻接点对应于通过将V中的节点插入子路T’得到的一条路径T*，最多有一个节点插入T’的邻接节点。K个弧的最低费用分配对应于T的最小费用邻域。
用图4，我们将解释9节点路径T=(1，2，3，4，5，6，7，8，9，1)的分配邻域。令V={2，3，5，8}，然后我们构建U中节点的子路如T’=(1，4，6，7，9，1)。图4解释了只有简单匹配边的双向图G。得到的新路径是T’’=(1，3，4，8，6，5，7，9，2，1)。注意当k=[n/2]时，分配邻域的大小等于Ω([n/2]!)。
图4 解释匹配邻域
分配邻域是由Sarvanov与Doroshko[66]针对k=n/2且n为偶数的旅行销售员问题首先提出的。Gutin[33]针对k=n/2给出了一个有局部最速下降算法的分配邻域搜索算法的理论比较。Punnen[60]考虑了k与n的一般分配邻域。删除路径而不是节点并按照解决最小权重匹配问题重新最优插入的邻域的拓展同样在[60]中给出了。Gutin[34]指出对于某些k值，邻域的大小可以随一些复杂性比较低的搜索邻域算法达到最大。Gutin与Yeo[37]构建了一个基于分配邻域的邻域，并指出运用该方法从任意路径T变动到另一路径T’最多要4步。Deineko与
Woeginger[12]研究了旅行销售员问题的几种指数性邻域以及基于双向图的分配和匹配的二次分配问题和基于偏序，树以及其他组合结构的邻域。基于匹配的邻域启发式算法同样被Dror和Levy[15]应用于存货安排问题。
另一类基于匹配的邻域可以通过包装子路得到，子路通常由解决一个双向最小权重匹配问题[43][59]产生。找到这种最优路径通常是NP难题。可以用有效的启发式算法搜索该邻域
[27][43][59]。应用该邻域的邻域搜索算法可以通过运用成本修订或者其他方式进一步研究以控制匹配产生。
我们下面要考虑一个基于非双向匹配的邻域结构。我们将在第三部分的一般集合分割问题的内容中讨论该邻域。令S={S1，S2，S3，…，Sk}表示集合A={a1，a2，a3，…an}的一个分割。然后构建一个完全图G=(N，E)使对于1≤i≤K的任意节点i表示S中的子集Si。现在G中边(i，j)的权重c[i，j]可以根据多种规则分别给出。一种可能的规则如下：
（1） 令子集Si对分割问题的成本贡献为d[Si]。
（2） 对于E中任意边(i，j)，连接Si与Sj中的元素，重新最优地分成两部分。令新的子
集为Si’与Sj’。
（3） 然后c[i，j]=(d[Si’]+d[Sj’])-(d[Si]+d[Sj])。
注意若含有非负权的边从G中被删除，那么该图中任意负成本匹配将会定义S的一个成本改善邻接点。Tailard将这种思想应用在一类普通的聚集问题[71]和交通工具路径问题[72]上。
5. 可解的特殊例子与相关邻域
有很多文献研究了NP难题的组合优化问题的有效解的特例。对研究者而言特别重要的是通过约束问题的拓扑结构，或者给原问题增加约束，或者两者的组合，从原NP难题中得到的特例。通过在这些有效解特例的基础上建立邻域，研究者可以形成在多项式时间内被搜索的指数数目的邻域。我们指出这其中有很多技术并没有经过验证，形成的结果也可能是比较差的局部最优解。注意在第4部分中讨论的循环移动邻域建立在寻找最低费用金字塔路径的一个O(n2)算法上。
下面的解释是关于Halin图的。Halin图是指通过在平面内嵌入所有节点的度不等于2的树并用回路连接所有叶节点，得到的图。Cornuejols等[10]给出了一个在Halin图上解决旅行销售员问题的O(n)算法。注意Halin图可能有指数数量的旅行销售员路径，如图3所示（参见
[10]）。
下面我们将介绍如何应用Halin图建立旅行销售员问题的很大规模邻域。假定T为一个路径。若H为Halin图且T为H的子图，那么我们称H为T的一个Halin拓展。图5解释了路径T=(0，1， 2，…， 9， 0)的一个Halin拓展。假定有一个有效的程序HalinExtend(T)，它可以创建T的Halin拓展。为了创建邻域N(T)，可以令H(T)= HalinExtend(T)，然后令N(T)={T’:T’为H(T)中的路径}。要在该邻域中寻找最佳路径，可以寻找H(T)中的最佳路径。在理论上，可以定义一个更大的邻域：N(T)={T’: 在T’中存在T的Halin拓展}。不过，由于该邻域要同时最优化T的Halin扩展，因此进行有效搜索非常困难。类似的基于Halin图系统的瓶颈旅行销售员问题和斯坦树问题可以通过分别运用Philips等[56]和Winter[82]给出的线性时间算法建立。 图5. Halin图
(a)10节点路径 （b）Halin拓展
在前面的例子中，我们考虑了金字塔路径，它可以看作附加约束的旅行销售员问题。我们也考虑了约束于Halin图的旅行销售员问题。在下面的例子中，我们将要考虑[28]同时依靠图的严格约束和额外边界约束的邻域。Glover与Punnen[28]确定了下面的路径种类，其中最佳的可以在线性时间内找到。令C1，C2，…，Ck为至少有3个节点的顶点不相交的k个回路，这样每个节点在一个回路中。一条单边删除路径是指具有如下性质的路径T：
1. 对于i=1到k，|T∩Ci|=|Ci|-1，即T与Ci有|Ci|-1条共同弧。
2. 对于i=1到k-1，T中有一条有向弧从Ci到Ci+1，从Ck到C1。
从回路中删除弧的方法最少为∏|C|，这可能意味着指数数目的大小，因此单边删除ii
路径的数目为指数大小。要确定最优单边删除路径，研究者可以解改善图上的一个相关最短路问题。运行时间为弧数目的线性函数。给定一条路径，可以删除路径上的k+1条弧，创建k条路径，然后将这k条路径变成前面叙述的k条回路。原则上，上面的邻域搜索方法很容易执行；不过搜索技术的质量很可能对执行的细节很敏感。Glover与Punnen[28]也考虑了更宽的邻域，包括他们所谓的“双删除路径”。他们也提供了最优化该类路径的有效算法。
Yeo[78]考虑了非对称旅行销售员问题的另一种邻域。他研究的邻域与Glover和Punnen
[28]的研究有一定的关联，但是规模却非常大。他指出，该邻域的搜索时间为O(n3)。Burkard与Deineko[7]确定了另一类指数性邻域，这样其最佳解可以在二次项时间内确定。这些方法都可以用来建立很大规模邻域搜索算法。不过，根据我们的了解，尚未有此种算法。
我们用一个一般性的方法总结本部分的结果，该方法将约束问题的求解方法移植到很大规模邻域搜索技术上。令X代表一类NP难题的组和优化问题。假定X’为在多项式时间内可解的X的约束。进一步假定对于X的实例(F，f)，对于F中的任意可行子集S，存在能够建立X’的实例（F’，f）的良好结构的子程序 “CreateNeighborhood(S)”，满足：
1. S是F’的元素
2. F’为F的子集
3. （F’，f）为X’的例子
我们把F’叫做S的X’诱发邻域。邻域搜索方法包含在每步迭代中调用
“CreateNeighborhood(S)”，然后运用多项式时间算法优化（F’，f）。然后用（F’，f）代替S，算法进行下一步迭代。特别要关注的是，当子程序CreateNeighborhood在多项式实践中运行，而且F’为指数性的情况。邻域就不能够明确的建立起来。当我们相信该方法在邻域搜索上有足够的潜力时，这种潜力就很大程度上没有实现。此外，许多情况下并不清楚如何发挥这种潜力。例如，当约束于混联图时，许多NP难的组合优化问题在多项式时间内是可解的。例如包含网络可靠性问题[67]，最优连通生成树问题[18]，定点覆盖问题[5][73]，反馈顶点几何问题[5][73]等等。有特定程序约束的工作日程安排问题[46]也有类似的结果。在邻域搜索中如何针对混联图最好地利用有效算法是一个有趣的开放性问题。
6.邻域指标
在该部分中我们将描述可能有助于改善给定邻域局部搜索算法性能的邻域指标。前面提到，邻域搜索启发式算法的设计中一个关键问题是邻域的大小与搜索邻域所用时间之间的平衡。因此一个重要的邻域指标是邻域大小。根据邻域图，给定一个解S的邻域，其大小可以视为从S离开的有向弧的数量，或者说等于S的输出度数。对于深度变量法，邻域大小不一定是指数性的，是搜索使得得到的解大大不同于基本解。另一方面，对基于网络的方法和可解特例诱发的手段，邻域大小是指数性的。
下面的表格总结了前面讨论的旅行销售员问题的邻域大小（本表基本上来源于[6]）：
邻域
2步最优
k步最优
金字塔式
循环移动式
边缘删除
基于最短路的边缘删除 大小大小) 搜索时间参考文献 Ω（n2） Ω（nk） Ω（2n） Ω（n2n） Ω((12n)1/3) Ω（n2n） θ(log n) θ(log n) θ（n） θ( n) θ( n) Ω ( n) O(n2O(nkO(n2) O(n3) O(n) O(n2)
循环交换（固定k子集）
混合交换
基于匹配1
Halin图
PQ树
θ（nk） θ（2n-1） θ（n!/2） 2(n loglog n) θ( log n) θ（n） θ( n log n) θ( n) θ( n loglog n) O(n2) O(n2) O(n3) O(n) O(n3) Ω（2n） Klyaus [45] Carlier & Villion [8] Glover & Punnen [28] Punnen and Glover [58]， Glover [30] Ahuja et al. [2] Potts &van de Velde [57] Sarvanov & Doroshko [66] Cornuejols et al. [10] Burkard et al. [6]
文献研究的另一个邻域指标是邻域图的直径。邻域图中节点S到节点T的距离为从S到T的最短路长度。邻域图NG的直径为对于NG中的节点S，T，满足d(S，T)=d的最小正整数。Gutin与Yeo[37]建立了对应邻域图直径为4的旅行销售员问题的指数极大小的多项式可搜索邻域；即，对于任意路径对T1和T5，存在路径T2，T3和T4，满足Ti∈N(Ti-1)，i=2，3，4，5。Carlier and Villon [8]考虑的基于循环移动的邻域直径为θ(log n)。
对于给定的邻域图，若对于j=2到k，目标函数f(ij)
最后我们考虑邻域搜索算法的控制分析。启发式算法的控制分析分析了受其支配的该算法产生的解的数量。令α表示产生F中一个解S*的组合优化问题的一个启发式算法。α的控
是集合F(S*)的势，其中F(S*)={S∈F: f(S)>=f(S*)}。若dom(α)=|F|，制数目，用dom(α)表示，
那么S*为一个最优解。旅行销售员问题不同搜索算法的支配分析可参阅文献[27]，[28]，[35]，
[36]，[38]，[59]和[60]。
7.很大规模邻域搜索算法的计算性能
在本部分中，我们将简要讨论前面提到的很大规模邻域搜索算法的计算性能。首先我们考虑旅行销售员问题。Lin-Kernightan算法及其变形被广泛认为是解决旅行销售员问题的最佳启发式算法。在一项大量的计算研究中，Johnson与McGeoch[42]通过提供一个详细的性能对比分析证明了这一点。Rego[61]对旅行销售员问题运用了一类结果甚好的删除链算法，这也表明了他的算法优于原Lin-Kernightan算法。Punnen与Glover[58]运用了一种给予最短路的删除链算法。Rego[61]与Punnen和Glover[58]直接相关，并运用了简单的结构。
1. 这里假定k=[n/2]，节点已删除。若删除更少的节点，邻域的大小相应的减少，那么时间限制将会更好。
最近，Helsgaun[39]报告了根据一个复杂的Lin-Kernightan算法得到的给人印象深刻的计算结果。尽管该算法运用核心的Lin-Kernightan深度变量搜索算法，它在几个关键方面不同于前面的算法。更优的计算结果原于有效的数据处理，特殊的5次最优操作，新的非顺序操作，有效候选列表，成本计算，元素成本上界的有效运用，Held与Karp 1次树的信息，以及灵敏度分析，等等。Helsgaun报告说他的算法给出了最优解已知的所有测试问题的最优解，包括Applegate等[4]考虑的7397城市问题与13509个城市问题。Helsgaun估计他的算法的平均运行时间为O(n22)。按照这种观点，注意到Applegate等[4]运用分枝定界法确定13509个城市问题的最优解要求一组3位α服务器4100（有12个处理器）和一组32奔腾II个人计算机花费3个月的计算时间。另一方面，Helsgaun运用了一个300MHz的Power Macintosh G3。对于85900
（我个城市的问题，TSPLIB的pla85900，Helsgaun用了2周的CPU时间得到了一个改善解。
们也注意到Applegate等[4]花费的大量时间是为了证明最优解的确是最优的。）
在表1中，我们总结了针对旅行销售员问题小例子的Rego算法[61](REGO)，Helsgaun-Lin- Kernightan [39]算法(HLK)，Mak与Morton[511]的修订Helsgaun-Lin-Kernightan算法和Punnen与Glover[58](SPG)的最短路算法的性能。在表中，我们运用了这些算法的最佳情形。
表1 旅行销售员问题的小例子：最佳解偏离最优解百分比
在表2中，我们总结了针对旅行销售员问题大例子的Rego的算法(REGO)[611]，Helsgaun-Lin-Kernighan算法(HLK) [39], 以及Johnson等Lin-Kernighan算法(JM-LK)[42]（错误，参考文献没有找到）的性能。在表中我们运用了这些算法的平均偏离百分比。
表2 旅行销售员问题的大例子: 一些运行时间内的平均偏离百分比
下面我们考虑赋能的最小生成树问题。这是第4部分讨论的分割问题的特例。Ahuja等[21]运用该问题结构，构建了基于循环交换邻域的很大规模邻域搜索算法。该算法非常有效，对于许多基准问题能够得到改善解。当前，该算法能够获得基准集合中列示的任意例子的最佳可得解，基准集合可以参阅http://www.ms.ic.ac.uk/info.html。
我们最后考虑解决一般分配问题(GAP)的大规模邻域搜索算法。Yagiura等[80]建立了基于删除链解决GAP的禁忌搜索算法。他们指出在合理的计算时间内，得到的解优于或者与现行解法的解可比。根据计算试验与对比，可以知道他们的算法解决基准问题的例子与最优解的偏离百分比小于16%。
本文中引用的许多文献同时也给出了根据算法计算的结果。详情请参阅这些文献。文中涉及的几种大规模邻域并没有在搜索框架内进行实验证明。该种和相关的邻域的有效执行是要深入研究的课题。
致谢：
第一作者的研究得到NSF DMI-9900087的支持。第二作者和第三作者部分由NSF DMI-9810359和DMI-9820998支持。第四作者由NSERC OPG0170381支持。
参考文献
Ravindra K. Ahuja
工业与系统工程系
佛罗里达大学
Gainesville，佛罗里达 32611，美国
Özlem Ergun
运筹学研究中心
麻省理工学院
剑桥，马萨诸塞州 02139，美国
James B. Orlin
斯隆管理学院
麻省理工学院
剑桥，马萨诸塞州 02139，美国
Abraham P. Punnen
数学，统计与计算机科学系
新不伦瑞克大学
圣约翰，新不伦瑞克，加拿大 E2L 4L5
（1999年7月22日）
（2000年10月11日修订）
Ravindra K. Ahuja， Özlem Ergun， James B. Orlin， Abraham P. Punnen
摘要
很多实际的最优化问题是计算复杂的。因此，解决这样问题的实际方法是运用启发式算法（近似值），这样可以在合理的计算时间内找到一个近似最优解。改进型算法通常是一个启发式算法，它通常是从一个可行解开始，并重复寻找更好的解。邻域搜索算法（又叫局部搜索算法）是一类改进型算法，算法的每一步迭代是通过搜索当前解的邻域得到一个改进的解。设计邻域搜索算法的一个关键是邻域结构的选择，即邻域的定义方式。根据经验，邻域越大，局部最优解的质量越好，最后得到的解越精确。同时，邻域越大，每一步迭代的时间越长。因此，除非可以用很有效的方法搜索很大的邻域，大规模邻域搜索技术不一定能产生一个有效的启发式算法。本文关注于输入数据和有效搜索邻域很大的大规模邻域的搜索技术。我们调查了３大类大规模邻域搜索技术：（1）深度变量法：应用启发式算法搜索大规模邻域；（2）大规模邻域搜索：应用网络流技术或动态规划搜索邻域；(3)通过限制在多项式时间解决原问题引入大规模邻域。
１.简介
很多实际的最优化问题是计算复杂的。因此，解决这样问题的实际方法是运用启发式算法（近似值），这样可以在合理的计算时间内找到一个近似最优解。研究启发式算法的文献可以分成两大类：构造型算法与改进型算法。构造型算法是通过给一个或多个决策变量赋值试凑构建一个解。改进型算法通常是从一个可行解开始，并重复寻找更好的解。邻域搜索算法（又叫局部搜索算法）是一类改进型算法，算法的每一步迭代是通过搜索当前解的邻域得到一个改进的解。本文关注于相对输入数据的邻域很大的大规模邻域的搜索技术。对于大规模邻域问题的例子，精确搜索邻域是不现实的，只能搜索邻域的一小部分或开发有效的模糊邻域搜索算法。
邻域搜索算法设计中的一个关键问题是邻域结构的选择，即邻域是如何确定的。选择方式大体上就确定了这个邻域搜索算法是否能得到高精度的解，还是仅仅得到比较差的局部最优解。据粗略的计算，邻域越大，得到的局部最优解越好，而得到的最终解的精确度越高。同时，邻域越大，每步迭代的时间越长。由于人们常常从不同的起始点多次运行邻域搜索算法，较长的执行时间将使单位时间的运行次数降低。因此除非可以以一种更加有效的方法进行搜索，一个较大的邻域不一定能够产生一个更有效的启发式算法。
运筹学领域中的很多成功和被广泛应用的方法可以被看作是很大规模的邻域搜索技术。例如，若将解线性规划问题的单纯型法视为一种邻域搜索算法，则列变换就是一种很大规模邻域的搜索方法。同样的，用于解决网络流问题的增量技术也可以归于很大规模邻域的搜索方法。解决最小费用流问题取消负费用回路的算法，以及解决指派问题的增广路径技术就是两例。
在本调查中我们将很大规模邻域搜索算法分成互相重叠的3种。我们研究的第一种邻域搜索算法是深度变量方法。该方法邻域成指数级增大，并利用启发式算法局部搜索这些邻域。第二类包括基于改进算法的网络流理论。该邻域搜索算法使用网络流技术确定改善的相邻解。最后，在第三类中我们将要讨论由子类或者在多项式时间内可解问题的约束引起的NP难题。尽管我们通过解线性规划问题的单纯型法，以及解决网络流问题的增量技术介绍了大
规模邻域搜索算法的概念，我们将不再论述线性规划问题。我们的问卷调查是将重点放在应用很大规模邻域搜索算法解决NP难题的优化问题上。
本文结构如下。在第2部分，简要介绍局部搜索。第3部分讨论深度变量方法。第4部分讨论基于网络流技术的很大规模邻域搜索算法。第5部分，给出一些可有效解决的NP难题的组合优化问题特例，以及基于这些特例的很大规模邻域搜索算法。第6部分，将描述对给定邻域进行局部搜索算法可能有所帮助的邻域指标。最后第7部分，介绍前面部分中一些算法的计算性能。
2.局部搜索：简述
首先，我们介绍一个组合优化问题以及邻域的概念。组合优化问题有不同的表述方式，这都依靠可行解集的表示方法。这里，我们将可行解集表示为一个有限集的子集。形式化表述如下：
令E={1，2，…，m}表示一个有限集合。一般地，对于集合S，令|S|表示集S的势。令其中2E表示集合E的全部子集的集合。F的元素叫做可行解。令f: F→R。函数 f 叫F⊆2E，
做目标函数。那么一个组合优化问题(COP)的例子可以表示为：
Minimize {f (S): S∈F}
假定F族没有将其元素完全列举出来，而是通过m次多项式的形式表示的。一个组合优化问题的例子可用(F，f )表示。对于我们考虑的大多数问题，费用函数为线性，即有一个向量f1，f2，…fm使所有可行集S，f (S)=∑i∈Sfi。
假定是(F，f )表示一个组合优化问题。邻域函数是建立映射N: F→2E的点。在该函数下，每个S∈F都有对应的E的子集N(S)。不失一般性，假定S∈N(S)，那么集合N（S）叫做解S的邻域。解S*∈F叫做对于邻域函数N的局部最优解，若对于所有S∈N(S)都有*f(S*)≤f(S)。若| N(S)|随着m的增加呈指数增长，邻域N(S)为指数邻域。在本文中，我们将把重点放在指数邻域上，同时我们也讨论由于太大实际中不能精确搜索的邻域。例如，随着m的增加（如大于100万），实际上并不能搜索有m3个元素的全部邻域。我们将应用很大规模邻域搜索算法等邻域搜索技术。
对于两个解集S和T，令S-T表示在S而不在T中的元素的集合。定义距离d(S，T)=|S-T|+|T-S|，即E中仅仅属于S或者T中的元素个数。有时，我们允许邻域含有不可行解。例如，对于旅行销售员问题，可以允许邻域中含有删除一条边的路径。为了强调邻域中比实际路径数量更多，我们常常在搜索中给出不可行解的一个组合描述。我们将这些不可行组合结构叫做参考结构。例如，一条Hamiltonian路径可能就是一个参考结构。
邻域搜索算法（最小费用问题）可以用下面的3部分概念组成：
1) 根据具体问题定义的一个邻域图NG，NG为有向图，其每个节点对应于一个可行解
（并且/或者是非可行参考结构的例子），图的一条弧(S，T)满足T∈N(S)。
2) 每步迭代搜索邻域图的方法。
3) 确定在步骤2中选择邻域图中下一个节点的方法。我们称该节点为基解。
当S为给定邻域内的一个局部最优解，结束算法。（详情参见文献[1]）
接下来，根据距离定义两个邻域。第一个邻域为Nk(S)={T∈F:d(S，T)≤k}。我们称该邻域为k距离邻域。
对于某些问题，任意两个可行解都有相同的势。旅行销售员问题就是如此，其中每个可行解S代表了n个城市完全图的一条路径和n条弧（关于TSP详情见文献[48]）。一般的，若|S-T|=|T-S|=1，可以通过一次交换得到T；若S-T|=|T-S|=k，可以通过k步交换得到T。定义S的k步交换邻域为{T: |S-T|=|T-S|≤k}。若任意两个基本可行解都有相同的势，那么S的k步交换邻域等于N2k(S)。旅行销售员问题的一个标准k步交换邻域为2步交换邻域，又称作2步最优邻域。该问题2步最优邻域图中的任意节点为一个路径，若一个路径可以通过2步交换从另一个路径获得，则可称两者相邻。搜索邻域的方法是很详尽的（或者有捷径），下一个基本解将是一个改善了的解。
由于Nm(S)=F，则当k增大时，搜索k距离邻域将会十分困难。通常，当k不固定时，邻域呈指数增长，当原问题为NP难题时，在邻域获得最优解（或者一个改善解）也是NP难题。
3.深度变量方法
对于k=1或2，k步交换邻域（或者k距离邻域）的搜索通常十分有效，但是平均而言，结果的局部最优比较差。当k比较大时，k步交换邻域将获得更好的局部最优解，但是花费的搜索精力会太大。深度变量搜索方法是局部搜索k步交换邻域的技术。该局部搜索的目标是在大量减少搜索时间的情况下寻找目标函数与全局最优解接近的解。通常，他们并不能保证是局部最优。在很大规模邻域搜索算法中，我们对搜索部分k步交换邻域的几种算法很感兴趣。在该部分中，我们将介绍解旅行销售员问题的Lin-Kernighan算法[50]，以及解决不同组合优化问题的k步交换邻域的其他启发式深度变量算法。在下一个部分，我们将介绍当k不确定时，在多项式时间内隐搜索指数性k步交换邻域的子集的其他方法。
在介绍Lin-Kernighan算法前，先介绍一些符号。接下来，我们要介绍如何将Lin-Kernighan算法推广到解决组合最优化问题的启发式深度变量方法（和喷出链）。假定T与T’为E的子集，但是并不一定可行。从T到T’的一条路径为序列T=T1，…，Tk=T’使对于j=1到 k-1，d(Tj，Tj+1)=1。
深度变量方法依靠有下面特点的移动子程序：
1. 在每步迭代中，子程序Move创建了一个子集Tj，以及根据某些搜索准则从（Sj-1，
Tj-1）得到了一个可能的可行子集Sj。子集Tj可能可行或者不可行。这个操作用
Move（Sj-1，Tj-1）=（Sj，Tj）来表示。
2. 对于j=1到k-1，d(Tj，Tj+1)=1。
3. 根据深度变量方法，Tj通常满足其他的性质。
令T代表当前旅行销售员问题的路径，不失一般性，假定T按照顺序1，2，3…n访问各个城市。T的一个2步交换邻域可以定义为用两条边(i，k)(j，l)或(j，l)(j，k)代替(i，j)(k，l)构成另一种路径T’。注意d(T，T’)=4。2步交换邻域可以用4步操作规范描述，其中第一步从T中删除边(i，j)，第二步操作插入边(i，k)，第三步删除边(k，l)，最后加入边(j，l)。
…，vn代表G的一条n个节点的Hamiltonian令G=(N，A)代表有n个节点的无向图。令P=v1，
路。径与环（术语参见文献Glover[30]）是指可以通过向Hamiltonian路加入弧(i，j)得到的含有n条弧的生成子图，其中i是路径的末端节点。注意若i是路径的末端节点，j是路径的另一末端节点，则径与环结构为Hamiltonian回路，也等价于一条路径。若T为路径或者径与环结
构，我们用f(T)代表其总长度。
在从路径S到T路径的转移中，Lin-Kernighan启发式算法允许更换n条边，即武断地说d(S，T)等价于k=2n。算法开始时，从原路径T1删除一边得到一条Hamiltonian回路T2。此后，T2的一个末节点保持不变，直到迭代结束。选择另一个末节点开始进行搜索。偶数次操作插入一边进入Hamiltonian回路T2j，该回路与不固定的径与环T2j+1的末端节点相近。迭代的奇数次操作从当前径与环T2j-1删除一边得到一条Hamiltonian回路T2j。从任意Hamiltonian回路T2j，通过加入2个末节点可以暗中得到一个可行路S2j。在Lin-Kernighan算法结束时，得到了一个新的基本路径Si，使对于所有j都有f(Si)=f(S2j)。
下面我们将更加详细地描述Lin-Kernighan算法的步骤。在偶数次操作中加入的边是接近不固定末端节点的最短边，当且仅当f(S)－f(S2j+1)>0时加入Hamiltonian回路T2j。Lin-Kernighan [50]也给出了一种边的优化选择方法。加入Hamiltonian回路T2j的边通过最大化f(T2j)－f(T2j+2)进行选择。另一方面，在奇数次操作中删除的边由前面操作得到的径与环T2j-1唯一决定，这样将会得到的T2j是一条Hamiltonian回路。当选择要加入的边时，要考虑其他的约束。研究者考虑了不同的约束组合如先前删除的边不能够再次加入或者前面加入的边在后面的操作中不能够删除等等。最后，当考虑了所有初始固定节点的可能依然没有改善的路径时，Lin-Kernighan算法以局部最优解结束。
下面我们用一个数字例子解释Lin-Kernighan算法。考虑图１(a)中10节点的旅行路径。算法首先删除弧(1，2)得到图１(b)所示的Hamiltonian路。然后加入弧(2，6)，给出如图１(c) 所示的径与环。
图１ Lin-Kernighan算法说明
(a)10节点路径 (b)Hamiltonian路 (c)径与环
从本结构中删除边(6，5)得到一条Hamiltonian路，加入边(5，8)，得到另一个径与环。在Lin-Kernighan启发式算法中的插入边的迁移要根据累计受益的费用标准，并且删除边的迁移唯一地生成了该路结构。当考虑了所有起始节点的可能而不能形成改善解，Lin-Kernighan算法得到了一个局部最优解。
Lin-Kernighan启发式算法有几种变形可以得到质量更好的启发式解。这些算法应用一些改进如2步最优，3步最优，以及特别的4步最优操作（文献[29][41][42][50][51][52][64]）以得到基本Lin-Kernighan操作不能得到的路径。同样，运用有效的数据结构刷新路径以确保计算效率和解的质量([24][42])。Papadimitriou[54]指出根据Lin-Kernighan算法计算确定的局部最优是完全的局部搜索问题。
现在我们根据以下Lin-Kernighan启发式算法的通用过程定义旅行销售员问题的深度变量法。该过程先取一个可行路径S作为输入，之后运用前面定义的Move函数。在每步迭代中，Move函数创建一对(Tj，Sj)，其中子集Tj是可行集或者一参考结构的不可行例子。子集Sj是可行集。Move函数被调用执行r次迭代，其中r根据合适的参考规则决定。最后，深度变量搜索过程返回含有当前的最优目标函数值的可行子集Sk。
procedure Variable-Depth-Search（S）;
begin
S1:=T1:= S;
For j:=2 to r do (Tj，Sj)=Move(Sj-1，Tj-1);
选择集合Sk使Minimize(f(Sj):1≤j≤r);
end;
这种特殊的深度变量搜索依靠一种做Move的启发式算法，它从初始解开始系统地形成解的路径。该框架具有相当的柔性，有很多不同的设计程序Move的方法。如何设计Move程序的细节是一个成功的启发式算法与不太成功算法的不同之处。
在上面提到的程序中，我们假定Move每步创建了一个单一可行解。事实上，每步创建多个可行解([31][61])是可能的，或者每步均无可行解（[30][58]）。
许多深度变量法要求中间解Tj满足特定的拓扑（或结构）性质。例如，在Lin-Kernighan算法中，我们要求对于任意奇数j，Tj是一个径与环。我们同时要求对于任意偶数j，Tj是一个Hamiltonian路。我们将在下面的章节中看到Tj满足额外的非结构性的性质的例子。例如，额外性质可能要依靠指标的顺序。
Glover[30]扩展与推广了Lin-Kernighan的思想，考虑了基于经典变换路径方法的一种结构化的深度变量方法，叫做喷出链。Glover写道“粗略地看，喷出链由选择一组元素进行状态变化引起（例如，占据新位置并且或接受新的值）。变化的结果会辩识出另一个集合，他们具有以下性质，即至少有1个元素要从当前状态中被删除。状态变化步骤与删除步骤交替进行，并且每一次选择是依据前面步骤的累积效果（通常受最近的前面步骤影响，但非必然）。
喷出链的术语一般是建议性的而在有些情况下，一连串的操作可能表现出多米诺骨牌效应。
不是限制性的，这提供了一种统一的思路，连接了一系列探索过程，而不是建立一个排斥其
（这里用斜体字。） 他分类形式的狭隘的成员资格。
本文中，我们将使用下面的更严格的喷出链定义。我们将深度变量法叫做喷出链，若
I. |T1|=|T3|=|T5|=…=n，并且
II. |T2|=|T4|=|T6|=…=n+1（或n-1）
对于任意偶数j，若|Tj|=|S|-1，那么Tj可以通过从Tj-1删除一个元素得到。否则，若|Tj|=|S|+1，那么Tj+1可以通过从Tj删除一个元素得到。本文中的许多深度变量法可以视作喷出链。特别是这些方法包括不同参考结构的构建和一个规则集，以从中得到一些不同的可行解。根据我们的认识，本文中考虑的解决旅行销售员问题的所有深度变量法都可看作喷出链。
我们可以想象基于Lin-Kernighan邻域的邻域图的节点构成的路和径-环。（注意路径也是径-环的例子。）邻域图每条边的末端点将连接一个径-环。搜索技术将会是由Lin和Kernighan提出的算法[44]，选择程序将会选择已发现的最佳路径。因此喷出链的参考结构应该是在喷出链技术中邻域图的节点。若下一轮基本解比当前基本解距离更远，则该技术可以叫做深度变量法。喷出链是一种深度变量法，该方法的一个邻域是另一邻域子集（因此在从大到小的变化中，删除出一个元素）。
在上面叙述的方法中，深度变量法依靠Move函数。也可以创建使用网络流搜索的Nk的指数性子集。在这些邻域中，任何邻域都可以通过一系列适当定义的邻域图的移动得到。注意对于Lin-Kernighan算法，邻域规模为多项式级大小，正是通过搜索求得与基本解不同的解。我们将在下面的章节中介绍这些基于网络流的技术。若在喷出链（添加与删除的交互系列）与邻域元素之间有任何的天然联系，那么可以将这些技术视为喷出链技术[30][31][58]
[21]。
深度变量算法与基于喷出链的算法的应用已经成功的给出了一些组合最优化问题的优良解。Glover[30]、Rego[61]、Zachariasen&Dum[83]、Johnson&McGeoch[42]、Mak&Morton[51]、Pesch& Glover考虑了旅行销售员问题的这些算法。Rego& Roucairol[63]和Rego[62]研究了交通工具路径问题。Dondorf&Pesch[13]提出了使用喷出链的聚类算法。Yagiura等考虑了解决一般分配问题的深度变量法[80]和修订喷出链[79]。此外，Laguna[47]等将短喷出链算法应用于多层次一般分配问题。这些技术也应用于统一图的分割问题[16][20][44][53]，分类分配问题[3]，渠道分配问题[17]，以及护理日程[14]。Sourd[70]应用了一个很普通的大邻域改善程序，其中两个邻域的距离根据不相关机器的日程任务而变化。根据当前解和启发式搜索，产生局部但是较大的枚举树可以得到这些邻域。
4. 基于网络流的改进型算法
在本部分中，我们在基于网络流的算法搜索的邻域内研究局部改进型算法。用于改善邻域的网络流技术可以分为3部分：（1）寻找最低费用回路的方法；（2）最短路或者基于动态规划的方法；以及（3）基于寻求最低费用分配和匹配的方法。根据回路定义的邻域可以看作2步交换邻域的一般形式。基于分配的邻域可以看作插入式邻域的一般形式。在下面的3小节中，我们给出指数性邻域的一般定义以及应用于寻找改善邻域的网络流算法。对于很多问题，可以在一个相关图上应用网络流算法确定一个改善邻域，我们将其叫做改善图。
4.1基于回路定义的邻域
在本部分中，我们将首先定义一个一般的分割问题。然后定义2步交换邻域和循环交换邻域。
令A={a1，a2，a3，…an}表示有n个元素的集合。若每个集合Sj非空，集合之间互不相交，他们的并为A，那么{S1，S2，S3，…Sn}定义了A的一个分割。对于A的任意子集S，令d[S]
表示S的费用。那么集合分割问题就是要找到A的一个最多有K个子集的集合使
小。 ∑kd[Sk]最
设{S1，S2，S3，…Sk}为任意可行分割。若可以在不同子集交换2个元素得到{T1，T2，T3，…Tk}，那么可以称{T1，T2，T3，…Tk}为{S1，S2，S3，…Sk}的2步交换邻接点。{S1，S2，S3，…Sk}的2步交换邻域包含了所有2步交换邻接点。若按照一定次序在S的k≤K个子集
T2，T3，…Tk}，那么可以称{T1，T2，T3，…Tk}为{S1，S2，S3，…Sk}中交换单个元素可得到{T1，
的一个循环交换邻接点。令(Sh1，Sm2，Sn3，…Spk)表示k个子集的这样一种次序，要求h=p，
我们把元素的这种交换叫做循环交换。我们用表2解释循环交换。即最后的子集要与Sh1相同。
在本例中，节点9从子集S1传递到子集S4。节点2从子集S4传递到子集S5。节点3从子集S5传到S3。最后，节点14从子集S3传递到S1，循环交换结束。也可以以任意相似的方式定义一个邻接点路径。从数学上看，通过加入合适的虚节点把一个路径交换变为循环交换是很容易的。
一般的，循环邻接点的数目远大于2步邻接点的数量。当有O(n2)个2步邻接点时，固定K不变，有O(nK)个循环邻接点。若K可以随n变化，则可能有指数个循环邻接点。
Thompson[75]，Thompson与Orlin[76]， Thompson与Psaraftis[77]介绍了如何通过在一个改善图中找到一个负成本互不相交子集回路，确定循环交换邻域中的改善邻接点。下面我们将叙述一下如何构建一个改善图。令A={a1，a2，…an}表示原集分割问题中元素集合，令S[i]表示含有元素ai的子集。图G=(V，E)，若V={1，2，…n}节点集合与原问题中A的元素次序相对应，则称为改善图。令E={(i，j)：S[i]≠S[j]}，其中弧(i，j)对应于节点i从S[i]传到S[j]，并把j从S[j]中删除。对于任意弧(i，j)∈E，令c[i，j]=d[{i}∪S[j]\{j}]-d[S[j]]，即当加入i删除j时S[j]的成本增加。若对于W的任意节点对i和j，S[i]≠S[j]，即对应于W中节点的A的元素都在不同的子集中，我们可以将G中的回路W叫做互不相交子集。分割问题的循环交换与改善图的互不相交子集回路有成本保留上的一一对应的关系。特别的，对于任意负成本循环交换，改善图中有一条负成本互不相交子集回路。不幸的是，确定改善图中是否存在互不相交子集回路是NP完全问题，确定一条负成本互不相交回路是NP难题。（参考，例如，Thompson[75]，Thompson与Orlin[76]， Thompson与Psaraftis[77]）
尽管确定一条负成本互不相交回路是NP难题，存在有效的启发式算法对图进行搜索。（参考，例如，Thompson与Psaraftis[77]与Ahuja等[2]）
循环交换邻域搜索已成功应用于一些特定分割问题的组合优化问题上。Thompson与Psaraftis[77]，Gendreau等[25]和Fahrion与Wrede[19]应用循环交换邻域搜索解决了交通工具路径问题。Frangioni等[23]应用循环交换解决了最小化机器生产间隔的日程安排问题。Ahuja等[2]用循环交换得到了一种解决最小能力生成树的最佳的方法，被作为基准广泛应用。
通过确定改善图中的负成本回路确定改善解的思想也见诸其他的一些文献中。Talluri[74]通过确定相关网络中的负成本回路，确定了日常飞行分配问题中飞行支架设备类型成本节约的变化。飞行分配问题可以用多日用品流整数规划模型表示，其中约束为每种日用品表示一次飞行。Talluri考虑了仅有2种飞行班次约束下的解，并探索了可以通过交换2种航班的一些飞行次数得到改善解。他发展了一个相关联的改善图，并且证明了改善的邻接点对应于改善图中的负成本回路。Schneur与Orlin[68]及Rockafellar[65]运用重复检测和沿负成本回路发送流的方法解决线性多日用品流问题。他们的技术已经延展到基于回路的多日用品流整数规划模型的启发式优化算法。Wayne在文献[81]中给出了解决一般的最小费用流问题的回路消去算法。Firla等[22]介绍了任意2个整数规划交集的改善图。该网络中路径与回路与优化的可行解相对应。此外，该网络形成了赋权的b匹配问题的算法。Glover&Punnen[28]与Yeo[78]讨论的算法构建了优于指数性路径的旅行销售员路径。这些算法也可以看作计算隐性特别层网络的最小费用回路。我们将在5部分更加详细的讨论启发式算法。
4.2路径定义邻域（或者动态规划定义）
我们将讨论3中不同的基于最短路或者动态规划的邻域搜索算法。关于这些方法的讨论将在旅行销售员问题中进行。当应用旅行销售员问题时，可以将这些邻域搜索方法看作：（1）顺序添加和删除边，（2）当通过互换路径中2城市的当前顺序定义交换时，允许类似的多步交换，（3）在当前路径中进行循环移动。我们将详细讨论这些邻域。
4.2.1 通过顺序添加和删除弧建立新的邻接点
我们首先讨论一类通过从当前路径交替添加和删除边得到邻域的最短路算法。这些方法完全的搜索3部分中有附加约束边的喷出链邻域的子集。为了简单，我们假定路径S要按照顺序1，2，3….，n，1通过城市。利用3部分中介绍的术语，令T表示S的一个k步交换邻接点，且从S到T的顺序为S=T1，…，Tk=T。这些邻域对应于Punnen&Glover[58]在其他几个邻域中描述的奇数和偶数步路创建的试验解以及从不同路径结构构建的试验解。由奇数路径生成试验解是Firal等[21]独立提出的。下面解释，由奇数或偶数步路径产生试验解通常要考虑下面的算法：
（1） 删除边（n，1）得到Hamiltonian路T2，从节点1加入边（1，i）到节点i（其中
i>2）得到径与环T3。
当前路的末节点为节点i。删除边（i，i-1），对于i
建立Hamiltonian路，然后建立径与环结构。
检查终止标准是否符合。若是，进入步骤（4），否则，令i=j返回步骤（2）。
删除边（j，j-1）加入最后边（j-1，n）完成路径。 （2） （3） （4）
(a)
图3. 解释交替路径变换
图3解释了9节点路S=(1，2，…，9，1)的处理过程。该路径交换步骤首先删除边(n，1)，并加入边(1，4)。然后删除边(3，4)，加入边(3，7)。最后删除边(6，7)，加入边(6，9)得到新的路径T。在图3(a)中，我们用粗线表示加入的边，要删除的边在边上加入破折号。图3(b)解释了路径交换后的得到的新路径。
Firla等[21]，Glover[30]与Punnen&Glover[58]指出，通过在改善图中寻找一条奇数或者偶数长度的最短路径，该邻域中的一个改善解可以在O(n2)次操作中得到。这里，我们描述一个通过确定奇数或偶数个节点的最短路而确定路径的最佳邻接点的改善图。注意S=(1，2，3，...，n，1)是当前有n个节点的旅行销售员路径。改善图为图G=(V，E)，其中V={1，2，…，
（这样2
对应于删除边（n，1）和添加边（1，j），弧(i，j)∈E（这样1
此外，由奇数和偶数路径产生的试验解，新路径结构如断路和产生不同试验解与参考结构的逆向路可参见文献[58]。奇数和偶数路径单独产生的邻域数目为Ω(n2n)。即使是非指数性邻域，搜索邻域的加速技术也是很重要的。例如，在一个有向非循环改善图中使用最短路算法，Glover [31]在O(n2)次操作中得到了一类4步最优解。
4.2.2复合交换构建新邻域
由路径交换定义的第二类局部搜索算法是交换邻域的推广。考虑n个节点履行销售员路径T=(1，2，3，…，n，1)，通过交换节点i与j的位置(1≤i≤j≤n)得到交换邻域。例如令i=3，j=6，T’=(1，2，6，4，5，3，7，…，n，1)为交换操作下的邻域。2个交换操作交换了节点i与节点j，若max{i，j}max{k，l}，那么称节点k与l独立。那么路径T的一个大规模邻域可以通过混合（联合）任意的一些独立交换操作来定义。 (b)
Congram等[9]，Potts&Van de Velde[57]把该混合交换邻域分别应用在独立机器总负重缓慢日程安排问题和旅行销售员问题上。他们把这种方法叫做动态搜索。在他们的文献中，
并且给出了在O(n3)时间内确定出最优邻接点的动Congram等[9]证明了邻域的大小为O(2n-1)，
态规划递归表达式。Hurink[40]在单机器批量问题上应用合成交换邻域的一个特殊例子，其中只有相邻的对才可以交换，并且指出通过在合适的改善图中确定一条最短路，可以在O(n2)时间内得到一个改善邻接点。
下面我们描述一个改善图，协助搜索混合交换邻域。令T=(1，2，3，…n，1)表示n个节点的旅行销售员路径。改善图为图G=(V，E)，其中（（i））V={1，2，…，n，1’，2’，…n’}是对应于原问题节点及其复制节点的节点集，（2）E为有向弧（i，j’）∪（j’，k）的集合，其中弧（i，j’）对应于节点i和j交换，弧（j’，k）表明节点k将会是下一步交换的第一个节点。例如，G中一条有3个弧(i，j’)，(j’，k)， (k，l’)的路径表示互换节点i与j，节点k与l的2步交换操作。要构建弧集合E，要考虑V中任意对（i，j’）和(j’，k)的节点，当且仅当j>i>1时，弧（i，j’）加入E中。当且仅当j=1而且k>j时，或j>1而且k>j+1时，弧（j’，k）加入E中。对于任意弧(i，j’)∈E，我们有等于删除边(i-1，i)，(i，i+1)，(j-1，j)， (j，j+1)，加入边(i-1，j)，(j，i+1)，(j-1，i)， (i，j+1)后，旅行销售员问题最优费用净增加的相关成本c[i，j’]。换言之，若d[i，j]为原问题中从节点i到j的费用，且d[n，n+1]=d[n，1]，那么
对于j’=i+1，c[i，j’]=(-d[i-1，i]-d[i，j]-d[j，j+1]+(d[i-1，j]+d[j，i]+d[i，j+1])并且
对于j’>i+1，c[i，j’]=(-d[i-1，i]-d[i，i+1]-d[j-1，j]-d[j，j+1])+(d[i-1，j]+d[j，I+1]+d[j-1，i]+d[i，j+1])。
所有边（j’，k）的费用为0。
现在确定混合交换邻域路径的最佳旅行销售员邻接点等价于在该改善图上确定最短路，因此需要时间为O(n2)。注意由于旅行销售员问题是循环问题，其中的一个节点要在变动过程保持不变。在上面的改善图构建中，不失一般性，我们假定节点1不能够移动，因此可以通过确定从节点1’到节点n或n’的最短路搜索邻域。当应用于旅行销售员问题时，Congram等[9]给出的搜索邻域的动态规划递归式也会花费O(n2)时间。上面给出的最短路算法应用于总负重缓慢日程安排问题时要花费O(n3)时间因为要花费O(n3)时间计算弧费用。
4.2.3用循环移动方式创建一个新邻接点
本部分中最后一类局部搜索算法建立在一种循环移动金字塔路径（Carlier& Villon[8]）上。若路径从城市1开始，然后按照递增顺序一直到城市n，最后按照递减顺序通过剩余城市回到城市1，那么该路径叫做金字塔式路径。令T(i) 表示路径T中第i个位置的城市。路径T’叫做路径T的金字塔式邻接点，若存在整数 p使：
（1） 0
T(ip) 其中，i1
T(jn-p) 其中，j1>j2>…>jn-p （3） T’(p+1)=T(j1)，T’(p+2)= T(j2)，…， T’(n)=
例如，若路径T=(1，2，3，4，5，1)那么T’=(1，3，5，4，2，1)为金字塔式邻接点。注意该邻接点的一个缺点是边(1，2)与边(1，n)属于所有路径。为了避免如此，Carlier & Villon[8]考虑了给定路径的n次旋转。该邻域的大小为θ(n2n-1)，并且在改善图中运用n次最短路算法，在O(n3)时间内可以搜索完毕。
下面我们将要描述一个对于旅行销售员问题中可以通过解最短路得到最佳金字塔邻域的改善图。令T=(1，2，3，…，n，1)为n个节点的旅行销售原路径。改善图为图G=(V，E)，其中（i）
V={1，2，…n，1’，2’，…n’}对应于原问题的节点及其复制节点。（2）E为有向弧（i，j’）∪（j’，k）的集合，其中弧（i，j’）对应于节点i到j成连续顺序，弧（j’，k）指跳过节点j+1到节点k-1并把它们按照相反的顺序添加在路径的末尾。要构建弧集合E，要考虑V中任意对（i，j’）和(j’，k)的节点。当且仅当i≤j时，弧（i，j’）加入E中。当且仅当j
c[i，j’]= d[j+1，i-1]，
c[j’，k]=-d[j，j+1])-d[k-1，k]+d[j，k].
注意在计算有末节点1，1’，n，n’的边的费用时，要特别小心。现在邻域可以通过确定从节点1到节点n或n’的最短路搜索，Carlier& Villon [8]也指出若一条路为上述邻域的局部最优，那么它是2步交换邻域的局部最优。
除了这3类邻域，对于一些特殊的旅行销售员问题也可以应用动态规划确定最优解。Simonetti和Balas[69]运用动态规划的方法在特定程序约束下的时间窗口内解决了旅行销售员问题。Burkard等[6]证明了可以用PQ树表示的特殊结构路径集中运用动态规划方法，可以在多项式时间内解决旅行销售员问题。他们也指出，金字塔路径集合可以用PQ树表示，同时存在一种O(n2)算法可以计算最短金字塔路径。这些结果将在第5部分中详细讨论。
4.3 由分配和匹配定义的邻域
在该部分中，我们要讨论通过确定改善图中的最小费用分配定义的指数性邻域结构。我们将在旅行销售员问题中解释邻域。同样，我们也指出分配邻域可以用确定非双向改善图中最小费用匹配进行广义定义。我们在集和分割问题上已经证明了这种广义性。
旅行销售员问题的分配邻域可以看作由路径中删除一个节点并将其重新最优化的插入定义的简单邻域的推广。考虑n个节点的路径T=(1，2，3，…n，1)，若从城市i到城市j的成本为d[i，j]，那么搜索分配邻域的第一步是建立一个双向改善图，步骤如下：
（1） 对于某些k=[n/2]，选择并从当前路径T删除k个节点。令删除的节点为V={v1，
v2，…vk}并且剩余的节点为U={u1，u2，…，un-k}。
（2） 构建一个子路T’=(u1，u2…，un-k，u1)。令qi表示对于i=1到n-k-1每个(ui，ui+1)
的边，令qn-k表示边(un-k，u1)。
（3） 现在构建一个完全双向图G=(N，N’，E)使N={qi:i=1到n-k}，N’=V，每条边(qi，
vj)的权为c[qi，vj]=d[ui，vj]+d[vj，ui+1]-d[uj，ui+1]。
T的一个邻接点对应于通过将V中的节点插入子路T’得到的一条路径T*，最多有一个节点插入T’的邻接节点。K个弧的最低费用分配对应于T的最小费用邻域。
用图4，我们将解释9节点路径T=(1，2，3，4，5，6，7，8，9，1)的分配邻域。令V={2，3，5，8}，然后我们构建U中节点的子路如T’=(1，4，6，7，9，1)。图4解释了只有简单匹配边的双向图G。得到的新路径是T’’=(1，3，4，8，6，5，7，9，2，1)。注意当k=[n/2]时，分配邻域的大小等于Ω([n/2]!)。
图4 解释匹配邻域
分配邻域是由Sarvanov与Doroshko[66]针对k=n/2且n为偶数的旅行销售员问题首先提出的。Gutin[33]针对k=n/2给出了一个有局部最速下降算法的分配邻域搜索算法的理论比较。Punnen[60]考虑了k与n的一般分配邻域。删除路径而不是节点并按照解决最小权重匹配问题重新最优插入的邻域的拓展同样在[60]中给出了。Gutin[34]指出对于某些k值，邻域的大小可以随一些复杂性比较低的搜索邻域算法达到最大。Gutin与Yeo[37]构建了一个基于分配邻域的邻域，并指出运用该方法从任意路径T变动到另一路径T’最多要4步。Deineko与
Woeginger[12]研究了旅行销售员问题的几种指数性邻域以及基于双向图的分配和匹配的二次分配问题和基于偏序，树以及其他组合结构的邻域。基于匹配的邻域启发式算法同样被Dror和Levy[15]应用于存货安排问题。
另一类基于匹配的邻域可以通过包装子路得到，子路通常由解决一个双向最小权重匹配问题[43][59]产生。找到这种最优路径通常是NP难题。可以用有效的启发式算法搜索该邻域
[27][43][59]。应用该邻域的邻域搜索算法可以通过运用成本修订或者其他方式进一步研究以控制匹配产生。
我们下面要考虑一个基于非双向匹配的邻域结构。我们将在第三部分的一般集合分割问题的内容中讨论该邻域。令S={S1，S2，S3，…，Sk}表示集合A={a1，a2，a3，…an}的一个分割。然后构建一个完全图G=(N，E)使对于1≤i≤K的任意节点i表示S中的子集Si。现在G中边(i，j)的权重c[i，j]可以根据多种规则分别给出。一种可能的规则如下：
（1） 令子集Si对分割问题的成本贡献为d[Si]。
（2） 对于E中任意边(i，j)，连接Si与Sj中的元素，重新最优地分成两部分。令新的子
集为Si’与Sj’。
（3） 然后c[i，j]=(d[Si’]+d[Sj’])-(d[Si]+d[Sj])。
注意若含有非负权的边从G中被删除，那么该图中任意负成本匹配将会定义S的一个成本改善邻接点。Tailard将这种思想应用在一类普通的聚集问题[71]和交通工具路径问题[72]上。
5. 可解的特殊例子与相关邻域
有很多文献研究了NP难题的组合优化问题的有效解的特例。对研究者而言特别重要的是通过约束问题的拓扑结构，或者给原问题增加约束，或者两者的组合，从原NP难题中得到的特例。通过在这些有效解特例的基础上建立邻域，研究者可以形成在多项式时间内被搜索的指数数目的邻域。我们指出这其中有很多技术并没有经过验证，形成的结果也可能是比较差的局部最优解。注意在第4部分中讨论的循环移动邻域建立在寻找最低费用金字塔路径的一个O(n2)算法上。
下面的解释是关于Halin图的。Halin图是指通过在平面内嵌入所有节点的度不等于2的树并用回路连接所有叶节点，得到的图。Cornuejols等[10]给出了一个在Halin图上解决旅行销售员问题的O(n)算法。注意Halin图可能有指数数量的旅行销售员路径，如图3所示（参见
[10]）。
下面我们将介绍如何应用Halin图建立旅行销售员问题的很大规模邻域。假定T为一个路径。若H为Halin图且T为H的子图，那么我们称H为T的一个Halin拓展。图5解释了路径T=(0，1， 2，…， 9， 0)的一个Halin拓展。假定有一个有效的程序HalinExtend(T)，它可以创建T的Halin拓展。为了创建邻域N(T)，可以令H(T)= HalinExtend(T)，然后令N(T)={T’:T’为H(T)中的路径}。要在该邻域中寻找最佳路径，可以寻找H(T)中的最佳路径。在理论上，可以定义一个更大的邻域：N(T)={T’: 在T’中存在T的Halin拓展}。不过，由于该邻域要同时最优化T的Halin扩展，因此进行有效搜索非常困难。类似的基于Halin图系统的瓶颈旅行销售员问题和斯坦树问题可以通过分别运用Philips等[56]和Winter[82]给出的线性时间算法建立。 图5. Halin图
(a)10节点路径 （b）Halin拓展
在前面的例子中，我们考虑了金字塔路径，它可以看作附加约束的旅行销售员问题。我们也考虑了约束于Halin图的旅行销售员问题。在下面的例子中，我们将要考虑[28]同时依靠图的严格约束和额外边界约束的邻域。Glover与Punnen[28]确定了下面的路径种类，其中最佳的可以在线性时间内找到。令C1，C2，…，Ck为至少有3个节点的顶点不相交的k个回路，这样每个节点在一个回路中。一条单边删除路径是指具有如下性质的路径T：
1. 对于i=1到k，|T∩Ci|=|Ci|-1，即T与Ci有|Ci|-1条共同弧。
2. 对于i=1到k-1，T中有一条有向弧从Ci到Ci+1，从Ck到C1。
从回路中删除弧的方法最少为∏|C|，这可能意味着指数数目的大小，因此单边删除ii
路径的数目为指数大小。要确定最优单边删除路径，研究者可以解改善图上的一个相关最短路问题。运行时间为弧数目的线性函数。给定一条路径，可以删除路径上的k+1条弧，创建k条路径，然后将这k条路径变成前面叙述的k条回路。原则上，上面的邻域搜索方法很容易执行；不过搜索技术的质量很可能对执行的细节很敏感。Glover与Punnen[28]也考虑了更宽的邻域，包括他们所谓的“双删除路径”。他们也提供了最优化该类路径的有效算法。
Yeo[78]考虑了非对称旅行销售员问题的另一种邻域。他研究的邻域与Glover和Punnen
[28]的研究有一定的关联，但是规模却非常大。他指出，该邻域的搜索时间为O(n3)。Burkard与Deineko[7]确定了另一类指数性邻域，这样其最佳解可以在二次项时间内确定。这些方法都可以用来建立很大规模邻域搜索算法。不过，根据我们的了解，尚未有此种算法。
我们用一个一般性的方法总结本部分的结果，该方法将约束问题的求解方法移植到很大规模邻域搜索技术上。令X代表一类NP难题的组和优化问题。假定X’为在多项式时间内可解的X的约束。进一步假定对于X的实例(F，f)，对于F中的任意可行子集S，存在能够建立X’的实例（F’，f）的良好结构的子程序 “CreateNeighborhood(S)”，满足：
1. S是F’的元素
2. F’为F的子集
3. （F’，f）为X’的例子
我们把F’叫做S的X’诱发邻域。邻域搜索方法包含在每步迭代中调用
“CreateNeighborhood(S)”，然后运用多项式时间算法优化（F’，f）。然后用（F’，f）代替S，算法进行下一步迭代。特别要关注的是，当子程序CreateNeighborhood在多项式实践中运行，而且F’为指数性的情况。邻域就不能够明确的建立起来。当我们相信该方法在邻域搜索上有足够的潜力时，这种潜力就很大程度上没有实现。此外，许多情况下并不清楚如何发挥这种潜力。例如，当约束于混联图时，许多NP难的组合优化问题在多项式时间内是可解的。例如包含网络可靠性问题[67]，最优连通生成树问题[18]，定点覆盖问题[5][73]，反馈顶点几何问题[5][73]等等。有特定程序约束的工作日程安排问题[46]也有类似的结果。在邻域搜索中如何针对混联图最好地利用有效算法是一个有趣的开放性问题。
6.邻域指标
在该部分中我们将描述可能有助于改善给定邻域局部搜索算法性能的邻域指标。前面提到，邻域搜索启发式算法的设计中一个关键问题是邻域的大小与搜索邻域所用时间之间的平衡。因此一个重要的邻域指标是邻域大小。根据邻域图，给定一个解S的邻域，其大小可以视为从S离开的有向弧的数量，或者说等于S的输出度数。对于深度变量法，邻域大小不一定是指数性的，是搜索使得得到的解大大不同于基本解。另一方面，对基于网络的方法和可解特例诱发的手段，邻域大小是指数性的。
下面的表格总结了前面讨论的旅行销售员问题的邻域大小（本表基本上来源于[6]）：
邻域
2步最优
k步最优
金字塔式
循环移动式
边缘删除
基于最短路的边缘删除 大小大小) 搜索时间参考文献 Ω（n2） Ω（nk） Ω（2n） Ω（n2n） Ω((12n)1/3) Ω（n2n） θ(log n) θ(log n) θ（n） θ( n) θ( n) Ω ( n) O(n2O(nkO(n2) O(n3) O(n) O(n2)
循环交换（固定k子集）
混合交换
基于匹配1
Halin图
PQ树
θ（nk） θ（2n-1） θ（n!/2） 2(n loglog n) θ( log n) θ（n） θ( n log n) θ( n) θ( n loglog n) O(n2) O(n2) O(n3) O(n) O(n3) Ω（2n） Klyaus [45] Carlier & Villion [8] Glover & Punnen [28] Punnen and Glover [58]， Glover [30] Ahuja et al. [2] Potts &van de Velde [57] Sarvanov & Doroshko [66] Cornuejols et al. [10] Burkard et al. [6]
文献研究的另一个邻域指标是邻域图的直径。邻域图中节点S到节点T的距离为从S到T的最短路长度。邻域图NG的直径为对于NG中的节点S，T，满足d(S，T)=d的最小正整数。Gutin与Yeo[37]建立了对应邻域图直径为4的旅行销售员问题的指数极大小的多项式可搜索邻域；即，对于任意路径对T1和T5，存在路径T2，T3和T4，满足Ti∈N(Ti-1)，i=2，3，4，5。Carlier and Villon [8]考虑的基于循环移动的邻域直径为θ(log n)。
对于给定的邻域图，若对于j=2到k，目标函数f(ij)
最后我们考虑邻域搜索算法的控制分析。启发式算法的控制分析分析了受其支配的该算法产生的解的数量。令α表示产生F中一个解S*的组合优化问题的一个启发式算法。α的控
是集合F(S*)的势，其中F(S*)={S∈F: f(S)>=f(S*)}。若dom(α)=|F|，制数目，用dom(α)表示，
那么S*为一个最优解。旅行销售员问题不同搜索算法的支配分析可参阅文献[27]，[28]，[35]，
[36]，[38]，[59]和[60]。
7.很大规模邻域搜索算法的计算性能
在本部分中，我们将简要讨论前面提到的很大规模邻域搜索算法的计算性能。首先我们考虑旅行销售员问题。Lin-Kernightan算法及其变形被广泛认为是解决旅行销售员问题的最佳启发式算法。在一项大量的计算研究中，Johnson与McGeoch[42]通过提供一个详细的性能对比分析证明了这一点。Rego[61]对旅行销售员问题运用了一类结果甚好的删除链算法，这也表明了他的算法优于原Lin-Kernightan算法。Punnen与Glover[58]运用了一种给予最短路的删除链算法。Rego[61]与Punnen和Glover[58]直接相关，并运用了简单的结构。
1. 这里假定k=[n/2]，节点已删除。若删除更少的节点，邻域的大小相应的减少，那么时间限制将会更好。
最近，Helsgaun[39]报告了根据一个复杂的Lin-Kernightan算法得到的给人印象深刻的计算结果。尽管该算法运用核心的Lin-Kernightan深度变量搜索算法，它在几个关键方面不同于前面的算法。更优的计算结果原于有效的数据处理，特殊的5次最优操作，新的非顺序操作，有效候选列表，成本计算，元素成本上界的有效运用，Held与Karp 1次树的信息，以及灵敏度分析，等等。Helsgaun报告说他的算法给出了最优解已知的所有测试问题的最优解，包括Applegate等[4]考虑的7397城市问题与13509个城市问题。Helsgaun估计他的算法的平均运行时间为O(n22)。按照这种观点，注意到Applegate等[4]运用分枝定界法确定13509个城市问题的最优解要求一组3位α服务器4100（有12个处理器）和一组32奔腾II个人计算机花费3个月的计算时间。另一方面，Helsgaun运用了一个300MHz的Power Macintosh G3。对于85900
（我个城市的问题，TSPLIB的pla85900，Helsgaun用了2周的CPU时间得到了一个改善解。
们也注意到Applegate等[4]花费的大量时间是为了证明最优解的确是最优的。）
在表1中，我们总结了针对旅行销售员问题小例子的Rego算法[61](REGO)，Helsgaun-Lin- Kernightan [39]算法(HLK)，Mak与Morton[511]的修订Helsgaun-Lin-Kernightan算法和Punnen与Glover[58](SPG)的最短路算法的性能。在表中，我们运用了这些算法的最佳情形。
表1 旅行销售员问题的小例子：最佳解偏离最优解百分比
在表2中，我们总结了针对旅行销售员问题大例子的Rego的算法(REGO)[611]，Helsgaun-Lin-Kernighan算法(HLK) [39], 以及Johnson等Lin-Kernighan算法(JM-LK)[42]（错误，参考文献没有找到）的性能。在表中我们运用了这些算法的平均偏离百分比。
表2 旅行销售员问题的大例子: 一些运行时间内的平均偏离百分比
下面我们考虑赋能的最小生成树问题。这是第4部分讨论的分割问题的特例。Ahuja等[21]运用该问题结构，构建了基于循环交换邻域的很大规模邻域搜索算法。该算法非常有效，对于许多基准问题能够得到改善解。当前，该算法能够获得基准集合中列示的任意例子的最佳可得解，基准集合可以参阅http://www.ms.ic.ac.uk/info.html。
我们最后考虑解决一般分配问题(GAP)的大规模邻域搜索算法。Yagiura等[80]建立了基于删除链解决GAP的禁忌搜索算法。他们指出在合理的计算时间内，得到的解优于或者与现行解法的解可比。根据计算试验与对比，可以知道他们的算法解决基准问题的例子与最优解的偏离百分比小于16%。
本文中引用的许多文献同时也给出了根据算法计算的结果。详情请参阅这些文献。文中涉及的几种大规模邻域并没有在搜索框架内进行实验证明。该种和相关的邻域的有效执行是要深入研究的课题。
致谢：
第一作者的研究得到NSF DMI-9900087的支持。第二作者和第三作者部分由NSF DMI-9810359和DMI-9820998支持。第四作者由NSERC OPG0170381支持。
参考文献