电子商务环境下基于预售模式的混合带回程取货车辆路径问题

李 琳，孟 娇，陈 莹

(沈阳航空航天大学 理学院，沈阳 110136)

随着B2C电子商务的不断发展，高效的物流服务在客户的采购决策中发挥着越来越重要的作用。车辆路径问题(Vehicle Routing Problem,VRP)是物流行业发展过程中的重要组成部分，引起了该领域许多专家的关注。在B2C电子商务环境下，人们可以通过各种组合方式寻求物流配送过程的优化，使货物在实际运输过程中达到配送效率最高、配送费用最少、运输距离最短、配送时间最少的目标。现实生活中关于VRPMB的应用非常广泛，如：汽车制造商向供应商提供和回收零部件、半导体供应链分销网络中晶片的取货与送货过程、图书馆图书的发送与回馆问题等等。实践证明，降低物流配送费用、提高服务效率及质量、提高环保产业的市场需求不仅对企业具有十分重要的意义，对推动人类环保事业的发展同样也具有重大意义。

混合带回程取货的车辆路径问题(VRPMB)是在传统的VRP上增加了回程取货服务，客户可以是需要送货的，也可以是需要取货的，送货的客户和取货的客户可以是任意的、混合的。许多学者建立了VRP及VRPMB的数学模型[1-5]，并设计了相关算法求解该问题，如： Florian[1]结合了三种强大的局部搜索算法，三个互补的局部搜索算法使用顺序搜索和精简的想法并以有效的方式实现它们，由此产生的启发式算法可在几秒或几分钟内为各种基准测试实例计算高质量的解决方案，进而解决车辆路径问题。对于VRPMB问题，Kalayci[2]等人提出一种基于蚁群系统(Ant Colony System,即ACS)和变邻域搜索(Variable Neighborhood Search,即VNS)的混合元启发式算法。VNS是一种功能强大的优化算法，可提供密集的局部搜索，但它缺乏内存结构，通过利用ACS的长期存储器结构可以最小化这种弱点。因此可将它们组合在一起克服彼此的缺陷，从而提高算法的整体性能。Belgin[3]等人提出了一种基于混合启发式算法的变邻域下降算法(Variable Neighborhood Descent,即VND)和局部搜索算法(Local Search,即LS)，实验分析表明，混合启发式方法VND_LS对于找到同时取货和送货的双梯车辆路径问题的良好解是有效且高效的。Ahkamiraad[4]等提出一种基于遗传算法(Genetic Algorithm,即GA)和粒子群优化算法(Particle Swarm Optimization,即PSO)的混合算法，实验结果表明，在解决VRPMB时所提出的混合算法得到的解均是有效且高效的。

预售模式是以客户的需求来驱动商家生产，即利用B2C网络平台，提前一段时间发布产品信息，并在短时间内快速聚集单个分散的客户需求订单，然后给发货中心汇集一个大订单，发货中心可从供应链的前端、后端进行优化，从而更加精确地锁定订单，打包配送货物，从而大大降低物流成本。简言之，预售模式就是先收集客户需求订单，然后再进行流通和配送。

本文在传统的物流配送模式下引入了预售模式的概念，在预售期结束后某一时刻对订单进行打包配送，进而节省物流成本。建立了相应的数学模型，目标函数是为每辆车寻找一条合适的行驶路线，以便尽可能降低物流成本来满足客户取货和送货的要求。本文将K-均值聚类算法(K-means)和禁忌搜索算法(TS)相结合求解VRPMB，并与文献中的结果进行比较，实验结果验证了该混合算法的有效性。

1 VRPMB数学模型

VRPMB可描述为一个配送中心最多可用m辆车访问n个客户。每个客户必须被访问，目标是寻找起止配送中心且满足车辆容量限制的服务路径，以便最小化费用函数。0表示配送中心，可用车辆集合K={1,2，…，m}，所有客户点和配送中心的集合V={0,1,2…,n}，边集合E={(i,j)|i,j∈V}，客户i送货需求为di，客户i取货需求为pi，车辆容量限制为CK，车辆的初始容量为b0k，服务顾客i之后的车辆剩余容量为bi+1，两点间的配送距离为cij，车辆均为同质型车辆，故设单位车辆固定使用成本为F。

数学模型为

(1)

s.t.

(2)

(3)

(4)

(5)

bi+1=bi-di+piCK,∀i∈V/{0}

(6)

yik∈{0,1},∀i∈V/{0},∀k∈K

