Abstract We study the r -hub interdiction problem under the case of possible congestion. Hub interdiction problems are modeled as attacker-defender problems to identify a set of r critical hubs from a set of p hubs, which when attacked, causes maximum damage to network restoration activities of the defender. In this work we consider that in addition to the routing cost, the defender also aims to minimize the congestion cost. Incorporating the congestion cost in the problem introduces non-linearity in the objective function of the interdiction problem, which makes the problem challenging to solve. To address this, we propose two alternate exact solution approaches. The first approach is an inner-approximation-based approach (IBA), which overestimates the convex non-linear objective function and provides an upper bound. A lower bound is obtained from solving the lower-level problem exactly corresponding to the upper bound solution. The upper bound is tightened using improved approximation with new points generated in successive iterations. In the second approach (referred to as SBA), the problem is reformulated as a second-order conic program, which can be solved using an off-the-shelf solver. From our computational experiments on benchmark datasets (CAB and AP), we demonstrate the efficacy of both the proposed methods. However, IBA consistently outperforms SBA by a significant margin.

    Highlights Studies a new hub interdiction problem that accounts for hub congestion. Models the problem as a bi-level mixed integer program. Models congestion as a queuing system and power-law based function. Proposes two alternate exact solution approaches. The better of the two approaches solves instances up to 50 nodes within a few hours.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    The capacitated r -hub interdiction problem with congestion: Models and solution approaches


    Contributors:


    Publication date :

    2024-02-25




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Drug Interdiction Effectiveness

    D. E. Babcock | NTIS | 1991


    Initial Solution Constructors for Capacitated Green Vehicle Routing Problem

    Kozák, Viktor / Woller, David / Vávra, Václav et al. | British Library Conference Proceedings | 2021




    Errant vehicle interdiction device

    HICKLING MICHAEL | European Patent Office | 2017

    Free access