Multi-Criteria Optimization of FTTx Networks

Modern fixed telecommunication networks are based on fiber-optic technology. In the context of access networks, planners speak of FTTx (fiber-to-the-x) networks, where "x" indicates the device/location/customer to which the fibers are laid out. The planning of an FTTx network is a highly complex task for which mathematical optimization offers powerful modeling and solution tools. There has been no lack of research in this area in the past; the existing models, however, lack a satisfactory treatment of several important issues arising in practice. Many of these, we believe, can be appropriately addressed by employing multi-objective optimization. This conviction is the guideline of our project. Our first goal is to develop, based on existing models for FTTx network planning, suitable multi- objective optimization models for the network design problems arising in this context. Finding "efficient`` solutions of multi-objective optimization problems is, though, much more difficult than the treatment of the single-objective case. Hence, the second goal is to design appropriate methods for the proposed models that allow to solve realistic scenarios to "multi-objective optimality``. Phrased in more technical terms: We will devise exact methods and at the same time develop heuristics that approximate the Pareto set and provide, if possible, quality guarantees.

The main topics of this project were bi-objective combinatorial optimization problems arising in the design of last-mile telecommunication networks (FTTx networks) that are based on fiber- optic technology. The newest technological and sociological developments require a significant upgrade of existing telecommunication networks. Thereby, telecommunication providers are interested in improving the quality of broadband connections in the local access areas between the central office (connection to the backbone) and end-subscribers (ranging from large businesses to single households) while keeping their costs as small as possible. Since planning such networks is a highly complex task, powerful modeling and solution tools from mathematical optimization need to be used. Despite a large amount of existing research in this area existing models and algorithms fail to satisfactorily treat several important issues arising in practice. This particularly concerns trade-offs between overall costs for an operator and quality-of-service (e.g., available bandwidth) for the customers. These issues can be appropriately addressed by employing bi- or multi-objective optimization. This conviction was the starting point and the guideline of this project. We first proposed generalizations of the most relevant single-objective problem variants known from the literature to the bi-objective case. New models and algorithmic solution methods for these problems have been developed. These algorithms enable the computation of a set of solutions that account for the trade-off between costs and quality-of-service and which can be presented to a decision maker as alternatives under which he or she may choose a most preferred solution. Besides proposing new, exact, methods for solving bi-objective combinatorial optimization problems, we developed heuristics that allow to compute a set of high-quality solutions much faster. Finally, we also performed computational studies in which the practical performance of several alternatives for solving problems from the considered classes have been evaluated and compared in detail. During the course of these developments several research gaps regarding the study of theoretical properties of the considered problems as well as concerning further quality-of-service measures (e.g., packet delay) have been identified and addressed in subsequent research within the project. Results of the research have been successfully presented at various high-level scientific conferences in the area of network optimization and several articles have been published in top- level journals. Furthermore, fruitful cooperations with researchers from Belgium, Canada, Germany, Italy, Portugal, and Spain have been established and / or deepened.