配送路线优化课件

项目三项目三 配送服务配送服务教学任务：教学任务：1.进货入库作业、储存作业、盘点作业、返品处理进货入库作业、储存作业、盘点作业、返品处理作业作业2.订单处理与补货、拣货作业订单处理与补货、拣货作业3.出货作业出货作业上上车辆配装、货品装箱车辆配装、货品装箱、装卸工安装卸工安排排4.出货出货作业下作业下配送线路优化配送线路优化项目三 配送服务教学任务：1 1项目三项目三 配送服务配送服务小组小组PPT介绍介绍互动：提问互动：提问+分享分享内容补充内容补充+总结总结项目三 配送服务小组PPT介绍2 2任务任务3 出货作业之出货作业之配送线路优化配送线路优化 一、最短路径法一、最短路径法 二、节约法二、节约法任务3 出货作业之配送线路优化 一3 3任务任务3 配送线路优化方法配送线路优化方法 之之之之1 1：最短路径法：最短路径法：最短路径法：最短路径法 一、最短路径法一、最短路径法 所所谓谓最最短短路路径径法法，是是指指要要从从网网络络图图中中某某顶顶点点出出发发，经经过过图图中中路路径径到到达达另另一一顶顶点点，而而这这些些路路径径不不止止一一条条，如如何何找找到到一一条条路路径径使各边的权值之和为最小。使各边的权值之和为最小。任务3 配送线路优化方法 4 4任务任务3 配送线路优化方法配送线路优化方法 之之之之1 1：最短路径法：最短路径法：最短路径法：最短路径法最短路径法示例最短路径法示例1：新新加加坡坡某某配配送送中中心心签签订订了了一一项项配配送送运运输输合合同同，要要从从配配送送中中心心A配配送送一一批批货货物物到到销销售售地地F,两两点点之之间间可可选选择择的的行行车车路路线线如如图图所示，求从配送中心所示，求从配送中心A到销售地到销售地F的最短路径。的最短路径。DEBACF11428741823任务3 配送线路优化方法 5 5任务任务3 配送线路优化方法配送线路优化方法 之之之之1 1：最短路径法：最短路径法：最短路径法：最短路径法 最短路径法示例最短路径法示例2：从从V0到到V6找出最短路径？找出最短路径？任务3 配送线路优化方法 6 6任务任务3 配送线路优化方法配送线路优化方法 之之之之1 1：最短路径法：最短路径法：最短路径法：最短路径法 最短路径法计算最短路径法计算3 任务3 配送线路优化方法 7 7任务任务3 配送线路优化方法配送线路优化方法 之之之之1 1：最短路径法：最短路径法：最短路径法：最短路径法 最短路径法最短路径法练习题：练习题：某配送公司要将客户急需的商品从配送中心某配送公司要将客户急需的商品从配送中心P运送到商场运送到商场Q，图，图1表示由起点表示由起点P到终点到终点Q的路线图，各条弧所对应的数字表的路线图，各条弧所对应的数字表示通过该段路线所需时间。试求所需时间最短路线。示通过该段路线所需时间。试求所需时间最短路线。任务3 配送线路优化方法 9 9 任务任务任务任务3 3 配送线路优化方法配送线路优化方法配送线路优化方法配送线路优化方法 之之之之2 2：节约法：节约法：节约法：节约法（起止点重合的配送路线选择起止点重合的配送路线选择起止点重合的配送路线选择起止点重合的配送路线选择）任务导入任务导入1：某车一天的货运任务如下图：求最佳行车路线。注：方框为供货点，椭圆为需求点。K=4吨A=2吨B=1吨C=1吨121116678 任务3 配送线路优化方法 1010 任务任务任务任务3 3 配送线路优化方法配送线路优化方法配送线路优化方法配送线路优化方法 之之之之2 2：节约法：节约法：节约法：节约法（起止点重合的配送路线选择起止点重合的配送路线选择起止点重合的配送路线选择起止点重合的配送路线选择）任务导入任务导入2：某某配配送送配配送送中中心心A向向全全市市4个个商商店店B、C、D、E进进行行配配送送，各各点点相相对对位位置置见见下下图图，运运输输距距离离见见表表1，求求最最佳佳配配送路线。送路线。任务3 配送线路优化方法 1212任务任务3 配送线路优化方法配送线路优化方法 之之之之2 2：节约法：节约法：节约法：节约法 一、节约法的基本假定一、节约法的基本假定 前提假设前提假设：当从若干配送据点向众多的客户配：当从若干配送据点向众多的客户配送货物时，各用户的坐标及需求量均为已知，配送送货物时，各用户的坐标及需求量均为已知，配送中心有足够的运输能力。中心有足够的运输能力。利用节约法制定出的配送方案除了使配送里程利用节约法制定出的配送方案除了使配送里程最小外，还满足以下条件，方案能满足所有用户的最小外，还满足以下条件，方案能满足所有用户的要求，不使任何一辆车超载；每辆车每天的总运行要求，不使任何一辆车超载；每辆车每天的总运行时间或行驶里程不超过规定的上限，能满足用户到时间或行驶里程不超过规定的上限，能满足用户到货时间要求。货时间要求。任务3 配送线路优化方法 1313二、节约法的基本原理二、节约法的基本原理 假如由一家配送中心假如由一家配送中心O向两个用户向两个用户A、B送货，配送中心到送货，配送中心到两客户的最短距离分别是两客户的最短距离分别是a和和b，A和和B间的最短距离为间的最短距离为x，AB的的货物需求量分别是货物需求量分别是Q1和和Q2，且，且Q1+Q2小于车辆装载量小于车辆装载量Q，如同，如同71所示。所示。图图7-1 7-1 路线图路线图O从仓库O要运送货物给客户A和B第一条路线是从O到A，再返回，然后再从O到B，再返回O，总距离为aabb2a2b外一种路线，从O到A到B，再到O。总距离为：abx。将客户结合考虑，在第二种方案下走行路线的节约里程数是：（2a2b）（）（abx）即：abx二、节约法的基本原理 假如由一家配送中心O向两个用1414 它从不为负。因为三角形的第三条边总是小于其他两条边之和，因此，它最小为零。将客户连接起来，增加了节约。客户之间的距离越近，而且它们距离仓库越远，那么节约就会越大。这个方法也可以用时间来代替距离计算。关于这个公式，注意：二、节约法的基本原理二、节约法的基本原理 它从不为负。因为三角形的第三条边总是小于其他两条边之和1515 为了描述这个方法的使用，考虑下例。例：如图7-2所示，需要安排从仓库O送货给四个客户A、B、C、D。任何路程不得超过 75 千米。图图7-27-2 配送路线图配送路线图三、节约法示例三、节约法示例1 为了描述这个方法的使用，考虑下例。例1616 解：第一步：计算任一对客户的节约里程值，见表2-10：表表2-10 2-10 节约值计算表节约值计算表 第二步：从最大的节约值开始，将客户连接在一起，直到达到一个限制。三、节约法示例三、节约法示例1 第三步：因此选择第一条路线OCDO。从最大节约值27开始，连接客户C和D。距离OCDO，和为63千米，没有超过限制。选择下一个最大的节约值，为20，将A、B、C和D连在一起，距离OABCDO，超过了75千米，不予采纳。选择另一个最大的节约值10，将B、C和D连接在一起，距离OBCDO，超过了75 千米，仍然不采纳。选择另一个最大的节约值5，将A、C和D连接在一起，距离OACDO，大于75千米，不采纳。解：第一步：计算任一对客户的节约里程值，见表2-101717表表2-11 2-11 计算结果计算结果 第五步：重新进行刚才的程序，从最大的 20 开始，将 A 和 B 连接在一起，距离OABO是50千米，是第二条路线。第四步：划掉C和D之间的行和列，见表2-11。三、节约法示例三、节约法示例1表2-11 计算结果 第五步：重新进行刚才的程序，1818 任务任务任务任务3 3 配送线路优化方法配送线路优化方法配送线路优化方法配送线路优化方法 之之之之2 2：节约法：节约法：节约法：节约法（起止点重合的配送路线选择起止点重合的配送路线选择起止点重合的配送路线选择起止点重合的配送路线选择）任务导入：任务导入：某某配配送送配配送送中中心心A向向全全市市4个个商商店店B、C、D、E进进行行配配送送，各各点点相相对对位位置置见见下下图图，运运输输距距离离见见表表1，求求最最佳佳配送路线。配送路线。现在能找到最佳现在能找到最佳配送路线吗？配送路线吗？任务3 配送线路优化方法 1919 三、节约法示例三、节约法示例2 已知配送中心已知配送中心P0向向5个用户个用户Pj配送货物，其配送路配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离线网络、配送中心与用户的距离以及用户之间的距离如下图与表所示：图中括号内的数字表示客户的需求如下图与表所示：图中括号内的数字表示客户的需求量（单位：吨），线路上的数字表示两结点之间的距量（单位：吨），线路上的数字表示两结点之间的距离，配送中心有离，配送中心有3台台2t卡车和卡车和2台台4t两种车辆可供使用。两种车辆可供使用。问题：问题：1、试利用节约里程法制定最优的配送方案？、试利用节约里程法制定最优的配送方案？2、设卡车行驶的速度平均为、设卡车行驶的速度平均为40公里公里/小时，试比较小时，试比较优化后的方案比单独向各用户分送可节约多少时间？优化后的方案比单独向各用户分送可节约多少时间？三、节约法示例2 已知配送中心P0向5个用户P2020 三、节约法示例三、节约法示例2 三、节约法示例22121 三、节约法示例三、节约法示例2第第1步：作运输里程表，列出配送步：作运输里程表，列出配送中心到用户及用户间的最短距离。中心到用户及用户间的最短距离。三、节约法示例2第1步：作运输里程表，列出配送中心到用户及2222 三、节约法示例三、节约法示例2第1步：作运输里程表，列出配送中心到用户及用户间的最短距离。三、节约法示例2第1步：作运输里程表，列出配送中心到用户及2323 三、节约法示例三、节约法示例3练习：练习：某连锁零售店，某连锁零售店，下设有一个配送下设有一个配送P和和9个连锁分店个连锁分店A-J,配送配送中心和各连锁分店及中心和各连锁分店及各连锁分店之间的位各连锁分店之间的位置关系如图所示。该置关系如图所示。该商品由配送中心统一商品由配送中心统一采购并进行配送运输，采购并进行配送运输，配送中心有最大装载配送中心有最大装载量为量为2t和和5t的货车，的货车，并限定车辆一次运行并限定车辆一次运行距离不超过距离不超过35km，设送到时间均符合用设送到时间均符合用户要求，求配送中心户要求，求配送中心的最优配送运输方案。的最优配送运输方案。三、节约法示例3练习：某连锁零售店，下设有一个配送P和9个3232 三、节约法示例三、节约法示例3练习：练习：某连锁零售店，下设有一个配送某连锁零售店，下设有一个配送P和和9个连锁分店个连锁分店A-J,配送中心和各连锁分店及各连锁分店之间的位置关系如图所配送中心和各连锁分店及各连锁分店之间的位置关系如图所示。该商品由配送中心统一采购并进行配送运输，配送中心示。该商品由配送中心统一采购并进行配送运输，配送中心有最大装载量为有最大装载量为2t和和5t的货车，并限定车辆一次运行距离不的货车，并限定车辆一次运行距离不超过超过35km，设送到时间均符合用户要求，求配送中心的最，设送到时间均符合用户要求，求配送中心的最优配送运输方案。优配送运输方案。三、节约法示例3练习：某连锁零售店，下设有一个配送P和9个3333作业：节约法示例节约法示例4 下图所示为一配送网络，下图所示为一配送网络，P为配送中心所为配送中心所在地，在地，AJ为客户所在地，括号内的数字为配为客户所在地，括号内的数字为配送量，单位为吨送量，单位为吨（t），），线路上的数字为道路线路上的数字为道路的距离，单位为公里的距离，单位为公里（km）。现有可以利用。现有可以利用的车辆是最大装载量为的车辆是最大装载量为2吨和吨和4吨的两种厢式货吨的两种厢式货车，并限制车辆一次运行距离在车，并限制车辆一次运行距离在30公里以内。公里以内。现求最佳配送路线。现求最佳配送路线。作业：节约法示例4 下图所示为一配送网络，P为配送中3434配送路线优化课件3535第一步：首先计算相互之间最短距离，根据上图第一步：首先计算相互之间最短距离，根据上图中配送中心至各用户之间，用户与用户之间的距中配送中心至各用户之间，用户与用户之间的距离，得出配送路线最短的距离矩阵，如图：离，得出配送路线最短的距离矩阵，如图：第一步：首先计算相互之间最短距离，根据上图中配送中心至各用户3636第二步：从最短距离矩阵中计算出各用户之间的节约第二步：从最短距离矩阵中计算出各用户之间的节约行程见下图。例如，计算行程见下图。例如，计算ABAB的节约距离：的节约距离：PA的距离：的距离：a=10，PB的距离：的距离：b=9，AB的距离：的距离：c=4，a+b-c=15 配送路线节约里程图配送路线节约里程图 第二步：从最短距离矩阵中计算出各用户之间的节约行程见下图。例3737第三步：对节约行程按大小顺序排列，见下表。第三步：对节约行程按大小顺序排列，见下表。配送线路节约里程排序表配送线路节约里程排序表 第三步：对节约行程按大小顺序排列，见下表。配送线3838第四步：按照节约行程排列顺序表，组合成配送路线图 依据配送中心约束条件和节约里程顺序表，依据配送中心约束条件和节约里程顺序表，首先选择最节约里程路段，依次安排，最后形成首先选择最节约里程路段，依次安排，最后形成3条配送路线，运行距离为条配送路线，运行距离为80公里。需要公里。需要2吨汽车吨汽车1辆，辆，4吨汽车吨汽车2辆。辆。其中配送路线其中配送路线：4吨汽车吨汽车1辆，运行距离辆，运行距离27公里，装载量为公里，装载量为3.6吨；配送路线吨；配送路线：4吨车吨车1辆，辆，运行距离运行距离30公里，装载量为公里，装载量为3.9吨；配送路线吨；配送路线：2吨车吨车1辆，运行距离辆，运行距离23公里，装载量为公里，装载量为1.3吨。吨。第四步：按照节约行程排列顺序表，组合成配送路线图 3939配送路线优化课件4040