带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法

周　蓉　沈维蕾　刘明周　赵　韩

合肥工业大学，合肥，230009

带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法

周蓉沈维蕾刘明周赵韩

合肥工业大学，合肥，230009

摘要：为了同时实现总配送成本最低、车辆数最少和车辆行驶距离最短等目标，考虑车辆指派成本及运输路径成本的相对重要性，建立了带时间窗装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性，提出了一种混合离散粒子群求解算法。算法基于客户排列的直观无分段大路径解表示法，采用改进深度优先搜索分割法对问题解进行解码与评价；嵌入一种变邻域下降搜索程序并在个体粒子每次迭代时以一定概率选择执行，利用混合粒子群算法在多邻域深度搜索和在全局空间广度搜索进行寻优，同时应用模拟退火思想和比例选择性变异最差个体来改善个体搜索停滞现象。采用两个不同目标算例进行寻优测试，验证了所提算法的可行性和有效性。

关键词：带时间窗车辆路径问题；装卸一体化；离散粒子群优化算法；变邻域下降搜索

0引言

车辆在完成客户配送或取货过程中普遍存在回程或去程空载现象，如何有效整合正向和逆向物流，减少运输资源浪费，降低物流运作成本，是逆向物流系统规划中的重要决策问题。当客户同时具有送货和取货需求时存在两种车辆服务策略，一种策略是车辆将货物送至客户的同时从该处取走货物，车辆装卸操作同时完成；另一种策略是车辆完成所有送货需求后按原路径返回完成取货需求，车辆装卸操作分时完成。这两种策略问题分别称为装卸一体化车辆路径问题和带回程车辆路径问题[1-2]。如果带回程问题去程的取货量或回程的送货量为零，则问题转变为装卸一体化车辆路径问题。文献[2]的研究结果表明，装卸一体化车辆路径问题较带回程车辆路径问题具有更低的运作成本。装卸一体化车辆路径问题最早由Min[3]提出，用于解决1个中心图书馆与22个乡村图书馆之间的图书发送与回馆问题。有关该问题的研究文献比较多，但因其是NP-Hard问题，求解方法大多集中在启发式方法和元启发方法。启发式方法主要以经典C-W节约算法为基础，考虑不同的启发式规则进行求解[4-6]；元启发方法以群体智能为基础，考虑不同的信息传递与更新方式进行求解[7-8]。现实中客户对送货与取货通常有一定的时间要求，即要求车辆在指定的时间范围内完成装卸操作，这就是带时间窗装卸一体化车辆路径问题(vehicleroutingproblemwithtimewindowsandsimultaneouspickupanddelivery，VRPTWSPD)。该问题较装卸一体化车辆路径问题更能反映实际情况，因而具有更为广阔的应用前景，但由于决策目标、决策影响因素和约束条件较多造成求解困难，目前相关研究还比较少。

现有VRPTWSPD相关研究多以最小化车辆行驶距离为目标，虽然少数研究增加了车辆数目方面的分析，但缺乏对总配送成本、车辆数目、车辆行驶距离等多种目标的系统性分析。如：Angelelli等[9]以最小化车辆行驶距离为目标，采用分支定界算法解决了20个客户的小规模VRPTWSPD问题；Lai等[10]运用改进的差分进化算法求解了相同目标问题，并分别采用由8个客户和40个客户组成的两个不同规模算例进行了算法准确性和有效性验证；Wang等[11]以最小化车辆数目、最小化车辆行驶距离为目标，提出采用联合进化遗传算法进行求解，并将Solomon的经典VRPTW(vehicleroutingproblemwithtimewindows)问题集扩展为65个10～100个客户规模的VRPTWSPD算例，计算结果证明该方法较基本遗传算法和数学规划工具Cplex具有更好的稳定性。此外，王超等[12]还采用改进的模拟退火算法，以文献[11]扩展的部分VRPTWSPD问题为测试算例，证明了该方法在部分算例中较文献[11]的联合进化算法求解性能更好；Boubahri等[13]以最大化站点服务能力为目标，提出采用多蚁群算法对多校车站点的VRPTWSPD问题进行求解，但未进行算法验证。

