多品种流交通网络的最大流算法研究_崔皓莹.docx

《多品种流交通网络的最大流算法研究_崔皓莹.docx》由会员分享，可在线阅读，更多相关《多品种流交通网络的最大流算法研究_崔皓莹.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、交通运输工程与信息学报第 12 卷第 2 期 2014 年 6 月 Journal of Transportation Engineering and Information No.2 Vo 1.12 Jun. 2014 多品种流交通网络的最大流算法研宄 崔 皓 莹 寇 玮 华 丁 振 西南交通大学，交通运输与物流学院，成都 610031 摘要：基于 Fcxrd-Fulkerson算法在单一品种网络中最大流量分配的思路，通过对多品种交通网络的网络特 性进行分析，作者将多源多汇的交通网络构建成单源单汇的形式。在保证符合流量约束的条件下，设计了适用 于多品种交通网络的最大流分配算法。在交通网络的实

2、际应用领域里，多品种交通网络的问题普遍存在，因此 该算法为解决实际交通网络的相关问题提供了基础。 关键词：交通网络；多品种流；最大流； Ford-Fulkerson算法 中图分类号： U491 文献标识码 ： A 文章编号： 1672-4747 (2014) 02-0077-06 D0I： 10. 3969/j. issn. 1672-4747. 2014. 02. 006 Study of Maximum Flow Algorithm for Multicommodity Flow Traffic Network CUI Hao-ying KOU ffei-hua DING Zhen Sch

3、ool of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031， China Abstract： Based on Ford-Fulkerson algorithms idea about the maximum flow of a single commoditys traffic network, this paper first analyzed the flow constraints of a multi-species traffic network, then, a multi-

4、source and multi-sink transportation network was constructed for a single-source and single-sink transportation network. In accordance with the flow constraints, this paper built an algorithm which worked for the maximum flow distribution. This algorithm provided some contribution to solve the pract

5、ical problems. This algrithm could be used to the similar problems in a practical traffic network. Key words： Traffic network, multi-species flow, maximum flow, Ford-Fulkerson algorithm 收稿日期 ： 2013-04-24. 作者简介： 崔皓莹 （ 1990-),女，汉族 ， 重庆人，西南交通大学交通运输与物流学院硕士研宄生 ， 主要研究方向为交通运输规 划与管 理。 77 交通运输工程与信息学报 2014 年

6、第 2期 引言 交通网络中的最大流量的分配问题，通常是针对 单一品种的流量分配，在保持流量约束与守恒的条件 下，一般选择基于Ford-Fulkerson算法对流量进行调 整，以达到交通网络的最大流状态 1_1()。但在实际应 用中，多品种流的最大流分配常常会在交通网络中出 现，但是，针对于多品种流的研究成果却很少，因此， 本文在借鉴传统的网络流理论及算法的基础上，构建 了可行的多品种流交通网络最大流分配算法。 本文首先介绍多品种流交通网络问题并对其进 行分析，在保证流量约束的条件下，基于 Ford- Fulkerson 算法的思路， 构造多 品种流交通网络的最 大流算法，在保证网络流量分配为最

7、大流的状态下， 明确每一个品种在网络中的流量分配。 1 多品种流交通网络的引例 为了解释说明交通网络的多品种流问题，也为了 清晰地阐述多品种流交通网络最大流分配的算法研 宄，先给出多品种流交通网络的一个引例。 引例有交通网络如图 1所示，它分别给出了运 送能力和运送费用，即边的容量、费用。其中 A生 产 I和 m两种产品，数量分别为 71和 41; &生产 n 和 in两种产品，数量分别为 51和 81; A生产 i和 n 图 1 交通网络的引例 F i g. 1 An example of transportation network 两种产品，数量分别为 6 t和 3 t。 乃、 _y2、