不同融资渠道分别可以用于建设、运营、规划，且彼此不能混同。对于特定融资渠道用于再生水项目的融资份额一般也规定上限。对于基金的资金回收和持续运行实行谨慎的管理，对于各类融资适用于再生水项目的条件、申请程序等都有严格的法律规定。

(7)

xijk∈{0,1},∀i,j∈V,∀k∈K

(8)

决策变量为

xijk=

式(1)为目标函数，即最小化车辆行驶成本与车辆固定成本之和，约束(2)为车辆从配送中心出发的送货容量约束，约束(3)是每个客户只能被一辆车服务，约束(4)是车辆k从配送中心出发时的初始载重，为路径上所有客户的需求量之和，约束(5)是保证进入和驶出每个客户的车辆数相同，约束(6)是服务完客户i之后，车辆剩余载重量不能超过车辆的容量限制，式(7)和式(8)为决策变量。

2 求解VRPMB的算法设计

VRP是一个NP-hard问题，VRPMB亦是一个NP-hard问题，很难在较短的时间内获得全局最优解，本文采用启发式算法进行求解。禁忌搜索算法是一种元启发式算法，是对局部搜索算法的扩展，它是解决复杂车辆路径问题的一种非常有效的方法。Qiu[6]、符卓[7]等人利用禁忌算法求解VRPMB，并取得了一些研究成果。邱萌[8]对于需求可离散拆分的问题，采用禁忌搜索算法求解，取得了很好的搜索性能。殷佳林[9]等人提出一种蚁群算法与禁忌搜索算法的新混合算法，提高了全局搜索能力，加快了收敛速度。禁忌搜索算法的基本思想是防止重复并禁止或惩罚下一步骤中的重复。禁忌搜索算法的基本组成部分是一个起始解、移动机制、邻域、禁忌表长度、禁忌列表、禁忌特赦准则和终止准则。

2.1 初始解的设定

禁忌搜索算法対初始解有一定的依赖性，一个高质量的初始解[10]能够帮助禁忌搜索算法在解空间中找到一个最终的高质量解决方案，提升禁忌搜索算法的收敛速度。可以使用不同的解决方法来获得初始解决方案。这些结果是可以随机得到的，也可以用启发式方法得到一个初始解。本文采用K-means算法得到了有效的初始解。经典的K-means算法[11]是给定一个数据点集合和需要的聚类数目，由用户指定，根据某个距离函数反复把数据分入几个聚类中，但K-means算法是不带约束的算法，因而不能直接将其应用于VRPMB。本文设计的K-means算法，在对客户点进行聚类时，需要考虑客户点的需求总量不能超过车辆的最大运载容量。若某一簇的客户需求总量达到车辆最大运载容量时，其他客户便选择次近的簇加入其中，目的是将距离相近的客户规划在同一条路线上，由一辆车服务，以达到节约运输成本的目的。

假设给定数据样本X，包含了n个对象X={X1,X2,…,Xn}，其中每个对象都具有m个维度的属性。Xi表示第i个对象(1≤i≤n)，Oj表示第j个聚类中心(1≤j≤k)，Xit表示第i个对象的第t个属性(1≤t≤m)，Ojt表示第j个聚类中心的第t个属性。|Sj|表示第j个类簇中对象的个数，Xij表示第j个类簇中第i个对象(1≤i≤|Sj|)。

具体算法步骤如下：

(1)从数据集pi=0中随机选取k个元素，作为k个簇的初始聚类中心；

(4)将数据集D中全部元素在容量限制的条件下，按照新的中心重新聚类；

(5)重复(4)，直到聚类结果不再变化；

(6)输出结果。

2.2 邻域操作及候选集的确定

本文采用两交换法[12]得到邻域解。两交换法是指随机地交换两个客户点的基本信息。交换可以是一条路径内两个客户点的交换，2-交换法路径内交换方式如图1所示。也可以是两条不同路径的两个客户点之间的交换，2-交换法路径间交换方式如图2所示，并且由此可以设置出候选集。

图1 2-交换法，路径内交换示意图

图2 2-交换法，路径间交换示意图

2.3 确定禁忌对象和禁忌表长度

禁忌对象是指禁忌表中被禁的局部最优解，本文将每次迭代之后的最优解作为禁忌对象放入禁忌表中，用禁忌表记录已搜索的局部最优解的历史信息，使算法在一定程度上避免陷入局部最优，开辟新的搜索区域。禁忌表长度是指禁忌对象在不考虑特赦准则的情况下，禁止被选取的最大次数。禁忌表长度太短会造成搜索的循环，禁忌表长度太长又会导致计算时间过长，所以禁忌表长度应该根据问题的规模与特征进行选取。

