1、 I THE MAXIMIZE TRANSPORTATION NETWORK TRAFFIC RESEARCH OF YANCHENG CITY HUI COMPANY Abstract Today, China has become a big consumer electronic products, with the replacement of electronic products faster speeds, community youth groups to the pursuit of new electronic products, consumption has incre
2、ased, 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 transport network to maximize traffic and improve the efficiency of transport and reduce tran
3、sport 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, and understand and analyze the current situation of domestic and foreign research and theor
4、etical 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 the concept of maximum network flow definitions, characteristics, model design, calculation m
5、ethods 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 network. Then it discovered the problem, we propose a method to calculate corporate transpor
6、t 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 optimization as the goal, the actual situation of enterprises of transport equipment, based on
7、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 Materials Co., Ltd. Yancheng cargo transport network traffic, collecting the data, using referen
8、ce 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 methodI XX 市 XX 公司运输网络流量最大化研究 摘要 现如今，中国 已成为电子产品的消费大国，随着电子产品更新换代速度的 变快 ， 社会中青年 群体对新型电子产品的追捧 性消费也在增加 ， 使得电子材料产品的需求量也在不断地加大，这也
9、就导致了电子材料的运输费用在不断提高。如何使电子材料货物运输流量最大化， 提高 货物的输送效率 ， 使企业物流输送成本 降 到最 低成为刻不容缓的问题。 本文 主要 研究 XX 电子材料有限公司货物运输网络流量最大化的问题 。首先阐述了研究背景、 研究 目的及 其 意义，并 了解 分析 了 国内外研究现状及理论成果，提出 优化货物运输网络流量 的必然性 和该研究在企业中 所带来的实际价值以及现阶段 企业生产运输中 存在的问题。其次，本文阐述了 网络最大流的相关定义理念、 特点、 模型设计、计算方法 和研究 价值。在本文中，选择以 盐城市 XX 电子材料有限公司 为研究 的企业 对象，分析了该企
10、业在运输网络上的 现状和存在的问题。 而紧接着问题的发现 ， 本文 提出 企业运输网络流量优化的计算方法 ， 设计了简单的运输模型：主要以标号法，结合增广路等进行图解 。 最后， 以 企业的客户选择、运输路线、运输流量优化为目标 ， 以企业交通工具的实际设备情况为基础，通过运输弧的最大通过能力和实际运输流，制定合理的网络优化方案。 本文将理论引入实际研究，针对 盐城市 XX 电子材料有限公司货物运输网络流量的实际问题 ，收集各项数据，运用 标号法 求解， 进而 得出 盐城市 XX 公司运输的最大流量 。 关键词 XX 电子公司 ； 货物运输网络 ； 网络最大流 ； 标号法 I 目 录 1 绪论
11、 . 1 1.1 研究背景 . 1 1.2 研究目的与意义 . 1 1.3 国内外研究现状 . 2 2 基本的理论 . 5 2.1 网络与流 . 5 2.2 增广路 . 6 2.3 截集与截量 . 7 3 盐城市 XX 电子材料有限公司的基本情况 . 8 3.1 XX 公司的概况 . 8 3.2 XX 公司运输网络流量现状分析 . 8 3.2.1 以往运输状况 . 8 3.2.2 运输问题分析 . 9 4 利用标号法找出 XX 公司运输网络最大流 . 13 4.1 网络最大流相关定理和算法 . 13 4.1.1 最大流相关定理 . 13 4.1.2 寻找最大流的算法：标号法 . 14 4.2
12、建立模型 . 15 4.3 模型的求解 . 15 5 货物运输流量的优化建议与前后对比 . 18 5.1 优化货物运输流量的建议 . 18 5.2 企业货物运输流量问题优化前后的对比 . 18 结论 . 19 致谢 . 21 参考文献 . 22 1 1 绪论 1.1 研究背景 当今世界，在经济全球化的日益发展的轨迹上，物流业作为一个崭新的研究领域，吸引了众多的目光。 那么就会有一个疑问， 什么是物流？“物” ，简单的说，就是物质，更准确的术语 是指物质资料世界中具备物质 上的 实体特点 ，同时也具备 可以进行物理性位移的物质资料 。 1“流”是 一种 物理性 的 运动，这种物理性运动有 着 其
13、限定的 含义 ， 那 就是以地球为参照物， 而这种物理性运动时 相对于地球而发生的，它的范围可以是地理性的 宏观 大范围，也可以是同一个地域或者同一个环境中的微观 性小 运动。“物”和“流” 两者的组合，就成为了现今世界建立在目的（包括经济上、军事上、社会条件上的有目的的活动）和实物之间的运动形式。研究一个领域的根本性目的就是 其 为社会创造出有力的或者便利的价值。 作为社会生活中运用极为广泛的问题之一， 网络最大流问题在公路系统（车辆流量问题）、供电系统（电流量问题）、通讯网络（信息流问题）等都有应用，也是 计算机科学和运筹学重要的 研究和探索的 内容。 20 世纪 50 年代，由福特（ F
14、ord），富克逊（ Fulkerson）建立的“网络流理论”成为网络 流问题 应用的重要组成部分。 近半个世纪以来 ，关于网络最大流方面的研究， 不但 研究成果层出不穷 ，众多学者们发展突破的速度也令人吃惊。 2 在这样的大背景上，如何将网络最大流运用到实际的生产生活中显得尤为关键。本文基于以往学者的研究成果上，对网络最大流问题进行了个人的研究与学习，结合网络最大流中的标号算法以及一个发点一个收点的情况，将其应用于盐城 XX 电子材料有限公司的运输流量优化上。 1.2 研究目的与意义 网络最大流理论是图论网络中十几个著名理论结果的证明理论基础，而且是企业运作生活中人员分派、运输等问题的重要解决
15、方法之一。比如，港口物流运输操作中需要了解港口的最大运输流量；信息网络中对其信息承载和运输能力的研究；电力系统中对电的流量进行 的 估算；金融企业对企业本身现金流量的统计等等。涉及的范围可以是一个地域，也可以是一个研究点。从简化角度来讲，网络最大流问题是一个经典的组合优化的问题，也可以说是一个较为特殊的线性规划问题，作为一个运筹学和计算机领域重 要的研究内容，网络最大流问题是切实的把社会生活生产中的物流问题具体模型化，从而转化为运输网络中流的问题。从宏观角度，就是解决现实企业的网络中流量问题和费用问题，找出其中最优的解决方案，也 能够利用 图论以及线性规划等 数学 方法 ， 将 那些 表面 上
16、看起来和 网络流量无关的问题转 变 为 与 网络流 有关的 问题。以此同时 ， 网络最大流问题经常作为一些子问2 题出现在图论、组合优化以及线性规划等问题中 ， 占有一定的重要比重。 3 多年来 ， 尽管 有着近半个世纪的研究历史 ， 并且众 多学者极大地推进了最大流问题的研究进展 ， 但关于 网络 最大流问题的研究还远 远没有结束 。 首先 ， 在 纯粹的 理论算法 与 研究方面 ， 当今社会 还 未计算出网络 最大流问题 涉及到的 算法时间复杂度的精确下界 ， 现有的研究只是确定一个大概的界限 ， 也 没有任何一个通用算法达到或接近问题的下界 ，即只能是讲问题优化，并不是百分之百的能够达到
17、最大流中的“最” ； 其次 ， 在 众多 算法的实际 应用 性能方面 ， 目前算法的实际 优化 性能 并 不 能够 满足 过多的 应用问题的要求 ； 同时 ，网络 最大流问题作为特殊的线性规划问题 ， 远比一般 的 线性规划问题容易解决 ， 在实际操作中 发现 企业 应用领域中的问题和最大流问题 两者之间的 联系 ， 可以使应用问题更好地得到解决 。 因此 ，在 网络 最大流问题的研究 方面， 有 着 十分重要的理论意义和实用价值 。同样的 ， 在 该 问题 的 应用 与 研究趋势上， 最大流的应用研究一直是 富有 意义 和实用价值 的 探索 工作 ， 对于流量最大化 问题 上做着深入 研究
18、的 学 者 们 和 致力于探寻解决 具体问题的工程师 们 从不同的角度 ，以各自独特的发散性思维 充实着这方面的研究 。 不管是 从线性规划 来看， 还是从组合优化角度来看 ， 最大流问题都是 值得 深入 研究 的问题 ， 存在大量优秀的算法 。 4众 多 的 研究者 们 也已开发出大量的 计算 代码 。 因此 ， 对 于 许多实际 生活中的 应用问题 ， 如果能找到 这些问题 和最大流问题 之间 的联系 ， 就能够 使问题得到有效的解决 。而 发现实际 生活中的 应用问题和 流量 最大流问题的联系 也就成了一项 是非常重要的工作 。另一方面 ， 事实上 ， 许多 生活或者企业的一些 应用问题
19、所对应的 网络 最大流问题都有 较为明显的特征 ， 但 是能够 充分利用这些特征 ， 并利用这些特征来 设计 一些有效地 面向应用问题的算法并不 是很 多 。 这也是 最大流问题的一项 十分有意义的工作 ，也是一个专家学者们渴望突破的新领域。 除此之外，网络最大流虽然涉及的领域非常广泛，但是所能运用的问题方面有一定的限制，而这些限制并没有一定的联系特征，在现实的企业实际生产操作中，由于不同企业的生产特点不一样，网络并不是一直存在，构建网络也是一个难点。比如人员的指派，在网络流问题中，并没有考虑到企业人员的个人因素等。再者，网络最大流中“弧”也属于较难定义的一个范畴，饱和弧和非饱和弧的定义也并不
20、是绝对的，与理论知识不同，实际操作问题中还要考虑运输中“弧”的饱和值并不是一成不变，如蔬果等产业在运输过程中，由于贮存方式的不一样，就会造成运输网络中弧的饱 和值改变，进而影响整个网络流量优化的方案。这些种种的问题，使得网络最大流问题实际研究的必要性可见一斑。 1.3 国内外研究现状 网络最大流问题于不同的学 术 领域，无论是工 科学类 、文 科学类 、商业学、经济学等方面起到的作用越来越重要。同时，在各种社交网络的分析中，也有网络最大流的身影，如电子邮件网络、商品网络、留言网络等。 5 3 半个世纪以 来网络最大流的研究已有丰富的成果，众多学者们提出了一系列的求解网络最大流的算法，这些算法为
21、最大流问题建立了非常完善的理论知识体系。而网络最大流这个问题最初是在 1955 年由 Ford 和 Fulkerson 提出的。该问题的出现，以及之后许多相关的理论和算法的 相继问世 ， 不仅 密切 地 联系了运筹学和图论 两大模型处理方法 ， 而且 开辟了网络最大流应用的新篇章。 6 网络最大流的 求解算法 有： （ 1）通过路径推进流量的增广链算法，其中应用比较广泛的算法有 Ford&Fulkerson算法（又称 2F 标号算法）和 Dinic（ 1970）的增量网络算法， Edmonds-Karp（ 1972）的最短增广路算法； （ 2）预留推进算法，这种算法是通过 弧 的推流能够返回多
22、余 的 流量， 这种算法受到普遍的借鉴与应用，譬如 Karzanov 的网络阻断流算法， 而后又有以 Karzanov 的 理论为 基础，由 Goldberg 和 Tarjan（ 1986） 两位学者共同提出且 不断改进的推进重标号算法（即二分长度阻断流算法，进一步降低了算法时间的复杂度）等。 7 表 1-1 网络 最大流算法时间简表 8 时间 算法名称 算法简介 1956 年 一般增广路算法 在残量网络中，每次任意寻找一条增广路经进行增广，该算法不适用于复杂网络以及最大弧容量为无理数的网络，其算法时间复杂度依赖于网络中最大 弧 的容量值，使得该算法具有伪多项式性 1973 年 容量缩放增广路
23、算法 在残量网络中，每次寻找一条最大可增广容量和增广路径增广，降低了以往算法的复杂度，有原来的 O（ v 2 ） 和 O（ v2 ） 降低到 O（ log2 C ） 和 O（ vlogC ），其中 C 为整型网络的最大弧容量 1970 年 最短增广路算法 在残量网络中，每次找一条含节点数最少的增广路增广，即残量网络中源到汇的 BFS 路径 1972 年 连续最短增广路算法 在 Edmonds-Karp 的理论基础上进行改造，在每次 BFS找增广路时，记录每个点的距离标号，在距离标号所构成的最短路图上，不断地 DFS 找增广路，即一次标号多次增广 1973 年 一般预留推进算法 维护一个预流，不
24、断地对活跃结点执行 push 操作或relable 操作来调整预流，直到不能操作 1974 年 先进先出预留推进算法 以先进先出队列维护活跃结点 1977 年 最高标号预留推进算法 每次检查具有最高标号的活跃结点 在过去的 十几年时间里，随着 一直在进行 的 最大流问题深入 性 研究 ，许多研究人员们在主流算法的基础上 又 提出了许多改进的算法。 其中 “消链”算法 就是众多算法之一，该算法 是 在 Ford-Fulkerson 标记法在求解网络最大流的时候需要经过多次的标号和反复的4 调整基础上 ， 受 到 水流概念的启发，引入极大一致链的概念，该算法主要 是 通过反复并寻找极大一致链，并求
25、得最终的最大流。 9其他还有推荐技术、距离概念、建立动态树等等。而对于特殊的一些网络，如双容量网络、无向网络等算法更是不胜枚举。尽管最大流理论正在被不断地充实和完善，每种算法本身也存在着一定的弊端，而未来的时间长河中，对这些算法的改进仍是一项纷繁 复杂的工作，也是一个巨大的挑战。 5 2 基本的理论 2.1 网络与流 先看一个例子，来引出网络流的概念。 v1 2 v2 4 1 2 4 Vs 3 v3 2 Vt 4 3 3 V4 图 2-1 简单的网络图 如图，将图 2-1 看做是 某基地运输货物的 网 络图 ， Vs 为 发点 ， Vt 为终点， v1 ， v2 ，v3 ， v4 为 基地 中
26、转站，边上 （弧上） 的数表示该 运输网络 的最大 运货 能力，如何安排各 网络弧上的输送量 ，才能使从 Vs 到 Vt的总 运输流量 最大？ 运输 网络中， 货物整体的 最大通过能力是有限的， 且是一个固定值。而 实际 的运输 流量 并不是恒 等于 运输的可通过 容量，上述 的 问题就是要讨论如何 将运输 装置的 输送 能力充分利用， 进而 取得最好 的运输 效果（即流量最大），这类问题通常称为最大流问题。 10 定义 1：设有向 连通的网络图 G=（ V， E）， 网络 G的每条边（ vi ， vj ）上有非负数 Cij称为边（也称为弧）的容量，仅有一个入次为 0 的点 Vs 称为发点 S
27、end（源点 s），一个出次为 0 的点 Vt 称为收点 Take（汇点 t），其余的点为中间点，这样的网络 G 称为容量网络，常记做 G=（ V， E， C）。注：这里所说的发点 vs 是指只有从 vs 发出去的弧，而没有指向 vs 的弧；收点 vt 只有弧指向 vt ，而没有从 vt 发出去的弧。 11 定义 2：对任一 G 中的边（ vi ， vj ）有流量 ij ，称集合 = ij 为网络 G上的一个流（ Flow）。 定义 3：称满足下列条件的流为可行流： 容量限制条件：对 G中每条边（ vi ， vj ），有 0 ij Cij ； 平衡条件：对中间点 vi ，有iij =kki （
28、即中间点 vi 的物资输入量与输出量相等，也称为反对称性 ij =-ji ，也就是说，从节点 i到 j的净流量 值 等于从 j到 i的净流量 值 的相反数）；对收、发点 vt ， vs ，有isi =jjt =W（即从 vs 点发出的物资总量等于 vt 点输入的量，也称为网络流的流量守恒条件） W 为网络流的总流量。 6 可行流总是存在的，例如 = 0就是一个流量为 0 的可行流。图 2-1 中，每条弧上的数字给出的就是一个可行流 = ij ，它满足定义中的条件（ 1）和（ 2）。 最大流问题和图的紧密联系，但同时也是一个线性规划问题，求解能够更为直观简便。所谓最大流问题就是在 限定的 容量网
29、络中，求一个流 = ij ，使得总流量 v（）达到最大，即 Max v（） AVV ），（ jiij - AVV ），（ ijji =0 AVV ），（ jssj =v（ ） AVV ），（ tjjt =v（） 0 ij Cij （ i， j s， t） 定义 4：一个流 = ij ，当 ij =Cij ，则称流对边（ vi ， vj ）是饱和弧，否则称对（ vi ， vj ）不饱和弧。将 ij =0 的弧称为零流弧，将 ij 0 的弧称为非零流弧。 2.2 增广路 定义 5（增广路）： 若是网络中连接发点 vs 和收点 vt 的一条路，定义路的方向是从 vs 到 vt ，则路上的弧可分为两类
30、： 12 (1)弧的方向和路的方向一致，称此类弧为前向弧，所有前向弧的集合记为 (2)弧的方向和路的方向不一致，称此类弧为后向弧，所有前向弧的集合记为 - 设是一个可行流，若满足下列条件，称之为（关于可行流的）增广链。 在弧（ vi ， vj ） 上， 0 ij Cij ，即 中每一弧都是非饱和弧。 在弧（ vi ， vj ） - 上， 0ij Cij ，即 - 中每一弧都是非零流弧。 这也称为从 vs 到 vt 的可增广链。 可增广链的实际意义是：沿着这条链从 vs 到 vt 输送的流，还有潜力可挖，按照一定的调整方法（下文中的定理），就可以把流量提高，调整后的流，在各点仍满足平衡条件及容量
31、限制条件，即仍为可行流。这样就得到了寻找最大流的方法：从一个可行流开始，寻求关于这个可行流 的一条 可增广链， 如果 存在，则可以经过调整，得到一个新的可行流，其流量要比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链是就得到7 了最大流。 13 2.3 截集与截量 设 S， T V， S T=，将始点在 S 中，终点在 T中的所有弧构成的集合，记为（ S， T） 定义 6：给出网络 D=(V， A， C)，若点集 V 被剖分为两个非空集合 V1 和 V 1 ，使 vs V1 ， vt V 1 ，则把弧集（ V1 ， V 1 ）称为是（分离 vs 和 vt 的）截集。 14 显然，
32、若把某一截集的弧从网络中丢失，则从 vs 到 vt 便不存在路。所以，直观上说，截集是从 vs 到 vt 的必经之路。 定义 7：给一个截集（ V1 ， V 1 ），把截集（ V1 ， V 1 ）中所有弧的容量之和称为这个截集的容量（简称截量），记为 c（ V1 ， V 1 ），即 c（ V1 ， V 1 ） = ），（），（ 1v1vji VVCij .不难证明，任何一个可行流的流量 v（）都不会超过任一截集的容量。即 v（） c（ V1 ， V 1 ） 显然，若对于一个可行流 * ，网络中有一个截集（ V*1 ， V *1 ） ， 使 得 v（ * ） =c（ V*1 ，V *1 ），则 * 必是最大流，而（ V*1 ， V *1 ）必定是 D 的所有截集中，容量最小的一个，即最小截集。 15
