一种求解多车场带时间窗车辆路径问题的变邻域搜索算法

摘要

本发明提供一种求解多车场带时间窗车辆路径问题的变邻域搜索算法，在局部搜索过程中采用or-opt和2-opt混合算子进行局部搜索；将模拟退火算法模型中的Metropolis准则引入到VNS算法的基本框架中，用于在一定条件下接受部分较差解，以减小算法陷入局部最优的可能性，从而提高算法的可靠性；在算法框架中加入后优化过程，使算法的求解质量和收敛速度都得到一定程度的提高。

主权项

1.一种求解多车场带时间窗车辆路径问题的变邻域搜索算法,其特征在于步骤如下：（1）多车场带时间窗车辆路径问题有车辆载重、服务时间窗和车辆最长行驶时间的限制，在所有客户点的可能排列中，绝大部分对应的都是不可行解，许多算法在求解带有负载或时间窗等约束条件的车辆路径问题时，通常在求解过程中都只保留可行解，而将不可行解舍弃，但值得注意的是，在这些不可行解中，有可能存在少数的不可行解，即经过一定次数的迭代过程后能求得质量更好的可行解，鉴于此，本算法模型在求解过程中允许不可行解的存在，以使得算法具有更广阔的搜索空间，进而增大算法求得更优解的可能性；在本算法模型中，解的评价函数表示为f(x)=c(x)+αq(x)+βd(x)+γw(x)，其中α、β、γ为惩罚因子，且α>0，β>0，γ>0，对于解x来说，令c(x)表示车辆总的行驶距离或时间，令q(x)表示车辆总的载重违反量，令d(x)表示车辆总的行驶时间违反量，令w(x)表示车辆总的时间窗违反量，在计算车辆经过单条路径R的行驶时间违反量时，本文引入了由Savelsbergh提出的向前时间松弛ForwardTimeSlack的概念，用于对行驶时间违反量进行相应的优化；（2）本算法在初始解的构造阶段采用三标准聚类算法，依据客户的地理位置和时间窗大小将客户分配到特定的车场，并规划路线，进而生成初始解；（3）Shaking过程主要依据事先定义的邻域结构集合对解的结构进行一定的调整，以充分扩展当前解的搜索空间，减小算法在后续求解过程中陷入局部最优的可能性，对于Shaking过程而言，邻域结构集合的构造在很大程度上决定着变邻域搜索算法的求解效率以及逃离局部最优的能力；MDVRPTW的解是有多条路径组成，而每条路径都看成是客户节点的有向序列，在求解MDVRPTW时，本算法引入两种交换算子，分别为Cross-exchange和iCross-exchange，并利用这两种算子对当前解中的两条路径进行信息交互，进而产生新解，每次执行Shaking过程时，MVNS算法将从上述两种算子中随机选择一种用于路径交换，令参数p_icross表示iCross-exchange被选取的概率，则Cross-exchange被选取的概率为1-p_icross，值得注意的是，p_icross的取值一般比较小，这主要是因为MDVRPTW的解是具有方向性，因而在路径交换过程中应尽量保持子路径的原有方向以增大求得可行解的可能性；参与路径交换的两条初始路径、相应子路径的起始位置以及子路径的长度都需要通过当前解的邻域结构来确定，一般情况下，变邻域搜索算法都会采用多个邻域结构来提高算法的求解质量和稳定性，该集合由12个邻域结构组成，而且每个邻域结构都指定了参与路径交换的车场数以及子路径的最大长度，其中C_r表示分配给路径r的客户个数，由于MDVRPTW存在多个车场，用于路径交换的两条路径既从同一车场内选取或从不同的车场中分别选取，子路径是从选定的路径中随机选取出来的一段序列，其长度不能超过邻域结构规定的最大长度，在所有的邻域结构中，每个在其规定范围内的子序列长度被选择的概率都是相同的；（4）在本算法模型中，局部搜索过程将对Shaking过程中产生的新解x_s的邻域空间进行搜索以求得局部最优解x_l，在Shaking过程结束后，由于MDVRPTW的当前解x中只有两条路径发生改变，而其余路径均保持不变，因此LocalSearch过程只需要对这两条路径分别进行局部搜索，LocalSearch过程在整个VNS算法框架中是耗时最多的部分，而且在较大程度上决定着VNS算法最终的求解质量，因而在设计局部搜索算法时需要充分考虑到算法的求解效率，在本算法模型中选取了2-op和or-opt作为局部搜索算子，以便能在较短的时间范围内求得质量较好的局部最优解，值得注意的是，每次的局部搜索过程都只采用一种算子，两种算子通过随机的方式进行选取，其中，参数表示2-opt被选取的概率，相应地Or-opt被选取的概率可以表示为1-p_2-opt，采用这种混合算子的方式较为充分的结合2-opt和Or-opt两种算子的寻优能力，并且能在一定程度上拓展算法的求解空间；（5）为了在一定程度上加快算法的收敛速度，并提高算法的求解质量，本算法在求解过程中引入了后优化过程，在局部搜索完成之后，如果得到的局部最优解x_l优于全局最优解x_b，即，f(x_l)<f(x_b)则继续对x_l进行后优化操作以寻求更好的全局最优解，本算法中的后优化操作选用由Gendreau提出的US算法，该算法适用于求解带时间窗的旅行商问题和车辆路径问题；（6）在定义MDVRPTW的解的评价函数时，引入了车辆的载重违反量、行驶时间违反量以及时间窗违反量，并对这三种违反量设定了相应的惩罚因子，而在实验求解过程中，这些惩罚因子通常设定为较大的常数，以便使得算法迭代过程中更趋向于向可行解收敛，但这样做同时也使得算法容易陷入局部最优，本文通过采用在求解过程中接受部分较差解的方法来增大对求解空间的扰动，以减小算法过早陷入局部最优的可能性；本算法模型通过引入模拟退火算法模型中的Metropolis准则来控制算法在一定条件下接受较差解，其接受策略可描述为以下内容：令x表示当前解，x_l表示x经过Shaking和LocalSearch操作后最终得到的局部最优解，f(x_l)和f(x_b)分别表示解x和x_l评价函数值，令Δf=f(x_l)-f(x)，当Δf≤0时，对x_l作后优化操作得到解x_po，接受解x_po并更新当前解x，即x=x_po；当Δf>0时，以一定的概率(e^-Δf/T)接受解x_l并更新当前解x，即x=x_l，本文对温度采用线性冷却的方法，在初始状态下T=T₀，而每迭代iter_T次T便减少(T₀iter_T)/iter_max，其中，T表示当前温度，T₀表示初始温度，iter_max表示MVNS算法总的迭代次数；（7）本算法各个参数的设置：算法总的迭代次数iter_max设置为10⁷，惩罚因子α、β、γ取值为α=β=γ=100，参数p_icross取值为0.1，P_2-opt最终选定为0.5，T₀的取值为5，iter_T=1000；（8）通过采用Cordeau算例来评估本算法在求解MDVRPTW上的性能，Cordeau算例是由Cordeau、Laporte和Mercier设计的20个MDVRPTW算例，并从网站http://neo.lcc.uma.es/radi-aeb/webvrp/上获取，对于每一个算例而言，用于配送的车辆均属于同一类型，而且都具有相同的约束条件：最大载重量D和最长行驶时间T，每个算例中的距离类型均采用欧几里得距离，即欧式距离，并且假设车辆在客户节点之间的行驶时间等于客户节点之间的欧式距离；（9）为了验证本文提出的算法模型的寻优能力，分别与求解Cordeau算例的禁忌搜索算法TS和变邻域搜索算法VNS和CAVNS在求得的最优解和求解的稳定性两方面进行对比。