魏 嫄， 曾 华， 吴耀华 WEI Yuan,ZENG Hua,WU Yao-hua

（1.山东大学 现代物流研究中心，山东 济南 250061；2.四川省烟草公司成都市公司，四川 成都 610072）

在我国，一般以市级烟草配送中心为中心，直接配送到全市各地的上万个配送点。负责卷烟配送的车辆由烟草配送中心出发，依次到其负责的收货点进行配送，最终配送完成后车辆返回配送中心[1]。现有的卷烟配送车辆型号众多，载货量也有区别。卷烟配送路线的规划是一个LS-VRP（大规模车辆路径）问题，是一个NP问题。对于一般的LS-VRP问题有精确算法、亚启发式算法和启发式算法等。

众所周知，我国卷烟配送工作由来已久，因此各地烟草商业企业在发展中已经形成了自己的配货顺序，并根据配货顺序安排配送车辆。这种配货顺序有其存在的合理性，并且已经在运行之中，进行较大的改动有一定的风险。但是传统的车辆配送任务分配主要采取人工的方式进行，工作量大且优化程度较低。另外，在解决大规模VRP问题的方法中，一种思想先按照TSP问题利用算法生成一个全局的配送路线，之后对这个总的配送路线进行截断，来确定分配给每辆车的配送路线，从而生成卷烟配送VRP问题的配送方案。这种方法优化程度较高，而且可以保证较快的计算速度。因此基于大线路截断成小线路进行配送的方法有一定的实际价值。

而且除了总配送路程最短、费用最小、时间最短等一般VRP问题的约束之外，处于管理上的考虑，卷烟配送过程有其特有的特点，例如要求不同车辆工作时间比较均衡且小于上限、车辆之间的配送量均衡等。因此引入了一些原则进行配送任务划分来保证车辆工作强度的均衡。

本文研究的基于配送任务均衡的线路截断方法，属于一种亚启发式算法，主要实现的功能是在收货点配送排序确定的情况下，把这些收货点的配送任务分配给各配送货车。货车从配送中心出发，按照指定的顺序配送其负责的收货点，之后返回配送中心。在这个过程中要考虑配送路径最短、所用车辆最少、配送工作量均衡的要求。

1 模型建立

收货点配送任务序列为：

其中s1,s2,…,sn表示n个收货点的收货量。而其角标表示该收货点配送的次序。s1为第一个配送，s2为第二个配送，依次类推，sn为最后一个。每个收货点只能由一个车辆配送。

每个车辆包含标准载货量和标准服务客户数两个指标，这两个指标由车辆的型号和配送人员的工作时间确定。

配送车辆标准载货量为：与标准载货量、服务客户数与标准服务客户数的比值，即装载率和服务率，用来衡量车辆的工作负荷程度。表示了所有车辆的装载率和服务率。Pv与Pc计算了车辆实际装载率、服务率与平均值的差值之和，其值越大表示车辆的任务分配越不均衡。目标函数反映了实际卷烟配送中的实际要求。

2 模型求解

在实际的配送过程中，首先需要设定每辆车的装载率和服务率的上下限值即车辆的装载率不得高

式中Dis表示每个配送车辆的配送距离d之和，即总配送距离。N为使用的车辆总数。ρvj、ρcj分别表示第j辆车的装载量行配送任务的划分。

为了保证任务量的均衡和较短的配送距离，本文设计了基于线路截断的亚启发式算法进行配送任务划分。算法的流程如下：

Step1 对每辆车进行模拟装车，以车辆j为例，将待分配任务序列（第一次循环时即为初始S序列）中的收货点从前到后依次装入车辆j中，当车辆j的装载量与服务率之一达到其下限值时，当前最后一个装入的点即为其装载任务的下限点，假设该点为sl，之后继续装载，当车辆j的装载量与服务率之一达到上限值时，最后一个装入的点即为其装载任务的上限点，假设该点为su，则车辆j的可截断区间为［sl,su］。即该车辆的当前配送任务可以是从配送序列的第一个点s1开始到［sl,su］中任何一点结束。计算所有车辆的可截断区间。

