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

一种求解多车场带时间窗车辆路径问题的变邻域搜索算法的制作方法专利名称：一种求解多车场带时间窗车辆路径问题的变邻域搜索算法的制作方法技术领域：本发明涉及运筹学领域中的车辆调度问题，具体为一种求解多车场带时间窗车辆路径问题的变邻域搜索算法或是一种基于变邻域搜索算法的求解模型背景技术：现实中大量的物流车辆调度问题都可以归结为多车场带时间窗的车辆路径问题(Multi Depot Vehicle Routing Problem with Time Windows,MDVRPTW):物流车辆最初分别于多个不同物理地点上的车场，它们需要以最少的路径成本将指定数量的货物在要求的时间范围内送达顾客，并最后返回车场尽管MDVRPTW的实际应用已经非常广泛，但该问题在理论研究中尚未得到很好的解决多车场”与“时间窗”分别在问题的空间和时间方面施加的双重约束，使原本就具有 NP复杂性的问题求解具备了叠加的难度，针对大规模问题的求解效率还有待提高MDVRPTff仍是车辆路径问题集合中为数不多的没有得到深入研究的课题之一现实中的物流决策者对该类问题通常采用“以车场为中心对顾客分区并在区内规划路线”这一经验性做法，路线规划的科学性和有效性都难以保障。

MDVRPTW包含多车场车辆路径问题(MDVRP)和带时间窗车辆路径问题(VRPTW)这两类子问题的特性，但由于MDVRP和VRPTW所分别关注的空间和时间这两方面的约束具有相互冲突的求解特性，使得它们在组合为一个新问题之后，用于解决原有问题的启发式思想难以被重用当前求解MDVRPTW的算法主要以元启发式为主，包括禁忌搜索算法、遗传算法、变邻域搜索算法、粒子群算法以及模拟退火算法等等而这些元启发式算法在问题求解过程中都会遇到过早陷入局部最优，即早熟收敛的情况，这也是元启发式算法在求解MDVRPTW的一大通病同时元启发式算法中通常需要设置较多的经验参数，而这些参数往往需要根据具体的问题来进行设置，不具备较强的通用性因而，如何减小算法陷入局部最优的可能性以及相关参数的选取都是元启发式算法研究的难点问题发明内容本发明的目的是提供一种求解多车场带时间窗车辆路径问题的变邻域搜索算法本发明的目的是按以下方式实现的，步骤如下 (I)多车场带时间窗车辆路径问题有车辆载重、服务时间窗和车辆最长行驶时间的限制，在所有客户点的可能排列中，绝大部分对应的都是不可行解，许多算法在求解带有负载或时间窗等约束条件的车辆路径问题时，通常在求解过程中都只保留可行解，而将不可行解舍弃，但值得注意的是，在这些不可行解中，有可能存在少数的不可行解，即经过一定次数的迭代过程后能求得质量更好的可行解，鉴于此，本算法模型在求解过程中允许不可行解的存在，以使得算法具有更广阔的搜索空间，进而增大算法求得更优解的可能性； 在本算法模型中，解的评价函数表示为/Cr) =cCr) + Ctqijd + β {χ) + r#Cr)，其中α、β、γ为惩罚因子,且O" >Q, β>O, r>O。

