Abstract
We introduce two specific design problems of optical fiber cable networks that differ by a practical maintenance constraint. An integer programming based method including valid inequalities is introduced for the unconstrained problem. We propose two exact solution methods to tackle the constrained problem: the first one is based on mixed integer programming including valid inequalities while the second one is built on dynamic programming. We then provide a fully polynomial time approximation scheme for the constrained problem. The theoretical complexities of both problems in several cases are proven and compared. Numerical results assess the efficiency of both methods in different contexts including real-life instances, and evaluate the effect of the maintenance constraint on the solution quality.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Angilella, V., Chardy, M., Ben-Ameur, W.: Cables network design optimisation for the fiber to the home. In: Design of Reliable Communication Networks (2016)
Angilella, V., Chardy, M., Ben-Ameur, W.: Design of fiber cable tree networks for the fiber to the home. In: International Networks Optimisation Conference, Lisboa, Portugal (2017)
Angilella, V., Chardy, M., Ben-Ameur, W.: Fiber cable network design with operations administration & maintenance constraints. In: International Conference on Operations Research and Enterprise Systems, Funchal, Madeira, Portugal (2018)
Bley, A., Ljubic, I., Maurer, O.: Lagrangian decompositions for the two-level FTTx network design problem. Eur. J. Comput. Optim. 1(3), 221–252 (2013)
Chardy, M., Costa, M.C., Faye, A., Trampont, M.: Optimising splitter and fiber location in a multilevel optical FTTH network. Eur. J. Oper. Res. 222(3), 430–440 (2013)
Contreras, I., Fernandez, E.: General network design: a unified view of combined location and network design problems. Eur. J. Oper. Res. 219(3), 680–697 (2012)
FTTH Council Europe: FTTH Handbook, 7th edn. Wettelijk Depot (2016)
Gollowitzer, S., Gouveia, L., Ljubic, I.: Enhanced formulations and branch and cut for the two level network design problem with transition facilities. Eur. J. Oper. Res. 2, 211–222 (2013)
Grötschel, M., Raack, C., Werner, A.: Towards optimising the deployment of optical access networks. Eur. J. Comput. Optim. 2(1–2), 17–53 (2013)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Magazine, M., Oguz, O.: A fully polynomial approximation algorithm for the 0–1 knapsack problem. Eur. J. Oper. Res. 8(3), 270–273 (1981)
Mateus, G.R., Luna, H.P., Sirihal, A.B.: Heuristics for distribution network design in telecommunication. J. Heuristics 6, 131–148 (2000)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Angilella, V., Chardy, M., Ben-Ameur, W. (2019). Operations Administration and Maintenance Constraints in Fiber Cables Network Design. In: Parlier, G., Liberatore, F., Demange, M. (eds) Operations Research and Enterprise Systems. ICORES 2018. Communications in Computer and Information Science, vol 966. Springer, Cham. https://doi.org/10.1007/978-3-030-16035-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-16035-7_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-16034-0
Online ISBN: 978-3-030-16035-7
eBook Packages: Computer ScienceComputer Science (R0)