Generalized local branching heuristics and the capacitated ring tree problem

Using this concept we develop an efficient algorithm for the capacitated ring tree problem (CRTP), a recent network design model for partially reliable capacitated networks that combines cycle and tree structures. Our implementation operates on top of an efficient branch and cut algorithm for the CRTP. The sets of refinement variables are deduced from single-ball network node clusters. We provide computational results and an extensive analysis of the algorithm for a set of literature instances. We show that the approach is capable of improving existing best results for the CRTP and outperforms the pure refinement or local branching approaches.