混合粒子群算法求解带软时间窗的VRPSPD问题

范厚明，刘文琪，徐振林，耿 静

1.大连海事大学 交通运输工程学院，辽宁 大连 116026

2.大连海事大学 战略与系统规划研究所，辽宁 大连 116026

1 引言

同时集配货车辆路径问题（Vehicle Routing Problem with Simultaneous Pickup and Delivery，VRPSPD）是VRP中应用广泛的的变体之一，其扩展为每个客户处拥有集货和配货需求且要求车辆服务一次同时满足这两种需求。这种情况在实际生活中也广泛的存在，如：饮料行业空瓶的回收、包装物以及装载设备的循环再利用，工业有毒物品的回收净化再处理等[1]，在减少资源浪费的同时，又能够产生经济效益。现有研究表明，这种配送模式与单向配送相比能够有效地降低成本，提高效益[1-2]。因此随着环保意识的提高和逆向物流的发展，该类问题日益受到研究者的关注。为了更加贴近现实，考虑客户对于车辆到达时间有要求的实际情况，本文求解了更一般化的带软时间窗VRPSPD问题，即允许车辆到达时间违背时间窗约束，并产生相应等待或耽搁成本，这样处理不仅可以更好地从配送企业角度衡量工作效率，同时也能更好地保证一定的服务水平。

VRPSPD最早由Min[3]提出，解决了中心图书馆与地方图书馆之间图书分发与回库的问题。Dethloff[4]首次从逆向物流的角度对问题进行了定义，并采用一种考虑车辆剩余装载能力的插入启发式算法进行求解。由于VRPSPD是NP-hard问题[5]，因此更多的此类问题的求解方法主要集中于能够在较短时间内获得满意解的启发式算法、模拟退火算法[2]、遗传算法[6-7]、蚁群算法[8-9]、禁忌搜索[10]、量子进化算法[11]，以及混合算法[12]等，获得了一定的研究成果。然而，由于VRPSPDTW（VRPSPD with Time Window）的决策目标、约束条件更为复杂，使求解难度进一步加深，因此相关研究相对较少，仍有进一步研究的需要。曹二保等[5]首次采用差分进化算法进行求解，并提出一种根据解满足约束的情况，进行不断调节得出最小所需车辆数的方法，解决了客户数为8和40的带时间窗的同时集配货车辆路径问题（VRPSPDTW）；Wang和Chen等[13]扩展了Solomon[14]关于VRPTW（Vehicle Routing Problem with Time Window）的测试算例，通过CIM（Cheapest Insertion Method）的多种变形产生初始解，并提出一种共同演化遗传算法对VRPSPDTW进行了求解。王超等[15]采用模拟退火算法求解该问题，其中通过RCRS（Residual Capacity and Radial Surcharge）插入准则获得初始解，在此基础上Wang等[16]又进一步提出并行模拟退火算法对其求解，均与Wang和Chen等[13]的遗传算法进行比较。黄务兰等[17]通过改进的全局人工鱼群算法与平行模拟退火[16]在VRPSPDTW求解结果上的比较，验证了其改进算法的有效性。王超等[18]采用离散布谷鸟算法对VRPSPDTW问题进行了求解，通过Rank值的非参数假设检验对算法进行了验证。Belgin等[19]对二级同时取送货车辆路径问题进行了研究，并采用变邻域下降搜索结合局部搜索算法对该问题进行了求解。

虽然现有研究对于求解VRPSPDTW已获得一定的成果，但是对更贴近现实配送业务要求的带软时间窗VRPSPD研究却寥寥无几。邓爱民等[20]建立了带软时间窗VPRSPD的数学模型，采用增加了记忆功能的改进模拟退火算法对其进行了求解，并通过算例求解验证了算法的可行性，但在求解结果上仍有改进空间。通过上述软硬时间窗模型在整体成本的比较来看，即使车辆在某客户处违背时间窗约束，存在总配送成本相对较低的情况，即求解软时间窗约束的问题有可能产生在硬时间窗约束下难以获得的可行解，并且该类问题的通用性很强，可以经过一些参数或条件的改变转化为其他VRP扩展问题，因此与硬时间窗约束相比，软时间窗约束具有不可替代的优势。从查阅的文献中可知，目前将粒子群算法应用求解于带软时间窗的VRPSPD问题的研究还较少，并且结合不同的启发式算法进行优势互补，已然成为学者研究的重要方向之一。周蓉等[21]提出混合的离散粒子算法对VRPSPDTW进行了求解，结合了变邻域下降（Variable Neigborhood Descent，VND）和模拟退火算法的选择机制，其中是对每个粒子进行一定概率地选择VND。然而在后续的实验结果中得出，不同结合方式在一定程度上影响算法的性能。为了更好地探索和提供不同算法结合的思路，本文提出结合以VND为适应性扰动机制主体的混合粒子群优化算法（Particle Swarm Optimization，PSO），对带软时间窗的VRPSPD进行求解。