对于解z来说,令c Cr)表示车辆总的行驶距离或时间，令^Cr)表示车辆总的载重违反量，令i/Cr)表示车辆总的行驶时间违反量，令#Cr)表示车辆总的时间窗违反量，在计算车辆经过单条路径的行驶时间违反量时，本文引入了由Savelsbergh提出的向前时间松弛Forward Time Slack的概念,用于对行驶时间违反量进行相应的优化； (2)本算法在初始解的构造阶段采用三标准聚类算法，依据客户的地理位置和时间窗大小将客户分配到特定的车场，并规划路线，进而生成初始解； (3)Shaking过程主要依据事先定义的邻域结构集合对解的结构进行一定的调整，以充分扩展当前解的搜索空间，减小算法在后续求解过程中陷入局部最优的可能性，对于Shaking过程而言,邻域结构集合的构造在很大程度上决定着变邻域搜索算法的求解效率以及逃离局部最优的能力； MDVRPTff的解是有多条路径组成，而每条路径都看成是客户节点的有向序列，在求解MDVRPTff时，本算法引入两种交换算子，分别为Cross-exchange和iCross-exchange,并利用这两种算子对当前解中的两条路径进行信息交互，进而产生新解，每次执行Shaking·过程时，MVNS算法将从上述两种算子中随机选择一种用于路径交换，今嫌Picross表示iCross-exchange被选取的概率,则Cross-exchange被选取的概率为I _ Pieross，值得注意的是，Aw的取值一般比较小，这主要是因为MDVRPTW的解是具有方向性，因而在路径交换过程中应尽量保持子路径的原有方向以增大求得可行解的可能性； 参与路径交换的两条初始路径、相应子路径的起始位置以及子路径的长度都需要通过当前解的邻域结构来确定，一般情况下，变邻域搜索算法都会采用多个邻域结构来提高算法的求解质量和稳定性，该集合由12个邻域结构组成，而且每个邻域结构都指定了参与路径交换的车场数以及子路径的最大长度，其中Cr表示分配给路径r的客户个数，由于MDVRPTff存在多个车场，用于路径交换的两条路径既从同一车场内选取或从不同的车场中分别选取，子路径是从选定的路径中随机选取出来的一段序列，其长度不能超过邻域结构规定的最大长度，在所有的邻域结构中，每个在其规定范围内的子序列长度被选择的概率都是相同的； (4)在本算法模型中，局部搜索过程将对Shaking过程中产生的新解^的邻域空间进行搜索以求得局部最优解4，在Shaking过程结束后，由于MDVRPTW的当前解z中只有两条路径发生改变，而其余路径均保持不变，因此Local Search过程只需要对这两条路径分别进行局部搜索，Local Search过程在整个VNS算法框架中是耗时最多的部分，而且在较大程度上决定着VNS算法最终的求解质量，因而在设计局部搜索算法时需要充分考虑到算法的求解效率，在本算法模型中选取了 2-op和or-opt作为局部搜索算子，以便能在较短的时间范围内求得质量较好的局部最优解，值得注意的是，每次的局部搜索过程都只采用一种算子，两种算子通过随机的方式进行选取，其中，参数表示2-opt被选取的概率，相应地Or-opt被选取的概率可以表示为I - ，采用这种混合算子的方式较为充分的结合2-opt和Or-opt两种算子的寻优能力，并且能在一定程度上拓展算法的求解空间； (5)为了在一定程度上加快算法的收敛速度，并提高算法的求解质量，本算法在求解过程中引入了后优化过程，在局部搜索完成之后，如果得到的局部最优解A优于全局最优解xbM, f{x^ O时，以一定的概率(θ_Λ /τ)接受解Z7并更新当前解X，即X = 4，本文对温度采用线性冷却的方法，在初始状态下^ = &，而每迭代便减少{T0 iterT) /i,其中，T表示当前温度，T0表示初始温度,itermax表示MVNS算法总的 迭代次数； (7)本算法各个参数的设置算法总的迭代次数设置为107，惩罚因子α. β、Y取值为α 二 β 二 Y 二 100，嫌Picross取值为O. \，P2_opt最终选定为O. 5，7；的取值为5，iterJ- 1000 ； (8)通过采用Cordeau算例来评估本算法在求解MDVRPTW上的性能,Cordeau算例是由Cordeau、Laporte 和 Mercier 设计的 20 个 MDVRPTW 算例，并从网站 http://neo. lcc. uma.es/radi-aeb/webvrp/上获取,对于每一个算例而言，用于配送的车辆均属于同一类型，而且都具有相同的约束条件最大载重量^和最长行驶时间r，每个算例中的距离类型均采用欧几里得距离，即欧式距离，并且假设车辆在客户节点之间的行驶时间等于客户节点之间的欧式距离； (9)为了验证本文提出的算法模型的寻优能力，分别与求解Cordeau算例的禁忌搜索算法TS和变邻域搜索算法VNS和CAVNS在求得的最优解和求解的稳定性两方面进行对比。

