Exact algorithms for bi-objective ring tree problems with reliability measures

We introduce bi-objective models for ring tree network design with a focus on network reliability within telecommunication applications. Our approaches generalize the capacitated ring tree problem (CRTP) which asks for a partially reliable topology that connects customers with different security requirements to a depot node by combined ring and tree graphs. While the CRTP aims at optimizing the edge installation costs, we propose four alternative, reliability-oriented objective functions. We study the case of service interruptions due to single-edge failures, and consider the overall number of tree customers and tree edges, the maximal number of subtree customers, and the maximal number of tree hops from rings as additional measures. To model the corresponding novel bi-objective problems, we develop mathematical multi-commodity flow formulations and identify relationships between the new objectives. For identifying the Pareto fronts, we apply an ϵ-constraint method based on integer programming. The computational efficiency is increased by employing local search heuristics in order to tighten upper bounds and by valid inequalities to strengthen lower bounds in the subproblems. In a computational study we report results, illustrate solution network topologies and extensively analyze the algorithm performance for instances from the literature.