PSO是一种基于群体智能搜索算法，模拟鸟类飞行的仿生算法，有着概念简单清晰，参数较少，鲁棒性好等优点，且在各类多维连续空间优化问题上表现出良好的特性[22]，在VRP及相关领域也有广泛应用，并取得较好的结果[22-27]。在PSO的参数中，惯性权重具有平衡全局和局部搜索的作用，因此本文所提算法在PSO中加入了适应性权重。但是由于其进化只是根据粒子个体自身经验信息和种群中的信息共享，所以容易陷入局部最优，出现早熟的现象，且爬山能力弱，不易跳出。本文提出结合以VND为主体的适应性扰动机制（Adaptive Perturbation Mechanism，APM）的混合粒子群搜索算法，能够更好地根据种群陷入局部极值的情况进行适应性扰动，其与以往采用扰动机制的文献[28-30]的不同之处：

（1）算法在种群迭代过程中，很有可能不只一次陷入局优，且每次陷入局优的情况不同，本文提出线性变化的调取APM准则，这样可以在充分发挥PSO全局搜索性能的前提下，提高搜索效率。

（2）在Shaking阶段中，不是所有的邻域结构都被采用，也不是随机或依已有概率来进行邻域结构的选取[5，16，28，30]，而是根据适应权重采取轮盘赌的方式进行选取。

（3）对于扰动后产生的劣解不是一味地舍去，而是根据一定准则接受（详见3.4.3小节），以便跳出局优。

本文主要研究带软时间窗的VRPSPD问题，设计了结合以VND为主体的适应性扰动机制的混合PSO算法进行求解，以车辆派遣成本、行驶成本和时间窗惩罚成本之和为总优化目标。实验结果分析表明，算法具有良好的寻优性能。

2 问题描述及数学模型

2.1 问题描述

VRPSPDSTW问题可以描述如下：多台同质车辆从物流中心出发，为一系列客户点进行服务，且每个客户处均设有独立的服务时间窗。软时间窗约束允许车辆到达时间早于或晚于所设时间窗，并根据偏离时间窗的长短进行惩罚。每辆车在访问客户点时，先卸货后取货，一次性满足客户的集配货需求，并且在任何服务节点均不得超过车辆容量限制，在服务完所分配的客户后，返回物流中心。要求在满足所有客户需求的前提下，使得车辆派遣成本、行驶成本和时间惩罚成本之和最小。可做如下假设：

（1）已知各客户和物流中心的位置，且客户处的送取货量已知。

（2）每个客户只能一辆车访问一次，并且要求车辆同时满足集配货两种需求。

（3）物流中心拥有多台同质车辆，即容量一致，且能够满足所有客户的需求。

（4）车辆平均行驶速度已知且不变。

（5）客户的服务时间窗已知。

2.2 问题描述模型建立

为了方便建模描述VRPSPDSTW问题，本文采用如下的符号体系。

Q：车辆最大容量；

Di：客户i处的配货量，非负值且小于Q；

Pi：客户i处的集货量，非负值且小于Q；

ETi：客户i的时间窗下限；

ELi：客户i的时间窗上限；

Tik：车辆k在客户i的到达时间；

WTi：客户i的等待时间，即WTi=max{ETi-Tik,0}；

si：客户i的服务时间；

dij：车辆从客户i到客户 j的距离（采用欧几里得距离得到）；

tij：车辆从客户i到客户 j的行驶时间；

n：总的客户数，其中采用i、j表示客户编号；

m：总的车辆数，其中采用k表示车辆编号；

cv：每辆车的派送成本；

cd：单位距离运输成本；

CTi：车辆早于时间窗到达时，单位时间机会损失成本；

CLi：车辆晚于时间窗到达时，单位时间惩罚成本；

yijk：表示经由客户i到客户 j的车辆k，离开客户i的车辆载重量；

xijk：为决策变量。若车辆k从客户i直接到达客户 j，xijk=1，否则为0。

建立相应的数学模型如下：

