问题描述：Capacitated Dispersion Problem
给定一个图$G=(V, E)$，每个节点有其“容量”$c_i$，节点两两之间有“距离”$d_{ij}$。要求：选出若干节点组成节点集$M$，使得被选中的节点容量之和大于或等于要求的容量大小，同时尽可能使节点分散开，也就是将被选中的节点之间的距离的最小值最大化。
目标函数：距离的最小值最大化
约束：
$B$是要求的容量，$M$是被选中节点的集合，用$x_i$来表示第$i$个节点是否被选中，选中为1，否则为0。
已有算法
Simple Greedy Heuristic
Strategic Oscillation (GRASP + VND)
Scatter Search
缺点：大算例效果差，计算时间长
总体框架
2-5 禁忌表初始化
6-7 贪婪构造初始解
9-10 邻域搜索及更新局部最优解（使用禁忌表）
12-14 目标函数比较及更新全局最优解
15-17 更新禁忌表
初始化
随机选一个初始点，接下来随机选一个离该点最远的点。
继续随机选离已选中的点最远的点，直到容量满足要求
局部搜索
三个操作：Add，Drop，CSwap
Add
选中一个未被选中的点。
Drop
移除一个已被选中的点。但移除后必须保证满足约束条件（容量要求）。
CSwap （创新点）
进行精选的Swap操作，不是考虑交换$M$和$V \backslash M$中的元素的所有的情况（太多了），而是只考虑一部分。
考虑的部分是：对于$M$，考虑最短边的端点；对于$V \backslash M$，考虑距离$M$最远和次远的点。所以实际上需要考虑的点不多。
选出这三个邻域得到的最优解。
目标函数快速计算（创新点）
注意：目标函数$f(M)$就是指被选中节点集中节点之间距离的最小值，也就是最短的那条边的长度。
仅在必要情况下才通过遍历的方式重新计算目标函数。
Add
计算Add的点到$M$的距离$d$，如果这个距离不大于原解的$f(M)$，那么$f(M)$不变，否则变为$d$。
Drop
Drop了一个点，会删除至少一条边，计算这些被删除的边长度的最小值$d$，如果这个距离大于原解的$f(M)$，或者剩下的边里还有距离为$d$的边，那么$f(M)$不变，否则需要重新计算。
CSwap
可以看成一次Add和一次Drop，同上
禁忌表相关
Hash functions（创新点）
$\beta_k$是作者自定义的参数 300 400 500
计算结果
参数$\beta_k$
随机初始化和贪婪初始化
和前面提到已有算法的对比