0 引言

带时间窗的车辆路径问题(vehicle routing problem with time windows, VRPTW)是在基本车辆路径问题^[1](vehicle routing problem, VRP)的基础上增加了客户接受配送服务的时间窗要求，较VRP更贴近实际配送情况。与VRP类似，VRPTW亦属于NP难问题。由于问题规模较大时，传统精确算法难以求出VRPTW的最优解，因此，国内外很多学者利用智能启发式算法来寻找该问题的满意解。常见的求解VRPTW的智能优化算法包括：蚁群算法^[2-5]、遗传算法^[6-7]、粒子群算法^[8-10]、禁忌搜索算法等^[11-13]。但是，由于遗传算法与禁忌搜索算法的早熟易收敛问题，蚁群算法和粒子群算法的易陷入局部最优缺陷，故目前仍未找到求解性能具有明显优势的VRPTW求解算法。因此，对VRPTW求解方法的研究仍属于运筹学、物流配送和交通运输工程等领域的研究重点和热点。

狼群算法^[14](Wolf Pack Algorithm, WPA)作为一种新型智能启发式算法，是对自然界中狼群分工协作捕食行为的智能模拟，是一种基于种群的随机寻优算法。目前，该算法已被成功应用于TSP问题、0-1高维背包问题和多维连续优化等多种问题的求解，并取得了良好的效果。但是，截至目前为止，尚未有文献将狼群算法应用于VRPTW的求解。

基于求解TSP的离散狼群算法^[15]，结合带时间窗的车辆路径问题的具体特征，提出了求解VRPTW的狼群算法, 并与其他智能算法如蚁群算法^[4]、遗传算法^[16-17]等比较，不仅验证了本算法在求解VRPTW问题上的有效性，而且拓宽了狼群算法的应用领域。

1 带时间窗的车辆路径问题

带时间窗的车辆路径问题可被粗略地分为：带硬时间窗的车辆路径问题(vehicle routing problem with hard time windows, VRPHTW)和带软时间窗的车辆路径问题(vehicle routing problem with soft time windows, VRPSTW)。VRPHTW要求各个客户的配送服务必须在预先给定的时间窗内开始，否则构成问题的不可行解；在VRPSTW中，配送车辆可以在客户预先给定的配送时间窗之外为其提供服务，但需要对违反时间窗约束的服务给予一定惩罚。

车辆路径问题的狼群算法既包括带硬时间窗的车辆路径问题的狼群算法，又包括带软时间窗的车辆路径问题的狼群算法。

1.1 问题描述

本研究带时间窗的车辆路径问题是指：在各客户需求量及其地理位置、配送中心地理位置均已知的情况下，要求合理安排配送路线，使得所有客户的需求均被满足，并且车辆的配送旅行总费用达到最小。同时，配送车辆还必须满足如下条件：

(1) 服务约束：每辆车可以为多个客户提供服务，但每个客户只能由1辆车为其服务且仅被服务1次。

(2) 配送中心约束：每辆车均由配送中心出发，在自身能力范围内服务完一定数量的客户后返回配送中心。

(3) 车载量约束：每条配送路径上所有客户的需求量之和不能超过配送车辆的最大载重量。

(4) 时间窗约束：客户i接受服务的最早开始时间和最晚开始时间分别为ET_i和LT_i(ET_i < LT_i)，若任一客户i接受服务的时间不能超过其时间窗[ET_i, LT_i]的限制，则该车辆路径问题属于VRPHTW；否则，属于VRPSTW。在VRPHTW中，若车辆在ET_i之前到达客户i，则需要等到ET_i才能为其服务，但车辆不允许在LT_i之后为客户i提供服务。

1.2 符号定义与数学模型

记N={1, 2, …, n}，V={0}∪N和K={1, 2, …, m}分别为客户集，物流网络中的所有顶点(配送中心编号为0) 集和配送车辆集。设某一配送中心利用m辆车为其n个客户提供配送服务，车辆k(k∈K)的载重量为Q_k；车辆从配送中心出发和到达客户i的时刻分别为T₀和T_i；客户i允许服务的最早开始时间和最晚开始时间分别为ET_i和LT_i；客户i的需求量、服务时间和等待时间分别为q_i，s_i和w_i(w_i=max{0, ET_i－T_i})；车辆由客户i到客户j的旅行成本(或距离)和旅行时间分别为c_ij和t_ij；为车辆k的配送客户集，|S_k|表示集合S_k中所含的顶点个数。

