Ramamoorthy, Prasanna, Jayaswal, Sachin, Sinha, Ankur and Vidyarthi, Navneet (2018) Multiple Allocation Hub Interdiction and Protection Problems: Model Formulations and Solution Approaches. European Journal of Operational Research . ISSN 03772217 (In Press)

Text (application/pdf)
970kBRamamoorthy2018.pdf  Accepted Version Available under License Spectrum Terms of Access. 
Official URL: http://dx.doi.org/10.1016/j.ejor.2018.03.031
Abstract
In this paper, we present computationally efficient formulations for the multiple allocation hub interdiction and hub protection problems, which are bilevel and trilevel mixed integer linear programs, respectively. In the hub interdiction problem, the aim is to identify a subset of r critical hubs from an existing set of p hubs that when interdicted results in the maximum postinterdiction cost of routing flows. We present two alternate ways of reducing the bilevel hub interdiction model to a single level optimization problem. The first approach uses the dual formulation of the lower level problem. The second approach exploits the structure of the lower level problem to replace it by a set of closest assignment constraints (CACs). We present alternate sets of CACs, study their dominance relationships, and report their computational performances. Further, we propose refinements to CACs that offer computational advantages of an orderofmagnitude compared to the one existing in the literature. Further, our proposed modifications offer structural advantages for Benders decomposition, which lead to substantial computational savings, particularly for large problem instances. Finally, we study and solve large scale instances of the trilevel hub protection problem exactly by utilizing the ideas developed for the hub interdiction problem.
Divisions:  Concordia University > John Molson School of Business > Supply Chain and Business Technology Management 

