基于扰动收缩粒子群算法的物联网配送车辆调度

卢锦川

(广西机电职业技术学院, 广西 南宁 530007)

0 引言

目前物流行业对智能化的要求越来越高，通过物联网融入可避免传统车辆模式缺陷，物联网配送车辆能够记录跟踪车辆到达时间以及地理偏差等重要信息[1-2]，使得服务质量提高，减少运输工程成本的增加[3]。

物联网配送车辆调度要求运输成本最优，解决方法主要有列生成法、集分割法、动态规划法等，但是由于其计算复杂度与规模之间呈几何级数变化关系，根本无法求得问题的最优解，不能满足现代物联网实际应用要求[4-5]。当前，智能优化算法具有求解效率高等优点，如遗传算法(Genetic Algorithms,GA)[6]、蚁群算法(Ant Colony,AC)[7]、粒子群算法(Particle Swarm Optimization,PSO)等越来越受到研究者的关注[8-9]。但是在实际应用中也存在着局部搜索能力差、收敛时间过长、易陷于局部最优等问题，遗传算法对初始种群产生十分敏感，蚁群算法易受参数影响，计算量大，粒子群算法收敛后期易陷入局部最优解。混沌量子粒子群算法(Chaotic Quantum Particle Swarm Optimization,CQPSO)应用于车辆调度问题[10]，取得了较好的效果；模拟退火粒子群算法(Simulated Annealing Particle Swarm Optimization,SAPSO)[11]，快速求得带时间窗车辆路径问题的优化解；柯西变异粒子群算法(Cauchy Mutation Particle Swarm Optimization,CMPSO)可应用在多车场多车型车辆路径调度问题[12]，但是算法后期效率也比较低。

为了获得更加理想的物联网配送车辆调度方案，针对标准粒子群算法的不足，采用扰动收缩粒子群算法(Perturbation Contraction Particle Swarm Optimization,PCPSO)，扰动过程通过非线性控制，收缩通过加权系数进行，并完成相关仿真内容，以验证算法的有效性。

1 物联网配送车辆优化调度问题的数学模型

每辆车上装载电子标签，当经过读写器时，存储在电子标签芯片中的车牌号信息被获取，为后续对该车信息管理提供了保障；GPS定位对车辆定位与跟踪；管理系统对实现本地、外地的交通路线、车辆位置和轨迹等信息的可视化，实现实时获取物流配送车辆的位置、速度、载货量、到达及离开各配送节点的时间，使得车辆信息管理系统查看智能化；GPRS网络实现完成车辆和各种数据网之间的数据传送和格式转换。物联网配送车辆调度系统如图1所示。

图1 物联网配送车辆调度系统Fig.1 Internet of Things distribution vehicle scheduling system

将无线数字传输模块植入交通信号系统及联网车辆，实现相互之间的信息传输，实现车辆与道路基础设施、车辆之间的信息交换，汽车的显示终端可作为城市道路交通导航系统使用，车辆之间可以相互提供数字化信号灯信息、位置、车速等信息，以此作为接受信息车辆安全行驶的依据。在执行配送任务过程中，基于反映顾客需求、车辆及道路等变化情况的实时信息，对车辆运行路重新进行设计和优化，形成新的调度方案并安排执行,考虑到货物品种及数量、需求时间和地点、运输线路以及运输时间的不确定性，因此从运输成本、时间惩罚成本、固定成本3个方面建立数学模型。

1.1 运输成本

(1)

式中，λ为单位里程费用；d(i-1)i为客户(i-1)到客户i的距离。

1.2 时间惩罚成本

由于顾客对配送时效的要求越来越高，物联网配送车辆在实际配送过程需要接受顾客的接收时间[14-15]，因此增设惩罚成本ζ2：

(2)

(3)

1.3 固定成本

物联网配送车辆的固定成本ζ3与派遣车辆数量有关，使用较少的车辆数减少企业的固定成本。

(4)

式中，τ为单个物流配送车辆完成单次配送任务的固定费用，包括物联网器材以及使用费、车辆保养费、司机费等；Nk为车辆k在配送过程中的客户节点数量，sign(Nk)=1为车辆k被使用。

根据优化目标要求配送车辆总里程数为最短，并且固定成本、惩罚成本最少，则总成本最小化数学模型为：

(5)

2 随机扰动粒子群过程

2.1 基本粒子群算法

(6)

2.2 扰动收缩过程

尽管传统的粒子群算法可以解决非线性优化问题，为避免算法运行后期易出现局部最优解误认为全局最优解现象发生，增设扰动收缩操作。

2.2.1 扰动操作

对基本粒子群算法增设扰动因子δ用来平衡粒子的全局和局部搜索[17]，则粒子更新速度和位置为：

(7)

δ为一个随机数，主要作用是控制随机扰动的振幅。δ值越大，粒子越具有强大的能力逃离当前位置，而δ值越小，越可以提高粒子的局部搜索能力。

