Multi-criteria optimization models for the deployment of FTTx networks, development and implementation of algorithmic approaches
Final Report Abstract
The planning of high-speed, fiber-based access networks is a highly complex task, where different contradicting objectives have to be taken into account, such as minimizing deployment cost and/or maintenance cost, and maximizing coverage, i.e. the number of potential customers reached. The main objectives of the project were to provide new optimization models for the occurring problems taking these multi-criteria aspects into account, to study various methods for solving these models exactly or approximately, and to determine which models and methods are suitable to be applied in large, realistic scenarios. A basic model was developed, which we termed "2-Architecture Connected Facility Location". It can be applied in a single-objective fashion, with given minimum coverage rates for two "architectures", to compute a mixed-architecture network with optimal cost. In an applied scenario, the two architectures would most likely correspond to fiber-based (FTTH, fiber-to-the-home) and partly copper-based (FTTC, fiber-to-the-curb) technology, but varying applications are conceivable. For solving this model, different formulations using cuts as well as multicommodity flows were examined, which yield relaxed models of different strength. Resulting solution methods were compared computationally using realistic problem scenarios. The basic model can easily be generalized to take more than two architectures into account, resulting in multi-objective models. Additionally, the models can be augmented to incorporate other practically relevant side-constraints. Use-cases addressed include the following, where in each case both cost-optimal as well as combined cost/coverage-optimal planning is possible: - design of a mixed FTTH/FTTC network; - design of an FTTC network with different service levels, aiming at prescribing certain data transmission speeds for a fraction of potential customers; - reducing customer segmentation, to avoid that the geographical area is clustered into small patches served with different technologies; - design of an FTTH/FTTC network incorporating wireless technology. A number of algorithms were devised within the project to efficiently find solutions to the multi-objective models. For the bi-objective cases, this includes in particular an "adaptive-search" algorithm as well as adaptations of the well-known "two-phase" method. For three and more objectives, two algorithms were proposed and tested computationally, a 3-objective variant of the well-known "epsilon-constraint" method and a recursive algorithm similar to the "full m-split" method. Both algorithms can be generalized to more than 3 objectives; furthermore, they can be viewed as special cases of a general framework, which allows to combine different mathematical models for the problem at hand with different solution methods working on the appropriate objective space. Accordingly, the two algorithms were implemented as exemplary plug-ins to the implementation of the framework. Finally, further problem scenarios were identified that naturally lead to multi-objective optimization problems: time-expanded planning of access networks, as well as the inclusion of operational issues, such as maintenance cost, hardware utilization, or energy consumption.
Publications
-
A new exact method and matheuristics for bi-objective 0/1 ILPs: Application to FTTx-network design, 2015
M. Leitner, I. Ljubić, M. Sinnl, and A. Werner
-
On the two-architecture connected facility location problem. Electronic Notes in Discrete Mathematics, 41:359–366, May 2013
M. Leitner, I. Ljubić, M. Sinnl, and A. Werner
-
Towards optimizing the deployment of optical access networks. EURO Journal on Computational Optimization, 2:17–53, 2014
M. Grötschel, C. Raack, and A. Werner
-
A two-phase method for the biobjective k-architecture connected facility location problem and hypervolume computation. Technical Report 15- 08, ZIB
S. Uslu and A. Werner
-
Two algorithms for solving 3- objective k-ArchConFL and IPs in general. Technical Report 15-48, ZIB
M. Leitner, I. Ljubić, M. Sinnl, and A. Werner
