0 引言

车辆路径问题(vehicle routing problem，VRP)属于NP-Hard问题^[1]，自Dantzig^[1]在1959年提出之后，便引起了组合优化学界和交通运输学界的重视^[2-4]，VRP在物流配送领域存在广泛应用价值^[2-8].城市连锁超市^[9]商品配送具有时间段要求，可归结为带时间窗的车辆路径问题^[10](VRP with Time Windows，VRPTW). VRPTW根据时间窗是否允许偏离可分为带软时间窗的VRP(VRP with Soft Time Windows，VRPSTW)和带硬时间的VRP(VRP with Hard Time Windows，VRPHTW).在实践中，各连锁超市基于自身的市场环境，会根据库存、顾客预订购需求及历史消费数据等情况，提前向配送中心发出下一批次的商品需求(一般是每日1~2个批次)，并且希望配送中心尽可能满足其提出的期望时间窗，以便超市的经营.

目前，国内外已有较多关于VRPHTW的物流配送研究文献，但针对城市连锁超市配送的VRPSTW文献较为少见.以往的VRP研究^[8]中，为了方便各城市配送需求节点的运作，通常采用硬时间窗约束.文[2]设计了一个混合遗传算法(hybrid genetic algorithm，HGA)来求解模糊需求VRPHTW，其在算法中设计了多种邻域搜索策略，提升了遗传算法(genetic algorithm，GA)的寻优性能.文[3]设计了模拟退火算法(simulated annealing，SA)和遗传算法(GA)来求解经典VRPHTW，并对各算法的寻优性能进行了比较.文[8]将节能策略纳入VRPHTW中，采用蚁群优化算法(ant colony optimization，ACO)求解了一个北京市的区域配送算例.

硬时间窗虽有利于准时制配送(just in time distribution，JITD)，但刚性过强，常会造成低装载率、长距离迂回行驶等情况，使得整个配送系统成本过高，因此，软时间窗^[2]更有利于柔性配送与降低成本.不过，若采用软时间窗限制，则也容易造成配送线路末尾的部分超市收货太迟，耽误商品出售.因此，在采用软时间窗约束时，还应结合超市现有库存及历史销售情况对连锁超市的断货时间点进行预估，当让车辆在断货时间点前推一个最长工作时间L发货时，即可保证各超市在每个营业时段内不会断货，能接收到从配送中心送达的下一批次需求商品.这样一来，既不影响超市的商品销售，也可降低整个配送系统的总成本，助力企业的可持续发展^[11].由此可知，本文的连锁超市商品配送路径优化可归结为一种带工作时间和软时间窗的VRP(VRP with Soft Time Windows and Working Time，VRPSTWWT).

带时间窗的VRP^[10](VRP with Time Windows，VRPTW)属于多约束多极值NP-Hard问题，其求解比基本VRP更复杂^[12-13].目前，采用VRPHTW模型的文献较多，采用VRPSTW的相对较少，而硬时间窗可以看成软时间窗的特例，设计能有效解决大规模VRPSTW的智能算法正是城市连锁超市配送的实践需要^[12]，因此，本文对VRPSTWWT的研究具有较强的理论与实践意义.本文将结合带工作时间和软时间窗VRP特点，构建相应的双目标数学模型，设计一个改进的自适应禁忌搜索算法(Adaptive Tabu Search algorithm，ATS)进行求解.

1 问题描述与数学模型构建

本文的城市连锁超市商品配送路径优化属于VRPSTWWT，是指在满足车辆装载能力Q和线路最长工作时间L限制条件下，合理安排同车型车辆k(k=1，2，…，K)从配送中心点0出发至各超市节点i(i=1，2，…，N)之间的送货顺序，最终返回配送中心，并使总成本最小. VRPSTWWT在每一批次商品配送中需满足一定条件，具体如下：

1) 基于长期的经营，假设连锁超市已有较稳定的顾客需求.为保障每批次进行配送的车辆能够及时到位，本文约定全部车辆送货后需返回配送中心，因此本文的车辆线路为闭合式^[14].

