Ruin&Recreate算法

在解决 NP 问题的时候，采用启发式算法是目前比较可行的方案，2017到2018两年，在公司实现了两个此类的算法，分配解决 VRP（车辆路由） 和 CLP （容器装箱），使用的核心算法就是这里的 Ruin&Recreate 算法，算法本身也并不复杂，却很有用。

1. 先假设拿到一个VRP问题，并且已经基本构建了初始的路径。
2. Ruin步骤，从其中移走一些点，这些点认为已经不需要进行运算了，然后连接剩下的点，可以得到一个更短距离的线路
3. Recreate步骤，将刚才移除的点，再加入到整个线路中，构建出新的额完整线路，这个步骤是最为困难的

第一个需要作出的选择就是，我们是否接受一个新的结果（Recreate）之后的结果，还是保留之前（Ruin）之前的结果，

1. 只接受更好的解决方案（贪心）
2. 模拟退火（SA）
3. Threshold 接受（轮盘）
4. 大洪水（类似登山算法，需要邻居都大于tolerance)

对于简单的场景，比如Travel Salesman 问题，只需要很小改变就可以解决问题，因为原问题的初始解一般很接近最优解。

对于复杂的场景，则有更多的问题

1. 不均衡，一个很小改变，却可能带来非常大的变化。变化是不连续并且不均衡的，这意味着不可预测
2. 很难找到一个可接受的解，复杂的问题（拥有多个目标函数，和约束条件）一般伴随着大量的约束，约束越多就越难找到一个可行解。就算找到一个可行解，其领域解（小步骤移动带来的解）也经常是一个不可行解，找到一个可行解并将其移动到写一个可行领域解，非常困难。很多算法通过惩罚函数来避免不可行解，但这样会排除掉所有稍微不可行的解，这对找到更优的解显然是不利的。

在R&R算法中，我们采用更大范围的变化，来代替小范围的变化，然后尝试最佳的Recreate手段。我们有理由相信，通过更大规模的变化，我们有更多优化空间，从而找到一个可行解。从而解决此类非连续问题。

改变： 改变可以带来更好的结果，选择改变策略非常重要

1. 交换领域搜索，通过交换路径之间的两个点，或者路径内的两个点，得到一个更好的解
2. 插入领域搜索，从当前路径，或者其他路径选择一个点插入到当前路径，得到一个更好的结果
3. 2-0pt领域搜索，选择两条路径（四个点）减除其中的两条边，并重新插入两条边，构成新的连通图，得到一个更好的结果
   
   一些常用的算法
4. 模拟退火算法，不会基于之前的做过的计算进行计算。而是每次都重新计算，和之前没有联系。
5. 遗传算法，基于之前的计算，进行变换，不同遗传算法在于基因的选择和变化方法的不同
6. 禁忌搜索，通过禁忌表，避免重复搜索
7. Searching for backbones，如果两次搜索后，解中有部分是不变，则认为这部分已经经过了大量的优化，将其视为最优解，之后的计算不再变换。从而逐步减少搜索范围。

R&R算法概述

Ruin 步骤，前面已经提到了，目标是用一组需要服务的站点（集合 T ）中现在一部分站点。构建出一个不包括这些服务站点（集合 B ）的解。
Radial Ruin : 从T中的N个节点，随机选择一个节点 c ，选择一个随机数 A 是的 A <= [F * N] 其中 0 < F < 1，将 c 以及和它最近领的 A-1 个点，从 T 移到集合 B中。最邻近的定义可以使用一套确定的规则，在VRP问题中，我们选择欧几里得距离。 Random Ruin：随机选择 A <= [F*N] 0 <= F <= 1个节点从T移动到集合 B中。和 Radial Ruin 相比，Random Ruin 是全局的随机策略，而 Radial Ruin 是局部策略。 Sequential Ruin：随机一个节点c，以及一个随机数 A，从 c 算起的 A-1 个随机数，都从T移动到 B中。

Recreate 步骤，Recreate 步骤，将B中的节点，重新添加到T中，并且添加之后需要满足限定条件的约束。并且对应的成本要最低。 从B中按照随机的顺序取出节点，并对所有的车辆询问，是否可以承载该节点，已经承载之后带来的成本增加。如果可以则选择成本最小的车辆加入。如果所有的车辆因为容量或者时间窗限制，没有办法满足，则需要新加入车辆。

1. 从一个初始解开始
2. 选择 Ruin 模式
3. 从 T 中选择 A 个节点准备移动到 B 中
4. Ruin
5. Recreate
6. 使用决策规则，决定是否接受新的解，如果接受，则使用新的解作为初始解执行（2），如果不接受，使用旧的解重新执行（2）

对时效的考虑，假设有一组客户 C1，C2，…… Ck，（C1和Ck为虚拟的起始点），

1. 设 Ci(first) 和Ci(last)为Ci允许开始服务的最早和最迟时间。
2. Ci(job)为服务时间，起始点这个值为0
3. 现在假设Ci(early)和Ci(late)表示Ci在实际线路中，可以开始的最早和最迟时间。如果时间窗有冲突，则当且仅当Ci(early) > Ci(late)
4. 从Ci到Cj的时间为d(Ci,Cj)
5. 当Ci新加入到线路中的时候，初始化Ci(early) = Ci(first)以及Ci(late) = Ci(last)，之后early和late的值会同步重新计算

Ci(early)，会取Ci最早可以开始的值，与，上一个点到当前点也就是Ci-1到Ci的最早事件（Ci-1的最早开始时间+Ci-1的作业时间+行驶时间）中较大的值，作为在线路中i点最早可以开始的时间。同样的Ci(late)可以计算为
for i := 2 to k do Ci(late) = min { Ci(late) , Ci-1(late) + Ci-1(job) + d(Ci-1,Ci) }. 也就是取当前点最迟开始时间，与，上一个点最迟开始时间+作业时间+行驶时间，中较小的值 如果实现 Ci(early) > Ci(late) 则出现了时间冲突。

当在Ruin步骤中，移除一个节点Ci，之后剩余线路的时间窗也需要重新计算

原理大致相同，不再赘述

另一个问题是怎么找到满足我们期望车辆数目nT的解。这里使用一个巧妙的方法，对每一辆超过nT数量的车，都分成50个单元，同时这些使用这些单元的成本（因子为5），这样如果必须使用nT的车辆则结果不会有变化，但是如果可以使用少于nT的车，那么计算就会被引导到更少车辆的方案。

最后提到一点，对于复杂问题的优化，简单的变换比复杂智能的组合变换更好，使用CPU的计算时间可以计算几百万次简单并且快速的变换，而不是采用混合的智能变换，其会消耗很多的计算时间，数千次的简单变换会优于一次复杂的变换。