决策变量：

数学模型：

(1)

(2)

(3)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

模型中，式(1) 为目标函数，表示服务完所有客户所需旅行总费用(或总距离)最短；式(2) 为车辆载重量限制；式(3) 表示每个客户只能由1辆车为其服务且仅被服务1次；式(4) 表示从配送中心出发的车辆在完成配送任务后返回配送中心；式(5) 表示车辆在服务完节点i后紧接着服务节点j；式(6) 表示车辆在服务节点j之前服务节点i；式(7) 消除路径中的子回路；式(8) 为车辆到达每个客户的时间表达式；式(9) 为服务时间窗限制。式(9) 要求任一客户i接受服务的时间不能超过其时间窗[ET_i, LT_i]的限制，因此，模型(1) ~(11) 属于VRPHTW。

若松弛上述模型中的约束条件(9)，允许任一客户i在其预先给定的时间窗[ET_i, LT_i]外接受服务，并记P_E和P_L分别为车辆提前到达某客户的单位等待成本和延迟服务客户的单位惩罚成本，则可将上述VRPHTW问题(1) ~(11) 转化为下述VRPSTW问题：

(12)

其中，max{ET_i－T_i, 0}和max{T_i－LT_i, 0}分别表示提前到达客户i的等待时间和晚到的服务延迟时间，式(12) 中的第2项和第3项分别表示提前到达的等待成本和延迟服务的惩罚成本。显然，当P_E=P_L=M(M为一个足够大的正数)时，该VRPSTW问题亦可被认作VRPHTW问题。

2 求解VRPTW的狼群算法

与蚁群算法^[2-5]、粒子群算法^[8-10]、蜂群算法^[18]等群体智能算法类似，狼群算法是通过模拟其捕食行为而建立的仿生算法。它与蜂群算法有着异曲同工之处，将整个狼群分为头狼、探狼和猛狼3种角色，依据职能分工(游走、召唤、围攻)与群体信息交互实现协同寻优。本研究根据带时间窗的车辆路径问题的具体特征，借鉴求解TSP问题的离散狼群算法^[15]思想，提出了一种求解VRPTW的狼群算法。首先设计了一种二维编码方式，采用近邻初始化方式构建初始解；随后通过游走行为使人工狼对问题的解空间进行充分搜索，并利用召唤和围攻行为，借助种群间的信息共享使狼群向最优解空间聚集，达到快速寻优的目的。

2.1 编码方式

本研究采用二维编码方式对各人工狼进行编码。每只人工狼i与两个n维向量X_ir和X_iv相对应：X_ir为人工狼i对应的客户编码序列；X_iv为车辆编码序列(即各客户对应的服务车辆编号)；换言之，与人工狼i所相应的两个n维向量X_ir和X_iv可以共同决定问题的一个解。

例如，对于一个拥有8个客户的VRPTW问题，与某人工狼i所相应的8维向量X_ir和X_iv分别为：

并由X_ir和X_iv可知与该人工狼i所对应的配送路径为：

路径1(车辆编号为1的路径): 0→3→6→0；

路径2(车辆编号为2的路径): 0→2→5→1→8→0；

路径3(车辆编号为3的路径):0→4→7→0。

2.2 相关定义

定义1：近邻矩阵。near(i, p)=j(i, p, j∈N)表示客户j是距离客户i第p近的客户，记客户i到自身的距离最远，即near(i, n)=i。若near(3, 1)=6，则表明客户6是距离客户3最近的客户。

定义2：反转算子。给定人工狼i的客户编码序列X_ir，反转算子Rev(X_ir, a, b)(a∈N，b∈N且a≠b)表示将序列X_ir中a和b之间的所有客户点(包括a和b)进行逆序排列。如：X_ir=[2, 4, 6, 1, 3, 9, 5, 8, 7]，a=6，b=5，则Rev(X_ir, a, b)=Rev(X_ir, 6, 5)=[2, 4, 5, 9, 3, 1, 6, 8, 7]。

2.3 种群初始化

本研究采用近邻初始化方法构建初始解。对于规模为Num的人工狼群，初始化的具体步骤如下：

步骤1：对人工狼i(i≤Num)，置X_ir=Φ和X_iv=Φ；

步骤2：随机产生初始服务客户点a(a∈N)，并令X_ir=X_ir∪{a}和迭代次数t=1；

