运输线路决策.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/8/9 Sunday,#,2026/11/5,运输线路决策,最短路径法,练习,A,F,E,D,C,B,50,40,90,80,40,50,30,表上作业法,是单纯形法在求解运输问题的一种简化方法，,寻求运费最少,的调运方案。,解题思路是：,首先依据已知问题列出货物的供需平衡表及运价表；然后使用左上角法或者最小元素法或伏格尔法确定初始的调运方案；最后根据一个判定法则判断初始方案是不是最优方案，如果不是最优方案，要借助调出变量调整调配方案，再判断，直到判定为最优方案为止。,初始方案容易找,利用左上角法寻找初始方案，基本思路,从运价表元素中,左上角的元素开始，集中供应，依次安排调运量,，直到得到一个可行方案。,利用最小元素法寻找初始方案，基本思路,就近运输，也就是,从运价表中找到最小的运价，优先满足运价最小的调运,，然后在剩下的供需状态中，寻找次小的运价，满足此供需路径，再重复寻找剩下的最小的运价给与满足，直到给出初始方案为止。这种方法找到的方案，虽然每次都找的是运价最低的路径优先调运，但为了节省一个节点的费用，有时会造成其他节点费用的大幅增加，所以进行判定最优解时，会比较麻烦。,伏格尔法,，一个调运地如果不能按最小运费就近供应，就考虑次小运费，这就有了一个差额，差额越大，说明不按最小运费供应，越不合理，运费增加越多，所以应优先采用最小运费调运。,例3-1 某公司有3个仓库，分别是A、B、C，供应量分别是7吨、4吨、9吨，每天向4个配送中心送货，分别是甲、乙、丙、丁，需求量分别是10吨，3吨、2吨和5吨。单位运价表如图7-2所示，请确定初始可行方案。,单位运价表 单位：元/吨,销地,产地,甲,乙,丙,丁,A,2,3,7,6,B,1,3,2,6,C,3,5,4,8,解：,第一步建立货物的供需平衡表及运价表如表所示。,平衡表,销地,产地,甲,乙,丙,丁,供应量,（吨）,A,2,3,7,6,7,B,1,3,2,6,4,C,3,5,4,8,9,需求量,（吨）,10,3,2,5,20,第二步，利用最小元素法寻找初始方案,最小元素法确定的初始方案表,销地,产地,甲,乙,丙,丁,供应量,（吨）,A,6,1,7,B,4,4,C,2,2,5,9,需求量,（吨）,10,3,2,5,20,第三步判定最优方案,位势法,首先在初始方案中找到运量分配最多的行或列，确定其所在行或列的位势为零，,然后根据有调运量的格所对应的运价等于行位势加上列位势之和，依次求出各行和列的位势，,再根据下列公式求空格所对应的检验数。,A,ij,C,ij,（U,i,+V,j,）,公式中的A,ij,表示空格所对应的检验数，C,ij,表示空格所对应的运价，U,i,表示行位势，V,j,表示列位势，i表示运价表的行数，j表示运价表的列数。,最小元素法确定的初始方案表,销地,产地,甲,乙,丙,丁,供应量,（吨）,A,6,1,7,B,4,4,C,2,2,5,9,需求量,（吨）,10,3,2,5,20,最小元素法确定的初始方案的检验数,销地,产地,甲,乙,丙,丁,供应量,（吨）,A,6（0）,1（0）,（5）,（0）,7,B,4（0）,（1）,（1）,（1）,4,C,（-1）,2（0）,2（0）,5（0）,9,需求量,（吨）,10,3,2,5,20,最后判断，如果所有的检验数均大于等于零，则判断的方案最优。当检验数有至少一个负数时，说明该方案不是最优的方案，运输成本还有调整的空间，对负数检验数绝对值最大的所在的闭回路进行调整。,Aij=0，初始方案最优；有一个Aij0，则不是最优，需要调整负数中|Aij|值最大的所在闭合回路。,闭合回路,基本思路是从任意一个空格（没有安排调运量的格）出发，沿着行或列寻找的一条除此空格之外其余顶点均为有数字格（安排有调运量的格）的闭合回路。,找出某一空格的闭合回路；从该空格开始在闭合回路上给各个顶点进行“+”、“-”间隔标号；,对负数检验数绝对值最大的所在的闭回路进行调整:标有负号顶点中对应的最小运量作为调入运量，标有“+”的顶点所对应的运量加上调入运量，标有“”的顶点所对应的运量减去调入运量；,形成新的调运方案，再判断和调整直到得到最优方案为止。,例7-2 某公司有3个仓库，分别是A、B、C，供应量分别是7吨、4吨、9吨，每天向4个配送中心送货，分别是甲、乙、丙、丁，需求量分别是10吨，3吨、2吨和5吨。单位运价表如图所示，请确定最优方案。,单位运价表 单位：元/吨,产地 销地,甲,乙,丙,丁,A,2,3,7,6,B,1,3,2,6,C,3,5,4,8,销地,产地,甲,乙,丙,丁,供应量（吨）,A,（1）,3,（5）,4,7,B,2,（0）,2,（0）,4,C,8,（0）,（0）,1,9,需求量（吨）,10,3,2,5,20,A,ij,0，得到最优解,x,13,=5,x,14,=2,x,21,=3,x,24,=1,x,32,=6,x,34,=3,其余,x,ij,=0;,最优值：,f,*=35+102+13+81+46+53=85,例,某地区有3个煤矿，所产煤炭全部销往两座火力发电厂。各矿产量、电厂需求量及单位运价表如表所示，问如何安排运输可使总运费最省？,运价 电厂,煤矿,B1,B2,煤产量,A1,3,5,5000,A2,4,2,11000,A3,6,9,8000,需求量,10000,14000,练习题,:某商品产地：A、B、C、D销地：a、b、c、d、e供应量分别为：100、300、600、800，需求量分别为：250、300、350、400、500,，请确定最优方案。,单位运价表 a b c d e,A,B,C,D,30,20,30,50,30,30,30,10,30,40,70,80,40,20,20,50,40,70,70,80,练习,供需不平衡的物资调运问题,1、供应量大于需求量,2、需求量大于供应量,处理：引入一个虚设的需求点，令其的需求量等于实际问题中供应量与需求量之差。实际中，相当于在某个供应点的仓库里将多余部分储存起来了。因此，可视其相应运价为 。,零,处理：引入一个虚设的供应点，令其的供应量等于实际问题中需求量与供应量之差。实际中，相当于在某个需求点内设立一个仓库，将不足部分另找出路供应好，预先储存起来了。相应运价为零。,例:某公司从两个产地,A,1,、,A,2,将物品运往三个销地,B,1,、,B,2,、,B,3,，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,解：增加一个虚设的销地运输费用为0,例:某公司从两个产地,A,1,、,A,2,将物品运往三个销地,B,1,、,B,2,、,B,3,，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,解：增加一个虚设的产地运输费用为0,图上作业法,图上作业法：,利用商品产地和销地的地理分布和交通路线示意图，采用科学规划的方法，制定出商品合理的运输方案，来求得商品运输最小吨公里的方法。,它适用于交通线路为线状、圈状，而且对产销地点的数量没有严格限制的情况。,如果没有对流和迂回，就是一个运输力最省的最优方案。,图上作业法,交通图画法,1、交通图的符号：,发点用“”表示，并将发货量记在里面，收点用“”表示，并将收货量记在里面。两点间交通线的长度记在交通线旁边。,2、调运物资的流向图：,物资调运的方向（流向）用“”表示，并把“”按调运方向画在交通线的,右边,，把调运物资的数量记在“”的右边并,加上括号,。,例1：调运线路呈线状。,依据“就近调空”原则，只要不出现对流情况，即是最优方案。,设产地A、D、F，产量为10、3、9，销地B、C、E、G，需求为2、5、11、4，试求合理的运输方案。,第一步，编制商品产销平衡表,需,供,B,C,E,G,产量,A,10,D,3,F,9,销量,2,5,11,4,22,第二步，绘制交通线路示意图,A,10,B,-2,-5 C,3 D,E,-11,F,9,G,-4,第三步，按交通路线示意图进行图上作业。就近调空，首先从各端开始就近调运，在进行调整。,A,10,B,-2,-5 C,3 D,E,-11,F,9,G,-4,第四步，将结果填入商品调运平衡表。,需,供,B,C,E,G,产量,A,2,2,6,10,D,3,3,F,5,4,9,销量,2,5,11,4,22,例,有某物资17万吨，由A1，A2，A3，A4发出，发量分别为5，2，3，7（单位：万吨），运往B1，B2，B3，B4，收量分别为8，1，3，5，收发量是平衡的，它的交通路线如图所示，问应如何调运，才能使运输吨千米最小。,5,2,3,7,8,1,3,5,A1,A2,B1,A3,B2,B3,A4,B4,例2：调运线路呈圈状。设有产地，销地,其距离及供需量见书，求最优运输线路。,它的原则可归纳为：流向划右方，对流不应当；里圈、外圈分别算，要求不过半圈长；如若超过半圈长，应甩运量最小段；反复求算最优方案。,第一步，在每个圈中，去掉一段距离最长的线路，用虚线表示，变成线状，再根据线路不含圈的情况作出初始调运方案。,第二步，检查有无迂回现象。,第三步，调整流向。,第四步将结果填入平衡表。,例,调运线路成圈状例。设有某商品发运点A、B、C、D等四处，接收点a、b、c、d位于圈状，其距离及供需量如表所示，试求最优运输路线。,解：,具体作业步骤如下：,A首先假定里程最长的一段没有货流通过，使圈状线路变成非圈线状，其B 应甩去。,B进行合理运输，即从B运150吨到a，再从a运20吨到A，A运100吨到d。另一方面，从D运10吨到d。此外，从D运90吨到e，C地运70吨到e，同时运100吨到b地。,C根据图中虚线简示将内外圈货流里程汇总检查是否超过全圈长的一半,一般来说，利用图上作业法寻求商品最优运输方案，可以按运输吨公里最小原则，也可以从运送时间最短或运费最省等角度来分别计算，只要商品在图上没有对流，内外圈长都不大于半圈长，该运输方案就是最优运输方案。,练习,3,1,3,1,1,3,2,A1,A2,B1,A3,B2,B3,B4,7,5,3,4,4,4,3,2,在实际运输活动中，各流向上的物资是不平衡的，如进多出少或进少出多，就会出现有时车辆卸货后空载，如何调运才能使空车行驶里程最少。,练习,货名,发货点,收货点,里程,运量,XX,G,B,166,9,XX,G,H,57,1,XX,I,H,132,10,XX,J,H,75,9,XX,A,D,167,10,XX,A,B,78,5,XX,K,B,74,9,XX,F,D,41,6,XX,E,B,144,9,XX,C,D,57,13,节约法确定路径的基本原理,车辆运行计划法(VSP，Vehicles Scheduling Program)又称里程节约法（VSP方法）。适用于实际工作中为求得较优解或最优的近似解时采用。它的,基本原理是三角形的一边之长必定小于另外两边之和。,如图所示。,为实现所节约里程。可根据用户要求、道路条件等设计几种巡回方案，再计算节约里程，以其中节约里程最大者为优选的方案。VSP方法可对所有需求地点计算其节约里程，按节约量的大小顺序，优选确定路线。,如图所示交通网络图。由起始点P向A、B、C、D、E等五个用户送物品。图中连线上的数字表示公路里程（km）。图中靠近各用户括号里的数字，表示对货物的需求量（t）。起始点备有2t和4t载质量的汽车，且汽车一次巡回行驶里程不能超过30km。求解满意的送货方案。,P,A,B,C,D,E,P,-,8,3,10,8,7,A,-,8,17,15,9,B,-,9,11,10,C,-,7,13,D,-,6,E,-,-,A,B,C,D,E,A,-,3,1,1,6,B,-,4,0,0,C,-,11,4,D,-,9,E,-,序号,路程,节约数额,1,C-D,11,2,D-E,9,3,A-E,6,4,B-C,4,5,C-E,4,6,A-B,3,7,A-C,1,8,A-D,1,节约里程数额排序表,节约里程表,最短距离表,从图中可以看出，依次确定的3条路径均符合约束条件。最后选择的方案是：使用2辆4t车，1辆2t车，行驶里程共52km。其中：,路径1：4t车，载货量3.5t，行驶里程30km；,路径2：2t车，载货量1.5t，行驶里程16km；,路径3：4t车，载货量3t，行驶里程6km。,在环形的线路起点，可以通过计算实载率的思路确定。总之，这一方法用计算机计算将变得非常简单。,练习：有一配送中心（Q）要向10个用户配送，配送距离（公里）和需用量（吨）。采用最大载重量2t、4t、8t三种汽车，并限定车辆一次运行距离 50 km。,第一步，从配送网络图中列出配送中心至用户及用户相互间的最短距离。,第二步：从最短距离中，计算用户相互间的节约里程。,第三步：将节约里程按大小顺序排列分类。,第四步：按节约里程大小顺序，组成配送路线,第一步：做出最短距离,例如：C-d之间的节约里程为：,S=s1s2-s3=785=10 km,第二步：从最短矩阵中，计算用户相互间的节约里程如图所示。,第三步：将节约里程按大小顺序排列分类见表,第四步：按节约里程大小顺序，组成配送路线。此方案总路线7条，总行程为109公里，用6辆2吨载重汽车和1辆4吨汽车。,按上述方法，逐次取代，优化配送路线，得出方案共有两条路线，线路A和B，总行程70公里，用8吨的载重车1辆（实际载重6.9吨），最大行程46公里；2吨的载重车1辆（实际载重1.9吨），最大行程24公里。,节约里程法应用原则,节约里程法的原则是在约束条件下追求利润最大化。为了使利润最大，可以通过使路程最短，运力最优，运送准确性最高来实现。约束条件也就是应该注意的事项，例如：,客户的需要。即客户对配送数量、质量、时间的要求。,应充分考虑交通和道路情况。,充分考虑收货站的停留时间。,应充分考虑运载工具的载重量和容积要求及配送中心的配送能力等。,起讫点重合的问题,起讫点重合的路径问题一般被称为推销员问题。直觉方法和启发式方法是求解这类问题的有效方法。,例如，好的路线规划中应没有线路交叉，呈凸形或水滴形。,行车路线和时刻表的制订,原则,划分站点群以分派车辆时，将距离靠近的站点划在一起；,在安排每天各车的运输线路时，同样要使它们的站点群不重叠；,从距离仓库最远的站点开始划分站点群，分派车辆；,各卡车的行车路线应呈水滴状，避免交叉；,对于孤立于站点群之外的站点，可采用其它配送方式，如第三方服务；,各站点规定的取货/送货时间要与行车路线之间协调；,启发式方法,启发式方法中很多是贪婪方法,，例如,最近邻点法，最近插入法等。,最近邻点法就是从某点开始，总是找离目前位置最近的、还未到过的节点作为下一点，直到所有节点走完，再回到起点。得到的结果常常是不理想的。,最近插入法要更进一步，在选择下一点时，不仅仅只考虑当前的一点，而是考虑所有已走过的点。另外，它每一步是整个回路的扩张，即从一开始它就考虑回到起点的成本。方法描述如下：,（1）,找出离起点最近的节点，构成子回路T。,（2）,重复（,3,）直到,T,包含所有节点：,（,3,）从子回路,T,以外的节点中找出离回路,T,中节点最近的节点v，在,T,中找到一条边(a,b)，使av+vb-ab最小，将v插在a,b之间，用av+vb代替(a,b)，构成新的回路,T,例如一家面包房每天要向五家零售店送货，各点之间的行车时间如下：,自,到,面包房,0,零售店,1,零售店,2,零售店,3,零售店,4,零售店,5,面包房,0,0,24,50,38,55,20,零售店,1,22,0,32,23,45,18,零售店,2,47,35,0,15,21,60,零售店,3,39,27,17,0,14,25,零售店,4,57,42,18,16,0,42,零售店,5,21,16,57,21,41,0,扫描法,方法简单，在较快时间内得到一个合理解。,在地图或方格图上确定所有站点的位置；,划分站点群：自仓库向任意方向划一直线，沿一个方向（顺时针或逆时针）旋转，依次根据一辆车能装载的站点划分出所有的站点群；,用“水滴法”或其它方法确定每个站点群的路线计划。,缺点：,在划分站点群时，没有考虑在途总运行时间、各站点的取货/送货时间等。,可以对结果调整（如：与P.158图7-8是自相矛盾的）。,货郎担问题,有一个串村走户卖货郎，他从某个村庄出发，通过若干个村庄一次且仅一次，最后仍回到原出发的村庄，问应如何选择行走路线，能使总的行程最短？,例：求解四个城市旅行推销员问题，其距离矩阵如表。当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按怎样的路线走，能使总的行程距离最短？最短距离为多少？,距离,i,j,1,2,3,4,1,8,5,9,2,6,7,3,5,4,中国邮路问题,邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为,中国邮路问题,。,1、提出问题,返回 结束,上图表示从R1-R15个街道交叉点，街道上的数字表示该街道的长度，单位为米。,首先把这个实际问题转换成一个非负赋权图G，G的顶点代表街与街之间的交叉路口和终端，两个顶点相邻当且仅当这两点所对应的路口有直通街道而中间不通过其他路口，每条边的权是这条边所对应街道的长度。G的通过每条边至少一次的闭途径称为,G的环游,。具有最小权的环游称为G的,最优环游,，则中国邮路问题就是要在赋权图G中找一条最优环游,。,2、分析问题,街道结构图,由上构造右图,3、解决问题,返回 结束,寻找Euler图的最优环游的基本思路：,（1）用双倍边方法求 的一个Euler赋权母图 ，使 达到最小。,（2）用Fleury算法求得 的Euler环游 ,就是 图 的环游；,定理4.2.1,（管梅谷，1960）设 是一个连通的赋权图，是 的一个Euler赋权生成母图，则,当且仅当 没有重复数大于2的边。并且 的每一个长度至少是3的回路中多重边的权和不超过此回路权和的一半。,返回 结束,奇偶点图上作业法（求最优环游算法）：,(1)把 中度为奇数的顶点两两配对，记为 。对每个 ，中取一条 路 ，将 上的每一条边都添加一条边，从而得到 的一个赋权Euler生成母图 。,(2)去掉 中关于 的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接。,(4)用Fleury算法求 的Euler环游。,(3)检查 的每一个回路，如果某个回路 上多重边 的权和超过此回路权和的一半，则将 进行调整：删除 ，的边重数增加 1。,例1,下图(a)给出赋权图 ，是 的四个奇点。根据上述算法,求下图的最优环游。,解：根据上述算法(1)，把 和 配对，和 配对，取 ，并对 中每条边各添加一条边；又取 ，,并对 中每条 边各添加一条边。得图(b).依次按算法，得到图(c),(d),(e),奇偶点图上作业法缺陷：,奇偶点图上作业法需要检查图中的每个回路。随着顶点个数和边数增加，回路个数增加。如下图一，图二。图一回路超过150个，图二回路至少有上千个。,思考：如何求恰好有两个奇点的,赋权图的,最优环游？,设 恰好有两个奇点 和 ，则可以利用2.2节求出 的一条最短 路 ，在 中只要把 中的每一条边中再添加一条边，加上权就可得Eluer图 。可以证明 的Eluer环游就是,的最优环游。下左图的最优环游即为右图。,