配送路线优化课件.ppt

1、 教学任务：教学任务： 1.进货入库作业、储存作业、盘点作业、返品处理进货入库作业、储存作业、盘点作业、返品处理作业作业 2.订单处理与补货、拣货作业订单处理与补货、拣货作业 3.出货作业出货作业上上车辆配装、货品装箱车辆配装、货品装箱、装卸工安装卸工安排排 4.出货出货作业下作业下配送线路优化配送线路优化 小组小组PPT介绍介绍 互动：提问互动：提问+分享分享 内容补充内容补充+总结总结 一、最短路径法一、最短路径法 二、节约法二、节约法 一、最短路径法一、最短路径法 所谓所谓最短路径法最短路径法，是指要从网络图中，是指要从网络图中某顶点出发，经过图中路径到达另一顶点，某顶点出发，经过图中路

2、径到达另一顶点，而这些路径不止一条，如何找到一条路径而这些路径不止一条，如何找到一条路径使各边的权值之和为最小。使各边的权值之和为最小。 最短路径法示例最短路径法示例1： 新加坡某配送中心签订了一项配送运输合同，要从配送中新加坡某配送中心签订了一项配送运输合同，要从配送中心心A配送一批货物到销售地配送一批货物到销售地F,两点之间可选择的行车路线如图两点之间可选择的行车路线如图所示，求从配送中心所示，求从配送中心A到销售地到销售地F的最短路径。的最短路径。 DEBACF11428741823 最短路径法示例最短路径法示例2： 从从V0到到V6找出最短路径？找出最短路径？ 最短路径法计算最短路径法

3、计算3 最短路径法计算最短路径法计算3参考答案：参考答案： 2的最短距离的最短距离100路径路径1-2 3的最短距离的最短距离175路径路径1-3 4的最短距离的最短距离150路径路径1-4 5的最短距离的最短距离325路径路径1-4-5 6的最短距离的最短距离359路径路径1-4-6 7的最短距离的最短距离425路径路径1-4-7 8的最短距离的最短距离550路径路径1-4-7-8 9的最短距离的最短距离550路径路径1-4-6-9 10的最短距离的最短距离575路径路径1-4-6-9-10 最短路径法最短路径法练习题：练习题： 某配送公司要将客户急需的商品从配送中心某配送公司要将客户急需的

4、商品从配送中心P运送到商场运送到商场Q，图图1表示由起点表示由起点P到终点到终点Q的路线图，各条弧所对应的数字表示的路线图，各条弧所对应的数字表示通过该段路线所需时间。试求所需时间最短路线。通过该段路线所需时间。试求所需时间最短路线。 任务导入任务导入1： 某车一天的货运任务如下图：求最佳行车路线。注：方框为供货点，椭圆为需求点。K=4吨A=2吨B=1吨C=1吨121116678解：分析：从供货点到需求点再返回供货点的线路共4条，距离计算如下： 1：K-A-B-C-K, L1=12+6+7+11=36 2：K-C-B-A-K, L2=11+7+6+12=36 3：K-A-C-B-K, L3=1

5、2+8+7+16=43 4：K-C-A-B-K, L4=11+8+6+16=41 5：K-B-A-C-K,L5=16+6+8+11=41 6：K-B-C-A-K,L6=16+7+8+12=43分析各线路的货运周转量大小并排序 Z1=4*12+2*6+1*7+11*0=48+12+7=67 Z2=4*11+3*7+2*6+0*12=44+21+12=77 Z3=4*12+2*8+1*7+0*16=48+16+7=71 Z4=4*11+3*8+1*6+0*16=44+24+6=74 Z5=4*16+3*6+1*8+0*11=64+18+8=90 Z6=4*16+3*7+2*8+0*12=64+21

6、+16=101显然，第一条线路的货运周转量最小，故选择第一条线路。 任务导入任务导入2： 某配送配送中心某配送配送中心A向全市向全市4个商店个商店B、C、D、E进行进行配送，各点相对位置见下图，运输距离见表配送，各点相对位置见下图，运输距离见表1，求最佳，求最佳配送路线。配送路线。 一、节约法的基本假定一、节约法的基本假定 前提假设前提假设：当从若干配送据点向众多的客户配：当从若干配送据点向众多的客户配送货物时，各用户的坐标及需求量均为已知，配送送货物时，各用户的坐标及需求量均为已知，配送中心有足够的运输能力。中心有足够的运输能力。 利用节约法制定出的配送方案除了使配送里程利用节约法制定出的配