本发明的有益效果是在初始解的构造阶段采用聚类算法完成客户的分配，运用混合算子进行局部搜索，在通过后优化过程增强寻优效果，最后引入模拟退火算法模型对新解进行控制为了验证本算法模型的有效性，在Cordeau提出的标准测试用例上对本算法进行了实验，并与其他优化算法进行了对比实验结果更新了大部分测试用例的当前最优解，并在算法的稳定性体现出较强的优势图I为本算法模型的基本流程 图2为MDVRPTW解的图形化表示； 图3为Shaking过程中使用的交换算子； 图4为Shaking过程中使用的邻域结构集合； 图5为Shaking过程举例； 图6为局部搜索使用的混合算子；图7为Cordeau算例描述； 图8、9为实验对比结果具体实施例方式参照说明书附图对本发明的算法作以下详细地说明本算法模型的基本流程图，如图I所示下面结合流程图中的各个步骤来说明本发明的技术方案I)多车场带时间窗车辆路径问题有车辆载重、服务时间窗和车辆最长行驶时间的限制，在所有客户点的可能排列中，绝大部分对应的都是不可行解许多算法在求解带有负载或时间窗等约束条件的车辆路径问题时，通常在求解过程中都只保留可行解，而将不可行解舍弃。

但值得注意的是，在这些不可行解中，有可能存在少数这样的不可行解，即经过一定次数的迭代过程后能求得质量更好的可行解鉴于此，本算发模型在求解过程中允许不可行解的存在，以使得算法具有更广阔的搜索空间，进而增大算法求得更优解的可能 性； 在本算法模型中，解的评价函数表示为/Cr) =cCr) + aQ{j) + β ^) + Vw(x),^中a、β、γ为惩罚因子,且>Q, β>O, r >O对于解z来说,令c Cr)表示车辆总的行驶距离或时间，令^Cr)表示车辆总的载重违反量，令i/Cr)表示车辆总的行驶时间违反量，令Hx)表示车辆总的时间窗违反量在计算车辆经过单条路径的行驶时间违反量时，本文引入了由Savelsbergh提出的向前时间松弛(Forward Time Slack)的概念,用于对行驶时间违反量进行相应的优化； (2)本算法在初始解的构造阶段采用三标准聚类算法，依据客户的地理位置和时间窗大小将客户分配到特定的车场，并规划路线，进而生成初始解； (3)Shaking过程主要依据事先定义的邻域结构集合对解的结构(如图2所示)进行一定的调整，以充分扩展当前解的搜索空间，减小算法在后续求解过程中陷入局部最优的可能性。

对于Shaking过程而言,邻域结构集合的构造在很大程度上决定着变邻域搜索算法的求解效率以及逃离局部最优的能力； MDVRPTff的解是有多条路径组成，而每条路径都可以看成是客户节点的有向序列在求解MDVRPTW时，本算法引入两种交换算子(如图3所示)，分别为Cross-exchange和iCross-exchange,并利用这两种算子对当前解中的两条路径进行信息交互,进而产生新解每次执行Shaking过程时，MVNS算法将从上述两种算子中随机选择一种用于路径交换参数Picross表示iCross-exchange被选取的概率,则Cross-exchange被选取的概率为I-Picross值得注意的是，Amws的取值一般比较小，这主要是因为MDVRPTW的解是具有方向性，因而在路径交换过程中应尽量保持子路径的原有方向以增大求得可行解的可能性； 参与路径交换的两条初始路径、相应子路径的起始位置以及子路径的长度都需要通过当前解的邻域结构(如图4所示)来确定一般情况下，变邻域搜索算法都会采用多个邻域结构来提高算法的求解质量和稳定性如图所示，该集合由12个邻域结构组成，而且每个邻域结构都指定了参与路径交换的车场数以及子路径的最大长度，其中G表示分配给路径r的客户个数。

由于MDVRPTW存在多个车场，用于路径交换的。