杨拓论文初稿武汉烟草集团配送线路路径优化设计(最终版).doc

目目 录录 摘摘 要要 2 2 ABSTRACTABSTRACT 3 3 第第 1 1 章章 绪论绪论 4 4 1 1 选题背景 4 1 2 研究意义 5 1 3 研究内容与技术路线 5 2 2 武烟集团配送线路的现状与分析武烟集团配送线路的现状与分析 6 6 2 1 武烟集团基本情况 6 2 2 武烟集团烟草配送线路的发展现状 6 2 3 武烟集团烟草配送线路的分析 7 2 4 武烟集团配送线路存在的问题 8 第第 3 3 章章 武烟集团配送线路路径优化武烟集团配送线路路径优化 8 8 3 1 问题提出与描述 8 3 2 解决思路 9 3 3 具体实现 9 第第 4 4 章章 总结与展望总结与展望 1919 4 1 主要研究工作总结 19 4 2 未来展望 20 参考文献参考文献 2121 致致 谢谢 2222 2 摘摘 要要 随着竞争环境的变化 物流作为 第三利润源 开始逐渐被引入我国的烟草行业 其中 烟草配 送作为烟草物流系统的重要组成部分 它的发展与创新关系到烟草企业的核心竞争力 现阶段烟草企 业的核心竞争力主要由两方面构成 其一是产品技术 也就是生产国式卷烟所需的各项技术 其二就 是物流配送技术 在生产设备 原辅材料趋于同质的今天 如何做到比竞争对手更及时 更有效地满 足市场需要 已成为企业竞争的重要内容 二者相比 物流配送技术更具战略价值 然而配送线路规 划的成功与否直接影响配送的效率与成本 所以 对配送线路的优化 成为烟草企业提高核心竞争力 的重要手段 本文以武汉烟草集团配送线路作为研究对象 分析其配送线路的现状与问题 建立合理的数学模 型 实现配送路线的合理选择 优化资源配置 全面提升卷烟配送效率 降低配送成本 从而提升武 汉烟草集团市场竞争力 关键词 武烟集团 烟草配送 车辆线路优化 路径优化 3 ABSTRACT As competition environment changes logistics as third profit source gradually began to were introduced in China s tobacco industry Among them the tobacco distribution as tobacco logistics system is the important component of its development and innovation is vital to tobacco enterprise core competitiveness At present the core competitiveness of tobacco enterprises mainly by two aspects constitute one is the product technology is also the producer type cigarette all the necessary technology Second is the logistics technology the production equipment raw material tends to coessential today how to do better than the competition more seasonable more effectively meet the needs of the market has become the important content of the enterprise competition Both logistics technology compared to more strategic value But the success of distribution line planning directly influences the efficiency and cost delivery therefore the optimization of distribution lines become tobacco enterprise important means of improving the core competitive power Taking wuhan tobacco group distribution lines as the research object analyzes its present situation and problems of distribution lines establish a rational mathematical model the reasonable choice of distribution route optimize the allocation of resources improve overall cigarette distribution efficiency reduce the distribution costs and thus enhance wuhan tobacco group market competitiveness Keywords Tobacco distribution Vehicle routes optimization Path optimization 4 第第 1 1 章章 绪论绪论 1 1 选题背景 烟草行业作为国民经济发展和国家税收的重要产业之一 已成为国家重视的基础产业 物流作为 企业的第三利润源泉 是企业降低成本 提高利润的重要领域 因此 烟草物流成本理论已成为物流 分支理论中的一个热点 科学运作烟草物流配送是烟草物流成本能否得到最大程度降低的一个重要因 素 从某种意义上来说 烟草物流配送水平的高低将直接决定着烟草物流成本的高低 进而影响到烟 草企业的经济效益 随着竞争环境的变化 卷烟流通格局发生了较大的变化 尤其是经营体制的转变和个体工商户的 迅速发展 使卷烟购销经营渠道和经营方式都发生了很大的变化 相应的卷烟物流配送模式也发生了 重要改变 武烟集团作为全国知名的烟草企业 借鉴国外先进经验 结合武汉本地实际 提出了管理 与服务相结合 以服务为主的 全面访销 全面配送 专销结合 访送分离 的城市卷烟销售网络模式 并把网络路线建设作为集团工作的重中之重来抓 作为 一把手工程 发展工程 生命工程 来抓 1 2 研究意义 由于市场竞争日趋激烈 企业为了降低成本 提高自身竞争力逐渐采用 零库存 的运作方式 消费者对产品需求多样化和快速变化 企业相应必须采取 少批量 多批次 的进货和生产方式 另 外还有对企业全面质量管理的要求等等因素 这些都要求更快 更频繁地运输少量 多批次的货物 直接或间接地导致了配送成本的增加 配送成本往往占据整个物流成本的一半以上 因此 提高配送 效率具有巨大的经济效益 如何降低配送成本也因此成为一个备受关注的问题 目前 我国烟草物流配送在理论和实际运作上都严重滞后于国外发达国家 究其原因是 一方面 由于我国烟草企业长期是国营体制 大锅饭思想使得烟草企业的管理思想僵化 管理者对企业物流配 送不够重视 造成烟草物流配送发展严重滞后于烟草市场需求的扩大 另一方面 由于物流这门学科 引入中国的时间并不长 致使国内学者对烟草物流配送的理论研究严重滞后于国外同行 烟草物流配 送理论的缺失在实际企业管理中表现为 企业无法科学地规划本企业的烟草物流配送 往往凭经验去 运作企业物流配送 致使烟草物流配送成本长期居高不下 出现客户抱怨频繁等问题 因此 提高烟 草物流配送运作水平对于提高我国烟草企业核心竞争力具有重要的战略意义 而提高配送效率与降低配送成本的实现 就必须进行配送路线路径的优化 物流配送路线路径优 化是物流系统中的关键一环 对配送路线路径的优化 可以提高物流经济效益 实现物流科学化 因此 从烟草企业的层面上看 烟草配送线路的设计与优化是关系到企业经济效益实现 关系到 卷烟零售户的满意度提高 进而关系到企业核心竞争力提升和生存 发展的大问题 配送路径规划的 成功与否 将直接影响配送成本高低 工作效率快慢和服务质量优劣 关系到大物流建设的整体优势 能否实现 5 1 3 研究内容与技术路线 烟草配送线路作为联系烟草企业和消费者的纽带 是烟草物流建设的重要内容 通过对配送线路 的优化 可以有效提升烟草物流的运作水平 有力的配合我国卷烟销售网络的建设工作 有利于 电 话订货 电子结算 网上配货 现代物流 的新型卷烟经营模式在全国的推广 基于此 本文在已有 的研究基础上 通过大量现场调研 深入分析了烟草商业配送线路优化问题 并重点讨论了相应的优 化模型的构建和应用 论文主要包括以下内容 第一章 绪论 简要分析了介绍本选选题的背景和研究意义 第二章 武烟集团物流配送线路的现状与分析 第三章 针对武烟集团配送线路路径存在的问题 对其进行合理优化 选择算法 建立数学模型 求解出结果 第四章 总结与展望 总结本文主要工作 分析本文的优点和进一步解决的问题 2 武烟集团配送线路的现状与分析武烟集团配送线路的现状与分析 2 1 武烟集团基本情况 武汉烟草 集团 有限公司组建于 1995 年 是全国烟草行业 36 家重点企业之一和全行业 5 家拥 有国家级技术中心的企业之一 也是国家烟草专卖局确认的 10 重点技改企业 集团总部位于享有 九 省通衢 之称的华中重镇武汉 集团现有员工 5860 人 资产总额 73 亿元 下设武汉卷烟厂 三峡卷烟 厂 红安卷烟厂 广水卷烟厂 武烟集团核心企业武汉卷烟厂是中国历史最悠久的烟草企业之一 其 前身是创建于 1916 年的南洋兄弟烟草公司汉口分公司 集团现主要生产 红金龙 黄鹤楼 等品牌系列卷烟 与英美烟草公司合作生产 顺百利 茂大 品牌雪茄烟 是行 业内唯一一家能生产烤烟型 混合型卷烟和雪茄烟产品的企业 近年来 集团探索出 全面访销 全面配送 专销结合 访送分离 的网建模式 建立起管理信息 系统 采取统一经营行为 访销程序 批发价格和核算形式 微机联网和联销计酬办法等六个统一 规范网络运行 大大增强了网络的功能和作用 实现了卷烟销量和企业经营效益同步增长 与此同时 武汉烟草通过加大科技投入和整合人力及物流资源 集并全市 13 个区的卷烟仓库 实 行一库式数字化仓储 在卷烟销售上实行全市统一电话访销 集中收集订单和集中分拣 配送 实施 的 一库式 配送模式 使卷烟购销实现科学化 信息化和自动化管理 走在了全国同行业前列 2 2 武烟集团烟草配送线路的发展现状 1 在卷烟物流配送体系建设方面 武烟集团坚持以市场为主体的体制运作 不断优化物流业务 流程 积极推行一体化配送 不断降低运营总成本 商品采购由市级公司统一通过电子商务平台完成 6 集中一个仓库 由物流配送中心统一分拣到户 同时 结合各地交通 客户布局等客观情况 合理设 置卷烟转送点 由物流中心用箱式货车将分拣好的卷烟送至转送点 实行二级配送 2 全市统一实行了 一库制 配送 全市共设卷烟仓库 13 个 总面积达 6561 平方米 设立分 库的单位实行 一账两库 集中分拣打码 二级中转 直送到户 的方式 对分库所在区营销部原有 的仓库 按照分拣到户的要求进行了改造 3 数字化卷烟配送中心建设工作情况 武汉市数字化 一库式 卷烟配送工程于 2005 年 9 月 竣工 总投资 890 万元 全市的卷烟仓库全部集并 实行 一库式 数字化仓储 卷烟在物流配送中 心集中分拣到户 并采用 一级配 一级送 和 一级配 二级送 两种模式送货到户 目前 武汉 市烟草公司物流配送中心仓储面积 6561 平方米 能满足 1 6 万大箱卷烟的储存需求 出入库效率为 600 件 小时 选用电子标签拣选设备 分拣效率达到 7000 8000 条 小时 日分拣量达 1500 箱左右 配送服务覆盖 13 个区共 3 6 万户零售客户 2 3 武烟集团烟草配送线路的分析 按照湖北省出台的网建工作 九个统一 的工作要求 武烟集团围绕 100 集中访销 100 集中 配送 的工作目标 努力打造充满生机与活力的市场营销主体 1 统一卷烟分拣 物流配送体系的建设 各区配送中心实现了卷烟分拣 打码到户 目前 全市投入使用的半自动分拣线共 13 条 全省有 送货车 212 辆 配送线路 562 条 基本覆盖全市 各区按照确定的配送周期做到了定线路 定人员 定车辆 服务准时 2 关于物流成本 降低存货成本和商品损耗 通过对现有仓库进行改造 建设数字化仓库 实现了存储量 类别按 储位管理 尽可能做到按需调整入库量 总量库存可以加大 单品种库存可根据销售随时调整 减少 占用资金 工商协同 降低整体物流成本 市分公司实现统一大配送后 改变了过去工业企业将卷烟分送到 区的状况 工业企业根据各区公司销售计划 将卷烟整体配送到仓库 既降低了将卷烟分送到区的物 流成本 又解决了过去区级营销部少量需求供应不及时的矛盾 明显体现出统一大配送的综合效益 因地制宜 优化配送线路 降低物流成本 在建设现代物流的实践中 各区公司采取主干线路直 接配送和偏远区域分支线路二级配送相结合的方式 不断优化重组配送线路 减少人员 降低了物流 成本 卷烟配送采取第三方物流送货 降低物流成本 在大力发展集中访销配送 完善卷烟销售网络的 同时 武汉市公司灵活运用第三方物流所提供的物流配送服务和先进物流技术 不仅有利于企业发展 降低管理成本 而且能有效规避交通安全管理风险 武汉市公司在物流配送上采取第三方物流的探索 局部来看规避了一些风险和费用 但在第三方物流的选择上 要通过对物流企业的经营资质 运行成 本 特长资源 服务水平 4 个方面评估 通过招标选择承担风险能力强 营运手续完备 内部管理规 范的第三方物流企业 并签订内容全面公平 责任明确的承包合同 在日常管理上 对第三方物流企 7 业要提出相关要求 一是在分公司卷烟配送中心和基层各营销部办公地设立办公室 处理卷烟中转 送货运输工作中的协调与衔接等有关事项 避免出现以包代管的现象 二是驾驶员必须符合行业管理 要求 三是车辆 货物 司乘人员和第三责任人保险缺一不可 保险种类和保险额度必须达到要求 四是顶替车辆和驾驶员应符合双方签订的合同规定要求并承担乙方全部的责任 五是严禁无行为能力 人 限制行为能力人和无承担能力人为责任担保人 六是对双方共同确定的规定配送线路 配送承包 车辆车主或公司在承包期内无权私自转让或变更 七是车辆状况应始终保持良好 引入第三方物流后 产生的效果主要有 一是有利于降低送货作业成本 二是有利于降低安全管 理难度和送货安全风险 三是有利于企业集中精力抓好内部管理 提高市场管理质量 四是有利于适 应市场和销售量的变化 动态选择配送车辆数量 2 4 武烟集团配送线路存在的问题 1 运力不能得到充分发挥 由于武汉市十三区区域广阔 城市交通拥挤 人口密度不均 给全 市整体配送带来巨大的运输压力 不同送货线路之间存在工作量不均衡的情况 有的线路 吃不饱 而有些偏远线路送货任务繁重 送货人员和司机经常加班送货 产生一系列的安全隐患和服务质量问 题 给公司及员工的利益带来很大的影响 2 车辆调度安排不合理 由于每条线路上每次零售户需求分别不同 每次运输线路都是由司机 凭经验选择路径行驶 盲目性较大 经常走 弯路 远路 冤枉路 费力费时 3 配送车辆的满载率低 由于缺乏对客户信息的完整收集 导致车辆的配载不均衡 经常出现 半车 空等现象 直接的结果是满载率低 第第 3 章章 武烟集团配送线路路径优化武烟集团配送线路路径优化 针对武烟集团配送路线存在的问题 对其配送线路进行科学地优化和整合 对配送车辆进行合理 的调度 对线路之间的工作量进行科学的均衡 对配送线路装载率进一步合理的提高 是武烟集团烟 草配送线路优化希望达到的目标 3 1 问题提出与描述 1 已知条件 武汉的所有卷烟零售户的集合 N 为已知 N 0 1 2 n 其中 0 为配送中心 其他为卷烟零售户所在地 从配送中心出发的配送线路 经过卷烟零售户所在地之后再返回配送中心 这时 配送线路所 经过的零售户的顺序称为路线 在配送中心的配送线路的种类 数量以及每辆车最大装载能力 W 为已知 8 卷烟零售户数为 n 地理位置为已知 且每一个客户的卷烟需求量已知 i P i G i R i 1 2 n 每辆车每日最长送货时间为 k T 配送中心到各零售户点的距离及零售户之间的距离为 ij d 1 2 1 in 表示配送中心 1 2 0jn ij i 2 目标 车辆应用台数 k 各车行走路径 使总的距离最少 满载率较高 用车较少 3 约束条件 配送线路的车载量 如依维柯的车载量为 80 件 五菱之光车载量为 40 件 配送人员的工作时间 一般不超过 7 个小时 地理上相对集中的零售户由一辆送货车进行送货 送货车辆按照每天的订单数量出库 配送线路尽可能满载 每天送货线路的工作线路基本均衡 3 2 解决思路 总体思路 应用先分组后路径算法 Cluster First Route Second Method 即阶段一 对武汉 烟草配送区域进行分组 阶段二 求出最优线路 具体思路如下 阶段一 第一步 根据配送辐射半径 确定一级 二级和三级配送的区域和和配送中心 中转站 对接点 位置 以及所覆盖的零售户 第二步 根据零售户经营场所的地理环境 交通情况的不同将其划入不同的送货车辆区 如分 为依维柯车区 五菱之光车区等 第三步 采用聚类算法将同一送货车区零售网点进行划分或分组 使地理上相对集中的零售户处 于同一辆车的配送区域内 阶段二 通过求解中国邮递员问题 求解某一个配送线路的配送区域内具体的一条卷烟配送路线或次序 通过上述步骤 将 VRP 问题一步细化 分割 在满足系统优化目标的同时 提高系统运行效率 缩短系统运行时间 使方案更加可行 希冀得到一个近似的可操作的满意解 9 3 3 具体实现 3 3 1 聚类算法简介 聚类算法是一种新兴的多元统计方法 是当代分类学与多元分析的结合 聚类分析是将分类对象 置于一个多维空间中 按照其空间亲疏进行分类 通俗地讲 聚类分析就是根据事物彼此不同的属性 进行辨认 将具有相似属性的事物聚为一类 使得同一类事物具有高度的相似性 相似或不相似的度 量基于数据对象的描述的取值来确定的 通常是利用距离进行描述 常见的聚类分析方法有 1 切割的聚类方法 代表算法有 K MEANS 算法 ISODATA 算法等 2 层次的聚类方法 代表算法 CURE 算法 3 基于密度的聚类 代表算法 DBSCAN 算法等 4 基于网格的聚类 代表算法 CLIQUE 算法等 烟草行业配送线路优化需要对零售户的空间地理数据进行聚类分析 由于数据量较大 需要一个 效率高的算法 而且 K MEANS 算法适合于数据型数据 对数据输入顺序不敏感等特点 为比较适合的 一种算法 K MEANS 聚类算法的基本思路是 首先从 n 个数据 8 对象任意选择 k 个对象作为初始聚类中心 而对于所剩下其它对象 则根据它们与这些聚类中心的相似度 距离 分别将它们分配给与其最相 似的 聚类中心所代表的 聚类 然后再计算每个所获新聚类的聚类中心 该聚类中所有对象的 均值 不断重复这一过程直到所有中心都不在变化为止 k 个聚类具有以下特点 各聚类本身尽可 能的紧凑 而各聚类之间尽可能的分开 3 3 2K MEANS 聚类实现 K MEANS 聚类算法有两个关键问题需要解决 一是初始聚类中心的个数 二是初始聚类中心的位 置 1 初始聚类中心的个数 也是配送区域划分的个数 也就是为这些配送区域送货的配送线路的 台数 即 k 配送线路的台数 1 加 1 主要考虑车辆配装时不可能完全满载 送货量 车载量 2 初始聚类中心的位置 原算法是随机的 为提高聚类的效果 优化聚类的结果 依照密度的分布 对初始聚类中心优化生成 以每个零售户的地理数据点为圆心 以数据库中零售户地理信息表中所有地理数据之间距离的平 均值为半径作圆 然后根据每个圆内的数据点的密度来排序确定初始聚类中心 这样 k means 聚 类算法需要的初始中心就由以上算法生成 而无需用户进行事先指定 整个过程包括以下几个基本步 骤 1 将数据库中的每个点都看成一个类 计算所有点之间的距离 生成距离矩阵 两点之间欧式的距 10 离为 22 ij D ijij xxyy 1 2 3 i jn 2 选取 2 个正数 一般 R2 2 R1 其中 R1 为数据库中所有点之间距离的平均值 11 nn ij ij D D n n 3 以每个点为圆心 以 R1 为半径作圆 计算落在每个圆内的点数目 即样本密度 如求点的样本密 度的样本密度 iii A x y i Step1 令 0 i Step2 取判断其是否落在以以 R1 为半径的圆内 其判断方法为 111 A x y iii A x y 如上述成立 则 22 111 1 iii A AxxyyR 1ii Step3 判断是否所有点均已判断完 如果完毕 即为的样本密度 否则判断下一点 重复第二 i i A 步 4 将样本密度按从大到小的顺序排列 取密度最大者作为第一个聚类中心 Z1 选择密 度次大的数据点 若与第一凝聚点之间距离大于 R2 即 则把作为第二个 Z Z 1 Z 1 2Z ZR Z 凝聚点 Z2 否则继续判定下一密度最大者 若下一密度最大者的点与前面若干个凝聚点之间距离均大 于 R2 则将之作为又一新的凝聚点 如此反复迭代直到达到要求聚类的数目 k 5 把得到的 k 个聚类中心 Z1 Z2 Z3 Zk 作为 K MEANS 算法的初始聚类中心 我们选取武昌 这一地区的 97 户零售商 其分布如下图 图图 1 1 武昌区烟草零售户的地理坐标信息模拟武昌区烟草零售户的地理坐标信息模拟 按照上述改进后聚类算法的思路 将 97 个零售户分成八个类 即八个配送区域 11 图图 2 2 八个类的分布图 情况二 八个类的分布图 情况二 3 3 3 以车载量为限制条件对聚类结果调整 聚类完成后 还应根据车载量这个约束条件对聚类结果进行判断调整 具体实现方法为 Step1 计算每一个类内的零售户的订单量总和 Step2 判断每一类内零售户订单量总和是否超过车载量如果未超过 说明符合限制条件 如果超过车载量 选择该类中距离质心最远的点 将其拟归入距离其他类质心距离最近的类 归 入某一类前 还必须判断如归入后该类的卷烟零售户的订单量是否小于车载量 如果小于 即将该数 据归入该类 否则 选择欧氏距离再次之的类作为拟归入的类 同样判断该类卷烟零售户订货量是否 小于车载量 如果小于则归 否则选择距离再次之的 Step3 当所有的类零售户订单量总和都小于车载量时 暂告一段落 调整完毕以后 每一类的卷 烟零售户地理位置相对集中 且订单量总量小于车载重量 3 3 4 以工作量为限制条件对聚类结果调整 提出泛工作量的概念 对配送线路的工作量进行测量 并以工作量为约束条件对聚类以后的结果 进行调整 关于配送人员工作量的计算一直是物流配送中心管理工作中一个难点 难点之一在于影响配送人 员工作量的因素较多 难点之二在于各影响因素的量纲不统一 无法计算和判断 为了能更好地计算配送人员的工作量 笔者通过与配送中心管理人员 驾驶员 送货员进行广泛 接触 了解配送人员的实际工作情况 并通过实地跟车送货 提出了一个衡量配送人员工作量 包括 驾驶员和送货员 的一个概念 泛工作量 该指标综合考虑了送货里程 零售户户数 送货卷 烟量 以及零售户的结算方式 路况等因素 并且通过一定的权值 将各个影响因素均统一转化成秒 分或小时这些时间单位的数值 从而将工作量的大小以工作时间的长短来表示 能比较直观和准确地 衡量不同送货线路负荷大小 具体可以用下式来表示 12 234 1 iiiiii La Ca pa Ra HD 上式为配送线路的长度 该条配送线路上零售户数 为该条配送线路上卷烟配送量 i C i P i R 为配送线路上现金结算的零售户 D 为配送人员每天配送卷烟必须花费的固定时间 主要包括车况 i H 检查 停车入库的时间 现金交付银行 分别为 的权值 该数值 1 a 2 a 3 a 4 a i C i P i R i H 的确定主要根据对历史数据的分析以及根据笔者的实地跟车送货过程对配送人员具体工作量的分析得 出 1 系数的确定 影响系数有两个因素 一是配送线路速度理论速度 v 二是配 1 a 1 1 a bv 1 a 送道路的路况 用交通路况系数 b 来表示 路况越差 b 越小 配送时间越长 如送货车辆依维柯行 驶速度为 v 50 公里 小时 五菱之光行驶速度为 v 30 公里 小时 如果将路况分三级 必要时可以 分得更细 根据路况的不同 可以得到不同的 具体见下表 1 a 表表 1 1 系数结果系数结果 1 a 一级 政务区 二级 住宅区 三级 商业区 交通路况系数 1 b 0 80 60 4 依维柯速度 v40 公里 小时30 公里 小时20 公里 小时 五菱之光速度 v24 公里 小时18 公里 小时12 公里 小时 依维柯 1 a 0 025 0 033 0 05 五菱之光 1 a 0 0420 0560 083 配送线路的长度 即配送线路将卷烟送到其配送区域内的所有零售户门上所行驶的线路长度 它的计 算是一个比较复杂的计算 将会在下述中国邮递员问题中进行探讨 2 系数的确定 系数取决配送人员完成一个零售户配送流程的时间 按照目前的工作规范 2 a 2 a 和要求 配送人员的工作流程大致为 停车靠边 搬烟下车 步行到零售户店中 问候沟通 清点卷烟 粘贴送货票据 收取现金 步行回到车上 启动开车 其中清点卷烟的时间与 该零售户所订卷烟数量有关 将会在讨论系数时加以确定 其他各环节所用时间基本相同 该系数 3 a 可通过对历史数据或实地调查数据的采集分析得到 如根据实地调查 平均每户零售户完成这个规定 环节的工作约需两分半钟 即 系数为 1 8 分钟 户 2 a 3 系数的确定 系数由配送前装车时间和卷烟清点时间构成 每天配送前 配送 3 a 3 a 31 a 32 a 人员将卷烟人员搬运上车 所消耗的时间为装车时间 配送人员将卷烟送到零售户店中 送货员会当 着零售户的面 对卷烟数量 品种和质量以及清点核对 并请零售户在送货单上确认签字 这是卷烟 清点时间 这是清点时间 根据实地考察 平均每增加五十条卷烟 装车时间会增加 24 秒 即 0 4 31 a 13 分钟 每件 将增加清点时间 1 5 分钟 即清点系统系数为 1 5 分钟 件 3 a 0 4 1 5 1 9 32 a 分钟 件 4 系数的确定 为向现金结算户收取现金的时间 约为 2 分钟 户 以一条送货线路 4 a 4 a 4 a 为例 该送货线路送货车型为依维柯 其 2008 年 11 月送货数量 52436 条 送货零售户 1625 户 其中现金结算户 487 户 目前电子结算户占零售户的比率约 70 送货里程 946 公里 其中一级 路况 206 公里 二级路况 510 公里 三级路况 230 公里 有效工作日 22 天 该送货线路全月 工作量约为 1234 20193412 5 1992 569744408838 06 147 3 iiiii LaCa pa Ra HD 分钟小时 该送货线路平均每天工作量约为 L 22 147 3 22 6 7 小时 这与实际工作情况基本相符 目L 前各送货线路上的送货时间一般为 6 7 小时 进一步印证上述计算工作量的方法的可行性 通过增加 上述两个限制条件 聚类结果调整为下图 图图 3 3 调整后的聚类调整后的聚类 通过 K MENAS 聚类 再加上车载量和工作量这两个限制条件对聚类结果进行整后 配送区域划分 完成 在一个配送区域内如何求得该配送区域的最优行车路线 使得卷烟送货车沿着这条行车路线能 将卷烟送到每一个零售户手中 而且所走的路程最短 这是一个求解多点之间的最优化路线问题 对于多点之间的最优化路线的计算有很多方法 其中中国邮递员问题是解决多点之间的最优化路 线比较好的模型之一 中国邮递员问题解决的是边遍行问题 求的是欧拉回路 具体到烟草配送实际 对于某一个配送区域 零售户的经营场所是固定分布在街道上 如果配送线路能以最优的路线遍行零 售户所位处的街道上 即能完成送货任务 这是一个求解欧拉回路的中国邮递员问题 因此 用中国 14 邮递员问题模型来求解某一个配送区域的最优配送线路是比较合适的 用数学的语言来描述就是一个配送区域内的最优线路求解问题 如果把配送区域内街道用一条边 街道的长度用边权 w来表示 物流配送中心 街道交叉口用点表示 那么一个卷 j vv i j vv i 烟配送区域就构成一个边权连通无向图 配送区域内最优线路的问题用图论的语言来描述 就是在一 个边权连通无向图中 怎么寻找一个回路 C 使得 C 至少经过每条边一次且 C 的长度最短 这里我们选取洪山区这一聚类 描绘出分布图 以 A 点为物流配送中心 V1 至 V11 为街道的交 叉口 如下图所示 图 4 洪山区烟草零售商分布图 15 图图 5 5 聚类的模拟图聚类的模拟图 如果能寻找一个回路 C 使得 C 至少经过每条边一次且 C 的长度最短 C 即是该配送区域的最 优送货线路 关于中国邮递员问题的基本解题在上文已作了具体的描述 对于一般的边权连通无向图 求解欧拉回路的关键在于就是求奇次点对最小权完美匹配 3 3 6 最优路线的确定 将求 G 奇次点的最小权完美匹配问题 可转化为指派问题来解 指派问题是运筹学中一个基本问题 是指管理部门可能经常面临这样的问题 有若干项任务需要 完成 又有若干对象能够完成其中每项任务 由于每个对象的特点与能力不同 完成各项任务的效益 也各不相同 又因任务性质的要求或管理上的需要等缘故 每项任务只能交给一个对象去完成 则应 指派哪个对象去完成哪项任务 能够使完成任务的总效益最佳 这类问题就称为指派问题或分配问题 指派问题中 人与任务之间是一对 每一对都有一定的消耗 最终要求解使总消耗为最少的人与任务 的配对 同样 奇次点间也是一对对的 每对间的距离即是消耗 最终要求解的就是使总距离为最少 的奇点对 效率矩阵就是由奇点对间的距离组成的 此时就将此问题转化成求解指派问题 1 找出奇点及奇点数 设一般配送区域线路优化问题均可找到对应的无向图为 G V E 设图 G Vn Em 有个奇点 分别记为 由图的知识知 r 为偶数 在本实例中 配送区域对应的无向图 12 kkkr vvv 如下 16 图图 6 6 配送区域对应的无向图配送区域对应的无向图 表表 2 2 各点对应的度数值各点对应的度数值 点 V1V2V3V4V5V6V7V8V9V10V11V12A 度数 3233232334332 选取 8 个奇点 分别为 为了计算方便 边的长度不是一个绝对值 按 1346891112 v v v v v v vv 照一定的比例缩小的整数值 实际应用进行一定比例的放大即可 2 求出各个奇点的最短距离 利用 Floyd 方法 求出各个奇顶点与之间的最短距离 同时将各奇点两两之间的最短距离 i v j v 也一并求出 记表示奇点与之间的最短距离 记 F 显然 F 为对称矩阵 本例为 ij f mi v mj v ijr r f 17 这个矩阵就是指派问题中的效益矩阵 3 找出各个奇点的两两配对的最优匹配方案 设矩阵其中 为最小指派问题的系数矩阵 ijr r Cc ij ij fij c ij 解决指派问题的一个重要的方法是匈牙利法 Hungry 法 这种方法是由匈牙利数学家考尼格 Konig 提出的 因此得名匈牙利法 匈牙利算法的理论依据是根据考尼格提出并证明了的 两个定理 定理 1 设一个指派问题的效益矩阵为 若从的第 i 行元素中减去一个数cij n cij 从第 j 列中减去一个常数 得到一个新的效益矩阵 1 2 i u im 1 2 j vjn ij b 其中每一元素 则问题的最优解也是问题的最优解 21 ijijij bcuv ij bcij n 定理 2 若一方阵中的一部分元素为 0 一部分元素为非 0 由覆盖方阵内所有 0 元的最少 直线数恰好等于那些位于不同行 不同列的 0 的最多个数 21 用该法可求出为本例的最优解 即 为独立的 8 个 0 元 即最小指派解对应的系数和为 17233248566571 84 o o o o o o o o 18 1723324856657184 2 1 1 3 1 12314cccccccc 所以为该配送区域邮路问题的奇点最优配对方案 即选择 配对 配对 17234856 ffff 111 v v 34 v v 配对 配对 配对所得的最小和为 612 v v 89 v v 17234856 7ffff 4 为各个配送奇点的最短径加边 图图 6 6 加边后的最短路经加边后的最短路经 在邮路图中对每个配对奇点之间按照最短路径添加重复边 得到 此图中已没有奇点 G 5 从配送中心出 A 发 找出欧拉回路 此 1112434561267 vvvvvvvvvv 89101189 vvvvvvA 回路即为该配送区域内的最短路径 总路径为 55 下图为送货车的送货顺序图 19 图图 7 7 送货顺序送货顺序 模拟送货车的实际送货路线 从配送中心 A 出发 给零售户 90 送货 到达路口 给零售户 89 送货 到达路口 给零售 1 v 2 v 户 87 送货 到达路口 给零售户 84 送货 到达路口 给零售户 85 送货 到达 路口 3 v 10 v 1 v 再到路口 给零售户 83 送货 到达 路口 给零售户 82 送货 到达路口 给零售户 10 v 11 v 12 v 79 送货 到达 路口 给零售户 88 送货 到达路口 再到 路口 给零售户 73 送货 4 v 3 v 4 v 到达路口 给零售户 72 送货 到达路口 给零售户 78 送货 到达 路口 再到路口 5 v 6 v 12 v 6 v 给零售户 76 送货 到达路口 给零售户 77 送货 到达路口 给零售户 81 送货 到达 7 v 8 v 路口 给零售户 86 送货 到达路口 再到 路口 给零售户 80 送货 到达路口 再 9 v 10 v 11 v 8 v 到路口 给零售户 91 送货 最后回配送中心 完成了对些配送区域内 18 位卷烟零售户的送 9 v 货任务 总送货路程 2 5 1 5 1 1 1 3 4 1 1 3 4 3 3 6 3 1 2 1 2 1 1 55 用此方法 可以 求出所有配送区域内所有送货车辆的最短行驶路线 20 第第 4 章章 总结与展望总结与展望 4 1 主要研究工作总结 综上所述 本文对武汉市烟草集团烟草配送线路的优化问题提出了一个比较完整的解决方案 该方案具有以下优点 首先 实现了车辆的合理调度 减少不必要的出车次数 配送中心每天根据配送当天的订货 量以及配送线路的型号来决定配送线路出动的数目 在 K MEAN 聚类分析中 按照的 1 订货量 车载量 方法求出 K 值 K 既是聚集点的个数 也是送货车辆出动的数量 如果按照 30000 箱的年销售 量 80 件的车载量 11 条配送线路来计算 平均每天出动的配送线路为 辆 全年预计可减少出车次数 30000 250 1 7 47 18 12 20 92 80 50 车次 减少送货 1506 人次 11 8 20 92 12 753 12 其次 提高车辆满载率 通过出车次数的减少 必然提高每辆车的满载率 如果以每天平均 8 辆的出车数来计算 车辆满载率为 远远高于现在的配送线 30000 250 93 36 8 12 20 92 80 50 路满载率 30000 250 67 90 11 12 20 92 80 50 第三 实现了配送线路送货线路的最优化生成 通过 K MEANS 聚类算法形成配送区域 再利 用指派问题求解 CPP 问题得到每一个配送区域内的最优线路 使每一辆配送线路能按照优化的 配送线路行驶送货 有效缩短了行车里程 避免走重复路 回头路 同时为零售户的送货服务更 及时 该解决方案科学合理 结构严谨 层层紧扣 通过四步将 VRP 问题层层分解 细化 减小问 题规模 得到可行解 一是在配送区域划分采用了 K MEANS 方法 并对初始聚类点的确定方法进 行优化改进 使聚类结果更加合理 效率更高 二是在配送区域划分时加上工作量和车载量两个 约束条件 使最终结果真正有实用价值 三是在求解配送区域内的多点最优线路问题时 将其转 化 CPP 问题 通过求解欧拉回路来求解最优线路 四是在求解 CPP 问题时将其转化成指派问题 来求解 总的来说 应用上述方法对武汉烟草集团烟草物流配送线路进行优化 可以科学地规划配送 线路 使线路最优 合理地调度车辆 使满载率提高 有效地加强内部管理 使管理成本降低 对于实现 低成本 高效率 优服务 的烟草物流建设目标是一个很好的推动 4 2 未来展望 本论文仅对物流配送线路优化问题进行了初步的研究 所获得的成果还很不完善 还有大量工作 21 需要去做 主要体现在 1 考虑烟草品种的类别 本研究仅考虑客户需求的货物重量 并没有考虑具体的货物类别 而实 际上随着经济的发展 消费多样化 要求多样化 的新观念逐渐形成 多品种 少批量的配送方式 必