粒子群优化(particleswarmoptimization，PSO)算法是一种基于群体智能的自适应元启发算法，在许多车辆路径与调度问题的求解应用中已被证明具有良好的优化性能[7,14-15]。PSO算法在搜索处理后期阶段容易出现早熟收敛从而陷入局部最优，因此通常与局域搜索相结合，利用其拓展局域深度搜索的特点提高整体搜索性能[7,15]。受到该思想的启发，本文将变邻域下降搜索程序嵌入基本离散粒子群算法，提出一种混合离散粒子群算法求解包含多种目标的VRPTWSPD问题，并通过算例仿真和结果对比验证了所提出算法的可行性和有效性。

1问题描述与模型

VRPTWSPD问题可以描述为：物流中心拥有一定数量的相同车辆，车辆从配送中心出发，在一定时间内完成确定数量客户集的送货与取货后返回物流中心。每个客户的送货与取货由同一车辆同时完成。每个客户具有确定的位置及独立的服务时间窗，每辆车在指定的时间范围离开和返回物流中心。要求合理安排车辆配送路线，在派出车辆数目最小、车辆行驶距离最短情况下，实现总配送成本最小。采用符号体系描述如下：假设物流中心共有N个客户，采用i、j表示客户编号(i = 1, 2, …, N; j = 1, 2, …,N), 0表示物流中心；Z为总配送成本；客户的送货量和取货量分别为di、pi；客户之间的距离为cij，物流中心到客户i的距离为c0i；车辆单位距离行驶成本为g，单车指派成本为f，最大装载量为Q；车辆总数为K，车辆k(k = 1, 2, …, K)到达客户i的时间为Tik，在节点i的等待时间为tik，在i、j两个节点之间的行驶时间为tijk，离开客户i时车上载重量为Uik，离开和返回物流中心的时间分别为L0k、R0k(也可以由车辆的最大行驶距离L进行限制)；客户i要求的服务时间窗为[ai,bi]，服务时间为si；物流中心0对车辆的时间窗要求为[a0,b0]；m、n分别为车辆指派成本、运输路径成本对总配送成本的重要性指数，m∈[0,1)，n∈(0,1]。

根据上述描述，建立VRPTWSPD问题的混合整数规划模型如下：

(1)

满足约束条件：

(2)

(3)

∀j=1,2,…,N

(4)

∀i=0，1,…,N;k=1,2,…,K

(5)

(6)

(7)

∀i=1,2,…,N;j=0,1,…,N

(8)

tik=max(ai-Tik,0)

∀i=1,2,…,N;k=1,2,…,K

(9)

ai≤Tik+tik≤bi

∀i=1,2,…,N;k=1,2,…,K

(10)

a0≤L0k∀k=1,2,…,K

(11)

R0k≤b0∀k=1,2,…,K

(12)

(13)

(14)

∀i,j=0,1,…,N;k=1,2,…,K

其中，式(1)为考虑了车辆指派成本、运输路径成本的总配送成本Z最小目标，隐含车辆数目最小、车辆行驶距离最短两个子目标；式(2)确保每个客户只被服务一次且仅由一辆车服务；式(3)确保使用车辆数不超过车辆总数K；式(4)为流量守恒式，即到达和离开每个客户的车辆相同；式(5)～式(7)为容量约束；式(8)～式(10)为客户的时间窗约束，其中式(8)中的M为一个很大的正数；式(11)～式(12)为物流中心的时间窗约束；式(13)确保车辆的最大行驶距离不超过L；式(14)为决策变量属性约束。调整m和n的值，可以使式(1)目标发生改变。如令m = 0、n = 1，模型目标为行驶距离最小化，与文献[10]相同；令n = 1- m，模型目标为配送成本最小化，与文献[11]相同。

2算法设计

2.1离散粒子群算法基本原理

离散粒子群算法通过重新定义粒子操作算子[16]，用问题的一个排列作为粒子的一个位置，用问题的所有排列构成问题的搜索空间，并通过遗传、变异和交叉操作，综合粒子的当前状态、个体思考及社会合作三部分信息实现粒子位置更新，其位置更新公式为[15]

