基于IPSO算法的多目标车辆配送路径规划研究

陈智勇

青海师范大学,青海 西宁 810000

基于IPSO算法的多目标车辆配送路径规划研究

陈智勇

青海师范大学,青海 西宁 810000

针对汽车零部件车辆配送路径规划问题，提出一种基于IPSO的多目标车辆路径规划算法。以平均行驶成本、等待时间成本和惩罚时间成本为目标函数，建立多目标车辆路径规划模型。研究结果表明，选择搜索成功率、平均行驶成本和搜索时间为评价指标，IPSO算法在搜索成功率和搜索时间以及平均行驶成本方面，均优于GA和PSO算法，同时避免局部最优，对降低配送成本和提升企业竞争力具有重要意义。

粒子群算法;路径规划;多目标函数;数学模型

随着经济和工业技术水平的快速发展，我国汽车工业持续高速发展，汽车零部件制造运输行业发展繁荣，竞争异常激烈，其零部件物流成本的高低直接影响其企业竞争力，车辆配送路径直接影响企业成本和客户服务水平，因此研究汽车零部件运输车辆的路径规划对降低企业成本和提高零部件供应及时率具有重要的实际意义，对提升企业竞争力具有重要意义[1]。大量研究表明，智能启发式算法对求解车辆配送路径规划具有很大优势，本文针对PSO算法存在局部最优和早熟的问题，提出一种改进的粒子群算法IPSO，并将其应用于车辆配送路径规划。

1 改进的粒子群算法

粒子群算法（Particle Swarm Optimization Algorithm，PSO）是受鸟群觅食行为启发提出的智能搜索算法，通过群体间的协作和竞争，实现粒子位置和速度的更新，更新公式如下[2]：

其中，vid(t)和xid(t)分别表示在t时刻时第i粒子的速度和位置；rand1和rand2表示随机数，处于[0 1]之间；c1、c2表示学习因子。

由于PSO算法存在局部最优问题，将随机搜索因子引入PSO算法，提出一种改进的PSO算法，改进模型如下：

其中，公式（4）表示粒子搜索的方向，保证IPSO在约束边界内搜索。公式（5）作用提高IPSO算法初期和后期粒子的全局搜索和局部搜索能力。α为控制参数，决定粒子分布。

2 汽车零部件车辆配送路径规划

2.1 问题描述

汽车零部件车辆路径规划问题可表述为[3,4]：假设一汽车零部件中心仓库，其中心配备有K辆，车辆载重容量为qk(k=1,2,3…,K)，配送需求点有L个，第i个需求点的需求量为C，其中，，完成需求点任务i零部件装载或卸货的时间为Ti，其中任务i必须在时间段[ETi, LTi]内完成，ETi,LTi分别表示任务i的最早开始时间和最迟开始时间。若配送车辆早于E Ti到达，则等待；反之，任务将被延迟。汽车零部件车辆配送示意图和需求点空间分布图如图1和图2所示。

图1 配送示意图Fig.1 The schematic distribution routes

图2 空间分布图Fig.2 The spatial distribution

2.2 数学模型

针对汽车零部件车辆路径规划问题的描述，汽车零部件中心仓库编号为0，需求点编号为1,2,3...,L，任务和中心仓库均被编号为 i=(0,1,2,3...,L)，决策变量定义如下[5]：

汽车零部件配送车辆路径规划数学模型如下：

其中，cij表示由点i到点j的运输成本；Si表示配送车辆到达需求点i的时间；pE，pL分别表示车辆提前达到需求点i的单位时间内的等待成本和滞后到达需求点i的单位时间内的惩罚成本。

该数学模型要求需求点都有车辆进行配送服务，并且每个需求点只能由一辆配送车辆负责完成，此外，同一条配送路径上的需求点的需求量之和不能超过配送车辆的最大载重。

3 基于IPSO算法的车辆路径规划

3.1 构造粒子表达

实现路径的最优规划，构造合适的粒子表达方式是解决该问题的关键。文中参考文献[6]，构造一个2L维空间对应L个需求点任务的车辆路径规划问题，使得需求点任务对应为2维。完成车辆被编号为k，此任务在车辆k的行驶路径中的顺序为r，为了便于计算和表达，PSO每个粒子对应的2L维向量X被划分为两个长度为L的向量Xv和Xr，二者分别表示任务对应的车辆编号和对应车辆的行驶路径中的顺序。

若需求点任务为7，配送车辆为3，此时若粒子位置向量X为：

需求点任务编号为：1234567

Xv:1 2 2 2 2 3 3

Xr:1 4 3 1 2 2 1

那么，该粒子对应的车辆配送路径为：

车辆1：0 1 0

车辆2：0 4 5 3 2 0

车辆3：0 7 6 0

3.2 算法步骤

Step1:种群初始化；（1）将粒子群划分为若干个两两互相重叠的相邻子群；（2）位置向量Xv每一维随机取整数，，表示配送车辆的数量，Xr取实数，；速度向量Vv每一维随机取整数，，Vr取实数，；（3）根据适应度函数公式（12），计算粒子适应度；（4）将适应度初始值作为粒子个体的历史最优值Pi，以此为参照对象，寻找总粒子群体内最优解Pg和各粒子群体内最优解Pl。

