0 引言

随着互联网技术的发展，电子商务业务^[1]获得了迅猛增长，电子商务因其迅速的时空反应、逼真的多媒体展示及交互式的销售渠道而大大降低了交易成本，现代电子商务交易^[2]也因其操作快捷与反应迅速而广受青睐.在国家电商扶贫政策^[3]的支持下，一系列的农产品电商企业应运而生，极大地方便了农产品的流通，促进了农村经济^[4]的发展.农产品电商^[5]的发展也给农村物流来带了前所未有的压力，落后的物流配送能力已成为制约农产品电商发展的瓶颈.

现代农产品电商企业的崛起，加速了农产品的线上交易，也提升了客户对物流配送服务质量的期待，而一般的中小型农产品电商企业自身难以实现高质量的物流服务.因此，中小型电商企业应将物流服务业务委托与专业的第三方物流企业^[6]，与物流企业实施战略合作，实现信息对称，提升物流响应速度，增强物流配送^[7]能力.而车辆路径问题^[8](vehicle routing problem, VRP)是物流配送的核心环节，其在农产品物流配送^[9]领域存在广泛应用价值，因此，对农产品电商物流配送车辆路径优化进行研究显得尤为重要.

农产品电商配送VRP通常具有一定的时效性期望，可归结为带时间窗VRP^[11](VRP with time windows, VRPTW).以往的农产品配送VRP研究^[11-12]中，为了实现准时制配送(just in time distribution, JITD)，常采用硬时间窗约束，即每个配送客户(客户企业)的期望时间窗不允许违反.硬时间窗VRP^[12](VRP with hard time windows，VRPHTW)模型虽在短期内有助于提升客户满意度，抢占客户市场资源，但刚性过强，常会造成车辆装载率低下和迂回行驶，使得整个配送系统的成本过高，不利于供应链上各节点企业的可持续发展.

在物流配送实践中，农产品客户(指农产品订购企业)提出的时间窗通常也只是一个大致期望，发生一定程度的时间窗偏离量并不会对客户造成多大影响(当然有可能对客户的收货带来不方便，产生一定机会成本).因此，本文约定在农产品电商配送中将以往的硬时间窗约束松弛为软时间窗，设计一个软时间VRP(VRP with soft time windows，VRPSTW)模型，并且规定若时间窗发生偏离则施行惩罚，即VRPSTW中可能产生一定量的时间窗偏离费用.农产品具有易腐变质性，由于时间窗可发生偏离，也容易形成过长的车辆线路，造成线路末端部分客户点的农产品发生质变.因此，本文再为车辆线路增设一个保证农产品质量的最长工作时间L_max，即每辆车从配送中心出发送货后必须在工作时间窗[0, L_max]内返回原出发点，由此可形成一个带工作时间和软时间窗的VRP(VRP with soft time windows and working time，VRPSTWWT).

VRP属于NP-Hard问题^[13]，VRPSTWWT比基本VRP更复杂，也是NP-Hard问题，相比硬时间窗约束，软时间窗有助于提升算法邻域搜索的柔性，增强启发算法的全局寻优能力.一般的精确算法难以求解大规模配送VRPSTWWT，需借助智能算法才能有效求解.从求解VRP的智能算法^[7]如禁忌搜索算法(tabu search algorithm, TSA)、遗传算法(genetic algorithm, GA)、蚁群优化算法(ant colony optimization, ACO)及粒子群优化算法(particle swarm optimization, PSO)等来看，TSA是一种较为高效的智能算法.

