第4章-配送与运输.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 配送与运输,刘群锋 讲师,东莞理工学院,1,运输方式的选择,物流运输的准则,及时,准确,经济,安全,1,运输方式的选择,实施运输的四个指标,经济性指标,迅速性指标,安全性指标,便利性指标,2,物资调运中的表上作业法,要解决的问题,从,m,个生产点运送物资到,n,个消费点,每个生产点的产量和消费点的销量是已知的,产销平衡表,从生产点到消费点的运费,(,或距离,),是已知的,运费表,目标：总运费最少,2,物资调运中的表上作业法,产销平衡表,发点 收点,A1,A2,A3,A4,发量,B1,8000,B2,6000,B3,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,2,物资调运中的表上作业法,运费表,发点 收点,A1,A2,A3,A4,B1,3,5,2,6,B2,1,7,8,2,B3,5,3,4,9,表,2,发点到收点的运费表（单位：元,/t,）,2,物资调运中的表上作业法,产销平衡表与运费表的合一,发点 收点,A1,A2,A3,A4,发量,B1,3,5,2,6,8000,B2,1,7,8,2,6000,B3,5,3,4,9,5000,收量,7000,4000,5000,3000,表,3,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,2,物资调运中的表上作业法,表上作业法的步骤,制定初始方案,最小元素法,求检验数,位势法,检验初始方案是否最优,如果不是最优，进行调整，直到最优,闭回路法,2,物资调运中的表上作业法,用最小元素法制定初始方案,找到运费表中最小的数,把这个数所在的行对应的发量和列对应的收量中的较小者填入这个数所在的空格，并划去较小者所在的行或列,继续寻找下一个最小的数（运费）,.,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,发量,B1,3,5,2,6,8000,B2,1,7,8,2,6000,B3,5,3,4,9,5000,收量,7000,4000,5000,3000,表,3,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,发点 收点,A1,A2,A3,A4,发量,B1,8000,B2,6000,B3,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,6000,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,发量,B1,3,5,2,6,8000,B2,1,7,8,2,6000,B3,5,3,4,9,5000,收量,7000,4000,5000,3000,表,3,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,发点 收点,A1,A2,A3,A4,发量,B1,8000,B2,6000,B3,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,6000,5000,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,发量,B1,3,5,2,6,8000,B2,1,7,8,2,6000,B3,5,3,4,9,5000,收量,7000,4000,5000,3000,表,3,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,发点 收点,A1,A2,A3,A4,发量,B1,8000,B2,6000,B3,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,6000,5000,1000,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,发量,B1,3,5,2,6,8000,B2,1,7,8,2,6000,B3,5,3,4,9,5000,收量,7000,4000,5000,3000,表,3,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,发点 收点,A1,A2,A3,A4,发量,B1,8000,B2,6000,B3,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,6000,5000,1000,4000,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,发量,B1,3,5,2,6,8000,B2,1,7,8,2,6000,B3,5,3,4,9,5000,收量,7000,4000,5000,3000,表,3,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,发点 收点,A1,A2,A3,A4,发量,B1,8000,B2,6000,B3,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,6000,5000,1000,4000,2000,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,发量,B1,3,5,2,6,8000,B2,1,7,8,2,6000,B3,5,3,4,9,5000,收量,7000,4000,5000,3000,表,3,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,发点 收点,A1,A2,A3,A4,发量,B1,8000,B2,6000,B3,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,6000,5000,1000,4000,2000,1000,2,物资调运中的表上作业法,用最小元素法制定初始方案注释,填入一个空格，只能划去某一行或某一列,最终填满了,m+n-1,个空格，,m,为行数，,n,为列数,最终划去了,m+n-1,个行与列,如果填入一个空格时，行与列都得到了满足，此时也只能划去一行或列。,这种情况下，会有一个空格填入,0,2,物资调运中的表上作业法,位势法求空格的检验数,在运费表中把对应于有调运数的那些费用用圆圈圈起来,不断地对运费表中的一行或一列的所有数字加上一个相同的数（可以是正数或负数），直到圆圈中的数字全部变成,0,为止,没有被圈住的数字就是所在空格的检验数,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,B1,3,5,2,6,B2,1,7,8,2,B3,5,3,4,9,表,2,发点到收点的运费表（单位：元,/t,）,发点 收点,A1,A2,A3,A4,发量,B1,1000,5000,2000,8000,B2,6000,6000,B3,4000,1000,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,B1,3,5,2,6,B2,1,7,8,2,B3,5,3,4,9,表,2,发点到收点的运费表（单位：元,/t,）,位势法怎么操作？,第一行,3,个圈，对列操作，减法，圈中变,0,第三行,2,个圈，对行操作，减,3,，圈中变,0,第二行,1,个圈，对行操作，加,2,，圈中变,0,第二列,1,个圈，对列操作，圈中变,0,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,B1,0,5,0,0,B2,0,9,8,-2,B3,-1,0,-1,0,表,4,位势的计算,发点 收点,A1,A2,A3,A4,发量,B1,1000,5000,2000,8000,B2,6000,6000,B3,4000,1000,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,2,物资调运中的表上作业法,检验初始方案是否最优,空格的检验数如果都是正数，则已达到最优,如果有任何一个检验数是负数，则没有达到最优，必须进行调整,调整方法：闭回路法,2,物资调运中的表上作业法,闭回路调整,选择最小的负检验数所在的空格,以这个空格为出发点，沿水平方向或铅直方向前进，遇到数字格，变成与原方向垂直的方向继续前进，遇到,合适,的数字格再改变方向前进，,.,，直到回到原出发点,在回路上标记“,+”“-”,号：出发点标“,+”,，下一个数字格标“,-”,，再下一个又标“,+”,，,.,选出“,-”,号处的最小者,所有标“,-”,号处减去这个最小值,所有标“,+”,号处加上这个最小值,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,B1,0,5,0,0,B2,0,9,8,-2,B3,-1,0,-1,0,发点 收点,A1,A2,A3,A4,发量,B1,1000,5000,2000,8000,B2,6000,6000,B3,4000,1000,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,表,4,位势的计算,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,发量,B1,3000,5000,8000,B2,4000,2000,6000,B3,4000,1000,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,发点 收点,A1,A2,A3,A4,B1,3,5,2,6,B2,1,7,8,2,B3,5,3,4,9,表,2,发点到收点的运费表（单位：元,/t,）,2,物资调运中的表上作业法,再用位势法求空格的检验数，并检验是否最优,发点 收点,A1,A2,A3,A4,B1,0,7,0,2,B2,0,11,8,0,B3,0,0,-3,0,表,4,位势的计算,发点 收点,A1,A2,A3,A4,B1,3,5,2,6,B2,1,7,8,2,B3,5,3,4,9,表,2,发点到收点的运费表（单位：元,/t,）,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,发量,B1,3000,5000,8000,B2,4000,2000,6000,B3,4000,1000,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,发点 收点,A1,A2,A3,A4,B1,0,7,0,2,B2,0,11,8,0,B3,0,0,-3,0,表,4,位势的计算,2,物资调运中的表上作业法,发点 收点,A1,A2,A3,A4,发量,B1,4000,4000,8000,B2,3000,3000,6000,B3,4000,1000,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,发点 收点,A1,A2,A3,A4,B1,3,5,2,6,B2,1,7,8,2,B3,5,3,4,9,表,2,发点到收点的运费表（单位：元,/t,）,2,物资调运中的表上作业法,再用位势法求空格的检验数，并检验是否最优,发点 收点,A1,A2,A3,A4,B1,0,4,0,2,B2,0,8,8,0,B3,0,0,0,3,表,4,位势的计算,发点 收点,A1,A2,A3,A4,B1,3,5,2,6,B2,1,7,8,2,B3,5,3,4,9,表,2,发点到收点的运费表（单位：元,/t,）,2,物资调运中的表上作业法,最优解,最小运费为,45000,元，比原始方案节约,7000,元！,发点 收点,A1,A2,A3,A4,发量,B1,4000,4000,8000,B2,3000,3000,6000,B3,4000,1000,5000,收量,7000,4000,5000,3000,表,1,产销平衡表（单位：,t,）,2,物资调运中的表上作业法,练习一,发点 收点,A1,A2,A3,发量,B1,10,2,5,4,B2,9,3,6,7,B3,2,1,2,2,收量,2,3,8,13,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,2,物资调运中的表上作业法,练习二：产销不平衡怎么办？,发点 收点,A1,A2,A3,A4,发量,B1,2,11,3,4,7,B2,10,3,5,9,5,B3,7,8,1,2,7,收量,2,3,4,6,15 19,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,2,物资调运中的表上作业法,练习二：将不平衡转化成平衡,发点 收点,A1,A2,A3,A4,库存,发量,B1,2,11,3,4,0,7,B2,10,3,5,9,0,5,B3,7,8,1,2,0,7,收量,2,3,4,6,4,19 19,产销平衡表（单位：,t,）与运费表,（单位：元,/t,）,3,表上作业法的其他应用,作物布局问题,某农场有,1320,亩土地，这些土地分成一级、二级、三级、四级、五级。各级土地数量见下表。,要求种植玉米、地瓜、谷子、大豆四种作物，每种作物要求种植的面积见下表。,不同作物在不同级别的土壤上的产量不同，具体数据如下表,目标：总产量最大,3,表上作业法的其他应用,作物布局问题,作物 土壤,一级,二级,三级,四级,五级,作物面积,玉米,300,250,230,200,150,305,地瓜,450,400,350,620,谷子,280,240,220,170,140,55,大豆,220,280,155,125,110,340,土壤亩数,30,150,160,770,210,1320,3,表上作业法的其他应用,作物布局问题的解法,制定初始方案,最,大,元素法,求检验数,位势法,检验初始方案是否最优,如果不是最优，进行调整，直到最优,闭回路法,3,表上作业法的其他应用,作物 土壤,一级,二级,三级,四级,五级,作物面积,玉米,305,地瓜,620,谷子,55,大豆,340,土壤亩数,30,150,160,770,210,1320,作物 土壤,一级,二级,三级,四级,五级,作物面积,玉米,300,250,230,200,150,305,地瓜,450,400,350,620,谷子,280,240,220,170,140,55,大豆,220,280,155,125,110,340,土壤亩数,30,150,160,770,210,1320,3,表上作业法的其他应用,土方的合理调配问题,挖土区三处：甲、乙、丙,填土区四处：一、二、三、四,给定各挖土区到各填土区的距离,目标：总的土方公里数最小,3,表上作业法的其他应用,土方的合理调配问题,挖土 填土,一,二,三,四,挖土量,甲,10,9,12,7,500,乙,13,11,9,4,300,丙,14,15,11,5,400,填土量,350,450,250,150,1200,3,表上作业法的其他应用,土方的合理调配问题的解法,制定初始方案,最,小,元素法,求检验数,位势法,检验初始方案是否最优,如果不是最优，进行调整，直到最优,闭回路法,4,配送最优路线的选择,配送与运输,配送主要指短途运输,配送一般是一点到多点,运输通常是点到点的,常见的配送方式,起点与终点不同,起点与终点相同,4,配送最优路线的选择,起点与终点不同,起点与终点之间有许多节点和弧线,所有弧对应着一个数字，表示两个节点之间的距离或者运输时间和成本,从起点到终点的路线有许多条,目标：找出数字之和最小的路线连接起点与终点,4,配送最优路线的选择,起点与终点不同的例子,A,B,C,E,D,G,F,H,3,6,12,6,5,10,6,8,12,8,7,7,7,4,配送最优路线的选择,起点与终点不同的解法,逆推法,从终点出发向前划分阶段,n,条弧就有,n,个阶段,从,n=1,出发确定当前阶段每个节点到终点的最优路线,第,2,阶段的节点,C,到终点的最优路线记为,f,2,(C),f,2,(C)=13,（,C-F-H,）,逐步增加,n,，直到到达起点为止,f,3,(A)=19,（,A-C-F-H,）,4,配送最优路线的选择,n=1,时,f,1,(F)=6,f,1,(E)=8,f,1,(G)=7,n=2,时,f,2,(B)=min18,18=18 B-F-H,或,B-E-H,f,2,(C)=min13,14,15=13 C-F-H,f,2,(D)=min15,19=15 D-E-H,n=3,时,f,3,(A)=min21,19,20=19 A-C-F-H,4,配送最优路线的选择,起点与终点不同的例子,A,B,C,E,D,G,F,H,3,4,12,5,4,7,4,8,12,6,8,I,K,J,7,5,1,3,2,4,配送最优路线的选择,n=1,时,f,1,(H)=7,f,1,(I)=5,f,1,(J)=1,n=2,时,f,2,(F)=11 F-H-K,f,2,(E)=min10,11=10 E-H-K,f,2,(G)=min7,9=7 G-I-K,n=3,时,f,3,(B)=min23,17=17 B-E-H-K,f,3,(C)=min14,15=14 C-E-H-K,f,3,(D)=19 D-G-I-K,n=4,时,f,4,(A)=min20,19,23=19 A-C-E-H-K,4,配送最优路线的选择,起点与终点相同,一个配送中心向各需求点送货，送后返回,任意两点均连通,选择距离最短的送货路线,A,B,C,E,D,A,B,C,D,E,A,0,10,15,9,30,B,10,0,15,17,25,C,15,15,0,7,13,D,9,17,7,0,26,E,30,25,13,26,0,4,配送最优路线的选择,起点与终点相同的解法,从配送中心出发，寻找与之连接的距离最短的点（比如,D,）,从,D,点出发，寻找与之连接的距离最短的点，比如,C,一直持续下去，直到穷尽所有的需求点，然后回到配送中心,4,配送最优路线的选择,解答,配送中心,A-D-C-E-B-A,总配送距离为,9+7+13+25+10=64,A,B,C,E,D,A,B,C,D,E,A,0,10,15,9,30,B,10,0,15,17,25,C,15,15,0,7,13,D,9,17,7,0,26,E,30,25,13,26,0,4,配送最优路线的选择,练习,配送中心,A-B-E-F-C-D-A,总配送距离为,9+10+8+6+7+15=55,A,B,C,D,E,F,A,0,9,17,15,20,26,B,9,0,16,17,10,22,C,17,16,0,7,9,6,D,15,17,7,0,23,21,E,20,10,9,23,0,8,F,26,22,6,21,8,0,A,B,C,E,D,F,4,配送最优路线的选择,选择配送路线的“节约法,(Saving Algorithm),”,各个节点之间的距离,(,运费,),已知,各个需求点的需求量已知,运输车辆数目不确定,选择一条路线，使得总运输距离最短,4,配送最优路线的选择,“节约法,(Saving Algorithm),”,举例,客户需求量如下表（单位：吨）,客 户,A1,A2,A3,A4,A5,A6,A7,A8,A9,需求量,1.7,0.5,0.9,1.2,1.6,1.1,0.9,0.9,0.6,4,配送最优路线的选择,“节约法,(Saving Algorithm),”,举例,配送中心,O,到各个需求点的距离如下表（单位：公里）,O,A1,A2,A3,A4,A5,A6,A7,A8,A9,O,0,11,10,9,6,7,10,10,8,7,A1,0,5,10,14,18,21,21,13,6,A2,0,5,9,15,20,20,18,11,A3,0,4,9,19,19,17,16,A4,0,6,15,16,14,13,A5,0,9,17,15,14,A6,0,14,18,17,A7,0,12,19,A8,0,7,A9,0,4,配送最优路线的选择,“节约法,(Saving Algorithm),”,解法,节约里程表（单位：公里）,A1,A2,A3,A4,A5,A6,A7,A8,A9,A1,0,16,10,3,0,0,0,6,12,A2,0,14,7,2,0,0,0,6,A3,0,6,7,0,0,0,0,A4,0,7,1,0,0,0,A5,0,8,0,0,0,A6,0,6,0,0,A7,0,6,-2,A8,0,8,A9,0,4,配送最优路线的选择,“节约法,(Saving Algorithm),”,解法,节约里程次序表,序号,节点对,节约里程,序号,节点对,节约里程,序号,节点对,节约里程,1,(A1,A2),16,7,(A2,A4),7,13,(A6,A7),6,2,(A2,A3),14,8,(A3,A5),7,14,(A7,A8),6,3,(A1,A9),12,9,(A4,A5),7,15,(A1,A4),3,4,(A1,A3),10,10,(A1,A8),6,16,(A2,A5),2,5,(A5,A6),8,11,(A2,A9),6,17,(A4,A6),1,6,(A8,A9),8,12,(A3,A4),6,18,(A7,A9),-2,5,巡回运输中装卸工人的调配,问题的提法,多个装卸点,每个装卸点需要的工人数可能不同,多辆运输车辆,目标：用最少的装卸工人完成装卸任务,5,巡回运输中装卸工人的调配,举例：,3,辆车,车场,B 6,人,E 5,人,D 4,人,G 3,人,C 4,人,F 8,人,5,巡回运输中装卸工人的调配,解法,车比点多,不跟车,车比点少,跟车,跟车人数用编号法确定,编号法,按所需工人数从大到小的顺序将装卸点编号,跟车人数等于第,n,号装卸点所需工人数，其中,n,是车辆数,5,巡回运输中装卸工人的调配,举例：,5,辆车,车场,B 6,人,E 5,人,D 4,人,G 3,人,C 4,人,F 8,人,5,巡回运输中装卸工人的调配,举例：,7,辆车,车场,B 6,人,E 5,人,D 4,人,G 3,人,C 4,人,F 8,人,5,巡回运输中装卸工人的调配,练习,某车场每天有,5,辆车经过,8,个装卸点，组织巡回运输，在各个装卸点所需工人数分别为,4,人、,6,人、,7,人、,9,人、,6,人、,10,人、,8,人、,5,人，请问应该怎样调配装卸工人最合理？,