Skip to main content
SpringerLink
Log in

The ordered median tree of hubs location problem

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

In this paper, we propose the Ordered Median Tree of Hub Location Problem (OMTHL). The OMTHL is a single-allocation hub location problem where p hubs must be placed on a network and connected by a non-directed tree. Each non-hub node is assigned to a single hub and all the flow between origin–destination pairs must cross at least one hub. The objective is to minimize the sum of the ordered weighted averaged collection and distribution costs plus the sum of the interhub flow costs. We present different MILP formulations for the OMTHL based on the properties of the Minimum Spanning Tree Problem, the ordered median optimization and on the different ways of modeling flow within the network. Given that ordered median hub location problems are rather difficult to solve, we have improved the OMTHL solution performance by introducing covering variables in two valid reformulations. In addition, we have developed two pre-processing phases to reduce the size of these formulations. We establish an empirical comparison between these new formulations and we also provide enhancements that together with a proper formulation allow to solve medium-size instances on general random graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Alumur S, Kara B (2008) Network hub location problems: the state of the art. Eur J Oper Res 190(1):1–21

    Google Scholar 

  • Blanco V, Marín A (2019) Upgrading nodes in tree-shaped hub location. Comput Oper Res 102:75–90

    Google Scholar 

  • Boland N, Krishnamoorthy M, Ernst A, Ebery J (2004) Preprocessing and cutting for multiple allocation hub location problems. Eur J Oper Res 155(3):638–653

    Google Scholar 

  • Boland N, Domínguez-Marín P, Nickel S, Puerto J (2006) Exact procedures for solving the discrete ordered median problem. Comput Oper Res 33(11):3270–3300

    Google Scholar 

  • Bollapragada R, Li Y, Rao U (2006) Budget-constrained, capacitated hub location to maximize expected demand coverage in fixed-wireless telecommunication networks. INFORMS J Comput 18(4):422–432

    Google Scholar 

  • Campbell J (1996) Hub location and the \(p\)-hub median problem. Oper Res 44(6):923–935

    Google Scholar 

  • Campbell J, O’Kelly M (2012) Twenty five years of hub location research. Transport Sci 46(2):153–169

    Google Scholar 

  • Campbell J, Ernst A, Krishnamoorthy M (2002) Hub location problems. In: Drezner Z, Hamacher H (eds) Facility location: applications and theory. Springer, New York, pp 373–407

    Google Scholar 

  • Campbell JF, Ernst AT, Krishnamoorthy M (2005a) Hub arc location problems: part I Introduction and results. Manag Sci 51(10):1540–1555

    Google Scholar 

  • Campbell J, Ernst A, Krishnamoorthy M (2005b) Hub arc location problems. II: formulations and optimal algorithms. Manag Sci 51(10):1556–1571

    Google Scholar 

  • Campbell A, Lowe T, Zhang L (2007) The \(p\)-hub center allocation problem. Eur J Oper Res 176(2):819–835

    Google Scholar 

  • Cánovas L, García S, Marín A (2007) Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique. Eur J Oper Res 179(3):990–1007

    Google Scholar 

  • Chen H, Campbell AM, Thomas BW (2008) Network design for time-constrained delivery. Nav Res Logist 55:493–515

    Google Scholar 

  • Contreras I, Fernández E (2014) Hub location as the minimization of a supermodular set function. Oper Res 62:557–570

    Google Scholar 

  • Contreras I, O’Kelly M (2019a) Hub location problems. In: Laporte G, Nickel S, Saldanha da Gama F (eds) Location science, 2nd edn. Springer, New York, pp 311–314

    Google Scholar 

  • Contreras I, Díaz J, Fernández E (2009) Lagrangean relaxation for the capacitated hub location problem with single assignment. OR Spectr 31(3):483–505

    Google Scholar 

  • Contreras I, Fernández E, Marín A (2009) Tight bounds from a path based formulation for the tree of hub location problem. Comput Oper Res 36(12):3117–3127

    Google Scholar 

  • Contreras I, Fernández E, Marín A (2010) The tree of hubs location problem. Eur J Oper Res 202(2):390–400

    Google Scholar 

  • Contreras I, Tanash M, Vidyarthi N (2017) Exact and approximate algorithms for the cycle hub location problem. Ann Oper Res 258(2):655–677

    Google Scholar 

  • Ernst A, Krishnamoorthy M (1999) Solution algorithms for the capacitated single allocation hub location problem. Ann Oper Res 86:141–159

    Google Scholar 

  • Farahani RZ, Hekmatfar M, Arabani A, Nikbakhsh E (2013) Hub location problems: a review of models, classification, solution techniques, and applications. Comput Ind Eng 4(4):1096–1109

    Google Scholar 

  • Fernández E, Sgalambro A (2020) On carriers collaboration in hub location problems. Eur J Oper Res 283(2):476–490

    Google Scholar 

  • Fonseca MC, García-Sánchez A, Ortega-Mier M, Saldanha-da-Gama F (2010) A stochastic bi-objective location model for strategic reverse logistics. TOP 18(1):158–184

    Google Scholar 

  • Gollowitzer S, Ljubić I (2011) MIP models for connected facility location: a theoretical and computational study. Comput Oper Res 38(2):435–449

    Google Scholar 

  • Hamacher H, Labbé M, Nickel S, Sonneborn T (2004) Adapting polyhedral properties from facility to hub location problems. Discrete Appl Math 145(1):104–116

    Google Scholar 

  • Hu TC (1974) Optimum communication spanning trees. SIAM J Comput 3(3):188–195

    Google Scholar 

  • Kalcsics J, Nickel S, Puerto J, Rodríguez-Chía AM (2010a) The ordered capacitated facility location problem. TOP 18:203–222

    Google Scholar 

  • Kalcsics J, Nickel S, Puerto J, Rodríguez-Chía AM (2010b) Distribution systems design with role dependent objectives. Eur J Oper Res 202:491–501

    Google Scholar 

  • Kara B, Tansel B (2000) On the single-assignment \(p\)-hub center problem. Eur J Oper Res 125(3):648–655

    Google Scholar 

  • Kara B, Tansel B (2003) The single-assignment hub covering problem: models and linearizations. J Oper Res Soc 54(1):59–64

    Google Scholar 

  • Kratica J, Stanimirović Z (2006) Solving the uncapacitated multiple allocation p-hub center problem by genetic algorithm. Asia Pac J Oper Res 23(4):425–437

    Google Scholar 

  • Labbé M, Yaman H (2004) Projecting the flow variables for hub location problems. Networks 44(2):84–93

    Google Scholar 

  • Labbé M, Yaman H (2008) Solving the hub location problem in a star-star network. Networks 51(1):19–33

    Google Scholar 

  • Labbé M, Yaman H, Gourdin E (2005) A branch and cut algorithm for hub location problems with single assignment. Math Program 102(2):371–405

    Google Scholar 

  • Lee CH, Ro HB, Tcha DW (1993) Topological design of a two-level network with ring-star configuration. Comput Oper Res 20(6):625–637

    Google Scholar 

  • Marín A (2005a) Formulating and solving splittable capacitated multiple allocation hub location problems. Comput Oper Res 32(12):3093–3109

    Google Scholar 

  • Marín A (2005b) Uncapacitated Euclidean hub location: strengthened formulation, new facets and a relax-and-cut algorithm. J Glob Optim 33(3):393–422

    Google Scholar 

  • Marín A, Cánovas L, Landete M (2006) New formulations for the uncapacitated multiple allocation hub location problem. Eur J Oper Res 172(1):274–292

    Google Scholar 

  • Marín A, Nickel S, Puerto J, Velten S (2009) A flexible model and efficient solution strategies for discrete location problems. Discrete Appl Math 157(5):1128–1145

    Google Scholar 

  • Marín A, Nickel S, Velten S (2010) An extended covering model for flexible discrete and equity location problems. Math Methods Oper Res 71(1):125–163

    Google Scholar 

  • Martins de Sá E, de Camargo RS, de Miranda G (2013) An improved Benders decomposition algorithm for the tree of hubs location problem. Eur J Oper Res 226(2):185–202

    Google Scholar 

  • Martins de Sá E, Contreras I, Cordeau JF, de Camargo RS, de Miranda G (2015) The hub line location problem. Transport Sci 49(3):500–518

    Google Scholar 

  • Meyer T, Ernst A, Krishnamoorthy M (2009) A 2-phase algorithm for solving the single allocation \(p\)-hub center problem. Comput Oper Res 36(12):3143–3151

    Google Scholar 

  • Nguyen VH, Knippel A (2007) On tree star network design. In: Proceedings of international network optimization conference INOC 2007, pp 1–6

  • Nickel S, Puerto J (2005) Location theory: a unified approach. Springer, Heidelberg

    Google Scholar 

  • O’Kelly ME, Miller HJ (1994) The hub network design problem: a review and synthesis. J Transp Geogr 2(1):31–40

    Google Scholar 

  • Ortega F, Wolsey L (2003) A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem. Networks 41(3):143–158

    Google Scholar 

  • Puerto J, Ramos A, Rodríguez-Chía A (2011) Single-allocation ordered median hub location problems. Comput Oper Res 38:559–570

    Google Scholar 

  • Puerto J, Ramos AB, Rodríguez-Chía AM (2013) A specialized branch and bound and cut for single-allocation ordered median hub location problems. Discrete Appl Math 161:2624–2646

    Google Scholar 

  • Puerto J, Ramos A, Rodríguez-Chía A, Sánchez-Gil M (2016) Ordered median hub location problems with capacity constraints. Transport Res Part C Emerg Technol 70:142–156

    Google Scholar 

  • Ramos A (2012) Localización de concentradores para mediana ordenada. Ph.D. Thesis Universidad de Sevilla (In Spanish)

  • Rodríguez-Martín I, Salazar-González J (2008) Solving a capacitated hub location problem. Eur J Oper Res 184(2):468–479

    Google Scholar 

  • Taherkhani G, Alumur SA (2019) Profit maximizing hub location problems. Omega 86:1–15

    Google Scholar 

  • Tan P, Kara B (2007) A hub covering model for cargo delivery systems. Networks 49(1):28–39

    Google Scholar 

  • Wagner B (2008) Model formulations for hub covering problems. J Oper Res Soc 59(7):932–938

    Google Scholar 

  • Yaman H (2005) Polyhedral analysis for the uncapacitated hub location problem with modular arc capacities. SIAM J Discrete Math 19(2):501–522

    Google Scholar 

Download references

Acknowledgements

The authors have been partially supported by projects MTM2016-74983-C02-01,02 (MINECO/FEDER), CEI-3-FQM331, US-1256951, “NetmeetData” (Fundación BBVA, 2019), P18-FR-1422 (Proyecto Frontera del conocimiento JJAA) and FEDER-UCA18-106895 (Junta de Andalucía/FEDER/UCA).

Author information

Authors and Affiliations

  1. Department of Statistics and Operational Research, University of Seville, Seville, Spain

    Miguel A. Pozo & Justo Puerto

  2. Department of Statistics and Operational Research, University of Cádiz, Puerto Real (Cádiz), Spain

    Antonio M. Rodríguez Chía

Authors
  1. Miguel A. Pozo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Justo Puerto
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Antonio M. Rodríguez Chía
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Antonio M. Rodríguez Chía.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pozo, M.A., Puerto, J. & Rodríguez Chía, A.M. The ordered median tree of hubs location problem. TOP 29, 78–105 (2021). https://doi.org/10.1007/s11750-020-00572-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-020-00572-z

Keywords

Mathematics Subject Classification

Search

Navigation