从已有VRP文献^[8-36]来看，以需求不可拆分的传统VRP类型为主，需求可拆分VRP(VRP with split deliveries, VRPSD)研究相对较少.在传统VRP类型^[8-17]中，为了降低算法对大规模配送问题的求解难度，常假设各客户的需求量不大于车辆载重，约定各农产品客户的需求不可拆分，即单个农产品客户的需求只能由一辆车一次送达.但已有的VRPSD类型^[18-24]研究表明，将传统VRP中需求不可拆分的条件进行松弛，允许客户需求进行拆分由多辆车分批送达，会有助于提高车辆装载率，减少车辆数目，缩短行驶距离，降低配送成本.如文[18]研究了一种带最小分割量的VRPSD；文[19]研究了一种需求离散拆分和带硬时间窗的VRPSD，并采用一个分支定价算法成功求解了部分中大规模的VRPTW基准算例；文[20]对每次拆分量的大小进行控制，研究了一种最小—最大拆分量约束的VRPSD；文[21]研究了一种车辆满载的开放式VRPSD，规定除最后一辆车外其余车辆都必须保证满载；文[22-24]研究了一类需求依订单拆分的VRPSD，其约定客户的需求量可以依订单来离散拆分，但是单个订单量不可再拆分.以往的VRPSD相关类型^[18-24]研究都有其对应的理论意义与应用环境，不过在农产品电商物流配货实践中，为了方便装货与计量，常会将客户订单的需求量按照箱、袋等进行单元化打包装车.因此，电商客户的需求量在装配过程中可按计量单位(如箱、袋等计量单位)进行单元化拆分，研究需求单元拆分VRP(VRP with split deliveries by unit, VRPSDU)具有较高的实践价值与理论意义.

VRPSTWWT和VRPSDU都是基本VRP的拓展类型，其求解难度比基本VRP更大.构建符合实践需求的车辆路径问题模型，设计高效的智能优化算法已成为农产品电商物流配送亟待解决的难题.综合前述分析，本文将在传统VRPTW和已有VRPSD相关类型的基础上，结合客户点的需求单元拆分、软时间窗和工作时间约束及车辆装载限制，构建一个需求单元化拆分的VRPSTWWT(VRPSTWWT with split deliveries by unit, VRPSTWWTSDU)模型，并设计一个自适应TSA(adaptive tabu search algorithm, ATSA)求解.

1 问题描述与模型构建

为了方便描述，对相关符号予以说明：物流配送网络节点集为A，A={0, 1, …, N}，其中配送中心为点0，对应的需求量为0.各农产品客户点为i，i∈A/{0}，客户点i的单元需求量为d_i，服务时间为s_i，期望时间窗为[e_i, h_i]，约定各点的时间窗可松弛为软时间窗约束，配送策略为提前等待，推迟惩罚. x_i^k∈{0, 1}，若车辆k配送了点i的需求量，取值为1，否则为0.设y_ij^k∈{0, 1}，若车辆k拜访完点i后便直接使向点j，取值为1，否则取0.车辆k的实际线路工作时间为L_k.记配送系统需要的车辆数为K+K′，车辆的单元装载量都为V，其中K′代表了满载直达配送车辆数，K代表了需要使用的剩余车辆数.记剩余使用车辆集为B，B={1, 2, …, k, …, K}，车辆k(k∈B)配送客户点i的剩余需求单元量为d′_i^k.车辆从t₀=0时刻出发，到达点i的时刻为t_i.本文约定d_i、d′_i^k与V都为整型数据.

本文研究的VRPSTWSDU是指在满足车辆单元装载量V、各点i的软时间窗及需求单元拆分等条件下，合理安排同车型的车辆k从物流配送中心点0出发至各点i之间的闭合式线路行驶顺序，并使配送总成本最小化.本文将客户的配送需求按照统一规格进行单元化装载，认为每一个单元的量为1，即文中d_i表示客户点i需要d_i个单元的量，本文的数学模型为

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

结合前述分析，约束式(1)~约束式(20)可构成本文的双目标规划数学模型.具体说明：

本文配送的总成本最小化包含2级目标：第1级目标为最小化车辆数K，第2级目标为最小化行驶时间Z₁、等待时间Z₂、推迟时间Z₃及服务时间Z₄对应的费用之和Z，具体如式(1)~式(6)所示.在配送VRP^[32]实践中，一般认为，多使用一辆车带来的费用会远多于行驶费用的减少，这是因为专用电商配送车辆通常较为贵重，而且多使用一辆车就需要多支付一位司机的用工费用、油耗费用及相应的环保费用等.因此，本文约定第1级目标K相比第2级目标Z具有绝对优先权，即可行解中K值越小越好.