2) 在每一批次商品配送前，各超市以“预订送模式”向总部配送中心发送商品需求信息，即假设各超市节点的需求信息提前已知，其中第i个节点的信息如需求量d_i、期望时间窗[a_i，b_i]、服务时间w_i、地理位置等都已知.约定车辆在t₀=0时刻从配送中心出发，并在最长工作时间L内返回配送中心，即配送中心点0拥有一个硬时间窗约束[0，L].

3) 各超市节点的时间窗[a_i，b_i]为软约束.当车辆到点i的时刻t_i偏离期望时间窗时需支付惩罚费用，提前与推迟的单位惩罚费用设定为：早于a_i时刻到达为a，晚于b_i时刻到达为b，a与b的取值需根据市场实际情况来进行确定，当对时间窗的要求高时取较大值，反之则可取较小值.本文取a=0.1，b=0.1.

4) 每个批次内各超市的需求须保证，且只能由一辆车单次送达.假设各点之间的行驶时间符合三角不等式，将行驶时间与行驶费用对等.若同一车辆在服务完点i后紧邻服务点j，则应有式(1)，其中t_ij为点i与j之间的行驶时间.

(1)

5) 由于大型专用商品货车通常较贵，多一辆车通常需多支付一位司机费用和其它附加费用，所以本文与一般VRP文献^[4]一样，设定两级目标，第一级目标为使用车辆数K最小化，第二级目标为行驶时间费用与时间窗的偏离费之和Z最小化，且规定第一级目标具有绝对优先权.另外，根据d_i与Q可估算所需的车辆数下限K_min，其取值如式(2)，其中⌊ ⌋为向下取整.

(2)

6) 设y_ij^k为布尔型变量，当第k辆车服务点i后便紧邻服务点j，其值为1，否则为0.

7) 忽略各种故障、意外等带来的影响.

根据以上描述，本文VRPSTWWT的双目标数学模型具体如下：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

以上式(1)~式(11)构成了本文的双目标数学模型.其中式(3)、式(4)为目标函数；式(5)、式(6)为车辆的最长工作时间与装载能力限制；式(7)~式(10)可保证每个超市节点只被服务一次，各中间点的进出车辆数量相等及全部车辆从配送中心出发并最终返向原来出发点；式(11)可消去子回路.

2 自适应禁忌搜索算法设计

VRPSTWWT属于NP-Hard问题，精确算法^[5]难以有效求解大规模配送问题，一般都采用智能算法^{[4-9, 12-18]}(元启发式算法)，如模拟退火算法(SA)、蚁群优化算法(ACO)、遗传算法(GA)、禁忌搜索算法(tabu search，TS)等进行求解，各类型的基本智能算法都具有自身的优势与特点，但也存在一些明显缺陷.其中SA是一种类比固体退火原理的算法，属于概率式算法范畴，其存在收敛较慢、参数敏感性强和初始解依赖性强等问题，寻优能力有限；ACO是一种模仿蚂蚁觅食的算法，也是一种概率式算法，其算法参数设定较麻烦，常存在停滞现象，基本算法难以使计算性能达到最优；GA作为一种生物进化仿生算法，具有较强的全局寻优能力，但也易存在早熟和停滞现象，而且在求解大规模问题时计算时间较长；基本TS是一种模仿人类智能思维过程的算法，其特点是对已搜索的地方禁忌，其邻域搜索能力较强，不过有学者认为其最终解的质量对“初始解”有一定的依赖性^[3].

禁忌搜索理论上是一种邻域搜索能力较强的全局优化算法^[4]，本身蕴含了巨大的寻优潜力，从已有文[12-18]来看，TS是一种求解VRP类型的高效算法.与基本TS相比，本文会在设计的自适应禁忌搜索算法中加入多种性能提升策略，增强ATS的鲁棒性，提升算法的全局寻优能力.

2.1 解的表示与初始解