7、送方案除了使配送里程最小外，还满足以下条件，方案能满足所有用户的最小外，还满足以下条件，方案能满足所有用户的要求，不使任何一辆车超载；每辆车每天的总运行要求，不使任何一辆车超载；每辆车每天的总运行时间或行驶里程不超过规定的上限，能满足用户到时间或行驶里程不超过规定的上限，能满足用户到货时间要求。货时间要求。 假如由一家配送中心假如由一家配送中心O向两个用户向两个用户A、B送货，配送中心到送货，配送中心到两客户的最短距离分别是两客户的最短距离分别是a和和b，A和和B间的最短距离为间的最短距离为x，AB的的货物需求量分别是货物需求量分别是Q1和和Q2，且，且Q1+Q2小于车辆装载量小于车辆装载量Q

8、，如，如同同71所示。所示。O从仓库O要运送货物给客户A和B第一条路线是从O到A，再返回，然后再从O到B，再返回O，总距离为aabb2a2b外一种路线，从O到A到B，再到O。总距离为：abx。将客户结合考虑，在第二种方案下走行路线的节约里程数是：（2a2b）（）（abx）即：abx 它从不为负。因为三角形的第三条边总是小于其他两条边之和，因此，它最小为零。 将客户连接起来，增加了节约。 客户之间的距离越近，而且它们距离仓库越远，那么节约就会越大。 这个方法也可以用时间来代替距离计算。2314关于这个公式，注意： 为了描述这个方法的使用，考虑下例。 例：如图7-2所示，需要安排从仓库O送货给四个

9、客户A、B、C、D。任何路程不得超过 75 千米。 解：第一步：计算任一对客户的节约里程值，见表2-10： 第二步：从最大的节约值开始，将客户连接在一起，直到达到一个限制。 第三步：因此选择第一条路线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千米，不采纳。 第五步：

10、重新进行刚才的程序，从最大的 20 开始，将 A 和 B 连接在一起，距离OABO是50千米，是第二条路线。 第四步：划掉C和D之间的行和列，见表2-11。 任务导入：任务导入： 某配送配送中心某配送配送中心A向全市向全市4个商店个商店B、C、D、E进行进行配送，各点相对位置见下图，运输距离见表配送，各点相对位置见下图，运输距离见表1，求最佳，求最佳配送路线。配送路线。现在能找到最佳现在能找到最佳配送路线吗？配送路线吗？ 已知配送中心已知配送中心P0向向5个用户个用户Pj配送货物，其配送路配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离线网络、配送中心与用户的距离以及用户之间的

11、距离如下图与表所示：图中括号内的数字表示客户的需求如下图与表所示：图中括号内的数字表示客户的需求量（单位：吨），线路上的数字表示两结点之间的距量（单位：吨），线路上的数字表示两结点之间的距离，配送中心有离，配送中心有3台台2t卡车和卡车和2台台4t两种车辆可供使用。两种车辆可供使用。 问题：问题： 1、试利用节约里程法制定最优的配送方案？、试利用节约里程法制定最优的配送方案？ 2、设卡车行驶的速度平均为、设卡车行驶的速度平均为40公里公里/小时，试比较小时，试比较优化后的方案比单独向各用户分送可节约多少时间？优化后的方案比单独向各用户分送可节约多少时间？第第1步：作运输里程表，列出配送步：作运

12、输里程表，列出配送中心到用户及用户间的最短距离。中心到用户及用户间的最短距离。第1步：作运输里程表，列出配送中心到用户及用户间的最短距离。第第1步：作运输里程表，列出配送步：作运输里程表，列出配送中心到用户及用户间的最短距离。中心到用户及用户间的最短距离。第第2步：由运输里程表、按节约里程步：由运输里程表、按节约里程公式，求得相应的节约里程数，如下公式，求得相应的节约里程数，如下表（表（ ）内。）内。第第2步：由运输里程表、按节约里程步：由运输里程表、按节约里程公式，求得相应的节约里程数，如下公式，求得相应的节约里程数，如下表（表（ ）内。）内。第第3步：将节约里程按从步：将节约里程按从大到小

13、顺序排列大到小顺序排列第第3步：将节约里程按从步：将节约里程按从大到小顺序排列大到小顺序排列第4步：根据载重量约束与节约里程大小，将各客户结点连接起来，形成二个配送路线。即A、B两配送方案。第第5步：确定单独送货的配送线路步：确定单独送货的配送线路 计算初始方案配送距离计算初始方案配送距离=?配送线路配送线路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.9t4t,用一辆用一

