电商退换货车辆路径问题及蚁群算法研究

张庆华，吕小丹

北京科技大学 机械工程学院，北京 100083

1 引言

各大电商平台为了提高服务质量以抢占市场份额，提出了在消费者要求退换货后提供上门取件服务的措施。随着相关法律的进一步完善，电子商务中的退换货现象已经成为一种常态化的存在。物流企业必须在发展正向物流的同时重视逆向物流问题，因此研究此类问题具有重要实际意义。

逆向物流的概念较早时间就已经被提出，但是电子商务中逆向物流问题的研究大都集中于逆向物流网络优化设计[1]、应用价值[2]等问题的研究中，关于整合正、逆向物流的车辆路径问题的研究相对较少。罗耀波等[3]建立了带退货和软时间窗的多仓库选址-路径数学模型，设计了自适应混合遗传算法，并以自己设计的10个客户规模的测试数据进行测试。冯芳媛等[4]研究了一个带退货的多配送站点车辆路径优化问题，设计了禁忌搜索算法进行求解，并以自己设计的17个客户规模的测试数据进行测试。邢永峰[5]建立静态条件下回程带货车辆路径优化模型，设计了自适应算法对模型进行求解，并结合算例对模型进行了仿真实验分析。可以看出，在电子商务中关于整合正逆向物流的研究中，考虑时间窗因素的较少，并且测试数据大都是自行设计的较小规模的测试数据，没有同其他算法进行对比验证。

在本文研究的电子商务环境下的带退换货的车辆路径问题中，客户根据需求可分为：只需要提供配送服务的客户，只需要提供取货服务的客户，既需要提供配送服务也需要提供取货服务的客户。其中，只具备单一需求的客户可以看成该客户的其他需求为0，实际上这是对同时取送货问题的拓展。在现有文献的研究中，虽然有大量的文献研究VRPSPD（Vehicle Routing Problem with Simultaneous Pickup-Delivery）问 题 和 VRPTW（Vehicle Routing Problem with Time Windows）问题，但是关于VRPSPDTW（Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows）的研究国内外却很少。Wang等[6]于2012年在关于VRPTW问题的Solomon算例的基础上，提出了求解VRPSPDTW问题的唯一测试数据集，并且用遗传算法对这个数据集进行了求解。在此之前，虽然有一些学者对此类问题进行了相关研究，但是缺乏可靠的算例验证[7-9]。之后，文献[10]和文献[11]分别提出了一种并行的模拟退火算法和离散布谷鸟算法来求解该问题，并采取标准算例进行实验。其他算法在该问题的求解上还有很大的研究空间。

蚁群算法由于其自身性能上的鲁棒性和搜索较好解的能力，近年来被广泛应用在各种领域，但是由于初始信息素的匮乏，蚁群算法一般需要较长的搜索时间，同时容易陷入局部最优。凌海峰等[12]依据混沌理论的特点来调整蚁群算法参数，并且利用2-opt算法对最优解进行优化。何小锋等[13]针对蚁群算法在求解VRPTW问题时易陷入局部最优和收敛速度慢的问题，结合量子计算提出一种求解VRPTW的量子蚁群算法。李琳等[14]设计了一种改进的蚁群算法，在状态转移规则中引入时间窗跨度与服务等待时间因素。本文基于基本蚁群算法，在状态转移规则和信息素的更新规则上对蚁群算法进行了一些改进，同时将其和变邻域搜索算法相结合，提升算法的性能。最后通过与其他算法的对比和标准算例实验来验证所提算法的性能，并且结合企业真实数据来验证其有效性。

2 带软时间窗和退换货的车辆路径问题

2.1 问题描述

为了更好地界定所要研究的问题，方便模型建立和求解，需要对实际情况进行一些简化和抽象，提出以下假设：

（1）研究从一个配送中心向多个客户配送和取走商品的问题，客户可能同时存在取货送货两种需求，也可能只存在一种需求。配送中心和客户居住位置一定，配送中心产品可以满足客户配送需求。

