0 引言

近年来, 随着互联网经济的蓬勃生长, 相关行业对快速、高效的物流配送效劳的需求愈加迫切。我国物流行业的特点是起步晚、需求大、生长快, 在粗放式的生长历程中遗留下治理欠缺规范, 配送效率低下等问题[1]。利用盘算机技术实现物流配送作业计划的合理制定, 是解决前述问题的有效手段。本文以单仓储中心的多车物流配送作为应用场景, 则多台配送车辆的路径计划问题可建模为图论中经典的车辆路径问题 (Vehicle Routing Problem, VRP) [2]。由于实际生活中配送任务往往带有一定的时间限制, 所以又泛起了带时间窗的车辆路径问题 (Vehicle Routing Problem with Time Windows, VRPTW) 。VRPTW是在VRP的基础上增加客户要求会见的时间窗口, 且时间窗可分为软硬两种:硬时间窗VRP指每项任务必须在要求的时间规模内完成, 不然获得的解为不可行解, 而软时间窗VRP则是在凌驾要求时间规模时, 给予一定的处分[3]。VRP具有NP完全问题 (Non-deterministic Polynomial Complete, NPC) 求解庞漂后[4], 因而不保存多项式时间算法, 一般以模拟退火[5]、禁忌搜索[6]等启发式算法或以遗传算法[7]、蚁群算法[8]等智能算法进行求解。

粒子群优化 (Particle Swarm Optimization, PSO) 算法是智能算法的优秀代表[9], 因其简洁的内在寻优机理与快速的收敛速度而被广泛应用于VRP以及VRPTW的求解, 并由此衍生出许多革新算法[10,11,12,13,14,15]。李宁等[3]将粒子种群划分为若干个部分重叠的子群, 各粒子凭据所属子群内的最优解调解其位置。吴耀华等[10]将子群的看法同近邻机制[11]相结合提出局部近邻机制, 使粒子在更新速度时借鉴局部近邻粒子的优势, 提高算法收敛速度。马炫等[4]在粒子群算法的基础上引入粒子交换原理, 提出了一种整数粒子更新要领。马冬青等[12]为了增强算法的局部搜索能力, 在算法中增加了爬山操作。

以上研究大部分都是对算法中参数和调理因子的革新, 很少考虑粒子表达方法保存的问题。其中文献[3,4,10]均接纳了双层的粒子模型, 凭据先分组再排序的规则进行编码, 第一层体现各任务点对应的车辆, 第二层体现各任务点在对应的车辆运送路径中的优先顺序。由于分组与排列之间具有强耦合关系, 第一层编码的变革势必影响第二层编码更大的变换, 同时由于求解历程中直接套用公式, 易爆发小数, 解码时必须进行取整和排序, 导致搜索效率低、不可行解数量多等问题。为解决上述编码保存的问题, 本文结构了一种适用于解决VRPTW的新型粒子表达方法———排位编码方法, 将每个站点的后继站点所组成的序列作为编码, 改变后继即可改变车辆路径;并依据编码特点设计相应的粒子更新方法, 制止因取整和排序造成的不可行解数量多、求解效率低等问题。

1 优化模型

本文仅考虑单仓储中心的多车物流配送场景, 对多车配送作业计划进行如下约定:

1) 各配送车辆以仓储中心为发车起点并返回;

2) 各配送点均须被会见且至多被会见一次;

3) 各车配送任务量不得凌驾车辆载重上限;

4) 各配送点间任意可达, 任意两点距离以欧氏距离盘算。

在以上约定基础上, 若仓储中心有K辆车, L个配送点, 以站点1体现仓储中心, 客户站点2~L+1体现各配送点 (今后为便于区分将配送点称为客户站点) , 那么可将单仓储多车物流配送优化问题描述为:仓储中心用K辆车对L个客户站点进行配送, 各配送车辆的最大载重均为q;客户站点i的配送量为gi (i=2, …, L+1) 且max gi≤q;设完成客户站点i的配送任务需要的时间为Ti, 任务开始执行的时间规模为[ETi, LTi], 其中ETi为允许最早开始时间, LTi为允许最晚开始时间。若车辆抵达站点i的时间早于ETi, 则需在i处期待;若车辆抵达站点i的时间晚于LTi, 则任务需延迟执行[10]。求能够最小化车辆配送总本钱且满足所有客户站点需求的配送作业计划。其中, 配送总本钱可指代距离、用度、时间等一种或多种本钱形式, 本文仅将其作为一种笼统的看法, 不作具体意义的解读, 但这并不影响问题的性质。

