IDEAS home Printed from https://ideas.repec.org/a/spr/cejnor/v18y2010i3p269-291.html
   My bibliography  Save this article

The budget constrained r-interdiction median problem with capacity expansion

Author

Listed:
  • Deniz Aksen

    ()

  • Nuray Piyade

    ()

  • Necati Aras

    ()

Abstract

In this article, we elaborate on a budget constrained extension of the r-interdiction median problem with fortification (RIMF). The objective in the RIMF is to find the optimal allocation of protection resources to a given service system consisting of p facilities so that the disruptive effects of r possible attacks to the system are minimized. The defender of the system needs to fortify q facilities of the present system to offset the worst-case loss of r non-fortified facilities due to an interdiction in which the attacker’s objective is to cause the maximum possible disruption in the service level of the system. The defender-attacker relationship fits a bilevel integer programming (BIP) formulation where the defender and attacker take on the respective roles of the leader and the follower. We adopt this BIP formulation and augment it with a budget constraint instead of a predetermined number of facilities to be fortified. In addition, we also assume that each facility has a flexible service capacity, which can be expanded at a unit cost to accommodate the demand of customers who were serviced by some other interdicted facility before the attack. First, we provide a discrete optimization model for this new facility protection planning scenario with a novel set of closest assignment constraints. Then, to tackle this BIP problem we use an implicit enumeration algorithm performed on a binary tree. For each node representing a different fortification scheme, the attacker’s problem is solved to optimality using Cplex 11. We report computational results obtained on a test bed of 96 randomly generated instances. The article concludes with suggestions for future research. Copyright Springer-Verlag 2010

