运输路线优化PPT课件

,节约里程法,最短路径法,图表作业法,图上作业法,（2）运输线路的选择,运输线路的优化,在车辆路线设计方案中，“节约法”是最广为人知的方法，它也形成了人工和计算机载荷计划系统的基础。,从仓库O要运送货物给客户A和B,第一条路线是从O到A，再返回，然后再从O到B，再返回O，总距离为aabb2a2b,外一种路线，从O到A到B，再到O。总距离为：abx。将客户结合考虑，在第二种方案下走行路线的节约里程数是：（2a2b）（abx）即：abx,1节约里程法,它从不为负。因为三角形的第三条边总是小于其他两条边之和，因此，它最小为零。将客户连接起来，增加了节约。客户之间的距离越近，而且它们距离仓库越远，那么节约就会越大。这个方法也可以用时间来代替距离计算。,2,3,1,4,关于这个公式，有许多事情要注意：,为了描述这个方法的使用，考虑下例。,例：如图所示，需要安排从仓库O送货给四个客户A、B、C、D。任何路程不得超过75千米。,配送路线图,解：第一步：计算任一对客户的节约里程值，见下表：,节约值计算表,解：第一步：计算任一对客户的节约里程值，见下表：,节约值计算表,第二步：从最大的节约值开始，将客户连接在一起，直到达到一个限制。,第三步：因此选择第一条路线OCDO。,从最大节约值27开始，连接客户C和D。距离OCDO，和为63千米，没有超过限制。选择下一个最大的节约值，为20，将A、B、C和D连在一起，距离OABCDO，超过了75千米，不予采纳。选择另一个最大的节约值10，将B、C和D连接在一起，距离OBCDO，超过了75千米，仍然不采纳。选择另一个最大的节约值5，将A、C和D连接在一起，距离OADCO，大于75千米，不采纳。,计算结果,第五步：重新进行刚才的程序，从最大的20开始，将A和B连接在一起，距离OABO是50千米，是第二条路线。,第四步：划掉C和D之间的行和列。,如左图所示，要从P点出发，把货物运到AJ共10个目的地，括号内的数字表示需要运送货物的吨数，线路上的数字表示运输距离（单位：km）。另外，假设现在只有额定载重量分别为2t和4t的货车，每车每次运行距离不超过30km。请为该次运输任务选择最优运输线路。,用节约里程法选择运输线路,图表分析法是在分区产销平衡所确定的供销区域内，按照生产地与消费地的地理分布，根据有利于生产、有利于市场供给、近产近销的原则，应用交通路线示意图和商品产销平衡表找出产销之间经济合理的商品运输路线。,2、图表分析法,步骤2,步骤1,步骤3,步骤4,编制产销平衡表,绘制交通示意图,制定商品运输方案(就近原则),填入商品平衡表,图表分析法(操作步骤),例：有一种商品从A地运出400单位，从B地运出700单位，从C地运出300单位，从D地运出600单位，供给abc三地分别为700、800、500单位，各地间的里程(km)图如下，采用图表分析法进行运输路线的优化。,小飞守角制作,步骤1：编制产销平衡表,小飞守角制作,a,B,D,步骤2：绘制交通示意图,表示接受点，其中数字表示运量,表示发运点，其中数字表示发出量,表示两地的距离,小飞守角制作,a,B,D,步骤3：制定商品运输方案,300,200,C,步骤4：填入商品平衡表,图表分析法简单易行，不必计算运输里程，适用于产销地区域较小，产销点少，产销关系比较简单的情况。,最短路径法要求在一个无向图中从出发点开始，用最短的距离（或最少的费用）到达目的地。,从出发点开始，将其运输距离标号为“0”,找出与出发点相邻但未标号点的最小距离值并在相应点标号。,找出与已标号点相邻但未标号点的最小距离值并在相应点标号。,重复步骤3，直到最后一个未标号点也标号.,3最短路径法,用最短路径法选择运输线路,如上图所示，假设要从V1点出发到V7，请用标号法找出V1到V7的最短路径。图中线路上的数字表示运输距离（KM）。,【分析】从V1点出发到V7点，可以经过V1V2V5V7，也可以经过V1V3V6V7等。要找出最短路径，只需按步骤逐步计算即可。【操作】步骤1在V1点标为L1=0。步骤2求与V1相邻但未标号点的最小距离值并标号。V2：0+5=5V3：0+2=2则标号L3=2，并标记V1V3。,步骤3求与V1、V3相邻但未标号点的最小距离值并标号。V2：0+5=5V4：2+7=9V6：2+4=6则标号L2=5，并标记V1V2。步骤4求与V1、V2、V3相邻但未标号点的最小距离值并标号。V4：5+2=7V5：5+7=12V6：2+4=6则标号L6=6，并标记V3V6。,2最短路径法,步骤5求与V1、V2、V3、V6相邻但未标号点的最小距离值并标号。,则标号L4=7，L5=7，并标记V2V4，V6V5。,步骤6求与V1、V2、V3、V4、V5、V6相邻未标号点的最小值。,则标号L7=10，并标记V5V7。,综上所述，可知V1到V7最短路径为V1V3V6V5V7（如图中双线所示），距离为2+4+1+3=10。,如图所示是某地区交通运输的示意图.试问：从V1出发，经哪条路线到达V8才能使总行程最短？,图上作业法是指利用产地和销地的地理分布和运输线路示意图制定产品运输最小吨公里的方法。图上作业法可以避免对流运输和迂回运输的现象，找出运输线路最短、运力最省的运输方案。其原理可归纳为：流向画右方，对流不应当；里圈、外圈分别算，要求不能过半圈长；如若超过半圈长，应去运量最小段；反复运算可得最优方案。,4图上作业法,运输线路不成圈是指不构成回路的“树”形线路，包括直线、丁字线、交叉线、分支线等，其中，直线为图上作业法的基本线路。无论哪种线路，都要将此转化为直线运输形式，以便做出流向线。运输线路不成圈的图书作业法较为简单，就是从各端点开始，按“各站供需就近调拨”的原则进行调配，只要不出现对流现象就是最优方案。,（1）运输线路不成圈的图上作业法,某地区物资供应情况如下图所示，其中“”表示起运站，“”表示目的站。现要求通过图上作业法得到物资调运的最优方案。,运输线路不成圈的图上作业法,【分析】该题中有4个起运站：A1、A2、A3、A4，供应量分别为+7、+8、+6、+4；另有4个目的站B1、B2、B3、B4，需求量分别为-2、-8、-7、-8。为了便于检查对流现象，把流向箭头统一画在线路右边，调运量用数字表示，标注在箭头旁边。【操作】步骤1从起运站A1开始，把7个单位的物资供应给B1，剩余5个单位的物资再调运给A2。步骤2起运站A2的8个单位的物资供应给B2，从A1调运过来的5个单位的物资供应给B3，这时，B3缺2个单位的物资。,步骤3将起运站A4的4个单位的物资调运给A3，连同A3原有的6个单位的物资共10个单位，供应8个单位给B4，另外2个单位供应给B3，填补B3所缺的2个单位的物资。步骤4此时，没有出现对流现象，故此方案为最优方案，如下图所示。,运输线路成圈，就是形成闭合回路的“环”形线路，包括一个圈（有三角形、四边形、多边形）和多个圈。对于成圈运输线路的图上作业法，可按下述三个步骤寻求最优方案。去段破圈，确定初始运输方案就是在成圈的线路中，先假设某两点间的线路“不通”，去掉这段线路，把成圈线路转化为不成圈的线路，即破圈；按照运输线路不成圈的图上作业法，即可得到初始运输方案。,（2）运输线路成圈的图上作业法,检查有无迂回现象因为流向箭头统一画在线路右边，所以圈内外都画有一些流向，分别检查每个小圈，如果圈内和圈外流向的总长度都不超过全圈总长度的1/2，则可断定全圈不存在迂回现象，这个线路流向图就是最优的，否则继续第三步。重新去段破圈，调整流向在超过全圈总长1/2的里（外）圈各段流向线上减去最小运量，然后在相反方向的外（里）圈流向线上和原来没有流向线的各段上加上或减去最小运量，这样可以得到一个新的线路流向图，然后转到第二步检查有无迂回现象。如此反复，直到得到最优线路流向图为止。,某地区的物资供应情况如下图所示，其中“”表示起运站，“”表示目的站，线路间括号中的数字表示起运站与目的站之间的距离（单位：km），现要求用图上作业法找出物资调运的最优方案。,运输线路成圈的图上作业法,【分析】该题中有4个起运站：A1、A2、A3、A4，供应量分别为+20、+60、+100、+20；另有5个目的站B1、B2、B3、B4、B5，需求量分别为-30、-30、-50、-70、-20。图中有一个圈，由A1、B1、A2、B4、B3、B2构成。【操作】步骤1去段破圈，确定初始运输方案。去掉A1到B2的线路，然后按照“各站供需就近调拨”的原则进行调运，即可得到初始运输流向线路图，如下图所示。,步骤2检查有无迂回现象。由上图可看出不存在对流现象，但要检查里、外圈流向线长，看是否超过全圈（闭合线路）总长的1/2。在本例中，全圈总长为45+23+25+18+23+36=170（km）半圈长为170/2=85（km）外圈流向总长为45+25+18+23=111（km）里圈流向总长为23（km）因为外圈流向总长超过了全圈总长的1/2（111km85km），则可断定初始运输线路存在迂回现象，所对应的方案不是最优方案。因此，必须进行优化调整。,步骤3重新去段破圈，调整流向。初始方案中里圈符合要求，外圈流向总长超过全圈的1/2，故需缩小外圈。因为外圈流向线中运量最小的是A1到B1的“20”，所以去掉A1到B1的线路，并在外圈各段流向线上减去“20”的运量，同时在里圈个流向线上以及原来没有流向线的A1到B2线上各加上“20”的运量，这样可得到新的运输线路流向图，如下图所示。,步骤4检查新的流向线路图的里、外圈流向线长，看是否超过全圈（闭合线路）总长的1/2，在本例中，外圈流向总长为25+18+23=66（km）里圈流向总长为23+36=59（km）两者均没有超过全圈总长的1/2（即85km)，所以调整后的新流向线路