基于粒子群算法的最优物流运输线路规划方法研究

叶平

(上海邦德职业技术学院 经济与管理学院，上海 200444)

0 引言

科学、合理的物流运输路径能够大大降低物流成本，提高物流经济效益。这就要求我们对物流运输路径进行优化设计，进而提高物流运行效率。对于一个城市的交通网络来说，道路交叉口是实现交通流疏散的重要节点，但同时也是影响城市通行能力的主要因素，这就对物流运输造成了一定的影响[1]。

为优化物流运输路径，提高物流运输效率，首先需要有效地对城市交叉口的车流量进行控制。目前已有一些学者在车流量控制方面开展了大量的研究和应用，先后提出了多种交通控制方法和模型，如基于PLC的交叉口车流疏导系统[2]、拥挤车流控制技术[3]、交通网络流量预测与控制方法[4]等，对改善道路交通状况、缓解交通压力提供了重要支持。在此基础上相关学者提出了物流运输车辆的运输路径研究。文献[5]提出了基于多准则的帕累托最优公交路线的定义，利用随机搜索方法，通过估计每个解空间的值来指导搜索过程。文献[6]研究了一类随机需求下的电动汽车电池交换站选址—路径问题，提出了一种混合可变邻域搜索算法，该算法将二进制粒子群算法和可变邻域搜索技术相结合，以交互式方式解决位置和路由问题。

总的来说，国内外物流运输路径的研究方向主要分为以上5个方向，关于国内外产品物流现状的研究较多，且多集中于物流系统更新重造，相关研究针对带时间窗的多目标车辆路径规划问题，构建运输成本最低与客户满意度最高的配送路径优化模。但是，关于产品运输工具的研究较少，几乎都是对飞机、铁路和汽车这3种传统运输工具的研究，对于高速铁路运输的研究涉及较少。

虽然上述方法在一定程度上实现了路径优化，提高了运输效率。但是在面对车流量巨大的城市中，路径的选择和优化上还存在一定的制约。为解决这一问题，提出一种基于粒子群算法的最优物流运输线路规划方法，首先利用车联网技术实现城市交叉口交通的合理管控，然后充分利用粒子群算法的优势，组建引导需求和指令匹配对车辆的引导路径进行规划，实现物流运输线路的最优规划。

1 城市交叉口交通的合理管控

利用智能交通与物联网技术高效结合的车联网技术，通过多种信息传感器对车辆交通情况和信息进行收集，实现对车辆、道路和人的智能调度、协调和管理。利用车联网技术在车流量控制过程中，获取、传输和处理交通信息对城市交叉口交通的合理管控尤其重要。其中，车辆网的结构如图1所示。

图1 车联网结构示意图

其中，应用层由安全调控、车路协同系统等组成，结合大数据等技术让车联网显示实际价值。网络层主要信息的传递，由Wave协议栈和多种通信技术结合，是整个车联网的核心部分。感知层主要进行信息的采集，包括车辆信息、道路信息等，其中应用了3S技术、定位技术、数据处理技术等，是车联网有效运行的基础保障。应用层、网络层、感知层之间相辅相成、紧密联系、不可分割。

利用图1中的车联网结构获取相关信息，主要包括如下4类：车辆信息，如速度、位置、数量环境参数等[7]；路边供应设备信息，如车流密度、交通密度、位置状态、障碍物、行人状况等[8]；网络传输紧急状况信息，如道路维修及养护信息、交通事故信息、紧急状况等；社会资源信息，如停车场、加油站等。根据对相关信息的收集，建立的城市交叉口车辆动态信息流获取模型如图2所示。

图2 城市交叉口动态车辆信息流获取模型

通过车联网技术获取城市交叉口的交通信息，建立城市交叉口车辆动态信息流获取模型，获取、传输和处理交通信息对城市交叉口交通的合理管控信息，为车流量预测提供信息基础。

2 基于粒子群算法引导和规划物流运输路径

2.1 车流量预测

在进行车流量智能控制之前，首先需要对车流量进行预测。随机选取一个城市交叉口为预测点，车辆经过该预测点需要满足如下条件[9]。

(1)在不重叠的时间内，经过的车辆数量是独立的。

(2)对于足够小的时间段Δt，时间区间[t,t+Δt]内车辆经过的概率与t不产生关联，则有p(t,t+Δt)=μΔt+o(Δt)，其中μ表示单位时间经过的车辆数量；p(t,t+Δt)表示在时间区间[t,t+Δt]内有一辆车经过该预测点的概率，以此类推，pn(t1,t2)=p{N(t2)-N(t1)=n}，N(t)为[0,t]时间段内经过的车辆总数；n为可能经过的车辆数。

由于上述条件满足泊松分布所需要的前提，因此利用泊松分布模型对城市交叉口车流量变化进行预测[10-11]。根据条件(1)、条件(2)可得式(1)

(1)

根据条件(2)、条件(3)可得式(2)

(2)

令Δt→0，则车流量预测模型为式(3)。

(3)

2.2 车辆路径引导设计

在上述城市交叉口车流量智能控制方法的基础上，基于粒子群算法对车辆进行路径引导，进一步实现不同路况下的车流量调控，实现物流运输的最优路径规划，保障路面交通状态的平稳性。当粒子由于局部最优值而陷入停滞时，让该粒子向其个体历史最差位置进行学习，快速引导这些粒子逃离最优值，提升种群的多样性，提高算法的搜索能力。PSO算法流程图如图3所示。

图3 PSO 算法流程图

利用泊松分布模型预测城市交叉口车流量变化，结合粒子群算法组建引导需求和指令匹配，对车辆进行路径引导，进一步实现不同路况下的车流量调控，实现物流运输的最优路径规划。