部分学者^[3]认为基本TS最终解的质量对“初始解”有一定的依赖性.这一方面体现了基本TS的缺陷，但也间接说明TS的寻优性能还存在较大提升空间，即TS还有很多隐性的智能搜索功能尚待开发.以往文献为了克服基本TS对初始解的依赖现象，常设计混合算法来分阶段求解，即采用SA、ACO、GA或其它的启发式算法先生成较高质量的初始解，然后再采用TS进行优化，这种混合算法也常能收获不错的效果^[3].

人类作为智能化的高级动物，是生物界智商最高的代表，从Jensen(E·詹森)所著的《基于脑的学习》(华东师范大学出版社，2008年)可知人类本身蕴含着巨大的智能潜力，采用相适应的学习方式有助于挖掘大脑潜能，将人类智能从“隐”式转化为“显”式^[19]，美国心理学之父William James(威廉·詹姆斯)认为普通人的大脑智能开发不到10%，物理学家Albert Einstein(阿尔伯特·爱因斯坦)的大脑智能开发也只比一般人多几个百分点.不论William James这个10%的界定是否精确，但从中至少可知人类的智能思维潜力巨大. TS设计的核心便是对人类思维的模仿过程，其本身蕴含了人类的智能潜力，只要算法设计能充分挖掘TS的智能寻优潜力，再借助于计算机的计算速度，最终优化解的质量不应过于依赖初始解的质量，即采用随机方式生成初始解也可获得高质量优化解.

Fu等^[4]在研究带装载能力约束的开放式VRP时，设计了两个仅“初始解”构造方式不同的改进TS算法，其一为采用“随机方式”生成初始解，其二为结合“经典启发式算法”生成高质量的初始解，通过测试对比，其发现二者最终优化解的质量区别很小. Fu等^[4]指出TS本身就属于一类全局优化算法，理应具有较强的鲁棒性，只要改进策略设计优良，则随机生成“初始解”对最终结果无本质影响，另外，其还特别指出接受部分不可行解会有助于提升算法的寻优性能.

本文参考Fu等^[4]的初始解生成方式，决定采用随机方式构造初始化解.本文允许初始解违反客户点的期望时间窗，但车辆的装载能力Q和线路最长工作时间L限制必须保证.初始解的构造方式如下：先随机生成客户点1、2、…、N的一个排列，然后在满足Q与L限制下，按照此排列顺序将客户点依次添入车辆线路中，当违背Q或L限制时就开启一条新线路.

2.2 多邻域结构体设计

邻域变换可用来生成候选解集.本文的ATS算法设计了多邻域随机变换策略，每次随机选出一种邻域对当前解变换来获取候选解，多邻域结构体有助于增强邻域解的丰富性，避免算法的过早收敛，而随机挑选邻域策略则有助于ATS在少数几步内实现对多个邻域的快速访问.

在操作前，每次随机挑选出两条不同线路R₁与R₂，然后在R₁与R₂内各随机挑选一个非0点来进行操作，每次邻域操作后，逢多个0相邻则只保留最前面的一个，并对相关约束条件进行检验.邻域变换在以下5种结构中随机选择，例如在解S=(0329015047860…0)，下划线处为随机选出的两个客户点j₁与j₂的位置，结果如下：

1) 点交换.将点j₁与点j₂互换，得

2) 点前向插入.将点j₁插入点j₂前，得

3) 点后向插入.将点j₁插入点j₂后，得

4) 点逆序.将点j₁与点j₂之间排列逆序(只考虑R₁与R₂中的客户点排列，其余线路中的客户点相对位置不变)，得

5) 点尾巴交换.将点j₁及之后的客户点与点j₂及之后的客户点全部互换(只考虑R₁与R₂内的客户点排列，其余线路中的客户点相对位置不变)，得

2.3 解的评价

