We present topology design methodology for broadband (FTTx) access networks. The calculations
are based on real geographic data (digital maps) and infrastructural information of
the targeted area, using detailed and realistic cost models in order to provide results
of practical interest. The developed heuristics offer low time consumption and nearly
optimal solutions for the highly complex problem of minimal cost network deployment,
due to the properly chosen and customized heuristic algorithms for the various network
technologies. We review the specific properties of the FTTx network technologies,
present a formal representation of the problem including a detailed cost function
and network model, discuss complexity issues. The various solution techniques are
presented along with case studies of real-life scenarios, in order to show potential
of the methodology. The developed heuristic algorithms offer approximation of the
optimum within 10-15%, while time consumption remains in the range of a few minutes
even for large-scale scenarios with 10.000s of customers. Beyond topology design,
the results provided by these methods are useful for preliminary CAPEX estimation
and techno-economic comparison.