问题用数学语言描述如式 (1) ~ (5) :

上述模型中, cij体现车辆从点i行驶至j的行驶本钱, 显然cij=cji。当车辆k完成从点i至j的配送时, xijk=1;不然, xijk=0。当点i的配送由车辆k完成时, yki=1;不然, yki=0;pE, pL划分为单位时间的期待本钱和迟到罚金。式 (1) 中的目标函数min Z确保配送总本钱最小。约束中, 式 (2) 为货车容量限制, 每辆车的配送总量不得凌驾货车载重量;式 (3) 包管每个客户站点只能由一辆车配送一次, 不可重复配送;式 (4) 和式 (5) 则包管所有客户站点都被配送到。

2 粒子群算法简介

PSO依赖于一个种群, 通过种群中各粒子在解空间中的协同航行实现对问题潜在解的搜索。在一个n维搜索空间中, 粒子i的位置可体现为一个n维向量Xi, 其速度以向量Vi体现, 所经历的最优位置记为Pbest_i, 种群中所有粒子经历过的最优位置记为Gbest。粒子航行历程中的速度和位置更新要领以式 (6) 、 (7) 描述:

其中:ω为惯性权重;c1和c2为加速因子, 亦称学习因子;r1, r2~U (0, 1) 。

粒子群算法的盘算流程分为以下几步:

办法1随机初始化各粒子的位置和速度, 将各粒子的初始位置作为Pbest_i, 以目标函数式 (1) 为依据, 对各粒子进行适应度的评价, 把种群最优个体作为Gbest;

办法2凭据式 (6) 、 (7) 划分更新各粒子的速度和位置;

办法3盘算更新后各粒子的适应度值并更新Pbest_i和Gbest;

办法4检验是否满足算法终止条件:若满足, 终止迭代;反之, 返回办法2。

3 求解VRPTW的粒子群算法

3.1 编码与解码

本文在结构编码方法时, 接纳一种基于后继的排位编码方法, 先将所有站点顺次号从小到大排列, 然后凭据各站点实际配送顺序, 在每个站点下填入其后继站点。这样所有后继站点组成的编码就组成了一种粒子表达方法。

例如, 当使用3辆车为9个客户站点效劳时, 车辆路径为:1-4-9-5-1;1-2-7-6-10-1;1-3-8-1。编码结果如图1。

图1 编码结果   

由于3辆车都从配送中心出发, 所以配送中心1的后继站点有3个, 而其余站点都只有一个后继站点。编码中1泛起的次数即是车辆数, 体现所有车辆最后都回到配送中心, 2~10均只泛起一次, 体现每个客户站点都被配送且只配送一次。

解码时, 以配送中心下的每个站点作为每辆车的第1个客户站点, 划分以它们为序号进行索引, 找到的对应元素就是需要配送的第2个站点, 再以第2个站点为序号继续索引, 直至最后所有车辆都回到配送中心。

这种编码方法有以下特点:首先选用整数编码, 与车辆路径问题的离散性相适应;其次从某个元素所对应的序号和该元素的巨细可以断定它们代表的两站点之间保存一条车辆路径, 那么改变某个序号位置下的元素, 就改变了对应站点的后继站点, 所以可以通过变换编码, 实现车辆路径的改变。车辆路径的改变相当于粒子群算法中粒子的位置爆发改变, 这一点又与算法的要求相吻合。

3.2 适应度函数和约束的处理

本算法要寻找的目标解是总本钱最小的行驶计划, 而总本钱中行驶本钱占的比重最大, 所以在确定适应度函数时, 行驶本钱是主要评判标准。其次考虑约束:针对时间窗约束, 接纳增加期待本钱和迟到罚金的手段;针对车辆的载重量约束, 引入外部罚函数, 付与不可行解或不法解一个极大值, 将有约束最优化问题转化为无约束最优化问题。设某辆车分派的总任务量, 那么适应度函数写成表达式的形式如式 (8) :

式 (8) 中S是粒子目今位置的适应度值, 等号右侧前三项划分对应行驶本钱, 期待本钱和迟到罚金, 即目标函数, 最后一项为超载本钱, p为单位超载的处分因子。

群体中粒子的位置每次爆发变革后, 都要进行适应度的盘算, 并将其与粒子历史个体最优进行比较。若目今位置的适应度小于历史个体最优, 则用目今位置替换历史个体最优, 不然保存。再通过比较所有粒子的历史个体最优, 找出适应度最小的替换种群的历史全局最优。

3.3 粒子更新

由于接纳了全新的粒子编码形式, 粒子速度与位置的更新无法直接套用式 (6) 、 (7) , 因而需要在对粒子速度与位置更新公式理解的基础上, 重新设计相应的算子, 以实现粒子种群在解空间中的协同搜索。

对PSO粒子更新公式进行剖析, 令G1=ω·Vi (t) 、G2=c1·r1· (Pbest_i (t) -Xi (t) ) 、G3=c2·r2· (Gbest (t) -Xi (t) ) , 则式 (6) 可简写为V=G1+G2+G3, 其中认知项G2和社会学习项G3决定了粒子对解空间的开采能力, 是粒子以向更优个体趋近的方法实现优化的一种学习机制;惯性项G1则确保了粒子对解空间未知区域的勘探能力。不失一般性, 一个群智能优化算法具备优秀寻优能力的前提是能够很好地平衡开采和勘探。只注重开采而缺少勘探, 算法体现为局部收敛;只注重勘探而缺少开采, 算法体现为盲目地随机搜索。

在对PSO粒子更新公式进行上述剖析的基础上, 本文利用已有的编码特点, 设计了基于“学习”和“变异”的粒子更新要领, 具体操作办法如下:

3.3.1 学习

如前所述, 开采实质上是粒子以向更优个体趋近的方法实现优化的一种学习机制。目今粒子向更优个体的趋近历程具体体现为两粒子编码差别的逐步缩小。据此, 学习机制中只考虑G2和G3项, 忽略G1项, 同时界说k1, k2为学习因子, 其作用同c1·r1, c2·r2, 那么式 (6) 、 (7) 可合并改写为式 (9) :

式 (9) 中涉及三种运算。本文对这三种运算界说如下:

1) 体现确定x中差别于y的元素及其位置信息;

2) 体现从x中随机选取部分元素, 且该部分元素占x中总元素个数的k倍;

3) 体现依据y中元素及其位置信息修正x的对应部分。

说明以上运算的具体实现办法:

办法1确定Pbest_i (t) 和Gbest (t) 中差别于Xi (t) 的部分, 即:和;

办法2凭据学习因子k1, 从中随机提取对应个元素, 完成的运算, 的运算同理;

办法3凭据界说3) , 以G2所得结果修正Xi (t) 中的对应部分, 获得新编码Xi (t) ', 再以G3所得结果修正Xi (t) ', 获得Xi (t+1) 。

需要强调的是, 若将G2所得结果中的站点称作目标点, Xi (t) 中对应位置的待修正站点称作初始点, 那么办法3中“修正”具体指:将Xi (t) 中的初始点更换为G2所得结果中相应位置的目标点, 同时将Xi (t) 中原本即是目标点的元素更换为初始点, 实际操作时将Xi (t) 中即是目标点的元素与初始点交换位置即可。别的在执行办法2时需检测是否有自环爆发。所谓自环, 就是指几个客户站点独立成环, 没有遵循从配送中心出发并回到配送中心的原则。自环爆发的原因在于目标点和其对应的初始点位于同一辆车的配送路线上。例如, 某辆车的配送路线为1-2-4-7-5-6-1, 当目标点为6, 初始点为4, 将4和6交换后, 这条线路被拆分为1-2-6-1和7-5-4-7-…, 这就导致了7, 5, 4这三个站点独立成环。为了制止自环, 在选定目标点时需检验其是否保存于初始点所在的线路中, 若保存, 则需重新选择目标点, 并再次检验。

举例目今粒子向个体最优粒子学习的操作:

Pbest＿i (t) 体现的车辆路径为:1-2-4-7-1;1-3-5-6-1。

Xi (t) 体现的车辆路径为:1-2-7-1;1-5-3-4-6-1。

首先找出两粒子编码中的差别之处, 共5处, 若k1=0.2, 则需要随机选取的元素个数为1。若选择第2站点的后继进行学习, 那么Xi (t) 中第2站点的后继7为初始点, Pbest＿i (t) 中第2站点的后继4为目标点。经检验在Xi (t) 中站点7和站点4不在同一条路径上, 所以切合交换条件。接下来将Xi (t) 中的7与4进行交换, 获得Xi (t) '的编码, 学习历程中粒子的编码变革如图2所示。