步骤3：根据近邻矩阵，在未被访问的客户集中选择距离上一个访问客户点a最近的客户b作为下一个服务客户，并更新X_ir=X_ir∪{b}和t=t+1。

步骤4：若t < n，则转步骤3；否则，转步骤5。

步骤5：根据客户编码序列X_ir，满足车载量限制和时间窗等约束条件，得到与X_ir相对应的车辆编码序列X_iv。

步骤6：若i < Num，则令i=i+1，并转步骤1；否则，结束初始化操作。

2.4 智能行为设计

带时间窗的车辆路径问题的求解关键在于以目标函数最小化为前提，确定各路径上客户的访问先后顺序。结合带时间窗的车辆路径问题的具体特征，可将狼群算法中头狼选择、探狼游走、头狼召唤和猛狼围攻等机制定义如下：

(1) 头狼选择机制。根据初始解和式(12) 计算各人工狼的适应度，并记人工狼i的适应度值为Y_i。选择狼群中适应度值最小的人工狼i为头狼，则头狼的适应度值为Y_leader=Y_i。若存在多匹人工狼的适应度值相同且最小，则随机选择其中1匹为头狼。

(2) 游走机制。将头狼以外的人工狼视为探狼。若探狼i的适应度Y_i满足Y_i < Y_leader，则探狼i替代头狼，并发号命令；否则，探狼i需要向其周围h个方向进行游走(游走方向是指在解空间中试探性寻找更佳解的方位)，探寻猎物。将探狼i向第l(l=1, 2, …, h)个方向游走的行为定义为：对与其相对应的客户编码序列X_ir={x_i1, x_i2, …, x_in}进行反转操作。具体操作过程为：首先，在X_ir中随机选取一个客户x_ik，记与x_ik相邻的下一个客户为x_i(k+1)；然后，根据近邻矩阵，确定距离客户x_ik最近的客户，并将其记为x_ig；最后，更新X_ir=Rev(X_ir, x_i(k+1), x_ig)，并依据X_ir及相关约束条件更新车辆编码序列X_iv。如果探狼i向第l个方向游走时，存在x_i(k+1)=x_ig，则在客户编码序列X_ir中随机选择2个不同客户x_ia和x_ib，并更新X_ir=Rev(X_ir, x_ia, x_ib)和X_iv。下面给出了探狼i向某一方向游走前后的客户编码序列X_ir变化情况示例：

记探狼i向第l个方向游走前后的适应度值分别为Y_i和Y_il，若Y_il < Y_i，则将探狼位置更新为游走后的新位置；否则，探狼的位置不发生变化。随后，重复游走行为，直到Y_i < Y_leader或者T>T_max(T为游走次数，T_max为最大游走次数)。

(3) 召唤机制。将头狼之外的所有人工狼视为猛狼，头狼通过召唤将自身经验与猛狼进行分享。召唤行为可定义为：首先，在头狼的客户编码序列X_sr中随机取一子序列，并令其替换猛狼i的X_ir中相同位置相同长度的子序列；随后，通过调整策略，确保每个客户在X_ir中仅出现一次；最后，根据新的客户编码序列X_ir和客户车辆相关约束条件更新猛狼i的车辆编码序列X_iv，从而得到新的配送路径。例如：若头狼和猛狼i的客户编码序列分别为X_sr=[7, 2, 5, 8, 3, 1, 6, 4]和X_ir=[3, 1, 5, 7, 8, 2, 4, 6]。随机选取头狼X_sr中的子序列[8, 3, 1]，令其替换X_ir中的子序列为[7, 8, 2]，则X_ir可被更新为[3, 1, 5, 8, 3, 1, 4, 6]；然后，通过映射消除重复客户(3→7, 1→2) 得到猛狼i的客户编码序列X_ir=[7, 2, 5, 8, 3, 1, 4, 6]；最后，根据更新后的X_ir及约束条件更新车辆编码序列X_iv，进而得到新解。

召唤机制体现了头狼对其他人工狼的引导作用。在向头狼聚拢的过程中，若存在Y_i < Y_leader，则猛狼i替换头狼，并继续召唤行为；否则该猛狼结束奔袭，转入待围攻状态。