本文设计接受部分不可行解的策略，让ATS算法在变换过程中接受部分违反载重和路长的新邻域解，以通过不可行解来过渡到更好的可行解，此举有利于算法跳出局部最优.记第k条线路的超载量与路长超出量分别为ε_k与δ_k，将ATS算法中解的总评价函数G设为式(12)，行驶费用评价函数F设为式(13).

(12)

式(12)中的P₁、P₂是定性概念，只表示优先级P₁≫P₂，即使用车辆数最少的可行解有绝对优先权^[4]，在迭代寻优过程中，每次都需要结合评价函数来挑选下一次迭代的最优解S^best与当前解S^now，约定S^best必须可行，而S^now则允许接受部分违反约束的不可行解.采用分层计算求解双目标. S^best的挑选规则如下：先在候选解集内挑选出车辆数最少的可行候选解构成解集A，然后再从集合A内挑选F值最小的解S^*，此S^*便是“最佳可行候选解”，结合前述的两级评价目标，若是S^*比原S^best更优，则将S^*设为新S^best与S^now；若S^*没有比S^best更优，则原S^best保持不变，另再挑选新S^now.新S^now的挑选规则如下：先从候选解集内挑选出满足K≥K_min的非禁忌解来构成解集B，若B≠Ø，则从集合B内挑选车辆数最少的解来构成解集C，再从集合C中挑选F值最小的解S^#，并将S^#设为新S^now；若发现B=Ø，则解禁满足K≥K_min的“最佳候选解”S^*#，并将S^*#设为新S^now.

(13)

式(13)中的Z′表示违反车辆装载能力Q和最长行驶时间L限制的惩罚值，取Z′为

(14)

式(14)中τ为自适应惩罚系数，通过实验取变动范围为τ∈[20，2 200]，τ的初值设为100，若接连有5次迭代的解不可行，则将其乘以2，若接连有5次迭代可行，则将其除以2，这样有利于引导ATS算法在不可行解与可行解之间进行交替搜索.

2.4 禁忌规则与终止条件

禁忌规则的设计是ATS算法的核心，其中禁忌长度对算法性能影响很大.禁忌的直接目的便是为了避开重复搜索，在合适的情况下，较大的禁忌长度常有利于防止循环搜索，较小的禁忌长度常有利于解的多样性，但若是长度选取不适应则难以获得期望的效果.从以往的VRP文[3-4]来看，禁忌长度的种类主要有固定值和随机值两大类，禁忌长度在5~16之间取值比较合理.为充分发挥固定值与随机值两类禁忌长度的隐性优势，及避免算法前期的重复搜索和增强算法中后期的随机多样性，本文特设计混合禁忌长度，禁忌长度的取值为：在迭代的前Nu₀步内取定值16，在Nu₀步以后每次都取5~16之间的随机整数，通过实验本文取Nu₀=500+15N.

本文将禁忌表设为l×3阶线性表，其中第一、二列用来存储邻域操作的组合点i与j，第三列则用来存储对应的禁忌长度值.当点i与j被选择进行操作后，其对应的候选解被选择为下次迭代的“当前解”时，就在禁忌表的对应位置填入禁忌长度，规定表内的禁忌对象每次迭代后都要将禁忌长度减1，直到降为0才可解禁.为了加速算法前期的搜索进程和避免后期的禁忌过度，禁忌表的长度l取值如下：在迭代的前Nu₀步内取N，在Nu₀步后则取16.

设每次迭代可生成Nu₁个候选解，候选解数目占邻域解总数的比例γ大小会影响到每次选到更好解的概率，候选解的个数选取应与问题规模N有关系，按照一定比例γ值来挑选候选解数目是一种思路^[4].本文邻域规模不小于5C_N²=5N(N-1)/2，邻域规模复杂度为关于N的二次方，随着N的增大也是个不小的数目.若取γ=5%，则当N=30时，5C_N²=2 175，Nu₁=108.75；当N=100时，5C_N²=24 750，Nu₁=1 237.5，点数从30~100只增加了70个，但需要计算的候选解个数却增多了1 128.75，随着N的增大，Nu₁会迅速变大，所需的存储空间与计算时间会大增，采用固定比例γ值来挑选候选解数量也不太合适.本文采用线性方式来设置候选解数目，并给予一定基数，这种设置能较好地适应不同规模问题的求解，对于中小规模问题可使Nu₁不会太小，对于大规模问题也能保证Nu₁不会因为N的增大而急剧膨胀，通过实验本文取Nu₁=50+N，当N变化时，候选解个数的变化量与问题规模点数的变化量是相同的，因此本文的线性设置方式比固定比例γ值设置会更合理.