式（1）为目标函数，其中第一部分表示车辆派遣费用；第二部分表示运输费用；最后一部分是由早到或晚到时间惩罚成本构成；式（2）确保派出的车辆数不超过最大车辆数；式（3）各节点车辆进出平衡，当i为0时，表示车辆从中心出发后又返回中心；式（4）确保每个客户只被一辆车访问，且只能访问一次；式（5）为消除子回路约束；式（6）表示路径上任意节点处的车辆载重均不超过最大载重量；式（7）表示车辆从中心出发时的载重量与所要配送的客户的配货量相等，且不超过Q；式（8）表示车辆返回物流中心，载重量为所服务客户总的取货量，且不超过Q；式（9）车辆在经由前后客户节点后的载重平衡，即车辆离开节点j的载重量等于车辆到达时的载重量去掉 j的配货量，增加 j的取货量；式（10）表示时间约束，其中M 为一个任意大的数；式（11）、（12）为变量属性约束。

3 混合PSO算法设计

3.1 PSO基本原理

PSO算法最初是由Kennedy和Eberhart于1995年提出一种新的仿生进化算法[31]，模拟鸟群觅食行为，通过鸟之间的协作和个体经验来引导鸟群的整体运动。在PSO算法中，每个备选解抽象成一个无质量的粒子，若干个粒子形成一个种群，搜索过程为每个粒子追随两个极值，一个是粒子本身历史搜索的个体极值 pbest，另一个是全种群到目前为止搜索到的群体极值gbest。所有粒子都有一个根据目标函数所确定的适应值进行评价，有相同维度的位置和速度向量，速度来决定各个粒子飞行的方向和距离，其数学描述如下：

设种群中每个粒子代表D维空间中的一个解，在第t代第i个粒子位置表示为，速度表示，该粒子第t代的个体最优位置为 pbestt，种群第t代的种群最优位置为gbestt，在第(t+1)代状态粒子速度和位置更新公式如下：

其中，c1、c2表示加速因子，r表示[0，1]之间的随机数，w表示惯性因子，其大小的设置影响着算法的收敛速度和结果，较大的w有利于跳出局部最优解，有利于提高算法的全局搜索能力，较小的w有利于算法收敛，会增强算法的局部搜索能力。

3.2 粒子编码

为了充分发挥PSO在连续空间优化问题良好的搜索性能，本文采用实数编码方式[25]，即对于拥有n个客户、m辆车的问题来说，粒子的速度和位置均为n维实数向量，速度每一维的整数部分表示所用车辆编号，在同一车辆编号（即整数部分相同）的小数部分，大小顺序对应该客户在此路径中的访问顺序。故每个粒子的位置取值范围为1～m.99，速度取值范围为-(m.99-1)～(m.99-1)。为了保证粒子在可行范围内搜索，限定位置变化范围为[xmin,xmax]，速度变化范围为[vmin,vmax]。

3.3 初始化种群

首先根据3.2节编码方式和设定范围随机生成粒子的速度和位置，然后其中的一半粒子根据最邻近方法并转换成实数编码，产生新的位置，由于粒子的速度和位置是一一对应关系，所以这一半粒子的速度是根据式（14）将前后两个位置相减得到。

由于算法采用的是实数编码，所以本文提出如下映射方法，将最邻近方法产生的解映射为实数形式，即：在同一车辆访问的节点集合中，假设共有n个节点，车辆编号为k，则对于该路径上的第i个节点来说，其位置大小为i×0.99/(n+1)+k。

3.4 适应性扰动机制APM（Adptive Perturbation Mechanism）

在PSO算法中，gbest记录着当前种群经历的最优状态，影响所有个体位置状态的变化过程。若一味地接受更优解，很有可能导致算法的搜索逐渐聚集在局优附近，探索能力减弱。因此，为了改善上述问题，本文通过以VND为主体根据算法搜索进程情况进行适应性扰动，不仅可以扩展搜索的空间，而且可以根据设定的阈值接受劣解，以便跳出局优。同时为了防止因扰动而丢失搜索过的最好解，将Gbest作为历史搜索到的最优解，gbest作为种群极值。

对于扰动机制来讲，一个是扰动的时机，它可以有效地平衡PSO和VND两者之间搜索优势的发挥，另一个是构成扰动部分采用变邻域结构，这两者都对扰动部分产生的效果起着关键性的作用。

3.4.1 线性启动准则

为了更好地发挥PSO的全局搜索能力，同时也为APM过程提供一个较好质量的扰动解，故本文提出如下线性启动准则：

