物流运输路径规划

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