带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法

符 卓，刘 文，邱 萌

(中南大学交通运输工程学院，湖南 长沙 410075)



带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法

符 卓，刘 文，邱 萌

(中南大学交通运输工程学院，湖南 长沙 410075)

需求可拆分车辆路径问题是车辆路径问题中的重要类型，又可分为需求可任意(按计量单位)拆分和需求依订单拆分两种子类型，在配送车辆路径优化等实际问题中有着广泛的应用背景。综合考虑客户需求依订单拆分和客户对于被服务时间的要求，本文针对带软时间窗的需求依订单拆分车辆路径问题及其优化算法进行研究。建立了问题的数学模型，设计了求解的禁忌搜索算法，以Solomn 标准算例为基础构造算例对算法进行测试，并将求解结果与相关文献中的结果进行比较。结果表明，算法收敛性较好，为解决该类问题提供了一种方法。

车辆路径问题；需求依订单拆分；软时间窗；禁忌搜索算法

1 引言

物流配送线路确定问题是物流配送管理中的核心问题之一，通常都归结为车辆路径问题(Vehicle Routing Problem, VRP)来研究。VRP的一般描述是：对一系列给定的客户点(送货点或取货点)，确定适当的车辆行驶路线，使车辆从车场出发，有序地对客户进行服务，并在满足一定的约束条件下(如车辆载重量、客户需求量、时间窗限制等)，使总运输成本达到最小(如使用车辆数最少、车辆行驶总距离最短等)。目前大部分有关VRP的研究工作，都是针对每个客户点的需求只能由一辆车来完成，即需求不可拆分的问题类型。

在实际的配送中，有时会允许对客户需求进行拆分，并由多辆车分别运送，以便充分利用车辆装载能力和降低车辆行驶成本。这类问题被称之为需求可拆分的车辆路径问题。1989年，Dror和Trudeau[1]首先对其最基本类型，即需求可拆分的纯送货VRP(Split Delivery Vehicle Routing Problem, SDVRP)开展研究。在已有的需求可拆分车辆路径问题研究中，都是以客户点需求可被任意拆分(即按计量单位拆分)为背景。在实际工作中，客户的一份订单中有时包含有多件货物，且是不可以拆分运送的，必须将一份订单中的货物装在同一辆车上运送，即此情形下拆分客户点需求时，不能拆分某一具体订单，只能按订单进行拆分。因此，以需求依订单拆分为应用背景进一步研究需求可拆分VRP很有必要。

此外，客户有时会对货物送达的时间区间提出要求，该时间区间通常称之为时间窗。根据该时间窗的要求是严格的，还是允许有所偏离但要支付相应的惩罚，又可相应地分为硬时间窗和软时间窗。在未特别指出时，硬时间窗通常简称为时间窗。显然，若某个客户的时间窗不能被违反(是硬的)，则也可通过将有偏离时应支付的惩罚设为无穷大来限制。由此可见，硬时间窗类型实际上是软时间类型的一种特殊情形。正如Fu Zhuo等[2]所归纳，将客户的时间窗要求按“软”的来处理有很多好处：

(1)许多实际问题并不要求将时间窗设置得非常精确。因此，时间窗实质上通常就是软的。

(2)在实际中，往往也不可能精确地确定车辆的行驶时间。

(3)将时间窗设置为软的，可以使车辆使用数和车辆的总行驶里程获得较大节省。

(4)软时间窗模型更一般化，且包含了硬时间窗的要求。因此，为求解软时间窗模型设计的算法，通过适当加大偏离时间窗时的惩罚值即可用于求解带硬时间窗的问题。

(5)在某些实例中，按硬时间窗的要求来求解时可能不存在可行解，而按软时间窗来处理时总存在可行解。例如当可调配的车辆数较少时，就有可能不存在满足所有客户硬时间窗要求的可行解，此情形下，按软时间窗来处理时总能提供可行解，只是到达某些客户点的时间有所偏离其所期望的时间窗。

(6)软时间窗模型还可以用来对车辆使用费用和满足客户时间窗要求(即服务质量)之间的背反关系进行权衡。

