基于统计步长PSO算法的烟草配送线路优化方案研究

钱漫 钟培泉 张亚萍 张振军

摘 要：烟草配送线路优化问题是烟草行业物流层面的重点问题之一。微粒群算法（Particle Swarm Optimization，简称PSO）是一种利用群体智能的随机全局优化方法，广泛应用于路径寻优、函数优化等领域。为了提高PSO算法的全局搜索能力，本文在标准PSO算法的基础上，定义了一种基于统计步长的微粒群算法：针对PSO算法易出现局部极值问题，引入惯性权重因子进行改进;针对PSO算法中加速步长为常量值而不符合实际情况的问题，定义了基于统计的加速步长进化方程。实践证明，本文研究的算法应用于烟草配送线路优化方案中，可以大大节约运输里程及运输成本。

关键词：线路优化;微粒群算法（PSO）;烟草配送线路优化方案

中图分类号：F252 文献标识码：A 文章编号：1003-5168（2021）09-0028-03

Abstract： he optimization of tobacco distribution routes is one of the key issues at the logistics level of the tobacco industry. Particle swarm optimization （PSO） is a stochastic global optimization method using swarm intelligence， which is widely used in route optimization， function optimization and other fields. In order to improve the global search ability of PSO algorithm， based on the standard PSO algorithm， the paper defined a particle swarm optimization algorithm based on statistical step size： aiming at improving the global search ability of PSO algorithm， the inertia weight factor was defined; aiming at solving the problem that the acceleration step size in PSO algorithm was constant， the evolution equation of acceleration step size based on statistics was defined. The practice shows that the algorithm studied in this paper can greatly save the transportation mileage and transportation cost when it is applied to the tobacco distribution route optimization model.

Keywords： route optimization;particle swarm optimization （PSO）;tobacco distribution route optimization plan

在烟草行业降本增效的大背景下，伴随着烟草物流配送业务的快速发展，成本问题成为制约烟草物流业的突出问题。如何经济、高效地进行卷烟配送成为烟草物流业务重点关注的问题之一。配送线路优化正是以距离最短、成本最低为目标的解决方案。配送线路优化方面的研究较多。谢萍等[1]针对乡镇执法部门的外业巡查工作效率问题，通过空间聚类形成巡查片区、车辆路径优化模型进行线路规划等两阶段设计了土地利用执法巡查路径优化模型;周爱莲等[2]针对卡车-无人机共同配送问题，在满足卡车可达性前提下以总配送时间最短为目标建立了混合整数规划模型;陈汐等[3]针对通勤类型定制公交线路规划问题，以乘客出行成本最小、车辆运营成本最优为目标，构建多区域运营模式的通勤定制公交线路规划模型，并以两阶段启发式算法求解多目标优化模型;许智宏等[4]针对线路优化算法动态性能不佳及大规模数据处理性能不足等问题，研究了基于遗传算法的大数据车辆动态线路调度模型，模型考虑了线路与时间对成本的影响，通过设计惩罚因子来改善遗传算法的收敛性与寻优性等。

微粒群算法是一种利用群体智能的随机全局优化方法，它具有易实现、可调参数少、全局搜索能力强等优点，但存在易陷入局部极值、常量值的加速步长无法反映实际粒子飞行状况等问题。因此，本文以基本的微粒群算法为基础，定义了一种基于统计步长的微粒群算法：针对局部极值问题，算法引入惯性权重因子进行改进;针对加速步长常量值问题，算法定义了基于统计的加速步长进化方程。实践证明，本文所提的算法应用于烟草配送线路优化方案中，可以大大节约运输里程及运输成本。

1 微粒群算法

微粒群算法（Particle Swarm Optimization，简称PSO）[5-6]是群体智能算法的一种，基本思想是通过群体中的个体相互协作和信息共享寻找最优解，目前广泛应用于路径寻优、函数优化、组合优化等各类优化问题。

基本微粒群算法的速度进化方程、位置进化方程如下：

式中，[vij（t）]为第[t]次迭代粒子的速度;[xij（t）]为第[t]次迭代粒子的位置;[r1j（t）]、[r2j（t）]为两个独立的随机函数;[pij（t）]为从开始到第[t]次迭代时个体最好位置或最优解;[pgj（t）]為从开始到第[t]次迭时全局最好位置或最优解;[c1]、[c2]为加速度常数。