经过学习之后, Xi (t) '体现的车辆路径为:1-2-4-6-1;1-5-3-7-1。车辆路径从之前的配送完第2站点配送第7站点, 变为配送完第2站点配送第4站点, 这一路线的改变即是借鉴了Pbest＿i (t) 的结果。同理, 再以G3所得结果修正Xi (t) '即可得Xi (t+1) 。这种更新方法操作简洁, 且盘算历程中不会爆发小数, 解码便当, 同时制止了因取整和排序而泛起不可行解的现象, 提高了算法的搜索效率。

图2 学习历程中粒子的编码变革 

3.3.2 变异

学习机制付与粒子开采能力, 粒子之间通过相互学习使种群逐渐收敛, 虽然历程中会爆发差别于初始解的新解, 但其搜索规模始终局限于初始解空间, 容易陷入局部最优解。为了扩大种群搜索规模, 需要粒子具备空间勘探能力, 即式 (6) 中的惯性项G1, 本文通过在迭代历程中引入变异机制来实现这一功效。变异机制中只考虑G1项, 忽略G2和G3项, 同时界说Pm为变异率, 那么式 (6) 、 (7) 可合并改写为式 (10) :

式 (10) 中的运算同学习机制中的界说, Vi (t) 为随机生成的粒子编码, ω为变异强度, rnd为区间 (0, 1) 上的随机数。

由于Vi (t) 是随机生成的, 所以在实际操作中借鉴学习机制, 随机交换某两个站点的后继站点, 即可完成变异操作。变异历程中同样需要制止自环的爆发, 但这里使用和学习机制中差别的要领。因为在学习机制中, 更优粒子的编码是确定的, 当目标点选准时其对应的初始点也是确定的, 但在变异机制中, 初始点和目标点都是随机的, 所以可以先选定初始点, 然后把初始点所在线路上的所有客户站点从全部站点荟萃中剔去, 再从剩余站点中选取目标点直接进行交换, 从泉源上杜绝自环的爆发。

举例粒子的变异操作:

Xi (t) 体现的车辆路径为:1-2-3-7-1;1-4-8-1;1-6-5-1。

编码中共包括10个元素, 若ω=0.1, 则需要交换的元素对数为1。选择第3站点的后继站点7作为初始点, 将站点7所在线路上的所有客户站点即2, 3, 7从全部站点荟萃中剔去, 然后从剩余站点中随机挑选一个, 好比站点8作为目标站点, 进行交换, 获得Xi (t+1) 的编码。变异历程中粒子的编码变革如图3。

Xi (t+1) 体现的车辆路径为:1-2-3-8-1;1-4-7-1;1-6-5-1。

图3 变异历程中粒子的编码变革   

3.4算法流程

针对VRPTW优化模型的特点, 本文首先结构编码使问题越发适应算法, 然后凭据实际问题的目标和约束设置适应度函数, 之后在编码方法的基础上设计了基于“学习”和“变异”的粒子更新要领, 在包管种群收敛的同时扩大搜索广度, 制止陷入局部最优, 最终找出全局最优解。粒子位置更新的完整数学表达如式 (11) 。本文所提算法可以图4所示的流程描述。

图4 求解VRPTW的粒子群算法流程  

4 仿真实验

为了验证算法的有效性并考察相关参数对算法性能的影响, 以Matlab对算法进行了编程实现。仿真平台为Intel Core i5-5200U CPU@2.2 GHz, 4 GB RAM。

4.1 仿真算例

接纳文献[4]中20个任务点的算例, 对各站点进行重新编号, 配送中心用序号1体现, 20个客户站点用2到21体现, 各站点的要求如表1。车速为50 km/h, pE=pL=50, p=100, 单位运输本钱为1。使用5辆车进行配送, 每辆车的载重量都为8 t。

表1 站点列表 

为了比较, 文中算法取与文献[4]相同的种群规模和迭代次数划分为100和1 000, 同样运行10次。本文算法参数设定如下:k1=k2=0.3, Pm=0.6, ω=0.15。比照结果如表2所示。本文最优解的车辆路径为:1-2-5-13-1;1-9-6-18-15-16-7-1;1-21-19-4-1;1-11-8-20-1;1-3-12-14-17-10-1, 如图5 (a) 所示。文献[4]最优解的车辆路径为1-21-13-1;1-2-3-5-6-4-1;1-9-12-14-10-7-1;1-19-17-18-15-16-1;1-11-8-20-1, 如图6 (b) 所示。

