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

A node rooted flow-based model for the local access network expansion problem

Author

Listed:
  • Corte-Real, Margarida
  • Gouveia, Luís

Abstract

In this paper, we present a new formulation for the local access network expansion problem. Previously, we have shown that this problem can be seen as an extension of the well-known Capacitated Minimum Spanning Tree Problem and have presented and tested two flow-based models. By including additional information on the definition of the variables, we propose a new flow-based model that permits us to use effectively variable eliminations tests as well as coefficient reduction on some of the constraints. We present computational results for instances with up to 500 nodes in order to show the advantages of the new model in comparison with the others.

Suggested Citation

  • Corte-Real, Margarida & Gouveia, Luís, 2010. "A node rooted flow-based model for the local access network expansion problem," European Journal of Operational Research, Elsevier, vol. 204(1), pages 20-34, July.
    • Handle: RePEc:eee:ejores:v:204:y:2010:i:1:p:20-34
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00703-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. T. L. Magnanti & R. T. Wong, 1984. "Network Design and Transportation Planning: Models and Algorithms," Transportation Science, INFORMS, vol. 18(1), pages 1-55, February.
    2. Gendreau, Michel & Potvin, Jean-Yves & Smires, Ali & Soriano, Patrick, 2006. "Multi-period capacity expansion for a local access telecommunications network," European Journal of Operational Research, Elsevier, vol. 172(3), pages 1051-1066, August.
    3. Anantaram Balakrishnan & Thomas L. Magnanti & Richard T. Wong, 1995. "A Decomposition Algorithm for Local Access Telecommunications Network Expansion Planning," Operations Research, INFORMS, vol. 43(1), pages 58-76, February.
    4. Gouveia, Luis & Lopes, Maria Joao, 2000. "Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs," European Journal of Operational Research, Elsevier, vol. 121(2), pages 394-411, March.
    5. Flippo, Olaf E. & Kolen, Antoon W. J. & Koster, Arie M. C. A. & van de Leensel, Robert L. M. J., 2000. "A dynamic programming algorithm for the local access telecommunication network expansion problem," European Journal of Operational Research, Elsevier, vol. 127(1), pages 189-202, November.
    6. Carolyn Jack & Sheng-Roan Kai & Alexander Shulman, 1992. "Design and Implementation of an Interactive Optimization System for Telephone Network Planning," Operations Research, INFORMS, vol. 40(1), pages 14-25, February.
    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. van de Leensel, R.L.J.M. & Flippo, O.E. & Koster, Arie M.C.A. & Kolen, A.W.J., 1996. "A dynamic programming algorithm for the local access network expansion problem," Research Memorandum 027, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    2. Linos F. Frantzeskakis & Hanan Luss, 1999. "The network redesign problem for access telecommunications networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(5), pages 487-506, August.
    3. Gendreau, Michel & Potvin, Jean-Yves & Smires, Ali & Soriano, Patrick, 2006. "Multi-period capacity expansion for a local access telecommunications network," European Journal of Operational Research, Elsevier, vol. 172(3), pages 1051-1066, August.
    4. Martins, Carlos Lúcio & Fonseca, Maria da Conceição & Pato, Margarida Vaz, 2017. "Modeling the Steering of International Roaming Traffic," European Journal of Operational Research, Elsevier, vol. 261(2), pages 735-754.
    5. Yazar, Başak & Arslan, Okan & Karaşan, Oya Ekin & Kara, Bahar Y., 2016. "Fiber optical network design problems: A case for Turkey," Omega, Elsevier, vol. 63(C), pages 23-40.
    6. S Mudchanatongsuk & F Ordóñez & J Liu, 2008. "Robust solutions for network design under transportation cost and demand uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 652-662, May.
    7. Scheibe, Kevin P. & Ragsdale, Cliff T., 2009. "A model for the capacitated, hop-constrained, per-packet wireless mesh network design problem," European Journal of Operational Research, Elsevier, vol. 197(2), pages 773-784, September.
    8. Flippo, Olaf E. & Kolen, Antoon W. J. & Koster, Arie M. C. A. & van de Leensel, Robert L. M. J., 2000. "A dynamic programming algorithm for the local access telecommunication network expansion problem," European Journal of Operational Research, Elsevier, vol. 127(1), pages 189-202, November.
    9. Gutierrez, Genaro J. & Kouvelis, Panagiotis & Kurawarwala, Abbas A., 1996. "A robustness approach to uncapacitated network design problems," European Journal of Operational Research, Elsevier, vol. 94(2), pages 362-376, October.
    10. Petersen, E. R. & Taylor, A. J., 2001. "An investment planning model for a new North-Central railway in Brazil," Transportation Research Part A: Policy and Practice, Elsevier, vol. 35(9), pages 847-862, November.
    11. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    12. Cipriani, Ernesto & Fusco, Gaetano, 2004. "Combined signal setting design and traffic assignment problem," European Journal of Operational Research, Elsevier, vol. 155(3), pages 569-583, June.
    13. Wu, Dexiang & Wu, Desheng Dash, 2020. "A decision support approach for two-stage multi-objective index tracking using improved lagrangian decomposition," Omega, Elsevier, vol. 91(C).
    14. 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.
    15. Lara, Cristiana L. & Koenemann, Jochen & Nie, Yisu & de Souza, Cid C., 2023. "Scalable timing-aware network design via lagrangian decomposition," European Journal of Operational Research, Elsevier, vol. 309(1), pages 152-169.
    16. Klaus Büdenbender & Tore Grünert & Hans-Jürgen Sebastian, 2000. "A Hybrid Tabu Search/Branch-and-Bound Algorithm for the Direct Flight Network Design Problem," Transportation Science, INFORMS, vol. 34(4), pages 364-380, November.
    17. Joseph Y. J. Chow & Amelia C. Regan, 2011. "Real Option Pricing of Network Design Investments," Transportation Science, INFORMS, vol. 45(1), pages 50-63, February.
    18. Nader Naderializadeh & Kevin A. Crowe, 2020. "Formulating the integrated forest harvest-scheduling model to reduce the cost of the road-networks," Operational Research, Springer, vol. 20(4), pages 2283-2306, December.
    19. Melkote, Sanjay & Daskin, Mark S., 2001. "Capacitated facility location/network design problems," European Journal of Operational Research, Elsevier, vol. 129(3), pages 481-495, March.
    20. Wang, Zujian & Qi, Mingyao, 2019. "Service network design considering multiple types of services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 1-14.

    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:204:y:2010:i:1:p:20-34. 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.