Heuristic methods for the rectilinear Steiner arborescence problem

In the rectilinear Steiner arborescence problem a minimum cost arborescence spanning a given subset of vertices has to be found under the condition that the underlying metric is rectilinear. This problem has potential applicability in the planning and design processes of, for example, irrigation and drainage networks. Some heuristic algorithms are proposed and compared even for large scale data. In addition, a problem variant is discussed that is more appropriate for real world applications, i.e., when some forbidden regions or obstacles have to be observed.