以往的VRP文献中^[32]，由于约定单个客户的需求量不可拆分，常假设每个客户点的需求量都不大于车辆载重，但在大规模配送实践中，也会存在个别大客户其需求量超出车辆装载限制的情况，因此，本文把客户需求超出车辆装载能力的情况也一并纳入考虑.当点i的需求量d_i大于车辆装载限制V时，先采用满载直达配送策略，直到点i的剩余需求量d′_i不大于V.记点i需要的满载直达配送车辆数为ω_i，则应有车辆的装载约束如式(7)~式(11)所示.由于以上的K′辆满载直达配送的车辆线路是固定不变的，因此在算法迭代求解前先把这些车辆对应的服务需求量减去，即算法迭代过程中只需要考虑剩余需求量d′_i的分配情况.式(12)为车辆需满足的线路工作时间限制.

结合d′_i与V可对所需要的车辆数下限¹K_min进行估计，取值如式(13)，其中代表向下取整数，不满足式(13)的配送方案肯定是一种劣质的不可行解.另外，物流企业结合配送实践情况，也可人为的替剩余的非满足直达配送需求规定一个车辆数下限²K_min，则实际需要的剩余车辆数K的下限K_min应满足式(14).

假设点之间的行驶速度不变，记点i、j之间的直达行驶时间为t_ij，如果同一辆车在拜访完点i之后便直接驶向点j，则应满足式(15).约定客户点j的需求量可单元拆分由多辆车共同送达，则点j至少应有1辆车拜访，即应满足式(16).约定全部车辆从配送中心出发并返回原出发点，则应有式(17)~式(18).中间客户点a的进出车辆流平衡约束如式(19)所示.车辆线路的子回路消去条件如式(20)所示.

2 ATSA设计

VRPSTWSDU属于一类NP-Hard问题，精确算法的求解能力有限，本文采用智能禁忌搜索算法进行求解. TSA作为一种模拟人类智能思维的智能启发式算法，可利用短期禁忌表对已搜索过的地方实施禁忌，避免迂回搜索，其邻域搜索功能很强.夏扬坤和符卓等对禁忌搜索算法进行了重点研究^{[22-25, 32]}，他们指出TSA具有简单性、精确性、适应性、易操作性等优点，从已有VRP文献^{[7, 22-25, 32]}来看，TSA确实是一种求解VRP的高效智能算法.本文将在TSA中增设多种改进策略，并将自适应惩罚机制和多邻域搜索策略嵌入TSA中，设计一个改进的ATSA，以增强TSA的全局寻优能力.

为了方便算法描述，定义相关符号：η_k为第k条车辆线路；S为问题的1个解，S=(η₁, ..., η_k, ..., η_K)；S^initial为初始解；S^neighbor为邻域操作生成的邻域解；S^candi为从邻域解中挑选出的候选解，可构建候选解集C，S^candi∈C；^#S^candi为最佳的候选解，^#S^candi∈C；S^non-tabu为非禁忌候选解，可构建非禁忌候选解集D，S^non-tabu∈D，；^#S^non-tabu为最佳的非禁忌候选解，^#S^non-tabu∈D；S^feasible为可行候选解，可构建可行候选解集E，S^feasible∈E，；^*S^feasible为最佳的可行候选解，^*S^feasible∈E；S^now为当前解；S^best为当前的最好解.

2.1 解的编码

以往的VRP文献中，虽然有些涉及了需求可按计量单位连续拆分思想，但直接采用需求单元化拆分编码的较少^[35].由于客户点i的需求量d′_i可任意单元化拆分，则点i的需求也可看成由d′_i个需求量为单位1的单元构成，因此本文设计一种双行编码来表示一个解S，第1行代表节点编号顺序，第2行代表对应的单元量.其中第1行紧邻的两个0及之间的数字代表一条车辆线路(有多个数字的只保留最前面的一个).如图 1中给出了解S的前两条线路编码，对应的线路为η₁=(0326740)、η₂=(041580)，从中可看出客户点4被依单元拆分配送，进入线路η₁的单元有1个，进入线路η₂的单元有2个.

2.2 可行初始解的构造

由于本文允许单个客户点的需求量d_i超出车辆载重V，因此需考虑2种情形来生成初始可行解.

