IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v269y2018i3p1086-1106.html
   My bibliography  Save this article

Fiber cable network design in tree networks

Author

Listed:
  • Angilella, Vincent
  • Chardy, Matthieu
  • Ben-Ameur, Walid

Abstract

This work focuses on a fiber cable network design problem in the context of Fiber To The Home (FTTH) where separation techniques such as splicing and tapping are considered. Assuming the civil engineering structure is a tree, the problem is proven to be NP-hard and even hard to approximate. Two exact integer programming models taking into account some operator’s engineering rules are introduced. Enhancements are provided for both models leading to significant computing time reduction. Computational experiments are performed on real-life instances with real costs including both manpower and material costs incurred by the network operator.

Suggested Citation

  • Angilella, Vincent & Chardy, Matthieu & Ben-Ameur, Walid, 2018. "Fiber cable network design in tree networks," European Journal of Operational Research, Elsevier, vol. 269(3), pages 1086-1106.
    • Handle: RePEc:eee:ejores:v:269:y:2018:i:3:p:1086-1106
    DOI: 10.1016/j.ejor.2018.02.034
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171830167X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.02.034?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Tahon, Mathieu & Van Ooteghem, Jan & Casier, Koen & Verbrugge, Sofie & Colle, Didier & Pickavet, Mario & Demeester, Piet, 2014. "Improving the FTTH business case–A joint telco-utility network rollout model," Telecommunications Policy, Elsevier, vol. 38(5), pages 426-437.
    2. Gollowitzer, Stefan & Gouveia, Luis & Ljubić, Ivana, 2013. "Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities," European Journal of Operational Research, Elsevier, vol. 225(2), pages 211-222.
    3. Contreras, Ivan & Fernández, Elena, 2012. "General network design: A unified view of combined location and network design problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 680-697.
    4. MARCHAND, Hugues & MARTIN, Alexander & WEISMANTEL, Robert & WOLSEY, Laurence, 2002. "Cutting planes in integer and mixed integer programming," LIDAM Reprints CORE 1567, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ortiz-Astorquiza, Camilo & Contreras, Ivan & Laporte, Gilbert, 2018. "Multi-level facility location problems," European Journal of Operational Research, Elsevier, vol. 267(3), pages 791-805.
    2. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    3. Ivan Contreras & Moayad Tanash & Navneet Vidyarthi, 2017. "Exact and heuristic approaches for the cycle hub location problem," Annals of Operations Research, Springer, vol. 258(2), pages 655-677, November.
    4. Davood Shishebori & Lawrence Snyder & Mohammad Jabalameli, 2014. "A Reliable Budget-Constrained FL/ND Problem with Unreliable Facilities," Networks and Spatial Economics, Springer, vol. 14(3), pages 549-580, December.
    5. Yogesh Kumar Agarwal & Prahalad Venkateshan, 2019. "New Valid Inequalities for the Optimal Communication Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 268-284, April.
    6. Abdolsalam Ghaderi, 2015. "Heuristic Algorithms for Solving an Integrated Dynamic Center Facility Location - Network Design Model," Networks and Spatial Economics, Springer, vol. 15(1), pages 43-69, March.
    7. Camilo Ortiz-Astorquiza & Ivan Contreras & Gilbert Laporte, 2019. "An Exact Algorithm for Multilevel Uncapacitated Facility Location," Transportation Science, INFORMS, vol. 53(4), pages 1085-1106, July.
    8. Rendon Schneir, Juan & Xiong, Yupeng, 2016. "A cost study of fixed broadband access networks for rural areas," Telecommunications Policy, Elsevier, vol. 40(8), pages 755-773.
    9. Lin, Cheng-Chang & Lee, Shwu-Chiou, 2018. "Hub network design problem with profit optimization for time-definite LTL freight transportation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 104-120.
    10. Sarid, A. & Tzur, M., 2018. "The multi-scale generation and transmission expansion model," Energy, Elsevier, vol. 148(C), pages 977-991.
    11. Gerli, Paolo & Van der Wee, Marlies & Verbrugge, Sofie & Whalley, Jason, 2018. "The involvement of utilities in the development of broadband infrastructure: A comparison of EU case studies," Telecommunications Policy, Elsevier, vol. 42(9), pages 726-743.
    12. Martello, Silvano & Pinto Paixão, José M., 2012. "A look at the past and present of optimization – An editorial," European Journal of Operational Research, Elsevier, vol. 219(3), pages 638-640.
    13. Marie Schmidt & Anita Schöbel, 2014. "Location of speed-up subnetworks," Annals of Operations Research, Springer, vol. 223(1), pages 379-401, December.
    14. Pablo A. Miranda-Gonzalez & Javier Maturana-Ross & Carola A. Blazquez & Guillermo Cabrera-Guerrero, 2021. "Exact Formulation and Analysis for the Bi-Objective Insular Traveling Salesman Problem," Mathematics, MDPI, vol. 9(21), pages 1-33, October.
    15. Hewitt, Mike & Crainic, Teodor Gabriel & Nowak, Maciek & Rei, Walter, 2019. "Scheduled service network design with resource acquisition and management under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 324-343.
    16. Kovcs, Andrs & Brown, Kenneth N. & Tarim, S. Armagan, 2009. "An efficient MIP model for the capacitated lot-sizing and scheduling problem with sequence-dependent setups," International Journal of Production Economics, Elsevier, vol. 118(1), pages 282-291, March.
    17. Lluís-Miquel Munguía & Geoffrey Oxberry & Deepak Rajan & Yuji Shinano, 2019. "Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs," Computational Optimization and Applications, Springer, vol. 73(2), pages 575-601, June.
    18. Mariusz Mycek & Mateusz Żotkiewicz, 2019. "On optimal trajectory for the multi-period evolution of FTTx networks," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 71(3), pages 353-376, July.
    19. Lüer-Villagra, Armin & Marianov, Vladimir, 2013. "A competitive hub location and pricing problem," European Journal of Operational Research, Elsevier, vol. 231(3), pages 734-744.
    20. Mohammadi, M. & Dehbari, S. & Vahdani, Behnam, 2014. "Design of a bi-objective reliable healthcare network with finite capacity queue under service covering uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 15-41.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:269:y:2018:i:3:p:1086-1106. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.