安吉物流配送网点的选址和路线优化

安吉物流配送网点的选址和路线优化安吉物流配送网点的选址和路线优化 班级 班级 姓名 姓名 学号 学号 指导老师 指导老师 安吉物流配送网点的选址和路线优化 2 目录目录 一 概述 2 二 物流网络节点的选址 3 一 选址影响因素 3 二 物流网络选址流程 4 三 物流网络节点的选址方法 5 1 基本解析法 5 2 重心法模型 6 三 配送路线的优化 6 一 节约里程法 7 1 节约里程法的基本规定 7 节约里程法的步骤 8 二 遗传算法 10 1 问题的描述 10 2 遗传算法的设计 10 四 总结 11 安吉物流配送网点的选址和路线优化 3 安吉物流配送网点的选址和路线优化安吉物流配送网点的选址和路线优化 一 概述一 概述 随着我国经济的快速发展 国民经济多物流业的要求逐渐提高 需求越来 越个性化 特殊化和专业化 传统的物流服务已经很难满足经济的现代化需求 在传统的仓储服务 运输服务和其他单功能的服务模式逐渐的被淘汰下去 现 在很多企业 包括生产企业 零售企业和服务行业都开始使用配送中心这种多 功能服务模式来提高企业自身的竞争力 所谓配送中心是指接受并处理末端用户的订货信息 对上游运来的多品种 货物进行分拣 根据用户订货要求进行拣选 加工 组配等作业 并进行送货 的设施和机构 是从供应者手中接受多种大量的货物 进行倒装 分类 保管 流通加工和情报处理等作业 然后按照众多需要者的订货要求备齐货物 以令 人满意的服务水平进行配送的设施 由于大多制造业 都采用集中生产后通路分销的模式 物流需要负责将商 品从生产工厂输送到消费市场的终端 所依靠的实体系统就是所谓的物流网络 系统 常见的模式有 模式一 工厂 RDC 销售终端 模式二 工厂 RDC FDC 销售终端 上述中的 RDC 就是区域物流中心 FDC 是指前进物流中心 每种节点尤其 自己的作用和分工 从 DC 的分工来看 RDC 起到配运核心作用 而 FDC 常为季 节性使用 起作用为临时囤货 以在销售旺季或者交通不便季节可以及时对销 售终端供货 从上述可以看出配送中心的作用非常明显 但是配送中心的建设是对一个 企业来讲至关重要的 首先 配送中心的建设是件大的工程可能花费企业的大 量资金 再者配送中心是用来增加企业的配送能力提高其快速反应能力 所以 对公司来讲最重要的就是如何正确的给配送中心选址问题 安吉物流公司简介 上汽集团是国内领先的汽车制造企业 最大的乘用车制造商和销量最高的 汽车生产商 2011年 上汽集团整车销量突破400万辆 同比增长12 市场占 有率更是达到21 蝉联国内汽车集团首位 上海汽车作为上汽集团的下属自主 品牌 目前拥有两大生产基地 分别是上海南汇临港基地和南京浦口基地 其 中上海基地生产车型为荣威A 南京生产的车型为荣威B 上海工厂生产出来的 汽车存储在临港库 库容为12000台 南京工厂生产出来的汽车存储在南京库 库容为6000台 作为上汽集团全资子公司 安吉物流承担着上海汽车两大基地商品车的运 输业务 负责为客户提供点对点的运输服务 公司根据订单的具体要求 选择 合适的运输方式和路线 从上海或南京的仓库发货 目前安吉物流配送城市覆 盖全国大部分地区 在案例六中我们可以很清楚的知道安吉物流公司所承担的物流任务和运输 安吉物流配送网点的选址和路线优化 4 方向以及运输服务范围 如下图所示 上汽的生产基地仅有两个 上海和南京 而且这两个生产基地的距离非常 的近 需要配送的目的地却是十分的分散 有沈阳 银川 西宁 成都 昆明 以及南宁和广州等城市 这么多配送点如果没有很好地配送中心进行协调的话 运输成本一定会很高 而且也会降低上汽的快速反应能力 所以配送中心的选 址是非常重要的 二 物流网络节点的选址二 物流网络节点的选址 一 选址影响因素 一 选址影响因素 物流网络节点的选址是一个复杂的过程 既要考虑市场因素 又要考虑到 当地的交通条件气候情况等 一般的选址过程中考虑的因素包括以下几个方面 1 1 土地成本 配送中心的成本中心 占重要一部分的是土地的成本 每个不同地段土地 的成本都不一样 所以地价的高低直接影响到配送中心的选址和网络布局 同 时 不同地区的经济发展规划不同 有的地区鼓励物流业发展 这种情况企业 就可以以比较低廉的价格获得想要的土地 2 交通条件 安吉物流配送网点的选址和路线优化 5 配送中心的成本中出入库的运输成本约占总成本的 50 60 交通运输 情况直接影响到配送中心的运营情况 交通顺畅则配送中心就运营红火 交通 情况很糟糕的话就会对配送中心的设施造成很大的浪费 所以 配送中心的选 址最好是靠近交通枢纽 最好点的就是交通主干道枢纽 铁路编组站或机场等 3 自然条件 配送中心是大量的商品集结地 需要储存大量的堆码很高的货物 会对地 面造成很大的压力 如果配送中心下面是松软的淤泥等不太好的土质的话 地 面就会由于重压而下沉等现象 还有其他的一些自然条件比如 气候 港口水 位等等 4 土地可得性 配送中心建设时还要考虑到今后配送中心的可扩展性 所以 所以规划配 送中心时 还要考虑在规划区域内能否获得足够的土地面积 5 人力成本 每个行业人才是必不可少的 所以对于配送中心这种多功能的网络节点来讲 人才更是重要的 并且要求也是越来越专业 因此在规划配送中心时 也是要 考虑人力的资源成本 6 服务水平 在现代物流中 能否实现及时准时配送时现代物流服务中服务水平高低的 重要指标 因此 在物流网络选址时 要充分考虑到快速有效地为客户提供高 质量的配送服务 7 基础设施的完善 配送中心的所在地 除了道路畅通之外 还要考虑其他的一些因素 比如 说 供水 供电 燃气等等是否配套 二 物流网络选址流程 二 物流网络选址流程 配送中心选址决策包括几个层次的筛选 是一个慢慢缩小范围的过程 更 为具体的选择过程如下 2 1 收集整理资料 通过对历史资料的收集和整理 可以获得关于物流系统现状的认识 以确 定配送中心服务对象的需求条件 并初步确定配送中心的选址原则 获得准确 的第一手资料对后续备选地址的选择及定量化模型的设计均有重要作用 2 选定备选地址 在进行配送中心位置选择时 首先要根据上述个影响因素进行定性分析和 审慎评估 大致确定出几个备选地址 在确定备选地址时首先要确定地区范围 如在世界范围内选择 首先确定某个国家 在确定某个省份 最后是进一步将 位置确定在某个城市或商业地区 备选地址的选择是否恰当 将直接影响到后续对最优方案的确定 备选地 址过多 后续优化方案的工作量将过大 成本高 备选方案过少 可能导致最 后的方案远离最优方案 选址效果差 所以合适的备选地址的确定是配送中心 选址及网点布局中非常关键的一步 3 优化备选方案 在备选方案确定后 最后一步要做的就是更详细的考察若干个具体地址 安吉物流配送网点的选址和路线优化 6 可以在此基础上建立数学模型 通过定量化计算 得到最优后的地址 近年来 选址理论发展迅速 计算机技术也得到广泛应用 这些发展都为定量化选址方 法的研究提供了有力的支持 目前已有多种优化选址方法被开发出来 4 优化结果复查 由于在定量分析中主要考察对选址产生影响的经济性因素 所以当直接应用定量模型 得出结果进行物流配送中心选址时 常常会发现在经济上最为可取的选址地点在实际上却 行不通 这是因为除了经济型因素以外 还有很多非经济因素影响物流配送中心坐落地点 的确定 如自然条件 劳动力因素等 因此 在这一步骤里要考虑其他非经济性因素考虑 进去 如综合地理 地形 环境 交通 劳动力 以及有关法规等条件 对优化结果进行 评价 看优化结果是否具有现实可行性 复查时 要将各项影响因素根据它们的影响程度赋予相应的权重 采用加 权法进行复查 5 确定最终方案 如果优化方案结果通过复查 即可将优化结果作为最终方案 如果没有通 过复查 则重新返回第二步 进行备选地址筛选 优化备选地址 复查等一系 列步骤 直至最终得到结果 三 物流网络节点的选址方法 三 物流网络节点的选址方法 1 1 基本解析法 基本解析法 基本解析法就是指物理地理重心方法 这种方法通常只考虑运输成本对配 送中心选址影响 而运输成本一般是运输需求量 距离及时间的函数 所以解 析方法根据距离 需求量 时间或者三者的结合 通过在坐标上显示 已配送 中心位置为因变量 用代数方法来求解物流中心坐标 基本解析方法考虑影响因素较少 模型简单 主要适用于单个物流中心选 址问题 对于复杂的选址问题 解析方法常常感到困难 通常需要借助其他更 为综合的分析技术和方法 基本解析方法只考虑与运输成本相关的需求量 距离或时间三者中的某一 个变量 来解释出使运输成本最低的物流配送中心的坐标 当只考虑距离时 基本解析方法可以被称为距离重心法 距离重心法的思 想是通过不断反复才能得到一个不断改进的配送中心位置 由于是单一设施法 所以配送中心的运营成本固定不变 而运输费用随距离而变化 建设成本可以 是为固定不变 因此可以只考虑在不同地点设置配送中心因与各用户距离变化 而引起运输费用的变化 找出令运输总费用最小的点 并将其作为最佳设施做 落点 假设所要求的物流中心坐标是 Xd Yd 则物流配送中心到用户 j 的运输 费用为 AjDj aj 为运输费率 Dj 为配送中心至各用户 j 的直线运输距离 此时 总运费 其中 3 现在要求 Xd Yj 为何止时使得总运费 T 最小 当然这种选址方法对于安吉物流公司物流配送中心来讲不太好 就上图可 安吉物流配送网点的选址和路线优化 7 以看出其目标城市的坐标不太选 基坐标的选择就存在难题 2 2 重心法模型 重心法模型 定量分析是通过数学模型计算分析最优的配送位置 配送中心的选址会因为选址范围 和选址数量不同 计算的数学模型也不相同 如多配送中心向多客户配送与单一的配送中 心向多客户配送及单一配送中心向单一客户配送所采用的模型就各不相同 这里将介绍单 一物流配送中心向多客户配送及的重心法模型 重心法模型公式如下 式中 运输费率 物流量 配送中心到客户的直线距离 H 配送总成本 由于该方法包含了距离变量 所以需要使用迭代法求解 1 不考虑距离因素时利用公式 求的 x 值和 y 值 代入距离模型和成本模型中 求出初始成本 2 代入重心法模型中 求出改善后的坐标 代入距离模型和成本模型中 求出总成本 3 比较初始成本和总成本 如果大于则说明改善后的坐标是最优解 否则继续 迭代 直至改善空间已经非常小可忽略不计 则最后迭代的结果即为近似最 优解 如案例六中 要选出两个配送中心 可以在初步的筛选的基础上 通过假设武 汉 济南或者天津等为待选配送中心 利用重心法可以进行简单的处理等 三 配送路线的优化三 配送路线的优化 配送中心的选址很重要 但是在配送中心选定之后 对于物流公司来说还 有一个非常重要的事情要做 配送中心配送线路的优化 从配送中心到目的 地有很多种路径可走 而每种路径由于状况 距离以及其他一些不定因素的影 响 所话费的时间会不同 成本当然也不尽相同 对于一个物流公司来讲 在 安吉物流配送网点的选址和路线优化 8 一定服务水平下 成本最低才是企业最终的目标 配送运输由于配送方法的不同 其运输过程也不尽相同 影响配送运输的 因素很多 如车流量的变化 道路状况 客户的分布状况和配送中心的选址 道路交通网 车辆定额载重量以及车辆运行限制等 配送线路设计就是整合影 响配送运输的各种因素 适时适当地利用现有的运输工具和道路状况 及时 安全 方便 经济地将客户所需的商品准确地送达客户手中 在配送运输线路 设计中 需根据不同客户群的特点和要求 选择不同的线路设计方法 最终达 到节省时间 运距和降低配送运输成本的目的 下面介绍几种配送路线优化的常用方法 一 节约里程法 一 节约里程法 节约里程法又称节约算法或节约法 是指用来解决运输车辆数目不确定 的 VRP 问题的最有名的启发式算法 1 1 节约里程法的基本规定 节约里程法的基本规定 利用节约法确定配送路线的主要出发点是 根据配送中心的运输能力和 配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公 里数最小的配送方案 另还需满足以下条件 1 所有用户的要求 2 不使任何一辆车超载 3 每辆车每天的总运行时间或行驶里程不超过规定的上限 4 用户到货时间要求 基本思想 为达到高效率的配送 使配送的时间最小距离最短成本最低 而寻找的最佳配送路线 节约里程法的基本思路 4 如图 设 为配送中心 和 为配送点 即客户 到 或 的距离分别为 两个配送点之间的距离为 现有两种送货方案 即 向 分别送货和 向 同时送货 对 比这两种方案 可得出 方案 的配送路线为 配 送距离为 方案 的配送路线为 配送距离为 显然 由三角形的几何性质可得 方案 安吉物流配送网点的选址和路线优化 9 优于方案 其中 为节约里程量 节约里程法的步骤 节约里程法的步骤 基于节约里程法的基本思路 在配送网络中 通过合理的车辆调度和最 短的路线选择 尽量使运输车辆多载 尽量节约总配送时间和总配送里程 具体步骤如下 计算各配送点间最短路径 一般通过狄克斯特拉 算 法计算 进行节约里程的计算 即两个配送点之间的节约里程为这两个配送点分别 到配送中心的最短路径之和减去两个配送点之间的最短距离 对节约里程进行降序排序 形成初始解 在满足车辆限载 客户需求量大小 时间限制 客户所在地 理位置等所有条件下 根据第一步所得的最短路径对配送点进行一对一直达 式配送 得到所需配送车辆和行程 进行回路的合并 得出配送优化方案 从节约里程排序表找出产生 该节约里程的两个配送点 再判断连接 的回路是否存在合并的 可能性 如果一个回路以 开始 一个回路以 结束 且 满足需求量和车载量等约束条件 则该回路可以合并 并进行下面的合并操 作 删除两个回路中的部分路径 和 然后引入新的连 接 得到新的回路 重复上述过程 直至没有可以合并的回路 从而得出配送优化方案 确定最优方案 重复上一步的合并过程 得出多个优化方案 并对得出的 优化方案进行比较 得出最终优化方案 假设前面物流中心的选址是武汉和天津 那么对应的配送中心A就是武 汉和天津 B和C则是其他的目的城市 如北京 成都 石家庄 郑州 兰州 和昆明等 首先计算出配送中心到各个配送网点的实际路程距离 然后列出 各个节点间的最近距离 如下图所示 安吉物流配送网点的选址和路线优化 10 再由上述节约里程法的基本原理计算出各个节点之间的节约路程从中选 出最长的节约路程 如下所示 根据表2对上述中节约的里程进行从大到小进行排列 确定出最初的配 送路线方案 再进行回路合并 并且要严格按照实际限制条件进行合并 不如货车的 在中极限不能超载 货车最远运输距离不能超过等等现实意义的约束条件 逐层进行优化直至找到最优路线为止 这样就能很好的解决配送问题 安吉物流公司在进行配送网点的选址和配送路线的优化之后 使得服务水平 不变的情况下公司的物流成本有了很大的降低 反应速度得到很高的提升等 安吉物流配送网点的选址和路线优化 11 二 遗传算法 二 遗传算法 所谓遗传算法是指 一类借鉴生物界的进化规律 适者生存 优胜劣汰 遗传机制 演化而来的 随机化搜索方法 它是由 美国的J Holland教授1975 年首先提出 其主要特点是直接对结构对象进行操作 不存在求导和函数 连续性的限定 具有内在的隐并行性和更好的全局寻优能力 采用概率化 的寻优方法 能自动获取和 指导优化的搜索 空间 自适应地调整搜索方向 不需要确定的规则 遗传算法的这些性质 已被人们广泛地应用于组合优 化 机器学习 信号处理 自适应控制和人工生命等 领域 它是现代有关 智能计算中的关键技术 遗传算法的假定条件 5 1 由底层供应商对客户进行配送 2 主要为零售性配送活动 3 客户所订购的商品为一些高附加值的商品 如汽车 电脑等 4 忽略交货时的时间间隔 5 一次出行可以解决服务于多个客户的配送问题 基于以上假定 车辆为了满足费用最小化的目标就要寻找一条能历尽所 有目标客户且每个客户仅访问一次 最后返回出发地的行驶路线 也就是寻 求一条最短路径 费用 这种配送问题是一个典型组合优化问题 1 1 问题的描述 问题的描述 设有n个客户的集合 user c1 c2 c3 cn 对于客户Ci Cj属于 user 从Ci到Cj的距离记为 Dij属于R 假设Dij Dji 该问题的解就是在集 合user中找一个不重复的全排列C1i C12 Cin使其距离E 当Cin 1 Ci1时 最短 2 2 遗传算法的设计遗传算法的设计 1 编码方式 由于在求解该问题时 个体表示的是一个可行解 即一条回路 因此它是 城市序号的一组排列 所以传统的二进制编码方式及其基础上的遗传操作不适 用于求解该问题的遗传算法 遗传算法中常用的编码方式有顺序表示法 路径表示法及矩阵表示法等 其中 顺序表示法是指将所有城市依次排列构成一个顺序表 在这个顺序表的 基础上按照某条路径中城市的排列顺序后的个体编码 这种编码最大的问题在 于不够直观 编码和解码算法较为复杂 容易出错 而矩阵表示法是用一个矩 阵来表示一条路径 存在着存储耗费大的问题 于是本文采用路径表示法 路径表示法是表示路径对应的基因编码中最自然 最简单的表示方法 是一类 整数编码方式 特别适合与表示本文具体问题中的个体 将染色体定义为一条 解路线中的客户号序列 我们定义S T大小的pop矩阵来表示群体 求16个客户 安吉物流配送网点的选址和路线优化 12 的问题 T 取17 矩阵每前16个客户的问题 T取17 矩阵每行前16 个元素表示 经过的客户编号 最后一个表示经过这些客户要走的距离 设有n个客户 C1 C2 C3 Cn 假定都是从起始配送中心出发 最后回到该配送中心 则 任意一条染色体可用公式 1 数串表示 其中 Ni 1 2 3 n 染色体中 的单元称为节点 1 2 3 4 5 6 7 N 1 在该问题求解中 染色体的适应值为 其中从Ci到Cj的距离记为 则从群体中选择优胜个体 淘汰劣质个体 它建立在群体中个体适应度评 估的基础上 采用最优保存策略的方法 2 交叉算子设计 传统的遗传算子不太适用于求解该问题 这是因为按问题要求 一条路径 中必定经过且只经过每个客户一次 即个体编码串中每个客户序号都将出现且 只出现1次 而基于二进制编码的单点和多点交叉算子极有可能造成城市序号重 复或缺失而形成非法个体 解决这类问题