8、 分别为 三个需求地，M需要 i和 m两种产品，需求量分别为 6t和 7t;少 2需要 n和 m两种产品，需求量分另 ij为 3t 和 9t;_y3需要 I和 n两种产品，需求量分别为 7 t和 8t。 针对此引例，传统的交通网络最大流分配算法 就不能完全适用于多品种交通网络的流量分配问 题，所以，有必要研究多品种流交通网络的最大流 分配算法。 2 多品种交通网络的最大流分配研究 2. 1 多品种交通网络最大流问题分析 给定交通网络 G=(r， ； c， F， nr ) , 其中 7=0,v2,，)，五气 而， ， ) 。对顶点集合 r取定 两个非空子集 X、 7。 X为只发出流量的顶点集合，

9、 7 为只接收流量的顶点集合，且 xnr=0。把 x中的顶 点义称为网络 G的源， 7中的顶点 M称为网络 G的 汇。针对边 A赋 予 两 个 非 负 的 整 数 参 数 ， 分 别 为 边 的 容 量 、流 量 。设 顶点 v#x、 r,即 v,为中 间点，用 /+表示顶点 V,发出的流量之和， / ,)表 示顶点 V,接收的流量之和。设 A:为多品种流中的第 个品种流，其中 Al， 2, ，心为第个品种流在边 (Vi,Vj)上的流量， /+(v,A)表示顶点 Vi发出第 A:个品种流 的流量之和，尸 (VA)表示顶点接收第 A:个品种流的 流量之和。 针 对多品 种交通 网络图 ，边要 遵

10、从两 个约 束条件： (1) 所有品种的流量之和须小于该边的容量，则 有 k=i (2) 所有中间点 v,都要遵从流量守恒条件，即在 保证所有品种的总流量守恒的同时，也要保证每一个 品种的分流量守恒，则有： 78 基于以上分析，多品种交通网络的最大流分配模 多品种流交通网络的最大流算法研究 崔皓莹等 型如模型 (1)所示 : 容量 (容量约束条件） (总流量守恒条件） (品种分流量守恒条件） (边流量等于分量之和） 2. 2 最大流算法思路 (2)单汇的构建 基于所有汇只共需要的品种数心在 G中设 定 g个新汇： /，同时将接收品种的顶点只与顶点 /相连，构建出边以， /)。该边的容量 c(y

11、,， /)等于交 通网络 G的汇只所需要的第灸个品种的数量。 设定 作为单汇，同时构建边 A， 该边的 容量 c A 3/)。 第二步 设集合 X=:v:， ？， A | &=1， 2, ， i=l,2, ,n . V=Vi I z=l,2, ,n . Y=yhyk,y 基于 Ford-Fulkerson算法的思路，本文针对于多 A=l， 2,“ ，心 =1， 2, ，并给定网络图 个初始流 品种交通网络问题设计了其最大流算法。先将多源多 汇的交通网络图 G， 化为单源单汇形式的网络图 (一 般为零 流 ） ， 即 初始的 -f 均为 边（ V, V;)的属性为容量、流量，设表现形式如下， B

12、P c,j,f ii 式中 石 表示边 （ v,_， v； ) 、 Jijl， Jijk ， Jijq) 的总流量；表示各品种的分流量。再给定网络图 个初始的可行流 /(也可以是零流 ）， 对结点进 行标号，判断和寻找是否存在增流链，如果不存在， 则当前网络己为最大流，算法停止；如果存在增流链， 再根据其调整值，调整网络，直至没有赠流链，算法 停止。 针对最大流算法，设计结点 ” 的标号形式如下： v,，边的方向，产 7)，其中， v,表示被标号点 V的前一 个顶点；边的方向通过 “+” 或表示前向边或后向 边；产 (V,)表示增流链中针对于 &品种的调整量。 2. 3 最大流算法步骤 算法步

