The Steiner tree problem with hop constraints

The Steiner tree problem in graphs is to determine a minimum cost subgraph of a given graph spanning a set of specified vertices. In certain telecommunication networks, additional constraints such as, e.g., reliability constraints, have to be observed. Assume that a certain reliability is associated with each arc of the network, measuring the probability that the respective arc is operational. In case there has to be a guarantee that each message sent from a root vertex to a specified vertex reaches its destination with a certain probability, so-called hop constraints may be used to model the respective generalization. In this paper, we discuss the Steiner tree problem with hop constraints, i.e., a generalization of Steiner's problem in graphs where the number of arcs (hops) between a root node and any of the specified vertices is limited. A mathematical programming formulation is provided and extended to handle problem instances of moderate size. As the Steiner tree problem with hop constraints is NP-hard, a simple heuristic is developed and an exchange procedure based on the tabu search metastrategy is applied to improve given solutions. Numerical results are discussed for a number of problem instances derived from, e.g., well-known benchmark instances of Steiner's problem in graphs.