情形1   当各点的需求量都未超出车辆载重限制时，设计一个“最近0”启发式方法来生成可行“初始解”且初始解不考虑拆分，采用式(2)的软时间窗惩罚机制计算行驶费用Z，但其它约束必须满足. “最近0”启发式方法的具体操作为：先结合各点(1~N)到配送中心点0的距离对各点进行升序，生成一个自然数排列，然后在符合车辆载重V、最长工作时间L_max约束下，依照此排列将各客户点编号按序加入车辆行驶线路中，当违反约束式(11)~式(12)时便重新开启一条新的车辆线路.

情形2  当存在客户点的需求量大于车辆载重时，先按照式(7)~式(10)的方式处理，即先对这些超载的客户点进行“满载直达配送”，直到剩余需求量d′_i不大于V，之后的操作方式与情形1的相同.

本文约定对于一开始便进行“满足直达配送”的K′条线路在迭代寻优过程中固定不变，即已进行满载直达配送的客户点i所对应的满载需求量ω_i·V可直接从物流配送网络中分离出来.

2.3 多邻域搜索设计

TSA具有较强的邻域搜索功能，在迭代过程中，对当前解S^now施行邻域变换可生成新的邻域解S^neighbor.本文约定生成S^neighbor的数目上限为p，取p=20+N.本文设计一个多邻域结构体，嵌入多种邻域交换算子，并采用随机邻域挑选策略.

在每次邻域变换前，先挑选出两条相异的线路排列R₁和R₂，然后在R₁和R₂内采用随机挑选方式各选择一个客户点的单元位置来进行邻域操作，在排列的第1行遇多个0相邻则只保留一个，并对同一线路内的客户点施行合并操作，即将相同线路内的客户点的单元位置并排到一起. Fu等^[32]在研究不可拆分的传统开放式VRP时采用了多邻域搜索机制，测试效果良好，本文借用其多邻域搜索思想，采用5种邻域算子进行操作，具体为：1)点交换；2)点前向插入；3)点逆序；4)单元逆序；5)单元尾巴交换.

2.4 优化解的挑选

以往的VRP文献为了降低求解难度，常采用加权方式将多目标转化为单目标.多目标求解是现代优化理论研究的热点与难点，本文采用分层方式计算双目标函数，结合前述双目标，取优化解的总评价函数G为式(21)，其中的P₁与P₂只是一个定性概念，只表示挑选优化解当前解S^now和最优解S^best时的优先级，即第1级目标K值最小化相对于第2级目标F值有绝对的优先权^[32].本文采用接受部分不可行解的策略，以期待通过不可行解来过渡到更好的可行解邻域内，式(22)中的Z′代表了配送系统违反车辆载重和最长工作时间限制的惩罚费用；式(23)中的δ_k与ψ_k分别代表车辆k的超载量与工作时间超出量，λ为一个自适应惩罚系数，λ的取值可参见后续分析.

(21)

(22)

(23)

(24)

(25)

式(22)中的Z′代表了对S^now的扰动情况，一般可认为Z′越大在迭代过程中对S^now的扰动越厉害，而这种扰动也会进一步传递给S^best，即Z′越大也会越有利于新S^best偏离原S^best的邻域.一般来说，当S^best连续多次迭代都没有发生变化时，可认为是当前解所在的邻域内已难以找到更好解，因此算法需要尽可能地帮助新邻域解跳出此当前解的邻域.那么，对当前解施行更大惩罚，接受部分不可行解，增大其评价函数F对应的Z′值，可助力其对应的“邻域解”快速跳出此S^now的邻域.同理，当S^best在迭代中常发生变化时，可认为S^now所在的邻域内还可能存在更好解，因此算法需要尽可能的减少对此S^now的扰动，即让算法在此S^now所在的邻域内进行更充分的搜索.那么，对此S^now减小惩罚，减小其评价函数F对应的Z′值会有助于对当前的邻域进行更充分的搜索.