Step2 找到每个车辆可截断区间内相隔距离最长的一组相邻点两点之间距离记录为Savj， 则车辆的模拟配送任务为是剩余配送任务序列的起始点，即新的s1。之后比较所有车辆当前模拟装车的使用效率选择使用效率最高的车型作为当前循环的所选车型，其配送任务为其对应的 （s1… sa），将已配送的点以及该车辆从任务序列和备选车型中删除。于其上限值，也不能低于其下限值，服务率亦然。这样可以保证车辆的使用率。如果车辆运力紧张的情况下可以将下限值提高，但会降低在配送距离优化中的调整余地。如果需主要考虑配送里程的节约可以适当扩大区间，从而可以在更宽的范围内进

图1 某车辆的服务区间计算示意图

Step3 如果最后一个车的使用效率低于平均使用效率的20%，则可以通过调高每辆车的装载率和服务率下限值之后返回Step1，直到将最后一辆车的配送任务分配至其他车辆为止。如果使用效率高于平均使用效率的20%低于85%，则通过调低每辆车的装载率和服务效率下限值返回Step1，可以减少前面车辆的任务量，提升最后一辆车使用效率。如果最后一辆车的使用效率高于平均使用效率的85%则任务分配结束。

若循环20次之后仍无法跳出循环，则输出当前解。

3 仿真实验与数据分析

下面通过Matlab软件编程进行仿真实验。

配送任务序列为某地市实际卷烟配送任务，共712个点。

输入数据：

配送中心与收货点、各收货点之间的距离矩阵，各收货点的收货量，车辆矩阵：

车辆编号 1 2 3 4 5 6 7 8 9载货量下限 3 800 3 800.0 3 800.0 4 200.0 4 800.0 5 000.0 5 500 5 800.0 6 000.0载货量上限 4 180 4 180.0 4 180.0 4 620.0 5 280.0 5 500.0 6 050 6 380.0 6 600.0服务客户数下限 70 75.0 75.0 75.0 75.0 75.0 80 85.0 85.0服务客户数上限 77 82.5 82.5 82.5 82.5 82.5 88 93.5 93.5

首次循环的装车方案为：

车辆编号 3 1 2 4 5 6 7 8 9载重量 3 623.00 3 881.00 4 163.00 4 169.000 4 493.00 5 368.00 4 839.00 5 246.00 2 498.00服务客户数 82.00 77.00 79.00 82.000 82.00 82.00 88.00 93.00 47.00装载率 0.95 1.02 1.09 0.992 0.93 1.07 0.87 0.90 0.41服务率 1.09 1.10 1.05 1.090 1.09 1.09 1.10 1.09 0.55

当前总配送里程为1 262km。由于最后一辆车的使用效率0.96为平均使用效率2.06的46%，从而通过调低其他车辆的载货量与服务率的下限来将前面的车配送任务向后移。

通过8次循环调整后，装车方案为：

车辆编号 4 7 8 9 5 1 3 6 2载重量 3 575.00 4 489.00 4 361.00 4 899.00 5 033.00 3 822.00 4 013.00 4 239.00 3 849.00服务客户数 81.00 87.00 92.00 92.00 80.00 58.00 77.00 81.00 64.00装载率 0.85 0.81 0.75 0.81 1.04 1.00 1.05 0.84 1.01服务率 1.08 1.08 1.08 1.08 1.06 0.82 1.02 1.08 0.85

当前总配送里程为1 201km。最后一辆车的使用效率1.96为平均使用效率1.93的1.014%，达到终止条件，配送任务分配完毕。整个算法运行时间为1.87s。

可以看出，该算法可以在很短的时间内完成大规模配送任务的划分，并且较好地实现了配送任务的均衡与配送里程的节约，从而可以针对不同的卷烟需求做出相应的配送方案，从而实现动态任务规划和卷烟敏捷供应的目的。

[1] 翁建红，李朝阳.基于GPS的烟草物流配送线路规划[J].物流科技，2008,31(9):18-20.