其中iter表示PSO中的迭代次数，noimp_max和noimp_min分别表示最大、最小允许历史最优解Gbest未改进次数，若Gbest在连续多代未得到改进则认为算法陷入局部极值，所以只有当Gbest的未改进次数noimp_times大于viacriterion时，启动APM。

3.4.2邻域结构

在进行VND搜索之前，需要先定义一组邻域结构，本文采用了路径间、路径内等常见的邻域结构来进行扰动。

为了提高执行操作的有效性，在路径间邻域变换中，首先随机选择一条路径，通过计算此路径与解中其他路径重心之间的距离，并将各个距离与所有距离之和的比值作为选择概率，根据轮盘赌规则选择另一条路径r2。

（1）Cross1：由于所选两个路径所含客户数不同，所以分别随机选择交叉点。交叉点将路径划分为两部分，路径r1的第一部分与r2的第二部分结合形成新的路径，同理r1、r2的剩余两个部分结合成另一条新路径（见图1）。

图1 Cross1邻域结构示意图

（2）Cross2：此交叉操作与Cross1类似，不同之处在于路径r1的第一部分与r2的第一部分结合形成新的路径，同理r1、r2的剩余两个部分结合成另一条新路径，其中r1节点的顺序不变，r2节点的顺序要进行逆转（见图2）。

图2 Cross2邻域结构示意

（3）Shift（0，n）：在r1中任选一点或两点插入到r2中，即n取1或2。

（4）Exchange(m,n)：在r1、r2中分别选取连续的m、n个节点，将r1中的m个节点和r2的n个节点进行交换，在本文中，m取1或2，n取1。

（5）采用的路径内邻域结构如下，设解s中任选一条路径r。

（6）Swap：在r中交换任意两点的位置。

（7）插入：在r中任选一点或两点插入到路径中另外位置。

（8）2-opt：在r中任选两点，将两点间的节点顺序逆转。

3.4.3 适应性选择邻域策略

本文采用适应性选择策略[32]来选择路径间某一邻域结构进行搜索。与随机选择某一邻域进行变化相比，可以使搜索过较好解的邻域结构有更大机会被选中，减少搜索的盲目性，其内容如下。

起初，每个路径间邻域结构的权重赋予为1，扰动次数每隔50代进行更新权重，并重置使用次数和所得分数。根据如下公式进行更新[32]：

σj,t计算准则：在同一周期中，经过路径间邻域结构变化后，若其适应度值优于历史搜索到的最优解Gbest，则此邻域结构加30分，并设noimp_times为0，同时更新Gbest和gbest；若其所得解未进一步改善Gbest，但却优于Gbest+Gbest×δ，δ为偏差系数，δ∈(0,1)，则加10分，并累加noimp_times，Gbest不变，但更新gbest，起到扰动PSO的作用；如果均不满足上述两种情况，而是获得了满足约束解，则加6分，并替换种群中最差的粒子；否则分数不变。在本文所提算法中，δ取0.1。

3.4.4扰动搜索过程

本文设计的算法主要由路径间VND和路径内VND组成，为了方便描述分别表示为inter-VND、intra-VND。扰动部分其过程如下。

扰动搜索步骤如下：

步骤1输入初始解s，定义一组路径间邻域结构Nm，其中m=1,2,…,mmax，路径内邻域结构Nn，其中n=1,2,…,nmax。

步骤2 Shaking：根据3.4.3小节中的策略选择邻域为N，在该邻域多次循环，获得其中的最小解即s1←N(s)，与 f()s进行比较，若优则进行替换s。

步骤3 inter-VND其过程的伪代码如下[9]：

1.m←1；

2.whilem＜mmax

3.inter←1；

4.whileinter＜mmax

5.s2←Nm(s)；/找到在邻域Nm中的最好解/

6.if f(s2)＜f(s1)

7.s1←s2；

8.m←1；

9.else

10.m←m+1；

11.end

12.inter←inter+1；

13.end

14.end

步骤4 intra-VND。路径内的邻域变化与上述步骤相同，其中不同的是输入的初始解为s1，采用的是路径内邻域变化结构，以及所包含邻域的个数为nmax。

步骤5根据3.4.3小节进行选择邻域，结束扰动。

值得注意的是，搜寻解s在某种邻域结构的局优时，较易忽略循环的设定次数[9]。所以为了更好地提高搜索效率，本文在此过程（即在上述步骤5）中加入自适应性循环次数变化，可以根据在该种邻域结构搜索到解的质量来调整循环次数。