文[20]在改进的人工蜂群算法(是一种蜂群禁忌混合算法)中利用禁忌表来存储局部极值，并采用了一种混沌序列重新初始化的策略来避免过度禁忌，获得了较好的效果.文[20]禁忌的是局部极值，本文禁忌的是邻域交换点，为了进一步避免禁忌过度，本文ATS算法吸收文[20]的重新初始化思想，再增设一个“禁忌表重新初始化”的破禁忌策略，即在迭代Nu₀步以后，每隔m次迭代就将禁忌表重新初始化，通过实验本文取m=50.

设计两个终止迭代的条件，只需满足任意一个便可终止：第一个为总迭代次数达到预设的上限值Nu₂；第二个为“最好解”连续保持不变的迭代次数达到预设的上限值Nu₃.为使Nu₂与Nu₃的取值能较好地适应不同规模问题的求解，又不随规模的增长而急剧膨胀，本文将其设为关于N的线性方式，本文取Nu₂=5 000+100N，Nu₃=2 000+15N.

2.5 算法描述

依据TS算法基本框架，ATS算法描述如下：

Step 1  初始化

Step 2  读入相关数据及参数值.

Step 3  随机生成初始解，并把此解取为S^best和S^now.

Step 4  While未满足终止条件do

Step 5  While候选解数目小于Nu₁ do

Step 6  在预先设5种邻域之间随机挑选一种变换；

Step 7  按规则对S^now进行邻域变换，并将新产生的邻域解当作候选解；

Step 8  End；

Step 9  若最佳可行候选解S^*比原S^best更优，则把S^*设定为新的S^best和S^now，否则将S^#取为新的S^now；若全部候选解被禁忌，则解禁S^*#，并把其设为新的S^now；

Step 10  更新禁忌表；

Step 11  End.

3 算法测试 3.1 算例描述

本文采用Solomn算例^[3]中C1类(含C101，C102，…，C109共计9个算例)进行算法性能测试，其中每个算例都包含1个配送中心和100(N=100)个客户点，各点的需求量、位置坐标、服务时长及期望时间窗等数据都已知. 9个算例的主要数据差异体现在各点的需求量与期望时间窗，能够较好地模拟连锁超市的经营需求变动情况，体现求解算法的寻优性能.本文以点间的欧氏距离代表点间的行驶时间，由式(1)可估算出C1类算例所需车辆数下限为10辆.

3.2 计算结果

为方便描述客户点时间窗的满足程度，本文定义一个“时间窗满足率”β，参数β代表了车辆到达客户点的时刻落在期望时间窗内的客户数百分比.采用Matlab 2014a进行编程，在LENOVO^®V3000，CUP为2.40 GHz，内存为4 GB的AMD笔记本上测试ATS算法.每个算例测试5次，每次采用随机方式生成初始解.求解结果如下.

总体来看，各算例求得的最好结果都为K=10，Z=828.94，β=100%.在车辆数方面，9个算例求得的车辆数都非常稳定，每次测试求得的车辆数都是10，ATS对车辆数的求解结果非常稳定，各算例求解的距离费用与时间窗满足率结果可参见表 1~2.从表 1可知，5次测试中Z值除C104、C107、C109含有部分超出828.94的次数之外，其余算例各次测试都稳定在828.94，而β值也只有C104、C109存在稍微偏离时间窗的结果. VRPTW属于NP-Hard问题，不管是从车辆数与距离值，还是时间窗的满足率来看，本文ATS在对大规模问题的求解中稳定性都是不错的.