2.4 终止准则

本文采用的终止准则是目标控制原则：如果在一个给定迭代步数内当前最优值没有变化，可终止计算。

3 实验结果与分析

B2C电子商务环境下的订单具有多批次、小批量、多种类等特点，且实验数据不易获得，因此本文采用已有文献[13]-[18]的数据来验证算法的有效性。算法是用Python实现，在环境为Windows 7、内存为8GB的Dell Optiplex 3046的计算机上运行。

3.1 VRPMB问题特例

实验1是8个客户的问题，实验2是20个客户的问题，是本文的VRPMB模型中的取货需求的特殊实例，车辆的最大载重量均为8t，车辆的固定成本忽略不计。具体数据见文献[13]-[14]。设置总迭代次数N=50，聚类中心=3，禁忌表长度T=10。实验1计算比较结果见表1。

从表1可以看出，本文设计的算法得出的结果与文献[13-14]的结果相同，但是总耗时更少，为0.04 s。得出3辆车配送方案的具体配送路线分别为：车辆1：0-4-7-8-0；车辆2：0-5-3-1-2-0；车辆3：0-6-0。

实验2随机求解10次，取总迭代步数N=100，聚类中心=5，禁忌表长度T=20，得到的计算结果见表2。

表1 实验1结果比较

由表2可以看出：随机求解10次的结果均为高质量的解决方案，平均使用车辆为5辆，平均车辆运行距离为875.36 km，其中最好的解是864.94 km，最差解的运行距离仅比最好解高2.96%({(最差的解-最好的解)/最好的解}×100%)。从运行时间上看，10次求解的平均计算时间为0.562 s，计算效率较高。实验2得到的最好配送方案为第8次的运行结果，5辆车的具体配送路径分别为：车辆1：0-9-11-13-16-2-8-0；车辆2：0-1-4-17-14-15-3-0；车辆3：0-6-5-20-0；车辆4：0-10-7-19-0；车辆5：0-18-12-0。

表3 实验2结果与文献[13]-[15]结果比较

表3给出实验2中本文计算结果与文献[13]-[15]的结果比较，求得的最好解为864.94 km，远远优于其它文献的最好结果，所需车辆数为5辆，比文献[14]-[15]的用车数量更少，在运算时间上具有较高的效率。

3.2 VRPMB问题

实验3的数据取自文献[16]-[18]，是20个客户点的VRPMB问题，车辆的最大载重量均为8 t，车辆一次配送的最大行驶距离都为50 km，车辆的固定成本忽略不计。实验3随机求解10次，设置总迭代步数N=100，聚类中心k=5，禁忌表长度T=20，得到的计算结果见表4。

从表4可以看出：在对实验3进行的10次求解中都得到了质量很高的解，平均使用车辆数为3辆，其解的平均值为103.19 km，优于文献[17]的最好结果，其中有两次解的质量最好，其运行总距离均为100.66 km。对应的配送方案为：车辆1：0-9-18-11-10-3-2-8-0；车辆2：0-19-17-16-4-5-13-15-0；车辆3：0-14-6-1-20-7-12-0。求解算法的计算结果也比较稳定，在10次求解结果中，最差解的运行距离仅比最好解高5.42%({(最差的解-最好的解)/最好的解}×100%)。从运行时间上看，10次求解的平均计算时间为0.544 s，计算效率较高。

表4 实验3求解结果

表5 实验3结果与文献[16]结果比较

表5是与文献[17]以及文献[18]的总费用进行比较，可以看出本文的运算结果较好，验证了算法的有效性。

4 结论

物流配送智能化已经成为电子商务环境下物流发展的一个新趋势，专家们致力于物流配送优化的研究，旨在能够节省物流成本，节约车辆资源。预售模式不仅可以应用到B2C电商平台，还可以引入到物流配送中，提前收集客户需求订单，然后打包配送货物，进而大大降低物流成本。本文提出了基于禁忌搜索算法(TS)和K-均值聚类算法(K-means)的混合启发式算法，建立了VRPMB的数学模型，并进行实验求解。仿真实验结果表明，所提出的算法在解决方案质量和运行时间方面都是稳定且有效的，可得到高质量的解决方案。本文研究了静态条件下模型求解问题，未来的研究可以在动态条件下进行讨论，如考虑车辆运行时间的不确定、客户服务时间的不确定以及客户需求的不确定等多种不确定信息，也可在算法方面进一步探索，如考虑初始聚类中心的选取、邻域改进策略等。