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. 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.
    2. 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).
    3. 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.
    4. 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.
    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. Zachary Steever & Chase Murray & Junsong Yuan & Mark Karwan & Marco Lübbecke, 2022. "An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1849-1870, July.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Sarid, A. & Tzur, M., 2018. "The multi-scale generation and transmission expansion model," Energy, Elsevier, vol. 148(C), pages 977-991.
    9. 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.
    10. 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.
    11. Yulong Chen & Zhizhu Lai & Zheng Wang & Dongyang Yang & Leying Wu, 2021. "Optimizing locations of waste transfer stations in rural areas," PLOS ONE, Public Library of Science, vol. 16(5), pages 1-23, May.
    12. Christopher Hojny & Tristan Gally & Oliver Habeck & Hendrik Lüthen & Frederic Matter & Marc E. Pfetsch & Andreas Schmitt, 2020. "Knapsack polytopes: a survey," Annals of Operations Research, Springer, vol. 292(1), pages 469-517, September.
    13. Jiu, Song & Wang, Dan & Ma, Zujun, 2024. "Benders decomposition for robust distribution network design and operations in online retailing," European Journal of Operational Research, Elsevier, vol. 315(3), pages 1069-1082.
    14. Sönke Behrends & Anita Schöbel, 2020. "Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares," Journal of Optimization Theory and Applications, Springer, vol. 186(3), pages 911-935, September.
    15. Alexander Melnik & Kirill Ermolaev, 2020. "Strategy Context of Decision Making for Improved Energy Efficiency in Industrial Energy Systems," Energies, MDPI, vol. 13(7), pages 1-28, March.
    16. Ivan Contreras & Elena Fernández, 2014. "Hub Location as the Minimization of a Supermodular Set Function," Operations Research, INFORMS, vol. 62(3), pages 557-570, June.
    17. Amir Ahmadi-Javid & Nasrin Ramshe, 2019. "Designing flexible loop-based material handling AGV paths with cell-adjacency priorities: an efficient cutting-plane algorithm," 4OR, Springer, vol. 17(4), pages 373-400, December.
    18. Hadas, Yuval & Laor, Amir, 2013. "Network design model with evacuation constraints," Transportation Research Part A: Policy and Practice, Elsevier, vol. 47(C), pages 1-9.
    19. Manur, Ashray & Venkataramanan, Giri & Sehloff, David, 2018. "Simple electric utility platform: A hardware/software solution for operating emergent microgrids," Applied Energy, Elsevier, vol. 210(C), pages 748-763.
    20. Patrick Manser & Tom Haering & Tim Hillel & Janody Pougala & Rico Krueger & Michel Bierlaire, 2024. "Estimating flexibility preferences to resolve temporal scheduling conflicts in activity-based modelling," Transportation, Springer, vol. 51(2), pages 501-528, April.

    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.