带时间窗的连锁超市生鲜品配送车辆路径优化

■ 姚卓顺（苏州工业职业技术学院经贸管理系 江苏苏州 215104）

引言

1959年，Dantzig和Ramser提出了车辆路径问题（Vehicle Routing Problems，简称VRP），VPR问题至今都是解决物流配送问题的核心部分，它以路程最短、成本最小、耗费时间最少等为目的。本文的VRP描述为：在一定约束条件（需求量、车载量、需求时间、行驶里程、行驶时间等）下，对一定数量的门店，选择适当的车辆配送路径，使其从配送中心出发，将货物有序送至各门店后返回配送中心。

综合过去有关车辆路线问题的求解方法，可以分为精确算法（exact algorithm）与启发式解法（heuristics）。

精确算法一般会随着问题规模的增大而呈现数据量增大的情况，计算成本比较大，因此很难有效解决大规模的VRP问题，实际应用范围有限。

由于VRP是NP-hard问题，这类问题的大型实例很难以用精确算法求解，多年来很多专家对此类车辆运输问题进行了研究，提出了各种各样的启发式方法，常见的有构造算法、蚁群算法、遗传算法、节约里程法。

节约里程法，是用来解决运输车辆数目不确定的问题的最有名的启发式算法。节约里程法的核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。根据节约法的基本思想，如果一个配送中心p0分别向m个客户配送货物，在汽车载重能力允许的前提下，每辆汽车的配送线路上经过的客户个数越多，里程节约量越大，配送线路越合理。

节约里程法运算速度较快，特别是在小规模的配送路径优化问题中，节约里程法的优化解与最优解更加接近，其在实际应用中也能得到较满意的结果，连锁超市配送规模较小，所以本文将以节约里程法对连锁超市配送车辆路径进行优化。

带时间窗约束的VRP

时间约束问题大体分为两种，一种是“允许延时”的“软时间窗”问题，一种是“不允许延时”的“硬时间窗”问题。

“软时间窗”问题是指：客户对配送的时间要求具有弹性，客户能够承受因各种原因导致的不能准时送达，但要索取因此而带来的损失。

“硬时间窗”问题是指：客户对最长运达时间具有严格要求，也就是说，在客户的时间要求之内，配送中心必须将货物配送到位，否则配送没有达到客户的时间要求，直接导致了物流流通的障碍和瓶颈。

由于“硬时间窗”的约束，往往会导致成本激增，因此，相比而言，“软时间窗”更具管理柔性，我们可以通过制定惩罚机制，例如设定惩罚成本来提高准点服务频率。

在建立惩罚成本模型时，设门店a可接受的时间窗[Ma，Na]，门店要求的时间窗[ma，na]。根据配送车辆到达门店的时间，可以分三种情况：

一是配送车辆在门店要求的时间之前到达。此时又可分为两种情况，其一车辆是在门店可接受的时间到达，即在[Ma，ma]内，车辆到达后可以交货，但由于交货不在门店要求的时间内，需要付出一定惩罚成本，则函数可以表示为P(Xa)=(ma-Xa)·α；其二是车辆到达的时间在门店可接受的时间之前，即在Ma之前，此时客户无法收货，这时的惩罚成本无穷大，P(Xa)=∞。

二是配送车辆在门店要求的时间内到达，即在[ma，na]内，此时不产生惩罚成本，P(Xa)=0。

三是配送车辆在门店要求的时间后到达。此时也可分为两种情况，其一车辆是在门店可接受的时间到达，即在(na，Na]内，车辆到达后可以交货，但此时需要承担一定的惩罚成本，则函数可以表示为P(Xa)=(Xa-na)·β；其二是车辆到达的时间在门店可接受的时间之后，即在Na之后，此时客户无法收货，这时的惩罚成本无穷大，P(Xa)=∞。

综上，惩罚成本函数可以表示为：

式中：Xa是生鲜品送达门店的时间；A和β是惩罚系数；P(Xa)是惩罚成本；P是生鲜单位价值；qb是每个门店生鲜需求量。

表1 连锁超市配送中心与门店之间的距离

表2 门店的货物需求量及时间窗要求

连锁超市生鲜品配送车辆路径问题模型建立

（一）模型建立的约束条件

门店的数量固定且位置已知；门店的生鲜品需求量一定；生鲜品送达时间窗一定；每辆车的行驶时间不得超过司机工作的时间；每家门店且只能由一辆车一次性完成送货；每条配送线路各门店的需求量之和不得超过车辆的最大核载量；车辆由配送中心出发，有序到达各门店后返回配送中心。

（二）软时间窗约束下的模型建立

生鲜品配送中心每天派出n辆车从配送中心出发，为一家或多家门店送货，完成任务后再返回配送中心。生鲜品配送的成本主要包括运输成本、制冷成本以及软时窗下的惩罚成本。