自从Dror和Trudeau[1]首先对需求可拆分VRP开展研究以来，已经有越来越多的学者从事该领域的研究工作。Dror等[3-5]论证了需求可拆分可提高车辆装载率，并且节省车辆总成本。Archetti等[6-7]分析了需求可拆分的VRP的计算复杂性。Jin Mingzhou等[8-11]则研究了求解需求可拆分VRP的整数规划算法。Archetti等[12-15]提出了求解需求可拆分VRP的禁忌搜索算法。国内近年也有学者开展该领域的研究工作。谢毅[16]利用禁忌搜索算法和遗传算法分别求解了需求可拆分的VRP。孟凡超等[17]用禁忌搜索算法对需求可拆分的VRP进行了求解，并对算法进行了改进。陆琳等[18-22]也从不同角度对需求可拆分VRP做了一些相关研究。

Pankratz等[23-25]将需求可拆分VRP与时间窗结合，提出了相应的启发式算法。侯立文等[26]使用最大最小蚂蚁算法求解了带时间窗的需求可拆分VRP，并通过放大Solomn标准算例检验了算法的有效性。马华伟等[27]则对带多时间窗的需求可拆分VRP进行研究，并提出一个求解的改进蚁群算法。相对而言，针对传统的需求不可拆分VRP与时间窗结合的研究成果更多一些。如李宁等[28-30]使用粒子群算法对带时间窗VRP进行了求解。汪勇[31]研究采用协同进化遗传算法对带时间窗的VRP进行了求解。潘立军等[32-33]分别提出了求解带时间窗取送货问题的遗传算法和求解带时间窗VRP的时差插入检测法。宾松等[34]和祁文祥等[35]则涉及带软时间窗的问题类型。而Fu Zhuo等[2]则将软时间窗的主要类型归纳为6种，并提出了一个可求解各种软时间窗类型的VRP的一体化禁忌搜索算法。

目前，尚未看到直接研究需求依订单拆分VRP、或带软时间窗的需求可拆分VRP的文献。但上述相关的研究成果为开展这方面的研究提供了可借鉴的理论和方法。基于上述分析，本文主要研究带软时间窗的需求依订单拆分车辆路径问题(Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order，VRPSTWSDO)及其求解算法。以纯送货情形为背景，对单车场、单车型的VRPSTWSDO特点进行描述和分析，建立相应的数学模型，提出求解的禁忌搜索算法，并构造测试算例对其进行测试运算和比较分析。

2 问题表述

VRPSTWSDO是指一组车辆从车场出发，访问其需求量和希望得到服务的时间窗已知的各客户点，在访问客户点时允许到达客户点开始服务的时间有所偏离其时间窗要求，但必须给予相应的惩罚。当客户需求大于车辆的剩余载重时，进行拆分运输，但不可以分割该客户点某一具体订单，最终达到既不超过车辆载重，又最优化载重率的效果。问题的优化目标是确定合理的运输路线，在满足车辆装载能力和行驶距离限制的前提下，最小化所使用的车辆数、车辆行驶距离(时间)和时间窗偏离量，且满足所有客户点的需求。其中，最小化车辆数为第一优化目标，最小化车辆行驶时间和时间窗偏离量为第二优化目标。

设车场编号为1，客户点编号分别为2,3,…,N；

K为所需的车辆数；

Ci为客户点i的需求量，由R个订单组成；Ci=Ci1+Ci2+…+Cir+…+CiR，Cir为客户点i的第r个订单，每个订单不可拆分，r为需求点i的订单编号，r=1,2,…,R；

w为车辆装载能力，且Ci

L为每条线路的最大长度(行驶时间)；

yki表示第k辆车为客户点i配送的货物量；

ai为客户点i时间窗的最早时间；

bi为客户点i时间窗的最晚时间；

tij为客户点i到客户点j的行驶时间；

ti为到达客户点i的时间；

tis为客户点i的服务时间；

e为提前到达客户点i并开始服务的惩罚系数；

f为延迟到达客户点i并开始服务的惩罚系数。

定义变量如下：

xijk=1，表示车辆k从客户点i行驶到客户点j；否则，xijk=0。