假设当前邻域结构为N，输入的初始解为s，初设循环次数 pmax，首先在该邻域随机获得一个扰动解s′，由于邻域变化本身带有随机性，所以在搜索过程中，获得的邻域解的质量有所不同，其质量的优劣决定了在当前邻域搜索的次数多少。如果搜索到解s″优于当前s′，则代替当前解，在此基础上若满足设定的条件，则增加循环次数 pmax+1。如果不优于解s′，则累计循环计数器 p，若在此基础上不满足设定的条件，则减少循环次数 pmax-1，其中设定的条件为满足约束。同时，为了进一步控制循环的进程，计算在同一邻域中搜索到可行或不可行解连续出现的次数，若不小于ε，则变化循环次数。根据先前的实验，ε设为3。主要步骤如下：

1.s'←N(s);p←1;mm=0；

2.while p＜pmax

3.s''←N(s)；

4.iff(s'')＜f(s')

5.s'←s''；

6.ifs'满足条件 /可以设定为满足可行约束/

7.pmax←pmax+1；

8.mm←0；

9.end

10.else

11.p←p+1

12.ifs'不满足设定的条件

13.mm=mm+1；

14.ifmm＞=ε]

15.pmax←pmax-1；

16.end

17.end

18.end

19.end

3.5 适应性权重

在PSO部分，本文采用如下适应权重，其更新公式如下，设权重最小值wmin，最大值为wmax，第i个粒子的适应值为 fi，种群最小值为 fmin，平均值为 favg，对于粒子i的权重值计算如下：

3.6 算法求解过程

算法求解过程如下，其流程图见图3。

图3 混合粒子群算法流程图

步骤1采用上述3.3节方法产生初始粒子的位置和速度，计算适应度值并初始化种群的个体 pbest和种群的gbest、Gbest，以及最大迭代次数、加速因子等相关参数。

步骤2计算粒子的适应性权重（公式（17）），并根据公式（13）和（14）更新粒子位置和速度，计算适应值。

步骤3若优于粒子个体最优适应值 pbest或种群最优适应值gbest，则相应地更新 pbest或gbest。

步骤4种群所有粒子全部更新完以后，若gbest优于历史最优Gbest，则更新Gbest，设noimp_times为0，否则累加未改进的次数。

步骤5判断是否满足扰动准则，是则依3.4.4小节方法进行扰动搜索，进行下一步，否则转至步骤8。

步骤6对扰动后的解依3.4.3小节进行评分并记录邻域使用次数，以及相应地进行更新。

步骤7判断是否达到下一评分周期，若达到则更新权重，并重置分数和使用次数。

步骤8若迭代次数达到最大允许迭代次数且未改进次数达到终止的最大次数，则终止算法，否则返回步骤2。

4 算例验证与结果分析

为了验证所提算法的可行性和有效性，本文进行了3组实验。第1、2组实验分别选取了文献[13]和文献[21]中的算例进行硬时间窗问题的测试，第3组实验选取文献[20]中求解带软时间窗VRPSPD问题的算例测试。本文所设计算法在Matlab 2015a平台上编译，并在PC机上运行实验（测试环境CPU：双核奔腾2.80 GHz；内存：2 GB；操作系统：Windows 7）。

实验1实验选取由Wang和Chen[13]生成求解VRPSPDTW的算例，分别与遗传算法[13]、模拟退火[15]、平行模拟退火[16]以及全局人工鱼群算法[17]进行比较。

在这组实验中不同规模算例所取参数如下：W_min和W_max分别表示惯性权重的最大、最小值，Popsize表示种群规模，Itermax表示最大迭代次数（见表1）。加速因子c1=c2=1.496 18，在扰动部分中，Shaking阶段在同一邻域循环次数为3倍的Popsize，pmax在路径间、路径内分别设为2倍的Popsize、Popsize。值得注意的是，50个客户规模的算例中，为了充分地进行扰动，shaking阶段采用的邻域有所不同，采用的是doublereplace（1，1），triple shift（1，0），triple swap（1，1），double cross[30]以及exchange（m，n）（其中 m 和 n 的组合为（3，2）、（3，1）和（2，2））。

表1 不同规模算例所用参数