(15)

2.2混合离散粒子群算法

本文将变邻域下降搜索引入离散粒子群算法作为个体粒子的一种概率变异，通过扩大局域搜索空间实现个体深度搜索，从而提高群体寻优能力。

2.2.1解的表示、解码与评价

(1)解的表示。产生N个1 ～ N之间的互不重复自然数的排列，作为具有N个客户的带时间窗装卸一体化车辆路径问题的抽象解。该抽象解是一条以自然数序列表示客户服务顺序的无分段大路径[17]，对于单车场车辆路径问题通常在序列最前面加上0表示带物流中心的大路径。大路径解图示方法包括直观图和有向无圈图，直观图给出物流中心及所有客户的地理位置、客户的送货与取货需求量、客户及物流中心的服务时间窗等信息，如图1a所示(图中N = 5)；有向无圈图给出客户之间满足约束条件的所有可行配送路径的相关信息，如图1b所示。

有向无圈图(图1b)中弧(i,j)为大路径X={0,1,…,N}上第i个节点与第j个节点之间的可行配送路径，表示车辆从物流中心出发依次服务第i +1、i +2、…、j -1、j个节点后返回物流中心。可行配送路径满足车容量、客户及物流中心时间窗、车辆最大行驶距离等相关约束。设弧(i,j)上车辆的行驶距离为Dij，总配送成本为zij，其计算式如下：

(16)

zij=mDX(i+1,j)g+nf

(17)

(2)解码。大路径解码也称为大路径分割，通过采用标签管理方式对各节点进行标记，然后根据标记信息将大路径上的客户分别划入不同的车辆配送路径中，从而得到各车的配送方案(也称作子路径)。大路径分割思想最先由Beasley[18]提出并应用于求解车辆路径问题的先路径后丛聚启发式算法中，后被Prins[17]拓展用于求解VRP问题的遗传算法中。Duhamel等[19]将大路径分割方法分为广度优先搜索和深度优先搜索两种，其中深度优先搜索以其搜索速度快被广泛用于VRP问题的元启发方法中[17,19-20]。

根据VRPTWSPD问题的客户双重需求特性以及相关约束条件，包括车辆的最大载重量约束、客户要求服务的时间窗约束，对文献[20]的深度优先搜索方法进行修改，使其适用于VRPTWSPD问题的大路径分割。该方法分为两阶段：第一阶段构造有向无圈图并给每个节点创建成本和距离标签，确定每个节点上成本标签的最小值，推断各节点的前继节点。第二个阶段根据最后一个节点的前继节点信息，逐个向前提取各节点的标签信息，根据最小化总配送成本目标产生最优路径方案。

对大路径X={0,1,…,N}，若(i,j)为其有向无圈图G(X)上的一段可行弧，Pi、Vi和Di分别为节点i的前继节点标签、总配送成本标签与总行驶距离标签，Pj、Vj和Dj分别为节点j的前继节点标签、总配送成本标签与总行驶距离标签，则存在以下关系式：Pj=i，Vj=Vi+zij,Dj=Di+DX(i+1,j)。以图1为例，设车辆最大装载量Q=12，单车指派成本f=10，车辆单位距离行驶成本g=1,车辆行驶速度v=2,车辆在每个节点的服务时间s=10,大路径X={0,1,2,3,4,5};弧(0,2)表示路径0-1-2-0，节点2的前继节点标签P2=0，假设m =n= 1，节点2的总配送成本标签V2=V0+z02=0+65=65，节点2的总行驶距离标签D2=D0+DX(1,2)=0+55=55；弧(2,4)表示路径0-3-4-0,节点4的前继节点标签P4=2，节点4的总配送成本标签V4=V2+z24=65+105=170，节点4的总行驶距离标签D4=D2+95=55+95=150。根据图1b中的黑色加粗弧可知，当V5=V3+z35=100+100=200时，大路径X的最优分割为0-1-2-3-0、0-4-5-0，从而得到最优配送方案如图1c所示。

(a)直观图

(A,B):C[D,E]A:路径上的总配送装载量; B:路径上的总集货装载量;C:路径上的总成本; D:车辆离开物流中心的时间;E:车辆返回物流中心的时间(b)有向无圈图

