【DCVRP】元启发式算法进一步优化

本文主要是介绍【DCVRP】元启发式算法进一步优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

为什么加入元启发式算法？

DCVRP-IMGR的求解质量可以快速的达到10%之内，但在DCVRP_IMGR生成方案完成后至下一个动态事件发生之间存在一段时间，当动态事件发生的非常频繁，这段时间可能会非常短暂，然而动态事件发生得不是太频繁或者存在2个动态事件时间较长的情况下（这在实际配送中是比较常见的），这段时间的长度可能就足够采用更复杂的元启发式算法，以进一步改进DCVRP-IMGR生成的方案。

改进算法的主要指标是什么？

在求解大规模动态车辆路径问题，对算法的求解速度要求非常高。已经提出的 DCVRP-IMGR 能够迅速地产生质量满意的可IMGR产生的方案。该改进型算法应具有如下特点：
①算法的速度非常快；
②算法能够在任何指定时间终止；
③算法中的参数尽可能少。

对照下述的几种主流元启发式算法的特点发现，这些算法与要求的算法具有一定差距，因此，以车辆路径问题中的改进可行解的基本操作算法k-opt为基础，设计了一种具备上述特点的混合大邻域算法。

一、常见的启发式算法

1.1、模拟退火SA

1.2、遗传算法GA

1.3、蚁群算法ACO

step1 : 初始化个参数，输入系统基础数据，设找到的最优解 $L * = M A X - R L T$
step2: 将M个蚂蚁随机均匀的放到N个结点上，得到节点i的蚂蚁集S_i和蚂蚁数b_i, 初始化蚂蚁k的已走点集allowed_k ;
l表示已完成任务的蚂蚁书，l=0;
初始点为0的蚂蚁的过程变量Pro[k]=1, 初始点为非0点的蚂蚁的过程变量Pro[k]=2;
Step3：在结点i取蚂蚁k，判断其初始结点。
若为0点，按转移规则确定结点j，更新 tabu_k、S_i、b_i。
并且若 Pro[k］ =1，则 Pro[k］ =2，转Step3；而当 Pro[k］=2 时，若j点为初始结点，则 l++，转 Step3，否则转Step4。
若为非0点，则按转移规则确定转移结点j，更新 tabu_k、S_i、b_i。
并且当Pro[k]=1 时，若j点为0，则 Pro[k]=2，转Step3；当Pro[k] =2时，若j点为初始结点，则l=l+1，转Step3，否则转Step4；
Step4：更新S_j，重复Step3-4直到该结点的蚂蚁数量b_i=0为止；
Step5：重复Step3-5，直到所有结点的b_i=0;
Step6：在所有蚂蚁都移动一次后，按局部更新规则对所有路径的信息素进行更新；
Step7：更新所有结点的b_i，若所有结点上蚂蚁数量b_i=0或l=M，转下一步，否则转Step3；
Step8：由各蚂蚁的 tabu;得到路径集L={L1，L2，……，Lm}，在L中寻找可行解，得到可行解集A={A1，A2，……，Ap,}；
若未发现可行解，实施多周期蚂蚁组合策略生成L-ch子回路集，再在L-ch中寻找可行解。
若仍未发现可行解，则采取近似解可行化策略，转下一步；
Step9：采用爬山法对可行解集A中各个可行解进行局部优化，得到A’，计算本次搜索到的最优路径L*（k），
并得到迄今为止的最优路径，L*=min{L*（k)，L*}；
Step10：若算法陷入停滞，采用负反馈机制调整路径上的信息素，并调大ro，否则按全局更新规则进行信息素的全局更新；
Stepl1：判断k是否等于最大迭代次数k_max，若是，则算法终止，输出L*；否则，k++，转Step2。

1.4、粒子群算法(PSO)

在这里插入图片描述

1.5 、禁忌搜索算法TS

在这里插入图片描述

二、算法改进的可行性

改进车辆路径问题的可行解的基本规则分为2类：

任意两车辆路径建的操作规则 Inter-operator
- Swap
- Exchange
- Cross-Exchange
- inter-relocate
车辆路径内的操作规则Intra-operator
- intra-relocate
- or-opt
- k-opt
其中，k-opt的k是大于等于2的变量，因此k-opt是在上述operator中最为复杂的一种操作规则，也是最常用的一种操作规则。由于k-opt的复杂度为 $O(n^k)$ ,因此k的取值不适宜太大，一般常用的大小是取2或者3，否则速度会非常慢。但当k的取值为2huozhe 3时得到的可行解可能是质量比较低劣的局部最优解。中的来说，k-opt是元启发式算法中的关键部分，有效的设计和谁用k-opt是设计有效的启发式算法的重要内容。

从解的邻域空间的角度分析k-opt算法的性能，如图4.7所示k-opt算法的规则是：删除某车辆路径中的k条边，再添加k条新边（可以和已删除的k条边中的部分边重复）得到一个新的解。

解邻域空间的概念是一个可行解通过执行1次某种操作规则可得到的其他可行解的集合。因此，解邻域空间是一些可行解的集合，且不同的操作规则能够唯一的确定该集合中的具体元素。解空间的概念是某问题中所有可行解的集合。

三、基于复杂网络的k-opt算法解空间表示

如果想提高算法，了解解空间结构是一个很好的突破口。使用节点表示可行解，边表示可行解之间的领域关系。然后通过计算法复杂网络的基本指标分析算法解空间结构，其目的是得出优秀算法的解空间结构所呈现的特征，基于分析结论设计一个算法使其解空间呈现这种特征，最终使设计的算法性能具有竞争力。 这思路太牛逼了吧 👍

3.1 符号表示

VRP是一个配送问题，车辆从配送中心出发服务n-1个顾客后再回到配送中心。其可能路线的数量，等价于一个具有n个城市的TSP问题。

那么使用opt算法改进车辆配送路线，等价于k-opt算法用于改进TSP的性能。
符号定义如下：

规模n:
可行解数量N:
解空间 $\Omega$ : 等于 $\{\pi_1, \pi_2,\pi_3,\cdots,\pi_N\}$ ,其中， $\pi_i$ 表示解空间中的一个可行解。
$\pi_i$ ：可行解表示为一维数组；设有5个顾客( $n = 6$ ),路径为包含6个数字的数组0-1-2-3-4-5，即有 $\pi_i[0]=0,\cdots,\pi_i[5]=5$ .若假设路径没有方向性，即上述解与0-5-4-3-2-1为同一解。
$L(\pi_i)$ :可行解的路径长度
$\omega(\pi_i)$ :可行解 $\pi_i$ 的领域解空间
$\pi^*$ :最优解，或称全局最优解
$\pi_i^*$ :解 $\pi_i$ 的领域空间中的最优解，或称局部最优解