（2）车辆均从配送中心出发并且需要返回配送中心，每辆车只经过各客户一次，每个客户只允许一辆配送车辆访问一次，每个客户需求必须满足。

（3）在每个客户处，车辆先卸货，然后再装货。

（4）模型的目标函数是配送总成本最低，配送成本包括车辆固定成本（轮胎损耗费用、保养费用、折旧费用等）、行驶成本、等待成本和延迟成本。

基于以上假设，本文所研究的带软时间窗的电商退换货车辆路径问题可以描述为：某配送中心向一定客户提供配送货物和取走退换货物的服务，已知配送中心和各个客户之间的距离和车辆行驶时间，车辆的最大承载能力以及在每个客户提供服务的时间，车辆的固定动用成本和单位距离行驶成本。车辆可以在客户所要求的时间窗范围外对客户提供服务，但是违背时间窗会得到一定惩罚，车辆遵守“早到等待”原则，即车辆若早于客户所要求的最早开始服务时间到达，需要等待至最早开始服务时间再进行服务。要求合理安排车辆路径，在满足车辆载重和客户时间窗要求的前提下，使所有客户的需求量均被满足，并且使车辆配送成本最小。

2.2 符号含义

K：配送中心拥有的车辆的集合；

N：需要配送的客户集合；

V：配送网络中所有的节点集合，V=N⋃{}0；

dij：车辆从客户i到客户 j之间的行驶距离；

tij：车辆从客户i到客户 j之间的行驶时间；

Q：车辆的最大载重限制；

pi：客户i的退货收集需求量；

qi：客户i的配送需求量；

Wijk：车辆k从客户i到客户 j的途中车上装载的已收集的货物总量；

Zijk：车辆k从客户i到客户 j的途中车上装载的还未配送的货物总量；

Tik：车辆k到达客户i的时间；

[ETi,LTi]：客户i要求的时间窗，ETi表示最早开始服务时间，LTi表示最晚开始服务时间；

yik：车辆k是否参与客户i的配送任务，yik=1表示车辆k参与客户i的配送任务，yik=0表示车辆k不参与客户i的配送任务；

xijk：车辆k是否由客户i驶向客户 j，xijk=1表示从客户i到客户 j的配送任务由车辆k完成，xijk=0表示从客户i到客户 j的配送任务不是由车辆k完成；

sti：在客户i的服务时间；

C1：动用一辆车的固定费用；

C2：车辆行驶单位距离的成本；

e1：车辆的单位等待成本；

e2：车辆的单位迟到成本。

其中，i,j∈V，k∈K。

2.3 模型建立

3 混合变邻域改进蚁群算法

3.1 初始解的产生

本文在求解带软时间窗的电商退换货车辆路径问题时采取整数编码的方式，用0表示配送中心，1～n表示客户编号，1～k表示车辆编号，每个解的路径采用一个n+k+1的整型向量表示，每个解包含k条子路径，每条子路径表示一辆车的行驶回路，编码结构如图1所示。

图1 编码结构

蚁群算法由于在初期信息素匮乏，会导致整个算法搜索速度缓慢，因此较好的初始解能够提升整个算法的性能，根据初始解设置的初始信息素则能加快算法的搜索速度。目前，构建初始解常用的方法一般为扫描法、节约算法、贪婪算法等，其中Solomon[15]经过测试证明插入启发式算法求得解最优，通过扩展传统的节约插入算法提出了Solomon插入算法。本文借鉴潘立军等[16]提出的改进的Solomon插入法——时差法，提出了适合本文研究问题的插入前检测算法来构建初始解。即根据时间窗要求，计算出车辆在各客户点的最迟开始服务时间，根据车辆的装载能力约束和各客户点的取送货需求量，计算出车辆从各客户点出发的最大装载量，在满足时间约束和车辆装载能力约束的前提下，在最优插入位置插入评价最优的客户点。相对于插入后检测，可省去一部分不可行插入的过程，从而有利于提高算法速度。具体步骤如下所示：

