物流运输路径规划.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 物流运输路径规划,主讲人：邓建新,dengjxin,小李自广西大学营销专业毕业进入利客隆工作前天刚过,1,年，昨天得到了一个好消息，公司调它到总部做配送调度。小李,very,very,高兴，说公司很给力，决定一定要做好这份工作。而公司也希望借用小李的学识，,以,进一步规范企业配送，提高质量，降低成本，在沃尔玛、南城百货等大型超市挤压下争取生存机会。但对小李来说，调度还真是新鲜事。对于干了,1,年的小李，对公司的规模、布局了如指掌。,小李的难题,利客隆 超市分部图,总部,怎么走，成本最低？应该先送哪一个商店？,现需要送,20,吨百货到,A,、,B,等,10,个分店，,每个分店的需求都很零散，,至少需要多少什么型号的车辆？,每天各个分店都有部分百货要运回或转移到,其他分店，怎么运输车辆返空率最低，成本最低？,小李的答案类似解,太原,重庆,武汉,南京,徐州,连云港,上海,郑州,石家庄,塘沽,青岛,济南,天津,北京,长途运输路线问题,长虹街道近年新建了,11,个居民小区，各小区的大致位置及相互间的道路距离如图所示，单位（,100m,），各居住小区居民数为：,2000,3000,3500,3700,5000,2800,4500,。,1,2,3,4,5,6,7,6,4,4,7,2,2,3,5,5,6,7,政府的难题,政府想在,7,个小区准备共建一套医务所、邮局、储蓄所等服务设施，应建于哪一居民小区，使对居民总体来说感到方便。,电信部分拟将布设宽带到各个小区，应如何铺设最为经济？,工作组组织考察，从小区出发，经过各小区（顺序不限），最后到小区再离去，哪条路最近？,第六章 物流运输路径规划,第一节 图的基本概念,第二节 最短路径问题,第三节 最大流问题,第四节 最小费用流问题,第五节 单、多回路运输路线问题,图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。,第六章 物流运输路径规划,随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。,第六章 物流运输路径规划,1736,年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,与位置几何有关的一个问题的解,，解决了著名的哥尼斯堡七座桥问题。,17,世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），,城中有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。,第六章 物流运输路径规划,第六章 物流运输路径规划,哥尼斯堡一角,B,A,C,D,当地的居民热衷于这样一个问题，,一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。,尽管试验者很多，,但是都没有成功。,第六章 物流运输路径规划,为了寻找答案，,1736,年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即,能否从某一点开始不重复地一笔画出这个图形，最终回到原点。,欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。,B,A,C,D,第六章 物流运输路径规划,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。,例,有六支球队进行足球比赛，我们分别用点,v,1,v,6,表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知,v,1,队战胜,v,2,队，,v,2,队战胜,v,3,队，,v,3,队战胜,v,5,队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。,第一节 图的基本概念,第六章 物流运输路径规划,v,3,v,1,v,2,v,4,v,6,v,5,第一节 图的基本概念,我们就把类似以上的几个例子中通过点和点之间的线来反映实际生产和生活中的某些特定对象之间的特定关系的,所构成,图形称为,图（,Graph,）,。一般来说，通常用,点,表示研究,对象,用,点与点之间的线,表示研究对象之间的特定,关系,。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。,第一节 图的基本概念,图论中所研究的图，是指反映或描述自然界或人类社会中，大量的事物及事物之间关系的图形。是,由点和线组成的,。,点称为顶点,，它的集合用,V,（,Vertex,）,表示，顶点通常表示有形或无形的事物。,线称为边,，它的集合用,E,（,Edge,）,表示，边通常表示事物与事物（点与点）之间的联系或特定的关系。,一、图的定义,第一节 图的基本概念,例,1,某地区有五个镇,A,、,B,、,C,、,D,、,E,它们之间有公路相通的情况如图所示。,一、图的定义,在图论中，我们只关心,两点间是否有联系,，,至于公路的大小、等级、状况均无关紧要，亦即,不考虑线段（边）的长度,，,点的位置带有随意性,，它们,并不按比例尺画,，如五个镇之间的连接图也可画成右图表示。,A,B,C,D,E,一、图的定义,定义,1,：,一个图是由点集,V=,v,i,和,V,中元素的无序对集,E=,e,k,所构成的二元组，记作：,G=,（,V,，,E,）,，,其中,v,i,称为顶点，,e,k,称为边。,|V,|,表示顶点个数，,|E,|,表示边的个数。当,V,和,E,都是有限集合时，,G,为有限图，否则，称为无限图。本书只论及有限图。图中所有边都没有方向，称为,无向图,，否则称为,有向图,。例如下面图,6,-3,，即为无向图,.,一、图的定义,无向图,G=,（,V,，,E,）,其中：,V,v,1,、,v,2,、,v,3,、,v,4,、,v,5,E,e,1,、,e,2,、,e,3,、,e,4,、,e,5,、,e,6,、,e,7,并且：,e,1,（,v,1,、,v,2,）,e,2,（,v,1,、,v,2,）,e,3,（,v,1,、,v,3,）,e,4,（,v,1,、,v,4,）,e,5,（,v,3,、,v,4,）,e,6,（,v,3,、,v,3,）,e,7,（,v,2,、,v,5,）,一、图的定义,图,6-3,v,3,v,1,v,2,v,4,v,6,v,5,第一节 图的基本概念,有向图,D,（,V,，,A,）,V,为顶点集,A,（,arc,）为边或弧,关联边,：,和同一个顶点相连的边，均称为该点的关联边，如图,6,-4,中的,e,24,、,e,34,、,e,45,均是,v,4,的关联边。,相邻点,：,一条边的两个顶点，称为相邻点，如,v,2,与,v,4,，,v,4,与,v,5,等是相邻点，而,v,2,与,v,5,则不是。,一、图的定义,图,6-4,一、图的定义,环与多重边,：,两个顶点相同的边称为,环,，如,e,22,，,两个顶点之间的边数,2,时,叫,多重边,如,e,13,e,13,就是二重边。,图,6-4,二重边,环,次,：,一个顶点,v,具有关联边的总数称为该顶点的次，记作,d(,v,),（,每个环视作两条边），如图,6-4,。,d(,v,1,),=3,，,d,(,v,2,),=4,，,d(,v,5,),=1,。,把次为奇数的顶点称,为,奇顶点,，次为偶数,的顶点称为,偶顶点,。,图,6-4,一、图的定义,一、图的定义,悬挂点与孤立点,：,次为,1,的顶点称为,悬挂点,，如,v,5,。,次为,0,的顶点称为,孤立点,，如,v,6,。,图,5-4,v,6,孤立点,悬挂点,简单图,：,无环、无多重边的图称为,简单图,，如图,6-4(a),、,(b),、,(c),，,后面如无特殊说明，均指简单,图。,一、图的定义,图,6-4,（,a,）,图,6-4,（,b,）,图,6-4,（,c,）,子图与支撑子图,：,在图,G=(V,，,E),中，若,V,1,V,，,E,1,E,，,则图,G,1,=(V,1,、,E,1,),称为,G,的,子图,，如图,6-4,中的,(b),就是,(a),的子图。特别地：,V,1,=V,，,E,1,E,时，称,G,1,是,G,的,支撑子图,(,生成子图）。如图,6-4,中,(c),、,(b),都是,(a),的支撑图。,一、图的定义,图,6-4,（,a,）,图,6-4,（,b,）,图,6-4,（,c,）,定理,1,在任何图中顶点次数总和等于边数的,2,倍。,定理,2,任何图中，次为奇数的顶点必有偶数个。,即奇顶点必有偶数个。,一、图的定义,二、连通图,定义,2,无向图,G=(V,，,E),中，称某些点及其关联边的交替序列,v,1,e,1,v,2,e,2,e,n,v,n,为,从,v,1,到,v,n,的一条,链,，,v,1,、,v,n,分别称为链的,始点,和,终点,，链长为,n,。,若一条链的,始点与终点重合,，则称为,闭链,(,在无向图中闭链又称为回路）,，否则，称为,开链,。点边序列中若只有重复的点而无重复的边，则称为,简单链,。点边序列中若既没有重复的点也无重复的边，则称为,初等链,（也称为,通路,）,。,例如在图,6-5,中：,S=v,6,e,6,v,5,e,7,v,1,e,8,v,5,e,7,v,1,e,9,v,4,e,4,v,3,是一,条连接,v,6,、,v,3,的链，链长为,6.,S,1,=v,6,e,6,v,5,e,7,v,1,e,8,v,5,e,5,v,4,e,4,v,3,是一条连接,v,6,、,v,3,的简单,链，链长为,5.,S,2,=v,6,e,6,v,5,e,7,v,1,e,9,v,4,e,4,v,3,是一条连接,v,6,、,v,3,的,初等链。,e,1,e,2,e,3,e,4,e,6,e,7,e,8,e,9,e,10,v,1,v,2,v,3,v,4,v,5,v,6,e,5,二、连通图,图,6-5,连通的,在无向图中，若顶点,v,i,与,v,j,之间存在链，,则称,v,i,与,v,j,是,连通的,。,规定：,v,i,与自身是连通的,连通图,若无向图,G,中的任意两个顶点都是连通的，,则称,G,是,连通图,，,否则称,G,是,非连通图,。,二、连通图,3.,网 络,一个图连同定义在其边集上的实函数一起称为一个网络网络一般是连通图定义在边集上的实函数称为边的权数记为,w,ij,w,(,v,i,，,v,j,),它与边,(,v,i,，,v,j,),具有一一对应关系，可以用以表达网络上的各种有关性质，如路长、流量、费用等等网络的图解即在每条边旁标上相应的权数,若一网络的每条边都是无向边，则称为无向网络，记为,N,(,G,，,w,),或,N,(,V,，,E,),若一网络的每条边都是有向边，则称为有向网络，记为,N,(,D,，,w,),或,N,(,V,，,A,),若一网络中既有无向边，也有有向边，则称为混合网络,所谓网络分析，即对网络进行定性和定量分析，以便为实现某种优化目标而寻求最优方案这方面的典型问题有：最小树问题,，最短路问题,，中心问题，重心问题，,最大流问题,，,最小费用最大流问题,，,网络计划问题,，等等,3.,网 络,从,v,1,到,v,6,的路线是很多的。比如从,v,1,出发，经过,v,2,v,4,到达,v,6,或者从,v,1,出发，经过,v,2,，,v,3,，,v,5,到达,第二节 最短路径问题,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,v,6,等等,。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是,3+6+3=12,单位，按照第二个路线，总长度是,3+1+1+6=11,单位。,第二节 最短路径问题,基本算法有两种,：,Dijkstra,算法：求某一点到其他各点之间的最短距离,矩阵算法：求任意两点之间的距离。,第二节 最短路径问题,1、,双标号法（,Dijkstra,算法），它是在,1959,年提出来的。目前公认，在所有的权,w,ij,0,时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点,v,s,到任意一个点,v,j,的最短路。,二、最短路问题的算法,第二节 最短路径问题,Dijkstra,算法,1,2,3,4,假定1234是14的最短路。,则123一定是13的最短路，,234也一定是24的最短路。,第二节 最短路径问题,Dijkstra,算法,1,2,3,4,反证：设13的最短路为153,。,则1534的路长肯定小于,1234。,这与假设矛盾。,5,第二节 最短路径问题,Dijkstra,算法,设,d,ij,表示两个相邻点,i,j,点距离；如果不相邻,设,L,si,表示不相邻的,S,-,i,之间的距离。,为了标志最短路的点，就对其标号。,整个方法里面有两种标号：,（1）最短路上的点的标号，用P（permanent）表示;,（2）不是最短路上的点的标号，用T(temporary)表示。,第二节 最短路径问题,Dijkstra,算法,步骤：,（1）初始化，从起点s出发，给起点标P号，距离值为0，即,P(s)=0,其余个点标T号，距离为 。,（2）考察与s相应的点，计算s到这些点的距离,然后，在所有标T号的点中，,选择距离最小的那个标P号,。,第二节 最短路径问题,Dijkstra,算法,步骤：,（3）考察新P的点，方法同（2），直到所有点都都考察完毕，标上P号。,（4）根据P号点距离值的来源，追溯最短路径即求出最短路。,二、最短路问题的算法,例,6,求,v,1,到,v,6,的最,短路。,+,+,+,+,+,（,1,）首先给,v,1,以,P,标号,，,P(,v,1,),0,，,给其余所有点,T,标号，,T,(,v,j,),（,j,=2,，,3,，,6),(0),P,标号以,（）,形式标在结点旁边，,T,标号以不带（）的数字标在结点旁边,.,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,二、最短路问题的算法,P(,v,2,)=,3,（,3,）,5,P(,v,3,)=,4,（,4,）,+,+,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,+,+,+,(0),9,（,2,）考察,v,1,:,T,(,v,2,)=,min,T,(,v,2,),，,P(,v,1,),+,a,12,min,，,0,3=3,T,(,v,3,)=,min,T,(,v,3,),，,P(,v,1,),+,a,13,min,，,0,5=5,所以，,P(,v,2,)=,3,（,3,）考察,v,2,:,T,(,v,3,)=,min,T,(,v,3,),，,P(,v,2,),+,a,23,min 5,，,3,1=4,T,(,v,4,)=,min,T,(,v,4,),，,P(,v,2,),+,a,24,min,，,3,6=9,所以，,P(,v,3,)=,4,T(,v,3,)=,5,T(,v,4,)=,9,二、最短路问题的算法,P(,v,5,)=,5,（,3,）,（,4,）,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,+,+,(0),9,（,5,）,T(,v,4,)=,8,（,4,）考察,v,3,:,T,(,v,5,)=,min,T,(,v,5,),，,P(,v,3,),+,a,35,min,，,4,1=5,T,(,v,4,)=,min,T,(,v,4,),，,P(,v,3,),+,a,34,min 9,，,4,4=8,所以，,P(,v,5,)=,5,（,5,）考察,v,5,:,T,(,v,6,)=,min,T,(,v,6,),，,P(,v,5,),+,a,56,min,，,5,6=11,T,(,v,4,)=,min,T,(,v,4,),，,P(,v,5,),+,a,54,min 8,，,5,2=7,所以，,P(,v,4,)=,7,8,T(,v,6,)=,11,11,（,7,）,P(,v,4,)=,7,二、最短路问题的算法,（,3,）,（,4,）,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,11,(0),（,5,）,（,7,）,（,6,）考察,v,4,:,T,(,v,6,)=,min,T,(,v,6,),，,P(,v,4,),+,a,46,min 11,，,7,3=10,所以，,P(,v,6,)=,10,所有点都标上,P,标号,P(,v,6,)=,10,(10),(7),标出最短路,v,1,到,v,6,的最短路,可从,v,1,开始，根据永久性标号数值回溯得到,(7),标出最短路,最短路径是：,v,1,v,2,v,3,v,5,v,4,v,6,，,路长,10,同,时得到，到其余各点的最短路，即各点的永久性标号,P,（,v,i,）,注意：,双标号法只适用于所有,w,ij,0,的,情形，当赋权有向图中存在负权时，则算法失效,（,3,）,（,4,）,v,6,v,5,v,3,v,1,v,4,v,2,3,6,5,1,1,2,4,3,6,(0),（,5,）,（,7,）,(10),二、最短路问题的算法,