运输及配送系统规划ppt课件.ppt

1 第六章运输及配送系统规划 第一节运输方式的选择第二节物资运输调配决策第三节单一车辆配送路线的优化第四节多车辆配送路线的优化 2 重点 难点 1 运输方式的定量选择方法 2 单车辆路线优化方法 3 多车辆路线优化方法 扫描法和节约法 3 第一节运输方式的选择 一 运输方式选择的原则成本 速度 可靠性 安全性 一 安全性原则 二 及时性原则 三 准确性原则 四 经济性原则 4 二 运输服务方式选择的定性方法 即根据各种运输方式的经济和服务特征进行判断 运输成本 成本如何确定 速度 运输时间 可靠性 运输时间的波动 5 三 运输方式的定量分析法 1 成本比较法的基本思想 运输成本与库存成本的总成本 使该运输服务的成本与该运输服务水平以及相关库存成本之间达到平衡的运输服务就是最佳服务 即 既能满足客户需求 又使总成本最低的服务 成本比较法 6 2 计算过程示例说明 某公司欲将产品从位置A的工厂运往位置B的公司自有仓库 年运量D 700000件 产品单价C 30元 年存货成本I 产品价格的30 公司希望选择使总成本最小的运输方式 据估计 运输时间每减少一天 平均库存成本可以减少1 7 各种运输服务的有关参数 方式费率R 元 件 时间T 天 年运送批次平均存货量Q 2铁路0 12110100000驮背0路0 252042000航空1 424020250 选择哪种运输方式最满意 8 选择依据 总成本 运输成本 库存成本运输成本 运输量 费率库存成本 在途库存成本 工厂存货成本 仓库存货成本 库存量 库存费率 物资价格 9 库存成本 在途库存成本 工厂存货成本 仓库存货成本 在途库存费用 I C D T 365工厂存货成本 I C Q 2仓库存货成本 I C R Q 2 年运量D 700000件 产品单价C 30元 存货费率I 30 10 各种运输方式成本计算 年运量D 700000件 产品单价C 30元 存货费率I 30 11 各种运输方式成本计算结果 总成本最低的是公路运输方式 其次是驮背运输 成本最高的是铁路运输 12 结果讨论 1 存储费率改变 对选择有什么影响 降低存储费率 结果会怎样 2 运输费率和运输时间 对于选择结果有何影响 13 第二节物资运输调配决策 指在多个供应地和多个需求地之间如何合理调配货物 在满足需求前提下 使总运输成本最低 14 第二节物资运输调配决策 问题特征 两点间的运输线路固定 运输距离的影响反映在单位运费中 运输总成本由运输量决定 不涉及运输路线如何优化 15 问题分类 一 多起迄点间的直达运输 一 产销平衡的运输问题 二 产销不平衡的运输问题二 存在中间转运的物资调配 16 一 多起迄点间的直达运输 17 运输问题 多个货源可服务于多个市场地 怎么指定各目的市场的供货地 在有多个供应商 工厂 仓库服务于多个客户的情况下 这是运输组织中常见的问题 若供求不平衡呢 更复杂 请看下面几种情况 1 某企业要将济南 郑州 兰州三个工厂生产的钢材运输到北京 上海 西安 杭州 应该如何组织运输使运费最小 2 某大零售商有3个大型配送中心在北京 上海 广州 给它在天津 杭州 武汉 南宁四个城市的超市连锁店配货 应该如何组织运输使运费最小 18 一 产销平衡的运输问题 从每一供应地运送多少物资到各需求地 总运费最低 完成练习题4 19 一 产销平衡的运输问题 从每一供应地运送多少物资到各需求地 总运费最低 20 求解方法 运输问题的表上作业法 单纯形法 最佳方案 A 客户1 400 B 客户1 200 B 客户2 200 B 客户3 300 C 客户2 300完成练习题4 21 二 产销不平衡的运输问题 1 总产量大于总销量2 总销量大于总产量 略 22 二 存在中间转运的物资调配 一 问题描述 23 一 问题描述 某物流系统中有f个供应地 m个中转站 n个需求地 工厂Ak的生产能力为ak k 1 f 流通中心Ti的配送能力为ti i 1 m 零售店Bj的需求量为bj j 1 2 n 由Ak经Ti运到Bj的单位运价为Ckij 求 在设施点能力限制的条件下 满足零售店需求量的最优运输方案 24 二 数学模型 决策变量Xkij 由产地Ak经Ti运到零售店Bj的物资量目标函数 约束条件 1 配送量 生产能力的限制 2 流通中心发送能力的限制 3 满足零售店需求量 4 变量非负 25 三 求解方法 1 一般的线性规划方法求解 2 运输问题表上作业法方法 2 的思路 补充一些虚拟的产地或需求地 将有中转的运输问题转化为无中转的直达运输问题 进一步转化为供需平衡的运输问题 运用表上作业法求解 26 存在中间转运的物资调配 算例题目条件 中转能力不限 27 存在中间转运的物资调配 算例运输问题表 28 运输问题表中需求和供应量确定准则 29 存在中间转运的物资调配 算例最终运输表 30 第三节单一车辆配送路线的优化 两类问题 从O点送货到T点 从A点出发最后回到A点 31 问题及方法分类 一 起迄点不同的单一路线优化 一 动态规划法 二 Dijkstra方法二 起迄点重合的单一路线优化 一 旅行商问题TSP模型 二 中国邮递员问题 32 一 起迄点不同的单一路线问题 1 应用问题从一个发货点运输到一个不同的收货点 例如有一批货需要从A城市运送到E城市 根据从A城市到E城市的公路路网 用点表示经过的县市 线 链 表示两市之间的运输代价 时间 或距离 或时间和距离的加权平均 要确定 从A市到终点的最佳运输路线 最短路径问题 33 2 问题的不同条件 沿着眼前 局部 的最短路走下去 可能找不到最佳路线 34 一 最短路径的动态规划法 要点 适用于什么场合 如何求解 逆序 标号法 19 在节点旁标出该点到终点的最短距离 35 一 最短路径的动态规划法 要点 最佳路径是 19 A B2 C2 D1 E 36 思路 若点序列 Vs V1 V2 Vn 1 Vn 是从Vs到Vn的最短路 则 Vs V1 V2 Vn 1 必定是从Vs到Vn 1的最短路 定义 P Vi Vi到Vs的最短距离 lij两点间距离 二 最短路径的网络图法 Dijkstra方法 O A B C D E T 2 2 5 4 1 7 4 4 3 1 7 5 起点 终点 37 次序n旧节点新节点总距离第n个最近的节点 最短距离 连接1OA2A2OA2OC4C4OCAB2 2 4B4AB3AD2 7 9BE4 3 7E7BECE4 4 84AD2 7 9BD4 4 8D8BDED7 1 8D8ED5DT8 5 13T13DTET7 7 14 求解过程 起点 终点 38 二 起迄点重合的运输路线规划 应用问题 货车运输时碰到的普遍问题 从某仓库 或配送中心 送货到零售点然后返回 从零售店到客户地配送的路线设计 垃圾收运车 或送餐车 的路线设计 39 二 起迄点重合的运输路线规划 应用问题 原则 既经过所有点或街道 又要求时间最短或总距离最短 问题复杂性 可行方案很多 优化上的 组合爆炸 40 一 旅行商问题TSP模型 TravelingSalesmanProblem 经过网络中的各顶点 问题及方法的分类 二 中国邮递员问题 41 二 中国邮递员问题邮递员从邮局出发 走遍他所负责的街道 完成投递后返回邮局 怎样走才使总路程最短 城市配送中心为分布在各街道的便民连锁店配送完货物后再返回配送中心 流动推销员从销售中心出发 沿着街道推销商品 最后再返回销售中心 也属于这类问题 问题及方法的分类 42 一 单回路运输TSP模型 单一车辆的路径安排要求 不可遗漏 访问所有节点 或客户 只有一个回路 各点只能被访问一次 例如 从A出发送货到B C D个小配送站 任意两点间距离已知 或可求 求 最佳行程 43 TSP的数学模型 0 1模型 Xij 0 从i到j无通路Xij 1 从i到j有通路 44 组合爆炸 可行方案共 n 1 个 送货顺序 C3 C1 C2 C4总路长d d31 d12 d24 d43dij Ci Cj之间的距离 45 TSP问题的求解算法 整数规划 小规模问题 启发式算法 贪婪算法 参见例题解法 最近插入法 nearestinsertion 现代优化方法 Hopfield神经网络优化GA遗传算法 46 二 中国邮递员问题及其解法 图论要点复习 偶点与奇点 一笔画 问题 一笔画 的条件图论之 奇偶点图上作业 奇点之间的边重复 47 求解过程 确定初始可行方案判断方案的最优性 行走方案B 方案A 判断标准 每一边上最多有一条重复边 图中每个圈上重复边的总权不大于该圈总权的一半 48 邮递员问题及其解法 最优行走方案 方法局限 图形复杂后 可行方案太多 圈过多 49 第四节多车辆配送路线的优化车辆路径问题VRP VehicleRoutingProblem 50 第四节多车辆配送路线的优化 51 一 问题描述 某物流中心要为q个客户提供服务 己知每个客户点的地理位置及其货运需求量 物流中心需要调用多辆货车来满足这些客户的服务需求 每辆车载重量一定 如何指派车辆 行车路径 52 一 模型假设 1 单一物流中心 多部车辆配送 2 每个需求点由一辆车服务 每个客户点货物需求量不超过车辆的载重容量 3 车辆为单一车种 相同载重量 且容量有限 4 无时窗限制的配送问题 5 客户的位置和需求量均为已知 6 配送的货物视为同一种商品 便于装载 53 二 多车辆配送路线优化数学模型 了解 1 变量2 目标 xijk 车辆k是否直接从节点i到节点j yik 车辆k是否访问节点i 54 二 多车辆配送路线优化数学模型 3 约束条件 1 每个客户点只能被一辆车访问 2 车辆的载重能力约束 3 进入和离开某个客户的是同一辆车 4 消除子回环 5 参数的取值范围 6 所需最少车辆数 55 三 多车辆路径问题求解方法概述 1 精确优化方法2 人工智能方法3 模拟方法4 启发式方法 扫描法节约法 56 二 扫描法 sweepmethod 算法原理 按照角度大小以逆时钟或顺时钟方向扫描所有客户点 若满足车辆装载量即划分为一群 扫描完毕 在每个群内部用最短路径算法求出车辆行驶路径 二阶段法 57 二 扫描法 例8 5 载重量为10吨的车若干辆 58 例题各点位置的图形显示 59 二 扫描法 算法步骤 以物流中心为原点 计算客户点的极坐标 按一定方向扫描所有客户点 客户点需求量进行累加 60 在极坐标系显示各点位置 标出相应货运量 61 例 62 例 63 课堂练习 客户的取货量 单位 件 车辆载重10000件货物 W 3000 2000 3000 4000 1000 3000 2000 1000 2000 2000 2000 2000 64 三 节约法 savingsmethod 1 基本思想 如果将运输问题中的两个回路合并成一个回路 就可缩短线路总里程 即节约了距离 并减少了一辆卡车 节约的里程 65 2 节约法步骤 例8 6 配送中心共有4辆载重量为200件的卡车 如何分配客户 如何确定车辆行驶路径 66 2 节约法步骤 算法的关键问题 怎样确定初始可行方案 怎样对现有方案中的回路进行合并 每个客户由一辆车送货 先对节约量最大的两客户 回路 进行合并 67 2 节约法步骤 1 确定距离方阵 2 确定节约方阵 3 将客户划归由不同的卡车提供服务 4 确定每辆车的行车线路 68 2 节约法步骤 1 确定距离方阵 表8 13 69 2 节约法步骤 2 确定节约方阵 表8 14 配送中心 客户A 配送中心 配送中心 客户B 配送中心 配送中心 客户A 客户B 配送中心 节约距离 A B AB CAO CBO CAB 70 2 节约法步骤 2 节约方阵 表8 14 71 3 将客户划归由不同的卡车提供服务 现有线路的合并 合并原则 保证两条线路的合并是可行的 即运输总量不超过卡车载重量 使节约最大的两条线路合并成一条新的可行线路 途径 观察表8 14 找出最大节约量及其合并线路 72 最大节约34