hkir=1，表示车辆k运输客户点i的第r个订单的货物；否则，hkir=0。

如果客户点i和客户点j在同一线路上，且服务客户点i之后马上服务客户点j，那么tj=ti+tis+tij。

模型假设：

(1)两点间的行驶时间是对称的，即tij=tji；

(2)点与点之间的行驶时间符合三角不等式，即tik+tkj>tij；

(3)所有的车辆从车场出发，完成一趟任务后，必须返回车场；

(4)每个客户点的需求必须满足，但可以由一辆及以上车辆来满足。

根据上述描述，带软时间窗的需求依订单拆分的车辆路径问题的数学模型可以描述为：

MinK

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

yki=hki1Ci1+hki2Ci2+…+hkirCir,i=2,3,…,N;k=1,2,…,K

(9)

式(1)是第一优化目标，最小化车辆使用数；式(2)是第二优化目标，最小化车辆行驶成本和时间窗偏离；式(3)为线路长度限制；式(4)为车辆装载能力限制；式(5)、(6)表示每个客户点至少被访问一次，且需求均得到满足；式(7)表示流量守恒，即进入某客户点的车辆数和离开该客户点的车辆数相等；式(8)表示当且仅当车辆经过某客户点时，该客户点才能得到服务；式(9)表示客户点i的需求可以拆分，但每个订单不可拆分。

3 禁忌搜索算法设计

Dror等[36]和Archetti等[37]用各自的方法证明了需求依订单拆分VRP是NP-Hard 问题。本文研究的VRPSTWSDO是需求依订单拆分VRP的延伸，也是NP-Hard问题。禁忌搜索算法作为一种全局性邻域搜索亚启发式算法，适用于本文所设计NP-Hard 问题模型的求解。已有研究中，Gendreau等[38]和Cordeau等[39]分别对求解VRP的一些现代启发式算法，如模拟退火、禁忌搜索、遗传算法、蚁群算法和神经网络等进行了较为全面的综述。根据他们的分析，总体来说，禁忌搜索是目前求解VRP的较为有效的方法。另外，Ho和Haugland[40]研究带硬时间窗的需求可拆分车辆路径问题，相较于本文的软时间窗约束，约束条件更严格。Fu Zhuo等[2]研究带软时间窗的需求不可拆分的车辆路径问题，相较于本文的需求可拆分，约束条件也更严格。两篇文献应用禁忌搜索算法均较好地解决了所研究的问题。所以本研究选择设计禁忌搜索算法来求解该问题。

与使用其他现代启发式算法求解优化问题一样，使用禁忌搜索算法来求解问题时需要在其基本通用框架内，结合所要求解的问题进行一些具体设计。

3.1 初始解

禁忌搜索算法对初始解有较强的依赖性，好的初始解可使禁忌搜索在解空间中搜索到好的解，而较差的初始解则会降低禁忌搜索的收敛速度。一般来讲，求解某个具体问题时，可用其他算法生成高质量的初始解，再用禁忌搜索求解，以提高搜索的质量和效率。当然也可以采用一定的策略来降低禁忌搜索对初始解的敏感性[41]。傅少川等[42-43]分别采用了贪婪算法和最邻近贪心算法生成高质量的初始解，较好地求解了所研究问题。Fu Zhuo等[44]则采用随机方式生成初始解，并通过设计混合邻域搜索和设置当前最好解选择机制等来降低禁忌搜索对初始解的敏感性，也较好地求解了所研究问题。

本文选择采用随机方式生成初始解，并参考文献[44]中算法设计的策略，通过邻域结构、禁忌规则、参数设置等针对性的设计来降低禁忌搜索对初始解的敏感性，增强禁忌搜索算法的寻优能力。

3.2 解的表示方式

在邻域搜索过程中，本文采用客户点编号和客户点中被满足的订单相对应排列的方式表示线路。用Cir表示某条线路经过客户点i并配送了该点第r个订单的货物。比如某条线路的排列(1C21C22C31C331)，表示客户点2的第1、2两个订单，客户点3的第1、3两个订单均由此条线路配送。每条线路均由1开始，在经过若干个客户点之后，由1结束，表示每辆车从车场出发并在完成任务后回到车场。

