中烟工业毕节卷烟厂配送路线优化毕业论文(编辑修改稿)

中烟工业毕节卷烟厂配送路线优化毕业论文(编辑修改稿)内容摘要：

总配送中心在七星关区，由该总库向旗下的七个分库进行配送，再由七个分库的配送中心将卷烟送往各地的零售商。 如图 2所示： 图 2:毕节市及各县地图 来源：百度地图 随着社会经济水平的提高，以及各种交叉因素的影响，该市各地对香烟的需求量不断增大。 现今该厂实行每日定点定量配送。 需求量大的县市日需求量达到了 300 多件，而需求量小的县市仅为 50 多件。 该厂现拥有 4辆 5t 的配送货车，3 辆 2t的货车， 5t 货车可装卷烟 330 件， 2t 货车可装卷烟 120 件，每件卷烟约淮海工学院二〇一三届本科毕业论文 第 6 页 共 20 页 15kg，所以当货车装满时仍然不会超重。 现在该厂采用的是“点到点”的直接配送模式．共需 7 辆货车运行 8车次。 毕节卷烟厂物流配送存在的 问题 现在该厂采用的是“点到点”的直接配送模式。 其配送模式如图 3 所示．共需 7 辆货车 8车次。 在对该厂个配送路线进行数据综合分析之后发现，该厂的运输过程所产生的成本费用占据了配送过程中的百分之七十以上。 由于该厂每日都会配送大量的货物，也就必定会产生巨大的资源浪费。 经综合分析发现该厂所采用的配送模式的主要缺陷在于： (1)配送线路选择不够合理，没有得到优化，导致配送成本过大； (2)采用这种配送方式使得剩余货运量在进行直接配送时出现货车装不满，造成资源浪费，导致配送成本进一步加大，严重影响该厂的效益． 图 3：毕节卷烟厂现在配送路线图 由以上数据可以分析得出毕节卷烟厂物流配送中运输运输路线的不合理，因此合理安排运输路线可以极大的提高其车辆的使用率和节约成本。 显然，为了实现以上目标，就要对配送过程进行合理规划，这一点可以通过改进运输方式、进行线路规划等来实现。 4 0 3 2 1 6 5 7 淮海工学院二〇一三届本科毕业论文 第 7 页 共 20 页 4 毕节卷烟厂配送路线优化分析 物流配送路线优化模型及方法描述 VRP 模型 (1)模型提出。 配送是物流活动的重要环节。 从烟草企业的角度上看，烟草配送直接关系到企业经济效 益的好坏和核心竞争力的强弱。 配送线路规划是否合理，也将直接影响配送成本高低、工作效率快慢和服务质量优劣。 物流配送线路优化问题，主要是以线路最优化为目标的车辆调度问题，即 VRP 问题，该类问题的实质是在确定的需求下，如何对一个确定的客户集合安排车辆、行驶路线和时间，使得总的行使里程数最小，总费用最少。 配送车辆调度问题（ VRP），最早是由 Dantzig 和 Ramser 于 1959 年首次提出的，自此很快引起运筹学、应用数学、物流科学、计算机应用等学科的专家与运输计划的设计者和管理者的极大重视，成为运 筹学与组合优化领域的前沿与研究热点问题。 线路优化问题的常用算法，基本上分为精确算法和启发式算法两大类。 由于 VRP 问题是 NP 困难问题，而寻找近似算法更适合于实际情况，因此启发式算法就成了备受关注的解决方法。 目前，绝大部分这方面的研究成果也都对启发式算法的设计或改进做了新的开拓。 针对本文研究的问题，如何对配送线路进行科学地优化和整合，对配送车辆进行合理的调度、对线路之间的工作量进行科学的均衡，对配送车辆装载率进一步合理的提高，也是烟草配送线路优化希望达到的目标。 (2)多回路运输 —— VRP 模型。 多回路运输问题是目前很普遍的一种调配问题，尤其对于有多数服务对象的实体，例如一个拥有多客户的企业。 此类调配的核心问题是如何对车辆进行调度。 因此， VRP（ Vehicle Routing Problem）模型也应运而生，成了解决多回路问题的一个相当成功的模型。 该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、车辆容量限制，行驶里程限制等），达到一定的优化目标（如里程最短，费用最小，时间尽量少等）。 它涉及了多辆交通工具的服务对象的选择和路径 确定两方面问题。 一个典型的 VRP 模型可以如下表述： ①基本条件 现有 m 辆相同的车辆停在一个共同的源点 0v ，它需给 n个客户提供货物，顾客为 1 2 n,v v v、 … ，。 ②模型目标 确定所需的车辆数 N，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使总费用最小。 ③限制条件： N 不大于 m；每一个订单都要完成；每辆车完成任务后都要回淮海工学院二〇一三届本科毕业论文 第 8 页 共 20 页 到源点 0v ；车辆的容量限制不能超过；特殊问题还需 考虑时窗限制；运输规章限制。 节约算法基本原理及主要步骤 (1)节约算法（ Saving Algorithm）是用来解决运输车辆数目不确定的 VRP问题，它是目前用来解决 VRP 模型最有名的启发式算法。 (2)节约算法的核心思想是将运输问题中存在的两个回路（ 0，„ ， i， 0）和（ 0， j，„ ， 0）合并成一个回路（ 0，„ ， i， j，„， 0）。 在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运输距离。 相应的变化值，叫做节约距离 ijC ，如式①所示。 ij io oj jiC c c c    ① 调整过程如图 4 所示。 调整前 调整后 图 4：节约算法的图像描述 已知条件 :需求点集 RN ={1,2,„ , n},各点需求量 iR ,各点间最短距离 ijc。 第一步 ,形成一个初始解。 确定各车辆配送点集 12, , , mI I I 令 jIj , j =1,2,„ ,n (先采取单点配送 )。 第二步 ,进行节约度的计算。 计算所有点对的节约度 ijC ，然后对计算结果进行升序排列。 第三步，对回路进行合并。 从节约值中的最大的值开始，直到节约里程0 j i 0 j i 淮海工学院二〇一三届本科毕业论文 第 9 页 共 20 页 的队列空为止 ,重复下列步骤 :按照节约里程 队列从大到小的顺序 ,分析客户 i 和 j 之间合并的可能性 (是否满足装载限制条件、不在同一路径内以及合并次数不超过 2),将 i, j 连接起来 ,即可令。 i i j jI I I I    。 如果不是这样 ,则从节约里程队列中去除当前的节约里程，分析下一个客户对。 改进后的最近插入法 (1)TSP 模型是单回路运输问题中的最为典型的一个模型， (全称 :Traveling Salesman Problem1)，中文名称做旅行商问题。 它是一个典型的 NP 难题，在大规模的线路优化问题中无法利用它求得最优解。 而最近插入法就是一种解决此问题的启发式算法。 最近插入法是 Rosenkrantz 和 Stearns 等人在 1977 年提出的一种用于解决TSP(旅行商 )问题的算法。 最近插入法由四步完成： ①找到 0ic 最小的节点 iv ，形成一个子回路（ subtour），  00,kT v v v。 ②在剩下的节点中，寻找一个离子回路中某一节点最近的节点 kv。 ③在子回路中找到一条路径（ i， j） ,使得 ikc +kjc ijc 最小，然后将节点 iv 插入到节点 iv ， jv 之间，用两条新的路径 (i， k)，（ k， j）代替原来的路径（ i， j），并将节点 kv 加入到子回路中。 ④重复步骤②、③，直到所有的节点都加入到子回路中。 这样，子回路就演变为了一个 TSP 的解。 (2)由于最近插入法解决的是同一回路运输问题，因此，本文在此方法基础上对其进行改进和修正，以便能解决多回路运输 VRP 问题。 有改进的方法如下： ①找到 0ic 最小的节点 iv ，形成一个子回路（ subtour），  00,kT v v v。 ②在剩下的节点中，寻找一个离子回路中某一节点最近的节点 kv。 若此时回路的总货运量未超过车的载重限制，则继续步骤③。 否则，转①寻找新的一条回路。 ③在子回路中找到一条路径（ i， j） ,使得 ikc +kjc ijc 最小，然后将节点 iv 插入到节点 iv ， jv 之间，用两条新的路径 (i， k)，（ k， j）代替原来的路径（ i， j），并将节点 kv 加入到子回路中。 若此时该回路的总路程为未超过车辆的行程限制，则继续步骤④。 否则转步骤①，寻找新的一条回路。 淮海工学院二〇一三届本科毕业论文 第 10 页 共 20 页 ④重复步骤①和③，直到每一个节点都被归入某一个子回路中。 配送路线优化研究 建立 VRP 模型 利用多回路运输问题解决经济生活中出现的问题，这在如今的世界中已成为一项重要的科学成果和生活成果。 此类调配问题的核心问题仍是车辆调度，因而，据此对贵州中烟工业毕节卷烟厂的配送系统建立 VRP 模型。 基本条件：毕节卷烟厂需给旗下的 7 个分库送货，代号依次为 1,2,3,…… 6,7,毕节卷烟厂现拥有 5T 货车 4 辆， 2T货车 3 辆， 5T货。