Network Design Problems (NDPs) can model many real-life problems in a wide range of domains from transportation, supply chain management and logistics, through to the design of telecommunication networks and airline routes. NDPs are generally tackled through employing sophisticated exact methods and (meta-)heuristics. Exact methods mainly include mixed integer programming, column generation, and branch and bound techniques. Metaheuristics, as the second strategy of solving NDPs, can comprise any construction methods, local searches (point-based), evolutionary (population-based) techniques as well as their hybrids. In this abstract, we discuss the challenges and potentials of designing an effective hybrid metaheuristic for solving NDPs by considering the Steiner tree problem as a representative for NDPs...