Given a graph G = (V, E), the Tree Star problem aims to design a network composed of hubs and terminals. The backbone is a spanning tree over the hubs using only edges from E, while terminals form the tributary network and each is connected to a hub through an arc in A. The objective is to build this structure at minimum cost according to functions c for edges and d for arcs.

We address a survivable variant in which a subset of vertices may fail. When such a vertex goes down, connectivity must be preserved in the backbone and the tributary network to ensure service continuity. To solve this problem, we develop both an Integer Linear Programming formulation and a Greedy Randomized Adaptive Search Procedure, with the heuristic being the focus of the presentation.

The GRASP constructs initial solutions through a randomized backbone generation phase that ensures fault tolerance using pairs of internally disjoint paths. A variable neighborhood local search then improves these solutions via four operators that insert or remove hubs, adjust backbone connections, or reoptimize selected subgraphs. Correctness relies on the identification of edges that can be safely split and on decomposition methods that pinpoint modifiable components.

The heuristic is benchmarked against the ILP to evaluate tradeoffs between computation time and solution quality.