微粒群算法具有易实现、可调参数少、全局搜索能力强等优点。微粒群算法研究较多。例如，高明瑶等[7]针对轨道交通接运公交的站点设置与线路布局问题，以接运乘客的客运周转量最大化为目标函数，以公交线路长度和剩余客流量、区段剩余通过量为约束条件，以粒子群算法求解公交线路最优解;张耀军等[8]针对车辆路径优化问题，研究了一种改进的量子PSO算法，其以2-opt算法和1-1交换算法为局部优化算法，以种群熵算法为衡量算法;董锴等[9]针对电力系统评估结果误差较大的问题，利用PSO算法探求电力系统状态评估的最优策略。

2 基于统计步长的微粒群算法模型

微粒群算法虽然有很多优点，但还存在一些不足：第一，微粒群算法易陷入局部极值问题;第二，微粒群算法中的加速步长为常数，无法反映实际粒子的飞行状况。针对上述不足，本文提出了一种改进的微粒群算法——基于统计步长的微粒群算法。算法改进后，速度进化方程被改进为：

3 烟草配送线路优化方案

烟草配送线路优化目标是以最优路线、最低成本和最快时间将卷烟从配送中心送到目的地。为了解决烟草配送过程中过远运输、重复运输、无效运输等问题，本文定义了烟草配送线路优化方案。其间定义的运输平衡方程为：

步长为1次，重复执行下文所述步骤，直到车辆平均装载率达到70%为止。

利用基于统计步长的PSO算法求解，并确定路径最优方案，求解步骤如下。

一是设置PSO算法的初始参数，包括群体规模、加速度[c1]和[c2]、惯性权重[wi]的最大值及最小值、最大迭代次数及迭代停止准则等;初始化微粒群的随机位置和初始速度;定义适应度函数，以最小里程的目标函数式（13）为适应度函数。

二是根据适应度函数计算群体中每个粒子的适应值，改变粒子的历史最优位置及粒子邻域的局部最优位置：将每个粒子适应值与所经历过的历史最优位置的适应值进行比较，若较好，则将其位置作为该粒子的历史最优位置;同时将每个粒子的适应值与粒子动态邻域所经历过的最优位置的适应值进行比较，若较好，则将其位置作为该粒子邻域的局部最优位置。

三是根据线性递减权值策略改变每个粒子的惯性权重;根据基于统计的加速步长进化方程式改变每个粒子的加速步长;根据粒子的速度进化方程与位置进化方程对粒子的速度、位置进行进化;其速度进化和位置进化方程分别如式（5）、式（4）所示;判断适应值是否满足迭代停止准则或是否达到最大进化代数，如不满足则返回第二步重新计算，否则结束并得到所要求的结果。

本文以某烟草局物流配送中心A送货部部分线路的实际配送为例，在未采用优化方案前，从A送货部某天送往客户的总里程数为1 809 km，出车次数为18次，如表1所示。

比较发现，本文所提的优化方案可节约里程数11.2%左右，提高车辆装载率11.73%左右，减少出车次数6次，大大节约了烟草物流配送的成本与时间。

4 结论

本文针对微粒群算法易陷入局部极值且常量值的加速步长无法反映实际粒子的飞行状况等问题，在PSO算法基础上，定义了一种基于统计步长的微粒群算法，利用惯性权重因子和基于统计的加速步长进化方程改进了PSO算法，提高了算法的全局搜索能力，并根据线路优化目标建立了烟草配送线路优化方案，为烟草配送线路优化提供了一种新的方法。

参考文献：

[1]谢萍，刘小平，庄浩铭，等.基于车辆路径优化的土地利用执法巡查线路规划研究[J].地理与地理信息科学，2020（4）：70-76.

[2]周爱莲，蒋利，侯夏杰.应急物流中无人机配送线路优化[J].长沙理工大学学报（自然科学版），2020（2）：54-60.

[3]陈汐，王印海，刘剑锋，等.多区域通勤定制公交线路规划模型及求解算法[J].交通运输系统工程与信息，2020（4）：166-172.

[4]许智宏，王怡峥，王利琴，等.关于大数据的车辆动态线路遗传优化仿真研究[J].计算机仿真，2020（6）：122-125.

[5]刘晓峰，陈通.PSO算法的收敛性及参数选择研究[J].计算机工程与应用，2007（9）：14-17.

[6]SHI Y，EBERHART R C.Empirical Study of Particle Swarm Optimizer[C]//Proceedings of the 1999 Congress on Evolutionary Computation.1999.

[7]高明瑶，石红国.基于改进PSO算法的轨道交通接运公交线路优化问题[J].交通运输工程与信息学报，2019（4）：49-54.

[8]张耀军，谌昌强.基于改进量子PSO算法的可约束车辆路径优化[J].计算机测量与控制，2014（9）：2875-2878.

[9]董锴，崔艳林，周巍，等.基于PSO算法的電力系统状态评估分析方法研究[J].电子设计工程，2020（14）：158-162.