13、骤如下： 第一步将 G转换为单源单汇的结构形式，构 建新的网络图 (1)单源的构建 - ，设源 x的增流量 / )=+，可以对源 :v: 标号为 (0， +,+ )。 第三步对与 : c有直接连线的顶点 标号，其中 边 o, ：/)为前向边。若乂 此时该边流量不能增力口， 那么不对必标号，即不能对 &品种进行流量调整；若 乂此时流 量 能 增 加 ，存 在 / vx)=min/ :),c； /，那么，顶点乂标号为 ,+/(),可判断出此时 是对该路径的灸品种进行流量调整。 第 四步继 续检查，判断之 后的 边 Ov； )能否成 为增流链的边，边 （ Vi,v7)成为增流链中的边必须满 足如下条

14、件： (1)当 v7ex,r时，判断边 （ v,_, v7)是否为增流 链中的边，分以下两种情况： 当边 ,，以为前向边时：若 ,+， /); 若 /=巧，则该边流量不可以增加，即不对顶点 标号。 基于所有源七共有的品种数心在 G中设定 g 个新源必，同时将顶点，与生产品种的顶点 A相连， 构建出边 (，。该边的容量等于网络 G的源 七所生产的第 A:个品种的数量。 设定 作为单源，同时构建边 c， ),该边的 当边 (，以为后向边时：若 0，则该边流量 可以减少，边为增流链中的边，那么， /(VjminO)， /；/， ,且顶点 巧标 号为 V, 严 (巧 ); 若 = ,则该边流量不可以减

15、少，即不对顶点 v； 标号。 (2)当 时，判 断边 ,， V,)是否为增流链中 79 交通运输工程与信息学报 2014 年 第 2期 的边，分以下情况 : (2)边 (X vj在增流链中为后向边时，边的流量 当 Vy 时 ，设为 的前一 个顶点 ，判断 边 (Vm,只 )是否为增流链中的边，方法同上。 当已 只，时 ，判断 边沙 ， /)是否 为增 流链中的边，分以下两种情况： 顶点只与顶点 /有直接连线，则判断边， /)能否成为为增流链中的边，若边 ， /)为增流链中 的边，那么对顶点 /标号，若边沙， /)不为增流链 中的边，那么不对顶点 /标号。具体方法同上。 顶点 M与顶点 /没有直

16、接连线，则边以， /) 不为增流链中的边，那么不对顶点 /标号。 若顶点 /被标号，则转第五步；若顶点 /没被 调整为 ifiA， ， fijk - 俨 (0)， ， fijq) ，其余品种的流量保持 不变。 第六步返回第三步，不断循环，直到不能找到 增流链为止，即此时网络己为最大流，同时可确定多 品 种 流 交 通 网络 在最大 流情况 下，各 品种的 流量 分配方案。 2. 4 示例求解 为了更好地解释说明多品种交通网络的最大流 分配问题，下面对引例进行求解。 标号，说明此路径无法找到一条增流链，返回第三步 第 一步将 图 1的交 通网络 转换 为单源 单汇的 重新寻找增流链。 第五步当汇