(4) 围攻机制。由于奔袭后头狼距猎物(最优解)很近，可将头狼位置视为最优解位置。围攻主要体现头狼与其他人工狼间的信息共享，则将围攻行为定义为：在头狼的客户编码序列X_sr中随机选择一子序列s₁，若人工狼i的客户编码序列X_ir中存在与s₁包含相同客户但顺序不同的序列s₂，且s₂与s₁具有相同的首尾元素，则比较子序列s₁与s₂的配送路径长度。若s₂序列的路径长度length(s₂)小于s₁序列的路径长度length(s₁)且Y′_leader < Y_leader(Y′_leader为s₂替换X_sr中s₁后的适应度值)，则用s₂替换X_sr中的s₁，并根据X_sr和约束条件更新其车辆编码序列X_sv；若length(s₂)>length(s₁)，则用s₁替换X_ir中的s₂并更新其车辆路径编码序列X_iv和适应度Y_i，若存在Y_i < Y_leader，则用人工狼i替换头狼并结束围攻行为。

2.5 算法步骤

根据上述头狼选择机制、探狼游走机制、头狼召唤机制和猛狼围攻机制，可将求解VRPTW的狼群算法描述为如下求解步骤：

步骤1：初始化算法参数，设定最大迭代次数Iters，种群规模Num，最大游走次数T_max，探索方向h；

步骤2：近邻初始化狼群(包括X_ir和X_iv两部分)，计算各人工狼对应的目标函数值(Y_i)，并确定头狼；

步骤3：探狼根据游走机制执行游走行为，直至游走次数T>T_max或者Y_i < Y_leader；

步骤4：按照召唤机制执行召唤行为，若存在Y_i < Y_leader，则猛狼i替换头狼并发起召唤行为；

步骤5：根据围攻机制完成围攻行为，更新狼群并进入下一次迭代iter=iter+1；

步骤6：若iter≤Iters，则转步骤3，否则，转步骤7；

步骤7：输出当前最优解。

3 算例分析

为检验狼群算法的求解性能，在Intel(R)Pentium(R)CPU B960@2.20GHz处理器，2.00 GB内存，操作系统为32位Windows 7试验环境下，应用MATLAB 2014 a编程实现了求解VRPTW问题的狼群算法，并对下述4个算例进行仿真实验。

算例1 本算例来源于文献[11, 16-17]。有8个客户(编号1-8) 和1个配送中心(编号0)，配送车辆具有相同的行驶速度和容量限制，其中车速为50 km/h，最大容量为8 t，单位运输成本为1，超出时间窗的单位惩罚成本为P_E=P_L=50。

求解该算例的狼群算法参数设置情况为：最大迭代次数Iters=30，种群规模Num=20，最大游走次数T_max=10，探寻方向h=4。

运用狼群算法独立求解20次，解得最优费用均为910，总路程均为910 km，3条配送路径为：0-3-1-2-0；0-6-4-0；0-8-5-7-0。与文献[11, 16-17]中求得的最优解相同，并且求得最优解的成功率为100%。其中，文献[11]是采用Memetic混合粒子群算法，其种群规模为30，迭代次数为50，算法求解成功率为96%；文献[16]采用遗传算法求解，设置种群规模为20，最大迭代次数为50，算法求解成功率为67%；文献[17]采用改进遗传算法求解，其设定种群规模为20，迭代次数为20，算法成功率为80%。通过比较可以看出，本研究所设计的求解VRPTW的狼群算法具有较好的求解稳定性。

算例2 本算例来源于文献[4, 16-17]。设有9个客户(编号1~9)，配送中心编号为0，每辆车的最大容量为1，车行驶速度为1，客户具体信息(编号i，坐标(x, y)，需求量q_i，时间窗[ET_i, LT_i])如表 1所示。

求解该算例的狼群算法参数设置为：最大迭代次数Iters=30，种群规模Num=20，最大游走次数T_max=10，探索方向h=4。本研究与文献[4, 16-17]所采取的方法一致，在硬时间窗的情况下，设M为足够大的数M=10 000，并运用本研究算法独立求解算例20次，得到的最优解均为459.175 1，对应的车辆路径安排为：0-7-2-4-0、0-3-9-5-6-1-0、0-8-0。在软时间窗的情况下，单位等待成本与单位惩罚成本分别为P_E=2，P_L=3，独立求解算例20次，得到的最优解与在硬时间窗情况下的最优解完全一致。

