1、徐州工程学院毕业设计（论文）图书分类号：密 级：毕业设计（论文）盐城市XX公司运输网络流量最大化研究THE MAXIMIZE TRANSPORTATION NETWORK TRAFFIC RESEARCH OF YANCHENG CITY HUI COMPANY学生姓名学院名称学 号班 级2011物流1班专业名称物流工程指导教师2015年5 月20 日摘要现如今，中国已成为电子产品的消费大国，随着电子产品更新换代速度的变快，社会中青年群体对新型电子产品的追捧性消费也在增加，使得电子材料产品的需求量也在不断地加大，这也就导致了电子材料的运输费用在不断提高。如何使电子材料货物运输流量最大化，提高货
2、物的输送效率，使企业物流输送成本降到最低成为刻不容缓的问题。本文主要研究XX电子材料有限公司货物运输网络流量最大化的问题。首先阐述了研究背景、研究目的及其意义，并了解分析了国内外研究现状及理论成果，提出优化货物运输网络流量的必然性和该研究在企业中所带来的实际价值以及现阶段企业生产运输中存在的问题。其次，本文阐述了网络最大流的相关定义理念、特点、模型设计、计算方法和研究价值。在本文中，选择以盐城市XX电子材料有限公司为研究的企业对象，分析了该企业在运输网络上的现状和存在的问题。而紧接着问题的发现，本文提出企业运输网络流量优化的计算方法，设计了简单的运输模型：主要以标号法，结合增广路等进行图解。最
3、后，以企业的客户选择、运输路线、运输流量优化为目标，以企业交通工具的实际设备情况为基础，通过运输弧的最大通过能力和实际运输流，制定合理的网络优化方案。本文将理论引入实际研究，针对盐城市XX电子材料有限公司货物运输网络流量的实际问题，收集各项数据，运用标号法求解，进而得出盐城市XX公司运输的最大流量。关键词 XX电子公司；货物运输网络；网络最大流；标号法IIAbstractToday, China has become a big consumer electronic products, with the replacement of electronic products faster sp
4、eeds, community youth groups to the pursuit of new electronic products, consumption has increased, so that the demand for electronic materials products are constantly increase, which also led to the transportation costs of electronic materials continues to increase. How to make electronic materials
5、transport network to maximize traffic and improve the efficiency of transport and reduce transport costs become a pressing issue.This paper studies a splendorous maximize Electronic Materials Co., Ltd. freight transport network flow problems. First describes the background, purpose and significance,
6、 and understand and analyze the current situation of domestic and foreign research and theoretical results, the study proposes inevitability and optimize the transport of goods traffic in the enterprise brings real value and the stage production of transport Problems. Secondly, the paper describes t
7、he concept of maximum network flow definitions, characteristics, model design, calculation methods and research value. In this article, choose to Yancheng-Hui Electronic Materials Co., Ltd. for the study of business objects, analyze the current situation and problems of enterprises in the transport
8、network. Then it discovered the problem, we propose a method to calculate corporate transport network traffic optimization, design a simple transport model: mainly labeling method, combined with augmented Road were illustrated. Finally, enterprise customers choose, transport routes, traffic flow opt
9、imization as the goal, the actual situation of enterprises of transport equipment, based on the maximum arc through the transport capacity and the actual transport stream, develop a reasonable network optimization.This paper studies the theory into reality, for practical problem-Hui Electronic Mater
10、ials Co., Ltd. Yancheng cargo transport network traffic, collecting the data, using reference method to solve, and then draw the maximum flow Yancheng Cheng-hui company transport.Keywords Chenghui electronic company Cargo transport network Network maximum flow Label methodIII目 录1 绪论11.1 研究背景11.2 研究目
11、的与意义11.3 国内外研究现状22 基本的理论42.1网络与流42.2增广路52.3截集与截量53 盐城市XX电子材料有限公司的基本情况63.1 XX公司的概况63.2 XX公司运输网络流量现状分析73.2.1以往运输状况73.2.2运输问题分析84 利用标号法找出XX公司运输网络最大流114.1网络最大流相关定理和算法114.1.1最大流相关定理114.1.2寻找最大流的算法：标号法124.2建立模型134.3模型的求解145 货物运输流量的优化建议与前后对比165.1优化货物运输流量的建议165.2企业货物运输流量问题优化前后的对比17结论17致谢19参考文献20I1 绪论1.1 研究背
12、景当今世界，在经济全球化的日益发展的轨迹上，物流业作为一个崭新的研究领域，吸引了众多的目光。那么就会有一个疑问，什么是物流？“物”，简单的说，就是物质，更准确的术语是指物质资料世界中具备物质上的实体特点，同时也具备可以进行物理性位移的物质资料。1“流”是一种物理性的运动，这种物理性运动有着其限定的含义，那就是以地球为参照物，而这种物理性运动时相对于地球而发生的，它的范围可以是地理性的宏观大范围，也可以是同一个地域或者同一个环境中的微观性小运动。“物”和“流”两者的组合，就成为了现今世界建立在目的（包括经济上、军事上、社会条件上的有目的的活动）和实物之间的运动形式。研究一个领域的根本性目的就是其
13、为社会创造出有力的或者便利的价值。作为社会生活中运用极为广泛的问题之一，网络最大流问题在公路系统（车辆流量问题）、供电系统（电流量问题）、通讯网络（信息流问题）等都有应用，也是计算机科学和运筹学重要的研究和探索的内容。20世纪50年代，由福特（Ford），富克逊（Fulkerson）建立的“网络流理论”成为网络流问题应用的重要组成部分。近半个世纪以来，关于网络最大流方面的研究，不但研究成果层出不穷，众多学者们发展突破的速度也令人吃惊。2在这样的大背景上，如何将网络最大流运用到实际的生产生活中显得尤为关键。本文基于以往学者的研究成果上，对网络最大流问题进行了个人的研究与学习，结合网络最大流中的标
14、号算法以及一个发点一个收点的情况，将其应用于盐城XX电子材料有限公司的运输流量优化上。1.2 研究目的与意义网络最大流理论是图论网络中十几个著名理论结果的证明理论基础，而且是企业运作生活中人员分派、运输等问题的重要解决方法之一。比如，港口物流运输操作中需要了解港口的最大运输流量；信息网络中对其信息承载和运输能力的研究；电力系统中对电的流量进行的估算；金融企业对企业本身现金流量的统计等等。涉及的范围可以是一个地域，也可以是一个研究点。从简化角度来讲，网络最大流问题是一个经典的组合优化的问题，也可以说是一个较为特殊的线性规划问题，作为一个运筹学和计算机领域重要的研究内容，网络最大流问题是切实的把社
15、会生活生产中的物流问题具体模型化，从而转化为运输网络中流的问题。从宏观角度，就是解决现实企业的网络中流量问题和费用问题，找出其中最优的解决方案，也能够利用图论以及线性规划等数学方法，将那些表面上看起来和网络流量无关的问题转变为与网络流有关的问题。以此同时，网络最大流问题经常作为一些子问题出现在图论、组合优化以及线性规划等问题中，占有一定的重要比重。3多年来，尽管有着近半个世纪的研究历史，并且众多学者极大地推进了最大流问题的研究进展，但关于网络最大流问题的研究还远远没有结束。首先，在纯粹的理论算法与研究方面，当今社会还未计算出网络最大流问题涉及到的算法时间复杂度的精确下界，现有的研究只是确定一个
16、大概的界限，也没有任何一个通用算法达到或接近问题的下界，即只能是讲问题优化，并不是百分之百的能够达到最大流中的“最”；其次，在众多算法的实际应用性能方面，目前算法的实际优化性能并不能够满足过多的应用问题的要求；同时，网络最大流问题作为特殊的线性规划问题，远比一般的线性规划问题容易解决，在实际操作中发现企业应用领域中的问题和最大流问题两者之间的联系，可以使应用问题更好地得到解决。因此，在网络最大流问题的研究方面，有着十分重要的理论意义和实用价值。同样的，在该问题的应用与研究趋势上，最大流的应用研究一直是富有意义和实用价值的探索工作，对于流量最大化问题上做着深入研究的学者们和致力于探寻解决具体问题
17、的工程师们从不同的角度，以各自独特的发散性思维充实着这方面的研究。不管是从线性规划来看，还是从组合优化角度来看， 最大流问题都是值得深入研究的问题，存在大量优秀的算法。4众多的研究者们也已开发出大量的计算代码。因此，对于许多实际生活中的应用问题，如果能找到这些问题和最大流问题之间的联系， 就能够使问题得到有效的解决。而发现实际生活中的应用问题和流量最大流问题的联系也就成了一项是非常重要的工作。另一方面，事实上，许多生活或者企业的一些应用问题所对应的网络最大流问题都有较为明显的特征， 但是能够充分利用这些特征， 并利用这些特征来设计一些有效地面向应用问题的算法并不是很多。这也是最大流问题的一项十
18、分有意义的工作，也是一个专家学者们渴望突破的新领域。除此之外，网络最大流虽然涉及的领域非常广泛，但是所能运用的问题方面有一定的限制，而这些限制并没有一定的联系特征，在现实的企业实际生产操作中，由于不同企业的生产特点不一样，网络并不是一直存在，构建网络也是一个难点。比如人员的指派，在网络流问题中，并没有考虑到企业人员的个人因素等。再者，网络最大流中“弧”也属于较难定义的一个范畴，饱和弧和非饱和弧的定义也并不是绝对的，与理论知识不同，实际操作问题中还要考虑运输中“弧”的饱和值并不是一成不变，如蔬果等产业在运输过程中，由于贮存方式的不一样，就会造成运输网络中弧的饱和值改变，进而影响整个网络流量优化的
19、方案。这些种种的问题，使得网络最大流问题实际研究的必要性可见一斑。1.3 国内外研究现状网络最大流问题于不同的学术领域，无论是工科学类、文科学类、商业学、经济学等方面起到的作用越来越重要。同时，在各种社交网络的分析中，也有网络最大流的身影，如电子邮件网络、商品网络、留言网络等。5半个世纪以来网络最大流的研究已有丰富的成果，众多学者们提出了一系列的求解网络最大流的算法，这些算法为最大流问题建立了非常完善的理论知识体系。而网络最大流这个问题最初是在1955年由Ford和Fulkerson提出的。该问题的出现，以及之后许多相关的理论和算法的相继问世，不仅密切地联系了运筹学和图论两大模型处理方法，而且
20、开辟了网络最大流应用的新篇章。6网络最大流的求解算法有：（1）通过路径推进流量的增广链算法，其中应用比较广泛的算法有Ford&Fulkerson算法（又称2F标号算法）和Dinic（1970）的增量网络算法，Edmonds-Karp（1972）的最短增广路算法；（2）预留推进算法，这种算法是通过弧的推流能够返回多余的流量，这种算法受到普遍的借鉴与应用，譬如Karzanov的网络阻断流算法，而后又有以Karzanov的理论为基础，由Goldberg和Tarjan（1986）两位学者共同提出且不断改进的推进重标号算法（即二分长度阻断流算法，进一步降低了算法时间的复杂度）等。7表1-1 网络最大流算
21、法时间简表8时间算法名称算法简介1956年一般增广路算法在残量网络中，每次任意寻找一条增广路经进行增广，该算法不适用于复杂网络以及最大弧容量为无理数的网络，其算法时间复杂度依赖于网络中最大弧的容量值，使得该算法具有伪多项式性1973年容量缩放增广路算法在残量网络中，每次寻找一条最大可增广容量和增广路径增广，降低了以往算法的复杂度，有原来的O（v）和O（v）降低到O（）和O（vlog），其中C为整型网络的最大弧容量1970年最短增广路算法在残量网络中，每次找一条含节点数最少的增广路增广，即残量网络中源到汇的BFS路径1972年连续最短增广路算法在Edmonds-Karp的理论基础上进行改造，在每
22、次BFS找增广路时，记录每个点的距离标号，在距离标号所构成的最短路图上，不断地DFS找增广路，即一次标号多次增广1973年一般预留推进算法维护一个预流，不断地对活跃结点执行push操作或relable操作来调整预流，直到不能操作1974年先进先出预留推进算法以先进先出队列维护活跃结点1977年最高标号预留推进算法每次检查具有最高标号的活跃结点在过去的十几年时间里，随着一直在进行的最大流问题深入性研究，许多研究人员们在主流算法的基础上又提出了许多改进的算法。其中“消链”算法就是众多算法之一，该算法是在Ford-Fulkerson标记法在求解网络最大流的时候需要经过多次的标号和反复的调整基础上，受
23、到水流概念的启发，引入极大一致链的概念，该算法主要是通过反复并寻找极大一致链，并求得最终的最大流。9其他还有推荐技术、距离概念、建立动态树等等。而对于特殊的一些网络，如双容量网络、无向网络等算法更是不胜枚举。尽管最大流理论正在被不断地充实和完善，每种算法本身也存在着一定的弊端，而未来的时间长河中，对这些算法的改进仍是一项纷繁复杂的工作，也是一个巨大的挑战。2 基本的理论2.1网络与流先看一个例子，来引出网络流的概念。 v2 v 4 1 24V 3 v 2V 4 3 3 V图2-1 简单的网络图如图，将图2-1看做是某基地运输货物的网络图，Vs为发点，Vt为终点，v，v，v，v为基地中转站，边上
24、（弧上）的数表示该运输网络的最大运货能力，如何安排各网络弧上的输送量，才能使从Vs到Vt的总运输流量最大？运输网络中，货物整体的最大通过能力是有限的，且是一个固定值。而实际的运输流量并不是恒等于运输的可通过容量，上述的问题就是要讨论如何将运输装置的输送能力充分利用，进而取得最好的运输效果（即流量最大），这类问题通常称为最大流问题。10定义1：设有向连通的网络图G=（V，E），网络G的每条边（v，v）上有非负数C称为边（也称为弧）的容量，仅有一个入次为0的点Vs称为发点Send（源点s），一个出次为0的点Vt称为收点Take（汇点t），其余的点为中间点，这样的网络G称为容量网络，常记做G=（V，
25、E，C）。注：这里所说的发点v是指只有从v发出去的弧，而没有指向v的弧；收点v只有弧指向v，而没有从v发出去的弧。11定义2：对任一G中的边（v，v）有流量，称集合=为网络G上的一个流（Flow）。定义3：称满足下列条件的流为可行流：容量限制条件：对G中每条边（v，v），有0C；平衡条件：对中间点v，有=（即中间点v的物资输入量与输出量相等，也称为反对称性=-，也就是说，从节点i到j的净流量值等于从j到i的净流量值的相反数）；对收、发点v，v，有=W（即从v点发出的物资总量等于 v点输入的量，也称为网络流的流量守恒条件）W为网络流的总流量。可行流总是存在的，例如=0就是一个流量为0的可行流。图
26、2-1中，每条弧上的数字给出的就是一个可行流=，它满足定义中的条件（1）和（2）。最大流问题和图的紧密联系，但同时也是一个线性规划问题，求解能够更为直观简便。所谓最大流问题就是在限定的容量网络中，求一个流=，使得总流量v（）达到最大，即 Max v（） -=0 =v（） =v（） 0C（i，js，t）定义4：一个流=，当=C，则称流对边（v，v）是饱和弧，否则称对（v，v）不饱和弧。将=0的弧称为零流弧，将0的弧称为非零流弧。2.2增广路定义5（增广路）：若是网络中连接发点v和收点v的一条路，定义路的方向是从v到v，则路上的弧可分为两类：12(1)弧的方向和路的方向一致，称此类弧为前向弧，所有
27、前向弧的集合记为(2)弧的方向和路的方向不一致，称此类弧为后向弧，所有前向弧的集合记为设是一个可行流，若满足下列条件，称之为（关于可行流的）增广链。在弧（v，v）上，0C，即中每一弧都是非饱和弧。在弧（v，v）上，0C，即中每一弧都是非零流弧。这也称为从v到v的可增广链。可增广链的实际意义是：沿着这条链从v到v输送的流，还有潜力可挖，按照一定的调整方法（下文中的定理），就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量限制条件，即仍为可行流。这样就得到了寻找最大流的方法：从一个可行流开始，寻求关于这个可行流的一条可增广链，如果存在，则可以经过调整，得到一个新的可行流，其流量要比原来的可行
28、流要大，重复这个过程，直到不存在关于该流的可增广链是就得到了最大流。132.3截集与截量设S，TV，ST=，将始点在S中，终点在T中的所有弧构成的集合，记为（S，T）定义6：给出网络D=(V，A，C)，若点集V被剖分为两个非空集合V和，使vV，v，则把弧集（V，）称为是（分离v和v的）截集。14显然，若把某一截集的弧从网络中丢失，则从v到v便不存在路。所以，直观上说，截集是从v到v的必经之路。定义7：给一个截集（V，），把截集（V，）中所有弧的容量之和称为这个截集的容量（简称截量），记为c（V，），即c（V，）=C .不难证明，任何一个可行流的流量v（）都不会超过任一截集的容量。即v（）c（V
29、，）显然，若对于一个可行流，网络中有一个截集（V，），使得v（）=c（V，），则必是最大流，而（V，）必定是D的所有截集中，容量最小的一个，即最小截集。153 盐城市XX电子材料有限公司的基本情况3.1 XX公司的概况盐城市XX电子材料有限公司，隶属于江苏省，位于阜宁县益林镇（如图3-1） 。是一家专业生产绝缘凡立水，稀释剂的厂家，主营行业包括密封材料、绝密设备、保护材料，主营行业为电源（整流）变压器、其他变压器以及电感线圈。其生产的产品在电机线圈、变压器、电器及各种工业马达线圈等精密器件中得到的广泛的应用。公司的厂房区占地面积10000多平方米，员工200多名，其中工程师10名，技术人员28
30、名。公司生产设备和检测仪器都配备齐全。盐城市XX电子材料有限公司（盐城市一元石油化工有限公司）是专业生产销售绝缘凡立水、稀释剂系列产品的企业，已有十多年的历程基础，现公司拥有绝缘凡立水、稀释剂系列的高级工程师、技师等，配备有自带化验室研制设备和生产设备，以达到自主研发绝缘漆、稀释剂系列产品的目的。其中部分产品取得美国UL认证及美国DuPout杜邦公司EIS电器绝缘系统UL1446绝缘漆，而主要生产的高品质液态电器绝缘材料，产品涵盖B、F、H、C级浸渍，被应用于变压器、安定器、工业马达线圈以及其他机械设备。而下图3-1则为XX公司的地理位置。16 图3-1 盐城市XX电子材料有限公司地理图3.2 XX公司运输网络流量现状分析3.2.1以往运输状况XX电子材料公司在运输货物上，配备有微型1.8吨货车2辆，7吨卡车1辆。（1）运输的主要货物如表3-1表3-1 运输货物表货物名称总运量（立方米/月）运输费用（元/月）绝缘凡立水215约200稀释剂377约200绝缘漆UL1446123约400小计515约800 （2）订单分类见表3-2（表中数据为该类订单数量