1.运输成本。运输成本主要包括车辆的固定成本和变动成本。由于固定成本与车辆运输距离及门店数量没有直接联系，因此本文不予考虑。变动成本受油耗、车辆磨损、维修等因素的影响，所以他们主要与车辆的运输距离呈正比。计算公式为：

2.生鲜品的制冷成本。 在配送过程中，生鲜品的制冷成本主要是由于保存环境和配送时间而导致的。因此我们在研究时，忽略其他因素，将生鲜品的制冷成本分为两个部分，一是随着配送时间的增加制冷成本也随之上升；二是配送服务时，装卸生鲜品过程中开启车门，车内外冷暖空气对流导致车内温度上升，从而产生制冷成本。计算公式为：

3.惩罚成本如式（1）所示。 综上所述，我们构建的生鲜品配送车辆路径问题的目标函数：

公式中涉及的参数如下：

m是门店的数量；n是配送车辆数；lab是从门店a到门店b的运输距离；tab是从门店a到门店b的运输时间；tbh是从第h辆车在门店的停留时间；Cabh是从第h辆车在路段(la，lb)上的运输成本；C表示单位运输成本；Cbh是配送过程的制冷成本；Cz1是由于配送服务时间产生的制冷成本；Cz2是门店送货服务过程中热侵入时产生的制冷成本；ΔT是为冷藏车内与外界温差；q是每个门店生鲜需求量；xabh是0,1变量，若第第h部车辆经过路段(la，lb)，则xabh=1，否则xabh=0；xbh是0,1变量，若第h部车辆为b门店服务，则xbh=1，否则xbh=0。

连锁超市生鲜品车辆路径优化算例分析

客户在苏州市有1个配送中心和10家连锁超市门店，现要求对其生鲜品配送车辆路径进行优化。相关参数如表1、表2、表3所示。

根据前面所建立的软时间窗约束下生鲜品配送车辆路径问题的模型式（4），其相关因素包括运输成本、制冷成本和惩罚成本，其目标函数为总成本最小。本文利用节约里程法对连锁超市生鲜品车辆配送路径进行优化时，其涉及的相关因素包括节约的运输成本、节约的制冷成本和惩罚成本，所以我们的目标是使节约总成本最大的门店插入配送路径中，直至完成所有门店的配送任务，具体的计算公式如下：

P(Xa)如式（1）所示。

公式中：yab是节约里程数；Pr是节约的运输成本；Pd是节约的制冷成本；Pz是节约的总成本；v表示运输速度。

利用节约里程法结合时间窗约束，我们将带有时间窗约束的连锁超市VRP求解步骤归纳如下：

第一步，将门店按时间窗先后顺序排序；第二步，计算配送中心到各门店的节约里程数；第三步，从配送中心发车，首先将时间窗要求最早的门店作为第一个配送对象，然后将节约总成本最大的门店加入路线，成为第二个配送对象；第四步，重复第三步，直至所有的门店都被排入路线内。

根据以上步骤求解，最终的配送路线为P0配送中心—I凤凰街店—A东大街店—C养育巷店—E竹辉路店—B南园路店—G桃花坞店—J中街路店—F观前街店—D皮市街店—H相王路店—P0配送中心。

按当前连锁超市配送车辆路径规划的原则，即以最为靠近配送中心的门店开始送货，以下一门店距离上一门店最近来进行下一门店的送货，直至送完为止回到配送中心，这10家店目前的配送路线为：P0配送中心—B南园路店—E竹辉路店—H相王路店—I凤凰街店—C东大街店—A养育巷店—F观前街店—D皮市街店—J中街路店—G桃花坞店—P0配送中心。

因此，与连锁超市当前的配送路线相比较（表4），配送总成本节约了138-98.4=39.6元。

表3 相关参数值

表4 配送路径优化前后数值比较

结论

本文利用节约里程法结合门店时间窗的要求，进行了生鲜配送车辆路径规划，在满足连锁超市各门店生鲜收货时间需求的同时，选择较优的路径进行配送，这样提高了配送车辆生鲜送货服务质量，节省了车辆在各门店的卸货等待时间，同时也保证了生鲜及时进入各门店上货架。

1.朱金峰.冷链物流车辆路径模型优化研究[D].山东师范大学，2009

2.朱晓峰，蔡延光.物流配送的优化模型及算法在连锁企业中应用[J].顺德职业技术学院学报，2011（1）

3.胡运权.运筹学（第5版）[M].高等教育出版社，2008

4.付丽茹，解进强，罗松涛.运输配送路线优化（第1版）[M].清华大学出版社，2011

5.董立娟.带时间窗维束的冷鲜肉制品配送路径优化[D].中南大学，2011

6.陈晓伟，张悟移，耿继武.节约法在配送路线选择中的应用[J].昆明理工大学学报，2003（8）

7.中国物流技术协会.中国冷链物流发展报告[R].2010

8.缪小红.基于GIS的生鲜食品冷链物流配送路径优化研究[D].福建农林大学，2010