(c)最优方案图 1　大路径示例及解码图

(3) 解的评价。一般情况下，对目标函数值进行比较可以评价可行解的优劣程度。因此本文选取目标函数值Z作为解的评价值。

2.2.2种群初始化

由于初始解质量对粒子群算法求解的速度和质量影响较大，本文采用大部分初始种群个体随机生成、部分优良个体采用改进节约法[21]生成得到初始种群。随机产生方法遵循以下两条原则：第一，不允许产生相同的路径，若随机产生的路径与已存在的初始种群中的粒子完全相同，则在一定代数内重新产生直至不相同为止；第二，随机产生的路径与已产生粒子的目标值之差应不小于某一数值Δ(通常Δ=2[17])。

改进节约法是在Clark和Wright的经典C-W节约法基础上，综合考虑车辆总行驶距离、时间窗、同时取送货以及车辆容量限制等约束因素，重新定义节约值的算法。改进的节约值计算公式为[21]

(18)

(1)建立一条只包含物流中心0的大路径X。

(2)将所有客户按时间窗下限进行升序排列，命名为剩余客户群。

(3)取出第一个客户(即具有最小时间下限的客户)作为当前客户，将当前客户插入大路径X；同时将当前客户从剩余客户群中去除，得到新的剩余客户群。

(4)按式(18)计算当前客户与所有剩余客户的新节约值，选取与当前客户具有最大新节约值的客户插入X；更新剩余客户群，如果剩余客户群不为空，转步骤(3)，否则输出大路径X。

2.2.3位置更新准则

本文采用离散PSO策略实现个体粒子的位置更新。每次迭代时随机生成变异概率u1、个体交叉概率u2和全局交叉概率u3。根据式(15)，当u1≤w时进行自身变异操作，否则不变异；当u2≤c1时与个体极值进行交叉操作，否则不交叉；当u3≤c2时与全局极值进行交叉操作，否则不交叉。

变异操作采用两点插入式变异。任意选择待变异粒子中的两个位置(第一个位置除外)，将粒子中所选两个位置之间的所有元素按原顺序取出，作为变异粒子的前段，然后依次按原顺序插入第一个位置前的所有元素、所选择两个位置上的元素、第二个位置之后的所有元素，便得到变异后的粒子序列。具体变异过程如图2所示。

交叉操作采用PTL两点交叉[15]。由于个体粒子可能与个体极值或全局极值的位置相同，PTL两点交叉可以使相同序列交叉后得到不同的新序列。以个体粒子与个体极值交叉为例，PTL两点交叉步骤为：任意选择待交叉个体粒子中的两个元素(第一个元素除外)，交叉时首先将个体极值中的对应两个元素按原顺序取出，作为交叉粒子的前段，然后从个体极值中依次选择其他元素放置在其后，形成新的交叉粒子。具体交叉过程如图3所示。

图 2　粒子变异操作

图 3　粒子交叉操作

2.2.4局域搜索

本文以车辆路径问题中常用的六种邻域机制为基础，设计一种变邻域下降搜索程序作为局域搜索方法，用于位置更新后个体粒子的深度搜索，寻求以较快的速度在更大搜索空间内优化个体搜索质量，并据此作为个体极值及全局极值的选择依据。这六种邻域机制为：

(1)路径间部分交叉。对任意两条子路径，选择不同的位置将每条子路径分为前后两部分，将后面两部分进行交换得到两条新的子路径。对所有子路径、所有可行的位置进行分段交叉，选择令总配送成本最小的交叉结果作为新的个体。

(2)路径间两点交换。分别选择两条子路径上的一个元素，从原路径上删除后，插入到另一条子路径中。插入前，首先确定距离当前待插入元素最近的k个客户，判断另一条子路径中是否至少存在k个客户中的一个客户，如果存在则选择插入后新路径总配送成本最小的位置，否则不插入。

(3)路径间单点转移。对任意两条子路径，选择一条路径上的一个元素并删除后，将其插入到另一条子路径中。对所有插入位置，选择令插入后新路径总成本最小的位置。