图2 δ控制过程Fig.2 δ Control process

对δ操作控制如图2所示。在迭代前期δ值设置比较小，让粒子主要进行局部搜索，而在后期δ值设置逐渐变大，让粒子逃离当前位置，进行全局搜索。

2.2.2 收缩操作

(8)

2.3 粒子编码方式

由于配送涉及到3个变量，即收货点、物流配送车、行驶线路[18-19]，因此粒子编码如表1所示。

表1 粒子编码Tab.1 Particle coding

2.4 粒子解码方式

(1)对粒子第2行的元素aij进行取整操作int(aij)，收货点j得到分配的车辆i。

(2)对于车辆i的行驶路径，先完成收货点j的配送任务，然后按照收货点j对第3行元素bij从小到大排序确定车辆i行驶路线。

把ζ作为所研究问题的目标函数，ζ越低越好，而粒子的适应度值是越高越好，适应度函数采用ζ的倒数表示。

算法流程：

① 初始化粒子的参数及迭代次数；

② 计算粒子适应度，找出个体最优和全局最优值；

③ 对粒子群进行扰动收缩；

④ 更新粒子的速度和位置，并更新历史全局最优值；

⑤ 满足迭代次数，输出寻优结果，否则进行步骤③。

3 试验仿真

3.1 数据来源

试验设置粒子群个数为80个，最大迭代次数为200，采用Matlab进行仿真试验。假设某企业有物联网配送车辆3辆，需要配送客户9个，车辆额定载质量为5 t，单位里程费用为3元，车辆的行驶时间与距离成正比，每个任务点的需求量、装卸货的时间以及任务点的时间窗要求如表2所示。比如任务序号1，其货运量为3 t，配送时间为1.3 h，最早到达时间为1 h，最晚到达时间为2.5 h。

表2 货运量及时间窗Tab.2 Freight volume and time window

仓库与任务点以及各任务点之间的距离如表3所示。

表3 仓库与任务点以及各任务点之间的距离(单位：km)Tab.3 Distance between warehouse and each task point and distance between task points (unit:km)

3.2 结果与分析3.2.1 目标函数优化分析

物联网配送车辆总成本是评价分析算法性能的重要指标，对本研究涉及到的GA，AC，PSO，CQPSO，SAPSO，CMPSO以及PCPSO算法对比分析，目标函数总成本优化的迭代曲线如图3(a)所示，任务目标点寻优地理位置偏差如图3(b)所示。

图3 目标函数优化分析Fig.3 Analysis of objective function optimization

从图3(a)可以看出，各种算法都随进化迭代次数的增加而目标函数总成本呈递减趋势，但是本研究PCPSO算法前期递减速率较快，在第60次迭代时，总成本值逐渐趋于稳定，其他算法需要较多的迭代次数才能够趋于稳定；从图3(b)可以看出，本研究PCPSO算法对任务目标点寻优地理位置偏差值最小，避免了总成本增加。

各种算法获得目标函数总成本最优时消耗时间结果对比如表4所示。

表4 目标函数总成本最优时消耗时间结果对比Tab.4 Comparison of time-consuming results for optimal total cost of object function

从表4可以看出，本研究PCPSO算法消耗时间少于其他算法，在处理时间上都有着明显的提高，说明本研究PCPSO算法可以在较少的时间内获得总成本最优化，主要是PCPSO算法通过非线性控制δ值，迭代前期让粒子主要进行局部搜索，后期进行全局搜索，从而获得最优结果。

3.2.2 算法其他性能对比分析

涉及到的对比算法有GA，AC，PSO，CQPSO，SAPSO，CMPSO以及本研究PCPSO算法，对每种算法均进行30次蒙特卡罗试验。搜索成功率、违约惩罚成本占总成本比例如图4、图5所示。

图4 搜索成功率Fig.4 Search success rate

图5 违约惩罚成本占总成本比例Fig.5 Proportion of default penalty cost to total cost

从图4可以看出，本研究PCPSO算法每次试验的搜索成功率最高为70%，同时从图5可以看出，本研究PCPSO算法每次试验的违约惩罚成本占总成本比例最低为3%，说明本研究PCPSO算法具有较好的搜索成功率以及控制违约惩罚成本，主要是PCPSO算法可通过较少的迭代次数找到最优解，增强算法搜索功能，从而获得更优的车辆配送方案。

4 结论

针对物联网配送车辆调度过程中的效率问题，提出了扰动收缩粒子群算法，对成本最小化模型寻优使得配送成本最优，避免了运输成本的增加。试验仿真显示本研究算法对目标函数总成本优化中使用最少的迭代次数即可获得最优值，每次试验的搜索成功率最低为70%，每次试验的违约惩罚成本占总成本比例最高为3%，是一种高效的优化方法，为物联网配送车辆调度提供了一种新方法。