第13章 Very Large-Scale Neighborhood Search（未完待续）

Lin–Kernighan Search for the TSP

: 有一个顶点的度为3，一个顶点的度为1，其与顶点的度为2（一个环+一条尾巴，如上图中的“After”）
center：度为3的顶点（右图图中的“E”）
target edge：具有唯一性，1）在环中，2）有一个顶点是“center”，3）不是上一次迭代添加的边（如图中的（E, F）），target edge其实指在构造TSP环或下一个时将要被删除的边。
completion edge：具有唯一性，当target edge被删除时，可以完成TSP环的那一条边（如图中的边（B,F））
注：上图为无向图

Cyclic Exchange Neighborhood Search Algorithms(太难了,看原文会更好)

设计VLSN搜索算法的一个常见策略，是将寻找同时执行的改进移动集的问题建模为网络流问题。回路交换邻域搜索算法是VLSN搜索算法中的一个突出的类别，其主要方法是在辅助网络中计算最小代价不相交回路子集来寻找改进的移动集。

基本概念

partition transfer：各个子集的元素的个数可以发生变化
cyclic exchange：各个子集中的元素不变
path exchange: cyclic exchange去掉一条边（一个子集的元素增加一个，一个子集的元素减少一个）
cyclic exchange neighborhood：
path exchange neighborhood：

Finding Improving Cyclic Exchanges

improvement graph

Cyclic Exchange Neighborhood Search for the VRP

Example: Cyclic Exchange Neighborhood Search for the Capacitated Minimum Spanning Tree Problem

Other Very Large-Scale Neighborhood Search Algorithms

• Neighborhoods Based on Compounding Independent Moves
  • independent insertion 指两个插入动作互不影响，如中将插入到前，将插入到前，那么这两个插入操作互不影响，结果为，这两个插入操作时互相独立的。如将插入到前，将插入到前，结果为这两个插入操作就不是互相独立的。
  • CIM: compounded independent move

• Neighborhoods Based on Variable Fixing：在求解时固定一些变量的值

  tricks of the trade

• constructing negative-cost subset-disjoint cycles

• updating objective value
• updating improvement graphs
• approximating edge wweights in the improvement graph
• imcorporating composite cyclic exchanges（见下图）
• using VLSN search selectively
• relaxing the subset-disjoint condition