(4)路径内部分逆转，即为2-OPT操作。对任意一条子路径选择两个位置，通过对两个位置之间部分执行逆转产生新的子路径。对所有可行的位置对，选择令操作后新路径总成本最小的位置对。

(5)路径内两点交换。对任意一条子路径选择两个位置并相互交换形成新的子路径。对所有可行的位置对，选择令操作后新路径总成本最小的位置对。

(6)路径逆转。对任意一条子路径，将原序列从后向前颠倒顺序。该操作并不影响总的送货量与总的取货量，但可能降低车辆在不同客户点的最大装载量使其满足车容量，或者改变车辆到达客户的时间使其满足客户时间窗要求，从而为后续迭代过程中的新客户插入提供机会。

上述邻域机制中，前三种为路径间操作，后三种为路径内操作。由于路径间操作使得个体变异幅度较大，路径内操作的变异幅度较小，因此本文以有效变异为前提设计一种变邻域下降搜索程序，基本搜索思想为：首先按上述邻域机制顺序执行邻域搜索，如果搜索得到更好的目标值，则对该邻域进行路径内深度搜索，否则继续按上述顺序进行下一个邻域机制搜索。详细搜索步骤如下：

(1)设定搜索对象。设定搜索对象为大路径X及其配送路径集合R。

(2)按上述六种顺序初始化邻域机制编号，初始令o=1。

(3)对集合R，设当前域为h，如果o≤6，采用第o个邻域机制寻找到当前域h的最好邻域h′,转步骤(4)；否则，转步骤(5)。

(4)如果寻找到的邻域目标值比当前目标值低，即f(h′)

(5)输出新的配送路径集合R和大路径X。

由于客户变动会影响车辆在路径不同节点的最大装载量及到达时间的变化，从而使得新路径成为不可行路径，因此每一次邻域操作时都必须对路径进行可行性检查，即对各客户点的最大装载量及客户时间窗、车辆返回物流中心的时间窗进行可行性判断。为保障邻域搜索的有效性，只有满足可行性检查的邻域操作及相应更新才被接受。

2.2.5粒子“极值”更新方法

随着迭代次数的增加，种群多样性快速下降使得粒子过早收敛而陷入局部极值。解决该问题的常用办法是采用模拟退火思想概率接受劣解，或者引入变异机制对停滞粒子进行变异。对粒子个体极值采用模拟退火思想接受劣解，接受准则为：计算粒子迭代后和迭代前解的变化量ΔE，若ΔE≤0，接受新值；若exp(-ΔE/T)>rand(0,1)，也接受新值；否则拒绝。其中，T表示退火温度，rand(0,1)为0 ～ 1之间的随机数。

若全局极值在若干代内未改进，则认为种群陷入局部最优位置。全局极值更新方法为：以一定比例选取种群中目标值最低的粒子进行两点换位变异操作，若变异后粒子目标值小于全局极值，则更新全局极值，否则不更新。

2.2.6算法步骤

混合离散粒子群算法的具体步骤如下：

(1)初始化种群参数S、变异概率w、交叉概率c1和c2、局域搜索概率pL、最大迭代次数Imax、全局极值连续未更新最大次数Mg。

(3)判断是否满足终止条件。如果Ng>Mg且t>Imax则满足终止条件，转步骤(5);否则不满足终止条件，转步骤(4)。

(5)输出全局极值粒子Xg、全局极值Cg以及最优配送方案。

3实验结果与比较

为验证算法寻优性能，选取2个算例进行寻优测试。算法采用MATLABR2009b编程语言实现。微机运行环境为：CPUi5-2520，主频 2.5GHz，内存4G。

3.1算例选取及实验参数设置

选取文献[10]的算例2作为本文的算例1，用于验证模型(1)中m= 0，n = 1的情况。该算例按一定规律生成客户规模为40的VRPTWSPD问题相关数据，以车辆最大行驶距离作为物流中心的限制条件，要求有效安排行车路线使得车辆总行驶距离最短。