3.3 邻域结构

为增强算法的搜索能力，本算法采用混合邻域结构，即随机选择以下点操作或订单操作对当前解的邻域进行搜索。

随机选取两条线路R1和R2，将其客户点合并排列在一起，再进行相关操作。例如挑选到R1=(1C63C61C23C411)，R2=(1C72C33C32C521)，则合并排列为S=(1C63C61C23C411C72C33C32C521)。不考虑此排列中的第一个和最后一个“1”，从排列中随机选取两个订单q1和q2(加下划线表示)，其中将中间的“1”(车场)按只有一个订单的客户点处理。

3.4 解的评价

解的评价主要反映两方面的内容，一是解的目标函数值，二是解是否可行。 若某条路径中配送总量超过车辆装载能力w，或者车辆总行驶时间超过最长时间限制L，则该路径方案不可行。

该算法设计为可接受导致不可行解的变换，产生可行解和不可行解的混合，以便通过不可行解的过渡，对邻域空间进行充分搜索，找到更好的可行解，避免过早陷入局部最优。因此，将解的评价设为E=P1K+P2(Z+pM)，其中，P1、P2表示优先级，即P1>>P2，是定性的概念，不赋予任何具体数值。因此并不意味着目标之间的任何折衷，只表示每个目标的优先级。这样能够保证算法在求解时以最小化车辆使用数为第一优化目标，以最小化车辆行驶时间作为第二优化目标。M为当前解对应的配送路径方案的不可行路径条数，p为每条不可行路径的惩罚权重。若一个解是可行的，则M=0。p[50,2000]，开始时等于200，并通过一个自调整参数来加权，每隔10次迭代测试一次，若前面的10个解是可行的，则将其除以2；若所有的10个解都是不可行的，则将其乘以2。

3.5 禁忌规则

本算法选取定值15作为禁忌期(禁忌长度)。构造了一个(N×N)的矩阵作为禁忌表，以记录禁忌对象的禁忌情况。如果进行了点操作(操作(1)、(2)、(3))，则将被操作客户点i和j的禁忌情况存入(N×N)矩阵的元素(i,j)中。如果进行了订单操作(操作(4)、(5)))，则找到被操作订单q1和q2所属客户点i和j，将禁忌情况存入(N×N)矩阵的元素(i,j)中。每迭代一次，都要将禁忌表中其他被禁忌对象的禁忌期减去1，直至为0止。

3.6 算法描述

为了描述方便，定义以下变量：

iter为当前的迭代步数；

max-iter为最大的迭代步数；

cons-iter表示当前最好解保持不变的当前连续迭代步数；

max-cons-iter表示当前最好解保持不变的最大连续迭代步数；

cand-list当前解的候选解数量；

max-cand-list最大的候选解数量。

算法终止条件：当前最好解保持不变达到给定的max-cons-iter，或总迭代次数达到max-iter，则终止搜索进程。

算法流程框架如下：

步骤1：随机产生一个初始可行解，并将其作为当前解和当前最好解。

步骤2：初始化禁忌表，置iter和cons-iter为0。

步骤3：转入邻域搜索，随机选取所要进行的邻域变换。

步骤4：将所挑选的邻域变换作用于当前解，并将产生的新解放入候选解集中。

步骤5：cand-list的值加1。

步骤6：若cand-list<=max-cand-list，则转步骤3，否则，转下一步。

步骤7：若存在优于当前最好解的禁忌解，则解禁该解，并作为最佳候选解；若所有候选解都被禁忌，则解禁其中的最佳候选解；否则，从候选解集中选择非禁忌的最佳候选解；并置新的最佳候选解为当前解，iter的值加1。

步骤8：若新的最佳候选解优于当前的最好解，则更新当前最好解，并置cons-iter为0，否则，cons-iter的值加1；其中，若出现车辆数减少的可行解，则直接将其置为当前解和当前最好解，iter的值加1，并置cons-iter为0。

步骤9：若iter<=max-iter，且cons-iter<=max- cons-iter，则转步骤3；否则，终止算法。

4 测试结果及其比较