表2列出了本文所提算法运行10次获得的最好解，并与其他算法在总运输距离的比较。其中将Wang和Chen[13]采用GA计算的结果作为标准1，其他算法的结果进行“标准化”，即第二至五列均为与GA的比值，最后一列给出了所提算法计算得到的结果，最后一行列出了各算例的比值平均值。由表2可知，除算例Rcdp5004外，其他算例均能找到当前已知最好解或更优解，从比值的平均值来看，本文所提算法为0.937 5，分别与SAA[15]、p-SA[16]、IGAFSA[17]相比都较小，其中 Rcdp1007改进最大。在9个算例中，更新了6个算例的最好解。在求解50个客户规模的算例运行时间均在820 s以内获得，虽然运行时间较长（采用了多邻域循环所致），但是仍在可以接受的范围之内。综上，可以验证所提算法的可行性和有效性。

表2 各算法运行结果比较

Rcdp1001轨迹图如图4；Rcdp2504轨迹图如图5。

图4 Rcdp1001轨迹图

图5 Rcdp2504轨迹图

实验2根据文献[21]扩展的Solomon[14]算例的方法，生成配送和取货需求，在RC类算例中形成客户规模分别为10、25和50共9个算例。该组实验采用的相关参数与实验1相同。表3为本文算法与文献[21]运行结果的比较，从表中的结果可以得到，本文算法的节省车辆数（NV）和总行驶距离（TD）结果都优于离散粒子群算法DPSO[21]（Discrete Particle Swarm Optimization），在算例RCdp25107的比较结果可知，虽然所用车辆数比DPSO多1辆，但是总行驶距离改进了29.83%。在各算例运行时间均在475 s之内，虽然相比较而言，耗时较长，但仍在可接受范围内。综上表明，本文算法优势明显，同时也说明不同结合方式很大程度上影响着算法的性能。

表3 与离散粒子群算法结果比较

实验3本文根据文献[20]中，包含1个物流中心和20个客户点的算例，用来求解带有软时间窗的VRPSPD问题，通过计算总需求量与车辆载重的比值可知，最少需要车辆数为3，为了保证产生的粒子的多样性且有效地减少搜索的盲目性，本文设定车辆数为4。该实验所选用的参数与实验1中25个客户规模的算例相同，在模型中的参数与文献[20]中相同。

表4列出的是加入适应性权重的基本PSO（用BPSO表示）、SA[20]和本文所提算法运行10次的结果，从中可以看出本文算法在10次运行中均能找到较高质量的解。从表中得知，与BPSO相比，在平均值、最好值和最差值上分别改进了12.84% 、17.91%、14.69%，说明在PSO的基础上，所提算法可以有效地跳出局部最优；与文献[20]的SA比较，分别改进了5.08%、12.95%、4.05%。本文算法所获的最好解其总配送成本为175.2元，总运输距离为113.1 km，所用总的车辆数为3，与前两个算法所用车辆数均少1。具体的配送路线为：第1辆车：0-14-13-5-4-19-6-12-0；第2辆车：0-8-9-18-10-11-3-15-0；第3辆车：0-7-20-1-17-16-2-0。算法在10次运行的平均耗时为160.9 s，虽然算法耗时较多，但仍在可接受的范围内。

表4 各算法运行结果比较

如图6为本文算法运行最好结果（即第10次实验）总配送成本和运输成本的迭代变化图；如图7是其中扰动种群全局极值的变化图。从两者比较来看，在1 000代左右以及1 600代到1 900代这两个阶段的扰动，均能有效地引导算法跳出局优；在2 000代以后算法最终收敛。

图6 迭代变化图

图7 扰动图

综上，扰动部分可以更进一步优化PSO的搜索进程，起到改进的作用，同时也验证了算法的可行性和有效性。

5 结论语

本文针对更贴近现实物流配送网络的带软时间窗VRPSPD问题，建立了以车辆派遣成本、行驶成本和时间窗惩罚成本之和最小为目标的车辆路径优化模型，设计了混合PSO算法进行求解。为了克服PSO容易陷入局部最优，爬山能力弱等问题，在Gbest未改进次数达到线性扰动启动准则计算的值时，启动适应性扰动机制，即进行VND扰动，其中在Shaking阶段采取了适应性选择邻域策略，并在每个邻域搜索中应用可变的循环次数，以便提高对解空间的探测能力和搜索效率。

通过与现有算法求解结果比较，本文所设计的混合PSO能够有效地求解该问题，同时也表明了扰动机制可以很好地跳出局部最优，并在可接受的时间范围内获得满意解，验证了算法的有效性。今后，将针对不同算法之间的结合方式，以及求解更一般化的车辆路径问题进行进一步研究。