【《具有静态信息的多车场同时取送货车辆路径问题分析》5000字】

)在上述的数学模型中，目标函数（3.1）为使总配送成本最小，由三部分组成，第一部分是车辆的空载成本，第二部分是车辆的负载成本，第三部分是车辆使用一次的固定成本；约束（3.2）是每辆车的单程行驶距离不超过单程最大行驶距离；约束（3.3）是车辆访问客户前后的载重量递推公式；约束（3.4）是车辆访问客户后载重量约束；约束（3.5）每个客户有且仅有一辆车提供服务；约束（3.6）相同节点无路径；约束（3.7）车辆进出平衡；约束（3.8）和约束（3.9）保证车辆从一个车场出发服务后最终回到该车场；约束（3.10）车辆派出总数目不超过车场实际车辆数；约束（3.11）和（3.12）保证客户被车辆服务时一定有路径相接；约束（3.13）车辆不会从一个车场直接前往另一个车场；约束（3.14）是决策变量取值约束；决策（3.15）是客户取送货需求量非负约束。具有静态信息的MDVRPSDP禁忌搜索算法设计针对具有静态信息的MDVRPSDP问题，其算法具有以下两个难点：一是车场分配问题。MDVRPSDP问题中含有多个车场，任意一个车场都可以对客户进行服务，但是如果分配不合理，会导致车辆路径迂回冗余，导致服务质量降低，客户满意度也会受到影响。因此，如何构建将客户分配给车场是算法设计的难点。二是车辆安排问题。建模的目标函数中将车辆单程的固定成本作为总配送成本的一部分考虑，因此实际派送的车辆数目会影响到成本最小化的目标，合理规划路径，减少车辆使用数目尤为重要。针对这两个难点，本节算法设计时先采用广义距离SC计算各个车场到客户点之间的距离成本，采用最近邻算法将客户分配给车场并构造配送路径形成初始解，而后采用禁忌搜索算法进行优化求解。构造初始解本文采用自然数编码，并且采用最近邻算法构造初始解，对算法中的选择标准进行改进，将车辆的载重量及距离作为节点选择的标准。在构造初始车辆行驶路径时，首先确定与客户SC最小的车场作为起始点，在选择下一个节点时，优先选择使SC最小的客户点；若该客户没有被分配到其他路径并且符合一系列约束，则把该客户插入到路径中，并且更新路径状态。若无法满足系列约束，则重新创建路径。本文从文献[51]中得到启发，将SC表达式表示成：，式中的表示客户的取货需求量，表示客户的送货需求量，表示客户和客户之间的距离，表示权重系数。客户的取货需求量越少，送货需求量越多且与当前节点距离越近，则SC越小，客户被选作下一个节点的优先级越高。算法的伪代码如下所示：输入：客户数量、位置、取送货需求量，车场位置，车辆最大载重量Q和单程最大行驶距离L;输出：：初始解S初始化;while存在客户未被分配do 初始化与客户点间SC最小的车场为当前节点i while满足车辆单程最大行驶距离约束do 选择未分配客户j使SC最小 if客户j满足车辆最大载重量约束 将客户j插入路径 令客户j为当前节点i，并更新路径信息 else 找出满足载重量约束的客户集 在客户集中选择未分配客户h使SC最小 将客户h插入路径令客户h为当前节点i，并更新路径信息 Endif Endwhile创建新路径Endwhile输出初始解S邻域结构和解的评价邻域结构指在当前解的基础上按照特定的移动类型产生邻域解，不同的移动类型生成的邻域解的形式和数目不同，本文运用不同的算子产生当前解的邻域解。对于解的质量判断需要首先判断某一解得到的路径方案是否满足约束，同时计算目标函数值，在满足约束的前提下，目标函数值越优，解的质量越高。 2-opt算子：在两条不同路径上分别选取一个点互换位置形成两条新路径。图3.12-opt算子 Relocate算子：移出一条路径上的一点将其插入到另一条路径中形成两条新路径。图3.2Relocate算子 Cross算子：从不同的两条路径中分别选出一条边互换位置形成两条新路径。图3.3Cross算子禁忌参数禁忌长度设置过短容易陷入局部最优，设置过长容易导致算法时间增加。因此，禁忌长度的合理设置是禁忌搜索算法性能优劣的关键。本文将禁忌长度设置为到多个正整数（为客户数量），禁忌对象为上一个当前解对应的边()，并建立二维禁忌表。藐视准则和终止准则本文的藐视准则为：（1）若存在当前最优解的禁忌候选解，则特赦该禁忌对象元素；（2）若当前全部候选解都被禁忌且不满足准则（1），则特赦禁忌长度最小的元素。本文的终止准则为：当前迭代次数大于设置的最大迭代次数（iter>max-iter）或者当前最优解持续不变的连续迭代次数大于设置的最大连续迭代次数（cons-iter>max-cons-iter）时结束搜索。算法框架和基本流程KNN-TS算法的总体思路 首先，在算法系统中输入车场、客户点和车辆的相关数据信息，并通过计算获取客户点之间的距离以及SC的数值大小。其次，调用禁忌搜索算法KNN-TS求解函数，初始化算法系统的参数设置，通过最近邻算法形成初始车辆路径方案。然后，采用三种邻域结构生成一定数量的邻域解，选取其中较优的部分解形成候选解，将候选解与当前解进行比较，更新当前最优解。最后，判断算法是否满足终止条件，输出车辆路径优化方案。KNN-TS算法的基本流程 KNN-TS算法求解具有静态信息的MDVRPSDP问题的流程如图3.4所示：图3.4KNN-TS算法的基本流程该算法的具体步骤如下：Step1：输入客户、车场和车辆的信息，对信息进行预处理。算法采用datain函数首先读取客户和车场的位置，客户的取送货需求量，车辆的最大载重和单程最大行驶距离，而后采用preset函数对读取的数据进行预处理，方便后续使用和更新。Step2：初始化算法的参数。设置当前迭代次数iter=0，当前最优解连续次数cons−iter=0;禁忌表，禁忌长度取(,)之间的正整数；调用greedy函数依据SC值大小选择车场和车辆服务客户的顺序，从而生成初始解S，并将S设置为当前解和当前最优解，通过适应度函数（本文选取目标函数）计算初始解S的适应度值;当前候选解数目，最大候选解数目为,候选集为;设置禁忌准则和终止准则。 Step3:生成邻域解，选取候选解。调用neihood函数从三种邻域算子中随机选择一种邻域算子对当前解进行邻域变换生成邻域解，运用selection函数在邻域解中选取选择一部分解作为候选解，将置于候选集中，并且；若，转Step4，反之转Step3。 Step4：选择最佳候选解。调用cacul函数计算适应度函数值，并设置求目标函数的最小值。调用TSsolve函数，通过排序确定非禁忌最优候选解，或解禁优于当前最优解的禁忌候选解，并将其设置为最佳候选解，在全部候选解都被禁忌时选择禁忌长度最小的候选解进行解禁。 Step5：更新迭代信息。设置新的最佳候选解为当前解，iter=iter+1。如果新的最佳候选解优于当前最优解，则更新当前最好解，并令cons-iter=0；否则cons-iter=cons-iter+1。 Step6：更新禁忌表。将当前解的禁忌对象放入禁忌表中，并更新禁忌表。 Step7：终止准则。若或，算法终止并输出最优解，否则转Step3。 Step8：得出车辆路径方案。根据编码的方式，通过解码最优解即可得出最终的车辆路径方案和各项成本值。具有静态信息的MDVRPSDP算例仿真算例描述本文选取文献[28]中的算例，算例中有3个车场和30个客户点位于边长为20km的正方形区域，表3.1为车场的各项参数，表3.2为客户点的各项参数。出于简化计算的考虑，客户点之间的物理距离之间采用欧式直线距离代替。表3.1车场相关信息车场编号横坐标纵坐标车辆数车辆最大载重量车辆最大行驶距离A9.566.03310t50kmB6.4411.28310t50kmC11.1411.10310t50km表3.2客户相关信息客户编号横坐标纵坐标送货量取货量12.9613.360.80.9219.8114.380.40.736.5218.822.00.447.275.260.51.4514.9016.450.71.867.0414.251.80.576.145.031.01.280.6214.851.91.0914.4512.081.00.9101.291.420.71.0113.909.090.80.71215.1017.901.31.5130.3311.470.90.31412.280.341.90.5152.3315.851.90.61611.9213.100.71.91710.4810.761.80.91810.0019.272.00.71913.607.981.60.92019.148.530.20.52111.478.431.80.72211.592.672.00.52318.0210.561.11.32419.2112.430.60.92511.7016.902.61.42611.8519.901.01.22712.8012.180.20.5280.5111.100.10.4293.558.270.81.23017.611.011.60.4算法参数设置与分析本文算法编程的工具采用MATLAB2019b，操作系统是windows10，电脑内存为8GBDDR4，CPU为Intel®Core™i5-6200U。算法具体参数设置如下：10t的卡车空载行驶0.2L/km，重载0.01L/(t.km)，柴油的均价大约是7元/L，所有=1.4元/km，=0.07元/(t.km)，车辆启用的固定费用=60元/次。最大迭代次数max-iter=500，最优解保持不变的最大连续迭代次数max-cons-iter=300。禁忌长度的分析 禁忌长度决定禁忌对象的被禁任期，影响着算法的求解速度和寻优能力，在现有研究中，禁忌长度的设置与问题的规模相关。本文选取(,)之间的正整数，为了有效确定最优的正整数，分别将禁忌长度设置为5，15，20，30进行仿真实验，得到各数值下的迭代过程图如图3.5所示，得到各数值下的经济成本表3.3。可见当禁忌长度选取25时虽收敛速度相较其他取值略慢，但花费的成本明显较小，配送的经济效益最高。表3.3不同禁忌长度下的经济成本比较禁忌长度最佳经济成本/元10555.473215494.519820497.806325460.133730494.4625图3.5不同禁忌长度算法迭代对比图候选集规模的分析 候选集规模选取过大，则算法的计算量和存储量过大，求解速度会降低，反之选取过小，则容易造成过早收敛，陷入局部最优的情况。候选集规模的大小也同样需要根据问题的规模进行确定，现有文献中有从(50+3,250+3)中选取正整数进行赋值。本节在以禁忌长度为25的情况下，为了有效确定最优的正整数，分别将禁忌长度设置为100，150，200，250，300进行仿真实验，得到各数值下的迭代过程图如图3.6所示，得到各数值下的经济成本表3.4。可见当候选集规模250选取时能够取得较快的收敛速度，花费的成本也是较小的，配送的经济效益最高。表3.4不同候选集规模下的经济成本比较候选集规模最佳经济成本/元100477.0479150471.7564200472.5263250460.3071300477.8109图3.6不同候选集规模的算法迭代对比图车辆路径方案获得车辆路径优化方案综合上述仿真结果，针对本算例选取禁忌长度为25，候选集规模为250，并调整其余算法参数，根据KNN-TS算法得到初始路径图如3.7所示，最优结果的行驶路径如图3.8所示，迭代过程图如3.9所示。图3.7初始车辆路径图图3.8算法最优结果迭代过程图图3.9最优结果行驶路径图 在行驶路径优化方案中，实际派遣车辆为4辆，车辆的总行驶距离为118.8km，配送经济成本为458元，其中固定成本为240元，总油耗成本为218元，配送路径方案如表3.5。表3.5车辆路径优化方案车场车辆车辆路径方案车辆行驶距离114-7-11-29-10-14-22-2136.2km226-3-15-8-13-28-127.8km3316-5-12-26-18-2523.9km3417-19-30-20-23-24-2-9-2730.9km车辆路径优化方案对比分析在文献[28]中，10t的卡车空载行驶0.2L/km，重载0.01L/(t.km)，柴油的均价大约是8元/L,所有=1.6元/km，=0.08元/km，车辆启用的固定费用=50元/次。作者采用改进遗传算法，最终结果