文献[11]的VRPTWSPD算例基于Solomon经典的带时间窗VRP算例集，但未给出客户送货量与取货量的取值方法，故无法直接作为参考算例。RC1问题的客户部分丛聚部分分散、客户时间窗较窄，车辆行程较短、需求的车辆数量较多，是Solomon算例集中最复杂的一种情况。因此，本文分别选择算例RC101、RC104、RC107的前10、25和50个客户的基础数据，产生9组新的VRPTWSPD算例集作为本文的算例2；9组新算例依次命名为RCdp10101、RCdp25101、RCdp50101、RCdp10104、RCdp25104、Cdp50104、RCdp10107、RCdp25107、RCdp50107。算例中基础数据保持不变，客户送货量di及取货量pi数据按如下规则生成：设原算例中客户i需求量为Gi，客户i的坐标为(xi,yi)，令ri=min(xi/yi,yi/xi)，则di=Giri，pi=Gi(1-ri)。此外,由于总配送成本最小化目标通过使用车辆数最少和车辆行驶距离最短两个子目标实现，因此本例设车辆指派成本为一个很大的正整数，车辆单位距离行驶成本g = 1。算例2用于测试算法对模型(1)的求解精度，同时也用于分析种群初始化方法及局域搜索对算法性能的影响。

通过测试，参数设置为：种群S = 20，局域搜索概率pL=0.3，变异概率w = 0.4，交叉概率c1=c2=0.6;初始化种群参数α的取值范围为[1.5, 3.5]，β的取值范围为[0.1, 0.5]，γ的取值范围为[0.5, 1.0]，λ的取值范围为[0.5, 1.5]；粒子极值更新温度参数T=30，q = 0.98。对算例1，设置最大迭代次数Imax= 500，全局极值连续未更新最大次数Mg= 100；对算例2，设置最大迭代次数Imax= 1500，全局极值连续未更新最大次数Mg= 200。

3.2仿真结果分析

3.2.1算例1分析

表 1　算例1分析结果

3.2.2算例2分析

以本文新产生的算例2为基础数据，采用文献[11]的联合进化遗传算法(GA)以及本文算法分别进行仿真计算，9组算例的计算结果对比分析如表2所示。表中加粗字体表示计算得到的最优值。可见，GA算法在客户数为10、25的算例条件下，计算速度较快，且在RCdp25101算例中得到了好的决策结果，即使用车辆数为5、行驶距离为507.56km。本文算法在客户数为50的算例条件下，具有更好的近似最优解，如在RCdp50101及RCdp50107算例中，尽管行驶距离比GA算法大一些，但使用车辆数较之少1辆。由于车辆指派成本为一个很大的正整数，因此车辆数目的减少可以大大降低总配送成本。由此可以推论，本文算法在求解VRPTWSPD问题时具有更好的寻优能力。

表2　算例2计算结果比较

为了进一步分析种群初始化方法及局域搜索对算法性能的影响，选取RCdp25101作为对比分析对象，以迭代500次为上限，独立运算10次选取最优近似解进行分析。图4给出了采用2.2.2节的种群初始化方法(INITIAL)与采用另一种初始化种群方法(NO_INITIAL)，以任意产生I条大路径序列方式对种群进行初始化的算法收敛性对比。可见，在INITIAL情况下初始行驶距离较NO_INITIAL情况下初始行驶距离要小很多，收敛速度更快，最优行驶距离更小。这说明初始化种群方法对本文算法求解VRPTWSPD问题的性能具有较大影响，良好的种群初始化方法能促使其收敛加快并保持良好的寻优能力。

图4　INITIAL与NO_INITIAL收敛性对比

图5　LOCAL与NO_LOCAL情况下收敛性对比

图5给出了采用2.2.4节的局域搜索方法(LOCAL)与不采用局域搜索方法(NO_LOCAL)时的对比情况。由图5可见，在LOCAL情况下粒子收敛速度较快，迭代次数少且最小行驶距离更短。这说明本文提出的局域搜索在粒子群算法求解VRPTWSPD问题时，能大大减少迭代次数，缩短计算时间,有效避免陷入局部最优。

4结语