本研究算法最优解与文献[4, 16-17]中完全一致。其中，文献[4]中改进蚁群算法的蚁群规模为100，最大迭代次数500；文献[16]遗传算法中种群规模为20，最大迭代次数为100。可见本研究算法能通过更少的迭代次数与种群规模解得问题最优解，具有更佳的搜索策略。

算例3 本算例来源于文献[4, 12]，其配送中心编码为0，有15个客户(编号1~15)，车辆最大容量为5，车辆行驶速度v=1，客户具体信息(编号i，坐标(x, y)，需求量q_i，时间窗[ET_i, LT_i])见表 2。

求解本算例的狼群算法参数设置为：迭代次数Iters=50，种群规模Num=50，最大游走次数T_max=10，探寻方向h=4。此外，与文献[4]和[12]一致，在硬时间窗情况下，设置单位等待成本与单位惩罚成本为M=10 000，应用本研究算法独立求解20次，得到其最优解为562.12，如表 3所示；在软时间窗情况下，设置单位等待成本与单位惩罚成本分别为P_E=0.5，P_L=2，运用狼群算法独立求解20次，得到其最优解为538.73，其结果见表 4。

由表 3可知硬时间窗情况下，本研究算法求得最小费用为562.12，不仅优于文献[12]中禁忌算法解得的最小费用585.77，而且相对于文献[4]中应用改进蚁群算法求得最小费用567.27亦有提升；而对于软时间窗而言，从表 4可以看出，本研究算法求解结果虽然需在客户点12(等待成本12.13) 和客户15(等待成本0.20) 产生惩罚，比文献[12]仅在客户点15处产生等待成本9.6多一个惩罚点，但其最小费用538.73远优于后者的573.71；另外，与文献[4]相比，在同等惩罚情况下，本研究算法求解得到的最优解538.73亦是远优于文献[4]中的570.00。由此显而易见，本研究算法求解效果优于二者。

算例4 为了进一步验证本研究所设计的狼群算法求解较大规模的VRPTW实例时的可行性与有效性，随机选取4个Solomon给出的VRPTW算例(数据来源：)，并利用狼群算法对其求解。

本研究设计的狼群算法对4个例子求解的次数均为20次，求解结果见表 5。此外，对于客户数为25的算例，设置迭代次数Iters=50，种群规模Num=50；对于客户数为50的算例，迭代次数Iters=50，种群规模为Num=100。

表 5不仅给出了4个Solomon测试算例及其客户数，而且给出了这些算例在硬时间窗情况下的已知最优解和应用狼群算法解得的最佳解，并给出最佳解与已知最优解总路程之间的gap值(gap=((本研究算法所求得的总路程-已知最优总路程)/已知最优总路程)×100%)。其中，遗传算法、粒子群算法和碰撞粒子群算法的最优解来自文献[19]。

由表 5可知，本研究狼群算法求解的最优解与已知最优解一样具有相同的车辆数，尽管其总路程稍逊于已知最优解，但其gap值最大不超过5%。并且与遗传算法、粒子群算法和碰撞粒子群算法相比，在求解精度上具有一定优势。由此可见，狼群算法在求解较多客户数的VRPTW时能够在较小种群规模与迭代次数情况下解得良好的实验结果，总体来看与已知最优解的误差较小，且有些算例结果十分接近最优解，故进一步验证了狼群算法在求解VRPTW上的可行性与有效性。

4 结论

通过模拟狼群觅食行为，采用近邻初始化方法，重新定义狼群位置及智能行为，设计了一种求解带时间窗的车辆路径问题的狼群算法。算法采用种群近邻初始化方法使得各人工狼具有较优的初始解，提高了算法寻优速率；另外，算法所设计的召唤机制和围攻机制体现了个体间的相互交流与学习，有利于算法在较优的解空间中进行搜索，加快了算法的收敛。求解多个测试算例，并将算法的计算结果与禁忌搜索算法、遗传算法、改进蚁群算法和混合粒子群算法等方法的计算结果进行对比，结果表明：狼群算法具有更优的求解精度与收敛性。

研究表明：狼群算法在求解软硬时间窗的车辆路径问题中均具有很好的求解性能，是一种行之有效的优化算法。狼群算法在VRPTW问题上的成功应用进一步拓宽了其实际应用领域。在此研究的基础上，针对实际车辆调度中客户需求的动态变化，道路状况受天气或交通事故等外在因素影响而呈现出的动态特性，将会是作者下一步的研究重点。