A Resilient Variant of the Ring Star Problem

ABSTRACT The survivable variant of the Ring Star Problem aims at building a network such that when a hub fails, the Ring Star structure is preserved thanks to backup arcs and edges. In this article, we propose a resilient variant of the Ring Star Problem named 1‐R‐RSP in which the failure of a node in a given subset of so‐called uncertain nodes triggers two corrective operations to repair a ring star structure. The first operation repairs the ring, and the second operation reconnects the star. For a given real positive input parameter , which represents the total duration of breakdowns during the considered time horizon, the objective is to minimize the classical costs of the Ring Star Problem plus the costs incurred by the corrective operations when the hub associated with the largest fixing cost fails during units of time. We model this problem as an integer linear program (ILP), which is also addressed with a Branch‐and‐bins‐cut algorithm. We then perform a sensitivity analysis to help the decision maker understand the impact of the parameter .