云计算优化物流车辆路径规划算法

张娟萍

（山西工程科技职业大学，山西 晋中 030031）

1 引言

网络时代电子商务的兴起，带动商品配送物流的快速发展，而待配送任务随之逐渐呈海量的增长趋势和发展态势［1-2］。给传统物流业带来极大的冲击，亟待探索新的配送方式以满足实际业务需求，云计算能够有效的将车轴在物流配送中心，收方及车辆配置等方面进行合理调试，充分利用云资源降低配送的时间和成本，提高配送效率。因此，云计算的有效利用，优化配送模式管理，合理规划物流车路径，对现代物流发展意义重大，成为一个研究的热点问题［3］。

为充分发挥云计算物流业车辆管理和路径规划方面的优势，文献［4］提将交通拥堵影响作为其物流路径优化模型的一个因素，在时变网络下基于云计算统筹车辆安排和优化路径，算法对规避拥堵降低成本效果较好，但是算法易收敛失衡而计算不了最优解。文献［5］采用改进的粒子群算法迭代计算最短路径目标函数，算法对于一定范围内的配送车辆路径方案效果较好，可以获得最短路径，但整体性能不佳，且对于拥堵时段和客户满意度考虑不周。文献［6］基于云计算构建装配调度与路径规划的一体模型，以全连路网代替以往单一的中心节点结构，采用多个指标对调试进行优劣评价，通过多目标优化算法进行模型求解。文献［7］提出基于云计算的物流船运的路径规划，通过云端的航线整合，将客观数据与云端联通，并通过云端的最优路径规划实现航道的设计。

为此，为充分利用云计算的资源调度优势，提出云计算下，基于改进粒子群算法的物流企业车辆最优路径规划算法，算法首先构建路径规划的多目标优化函数，然后通过改进的粒子群算法对路径进行寻优，以提高算法的迭代收敛速度和收路径规划质量，实例验证了所提算法路径规划上的优势和车辆高度上的有效性。

2 物流车路径规划建模

高效的物流配送的提升企业效益和服务满意度的关键［7］，文中路径规划的最终目标物流车辆通过最优高度和路径规划在保证客户满意前提下，使得配送成本和配送时间最低。当前城市物流模式通常为以中心站为圆心，配送区域为其辐射周边，并根据密集度建立集散点和辐射小区域，为此，通常将物流配送抽像建模为中心与多辐射点的结构，基于以上考虑建立物流车的路径规划模型。

2.1 模型目标函数

物流车辆行驶的规划路径应使得整个企业的成本最低、配送速度最快，并确保货物到达目的地的时间既定，成本分析的形式化描述为S(sh1，sh2，…，shk)，式中：shk—调度状态，其通常由车辆标识、当前位置、目的地及运行路径点组成，则考虑道路的时间、距离及其他费用的加权成本代价为：

式中：Price(shi)—最优路径下将所有货物配送完成的代价；tv—shi高度状态下的总运输量。在不考虑满载与否的情况下，装卸成本可以简化为：

式中：k、ul(shi)—装配与卸载车次；lp、lu—装配与卸载一次成本。

而货物配送的剩余时间可以简化为：

式中：Time(shi)—配送过程中车上货物配送完成所需时间；loɑd(shi)—配送物品总量。

tr(S)与lu(S)最优可以保证物流最低配送成本和最快配送速度，lt(S)可以确保最紧急物品被优先配送，以提高客户满意度，平均满意度可以简化为［8］：

式中：N—客户数；ui—单个客户的满意度，在满中条件0≤ti≤Ti下，其计算方式为ui(ti)=Ti-ti Ti，式中：Ti—期望最迟货物到达时间；ti—实际到达时间。

根据以上分析，总的配送成本可以建模为：

式中：Cij—两个收货客户之间距离造成的单位成本；dij—两客户之间的配送距离；Cf—配送过程中车辆自身消耗带来的固有成本。

2.2 模型约束条件

在模型构建过程中，配送使用车辆需满足载荷约束［9］和数量约束，即

而在路径规划高度时，需要满足约束：

同时，由编号为k车辆完成客户i的货物配送，则其必须完成j的货物配送，即有：

此外，在模型求解过程中，目标函数的迭代计算需在式（9）所示约束下取值，即：

其中，i=0，1，…，N，j=0，1，…，N且i≠j。

3 基于粒子群算法的模型求解

粒子群算法中粒子代表一个优化解，因此将粒子视为一个阶段路径，可以将粒子群算法与物流车路径规划联系起来，则可以通过粒子群算法求解上述模型而获得最优路径。

3.1 适应度函数构造

为了对算法迭代寻优得到的路径时行优劣评价，粒子群算法需要先构造合适的适应度函数，适应函数也是粒子更新位置和速度的依据。这里构建适应度函数为：

式中：f(d)—配送车辆的起始位置至客户的欧氏距离；f(d′)—粒子群算法迭代过程中的总路径长度；g1(p)、g2(p)—惩罚函数，计算式为：

式中：α、β—惩罚系数；γ—调整惩罚系数关系；ρi、θi、ρ0、θ0—路径的极径和极角。适应度函数构造后，随机生成初始种群。

