ppt配送路线优化.ppt

项目三配送服务 教学任务 1 进货入库作业 储存作业 盘点作业 返品处理作业2 订单处理与补货 拣货作业3 出货作业上 车辆配装 货品装箱 装卸工安排4 出货作业下 配送线路优化 项目三配送服务 小组PPT介绍互动 提问 分享内容补充 总结 任务3出货作业之配送线路优化 一 最短路径法二 节约法 任务3配送线路优化方法之1 最短路径法 一 最短路径法所谓最短路径法 是指要从网络图中某顶点出发 经过图中路径到达另一顶点 而这些路径不止一条 如何找到一条路径使各边的权值之和为最小 任务3配送线路优化方法之1 最短路径法 最短路径法示例1 新加坡某配送中心签订了一项配送运输合同 要从配送中心A配送一批货物到销售地F 两点之间可选择的行车路线如图所示 求从配送中心A到销售地F的最短路径 任务3配送线路优化方法之1 最短路径法 最短路径法示例2 从V0到V6找出最短路径 任务3配送线路优化方法之1 最短路径法 最短路径法计算3 任务3配送线路优化方法之1 最短路径法 最短路径法计算3参考答案 2的最短距离100路径1 23的最短距离175路径1 34的最短距离150路径1 45的最短距离325路径1 4 56的最短距离359路径1 4 67的最短距离425路径1 4 78的最短距离550路径1 4 7 89的最短距离550路径1 4 6 910的最短距离575路径1 4 6 9 10 任务3配送线路优化方法之1 最短路径法 最短路径法练习题 某配送公司要将客户急需的商品从配送中心P运送到商场Q 图1表示由起点P到终点Q的路线图 各条弧所对应的数字表示通过该段路线所需时间 试求所需时间最短路线 任务3配送线路优化方法之2 节约法 起止点重合的配送路线选择 任务导入1 某车一天的货运任务如下图 求最佳行车路线 注 方框为供货点 椭圆为需求点 解 分析 从供货点到需求点再返回供货点的线路共4条 距离计算如下 1 K A B C K L1 12 6 7 11 362 K C B A K L2 11 7 6 12 363 K A C B K L3 12 8 7 16 434 K C A B K L4 11 8 6 16 415 K B A C K L5 16 6 8 11 416 K B C A K L6 16 7 8 12 43分析各线路的货运周转量大小并排序Z1 4 12 2 6 1 7 11 0 48 12 7 67Z2 4 11 3 7 2 6 0 12 44 21 12 77Z3 4 12 2 8 1 7 0 16 48 16 7 71Z4 4 11 3 8 1 6 0 16 44 24 6 74Z5 4 16 3 6 1 8 0 11 64 18 8 90Z6 4 16 3 7 2 8 0 12 64 21 16 101显然 第一条线路的货运周转量最小 故选择第一条线路 任务3配送线路优化方法之2 节约法 起止点重合的配送路线选择 任务导入2 某配送配送中心A向全市4个商店B C D E进行配送 各点相对位置见下图 运输距离见表1 求最佳配送路线 任务3配送线路优化方法之2 节约法 一 节约法的基本假定前提假设 当从若干配送据点向众多的客户配送货物时 各用户的坐标及需求量均为已知 配送中心有足够的运输能力 利用节约法制定出的配送方案除了使配送里程最小外 还满足以下条件 方案能满足所有用户的要求 不使任何一辆车超载 每辆车每天的总运行时间或行驶里程不超过规定的上限 能满足用户到货时间要求 二 节约法的基本原理 假如由一家配送中心O向两个用户A B送货 配送中心到两客户的最短距离分别是a和b A和B间的最短距离为x AB的货物需求量分别是Q1和Q2 且Q1 Q2小于车辆装载量Q 如同7 1所示 图7 1路线图 O 从仓库O要运送货物给客户A和B 第一条路线是从O到A 再返回 然后再从O到B 再返回O 总距离为a a b b 2a 2b 外一种路线 从O到A到B 再到O 总距离为 a b x 将客户结合考虑 在第二种方案下走行路线的节约里程数是 2a 2b a b x 即 a b x 它从不为负 因为三角形的第三条边总是小于其他两条边之和 因此 它最小为零 将客户连接起来 增加了节约 客户之间的距离越近 而且它们距离仓库越远 那么节约就会越大 这个方法也可以用时间来代替距离计算 2 3 1 4 关于这个公式 注意 二 节约法的基本原理 为了描述这个方法的使用 考虑下例 例 如图7 2所示 需要安排从仓库O送货给四个客户A B C D 任何路程不得超过75千米 图7 2配送路线图 三 节约法示例1 解 第一步 计算任一对客户的节约里程值 见表2 10 表2 10节约值计算表 第二步 从最大的节约值开始 将客户连接在一起 直到达到一个限制 三 节约法示例1 第三步 因此选择第一条路线O C D O 从最大节约值27开始 连接客户C和D 距离O C D O 和为63千米 没有超过限制 选择下一个最大的节约值 为20 将A B C和D连在一起 距离O A B C D O 超过了75千米 不予采纳 选择另一个最大的节约值10 将B C和D连接在一起 距离O B C D O 超过了75千米 仍然不采纳 选择另一个最大的节约值5 将A C和D连接在一起 距离O A C D O 大于75千米 不采纳 表2 11计算结果 第五步 重新进行刚才的程序 从最大的20开始 将A和B连接在一起 距离O A B O是50千米 是第二条路线 第四步 划掉C和D之间的行和列 见表2 11 三 节约法示例1 任务3配送线路优化方法之2 节约法 起止点重合的配送路线选择 任务导入 某配送配送中心A向全市4个商店B C D E进行配送 各点相对位置见下图 运输距离见表1 求最佳配送路线 现在能找到最佳配送路线吗 三 节约法示例2 已知配送中心P0向5个用户Pj配送货物 其配送路线网络 配送中心与用户的距离以及用户之间的距离如下图与表所示 图中括号内的数字表示客户的需求量 单位 吨 线路上的数字表示两结点之间的距离 配送中心有3台2t卡车和2台4t两种车辆可供使用 问题 1 试利用节约里程法制定最优的配送方案 2 设卡车行驶的速度平均为40公里 小时 试比较优化后的方案比单独向各用户分送可节约多少时间 三 节约法示例2 三 节约法示例2 第1步 作运输里程表 列出配送中心到用户及用户间的最短距离 三 节约法示例2 第1步 作运输里程表 列出配送中心到用户及用户间的最短距离 三 节约法示例2 第1步 作运输里程表 列出配送中心到用户及用户间的最短距离 三 节约法示例2 第2步 由运输里程表 按节约里程公式 求得相应的节约里程数 如下表 内 三 节约法示例2 第2步 由运输里程表 按节约里程公式 求得相应的节约里程数 如下表 内 三 节约法示例2 第3步 将节约里程按从大到小顺序排列 三 节约法示例2 第3步 将节约里程按从大到小顺序排列 三 节约法示例2 第4步 根据载重量约束与节约里程大小 将各客户结点连接起来 形成二个配送路线 即A B两配送方案 三 节约法示例2 第5步 确定单独送货的配送线路 计算初始方案配送距离 三 节约法示例2 配送线路A P0 P2 P3 P4 P0运量 q2 q3 q4 1 7 0 9 1 4 4t 用一辆4t车运送节约距离SA 10 8 18km 配送线路B P0 P5 P1 P0运量 q5 q1 2 4 1 5 3 9t 4t 用一辆4t车运送节约距离SB 2km 第6步 与初始单独送货方案相比 计算总节约里程与节约时间总节约里程 S SA SB 20km与初始单独送货方案相比 可节约时间 T S V 20 40 0 5小时 三 节约法示例3 练习 某连锁零售店 下设有一个配送P和9个连锁分店A J 配送中心和各连锁分店及各连锁分店之间的位置关系如图所示 该商品由配送中心统一采购并进行配送运输 配送中心有最大装载量为2t和5t的货车 并限定车辆一次运行距离不超过35km 设送到时间均符合用户要求 求配送中心的最优配送运输方案 三 节约法示例3 练习 某连锁零售店 下设有一个配送P和9个连锁分店A J 配送中心和各连锁分店及各连锁分店之间的位置关系如图所示 该商品由配送中心统一采购并进行配送运输 配送中心有最大装载量为2t和5t的货车 并限定车辆一次运行距离不超过35km 设送到时间均符合用户要求 求配送中心的最优配送运输方案 作业 节约法示例4 下图所示为一配送网络 P为配送中心所在地 A J为客户所在地 括号内的数字为配送量 单位为吨 t 线路上的数字为道路的距离 单位为公里 km 现有可以利用的车辆是最大装载量为2吨和4吨的两种厢式货车 并限制车辆一次运行距离在30公里以内 现求最佳配送路线 第一步 首先计算相互之间最短距离 根据上图中配送中心至各用户之间 用户与用户之间的距离 得出配送路线最短的距离矩阵 如图 第二步 从最短距离矩阵中计算出各用户之间的节约行程见下图 例如 计算AB的节约距离 PA的距离 a 10 PB的距离 b 9 AB的距离 c 4 a b c 15 配送路线节约里程图 第三步 对节约行程按大小顺序排列 见下