覆盖模型下的跨区域配送线路优化

摘要：本文结合烟草专卖性的特点，从客户需求角度出发，利用覆盖模型，针对现有卷烟配送线路提出跨区域配送线路优化的新方法。通过对不同需求的大量离散卷烟零售客户按道路情况聚类分析，化零为整得出零售客户需求点集，运用覆盖模型从零售客户需求点集中寻找虚拟物流配送中转站，进而打破以往按区域划分的配送方式，达到优化配送线路，提高装载率的目的。

关键词：跨区域配送路线 覆盖模型 虚拟卷烟物流配送中转站

烟草行业面对零售客户的卷烟配送一直是烟草物流中心的重要环节，及时满足客户需求，实现卷烟配送的高效率和低成本，是卷烟物流配送环节中的重要部分。2012年烟草行业开展精益物流工作，应对不断面临的挑战。但在卷烟配送过程中，零售客户终端具有数量大，分布广，需求量不定等特点，不同的送货线路之间存在任务量不均衡问题，易造成配送车辆装载率较低，配送资源浪费和一系列的服务质量问题，属于大规模的车辆线路规划问题（Vehicle Routing Problem，VRP），仅仅通过增加配送车辆和人员等满足配送服务，不符合精益物流的基本要求，因此必须寻求新的方法对配送线路进行优化，从根本上解决配送问题。

而在卷烟配送实现在途管理的基础上，卷烟配送线路的优化可通过构建电子地图，确定零售客户的位置及经济可行距离，有助于将大量离散点客户进行聚类分析，减少需求点的信息。通过选址模型能有效覆盖所有需求点信息，促进线路优化的进行。因此，本文在以后在途管理系统和选址模型的理论基础上，从选址角度提出优化配送线路模式。

随着卷烟配送在烟草精益物流建设中的地位不断提升，已有很多学者对优化烟草配送路线进行探讨。陈子侠（2003）研究了城市卷烟配送线路的网格划分算法；史亚蓉，万迪P等（2009）分析了基于GIS的物流配送线路规划研究；吴耀华等（2011）研究了在GIS环境下基于P-种植模型的卷烟配送体系优化。上述研究成果对卷烟配送线路优化的具体实施具有重要意义。但是，卷烟配送只能通过物流配送中心统一进行管理配送，并且需求客户数量大分散广需求量不定，运用传统VRP优化算法求解，复杂性高、计算耗时大，针对卷烟配送偏远地区道路交通状况差，配送成本高，不能及时送货到户等问题的研究方法较少，缺乏大范围推广及应用，对卷烟配送线路优化方法的探索研究尚显不足。

据此，本文结合烟草物流自身理化属性，通过研究凉山州烟草物流配送模式，以优化凉山州烟草物流配送线路为主要研究对象，运用电子地图以及集合覆盖理论建立模型，分析研究烟草物流配送的新方法，为烟草物流配送模式研究提供理论依据，促使跨区域配送在实践中进一步合理的应用与推广。

一、凉山烟草物流配送模式

凉山烟草公司目前在西昌市拥有6000多家卷烟零售网点，为满足全州烟草发展需求，2009年在西昌市西宁建成卷烟物流配送中心，并配有20余辆不同种类的运输车。基于凉山实际，配送中心将卷烟零售网点按区域划分，制定65条配送线路，在配送方式上采用“一访二分三送”，即采取一周一访的形式在一天内收集卷烟零售户需求订单，第二天进行分拣到户，第三天送货到户。零售卷烟客户量多且分散广泛，目前采用按区域划分配送线路具有一定的局限性，并且存在线路运输量过少或过多，容易造成配送车辆装载率低或无法满足客户需求，不能及时完成卷烟配送，因此，如何及时满足客户需求和处理不同送货线路的任务量，从而降低物流成本，提高配送效率，是凉山烟草实现烟草精益物急需解决流的主要课题之一。

二、覆盖模型和算法

（一）覆盖模型

覆盖模型，是对于需求已知的一些需求点，确定一组服务设施来满足这些需求点的需求。根据解决问题方法的不同，覆盖模型可以分为两种不同的主要模型：集合覆盖模型，用最小数量的设施去覆盖所有的需求点；最大覆盖模型，在给定数量的设施下，覆盖尽可能多的需求点。本文中通过寻找最少虚拟卷烟物流中转站，可减少配送线路，提高装载率和车辆利用率，减少资源浪费，提高配送效率，因此采用集合覆盖模型。

（二）集合覆盖模型的建立

目前，烟草物流配送体系为实现卷烟配送的全程跟踪，建立城区地理信息系统（Geography Information System，GIS），并在每辆卷烟配送车辆上都进行安装，因此：可确定卷烟配送网点中任意两点间的经济可行距离，即从物流中心或客户需求点到另一客户需求点的有效距离；根据城区的街道情况，将其划分为两个等级k={I，II}，I等级为一般道路，II等级为高速公路；在电子地图中确定物流中心及所有客户的地理位置、客户的编号和需求量等。

卷烟物流配送涉及客户数量大、范围广，在实际配送中将相对集中的客户一次配送，符合实际优化情况，因此集合处于同一路段上的零售商客户点形成需求点集，并满足以下要求：相邻需求点间的距离小设定固定值；按照就近原则，若某一路段需求点较少或相邻需求点间距离过大，可选择临近路段的需求点集。因此，需求点集的定义如下：

