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)
Preview |
Text (application/pdf)
970kBRamamoorthy-2018.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 post-interdiction 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 order-of-magnitude 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: | LocationHub-and-Spoke 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. 346-358D. Aksen, N. ArasA bilevel fixed charge location model for facilities under imminent attack Computers & Operations Research, 39 (7) (2012), pp. 1364-1381
D. Aksen, N. Aras, N. PiyadeA bilevel p-median model for the planning and protection of critical facilities Journal of Heuristics, 19 (2) (2013), pp. 373-398
D. Aksen, N. Piyade, N. ArasThe budget constrained r-interdiction median problem with capacity expansion Central European Journal of Operations Research, 18 (3) (2010), pp. 269-291
R. Albert, H. Jeong, A. BarabasiError and attack tolerance of complex networks Nature, 406 (2002), pp. 378-382
S. Alumur, B.Y. KaraNetwork hub location problems: The state of the art European journal of operational research, 190 (1) (2008), pp. 1-21
Y. An, Y. Zhang, B. ZengThe reliable hub-and-spoke design problem: Models and algorithms Transportation Research Part B: Methodological, 77 (2015), pp. 103-122
N. AssimakopoulosA network interdiction model for hospital infection control Computers in Biology and Medicine, 17 (6) (1987), pp. 413-422
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. 273-300
N. Azizi, S. Chauhan, S. Salhi, N. VidyarthiThe impact of hub failure in hub-and-spoke networks: Mathematical formulations and solution techniques Computers & Operations Research, 65 (2016), pp. 174-188
J. BendersPartitioning procedures for solving mixed integer programming problems Numerische Mathematik, 52 (1962), pp. 238-252
O. Berman, Z. Drezner, A. Tamir, G.O. WesolowskyOptimal location with equitable loads Annals of Operations Research, 167 (1) (2009), pp. 307-325
G. Brown, M. Carlyle, J. Salmern, K. WoodDefending critical infrastructure Interfaces, 36 (6) (2006), pp. 530-544
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. 1047-1064
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. 86-97
J.F. CampbellInteger programming formulations of discrete hub location problems European Journal of Operational Research, 72 (2) (1994), pp. 387-405
J.F. CampbellHub location and the p-hub median problem Operations Research, 44 (6) (1996), pp. 923-935
J.F. Campbell, M.E. O’KellyTwenty-five years of hub location research Transportation Science, 46 (2) (2012), pp. 153-169
P. Cappanera, M.P. ScaparraOptimal allocation of protective resources in shortest-path networks Transportation Science, 45 (1) (2011), pp. 64-80
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. 191-202
R. Church, M.P. ScaparraAnalysis of facility systems reliability when subject to attack or a natural disaster Critical infrastructure, Springer Berlin Heidelberg (2007), pp. 221-241
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. 129-146
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. 491-502
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. 1477-1490
I. Contreras, J.-F. Cordeau, G. LaporteBenders decomposition for large-scale uncapacitated hub location Operations research, 59 (6) (2011), pp. 1477-1490
I. Contreras, J.-F. Cordeau, G. LaporteThe dynamic uncapacitated hub location problem Transportation Science, 45 (1) (2011), pp. 18-32
I. Contreras, E. Fernández, A. MarínThe tree of hubs location problem European Journal of Operational Research, 202 (2) (2010), pp. 390-400
I. Contreras, M. Tanash, N. VidyarthiExact and heuristic approaches for the cycle hub location problem Annals of Operations Research (2016), pp. 1-23
H. Corley, D.Y. ShaMost vital links and nodes in weighted networks Oper. Res. Lett., 1 (4) (1982), pp. 157-160
K.J. Cormican, D.P. Morton, R.K. WoodStochastic network interdiction Operations Research, 46 (2) (1998), pp. 184-197
G. Dobson, U.S. KarmarkarCompetitive location on a network Operations Research, 35 (4) (1987), pp. 565-574
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. 614-631
S. Elhedhli, F.X. HuHub-and-spoke network design with congestion Computers & Operations Research, 32 (6) (2005), pp. 1615-1632
A.T. Ernst, M. KrishnamoorthyEfficient algorithms for the uncapacitated single allocation p-hub median problem Location science, 4 (3) (1996), pp. 139-154
I. Espejo, A. Marín, A.M. Rodríguez-ChíaClosest assignment constraints in discrete location problems European Journal of Operational Research, 219 (1) (2012), pp. 49-58
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. 1096-1109
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. 399-411
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. 615-646
R.A. Gerrard, R.L. ChurchClosest assignment constraints and location models: Properties and structure Location Science, 4 (4) (1996), pp. 251-270
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. 102-116
H.W. Hamacher, M. Labbé, S. Nickel, T. SonnebornAdapting polyhedral properties from facility to hub location problems Discrete Applied Mathematics, 145 (1) (2004), pp. 104-116
E. Israeli, R.K. WoodShortest-path network interdiction Networks, 40 (2) (2002), pp. 97-111
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 hub-and-spoke networks: A hub interdiction median problem Geographical Analysis, 45 (2) (2013), pp. 105-122
T.G. LewisCritical Infrastructure Protection in Homeland Security: Defending a Networked Nation Wiley-Interscience (2006)
F. Liberatore, M.P. Scaparra, M.S. DaskinAnalysis of facility protection strategies against an uncertain number of attacks: the stochastic r-interdiction median problem with fortification Computers & Operations Research, 38 (1) (2011), pp. 357-366
F. Liberatore, M.P. Scaparra, M.S. DaskinHedging against disruptions with ripple effects in location analysis Omega, 40 (1) (2012), pp. 21-30
C. Lim, J.C. SmithAlgorithms for discrete and continuous multicommodity flow network interdiction problems IIE Transactions, 39 (1) (2007), pp. 15-26
C. Losada, M.P. Scaparra, R.L. ChurchOn a bi-level formulation to protect uncapacitated p-median systems with facility recovery time and frequent disruptions Electronic Notes in Discrete Mathematics, 36 (2010), pp. 591-598
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. 345-365
A.W. McMasters, T.M. MustinOptimal interdiction of a supply network Naval Research Logistics Quarterly, 17 (3) (1970), pp. 261-268
D.P. Morton, F. Pan, K.J. SaegerModels for nuclear smuggling interdiction IIE Transactions, 39 (1) (2007), pp. 3-14
M. O’KellyNetwork hub structure and resilience Networks and Spatial Economics, 15 (2015), pp. 235-251
M.E. O’KellyThe location of interacting hub facilities Transportation science, 20 (2) (1986), pp. 92-106
M.E. O’Kelly, D. BryanHub location with flow economies of scale Transportation Research Part B: Methodological, 32 (8) (1998), pp. 605-616
F. Pan, D.P. MortonMinimizing a stochastic maximum-reliability path. Networks, 52 (3) (2008), pp. 111-119
F. Parvaresh, S. Hashemi Golpayegany, S.Moattar Husseini, B. KarimiSolving the p-hub median problem under intentional disruptions using simulated annealing Networks and Spatial Economics, 13 (4) (2013), pp. 445-470
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. 755-774
M. SavelsberghPreprocessing and probing techniques for mixed integer programming problems ORSA Journal on Computing, 6 (4) (1994), pp. 445-454
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. 188-210
M.P. Scaparra, R.L. ChurchA bilevel mixed-integer program for critical infrastructure protection planning Computers & Operations Research, 35 (6) (2008), pp. 1905-1923
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. 76-92
A. Sinha, P. Malo, K. DebA review on bilevel optimization: From classical to evolutionary approaches and applications IEEE Transactions on Evolutionary Computation (Forthcoming), pp. 1-20
D. Skorin-Kapov, J. Skorin-Kapov, M. O’KellyTight linear programming relaxations of uncapacitated p-hub median problems European Journal of Operational Research, 94 (3) (1996), pp. 582-593
J.C. Smith, C. Lim, F. SudarghoSurvivable network design under optimal and heuristic interdiction scenarios Journal of Global Optimization, 38 (2) (2007), pp. 181-199
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. 475-484
M. Tanash, I. Contreras, N. VidyarthiAn exact algorithm for the modular hub location problem with single assignments Computers and Operations Research, 85 (2017), pp. 32-44
A.K. Vatsa, S. JayaswalA new formulation and benders decomposition for the multi-period maximal covering facility location problem with server uncertainty European Journal of Operational Research, 251 (2) (2016), pp. 404-418
J. Wagner, L. FalksonThe optimal nodal location of public facilities with price-sensitive demand Geographical Analysis, 7 (1) (1975), pp. 69-83
A. Washburn, K. WoodTwo-person zero-sum games for network interdiction Operations research, 43 (2) (1995), pp. 243-251
R.K. WoodDeterministic network interdiction Mathematical and Computer Modelling, 17 (2) (1993), pp. 1-18
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics