  We consider a recently introduced class of network construction problems
where edges of a transportation network need to be constructed by a server
(construction crew). The server has a constant construction speed which is much
lower than its travel speed, so relocation times are negligible with respect to
construction times. It is required to find a construction schedule that
minimizes a non-decreasing function of the times when various connections of
interest become operational. Most problems of this class are strongly NP-hard
on general networks, but are often tree-efficient, that is, polynomially
solvable on trees. We develop a generic local search heuristic approach and two
metaheuristics (Iterated Local Search and Tabu Search) for solving
tree-efficient network construction problems on general networks, and explore
them computationally. Results of computational experiments indicate that the
methods have excellent performance.