在适应度函数基础上，设计粒子群算法的惯性权重和学习因子的自适应调整策略。设在第i次迭代过程时，粒子k与当次迭代过程获得的全局最优位置之间的欧氏距离边界值分别为Lmax和Lmin，则当距离Lij＞Lthre时，有：

式中：ωij—当次迭代粒子的惯性权重及边界值；ωmax、ωmin—权重边界值，式（12）表明，距离当前最优粒子越远的粒子，其全局搜索能力越强，从而提高了潜在全局最优粒子的性，(tmax-ti)tmax保证了粒子在后期的更优搜索能力。

对于学习因子，相应的在Lij＞Lthre时，有：

式（13）表明，距离当次迭代获得的最优粒子越远的粒子，其在更新时更多经验来自自身历史经验，而距离越近，粒子在更新时经验来自种群的社会最优经验。

3.2 变异操作

为避免算法迭代后期样本多样化受限而陷入局部最优问题，对算法进行变异操作。在多样性降低到一定值后，对粒子进行变换，粒子多样式采用粒子与种群中心间的距离表示，即：

式中，m、xi—粒子数量及其位置；pc—群中心位置，pc=m-1∑xi。当多样性降低到预设阈值，即p＞pt时，对其某一维度进行变异操作，以使粒子保留一部分历史搜索经验。

式中：δ—变异幅值；

r—随机数；

bmax、bmin—粒子在变异维度的边界值；

p—变异概率；

pt—变异概率阈值。

pt值决定变异操作对粒子的影响，值越大，粒子变异可能越小，种群多样性受限，不易跳出局部最优；值越小，粒子变异概率较大，但容易损失以往搜索经验，而偏离全局最优值。

3.3 冗余点筛选及算法流程

当物流车可选路径较多啊，粒子群算法会变得很复杂，参数的不同设置及迭代过程差异使得最终得到的最优路径并非最优，存在较多的冗余点，因而需要进一步去除冗余路径点，以使路径最优。这里基于云计算和粒子群优化的物流车路径规划算法流程，如图1所示。基于云计算的资源调试，粒子群在完成一次迭代后，先根据式（12）计算多样性，并判断其与阈值关系，如果p＞pt则算法进入概率变异，否则该粒子根据适应度值大小来判断下一次迭代的保留概率，数值越，保留概率相应的越高。算法最优路径迭代选择完成后，进行冗余路径的筛选，以得到最终的最优路径。

图1 物流车辆路径规划流程Fig.1 Logistics Vehicle Path Planning Process

4 仿真实验分析

为验证文中提出基于云计算和粒子群相结合的物流车路径规划算法的性能，利用matlab 2016a进行模型构建与测试分析，以Solomon benchmark中含有100个收货客户的C101模型算例作为实验数据。粒子群迭代最大次数为1200，参数值取值为：δ=0.049，pt=0.75，以遗传算法［8］和基于车联网和云计算的物流车高度算法［11］（记为IVCCIS算法）作为路径规划性能比较算法，实验中每个算法运行100次取平均值。首先分析改进算法的概率变异对粒子多样性的影响，如图2所示。可以看出未加入概率变异时，在迭代一定次数（300次）后，粒子的多样性降低到接近0，且继续迭代计算，多样性变化不大，说明算法很容易局部最优，而在算法中加入概率变异后，粒子的多样性一直持续到迭代终止，说明粒子在整个迭代过程中一直在进行分局搜索，有利用跳出局部最优。物流中心的仓储能力与物流车的运输总能力之间的比值（τ）是影响物流车辆路径最优规划的重要因素，这里算法与基于遗传算法的物流车路径规划算法在不同的比值τ下的加权成本tr(S)的多次实验平均值如图3所示。可以看出文中算法计算得到的最优路径对应的加权成本，在不同的能力比下，都取得比基于遗传算法的算法获得的最优路径对应的加权成本要低，说明文中算法的路径更优。

图2 多样性随迭代次数的变化Fig.2 Diversity Changes with the Number of Iterations

图3 不同能力比加权成本比较Fig.3 Comparison of Different Abilities than Weighted Costs

三种算法最优解平均值，如表1所示。从表1实验结果可以看出，算法取得相同的Parto解值，均为19，在平均满意度上，IVCCIS算法最低，主要因为其算法复杂，涉及参数调整较多，且存在较的冗余点，这从配送时间上也可以看出其时间最长，总成本上遗传算法要高于IVCCIS算法，而从三个指标看，这里算法最优从而验证了提出的改进物流车路径规划算法的良好性能。

表1 三种路径规划算法结果比较Tab.1 Comparison of Three Path Planning Algorithms

6 小结

基于云计算的资源高度优势，研究了物流企业的车辆配送最优路径规划问题，提出了云计算条件下基于改进粒子群算法的车辆优化调试算法，算法以加权成本、装卸成本、平均满意度和剩余时间四个指标描述物流车辆的调度问题，并建立了多目标优化函数，通过对粒子群算法的适度函数改进、参数自适应调整和概率变异操作提高算法路径规划寻优能力和迭代求解速度。实验结果验证了所提方法的路径规划优势及车辆调度上的合理性。