The construction of modern telecommunication networks requires an extended period of time, usually in the range of years, and hence has to be planned in multiple periods. During this time, economic prerequisites are subject to changes, a fact that must be taken into account in the planning phase. This introduces an uncertainty aspect for the parameters that determine the input to the mathematical models used for addressing the network design problem. In the project, models and methods were developed to cope with the long-term aspect as well as the resulting uncertainty in the planning problem. For long time horizons, mathematical models tend to get large and are therefore hard to solve by general algorithms. Hence it is important to develop suitable special algorithms to efficiently use these models. In particular, primal methods (which quickly compute possible solutions) and dual methods (which, when possible, ascertain optimality of found solutions) were the focus of our research. For the model developed early in the project, which covers realistic long-term scenarios, a successful dual method was devised, which is based on the well-known Lagrange duality theory. The necessary computations for the algorithm can be carried out quickly, due to a simple characterization of the dual optimum, and this leads to better dual bounds than using the general methods of state-of-the-art solvers. By considering a very special case of the general problem, an extension of the classical Knapsack Problem can be studied. Furthermore, for a generalization of the original model, an efficient primal method was obtained, which is surprisingly simple, but provides already much better solutions than a commercial solver, as test computations suggest. Introducing the uncertainty aspect complicates models even further. This is because the description of those possible solutions to the model that are robust against any uncertain input data (i.e., that are still feasible when the input data changes in a controlled way) requires new restrictions that have to be satisfied by the variables of the model. At the same time, this adds more structure to the problem, which can be exploited when designing primal solution methods. This was done for the multiperiod problem considered in the project, where certain other assumptions were taken, following the expertise of our Polish partners. The resulting algorithm, which makes use of various mathematical techniques such as duality, total unimodularity, randomized rounding, and shortest paths, manages to find much better solutions than the state-of-the-art commercial solver CPLEX; the corresponding paper won the Best Paper Award at the EvoComNet 2014 conference. Test computations were carried out using examples of real-world networks throughout, as provided by the SNDlib, a library of telecommunication networks that is widely used both by practitioners and in academia.