带时间窗装卸一体化车辆路径问题是一类应用广泛的复杂车辆路径问题，因其决策目标、决策因素和限制条件较多等特征需要高求解性能的启发式方法或元启发算法。针对带时间窗装卸一体化车辆路径问题，建立了隐含两个子目标的混合整数规划模型，提出了求解带时间窗装卸一体化车辆路径问题的混合离散粒子群算法。该算法采用基于C-W的改进启发式方法产生初始种群，在一定概率下对粒子进行局域搜索，并采用模拟退火思想接受粒子个体极值劣解。针对不同总目标，分别基于两个算例进行仿真分析。仿真结果表明，无论是单纯以总行驶距离为目标的算例1问题，还是以总配送成本为总目标、以车辆数最少和总行驶距离最短为子目标的算例2问题，本文提出的混合离散粒子群算法都能以较快的收敛速度找到近似最优解，且寻优性能好于已有的改进差分进化算法和联合进化遗传算法。由此可见，本文所提算法对于具有不同时间约束服务的物流配送和取货优化问题具有重要的指导意义，同时对于离散型组合优化问题的进一步研究也具有一定的理论参考价值。

参考文献：

[1]BerbegliaG,CordeauJF,GribkovskaiaI,etal.StaticPickupandDeliveryProblems:aClassificationSchemeandSurvey[J].TOP,2007,15(1):1-31.

[2]郎茂祥. 物流配送车辆调度问题的模型和算法研究[D]. 北京：北方交通大学, 2002.

[3]MinH.TheMultipleVehicleRoutingProblemwithSimultaneousDeliveryandPick-upPoints[J].TransportationResearchPartAGeneral, 1989, 23(5): 377-386.

[4]DethloffJ.VehicleRoutingandReverseLogistics:theVehicleRoutingProblemwithSimultaneousDeliveryandPick-up[J].OrSpectrum, 2001, 23(1): 79-96.

[5]BianchessiN,RighiniG.HeuristicAlgorithmsfortheVehicleRoutingProblemwithSimultaneousPick-upandDelivery[J].Computers&OperationsResearch,2007,34:578-594.

[6]李雪, 聂兰顺, 齐文艳,等. 基于近似动态规划的动态车辆调度算法[J].中国机械工程,2015,26(5):682-688.

LiXue,NieLanshun,QiWenyan,etal.AnAlgorithmofDynamicVehicleSchedulingProblemBasedonApproximateDynamicProgramming[J].ChinaMechanicalEngineering, 2015, 26(5):682-688.

[7]AiTJ,KachitvichyanukulV.AParticleSwarmOptimizationfortheVehicleRoutingProblemwithSimultaneousPickupandDelivery[J].Computers&OperationsResearch,2009,36:1693-1702.

[8]GajpalY,AbadP.AnAntColonySystem(ACS)forVehicleRoutingProblemwithSimultaneousDeliveryandPickup[J].Computers&OperationsResearch, 2009,36:3215- 3223.

[9]AngelelliE,MansiniR.ABranch-and-priceAlgorithmforaSimultaneousPick-upandDeliveryProblem[C]//LectureNotesinEconomicsandMathematicalSystems.USA:Springer, 2002: 249-267.

[10]LaiMingyong,CaoErbao.AnImprovedDifferentialEvolutionAlgorithmforVehicleRoutingProblemwithSimultaneousPickupsandDeliveriesandTimeWindows[J].EngineeringApplicationsofArtificialIntelligence, 2010, 23:188-195.

[11]WangHF,ChenYY.AGeneticAlgorithmfortheSimultaneousDeliveryandPickupProblemswithTimeWindow[J].Computers&IndustrialEngineering, 2012, 62: 84-95.

[12]王超, 穆东. 基于模拟退火算法求解VRPSPDTW问题[J]. 系统仿真学报, 2014,11(6):2618-2623.

WangChao,MuDong.SolvingVRPSPDTWProblemUsingSimulatedAnnealingAlgorithm[J].JournalofSystemSimulation, 2014, 11(6):2618-2623.