步骤1确定起始客户。Solomon经过相关测试之后，指出问题中客户所要求的服务时间窗口较窄时，选取距离配送中心最远的未构成线路的客户作为线路的起始用户得到的解较好，而客户所要求的服务时间窗口较宽时，选取最早结束服务时间未构成线路的客户作为起始用户得到的解较好。

步骤2将最优插入客户插入到最佳的插入位置。若该条配送子路径不能继续插入满足约束的客户点，则结束在该路径上插入客户，重新开始一条子路径并且确定起始用户。

步骤3判断是否所有的客户均已经被插入到路径中，若所有客户均已经被插入，则初始解构造完成，并且根据初始解更新信息素，否则执行步骤2。

3.2 可行路径的构建

在本文提出的蚁群算法中，将各蚂蚁放在配送中心，每只蚂蚁根据状态转移规则选择需要去往的下一个客户，当没有满足车辆载重约束的客户时，蚂蚁返回配送中心并且重新出发，直至所有客户被遍历，即每只蚂蚁都构建了一条完整的可行路径。本文的状态转移规则借鉴了蚁群系统（Ant Colony System，ACS）的状态转移规则，并进行适当调整。令wtj表示车辆在客户点j的等待时间，ltj表示车辆在客户点 j的延迟时间，当车辆早于客户所要求的最早开始服务时间到达，则需要等待至最早开始服务时间才能开始提供服务，过长的等待时间会影响车辆的配送效率；当车辆晚于最晚开始服务时间到达，就会产生延迟时间，过长的延迟时间则会大大影响客户的满意度。因此本文算法在状态转移规则中，考虑了车辆的等待时间或者延迟时间这个因素，有利于保障企业的利益和客户的服务质量。

所采取的状态转移规则如式（10）和（11）所示，其中τij为信息素浓度，ηij=1/dij为启发式信息，为蚂蚁k下一个可以访问的客户点集合，q0、α、β、γ、δ为预先设置的参数。

3.3 变邻域搜索

变邻域搜索（Variable Neighborhood Search，VNS）是由Hansen等在1997年提出的，使用不同邻域结构进行搜索，从而不断提高解的质量，具有很强的局部搜索能力。变邻域算法主要包括两个阶段，产生邻域解阶段和局部搜索阶段。通过阅读相关文献，并且结合所研究问题的特点，本文设计了四种邻域结构，并且设计了重定位（Relocate）算子[17]对产生的邻域解进行局部搜索。

四种邻域结构分别为：（1）2-OPT算子，在同一条路径中交换两个客户点；（2）Swap算子，在两条路径之间交换某个客户点；（3）Cross-exchange算子，在两条路径之间交换随机数量连续的客户点来产生邻域解；（4）2-OPT*算子。算法依次采用四种邻域结构产生邻域解进行局部搜索，当搜索到较优解时继续在该邻域搜索。

本文采用Relocate算子对所产生的邻域解进行局部搜索。Relocate算子就是对当前路径方案内所有的客户寻找其他的可行位置点进行插入，若搜索到新的解时，将其和当前最优解进行对比，若优于则更新当前最优解，并且继续在更新后的最优解基础上进行重定位操作。其中，每次Relocate算子搜索到新的最优解之后，会再次调用Relocate算子将最短路径上的客户定位到更新的减少了客户点的路径上，从而有利于消除最短路径，降低所使用的车辆数。局部搜索过程仍然采用3.1节中的插入前检测法，每次重定位操作都是将最优插入客户点插入到最优插入位置。

基于上述四种邻域结构和局部搜索方法，变邻域搜索的整个过程如下所示：

步骤1初始化参数设置。确定了四种邻域结构LYk,k={ }

1,2,3,4，最大循环次数CT，当前循环次数i=1。

