覆盖模型下的跨区域配送线路优化-最新年文档

覆盖模型下的跨区域配送线路优化烟草行业面对零售客户的卷烟配送一直是烟草物流中心的 重要环节，及时满足客户需求，实现卷烟配送的高效率和低成本， 是卷烟物流配送环节中的重要部分。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的送货半 径为。（三）模型求解Stepl：初始化。令所有的，并根据道路状况和到物流中心 距离确定集合和。如表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算法可得出虚拟物流中转站内所需走的重复道路，选出最优配送路线。（四）模型应用分析以凉山州XX局（公司）所有卷烟零售网点的分布情况、道 路情况以及需求量信息等为依据，通过模型的计算分析，最终得 出65个虚拟物流中转站，同时对所有卷烟零售网点的配送路线 重新规划，配送线路优化实施前后效果对比如表1所示。通过对比表明，覆盖模型下的跨区域配送线路优化能有有效 整合人力资源，增强物流中心的管控力度，提高送货及时率和配 送服务质量，在扩大配送范围的同时能减少物流资源的浪费。三、结束语本文基于凉山烟草物流配送体系，通过采用集合覆盖模型， 提出针对卷烟零售终端配送优化的新模型。通过模型建立，寻找 虚拟卷烟物流配送中转站作为新的配送线路，最终达到提高配送 车辆装载率，优化配送线路，降低物流成本，提高配送效率。文章在优化配送线路中采用新的模型算法，从选址角度对离 散多点客户进行聚类划分，与前人的研究相比，针对偏远地区道 路交通状况差，配送成本高，不能及时送货到户等问题的方法研 究方面进行了突破，研究方法和思路上有很大的突破，对解决大 规模网点的问题上有很大的研究价值和推广前景。