Suggested Citation

  • Deniz Aksen & Nuray Piyade & Necati Aras, 2010. "The budget constrained r-interdiction median problem with capacity expansion," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 18(3), pages 269-291, September.
  • Handle: RePEc:spr:cejnor:v:18:y:2010:i:3:p:269-291
    DOI: 10.1007/s10100-009-0110-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10100-009-0110-6
    Download Restriction: Access to full text is restricted to subscribers.

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Scaparra, Maria P. & Church, Richard L., 2008. "An exact solution approach for the interdiction median problem with fortification," European Journal of Operational Research, Elsevier, vol. 189(1), pages 76-92, August.
    2. Aras, Necati & Aksen, Deniz, 2008. "Locating collection centers for distance- and incentive-dependent returns," International Journal of Production Economics, Elsevier, vol. 111(2), pages 316-333, February.
    3. Teixeira, Joao C. & Antunes, Antonio P., 2008. "A hierarchical location model for public facility planning," European Journal of Operational Research, Elsevier, vol. 185(1), pages 92-104, February.
    4. Wen, U. P. & Huang, A. D., 1996. "A simple Tabu Search method to solve the mixed-integer linear bilevel programming problem," European Journal of Operational Research, Elsevier, vol. 88(3), pages 563-571, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sachuer Bao & Chi Zhang & Min Ouyang & Lixin Miao, 2019. "An integrated tri-level model for enhancing the resilience of facilities against intentional attacks," Annals of Operations Research, Springer, vol. 283(1), pages 87-117, December.
    2. Nader Azad & Elkafi Hassini, 2019. "A Benders Decomposition Method for Designing Reliable Supply Chain Networks Accounting for Multimitigation Strategies and Demand Losses," Transportation Science, INFORMS, vol. 53(5), pages 1287-1312, September.
    3. Bhuiyan, Tanveer Hossain & Medal, Hugh R. & Harun, Sarah, 2020. "A stochastic programming model with endogenous and exogenous uncertainty for reliable network design under random disruption," European Journal of Operational Research, Elsevier, vol. 285(2), pages 670-694.
    4. Parajuli, Anubhuti & Kuzgunkaya, Onur & Vidyarthi, Navneet, 2021. "The impact of congestion on protection decisions in supply networks under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    5. Parajuli, Anubhuti & Kuzgunkaya, Onur & Vidyarthi, Navneet, 2017. "Responsive contingency planning of capacitated supply networks under disruption risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 102(C), pages 13-37.
    6. Girish Ch. Dey & Mamata Jenamani, 2019. "Optimizing fortification plan of capacitated facilities with maximum distance limits," OPSEARCH, Springer;Operational Research Society of India, vol. 56(1), pages 151-173, March.
    7. Michael Stiglmayr & José Figueira & Kathrin Klamroth, 2014. "On the multicriteria allocation problem," Annals of Operations Research, Springer, vol. 222(1), pages 535-549, November.
    8. Sarhadi, Hassan & Tulett, David M. & Verma, Manish, 2017. "An analytical approach to the protection planning of a rail intermodal terminal network," European Journal of Operational Research, Elsevier, vol. 257(2), pages 511-525.
    9. Ghaffarinasab, Nader & Atayi, Reza, 2018. "An implicit enumeration algorithm for the hub interdiction median problem with fortification," European Journal of Operational Research, Elsevier, vol. 267(1), pages 23-39.
    10. Ramamoorthy, Prasanna & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2018. "Multiple allocation hub interdiction and protection problems: Model formulations and solution approaches," European Journal of Operational Research, Elsevier, vol. 270(1), pages 230-245.
    11. Chaya Losada & M. Scaparra & Richard Church & Mark Daskin, 2012. "The stochastic interdiction median problem with disruption intensity levels," Annals of Operations Research, Springer, vol. 201(1), pages 345-365, December.
    12. Ghaffarinasab, Nader & Motallebzadeh, Alireza, 2018. "Hub interdiction problem variants: Models and metaheuristic solution algorithms," European Journal of Operational Research, Elsevier, vol. 267(2), pages 496-512.
    13. Ramamoorthy, Prasanna & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2016. "Hub Interdiction & Hub Protection problems: Model formulations & Exact Solution methods. (Revised)," IIMA Working Papers WP2016-10-01, Indian Institute of Management Ahmedabad, Research and Publication Department.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. O'Hanley, Jesse R. & Church, Richard L., 2011. "Designing robust coverage networks to hedge against worst-case facility losses," European Journal of Operational Research, Elsevier, vol. 209(1), pages 23-36, February.
    2. Cao, Dong & Chen, Mingyuan, 2006. "Capacitated plant selection in a decentralized manufacturing environment: A bilevel optimization approach," European Journal of Operational Research, Elsevier, vol. 169(1), pages 97-110, February.
    3. Li, Qingwei & Savachkin, Alex, 2013. "A heuristic approach to the design of fortified distribution networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 138-148.
    4. Aksen, Deniz & Aras, Necati & Karaarslan, Ayse Gönül, 2009. "Design and analysis of government subsidized collection systems for incentive-dependent returns," International Journal of Production Economics, Elsevier, vol. 119(2), pages 308-327, June.
    5. Pokharel, Shaligram & Liang, Yijiong, 2012. "A model to evaluate acquisition price and quantity of used products for remanufacturing," International Journal of Production Economics, Elsevier, vol. 138(1), pages 170-176.
    6. Wenyuan Wang & Daniel Y. Mo & Yue Wang & Mitchell M. Tseng, 2019. "Assessing the cost structure of component reuse in a product family for remanufacturing," Journal of Intelligent Manufacturing, Springer, vol. 30(2), pages 575-587, February.
    7. Fatih Rahim & Canan Sepil, 2014. "A location-routing problem in glass recycling," Annals of Operations Research, Springer, vol. 223(1), pages 329-353, December.
    8. Lukac, Zrinka & Soric, Kristina & Rosenzweig, Visnja Vojvodic, 2008. "Production planning problem with sequence dependent setups as a bilevel programming problem," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1504-1512, June.
    9. S A Gabriel & Y Shim & A J Conejo & S de la Torre & R García-Bertrand, 2010. "A Benders decomposition method for discretely-constrained mathematical programs with equilibrium constraints," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(9), pages 1404-1419, September.
    10. Bagheri Hosseini, Mozhde & Dehghanian, Farzad & Salari, Majid, 2019. "Selective capacitated location-routing problem with incentive-dependent returns in designing used products collection network," European Journal of Operational Research, Elsevier, vol. 272(2), pages 655-673.
    11. Kuo, R.J. & Lee, Y.H. & Zulvia, Ferani E. & Tien, F.C., 2015. "Solving bi-level linear programming problem through hybrid of immune genetic algorithm and particle swarm optimization algorithm," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 1013-1026.
    12. Honora Smith & Daniel Cakebread & Maria Battarra & Ben Shelbourne & Naseem Cassim & Lindi Coetzee, 2017. "Location of a hierarchy of HIV/AIDS test laboratories in an inbound hub network: case study in South Africa," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(9), pages 1068-1081, September.
    13. Trung Hieu Tran & Jesse R. O’Hanley & M. Paola Scaparra, 2017. "Reliable Hub Network Design: Formulation and Solution Techniques," Transportation Science, INFORMS, vol. 51(1), pages 358-375, February.
    14. Mohsen Zamani & Mahdi Abolghasemi & Seyed Mohammad Seyed Hosseini & Mir Saman Pishvaee, 2019. "Considering pricing and uncertainty in designing a reverse logistics network," Papers 1909.11633, arXiv.org.
    15. Sarhadi, Hassan & Tulett, David M. & Verma, Manish, 2017. "An analytical approach to the protection planning of a rail intermodal terminal network," European Journal of Operational Research, Elsevier, vol. 257(2), pages 511-525.
    16. Eskandarpour, Majid & Zegordi, Seyed Hessameddin & Nikbakhsh, Ehsan, 2013. "A parallel variable neighborhood search for the multi-objective sustainable post-sales network design problem," International Journal of Production Economics, Elsevier, vol. 145(1), pages 117-131.
    17. Jeihoonian, Mohammad & Kazemi Zanjani, Masoumeh & Gendreau, Michel, 2017. "Closed-loop supply chain network design under uncertain quality status: Case of durable products," International Journal of Production Economics, Elsevier, vol. 183(PB), pages 470-486.
    18. Bhuiyan, Tanveer Hossain & Medal, Hugh R. & Harun, Sarah, 2020. "A stochastic programming model with endogenous and exogenous uncertainty for reliable network design under random disruption," European Journal of Operational Research, Elsevier, vol. 285(2), pages 670-694.
    19. Widener, Michael J. & Horner, Mark W., 2011. "A hierarchical approach to modeling hurricane disaster relief goods distribution," Journal of Transport Geography, Elsevier, vol. 19(4), pages 821-828.
    20. Guerriero, Francesca & Miglionico, Giovanna & Olivito, Filomena, 2016. "Location and reorganization problems: The Calabrian health care system case," European Journal of Operational Research, Elsevier, vol. 250(3), pages 939-954.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:cejnor:v:18:y:2010:i:3:p:269-291. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla) or (Springer Nature Abstracting and Indexing). General contact details of provider: http://www.springer.com .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.