步骤2判断是否超过最大循环次数，若超过则直接输出最优解；否则令k=1。

步骤3在当前邻域k中随机产生一个邻域解。

步骤4对产生的邻域解进行局部搜索。

步骤5判断局部搜索后的新解是否优于当前最优解，若优于则更新当前最优解；否则令k=k+1。

步骤6判断k是否小于5，若小于则转入步骤3；否则令i=i+1，转入步骤2。

3.4 信息素更新策略

在对蚁群算法的研究中，信息素的更新策略一般有局部更新和全局更新两种，局部更新策略是在蚂蚁每经过一条边之后就进行信息素更新，全局更新策略则是在所有蚂蚁走完它们的路径之后进行信息素更新。文献[18]提出了一种混合的全局更新策略，即在前10次迭代过程中根据本次迭代中的最优解进行信息素更新，10次迭代之后根据全局最优解进行信息素更新。采取这样的信息素更新策略可以在保持较好的收敛速度的同时提高搜索能力，更新规则如下：

其中，ρ表示信息素挥发系数；Lib表示当前迭代次数中的最优解；Lob表示全局最优解；Gen表示当前迭代次数；θ表示不同更新策略的迭代次数界限。为提高算法的收敛速度，本文采取上述对最优解的信息素全局更新策略，但是会出现算法在后期一旦陷入局部最优，就无法跳出的情况。因此在最优解连续一定迭代次数没有更新时，采取随机选取最优解中一定数量的路段，清空其信息素的措施，从而有利于跳出局部最优解继续搜索，避免陷入局部最优。

本文所设计的算法具体流程如图2所示。

图2 算法整体流程图

步骤1初始化参数。设置最大迭代次数MaxGen和最优解出现的最大重复次数MaxRT。

步骤2采用启发式算法产生初始解，令其为最优解BX,并且根据初始解更新信息素，令迭代次数Gen=0。

步骤3如果满足终止准则(Gen＞MaxGen)，则输出最优解BX；否则，对蚁群内每只蚂蚁根据状态转移规则生成配送路径，记录当前蚁群中的最优个体X。

步骤4对BX和X进行变邻域搜索，将其变邻域搜索后的结果同BX进行比较，若出现更优解则更新BX，否则最优解重复次数RT=RT+1。

步骤5如果RT＞Max RT，随机选取最优路径上的一定路段，清空其信息素并且令RT=0；否则根据BX进行信息素更新，继续执行步骤3。

4 算例实验

为检验混合变邻域改进蚁群算法的求解性能，本文设计了4个实验。其中，实验1为了验证3.1节改进插入法产生初始解的作用，将使用插入算法前后结果进行对比。实验2和实验3采用其他文献中的算例数据和国际标准算例，对本文提出的算法性能进行测试。为了验证本文所提出的模型和算法在实际问题中的适用情况，设计了实验4，采用企业的真实数据进行实验。

本文算法中的参数设置规则为：每次固定其他参数，对某一个参数进行取值，然后根据算例结果来确定最终取值。本文参数设置如表1所示。

表1 参数设置

实验1以Wang等[6]提出的关于VRPSPDTW的标准算例中的Cdp101算例进行实验，对比使用改进的插入法和不使用的结果，每个实验重复20次，分别记录第一次迭代中蚁群最优解和解的均值，其中车辆固定成本为100元，单位距离成本为1元/公里，单位等待成本为1元/公里，单位延迟成本为2元/公里。实验结果如表2所示。

表2 实验1对比结果表

从表2可以看出，采用改进后的插入法产生初始解，并且根据初始解设置初始信息素后，实验20次后，蚁群在第一次迭代中最优解的平均值为3 411.28，种群均值的平均值为5 895.95；不采用插入法产生初始解，实验20次后，蚁群在第一次迭代中最优解的平均值为3 945.92，种群均值的平均值为6 123.87。采用改进后的插入法产生的蚁群解的质量明显好于不采用的蚁群解的质量。

实验2的数据来源于文献[19]。设置最大迭代次数为100次，蚁群规模为20，本文算法的运算结果如表3所示。

表3 实验2算法结果对比表

从表3可以看出，本文研究的算法得到的结果比文献[19]采取模拟退火算法得到的结果更优。本文的结果只需要3辆车进行配送，相对于文献[19]减少了1辆车，提高了所用车辆的装载率；在各个客户点的平均等待时间和延迟时间也均小于文献[19]的结果，提高了客户满意度；总配送成本相对于文献[19]降低了12%，降低了企业的物流费用。

实验3为了进一步测试本文提出的混合变邻域改进蚁群算法的性能，以Wang等[6]提出的关于VRPSPDTW的标准算例作为实验对象，比较相关文献的结果。本文选取了客户规模10、25、50和100的算例各两个，与当前国际最优解[11]的对比如表4所示。在8个算例中，本文提出的变邻域改进蚁群算法在6个算例中求得的解与已知最优解一致，在算例Rcdp5001和算例Cdp101上，求得了和已知最优解相同的车辆数，距离上最大相差1.2%，十分接近最优解，从而进一步证明了本文所提出的算法在求解VRPSPDTW问题上的可行性和有效性。

表4 实验3算法结果对比表

实验4中客户点的分布情况如图3所示，客户点之间的距离信息和行驶时间数据均由真实的地图数据获得，客户所要求的时间窗(ET,LT)、送货量q、取货量p和服务时间ST如表5所示。配送中心有6辆车，车辆8：00从配送中心出发，最晚18：00返回配送中心，车辆的装载能力是4 m3。本文采取和文献[19]相同的参数设置规则，车辆的单位行驶成本是1元/公里，早于时间窗到达的等待成本为3元/小时，晚于时间窗到达的延迟成本为6元/小时，动用一辆车的固定成本是20元。根据上述条件，要求合理安排配送路线，使配送总成本最低。

表5 实验4客户信息数据

图3 实验4客户分布及路径规划结果

实验结果如表6所示，车辆在各个客户点均没有延迟服务，使得在此方面的顾客满意度达到最大，在各个点的平均等待时间为0.076 h，等待时间较小，4辆车的路线规划结果如图3所示，因此本文所建立的模型和求解算法能够满足实际问题的需要。

表6 实验4算法结果表

通过上述算例实验，本文所设计的改进蚁群算法，改善了基本蚁群算法在初期由于信息素匮乏而搜索速度慢的情况。在求解带软时间窗和同时取送货的车辆路径问题上，相对于模拟退火算法求得的结果，使用的车辆数量更少，等待延迟时间也更少。在关于VRPSPDTW问题不同规模的标准算例求解上，有些已经能够取得已知最优解，其余取得的结果也十分接近最优解。在实际问题的处理中，求得的结果能够满足实际需要。这都说明了本文算法具有良好的求解性能，能够搜索到较好的结果。

5 结束语

为了适应电子商务发展，整合物流企业的正、逆向物流，本文建立了关于电子商务环境下带软时间窗和退换货的车辆路径规划模型，并且在基本蚁群算法的基础上，设计了一种混合变邻域改进蚁群算法。使用插入法产生的初始解设置初始信息素，通过对比实验表明，采取这一措施后生成的蚁群解相比未采取时更优。将等待、延迟时间这些因素引入蚁群的状态转移规则，从而保障企业的利益和客户的服务质量。同时，为了提高算法的搜索能力和跳出局部最优的能力，本文设计了四种邻域结构的变邻域搜索算法进行局部优化。通过和其他文献中的算法对比和对标准算例的验证，本文所设计的算法均能够取得较优的结果，具有较强适应性，是求解本文提出问题的一种有效算法。本文研究的问题属于静态调度问题，在实际生活中，配送过程中往往会出现动态性事件，需要对现有的配送路线进行动态调整。因此，针对动态事件进行的动态调度研究将是接下来的研究方向。