表2 本文和文献[4]算法实验结果比照  

图5 本文和文献[4]算法获得的车辆路径比较 

视察表2中的数据和图5中的车辆路径可以发明, 参考文献[4]中最优解的车辆行驶总路程较短, 所以行驶本钱低于本文中的最优解, 但其期待本钱过高, 也就是说文献[4]中的算法用过高的期待本钱换取较低的行驶本钱。而本文提出的算规则是在减小行驶本钱的同时控制期待本钱的增长, 所以获得的最优解优于文献[4]算法。

由此可见, 本文提出的编码方法与粒子群算法具备较好的寻优能力, 能够有效解决单仓储中心情景下的多车物流配送优化问题。

4.2 实验中参数的选取

4.2.1 学习因子的选取

学习因子在本算法中代表了粒子向个体最优和全局最优学习的强度, 用目今粒子向更优粒子学习的元素个数占两粒子海明距离的比例来体现。接纳4.1节的算例, 坚持算法中其他参数稳定, 选取差别的学习因子进行实验, 为减小偶然因素导致的偏差, 每种情况运行程序20次并盘算出平均值, 对算法收敛后的适应度值的漫衍进行三阶最小二乘拟合, 结果如图6 (a) 。

视察图形曲线可以发明, 当学习因子位于0.25~0.3时种群收敛后的适应度值抵达最低, 所以, 学习因子在[0.25, 0.3]区间内取值时, 种群收敛于全局最优的概率最大。

4.2.2 变异率和变异强度的选取

变异率和变异强度的作用同标准粒子群算法中的惯性权重, 都是为了使算法在勘探和开采上取得平衡。在本问题中, 变异率指种群中爆发变异的粒子数占粒子总数的比例, 变异强度指变异的粒子中爆发交换的站点对数占总站点个数的比例。同样接纳4.1节的算例, 实验历程和剖析如下:

视察变异率对算法精度的影响时, 坚持算法中其他参数稳定, 对变异率取差别值, 划分运行程序20次并盘算出平均值, 对算法收敛后的适应度值的漫衍进行四阶最小二乘拟合, 结果如图6 (b) 。视察变异强度对算法精度的影响时, 对变异强度取差别值, 结果如图6 (c) 。

图6 几种实验参数对算法精度的影响   

从图6 (b) 中可以看出, 变异率在[0.5, 0.7]区间内时, 种群收敛后的适应度值抵达最小, 因此推断在该问题中将变异率设置在0.6四周时算法在搜索广度和深度上取得平衡, 求得最优解的概率较大。变异率的取值应遵循以下纪律:如果种群较快收敛至局部最优, 则需要增大变异率, 使更多的粒子飞出目今聚集的区域, 去更远的解空间中寻找是否保存更优解。如果种群中的粒子运动过于疏散, 长时间不收敛, 就需要减小变异率, 增强局部搜索, 包管种群在可接受的时间内收敛。

从图6 (c) 中可以看出, 当变异强度在0.2四周时, 算法求得最优解的概率较大。说明就目今种群的规模而言, 粒子的变异强度在[0.15, 0.25]区间内时, 取得比较适合的航行步长, 太大则易导致开采不敷细致, 太小则造成勘探能力缺乏。

总结实验结果, 算法中参数的选取具有一定的纪律可寻, 当参数取值从小到大变革时, 算法收敛后的适应度值总是先减小后增大, 并且能够在一个较宽的区间内取得最优。说明算法收敛精度受参数影响相对较小, 鲁棒性较强。

5 结语

本文提出了一种适用于解决带时间窗车辆路径问题的粒子群优化算法。首先结构排位编码方法将算法与问题紧密联系起来, 其次依据PSO原理设计了基于“学习”和“变异”的粒子更新要领, 实现粒子种群对解空间的开采和勘探。通过学习使种群中的粒子在认知和社会部分的影响下逐渐收敛, 而变异则增强粒子在解空间中的勘探能力, 制止陷入局部最优解, 最终在可接受的时间内找出令人满意的解。

针对实际生爆发活中的车辆路径问题可以在此算法的基础上凭据差别要求进行优化, 例如进一步提高解的质量:可以将粒子群划分为若干个两两相互重叠的相邻子群, 从而进一步减小算法陷于局部最优解的可能;增加更多的约束, 使之更切合实际问题:考虑站点之间的实际距离和可达性;增加算法可解决问题的场景:考虑将算法应用到多仓储中心的物流配送优化中等。