14、辆 4t车运送车运送节约距离节约距离SB=2km第第6步：与初始单独送货方案相比，计算总步：与初始单独送货方案相比，计算总节约里程与节约时间节约里程与节约时间总节约里程：总节约里程：S= SA+ SB= 20 km与初始单独送货方案相比，可节约时间：与初始单独送货方案相比，可节约时间：T =S/V=20/40=0.5小时小时练习：练习：某连锁零售店，某连锁零售店，下设有一个配送下设有一个配送P和和9个连锁分店个连锁分店A-J,配送配送中心和各连锁分店及中心和各连锁分店及各连锁分店之间的位各连锁分店之间的位置关系如图所示。该置关系如图所示。该商品由配送中心统一商品由配送中心统一采购并进行配送运输

15、，采购并进行配送运输，配送中心有最大装载配送中心有最大装载量为量为2t和和5t的货车，的货车，并限定车辆一次运行并限定车辆一次运行距离不超过距离不超过35km，设送到时间均符合用设送到时间均符合用户要求，求配送中心户要求，求配送中心的最优配送运输方案。的最优配送运输方案。练习：练习：某连锁零售店，下设有一个配送某连锁零售店，下设有一个配送P和和9个连锁分店个连锁分店A-J,配送中心和各连锁分店及各连锁分店之间的位置关系如图所配送中心和各连锁分店及各连锁分店之间的位置关系如图所示。该商品由配送中心统一采购并进行配送运输，配送中心示。该商品由配送中心统一采购并进行配送运输，配送中心有最大装载量为有

16、最大装载量为2t和和5t的货车，并限定车辆一次运行距离不的货车，并限定车辆一次运行距离不超过超过35km，设送到时间均符合用户要求，求配送中心的最，设送到时间均符合用户要求，求配送中心的最优配送运输方案。优配送运输方案。 下图所示为一配送网络，下图所示为一配送网络，P为配送中心所为配送中心所在地，在地，AJ为客户所在地，括号内的数字为为客户所在地，括号内的数字为配送量，单位为吨配送量，单位为吨（t），），线路上的数字为道线路上的数字为道路的距离，单位为公里路的距离，单位为公里（km）。现有可以利。现有可以利用的车辆是最大装载量为用的车辆是最大装载量为2吨和吨和4吨的两种厢式吨的两种厢式货车，并

17、限制车辆一次运行距离在货车，并限制车辆一次运行距离在30公里以内。公里以内。现求最佳配送路线。现求最佳配送路线。 第一步：首先计算相互之间最短距离，根据上图第一步：首先计算相互之间最短距离，根据上图中配送中心至各用户之间，用户与用户之间的距中配送中心至各用户之间，用户与用户之间的距离，得出配送路线最短的距离矩阵，如图：离，得出配送路线最短的距离矩阵，如图： 第二步：从最短距离矩阵中计算出各用户之间的节第二步：从最短距离矩阵中计算出各用户之间的节约行程见下图。例如，计算约行程见下图。例如，计算ABAB的节约距离：的节约距离： PA的距离：的距离：a=10，PB的距离：的距离：b=9，AB的距离：

18、的距离：c=4，a+b-c=15 配送路线节约里程图配送路线节约里程图 第三步：对节约行程按大小顺序排列，见下表。第三步：对节约行程按大小顺序排列，见下表。 配送线路节约里程排序表配送线路节约里程排序表 依据配送中心约束条件和节约里程顺序表，依据配送中心约束条件和节约里程顺序表，首先选择最节约里程路段，依次安排，最后形成首先选择最节约里程路段，依次安排，最后形成3条配送路线，运行距离为条配送路线，运行距离为80公里。需要公里。需要2吨汽车吨汽车1辆，辆，4吨汽车吨汽车2辆。辆。 其中配送路线其中配送路线：4吨汽车吨汽车1辆，运行距离辆，运行距离27公里，装载量为公里，装载量为3.6吨；配送路线吨；配送路线：4吨车吨车1辆，辆，运行距离运行距离30公里，装载量为公里，装载量为3.9吨；配送路线吨；配送路线：2吨车吨车1辆，运行距离辆，运行距离23公里，装载量为公里，装载量为1.3吨。吨。