17、被标号，那么说明存在增流链， 此时，按照标号方式的第一项，从汇进行反向追踪， 可得到增流链 2，以及调整量产（ 2)=产 （ y)。 流量的调 整按照以下规则进行： (1)边 ,， v； )在增流链中为前向边时，边的流量 网 络图，并给 个初始 流 ,给 定源 x标号 (0,+， + ), 如图 2所示，边旁数据依次表示容量、流量。 第 二步利 用标号 法寻找 从源 ; c到汇 y的一条增 流链 :v: x1 A Vi 少丄 少， =3，该增流链包含边， JC1),因此是对 I品种增流， 按照 Ford-Fulkerson算 法的思 路调整 流量 ，如图 3 调 整为 (4， _ fy+lk(

18、Q) 其余品种的流量保持 不变。 所示。 第三步反复迭代寻找增流链，对其对应品种进 行流量调整，其余步骤省略，最终的结果如图 4所示。 80 多品种流交通网络的最大流算法研究 崔皓莹等 通过以上步骤，由图 4可以知道该引例的总体方 案，也可以知道该引例各个品种的具体方案。交通网 G的最大流 max z=8+3+3+9+3+4 = 30， 同时可知： 发出 I品种 7t、 in品种 4t; &发出 n品种 5t、 in品 种 7 t， A发出 I品种 51、 n品种 21。 3 结束语 本文通过对多品种交通网络进行分析，并将多源 多汇网络图构建成单源单汇的网络图形式，再基于 Ford-Fulke

19、rson算法在交通网络中寻找增流链以及流 量调整的思路，设计了适合于多品种交通网络的最大 流算法，并通过示例对算法进行了验证。然而，在交 通网络中，仍然存在许多问题需要研究。一个多品种 交通网络的最大流的流值是一定，但分布的状态不同， 因此，最大流的分配方案是多种多样的，那么，也许 就会存在特定的产地或销地有着具体的流量要求的情 况下，求解多品种交通网络的流量分配问题，又或者 在多品种交通网络中的中间点有截流的情况下，对该 网络进行流量分配，这些问题都有待以后的研究。 81 交通运输工程与信息学报 2014 年 第 2期 参考文献 1 寇玮华编著，李宗平主审 .运筹学 M.成都：西 南交通大学

20、出版社， 2013. 2 甘爱英等 .运筹学 M.北京：清华大学出版社， 2002. 3 寇玮华，崔皓莹 .满足交通网络流量增长态势的扩 能优化研究 J.交通运输工程与信息学报， 2012， 10(4)： 19-25. 4 寇玮华，董雪，吕林剑 .交通运输网络中两个结 点间有流量约束的最小费用最大流算法 J.兰州交 通大学学报， 2009，28(6): 104-109. 5 Network Optimization 麻 省 理 工 学 院 开 放 课 件 EB/OL. http:/ 2003. 6 Transportation Flow System.麻省理工学院开放课件 EB/OL. htt

21、p:/ 2002. 7 谢政 ,汤泽滢 .带模糊约束的最小费用流问题 J. 模糊系统与数学 ,1999， 13(2): 90-941. 8 程琳，王炜 . Dial交通量分配模型和选择率问题 的研究J.交通运输系统工程与信息， 2002， 2(3): 29-32. 9 陈光亚 .带有向量值费用函数的交通网络平衡问题 模型与分析 J.交通运输系统工程与信息， 2006， 6(5)： 56-58. 10 任刚，王炜 . 可 直 接 计 算 转 向 流 量 的 改 进 型 Dial交通分配算法 J.中国公路学报， 2005， 18(4): 83-86. (中文编辑：吴继屏 ） 上接第 27页 6 郭

22、钰，宋瑞 .快速公交中间站设施设计研究 J. 交通运输工程与信息学报， 2006, 7(2): 120-126. 7 徐康明，蔡建臣，孙鲁明，冯俊 .快速公交规划 与设计 M.北京：中国建筑工业出版社， 2010: 2-4, 38-40. 8 魏海磊 .我国城市快速公交系统规划方法研究 D. 上海：同济大学， 2008. 9 常成志 .快速公交组合调度优化及仿真评价研究 D.北京：北京交通大学， 2010. 10 孙传娇 .快速公交调度优化研宄 D.西安：长安大 学， 2008 . 11 毛保华，姜帆，刘迁，等 .城市轨道交通 M.北 京：科学出版社， 2001: 162-172. 12 彭辉 . 城 市 轨 道 交 通 系 统 M.北京：人民交通 出版社，2008: 5-211. 13 慕威 . 城 市 轨 道 交 通 运 营 组 织 M.北京：人民 交通出版社， 2012: 29-40. 14 张国宝 .城市轨道交通运输组织 M.北 京 ： 中 国 铁道出版社， 2000: 45-57. 15 毛保华，李夏苗，王明生 .城市轨道交通系统运营 管理 M.北京：人民交通出版社， 2006: 92-98. (中文编辑：刘娉婷 ） 82