[13]BoubahriL,AddoucheSA,MhamediAE.Multi-antColoniesAlgorithmsfortheVRPSPDTW[C]// 2011InternationalConferenceonCommunications,ComputingandControlApplications(CCCA).NewYork:IEEE,2011: 1-6.[14]邱晗光, 张旭梅. 基于改进粒子群算法的开放式定位-运输路线问题研究[J]. 中国机械工程, 2006, 17(22): 2359-2361.

QiuHanguang,ZhangXumei.ResearchonOpenLocationRoutingProblemBasedonImprovedParticleSwarmOptimizationAlgorithm[J].ChinaMechanicalEngineering, 2006, 17(22): 2359-2361.

[15]PanQK,TasgetirenMF,LiangYC.ADiscreteParticleSwarmOptimizationAlgorithmfortheNo-waitFlowshopSchedulingProblem[J].Computers&OperationsResearch, 2008, 35: 2807-2839.

[16]郭文忠, 陈国龙, 陈振. 离散粒子群优化算法综述[J]. 福州大学学报(自然科学版), 2011, 39(5): 631-638.

GuoWenzhong，ChenGuolong，ChenZhen.SurveyonDiscreteParticleSwarmOptimizationalgorithm[J].JournalofFuzhouUniversity(NaturalScienceEdition), 2011, 39(5): 631-638.

[17]PrinsC.ASimpleandEffectiveEvolutionaryAlgorithmfortheVehicleRoutingProblem[J].Computers&OperationsResearch, 2004, 31: 1985-2002.

[18]BeasleyJE.Route-firstCluster-secondMethodsforVehicleRouting[J].Omega, 1983, 11:403-408.

[19]DuhamelC,LacommeP,ProdhonC.AHybridEvolutionaryLocalSearchwithDepthFirstSearchSplitProcedurefortheHeterogeneousVehicleRoutingProblems[J].EngineeringApplicationsofArtificialIntelligence, 2012, 25: 345-358.

[20]DuhamelC,LacommeP,ProdhonC.EfficientFrameworksforGreedySplitandNewDepthFirstSearchSplitProceduresforRoutingProblems[J].Computers&OperationsResearch, 2011, 38: 723-739.

[21]庄英群. 应用禁忌搜索法于混合送收货之车辆途程问题[D] .台中:逢甲大学, 2003.

(编辑王艳丽)

AHybridDiscreteParticleSwarmOptimizationAlgorithmforVehicleRoutingProblemwithTimeWindowsandSimultaneousPickupandDelivery

ZhouRongShenWeileiLiuMingzhouZhaoHan

HefeiUniversityofTechnology,Hefei, 230009

Abstract：Considering the relative importance of dispatching cost of vehicles and travelling cost of routes, a mixed integer mathematical formulation of the vehicle routing problem with time windows and simultaneous pickup and delivery (VRPTWSPD) was established to make the total delivery cost, the number of vehicles and the travel cost minimize simultaneously. A hybrid discrete particle swarm optimization algorithm was proposed for solving VRPTWSPD. Solutions of algorithm were represented by an intuitive fragment-free giant tour of a permutation of all customers, and were decoded and evaluated by the revised depth first search split procedure. A variable neighborhood descent search procedure was carried out under a certain probability for individuals at each iteration, so that individuals could update with depth search in multi-neighborhood and with bread search in global exploration. The simulated annealing idea and mutating a selective portion of worst individuals were applied to improve the stagnation of the search. The feasibility and effectiveness of the proposed algorithm were verified by two instances with different goals.

Key words：vehicle routing problem with time window; simultaneous pickup and delivery; discrete particle swarm optimization; variable neighborhood descent search

收稿日期：2015-04-28

基金项目：国家自然科学基金资助项目(71071046)

中图分类号：TP3

DOI：10.3969/j.issn.1004-132X.2016.04.013

作者简介：周蓉， 女，1977年生。合肥工业大学机械与汽车工程学院讲师。主要研究方向为资源调度、物流系统优化。发表论文10余篇。沈维蕾，女，1969年生。合肥工业大学机械与汽车工程学院副教授。刘明周，男，1968年生。合肥工业大学机械与汽车工程学院教授、博士研究生导师。赵韩，男，1957年生。合肥工业大学机械与汽车工程学院教授、博士研究生导师。