3.3 对比分析

为进一步说明ATS算法的稳定性，采用文[2]来进行间接比较分析.文[2]设计了一种混合遗传算法(HGA)来求解VRPHTW，其相关求解结果如表 3.从表 1和表 3可知，HGA不仅最好结果劣于本文的ATS，而且其各算例在车辆数与距离值的稳定性能方面都要比ATS差很远.对比结果可以表明ATS拥有较好的稳定性.

本文采用VRPTW中的代表性文[3, 6, 12]的结果来进行最优解的性能比较，对比文[3]研究的是经典不拆分的VRPHTW，文[6]研究的是需求可单元化拆分的VRPHTW，文[12]研究的是需求依订单拆分的VRPSTW.其中，文[3]使用模拟退火算法(SA)与遗传算法(GA)进行测试，文[6]结合已有的经典启发式算法构建了质量较高的初始解，利用种群增量思想，设计了一个改进的分散搜索(scatter search，SS)算法，文[12]则结合依订单拆分特点采用一个禁忌搜索算法进行了求解.对比文献都属于智能算法范畴，除了文[12]的C1系列只测试了7个算例外，其余文献都测试了9个算例，对比文献结果可同本文进行间接比较.由于对比文[3, 6, 12]只给出了各算法求解的最好结果，并未对各算例的求解结果进行详细的稳定性分析，因此本文也选用ATS的最好结果进行对比.

在求解结果方面，表 4给出了各算法最好解的距离费用(都为满足β=100%)，只有当未降到最少车辆数10的时候才给出具体的车辆数.从表 4可知，本文的测试结果已达到或接近目前世界的VRPHTW已知最好结果(P_best)，ATS的求解精度明显要比SA、GA、SS及TS的好. ATS在车辆数方面，比SA、GA、SS及TS分别节省1、1、0、0辆；在行驶距离(行驶时间)方面，都要比SA、GA、SS及TS的好或相等，比SA、GA、SS及TS算例的平均距离费用分别节省129.63、31.68、6.04及4.22，节省比例分别达15.64%、3.82%、0.73%及0.51%，随着连锁超市业务量的增长，这将是一个可观的费用节省.

在求解时间方面，由于文[3, 6]中没有给出各算例的求解时间，因此本文只与文[12]中TS算法作比较，具体可见表 5.从表 5可知，TS各算例的求解时间都要比ATS长很多，平均算例的求解时间为ATS的3.54倍，在求解时间效率上明显不如本文的ATS.

与文献的对比分析，进一步说明了ATS算法的有效性，同时也表明，若能在禁忌搜索算法中加入各种寻优性能提升策略，增强算法的鲁棒性，当算法能够向全局最优解逼近时，随机生成初始解对最终优化解的质量已无多大影响.

4 结论

软时间窗VRP比硬时间窗VRP能节省配送成本，可增强配送系统的柔性，带工作时间和软时间窗的VRP在物流配送实践中存在广泛应用价值.本文为城市连锁超市商品配送构建了相应的双目标数学模型，并设计了一个自适应禁忌搜索算法，文献对比表明，本文设计的ATS算法的稳定性和寻优能力都要强于对比文献中的SA、GA、HGA及TS算法.

从本文的研究结果可知，在算法中采用自适应惩罚策略，接受部分违反约束的不可行解能增强邻域搜索的柔性，有利于引导算法过渡到更好的可行解.另外，在禁忌搜索算法中设计随机禁忌长度，多邻域结构体及禁忌表重新初始化等策略则有助于提升算法的鲁棒性，增强全局寻优能力.

本文对纯送货的静态VRPSTWWT类型进行了研究，而逆向物流与路网时变性的动态VRP也是城市连锁超市配送实践中面临的大难题.因此，后续我们将对同时取送货的动态VRPSTWWT类型进行更深入的研究，并进一步优化ATS的寻优性能.