期刊名称：An International Journal of Optimization and Control: Theories & Applications (IJOCTA)
印刷版ISSN：2146-5703
出版年度：2012
卷号：2
期号：2
页码：173-186
DOI：10.11121/ijocta.01.2012.0098
语种：English
出版社：An International Journal of Optimization and Control: Theories & Applications (IJOCTA)
摘要：This paper deals with finding most vital links of a network which carries flows over time (also called ”dynamic flows”). Given a network and a time horizon T, Single Most Vital Link Over Time (SMVLOT) problem looks for a link whose removal results in greatest decrease in the value of maximum flow over time (dynamic maximum flow) up to time horizon T between two terminal nodes. SMVLOT problem is formulated as a mixed binary linear programming problem. This formulation is extended to a general case called k-Most Vital Links Over Time (KMVLOT) problem, in which we look for finding those k links whose removal makes greatest decrease in the value of maximum flow over time. A Benders decomposition algorithm is proposed for solving SMVLOT and KMVLOT problems. For the case of SMVLOT problem, the proposed algorithm is improved to a fully combinatorial algorithm by adopting an iterative method for solving existing integer programming problem. However, our experimental results showed the superiority of proposed methods.
关键词：Most vital link: Flows over time: Mixed integer programming