Step 2:根据公式（1）更新Xv、Xr和Vv、Vr，其中Xv向上取整，若V，X超过约束边界，则按边界值取值；

Step 3:计算所有粒子适应度函数值；

Step 5:将总粒子群体内最优解Pg和各粒子群体内最优解Pl与历史最优解进行比较，若优于历史最优解，则更新Pg和Pl；

Step 6:若满足算法停止条件，则输出最优解；反之，返回Step 2。

4 实验分析

为验证本文算法的有效性和可靠性，将本文算法IPSO和PSO、GA算法进行对比，选择参考文献[7～8]中实例为研究对象，其用户需求如表1所示，其中心仓库和各需求点的距离矩阵如表2所示。

表1 用户需求Table 1 User's demand

表2 距离矩阵Table 2 Distance matrix

IPSO参数设置：最大迭代次数1200，种群规模20，学习因子c1=c2=0.5，寻优结果（图3～7）。

图3 距离矩阵图Fig.3 Distance matrix

图4 IPSO配送路径Fig.4 IPSO distribution path

图5 IPSO寻优收敛图Fig.5 Chart of IPSO optimal convergence

图6 PSO配送路径Fig.6PSOdistributionpath

图7 PSO寻优收敛图Fig.7ChartofPSOoptimalconvergence

图8 GA配送路径Fig.8GAdistributionpath

图9 GA寻优收敛图Fig.9ChartofGAoptimalconvergence

表3 IPSO、PSO[8]和GA[9,10]对比结果Table 3 Comparison results of IPSO、PSO and GA

由图4～9和表3可知，IPSO算法的搜索成功率为67%，远高于PSO和GA的46%和25%，同时在搜索时间和平均行驶成本方面，IPSO算法也优于PSO和GA，从而验证IPSO算法。

5 结论

车辆配送路径直接影响企业成本和客户服务水平，因此研究汽车零部件运输车辆的路径规划对降低企业成本和提高零部件供应及时率具有重要的实际意义，本文针对PSO算法存在局部最优和早熟的问题，提出一种改进的粒子群算法IPSO，并将其应用于车辆配送路径规划。研究结果表明，IPSO算法在搜索成功率和搜索时间以及平均行驶成本方面，优于GA和PSO算法，效果较好。

[1]胡丽丽,王战备,赵峰.考虑驾驶员满意度的高斯和声搜索物流配送路径优化算法[J].计算机应用研究,2015,32(12):3622-3625

[2]张元标,吕广庆.基于混合粒子群算法的物流配送路径优化问题研究[J].包装工程,2007,28(5):10-12

[3]王华东,李 巍.粒子群算法的物流配送路径优化研究[J].计算机仿真,2012,29(5):243-246

[4]潘国强,胡俊逸,洪 敏.考虑GIS的物流配送区域划分与路径规划算法[J].大连海事大学学报,2015,41(1):83-90

[5]孙妮娜,卢才武,卢 娜,等.应用群智能混合算法优化救灾物资配送路径[J].消防科学与技术,2015(2):263-266

[6]王 华.一种物流配送最短路径混合算法[J].测绘科学,2014,39(9):135-137

[7]叶 勇,张惠珍.多配送中心车辆路径问题的狼群算法[J/OL].计算机应用研究,[2016-09-18].http://www.arocmag.co m/article/o2-2017-09-032.html

[8]马祥丽,张惠珍,马 良.带时间窗物流配送车辆路径问题的蝙蝠算法[J].计算机工程与应用,2016,52(11):254-258

[9]石 兆,符 卓.配送选址-多车型运输路径优化问题及求解算法[J].计算机科学,2015,42(5):245-250

[10]韩李涛,牟乃夏,戴洪磊,等.一种基于分层结构的最优路径算法[J].山东科技大学学报:自然科学版,2013,32(3):77-82

Research on Multi-objective Vehicle Route Program Based on IPSO Algorithm

CHEN Zhi-yong
Qinghai Normal University,Xining 810000,China

In this paper,a multi-objective vehicle route program based on IPSO was proposed to solve the vehicle route problem.The multi-objective vehicle route model was established based on the objective cost,waiting time cost and penalty cost to select the search success rate,average travel cost and search time as the evaluation index.The results showed that the IPSO algorithm in the search success rate and search time and average travel cost was better than GA and PSO algorithm.It is important for avoiding the local optimum,reducing the delivery cost and enhancing the competitiveness of enterprises.

Particle swarm optimization;route program;multi-objective function;mathematical model

TQ018

:A

:1000-2324(2017)02-0255-04

10.3969/j.issn.1000-2324.2017.02.019

2016-10-11

:2016-11-25

陈智勇(1981-),男,硕士,讲师,主要研究方向为统计自动化及其应用.E-mail:chenzhiyong@qhnu.edu.cn