结合上述分析，本文设计一种新的自适应惩罚机制来过渡到更好解的邻域，式(23)中的λ∈[20, 1000]，初始值为60，当超出范围时则令λ=20.令θ₁、θ₂为整型计数变量，取值范围为θ₁, θ₂∈[0, 12]，初始值都为0，当超出范围时则直接令θ₁, θ₂=0.在每次迭代完后，若原S^best没有发生变化，则令θ₁=θ₁+1，否则令θ₂=θ₂+1.每当θ₁=12时，让λ乘以2，每当θ₂=12时，便让λ除以2.

在禁忌搜索算法寻优过程中，有两个解的挑选策略对优化效果影响巨大，此两个解便是S^best和S^now的ATSA约定，在迭代寻优中S^best必须是可行解，而S^now则可以违反约束式(11)和约束式(12)，并结合自适应惩罚机制来挑选S^now.

本文采用分层方式计算双目标，依次考虑比较两级评价指标K、F.每次迭代当新候选解集生成后，先挑选出全部可行候选解来构建可行候选解集E.最佳可行候选解^*S^feasible的挑选方式如式为：对解集E中的解按照车辆数K进行升序排，挑选出其中K值最小的解来构成一个新解集；之后，对新解集中的解按照F值进行升序排，挑选出其中F值最小的首个候选解作为^*S^feasible.

若^*S^feasible比原S^best更优，即当满足K(^*S^feasible) < K(S^best)或K(^*S^feasible)=K(S^best)，F(^*S^feasible) < F(S^best)，则采用“藐视准则”，即不考虑禁忌情况，直接将此^*S^feasible设为新的S^now和S^best.

若^*S^feasible未优于原S^best，即当有K(^*S^feasible)>K(S^best)或K(^*S^feasible)=K(S^best)，F(^*S^feasible)≥F(S^best)，则S^best保持不变，只需挑选新的S^now，也是依次比较两级评价指标K与F.由于部分候选解可能被禁忌，因此这里S^now分两种情况进行挑选：先挑选出非禁忌候选解S^non-tabu来构建非禁忌候选解集D，若集合，则挑选出最佳非禁忌候选解^#S^non-tabu，并将其设定为新S^now；若集合，即全部S^candi都被禁忌，则挑选出最佳候选解^#S^candi(^#S^candi∈C)，并释放此^#S^candi，同时将此^#S^candi设为新S^now.这里^#S^non-tabu、^#S^candi的挑选方式与^*S^feasible的挑选类似，因此不再累述.

2.5 线性禁忌表设计

禁忌表设计是TSA的核心，其中禁忌表的结构、禁忌对象及禁忌长度对TSA的寻优能力影响较大.以往VRP文献^{[22-24, 32]}常采用N×N阶的方阵式禁忌表，禁忌对象则为邻域交换中的客户点对(i, j)，禁忌长度也常取为固定值.此种禁忌表设计方式简单易行，但禁忌容量过大，在迭代前期能加速寻优，但在中后期则特别容易禁忌过度，会降低算法的全局寻优能力.

为了弥补以往TSA^{[22-24, 32]}容易禁忌过度的不足，ATSA设计一个r×3阶的线性禁忌表T_r×3，并采用固定值和随机值的混合类型来刻画禁忌长度ε.禁忌表的第1、2列用于存储所选出的“当前解”所对应的邻域交换点对(i, j)，第3列用于存储ε值.其中，r值在迭代的前u₀步内取为N，其后则取为16，本文取u₀=500+10N.为了充分发挥固定值和随机值两种类型的禁忌长度优势，ATSA设计混合禁忌长度，ε值在迭代的前u₀步内取固定值16，其后则每次都取5~16之间的随机整数值.每迭代一次，令T_r×3内的第3列元素值都减去1，规定禁忌对象直到ε≤0才能够释放.另外，增设一定的重新初始化策略有助于新邻域解的丰富性^[22]，ATSA再增设一个“禁忌表重新初始化”策略，规定在迭代u₀步之后，每隔m次迭代，就将禁忌表T_r×3重新初始化为全0矩阵，取m=40.

2.6 算法迭代的终止条件