2.2.1 路径引导需求组建

为了保证高质量的交叉口车流量控制和车辆路径引导，需要捕捉动态车辆的数据。采用粒子群算法[12-13]结合三元问题法对在最小代价条件下对城市交叉口动态车辆信息进行筛选判断，其表述如式(4)。

(4)

其中，x代表一项动态路径引导的原子任务；y代表安全项；z代表突发事件后原路径可行状态；L代表执行任务的最小代价；Prec代表车辆信息流；Tras代表路径甄选；Effect代表车辆调控确认项。将路径引导数据经过格雷马斯矩阵筛选后得出以下2种选择判断。

(1)当tras 1AT.Tras时，tras.p0=tras.pt；

(2)当tras1,tras2.Tras时，tras1.p0tras2.p0=tras1.pttras2.pt。

其中，tras1为备选路径，如发生事故，那么tras1表示当前状态下选择路径；tras2为备选路径，依次类推。设p0为初始状态的路径引导任务状态集合，目的地状态判断集合为pt。根据格雷马斯矩阵进行如下判断，为式(5)。

(5)

由式(5)可以看出，当突发任务集合M为空时，任务保持选项；当突发任务集M不为空，则需要通过类型匹配计算进行引导路径的重新判断。

2.2.2 路径引导指令匹配

想要动态车辆路径引导得到安全、稳健的运行，需要让路径引导需求与路径引导算法达到匹配，这就要通过agent算法，针对车辆的路径进行规划，当引导需求与 agent 算法范围重合时，从引导需求输入到算法处理以及判断结果输出的过程就可以实现一次动态车辆的路径引导[14-15]。采用相似度函数以及语义距离方法将引导需求与agent算法规划能力相匹配，该过程如下。

(1)注册规划申请；

(2)设置不匹配判断条件，确认所接收到的引导需求是否与agent算法规划能力相匹配；

(3)返回。

根据当前引导需求设置agent算法参数R{Sio,Sim,Sit,Outi},其中Sio,Sim,Sit分别代表R的初始状态，运行中状态和最终状态，Outi为R的输出集合。

当agent算法中参数SAi{Sio,Sim,Sit,Outi,Reli}，其中Sio,Sim,Sit,Outi,Reli分别表示S的初始状态、运行中状态、最终状态和输出集合。Reli表示S的依赖关系集合。路径引导需求与算法引导能力匹配代码如下。

RSMatdhSA(rs,sa):

InPut:R,

S,

OutPut:TRUE(匹配)，

FALSE(不匹配).

//返回车联网数据加载，

进行数据更新//

该部分判断了agent算法规划范围及其子功能模块与路径引导需求的范围是否匹配，匹配时完成路径引导，不匹配时返回车联网数据库，进行算法知识库的更新后再进行匹配，得出最优路径，进而实现对城市交叉口车辆路径的智能、有效引导。

3 实验及结果分析

为了验证基于粒子群算法的最优物流运输线路规划方法的有效性，选取某城市的真实道路网，采用PreSdan软件对所选道路进行微观场景重建。该交通场景共计路段29个，共存在20个路口，其中12个三叉路口、5个直行路口、3个十字路口。交通场景的3D效果图如图4所示。

图4 交通场景的3D效果图

从图4可以看出，实验所选路段路口繁多，极容易出现交通拥堵。为了便于对路口进行观察，故此，将图像由3D简化为网络拓扑图简化拓扑图，并对道路路口进行了编号排序，如图5所示。

图5 实验路段交通场景拓扑图

3.1 车辆路径引导效果检验

采用所提方法和文献[2]方法、文献[3]方法在道路交叉口拥堵情况下，对车辆进行路径疏散引导，对引导效果进行比对。所提方法与文献[2]方法、文献[3]方法的路径引导结果如图6所示。

由图6可以看出，采用文献[2]方法引导后，车辆经过编号1、3、4、8路口，在编号11路口处再次拥堵无法前进。采用文献[3]方法引导后，车辆经过编号1、2、5、9、11、16路口后，在编号16路口处无法前进。而采用所提方法引导后，车辆在经过11号路口时，智能选择折返回归到8路口转向7、6、10、13路口最终完成车辆的安全引导。且在速度相同情况下，所提的引导方法在时间和效率上优胜于其他2种方法，说明了基于粒子群算法的最优物流运输线路规划方法能够在多个交叉口路口进行实时监控，更好地完成疏导车流的任务。

文献[2]方法

3.2 物流运输线路运输效率检测

以十字交叉口为实验对象，为检验所提的基于粒子群算法的最优物流运输线路规划方法的运输效率，以文献方法为对比对象，检验2种方法下的城市交叉口信号平均延误和车辆停车次数。实验结果如图7、图8所示。

图7 交叉口信号平均延误对比图

图8 交叉口平均停车次数对比图

分析图7和图8可知，所提的基于粒子群算法的最优物流运输线路规划方法的信号控制和车流量控制要优于文献方法，可有效降低城市交叉口信号的平均延误和交叉口处的车辆平均停车次数，进一步提高物流运输线路的运输效率。与文献方法相比，当车流量较小时(2 400 veh/h)，交叉口信号平均延误时间和平均停车次数分别降低约18% 和22%；当车流量较大时(7 200 veh/h)，交叉口信号平均延误时间和平均停车次数分别降低约32% 和16%。

4 总结

对城市交叉口车流量进行有效控制，能有效实现车流的疏散和分离，保障城市交通的畅通和安全。对此，本文提出了一种基于粒子群算法的最优物流运输线路规划方法，通过对交叉口信号进行调控和对车辆进行智能引导，实现对城市交叉口交通的合理管控，提高物流运输效率。