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

General network design: A unified view of combined location and network design problems

Author

Listed:
  • Contreras, Ivan
  • Fernández, Elena

Abstract

This paper presents a unified framework for the general network design problem which encompasses several classical problems involving combined location and network design decisions. In some of these problems the service demand relates users and facilities, whereas in other cases the service demand relates pairs of users between them, and facilities are used to consolidate and re-route flows between users. Problems of this type arise in the design of transportation and telecommunication systems and include well-known problems such as location-network design problems, hub location problems, extensive facility location problems, tree-star location problems and cycle-star location problems, among others. Relevant modeling aspects, alternative formulations and possible algorithmic strategies are presented and analyzed.

Suggested Citation

  • 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.
  • Handle: RePEc:eee:ejores:v:219:y:2012:i:3:p:680-697
    DOI: 10.1016/j.ejor.2011.11.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711009969
    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. Murawski, Lisa & Church, Richard L., 2009. "Improving accessibility to rural health services: The maximal covering network improvement problem," Socio-Economic Planning Sciences, Elsevier, vol. 43(2), pages 102-110, June.
    2. Correia, Isabel & Nickel, Stefan & Saldanha-da-Gama, Francisco, 2010. "The capacitated single-allocation hub location problem revisited: A note on a classical formulation," European Journal of Operational Research, Elsevier, vol. 207(1), pages 92-96, November.
    3. Yaman, Hande & Kara, Bahar Y. & Tansel, Barbaros Ç., 2007. "The latest arrival hub location problem for cargo delivery systems with stopovers," Transportation Research Part B: Methodological, Elsevier, vol. 41(8), pages 906-919, October.
    4. J. F. Campbell & A. T. Ernst & M. Krishnamoorthy, 2005. "Hub Arc Location Problems: Part I---Introduction and Results," Management Science, INFORMS, vol. 51(10), pages 1540-1555, October.
    5. Melo, M.T. & Nickel, S. & Saldanha-da-Gama, F., 2009. "Facility location and supply chain management - A review," European Journal of Operational Research, Elsevier, vol. 196(2), pages 401-412, July.
    6. Nagy, Gabor & Salhi, Said, 2007. "Location-routing: Issues, models and methods," European Journal of Operational Research, Elsevier, vol. 177(2), pages 649-672, March.
    7. Moreno Perez, Jose A. & Marcos Moreno-Vega, J. & Rodriguez Martin, Inmaculada, 2003. "Variable neighborhood tabu search and its application to the median cycle problem," European Journal of Operational Research, Elsevier, vol. 151(2), pages 365-378, December.
    8. Campbell, James F., 1994. "Integer programming formulations of discrete hub location problems," European Journal of Operational Research, Elsevier, vol. 72(2), pages 387-405, January.
    9. 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.
    10. Labbe, Martine & Laporte, Gilbert & Rodriguez Martin, Inmaculada & Gonzalez, Juan Jose Salazar, 2005. "Locating median cycles in networks," European Journal of Operational Research, Elsevier, vol. 160(2), pages 457-470, January.
    11. Boland, Natashia & Krishnamoorthy, Mohan & Ernst, Andreas T. & Ebery, Jamie, 2004. "Preprocessing and cutting for multiple allocation hub location problems," European Journal of Operational Research, Elsevier, vol. 155(3), pages 638-653, June.
    12. A.T. Ernst & M. Krishnamoorthy, 1999. "Solution algorithms for the capacitated single allocation hub location problem," Annals of Operations Research, Springer, vol. 86(0), pages 141-159, January.
    13. Contreras, Ivan & Fernández, Elena & Marín, Alfredo, 2010. "The Tree of Hubs Location Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 390-400, April.
    14. Alumur, Sibel A. & Kara, Bahar Y. & Karasan, Oya E., 2009. "The design of single allocation incomplete hub networks," Transportation Research Part B: Methodological, Elsevier, vol. 43(10), pages 936-951, December.
    15. Alfred A. Kuehn & Michael J. Hamburger, 1963. "A Heuristic Program for Locating Warehouses," Management Science, INFORMS, vol. 9(4), pages 643-666, July.
    16. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    17. Contreras, Ivan & Cordeau, Jean-François & Laporte, Gilbert, 2011. "Stochastic uncapacitated hub location," European Journal of Operational Research, Elsevier, vol. 212(3), pages 518-528, August.
    18. Melkote, Sanjay & Daskin, Mark S., 2001. "An integrated model of facility location and transportation network design," Transportation Research Part A: Policy and Practice, Elsevier, vol. 35(6), pages 515-538, July.
    19. Ebery, Jamie & Krishnamoorthy, Mohan & Ernst, Andreas & Boland, Natashia, 2000. "The capacitated multiple allocation hub location problem: Formulations and algorithms," European Journal of Operational Research, Elsevier, vol. 120(3), pages 614-631, February.
    20. Alumur, Sibel & Kara, Bahar Y., 2008. "Network hub location problems: The state of the art," European Journal of Operational Research, Elsevier, vol. 190(1), pages 1-21, October.
    21. Jiefeng Xu & Steve Y. Chiu & Fred Glover, 1999. "Optimizing a Ring-Based Private Line Telecommunication Network Using Tabu Search," Management Science, INFORMS, vol. 45(3), pages 330-345, March.
    22. Current, John R. & Schilling, David A., 1994. "The median tour and maximal covering tour problems: Formulations and heuristics," European Journal of Operational Research, Elsevier, vol. 73(1), pages 114-126, February.
    23. Drezner, Zvi & Wesolowsky, George O., 2003. "Network design: selection and design of links and facility location," Transportation Research Part A: Policy and Practice, Elsevier, vol. 37(3), pages 241-256, March.
    24. Ernst, Andreas T. & Krishnamoorthy, Mohan, 1998. "Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem," European Journal of Operational Research, Elsevier, vol. 104(1), pages 100-112, January.
    25. Skorin-Kapov, Darko & Skorin-Kapov, Jadranka & O'Kelly, Morton, 1996. "Tight linear programming relaxations of uncapacitated p-hub median problems," European Journal of Operational Research, Elsevier, vol. 94(3), pages 582-593, November.
    26. Costa, Alysson M. & França, Paulo M. & Lyra Filho, Christiano, 2011. "Two-level network design with intermediate facilities: An application to electrical distribution systems," Omega, Elsevier, vol. 39(1), pages 3-13, January.
    27. J. F. Campbell & A. T. Ernst & M. Krishnamoorthy, 2005. "Hub Arc Location Problems: Part II---Formulations and Optimal Algorithms," Management Science, INFORMS, vol. 51(10), pages 1556-1571, October.
    28. Ivan Contreras & Elena Fernández & Alfredo Marín, 2010. "Lagrangean bounds for the optimum communication spanning tree problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 18(1), pages 140-157, July.
    29. Yaman, Hande, 2009. "The hierarchical hub median problem with single assignment," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 643-658, July.
    30. Cordeau, Jean-François & Laporte, Gilbert & Pasin, Federico, 2008. "An iterated local search heuristic for the logistics network design problem with single assignment," International Journal of Production Economics, Elsevier, vol. 113(2), pages 626-640, June.
    31. Mari'n, Alfredo & Canovas, Lazaro & Landete, Mercedes, 2006. "New formulations for the uncapacitated multiple allocation hub location problem," European Journal of Operational Research, Elsevier, vol. 172(1), pages 274-292, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Teodor Gabriel Crainic & Mike Hewitt & Michel Toulouse & Duc Minh Vu, 0. "Scheduled service network design with resource acquisition and management," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 0, pages 1-33.
    2. Etemadnia, Hamideh & Goetz, Stephan J. & Canning, Patrick & Tavallali, Mohammad Sadegh, 2015. "Optimal wholesale facilities location within the fruit and vegetables supply chain with bimodal transportation options: An LP-MIP heuristic approach," European Journal of Operational Research, Elsevier, vol. 244(2), pages 648-661.
    3. Lai, Xiaofan & Xu, Zhou, 2016. "Improved algorithms for joint optimization of facility locations and network connections," European Journal of Operational Research, Elsevier, vol. 250(3), pages 745-753.
    4. repec:eee:energy:v:148:y:2018:i:c:p:977-991 is not listed on IDEAS
    5. 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.
    6. repec:spr:annopr:v:246:y:2016:i:1:d:10.1007_s10479-014-1682-7 is not listed on IDEAS
    7. Alibeyg, Armaghan & Contreras, Ivan & Fernández, Elena, 2016. "Hub network design problems with profits," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 96(C), pages 40-59.
    8. repec:eee:ejores:v:267:y:2018:i:3:p:791-805 is not listed on IDEAS
    9. repec:eee:ejores:v:269:y:2018:i:3:p:1086-1106 is not listed on IDEAS
    10. repec:spr:annopr:v:258:y:2017:i:2:d:10.1007_s10479-015-2091-2 is not listed on IDEAS
    11. repec:eee:proeco:v:198:y:2018:i:c:p:79-92 is not listed on IDEAS
    12. 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.
    13. López-de-los-Mozos, M.C. & Mesa, Juan A. & Schöbel, Anita, 2017. "A general approach for the location of transfer points on a network with a trip covering criterion and mixed distances," European Journal of Operational Research, Elsevier, vol. 260(1), pages 108-121.
    14. 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.
    15. 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.
    16. Rothenbächer, Ann-Kathrin & Drexl, Michael & Irnich, Stefan, 2016. "Branch-and-price-and-cut for a service network design and hub location problem," European Journal of Operational Research, Elsevier, vol. 255(3), pages 935-947.
    17. Christian Tilk & Stefan Irnich, 2016. "Combined Column-and-Row-Generation for the Optimal Communication Spanning Tree Problem," Working Papers 1613, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    18. 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.
    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. repec:eee:ejores:v:265:y:2018:i:2:p:488-502 is not listed on IDEAS
    21. Shishebori, Davood & Yousefi Babadi, Abolghasem, 2015. "Robust and reliable medical services network design under uncertain environment and system disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 77(C), pages 268-288.
    22. 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:219:y:2012:i:3:p:680-697. See general information about how to correct material in RePEc.

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

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.