ATSA采用2个终止条件，只需达到任意一个便可终止迭代：其一是总的迭代次数M_u1达到预设的上限值u₁；其二是S^best连续保持不变的迭代次数M_u2达到预设的上限值u₂.以往的VRP文献^{[24, 32]}常将u₁与u₂取为固定数值，为使u₁和u₂能适应不同规模大小的求解，又不会随着规模的增大而过度偏大，本文在此特将其取为关于规模N的线性函数，取u₁=4000+60N，u₂=2500+5N.

2.7 算法复杂度分析

ATSA的主要计算时间耗费在迭代与邻域变换的候选解生成上.假设总的迭代次数为ζ₁，每次迭代生成候选解的数量为ζ₂，问题的规模为N.在单次迭代中，计算时间最复杂的部分为候选解的生成过程(含邻域变换)，其计算复杂度约为ζ₂·O(N²)，则总的算法复杂度约为ζ₁·ζ₂·O(N²).可见，本文ATSA是与“问题规模”N的平方成正比的智能算法，其与一般的经典启发式算法处于同一个量级上，算法复杂度方面较为合理.

2.8 算法流程

本文ATSA的基本流程可参见图 2.

3 仿真测试 3.1 算例描述

文[34]在研究不可拆分的VRPSTW类型中，以粒子群算法为基础，设计了一个改进的伊藤算法(improved ITO algorithm, IITO)，并与文[33]的标准伊藤算法(ITO algorithm, ITO)进行了比较分析，验证了改进ITO(IITO)算法的改进效果.文[33-34]都采用Solomon算例^[34]中的R1.50类(含R101~R112共计12个算例)进行了算法测试.为了方便进行间接对比分析，本文也采用R1.50类算例来测试ATSA，并按照文[34]的总费用方式来计算出本文对应的最终总配送费用G_c，具体如式(26)所示，其中ρ_i(i∈{0, 1, 2, 3, 4})为对应的单位费用.本文单位费用的取值与文[25]保持一致，取ρ₀=500，ρ₁=40，ρ₂=ρ₃=10，ρ₄=5.

(26)

R1.50类算例都含有1个配送中心与50个客户点，车辆的载重限制为200，每个点的相关信息皆已知.当允许R1.50类算例中各点的硬时间窗松弛为软时间窗，允许需求进行单元拆分配送时便可作为本文需要的VRPSTWWTSDU类型算例.另外，结合文[34]中IITO算法求得的最好车辆数结果，本文给ATSA划定一个车辆数下界²K_min，约定²K_min的值可比算法IITO求得的最好车辆数少1.

3.2 计算结果与对比分析

本文采用Matlab2014a编程，在LENOVO^RV3000，CUP为2.40 GHz，内存为4GB的AMD笔记本上实现ATSA.对每个算例测试5次，具体求解结果如下.

表 1给出了总配送费用G_c的最好值best.G_c、平均值avg.G_c、最差值worst.G_c、极差值dev.G_c(极差表示最差值与最好值的偏离量)及极差百分比dev.G_c%(表示极差值相对于最好值的百分比).从表 1可知，全部算例G_c的偏差百分比控制在1.97%~8.16%，均值偏差为4.50%，而且除了R105/R109/R112这3个算例外，其余算例的偏差值都控制在了5.00%以内.另外，ATSA求得的车辆数结果非常稳定，车辆数在每次的求解结果都一样.结合以往大规模配送VRP稳定性^[11]研究可知，本文ATSA的算法稳定性是很好的.

文[34]在测试IITO和ITO算法时，并未给出全部算例的总配送费用值，其文中只对R103的费用进行了详细分析，因此本文在G_c方面也以R103进行对比分析，具体结果如表 2.从表 2可见，本文设计的ATSA在最好值、平均值、最差值三个指标方面的优化效果明显要好于对比算法IITO与ITO，相比IITO的改进比例在10%以上，相比ITO的改进比例在20%以上，这在大规模配送中可以节省巨大费用.另外，本文的dev.G_c值相比IITO略有改进，相比ITO改进达33.33%，可见，ATSA与IITO的算法稳定性要明显强于ITO，ATSA虽然优化能力明显强于IITO，但在算法稳定性方面与IITO基本一致.