其中C为零售商客户点的集合，同一路段相邻客户点的距离G满足G（Gi，Gi+1）；posc表示需求点集的中间位置，其中作为需求点集的长度，取点集中相邻最远点的距离；d表示需求点集的需求量，为点集中所有客户的需求量总和。结合GIS将所有需求点集以及道路情况等信息通过图形表示，如图4所示：

图中各点集点由编号（点集需求量，到物流中心距离，道路状况）进行表示，道路情况由（需求点集间距离）进行说明。

本文卷烟配送线路优化中，寻找尽量少的虚拟物流配送中转站，因此数学模型目标函数为：

数学模型为：

其中：

N―根据路段划分的客户需求点集的集合；

M―需求点集中可称为虚拟物流中转站点集的集合；

―第i个需求点集的需求量；

―虚拟物流中转站j可提供的供给量；由于卷烟配送均由配送车辆配送，每个配送车辆都有额定装载量L，因此虚拟物流中转站可提供的最大供给量为配送车辆额定装载量的倍数，即：由于凉山烟草物流中心现配备配送车辆有15量，额定装载量为100件/车，根据实际卷烟配送情况可知，若客户需求点距离物流中心较近，可进行一天两次配送，为方便研究，本文根据需求点集的道路情况确定虚拟物流中转站的供给量分别为：k=I；k=II。

―虚拟物流中转站j可覆盖的需求点集i点的集合；

―可覆盖需求点集i的虚拟物流中转站j点的集合；

―0-1变量，表示在j点建立虚拟物流中转站，表示不在j点建立；

―需求点集i点需求中被分配给虚拟物流中转站j的比例；

―物流中心到虚拟物流中转站j的距离；

―客户需求点集i到虚拟物流中转站j的距离；

―最佳经济配送半径，依据道路等级k={I，II}确定，遵循依托一般道路k=I的送货半径为，依托高速公路k=II的送货半径为。

（三）模型求解

Step 1：初始化。令所有的，并根据道路状况和到物流中心距离确定集合和。如表3-1所示：

Step 2：选定一个虚拟物流中转站。在M中选择，且的规模为最大的点为虚拟物流中转站，即，令，并在M集合中剔除节点，即。

Step 3：确定虚拟物流中转站的配送范围。如果将中的元素按的规模从小到大的顺序指派给，直至的容量为或为空。其中对于且，将i支配给的方法为：

若，则令，

在和N中剔除需求点i。

若，则令。

Step 4：若N或M为空，则停止；否则，更新需求点集集合和虚拟物流中转站集合，转第二步。

Step 5：选取任一虚拟物流中转站M0，以物流中心作为出发点，采用Edmonds算法使配送到虚拟物流中转站覆盖的离散点客户距离最短：首先根据覆盖区域内的地理位置分布，绘制出地理结构图G如图5，如果图中所有顶点都是偶点，则从任一顶点出发每条边仅需经过一次，如果图中含有奇点则将图中所有奇点提出，并将任意两顶点相连构造新图G*，G*中边{Vi，Vj}的值为G中顶点Vi到Vj的最短距离。其次在G*中找一个最小值完美匹配M’，使G*中每个点与M’中的边关联，且M’的值最小。最后在G中将相互匹配的奇点用最短路径相连，得出G的最小新增边集。

图中P为卷烟物流中心，各顶点表示某一虚拟物流中转站中需求客户，每条边的数字为道路长度，由于卷烟配送过程中，配送车辆需将货物配送到所有零售客户手中，完成配送后再返回邮局，因此通过Edmonds算法可得出虚拟物流中转站内所需走的重复道路，选出最优配送路线。

（四）模型应用分析

以凉山州烟草专卖局（公司）所有卷烟零售网点的分布情况、道路情况以及需求量信息等为依据，通过模型的计算分析，最终得出65个虚拟物流中转站，同时对所有卷烟零售网点的配送路线重新规划，配送线路优化实施前后效果对比如表1所示。

通过对比表明，覆盖模型下的跨区域配送线路优化能有有效整合人力资源，增强物流中心的管控力度，提高送货及时率和配送服务质量，在扩大配送范围的同时能减少物流资源的浪费。

三、结束语

本文基于凉山烟草物流配送体系，通过采用集合覆盖模型，提出针对卷烟零售终端配送优化的新模型。通过模型建立，寻找虚拟卷烟物流配送中转站作为新的配送线路，最终达到提高配送车辆装载率，优化配送线路，降低物流成本，提高配送效率。

文章在优化配送线路中采用新的模型算法，从选址角度对离散多点客户进行聚类划分，与前人的研究相比，针对偏远地区道路交通状况差，配送成本高，不能及时送货到户等问题的方法研究方面进行了突破，研究方法和思路上有很大的突破，对解决大规模网点的问题上有很大的研究价值和推广前景。

参考文献：

[1]陈子侠.城市卷烟配送线路的网格划分算法[J].上海交通大学学报，2003

[2]史亚蓉，万迪P，李双燕，吕珍玉.基于GIS的物流配送路线规划研究[J].系统工程理论与实践，2009

[3]胡耀华，谷吉祥，李定军.从“1十 4 ”到“1 十3” ――GIS环境下基于P-中值模型的卷烟配送体系优化研究[J].湖南烟草，2011