本文以国际上通用的Solomn[25]标准算例中的17个算例为基础，将各客户点的需求量随机分解为由1-5个订单组成，从而形成可用于测试本算法的算例。本算法使用Matlab7.11.0编程，并在CPU为Core(TM)i3双核处理器(2.40GHz)，内存2GB的微机上实现。

国内外对于需求依订单拆分的车辆路径问题研究较少，目前没有可直接对比的结果。故本文选取Ho和Haugland[40]和Fu等[2]中的第2种软时间窗类型(Type 2 of VRPSTW)的结果进行间接比较。两篇对比文献相较于本文约束条件更严格。因此，理论上而言，本文中两个优化目标的优化结果应小于或等于该两文献中的计算结果。

本算法中对于参数e，f的设定，需要根据实际应用中客户对于被服务时间要求程度来设定，本文设定e=f=0.2来测算算例。对于参数max-cand-list，max-cons-iter和max-iter的设定，经过多次求解算例，测试比较，设定参数值如下：max-cand-list=200，max-cons-iter= 4000，max-iter=20000。每个算例计算5次，选取其中的最好解与两篇文献中的最好结果做比较。计算结果和对比文献结果如表1所示。

计算结果表明，(1)对于测试算例，本文所得结果均优于或等于两篇文献的计算结果，达到了预期效果。(2)本文研究问题为带软时间窗，就是在有所偏离部分时间窗的基础上，最小化车辆行驶时间，亦达到基本要求。

表1 算法结果与比较

以表1中算例RC101为例，进一步说明本文算例的构造、所设计禁忌搜索算法计算得到的最终解、以及算法的收敛性等情况。

开始计算算例RC101时，各客户点的需求量被随机分解为由1-5个订单组成，订单生成情况如表2所示(其中0代表该订单不存在)。

表2 算例RC101各客户点的订单生成情况

本次计算RC101算例结束后得出最终解的路径规划情况如表3所示。需求未被拆分的客户点，则直接用该客户点编号来表示。需求被拆分的客户点，则在该客户点编号后，用括号详细罗列出被运送订单货物量，如表中加粗数字所示。编号中间用“-”连接。比如最终解中第1条线路为1-66(10, 1, 2)-91-70-89-79-74-80-61-56-1，则表示此线路中，包含客户点66, 91, 70, 89, 79，74，80，61，56，其中，只有客户点66被拆分，且货物量为10、1和2的三个订单由此线路服务。

表3 算例RC101最终解路径规划情况

至于本文所设计禁忌搜索算法的收敛情况，以本次计算算例RC101时，迭代过程中解的评价值E的变化情况为例说明，如图1所示。由图可知，算法收敛速度较快，收敛性较好。

图1 本次运算RC101算例时解的评价值E的变化情况

5 结语

本文研究带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法，并进行了编程实现。以 Solomn标准算例为基础构造算例对算法进行测试，并将求解结果与相关文献中的结果进行比较，表明所得结果优于目前约束条件更为严格的车辆路径问题的结果，且算法收敛性较好，达到了基本要求。为求解带软时间窗的需求依订单拆分车辆路径问题提供了一种求解算法。

[1] Dror M, Trudeau P. Savings by split delivery routing[J]. Transportations Science, 1989, 23(2):141-145.

[2] Fu Zhuo, Eglese R, Li L Y O. A unified tabu search algorithm for vehicle routing problems with soft time windows[J]. Journal of the Operational Research Society, 2008, 59(5):663-673.

[3] Dror M, Trudeau P. Split delivery routing[J]. Naval Research Logistics, 1990, 37(3):383-402.

[4] Archetti C, Savelsbergh M W, Grazia Speranza M. To split or not to split: That is the question[J]. Transportation Research Part E: Logistics and Transportation Review, 2008,44(1):114-123.

[5] Archetti C, Savelsbergh M W, Speranza M G. Worst-case analysis for split delivery vehicle routing problems[J]. Transportation Science, 2006, 40(2): 226-234.

[6] Archetti C, Feillet D, Gendreau M, et al. Complexity of the VRP and SDVRP[J]. Transportation Research Part C: Emerging Technologies, 2011,19(5):741-750.