文[34]在求解VRPSTW时虽未给出各算例的总配送费用，不过其采用车辆数(K)与距离值(Z₁)同目前VRPHTW已知的最好结果(P.best)进行了对比分析.为了进一步体现ATSA的优化能力，本文也与文[34]一样，采用最好解的结果进行间接对比，具体如表 3和表 4所示.

本文采用的是动态车辆数下降求解方式，表 3给出了各算法最好解的车辆数.从表 3可知，ATSA在车辆数下降方面要明显强于对比文献在求解VRPSTW时的算法，相比算法IITO与ITO，平均算例的节省比例分别达8.05%与12.64%，可见节省比例很大.另外，ATSA除了算例R106比VRPHTW已知的最好结果(P.best)多2辆车外，其余11个算例的车辆数都要等于或少于最好结果，ATSA相对于已知最好结果的平均算例节省比例达6.90%，可见ATSA具有较强的车辆数下降能力.

表 4给出了各算法最好解的距离值.从表 4可知，ATSA在距离值下降方面明显优于对比文[34]的算法，全部算例的结果都要比IITO和ITO的好，平均算例节省比例分别达10.53%与14.96%，可见节省程度很大.另外，在ATSA的距离值中除了5个算例略差于目前已有的最好结果(P.best)外，其余7个算例都获得了较大程度的节省，平均算例的节省比例达3.56%.

综合以上分析可知，无论从算法的优化能力还是稳定性能来看，本文的ATSA都要强于对比文献算法，文献对比可以表明ATSA的有效性.

3.3 拆分配送举例

本文以算例R110的最好结果来对拆分配送进行举例说明.计算结果显示，R110共计需要6辆车，其总配送费用为36 209，距离值为718，其中有两个客户点(点27与点31)被拆分配送，具体配送方案如表 5所示.从表 5可知，线路5配送了客户点27的7个单元量，线路7配送了客户点27的9个单元量.结合表 4可知，由于客户需求可单元化拆分，相比IITO和ITO算法，ATSA在车辆数与距离值方面获得了较大程度的节省，即ATSA比对比文献算法更能节省配送成本.从计算结果来看，当客户点的需求量不超出车辆装载能力时，其优化解中对应的客户点至多被拆分一次.

4 结论

需求单元化拆分的VRPSTWWT在物流配送领域存在广泛应用价值.从需求单元拆分VRP解的结果来看，每个客户点被拆分的次数应为ω_i或ω_i+1，即当客户点的需求量不超出车辆装载能力时，其最好解中对应的客户点至多被拆分一次.

本文将以往客户点的硬时间窗约束松弛，软时间窗VRP比硬时间窗VRP更灵活，有利于增强配送系统的弹性和禁忌搜索算法的柔性.将线路的“最长工作时间”纳入VRPSTW模型中，有助于保持农产品的生鲜质量.在VRPSTWWT模型中，允许客户需求进行单元化拆分配送可提高车辆装载率，减少车辆使用数目，缩短行驶距离，降低总配送成本，有利于企业的可持续发展.

需求单元化拆分VRP属于NP-hard难题，VRP的求解算法一直是组合优化学界的热点和难点，本文设计的自适应禁忌搜索算法在求解VRPSTWWTSDU类型时表现了良好的寻优性能.文献对比表明，本文设计的ATSA的算法稳定性与寻优能力都要强于改进伊藤算法(IITO)和标准伊藤算法(ITO).从本文的研究可知，在禁忌搜索算法中嵌入自适应惩罚机制，采用多邻域结构体，设计一定的重新初始化策略可增强算法的全局寻优能力.

从算法复杂度方面来看，本文设计的ATSA与一般的经典启发式算法在同一个量级上，算法复杂度较为合理.另外，ATSA的通用性较强，其对大规模配送车辆路径优化具有较强的适应能力.在实践中，只需将具体问题的约束纳入ATSA的算法框架内进行修改，便可用于解决其它类型的VRP.

本文对纯送货和需求单元拆分的静态VRPSTWWT类型进行了研究，而逆向物流与路网实时变化的动态VRP也是物流配送实践中的大难题.因此，后续将对同时取送货的动态VRPSTWWTSDU类型进行更深入的研究，并进一步提升ATSA的寻优性能.