Quickest flow over time network interdiction: mathematical formulation and a solution method

被引:0
作者
Morowati-Shalilvand, Shahram [1 ]
Shahmorad, Sedaghat [1 ]
Mirnia, Kamal [1 ]
Mehri-Tekmeh, Javad [1 ]
机构
[1] Univ Tabriz, Fac Math Sci, Tabriz, Iran
关键词
Quickest flow; Network interdiction; Flows over time; Mixed integer programming; ALGORITHMS;
D O I
10.1007/s12351-019-00472-6
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper proposes a new problem entitled as "the quickest flow over time network interdiction problem". This problem stands for removing some of network links using a limited interdiction resource with the aim of maximizing the minimum time required to transfer a predefined flow value through a given network. We formulate the quickest flow problem as a linear fractional programming problem and then, we transform it to a linear formulation. Using the linear formulation of the quickest flow problem we formulate the quickest flow network interdiction problem as a mixed integer linear programming problem. We also provide an improved formulation for the quickest flow network interdiction problem which is computationally more efficient than basic linear formulation. Finally, we apply the basic and improved formulations of the quickest flow network interdiction problem on a real world network and several grid networks.
引用
收藏
页码:1179 / 1209
页数:31
相关论文
共 37 条
[1]  
Ahuja R., 1993, Network flows: theory, algorithms, and applications
[2]   The multi-terminal maximum-flow network-interdiction problem [J].
Akgun, Ibrahim ;
Tansel, Barbaros C. ;
Wood, R. Kevin .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 211 (02) :241-251
[3]  
Anderson E.J., 1994, Probability, Statistics and Optimisation, V27, P369
[4]   Partitioning procedures for solving mixed-variables programming problems [J].
Benders, J. F. .
COMPUTATIONAL MANAGEMENT SCIENCE, 2005, 2 (01) :3-19
[5]  
Burkard R. E., 1993, ZOR, Methods and Models of Operations Research, V37, P31, DOI 10.1007/BF01415527
[6]  
Charnes A., 1962, Naval Res. Logistics Q, V9, P181, DOI [DOI 10.1002/NAV.3800090303, 10.1002/nav.3800090303]
[7]  
Corley H. W., 1982, Operations Research Letters, V1, P157, DOI 10.1016/0167-6377(82)90020-7
[8]   Stochastic network interdiction [J].
Cormican, KJ ;
Morton, DP ;
Wood, RK .
OPERATIONS RESEARCH, 1998, 46 (02) :184-197
[9]   Efficient continuous-time dynamic network flow algorithms [J].
Fleischer, L ;
Tardos, É .
OPERATIONS RESEARCH LETTERS, 1998, 23 (3-5) :71-80
[10]  
Fleischer L., 2002, Integer Programming and Combinatorial Optimization. 9th International IPCO Conference Proceedings (Lecture Notes in Computer Science Vol.2337), P36