IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v43y2009i1p86-97.html
   My bibliography  Save this article

Benders Decomposition for Hub Location Problems with Economies of Scale

Author

Listed:
  • Ricardo Saraiva de Camargo

    (Department of Applied and Exact Sciences, Federal University of Ouro Preto, João Monlevade, 35931-026, Minas Gerais, Brazil)

  • Gilberto de Miranda

    (Department of Industrial Engineering, Federal University of Minas Gerais, Pampulha, 30161-010, Belo Horizonte, Minas Gerais, Brazil)

  • Henrique Pacca L. Luna

    (Computer Sciences Institute, Federal University of Alagoas, Campus A. C. Simões, Tabuleiro dos Martins, 57072-970, Maceió, Alagoas, Brazil)

Abstract

When considering hub-and-spoke networks with multiple allocation, the classical models of the literature compute solutions with large discount factors for small flows on interhub connections. Addressing the economies of scale issue, a tighter formulation for this problem is presented, bringing forward a special structure. A specialized version of Benders decomposition is then developed to solve large instances in reasonable time.

Suggested Citation

  • Ricardo Saraiva de Camargo & Gilberto de Miranda & Henrique Pacca L. Luna, 2009. "Benders Decomposition for Hub Location Problems with Economies of Scale," Transportation Science, INFORMS, vol. 43(1), pages 86-97, February.
    • Handle: RePEc:inm:ortrsc:v:43:y:2009:i:1:p:86-97
    DOI: 10.1287/trsc.1080.0233
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1080.0233
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1080.0233?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
    ---><---

    References listed on IDEAS

    as
    1. John Klincewicz, 2002. "Enumeration and Search Procedures for a Hub Location Problem with Economies of Scale," Annals of Operations Research, Springer, vol. 110(1), pages 107-122, February.
    2. Aykin, Turgut, 1994. "Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem," European Journal of Operational Research, Elsevier, vol. 79(3), pages 501-523, December.
    3. Heragu, Sunderesh S. & Chen, Ja-Shen, 1998. "Optimal solution of cellular manufacturing system design: Benders' decomposition approach," European Journal of Operational Research, Elsevier, vol. 107(1), pages 175-192, May.
    4. 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.
    5. 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.
    6. Turgut Aykin, 1995. "Networking Policies for Hub-and-Spoke Systems with Application to the Air Transportation System," Transportation Science, INFORMS, vol. 29(3), pages 201-221, August.
    7. Mayer, Gabriela & Wagner, Bernd, 2002. "HUBLocator : an exact solution method for the multiple allocation hub location problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 18962, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    8. Skorin-Kapov, Darko & Skorin-Kapov, Jadranka, 1994. "On tabu search for the location of interacting hub facilities," European Journal of Operational Research, Elsevier, vol. 73(3), pages 502-509, March.
    9. Hasan Pirkul & David A. Schilling, 1998. "An Efficient Procedure for Designing Single Allocation Hub and Spoke Systems," Management Science, INFORMS, vol. 44(12-Part-2), pages 235-242, December.
    10. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2000. "A Benders Decomposition Approach for the Locomotive and Car Assignment Problem," Transportation Science, INFORMS, vol. 34(2), pages 133-149, May.
    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. Racunica, Illia & Wynter, Laura, 2005. "Optimal location of intermodal freight hubs," Transportation Research Part B: Methodological, Elsevier, vol. 39(5), pages 453-477, June.
    13. A. M. Geoffrion & G. W. Graves, 1974. "Multicommodity Distribution System Design by Benders Decomposition," Management Science, INFORMS, vol. 20(5), pages 822-844, January.
    14. 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.
    15. O'Kelly, M. E. & Bryan, D. L., 1998. "Hub location with flow economies of scale," Transportation Research Part B: Methodological, Elsevier, vol. 32(8), pages 605-616, November.
    16. A. T. Ernst & M. Krishnamoorthy, 1998. "An Exact Solution Approach Based on Shortest-Paths for p -Hub Median Problems," INFORMS Journal on Computing, INFORMS, vol. 10(2), pages 149-162, May.
    17. 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.
    18. 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.
    19. S. L. Hakimi, 1965. "Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems," Operations Research, INFORMS, vol. 13(3), pages 462-475, June.
    20. Jean-François Cordeau & François Soumis & Jacques Desrosiers, 2001. "Simultaneous Assignment of Locomotives and Cars to Passenger Trains," Operations Research, INFORMS, vol. 49(4), pages 531-548, August.
    21. Ximing Cai & Daene C. McKinney & Leon S. Lasdon & David W. Watkins, 2001. "Solving Large Nonconvex Water Resources Management Models Using Generalized Benders Decomposition," Operations Research, INFORMS, vol. 49(2), pages 235-245, April.
    22. Birge, John R. & Louveaux, Francois V., 1988. "A multicut algorithm for two-stage stochastic linear programs," European Journal of Operational Research, Elsevier, vol. 34(3), pages 384-392, March.
    23. Klincewicz, J. G., 1991. "Heuristics for the p-hub location problem," European Journal of Operational Research, Elsevier, vol. 53(1), pages 25-37, July.
    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. 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.
    2. Dhyani, Sneha & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2019. "Alternate Second Order Conic Programming Reformulations for Hub Location with Capacity Selection under Demand," IIMA Working Papers WP 2018-12-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    3. de Sá, Elisangela Martins & de Camargo, Ricardo Saraiva & de Miranda, Gilberto, 2013. "An improved Benders decomposition algorithm for the tree of hubs location problem," European Journal of Operational Research, Elsevier, vol. 226(2), pages 185-202.
    4. Yaman, Hande, 2011. "Allocation strategies in hub networks," European Journal of Operational Research, Elsevier, vol. 211(3), pages 442-451, June.
    5. 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.
    6. Ivan Contreras & Jean-François Cordeau & Gilbert Laporte, 2012. "Exact Solution of Large-Scale Hub Location Problems with Multiple Capacity Levels," Transportation Science, INFORMS, vol. 46(4), pages 439-459, November.
    7. Alumur, Sibel A. & Nickel, Stefan & Saldanha-da-Gama, Francisco, 2012. "Hub location under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 46(4), pages 529-543.
    8. Samir Elhedhli & Huyu Wu, 2010. "A Lagrangean Heuristic for Hub-and-Spoke System Design with Capacity Selection and Congestion," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 282-296, May.
    9. Ivan Contreras & Jean-François Cordeau & Gilbert Laporte, 2011. "Benders Decomposition for Large-Scale Uncapacitated Hub Location," Operations Research, INFORMS, vol. 59(6), pages 1477-1490, December.
    10. Alumur, Sibel A. & Campbell, James F. & Contreras, Ivan & Kara, Bahar Y. & Marianov, Vladimir & O’Kelly, Morton E., 2021. "Perspectives on modeling hub location problems," European Journal of Operational Research, Elsevier, vol. 291(1), pages 1-17.
    11. Neamatian Monemi, Rahimeh & Gelareh, Shahin & Nagih, Anass & Maculan, Nelson & Danach, Kassem, 2021. "Multi-period hub location problem with serial demands: A case study of humanitarian aids distribution in Lebanon," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    12. Julia Sender & Thomas Siwczyk & Petra Mutzel & Uwe Clausen, 2017. "Matheuristics for optimizing the network in German wagonload traffic," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 367-392, September.
    13. Jayaswal, Sachin & Vidyarthi, Navneet, 2023. "Multiple allocation hub location with service level constraints for two shipment classes," European Journal of Operational Research, Elsevier, vol. 309(2), pages 634-655.
    14. James F. Campbell & Morton E. O'Kelly, 2012. "Twenty-Five Years of Hub Location Research," Transportation Science, INFORMS, vol. 46(2), pages 153-169, May.
    15. He, Yan & Wu, Tao & Zhang, Canrong & Liang, Zhe, 2015. "An improved MIP heuristic for the intermodal hub location problem," Omega, Elsevier, vol. 57(PB), pages 203-211.
    16. Jayaswal, Sachin & Vidyarthi, Navneet, 2013. "Capacitated Multiple Allocation Hub Location with Service Level Constraints for Multiple Consignment Classes," IIMA Working Papers WP2013-11-02, Indian Institute of Management Ahmedabad, Research and Publication Department.
    17. Ivan Contreras & Juan A. Díaz & Elena Fernández, 2011. "Branch and Price for Large-Scale Capacitated Hub Location Problems with Single Assignment," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 41-55, February.
    18. Taherkhani, Gita & Alumur, Sibel A., 2019. "Profit maximizing hub location problems," Omega, Elsevier, vol. 86(C), pages 1-15.
    19. Gelareh, Shahin & Nickel, Stefan, 2011. "Hub location problems in transportation networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(6), pages 1092-1111.
    20. 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.

    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:inm:ortrsc:v:43:y:2009:i:1:p:86-97. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.