[7] Archetti C, Mansini R, Speranza M G. Complexity and reducibility of the split delivery problem[J]. Transportation Science, 2005,39(2):182-187.

[8] Jin Mingzhou, Liu Kai, Eksioglu B. A column generation approach for the split delivery vehicle routing problem[J]. Operations Research Letters, 2008, 36(2): 265-270.

[9] Chen S8, Golden B, Wasil E. The split delivery vehicle routing problem: Applications, algorithms, test problems, and computational results[J]. Networks, 2007,49(4): 318-329.

[10] Salani M, Vacca I. Branch and price for the vehicle routing problem with discrete split deliveries and time windows[J]. European Journal of Operational Research, 2011, 213(3):470-477.

[11] Archetti C, Bianchessi N, Speranza M G. Branch-and-cut algorithms for the split delivery vehicle routing problem[J]. European Journal of Operational Research, 2014, 238(3): 685-698.

[12] Archetti C, Speranza M G, Hertz A. A tabu search algorithm for the split delivery vehicle routing problem[J]. Transportation Science, 2006, 40(1):64-73.

[13] Aleman R E, Hill R R. A tabu search with vocabulary building approach for the vehicle routing problem with split demands[J]. International Journal of Metaheuristics, 2010, 1(1):55-80.

[14] Berbotto L, García S, Nogales F J. A randomized granular tabu search heuristic for the split delivery vehicle routing problem[J]. Annals of Operations Research, 2014, 222(1):153-173.

[15] Campos V, Corberán A, Mota E. A scatter search algorithm for the split delivery vehicle routing problem[M]//Fin R A,Rothlauf F. Advances in Computational Intelligence in Transport, Logistics, and Supply Chain Management,Berlin-Heidelberg:Springer,2008:137-152.

[16] 谢毅. 需求可拆分的物流车辆路线问题研究[D]. 上海：同济大学，2006.

[17] 孟凡超，陆志强，孙小明. 需求可拆分车辆路径问题的禁忌搜索算法[J]. 计算机辅助工程，2010, 9(1):78-83.

[18] 陆琳. 不确定信息车辆路径问题及其智能算法研究[M]. 北京：科学出版社，2010.

[19] 李三彬，柴玉梅，王黎明. 需求可拆分的开放式车辆路径问题的研究[J]. 计算机工程，2011, 37(6):168-171.

[20] 刘旺盛，杨帆，李茂青，等. 需求可拆分车辆路径问题的聚类求解算法[J]. 控制与决策，2012, 27(4):535-540.

[21] 刘旺盛，黄娟. 需求可拆分的车辆路径问题的分段求解[J]. 集美大学学报，2011, 16(1):38-44.

[22] 杨亚璪，靳文舟，郝小妮，等. 求解集送货可拆分车辆路径问题的启发式算法[J]. 华南理工大学学报，2010, 38(3):58-62.

[23] Pankratz G. A grouping genetic algorithm for the pickup and delivery problem with time windows[J].OR Spectrum,2005,27(1): 21-41.

[24] Frizzell P W, Gi In J W. The split delivery vehicle scheduling problem with time windows and grid network distances[J]. Computers & Operational Research, 1995, 22(6): 655-667.

[25] Solomn M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265.

[26] 侯立文，谭家美，赵元. 求解带时间窗的客户需求可分条件下的车辆路径问题[J]. 中国管理科学，2007, 15(6):78-83.

[27] 马华伟, 叶浩然, 夏维. 允许分割配送的多时间窗车辆调度问题的改进蚁群算法求解[J]. 中国管理科学，2012, 20(S1):43-47.

[28] 李宁，邹彤，孙德宝. 带时间窗车辆路径问题的粒子群算法[J]. 系统工程理论与实践，2004, 24(4):134-140.

[29] 吴耀华，张念志. 带时间窗车辆路径问题的改进粒子群算法研究[J]. 计算机工程与应用，2010, 46(15): 345-349.

[30] 马炫，彭芃，刘庆. 求解带时间窗车辆路径问题的改进粒子群算法[J]. 计算机工程与应用，2009, 45(27): 679-684.

