线路截断法在卷烟配送路径规划中的应用
开篇：润墨网以专业的文秘视角，为您筛选了一篇线路截断法在卷烟配送路径规划中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：卷烟配送路径规划是一个LS-VRP问题，同时要兼顾配送里程短、不同车辆配送任务均衡等要求。文章建立了基于任务量均衡、所用车辆最少、配送里程最短的多目标卷烟配送模型，并设计了基于线路截断的启发式算法进行求解，在实例运用中得到了较好的效果。
中图分类号：F252.14 文献标识码：A
Abstract： The cigarette distribute route problem is a LS-VRP problem with includes the consideration of distance saving and the work balance between each car. This paper found the module with the object of work balance， car saving and distance saving. Then design the route cut based heuristic algorithm to solve the module and get a good effect in the example problem solving.
Key words： route planning； cigarette distribute； heuristic algorithm； multiple objects
在我国，一般以市级烟草配送中心为中心，直接配送到全市各地的上万个配送点。负责卷烟配送的车辆由烟草配送中心出发，依次到其负责的收货点进行配送，最终配送完成后车辆返回配送中心[1]。现有的卷烟配送车辆型号众多，载货量也有区别。卷烟配送路线的规划是一个LS-VRP（大规模车辆路径）问题，是一个NP问题。对于一般的LS-VRP问题有精确算法、亚启发式算法和启发式算法等。
众所周知，我国卷烟配送工作由来已久，因此各地烟草商业企业在发展中已经形成了自己的配货顺序，并根据配货顺序安排配送车辆。这种配货顺序有其存在的合理性，并且已经在运行之中，进行较大的改动有一定的风险。但是传统的车辆配送任务分配主要采取人工的方式进行，工作量大且优化程度较低。另外，在解决大规模VRP问题的方法中，一种思想先按照TSP问题利用算法生成一个全局的配送路线，之后对这个总的配送路线进行截断，来确定分配给每辆车的配送路线，从而生成卷烟配送VRP问题的配送方案。这种方法优化程度较高，而且可以保证较快的计算速度。因此基于大线路截断成小线路进行配送的方法有一定的实际价值。
而且除了总配送路程最短、费用最小、时间最短等一般VRP问题的约束之外，处于管理上的考虑，卷烟配送过程有其特有的特点，例如要求不同车辆工作时间比较均衡且小于上限、车辆之间的配送量均衡等。因此引入了一些原则进行配送任务划分来保证车辆工作强度的均衡。
本文研究的基于配送任务均衡的线路截断方法，属于一种亚启发式算法，主要实现的功能是在收货点配送排序确定的情况下，把这些收货点的配送任务分配给各配送货车。货车从配送中心出发，按照指定的顺序配送其负责的收货点，之后返回配送中心。在这个过程中要考虑配送路径最短、所用车辆最少、配送工作量均衡的要求。
1 模型建立
收货点配送任务序列为：
S=s，s，…，s，…，s
其中s，s，…，s表示n个收货点的收货量。而其角标表示该收货点配送的次序。s为第一个配送，s为第二个配送，依次类推，s为最后一个。每个收货点只能由一个车辆配送。
每个车辆包含标准载货量和标准服务客户数两个指标，这两个指标由车辆的型号和配送人员的工作时间确定。
配送车辆标准载货量为：
V=v，v，…，v，…，v
配送车辆标准服务客户数为：
C=c，c，…，c，…，c
目标函数为：
MinDis=∑d
MinN
MinPv=∑ρv-
MinPc=∑ρc-
式中Dis表示每个配送车辆的配送距离d之和，即总配送距离。N为使用的车辆总数。ρv、ρc分别表示第j辆车的装载量与标准载货量、服务客户数与标准服务客户数的比值，即装载率和服务率，用来衡量车辆的工作负荷程度。、表示了所有车辆的装载率和服务率。Pv与Pc计算了车辆实际装载率、服务率与平均值的差值之和，其值越大表示车辆的任务分配越不均衡。目标函数反映了实际卷烟配送中的实际要求。
2 模型求解
在实际的配送过程中，首先需要设定每辆车的装载率和服务率的上下限值ρv， ρv、ρc， ρc。即车辆的装载率不得高于其上限值，也不能低于其下限值，服务率亦然。这样可以保证车辆的使用率。如果车辆运力紧张的情况下可以将下限值提高，但会降低在配送距离优化中的调整余地。如果需主要考虑配送里程的节约可以适当扩大区间，从而可以在更宽的范围内进行配送任务的划分。
为了保证任务量的均衡和较短的配送距离，本文设计了基于线路截断的亚启发式算法进行配送任务划分。算法的流程如下：
Step1 对每辆车进行模拟装车，以车辆j为例，将待分配任务序列（第一次循环时即为初始S序列）中的收货点从前到后依次装入车辆j中，当车辆j的装载量与服务率之一达到其下限值时，当前最后一个装入的点即为其装载任务的下限点，假设该点为sl，之后继续装载，当车辆j的装载量与服务率之一达到上限值时，最后一个装入的点即为其装载任务的上限点，假设该点为s，则车辆j的可截断区间为s，s。即该车辆的当前配送任务可以是从配送序列的第一个点s开始到s，s中任何一点结束。计算所有车辆的可截断区间。
Step2 找到每个车辆可截断区间内相隔距离最长的一组相邻点s，s，两点之间距离记录为Sav，则车辆的模拟配送任务为s…s，
s是剩余配送任务序列的起始点，即新的s。之后比较所有车辆当前模拟装车的使用效率ρ=ρv+ρc，选择使用效率最高的车型作为当前循环的所选车型，其配送任务为其对应的s…s，将已配送的点以及该车辆从任务序列和备选车型中删除。
Step3 如果最后一个车的使用效率低于平均使用效率的20%，则可以通过调高每辆车的装载率和服务率下限值之后返回Step1，直到将最后一辆车的配送任务分配至其他车辆为止。如果使用效率高于平均使用效率的20%低于85%，则通过调低每辆车的装载率和服务效率下限值返回Step1，可以减少前面车辆的任务量，提升最后一辆车使用效率。如果最后一辆车的使用效率高于平均使用效率的85%则任务分配结束。
若循环20次之后仍无法跳出循环，则输出当前解。
3 仿真实验与数据分析
下面通过Matlab软件编程进行仿真实验。
配送任务序列为某地市实际卷烟配送任务，共712个点。
输入数据：
配送中心与收货点、各收货点之间的距离矩阵，各收货点的收货量，车辆矩阵：
首次循环的装车方案为：
当前总配送里程为1 201km。最后一辆车的使用效率1.96为平均使用效率1.93的1.014%，达到终止条件，配送任务分配完毕。整个算法运行时间为1.87s。
可以看出，该算法可以在很短的时间内完成大规模配送任务的划分，并且较好地实现了配送任务的均衡与配送里程的节约，从而可以针对不同的卷烟需求做出相应的配送方案，从而实现动态任务规划和卷烟敏捷供应的目的。
参考文献：
[1] 翁建红，李朝阳. 基于GPS的烟草物流配送线路规划[J]. 物流科技，2008，31（9）：18-20.