Item Type:  Article 
Refereed:  Yes 
Authors:  Ramamoorthy, Prasanna and Jayaswal, Sachin and Sinha, Ankur and Vidyarthi, Navneet 
Journal or Publication:  European Journal of Operational Research 
Date:  29 March 2018 
Digital Object Identifier (DOI):  10.1016/j.ejor.2018.03.031 
Keywords:  LocationHubandSpoke networkInterdictionProtectionBenders Decomposition 
ID Code:  983685 
Deposited By:  MICHAEL BIRON 
Deposited On:  06 Apr 2018 16:30 
Last Modified:  29 Mar 2020 00:00 
References:
D. Aksen, S.Ş. Akca, N. ArasA bilevel partial interdiction problem with capacitated facilities and demand outsourcing Computers & Operations Research, 41 (2014), pp. 346358D. Aksen, N. ArasA bilevel fixed charge location model for facilities under imminent attack Computers & Operations Research, 39 (7) (2012), pp. 13641381
D. Aksen, N. Aras, N. PiyadeA bilevel pmedian model for the planning and protection of critical facilities Journal of Heuristics, 19 (2) (2013), pp. 373398
D. Aksen, N. Piyade, N. ArasThe budget constrained rinterdiction median problem with capacity expansion Central European Journal of Operations Research, 18 (3) (2010), pp. 269291
R. Albert, H. Jeong, A. BarabasiError and attack tolerance of complex networks Nature, 406 (2002), pp. 378382
S. Alumur, B.Y. KaraNetwork hub location problems: The state of the art European journal of operational research, 190 (1) (2008), pp. 121
Y. An, Y. Zhang, B. ZengThe reliable hubandspoke design problem: Models and algorithms Transportation Research Part B: Methodological, 77 (2015), pp. 103122
N. AssimakopoulosA network interdiction model for hospital infection control Computers in Biology and Medicine, 17 (6) (1987), pp. 413422
C. Audet, P. Hansen, B. Jaumard, G. SavardLinks between linear bilevel and mixed 0–1 programming problems Journal of optimization theory and applications, 93 (2) (1997), pp. 273300
N. Azizi, S. Chauhan, S. Salhi, N. VidyarthiThe impact of hub failure in hubandspoke networks: Mathematical formulations and solution techniques Computers & Operations Research, 65 (2016), pp. 174188
J. BendersPartitioning procedures for solving mixed integer programming problems Numerische Mathematik, 52 (1962), pp. 238252
O. Berman, Z. Drezner, A. Tamir, G.O. WesolowskyOptimal location with equitable loads Annals of Operations Research, 167 (1) (2009), pp. 307325
G. Brown, M. Carlyle, J. Salmern, K. WoodDefending critical infrastructure Interfaces, 36 (6) (2006), pp. 530544
R.S. de Camargo, G. de Miranda Jr, H.P.L. LunaBenders decomposition for the uncapacitated multiple allocation hub location problem Computers & Operations Research, 35 (4) (2008), pp. 10471064
R.S. de Camargo, G. de Miranda Jr, H.P.L. LunaBenders decomposition for hub location problems with economies of scale Transportation Science, 43 (1) (2009), pp. 8697
J.F. CampbellInteger programming formulations of discrete hub location problems European Journal of Operational Research, 72 (2) (1994), pp. 387405
J.F. CampbellHub location and the phub median problem Operations Research, 44 (6) (1996), pp. 923935
J.F. Campbell, M.E. O’KellyTwentyfive years of hub location research Transportation Science, 46 (2) (2012), pp. 153169
P. Cappanera, M.P. ScaparraOptimal allocation of protective resources in shortestpath networks Transportation Science, 45 (1) (2011), pp. 6480
S. Chaharsooghi, F. Momayezi, N. GhaffarinasabAn adaptive large neighborhood search heuristic for solving the reliable multiple allocation hub location problem under hub disruptions International Journal of Industrial Engineering Computations, 8 (2) (2017), pp. 191202
R. Church, M.P. ScaparraAnalysis of facility systems reliability when subject to attack or a natural disaster Critical infrastructure, Springer Berlin Heidelberg (2007), pp. 221241
R.L. Church, J.L. CohonMultiobjective location analysis of regional energy facility siting problems Technical Report, Brookhaven National Lab., Upton, NY (USA) (1976)
R.L. Church, M.P. ScaparraProtecting critical assets: the r interdiction median problem with fortification Geographical Analysis, 39 (2) (2007), pp. 129146
R.L. Church, M.P. Scaparra, R.S. MiddletonIdentifying critical infrastructure: the median and covering facility interdiction problems Annals of the Association of American Geographers, 94 (3) (2004), pp. 491502
R. Collado, D. PappNetwork Interdiction  Models, Applications and Unexplored directions Research report, Rutgers University (2012)
I. Contreras, J.F. Cordeau, G. LaporteBenders decomposition for large scale Operations Research, 59 (2011), pp. 14771490
I. Contreras, J.F. Cordeau, G. LaporteBenders decomposition for largescale uncapacitated hub location Operations research, 59 (6) (2011), pp. 14771490
I. Contreras, J.F. Cordeau, G. LaporteThe dynamic uncapacitated hub location problem Transportation Science, 45 (1) (2011), pp. 1832
I. Contreras, E. Fernández, A. MarínThe tree of hubs location problem European Journal of Operational Research, 202 (2) (2010), pp. 390400
I. Contreras, M. Tanash, N. VidyarthiExact and heuristic approaches for the cycle hub location problem Annals of Operations Research (2016), pp. 123
H. Corley, D.Y. ShaMost vital links and nodes in weighted networks Oper. Res. Lett., 1 (4) (1982), pp. 157160
K.J. Cormican, D.P. Morton, R.K. WoodStochastic network interdiction Operations Research, 46 (2) (1998), pp. 184197
G. Dobson, U.S. KarmarkarCompetitive location on a network Operations Research, 35 (4) (1987), pp. 565574
J. Ebery, M. Krishnamoorthy, A. Ernst, N. BolandThe capacitated multiple allocation hub location problem: Formulations and algorithms European Journal of Operational Research, 120 (3) (2000), pp. 614631
S. Elhedhli, F.X. HuHubandspoke network design with congestion Computers & Operations Research, 32 (6) (2005), pp. 16151632
A.T. Ernst, M. KrishnamoorthyEfficient algorithms for the uncapacitated single allocation phub median problem Location science, 4 (3) (1996), pp. 139154
I. Espejo, A. Marín, A.M. RodríguezChíaClosest assignment constraints in discrete location problems European Journal of Operational Research, 219 (1) (2012), pp. 4958
R.Z. Farahani, M. Hekmatfar, A.B. Arabani, E. NikbakhshHub location problems: A review of models, classification, solution techniques, and applications Computers & Industrial Engineering, 64 (4) (2013), pp. 10961109
J.D. FarleyBreaking al qaeda cells: A mathematical analysis of counterterrorism operations (a guide for risk assessment and decision making) Studies in Conflict & Terrorism, 26 (6) (2003), pp. 399411
A. FrangioniOn a new class of bilevel programming problems and its use for reformulating mixed integer problems European journal of operational research, 82 (3) (1995), pp. 615646
R.A. Gerrard, R.L. ChurchClosest assignment constraints and location models: Properties and structure Location Science, 4 (4) (1996), pp. 251270
N. Ghaffarinasab, R. AtayiAn implicit enumeration algorithm for the hub interdiction median problem with fortification European Journal of Operational Research (2017)
N. Ghaffarinasab, A. MotallebzadehHub interdiction problem variants: Models and metaheuristic solution algorithms European Journal of Operational Research (2017)
A. Gutfraind, A. Hagberg, F. PanOptimal interdiction of unreactive markovian evaders Integration of ai and or techniques in constraint programming for combinatorial optimization problems, Springer Berlin Heidelberg (2009), pp. 102116
H.W. Hamacher, M. Labbé, S. Nickel, T. SonnebornAdapting polyhedral properties from facility to hub location problems Discrete Applied Mathematics, 145 (1) (2004), pp. 104116
E. Israeli, R.K. WoodShortestpath network interdiction Networks, 40 (2) (2002), pp. 97111
S. Jayaswal, N. VidyarthiCapacitated Multiple Allocation Hub Location with Service Level Constraints for Multiple Consignment Classes Technical Report, Indian Institute of Management Ahmedabad, Research and Publication Department(2013)
T.L. LeiIdentifying critical facilities in hubandspoke networks: A hub interdiction median problem Geographical Analysis, 45 (2) (2013), pp. 105122
T.G. LewisCritical Infrastructure Protection in Homeland Security: Defending a Networked Nation WileyInterscience (2006)
F. Liberatore, M.P. Scaparra, M.S. DaskinAnalysis of facility protection strategies against an uncertain number of attacks: the stochastic rinterdiction median problem with fortification Computers & Operations Research, 38 (1) (2011), pp. 357366
F. Liberatore, M.P. Scaparra, M.S. DaskinHedging against disruptions with ripple effects in location analysis Omega, 40 (1) (2012), pp. 2130
C. Lim, J.C. SmithAlgorithms for discrete and continuous multicommodity flow network interdiction problems IIE Transactions, 39 (1) (2007), pp. 1526
C. Losada, M.P. Scaparra, R.L. ChurchOn a bilevel formulation to protect uncapacitated pmedian systems with facility recovery time and frequent disruptions Electronic Notes in Discrete Mathematics, 36 (2010), pp. 591598
C. Losada, M.P. Scaparra, R.L. Church, M.S. DaskinThe stochastic interdiction median problem with disruption intensity levels Annals of Operations Research, 201 (1) (2012), pp. 345365
A.W. McMasters, T.M. MustinOptimal interdiction of a supply network Naval Research Logistics Quarterly, 17 (3) (1970), pp. 261268
D.P. Morton, F. Pan, K.J. SaegerModels for nuclear smuggling interdiction IIE Transactions, 39 (1) (2007), pp. 314
M. O’KellyNetwork hub structure and resilience Networks and Spatial Economics, 15 (2015), pp. 235251
M.E. O’KellyThe location of interacting hub facilities Transportation science, 20 (2) (1986), pp. 92106
M.E. O’Kelly, D. BryanHub location with flow economies of scale Transportation Research Part B: Methodological, 32 (8) (1998), pp. 605616
F. Pan, D.P. MortonMinimizing a stochastic maximumreliability path. Networks, 52 (3) (2008), pp. 111119
F. Parvaresh, S. Hashemi Golpayegany, S.Moattar Husseini, B. KarimiSolving the phub median problem under intentional disruptions using simulated annealing Networks and Spatial Economics, 13 (4) (2013), pp. 445470
F. Parvaresh, S.M. Husseini, S.H. Golpayegany, B. KarimiHub network design problem in the presence of disruptions Journal of Intelligent Manufacturing, 25 (4) (2014), pp. 755774
M. SavelsberghPreprocessing and probing techniques for mixed integer programming problems ORSA Journal on Computing, 6 (4) (1994), pp. 445454
M.P. Scaparra, R. ChurchProtecting supply systems to mitigate potential disaster a model to fortify capacitated facilities International Regional Science Review, 35 (2) (2012), pp. 188210
M.P. Scaparra, R.L. ChurchA bilevel mixedinteger program for critical infrastructure protection planning Computers & Operations Research, 35 (6) (2008), pp. 19051923
M.P. Scaparra, R.L. ChurchAn exact solution approach for the interdiction median problem with fortification European Journal of Operational Research, 189 (1) (2008), pp. 7692
A. Sinha, P. Malo, K. DebA review on bilevel optimization: From classical to evolutionary approaches and applications IEEE Transactions on Evolutionary Computation (Forthcoming), pp. 120
D. SkorinKapov, J. SkorinKapov, M. O’KellyTight linear programming relaxations of uncapacitated phub median problems European Journal of Operational Research, 94 (3) (1996), pp. 582593
J.C. Smith, C. Lim, F. SudarghoSurvivable network design under optimal and heuristic interdiction scenarios Journal of Global Optimization, 38 (2) (2007), pp. 181199
B.D. Song, J.R. Morrison, Y.D. KoEfficient location and allocation strategies for undesirable facilities considering their fundamental properties Computers & Industrial Engineering, 65 (3) (2013), pp. 475484
M. Tanash, I. Contreras, N. VidyarthiAn exact algorithm for the modular hub location problem with single assignments Computers and Operations Research, 85 (2017), pp. 3244
A.K. Vatsa, S. JayaswalA new formulation and benders decomposition for the multiperiod maximal covering facility location problem with server uncertainty European Journal of Operational Research, 251 (2) (2016), pp. 404418
J. Wagner, L. FalksonThe optimal nodal location of public facilities with pricesensitive demand Geographical Analysis, 7 (1) (1975), pp. 6983
A. Washburn, K. WoodTwoperson zerosum games for network interdiction Operations research, 43 (2) (1995), pp. 243251
R.K. WoodDeterministic network interdiction Mathematical and Computer Modelling, 17 (2) (1993), pp. 118
Repository Staff Only: item control page