[31] 汪勇，丁凡，吴志华. 协同进化遗传算法求解带时间窗的车辆路径问题[J]. 统计与决策，2010, (10):76-87.

[32] 潘立军,符卓. 求解带时间窗取送货问题的遗传算法. 系统工程理论与实践, 2012, 32 (1):120-126.

[33] 潘立军,符卓. 求解带时间窗车辆路径问题的时差插入检测法. 系统工程理论与实践, 2012, 32(2):319-322.

[34] 宾松，符卓. 求解带软时间窗的车辆路径问题的改进遗传算法[J]. 系统工程，2003, 21(6):79-85.

[35] 祁文祥，陆志强，孙小明. 带软时间窗的集货与送货多车辆路径问题节约算法[J]. 交通运输工程学报，2010, 10(2):99-103.

[36] Dror M, Laporte G, Trudeau P. Vehicle routing with split deliveries[J]. Discrete Applied Mathematics,1994, 50(3): 239-254.

[37] Archetti C, Mansini R, Speranza M G. Complexity and reducibility of the skip delivery problem[J]. Transportation Science, 2005, 39(2): 182-187.

[38] Gendreau M, Laporte G, Potvin J Y. Metaheuristics for the Capacitated VRP[M]//Toth P, Vigo D. The vehicle routing problem. Philadelphia, PA: SIAM Monographs on Discrete Mathematics and Applications, 2002:129-154.

[39] Cordeau J F, Gendreau M, Laporte G, et al. A guide to vehicle routing heuristics[J]. Journal of the Operational Research Society, 2002, 53(5): 512-522.

[40] Ho S C, Haugland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers & Operations Research, 2004, 31(12):1947-1964.

[41] 刘光远，贺一，温万惠. 禁忌搜索算法及应用[M]. 北京：科学出版社，2014.

[42] 傅少川，胡梦飞，唐方成. 禁忌搜索算法在单分配多枢纽辐射式物流网络中的应用[J]. 中国管理科学，2012, 20(3)：145-151.

[43] 李进，傅培华，李修琳，等. 低碳环境下的车辆路径问题及禁忌搜索算法研究[J]. 中国管理科学，2015, 23(10)：98-106.

[44] Fu Zhuo, Eglese R, Li L Y O. A new tabu search heuristic for the open vehicle routing problem[J]. Journal of the Operational Research Society, 2005, 56(3):267-274.

A Tabu Search Algorithm for the Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order

FU Zhuo, LIU Wen, QIU Meng

(School of Traffic and Transportation Engineering, Central South University, Changsha 410075,China)

As an important type of vehicle routing problem, split delivery vehicle routing problem, which can be divided into two subtypes, split deliveries without restriction (by unit) and split deliveries by order, has broad applications such as distribution vehicle routing optimization and so on. In most of the present research of split delivery vehicle routing problem, customers’ demands can be split without restrictions. However, in practical, sometimes a customer order consists of several cargos and could not be split during deliveries. So the cargos in the same order can only be delivered by the same vehicle. In that condition, customers’ demands can be split in orders while a specific order could not be split. In addition, more and more customers have time window requirement during the distribution process. Considering this two respects, the vehicle routing problem with soft time windows and split deliveries by the order and its optimization algorithm are presented. The problem allows that the same customer can be serviced by multiple vehicles and the customer demand can be split but not split a specific order. Customers can be served either in the specified time windows or out of the time windows with according punishment. A mixed integer programming model for the problem is constructed and a tabu search algorithm for the model is proposed. The proposed algorithm was coded and tested on the problems which are based on the benchmark problems generated by Solomn. The computational results are compared with the ones in related literatures. It shows that the algorithm converges well and effectively solves the problem.

vehicle routing problem；split deliveries by order；Soft time windows；tabu search algorithm

1003-207(2017)05-0078-09

10.16381/j.cnki.issn1003-207x.2017.05.010

2015-12-14；

2016-05-12

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

符卓(1960-)，男(汉族)，中南大学交通运输工程学院，教授，博士，博士生导师,研究方向：物流系统优化，E-mail: zhfu@csu.edu.cn.

O221；F253.4

A