A branch-and-cut algorithm for the multiple allocation r-hub interdiction median problem with fortification. (15th November 2018)

• Record Type: Journal Article
• Authors: Quadros, Hugo; Costa Roboredo, Marcos; Alves Pessoa, Artur
• Is Part Of: Expert systems with applications. Volume 110(2018)
• Page Start: 311
• Page End: 322
• Publication Date: 2018-11-15
• Subjects: Bilevel problem -- Hub fortification -- Hub interdiction -- Branch-and-cut; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.05.036
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: New ILP formulation with a polynomial number of variables. The branch-and-cut algorithm was proved to be robust, solving all instances. Computational results overcome the best exact method found in the literature. Several open instances are solved for the first time. Abstract: Hubs are special facilities widely found in distribution systems acting mainly as transshipment and switching points, being used to concentrate and consolidate flows. Every hub is subjected to a disruption of its functionality, called interdiction, that can be caused by many reasons such as natural disasters or even intentional attacks. Interdictions result in an efficiency loss to the system, substantially increasing the total distribution cost. A way to mitigate the impact caused by interdictions is fortifying some hubs, avoiding them to be interdicted. This context naturally leads to the multiple allocation r-hub interdiction median problem with fortification, which consists of identifying q hubs to be fortified in a multiple allocation hub-and-spoke supply network, knowing that r hubs will be interdicted. We assume that the set of hubs chosen to be interdicted is the one that causes the highest increase in the total distribution cost. For this bilevel problem, we propose an integer linear programming formulation with an exponential number of constraints that is solved through a branch-and-cut algorithm. Our results show that our method requires less computational time than the exact algorithm found in the literature, being able to optimally solve several large instances.