Maximum Flow Assignment Algorithm for Transshipment Nodes with Flow Demands in Transportation Network
-
摘要: 运输网络中有流量需求的转运结点不遵从流量守恒条件,也不能按源、汇及中间结点归类.为解决这类转运结点的最大流分配问题,将这类转运结点分为汇结点和中间结点.根据Ford-Fulkerson算法寻找增流链的原理,提出了寻找这类转运结点增流链的方法、调整量计算公式和流量调整方法,形成了有流量需求的转运结点最大流分配算法.
-
关键词:
- 最大流 /
- 增流链 /
- 转运结点 /
- Ford-Fulkerson算法 /
- 运输网络
Abstract: In transportation networks,a transshipment node with flow demands fails to conform to flow conservation,and can not be categorized to a source,a sink or an intermediate node.To solve the maximum flow problems of transportation network containing this kind of transshipment nodes,the node is split into a sink node and an intermediate node.Following the principle in Ford-Fulkerson algorithm to search augmenting paths,a maximum flow assignment algorithm was proposed for transportation networks containing transshipment nodes with demands.The proposed algorithm consists of a method to search augmenting paths on the transshipment nodes,a formula to calculate adjustment quantities,and a method to change flows.-
Key words:
- maximum flow /
- augmenting path /
- transshipment node /
- Ford-Fulkerson algorithm /
- transportation network
-
甘爱英.运筹学[M].北京:清华大学出版社,2002:254-278.[2] 焦永兰.管理运筹学[M].北京:中国铁道出版社,2005:145-191.[3] AVINDRA R K,THOMAS M L,JAMES O B.Network flows:theory,algorithms,and applications[M].Princeton:Prentice-Hall,1993:46-210.[4] 凌永发,陈国良,李正明.网络最大流问题典型组合算法研究[J].云南民族大学学报,2006,15(3):211-214.LING Yongfa,CHEN Guoliang,LI Zhengming.Research on the typical algorithms for the maximum-flow problem of networks[J].Journal of Yunnan Nationalities University,2006,15(3):211-214.[5] NI Daiheng.Determining traffic flow characteristics by definition for application in ITS[J].IEEE Transactions on Intelligent Transportation Systems,2007,8(2):181-187.[6] GOLDBERG A V,RAOS.Flows in undirected unit capacity networks[J].SIAM J.Discrete Math.,1999,12(1):1-5.[7] 徐周波,古天龙,赵岭忠.网络最大流问题求解的符号ADD增广路径算法[J].计算机科学,2005,32(10):38-54.XU Zboubo,GU Tianlong,ZHAO Lingzhong.An augmenting-path-based symbolic add algorithm for maximum flow in networks[J].Computer Science,2005,32(10):38-54.[8] HACHTEL G D,SOMENZI F.A symbolic algorithm for maximum flow in 0-1 networks[J].Formal Methods in System Design,1997,10(2-3):207-219.[9] IRISBAHAR R,FROHM E A,CAONA C M.Algebraic decision diagrams and their applications[J].Formal Methods in Systems Design,1997,10(2-3):171-206.[10] 张宪超,万颖瑜,陈国良.一类实际网络中的最小截算法[J].软件学报,2003,14(5):885-890.ZHANG Xianchao,WAN Yingyu,CHEN Guoliang.Approaches to the minimum cut problem in a class of practical networks[J].Journal of Software,2003,14(5):885-890.[11] GOLDBERG A V.Recent developments in maximum flow algorithms[C]//Proceedings of the 6th Scandinavian Workshop on Algorithm Theory,Stockholm.Lecture Notes in Computer Science,1998:1-10.
点击查看大图
计量
- 文章访问数: 1684
- HTML全文浏览量: 60
- PDF下载量: 587
- 被引次数: 0