Skip to main content
SpringerLink
Log in

Dual-RAMP for the Capacitated Single Allocation Hub Location Problem

  • Conference paper
  • First Online:
Computational Science and Its Applications – ICCSA 2017 (ICCSA 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10405))

Included in the following conference series:

Abstract

We consider the Capacitated Single Allocation Hub Location Problem (CSAHLP) in which the objective is to choose the set of hubs from all nodes in a given network in such way that the allocation of all the nodes to the chosen hubs is optimal. We propose a Relaxation Adaptive Memory Programming (RAMP) approach for the CSAHLP. Our method combines Lagrangean Subgradient search with an improvement method to explore primal-dual relationships and create advanced memory structures that integrate information from both primal and dual solutions spaces. The algorithm was tested on the standard dataset and produced extremely competitive results that include new best-known solutions. Comparisons with the current best performing algorithms for the CSAHLP show that our RAMP algorithm exhibits excellent results.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. O’Kelly, M.E.: A quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res. 32, 393–404 (1987). doi:10.1016/S0377-2217(87)80007-3

    Article  MathSciNet  MATH  Google Scholar 

  2. Contreras, I., Díaz, J.A., Fernández, E.: Lagrangean relaxation for the capacitated hub location problem with single assignment. OR Spectr. 31, 483–505 (2009). doi:10.1007/s00291-008-0159-y

    Article  MathSciNet  MATH  Google Scholar 

  3. Farahani, R.Z., Hekmatfar, M., Arabani, A.B., Nikbakhsh, E.: Hub location problems: a review of models, classification, solution techniques, and applications. Comput. Ind. Eng. 64, 1096–1109 (2013). doi:10.1016/j.cie.2013.01.012

    Article  Google Scholar 

  4. Alumur, S., Kara, B.Y.: Network hub location problems: the state of the art. Eur. J. Oper. Res. 190, 1–21 (2008). doi:10.1016/j.ejor.2007.06.008

    Article  MathSciNet  MATH  Google Scholar 

  5. O’Kelly, M.E., Bryan, D., Skorin-Kapov, D., Skorin-Kapov, J.: Hub network design with single and multiple allocation: a computational study. Locat. Sci. 4, 125–138 (1996). doi:10.1016/S0966-8349(96)00015-0

    Article  MATH  Google Scholar 

  6. Campbell, J.F.: A survey of network hub location. Stud. Locat. Anal. 6, 31–49 (1994)

    Google Scholar 

  7. Lawler, E., Wood, D.: Branch-and-bound methods: a survey. Oper. Res. 14, 699–719 (1966). doi:http://dx.doi.org/10.1287/opre.14.4.699

  8. Ernst, A.T., Krishnamoorthy, M.: Solution algorithms for the capacitated single allocation hub location problem. Ann. Oper. Res. 86, 141–159 (1999). doi:10.1023/A:1018994432663

    Article  MathSciNet  MATH  Google Scholar 

  9. Correia, I., Nickel, S., Saldanha-da-Gama, F.: The capacitated single-allocation hub location problem revisited: a note on a classical formulation. Eur. J. Oper. Res. 207, 92–96 (2010). doi:10.1016/j.ejor.2010.04.015

    Article  MathSciNet  MATH  Google Scholar 

  10. Labbé, M., Yaman, H., Gourdin, E.: A branch and cut algorithm for hub location problems with single assignment. Math. Program. 102, 371–405 (2005). doi:10.1007/s10107-004-0531-x

    Article  MathSciNet  MATH  Google Scholar 

  11. da Graça Costa, M., Captivo, M.E., Clímaco, J.: Capacitated single allocation hub location problem-A bi-criteria approach. Comput. Oper. Res. 35, 3671–3695 (2008). doi:10.1016/j.cor.2007.04.005

  12. Almeida, W.G., Yanasse, H.H., Senne, E.L.F.: Uma abordagem exata para problema de localização de concentradores capacitado. In: 43 Simpósio Bras. Pesqui. Operacional, pp. 2192–2203 (2011)

    Google Scholar 

  13. Stanojević, P., Marić, M.: Solving large scale instances of hub location problems with a sub-problem using an exact method. IPSI BgD Trans. Internet Res. 1, 6 (2014). doi:10.1142/9789812709691_0055

    Google Scholar 

  14. Koulamas, C., Antony, S., Jaen, R.: A survey of simulated annealing applications to operations research problems. Omega 22, 41–56 (1994). doi:10.1016/0305-0483(94)90006-X

    Article  Google Scholar 

  15. Stanimirović, Z.: Solving the capacitated single allocation hub location problem using genetic algorithm. In: Recent Advances in Stochastic Modelling and Data Analysis, pp. 464–471. World Scientific (2007)

    Google Scholar 

  16. Almeida, W., Senne, E.L.F., Yanasse, H.: Abordagens meta-heurísticas para o problema de localização de concentradores com restrições de capacidade. In: X Worcap, p. 12 (2010)

    Google Scholar 

  17. Baker, J.: Adaptive selection methods for genetic algorithms. In: Proceedings 1st International Conference Genetic Algorithms, pp. 101–111 (1985)

    Google Scholar 

  18. Stützle, T., Dorigo, M.: The ant colony optimization metaheuristic: algorithms, applications and advances. In: Glover, F., Kochenberger, G.A. (eds.) Handbook Metaheuristics, vol. 57, pp. 250–285. Springer, New York (2003)

    Chapter  Google Scholar 

  19. Randall, M.: Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation. Comput. Optim. Appl. 39, 239–261 (2008). doi:10.1007/s10589-007-9069-1

    Article  MathSciNet  MATH  Google Scholar 

  20. Marić, M.: Variable neighborhood search for solving the capacitated single allocation hub location problem. Serdica J. Comput. 7, 343–354 (2013)

    MathSciNet  Google Scholar 

  21. Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24, 1097–1100 (1997). doi:10.1016/S0305-0548(97)00031-2

    Article  MathSciNet  MATH  Google Scholar 

  22. Stanojević, P., Marić, M., Stanimirović, Z.: A hybridization of an evolutionary algorithm and a parallel branch and bound for solving the capacitated single allocation hub location problem. Appl. Soft Comput. 33, 24–36 (2015). doi:10.1016/j.asoc.2015.04.018

    Article  Google Scholar 

  23. Rego, C.: RAMP: a new metaheuristic framework for combinatorial optimization. In: Rego, C., Alidaee, B. (eds.) Metaheuristic Optimization via Memory and Evolution. Tabu Search and Scatter Search. pp. 441–460. Kluwer Academic Publishers, New York (2005)

    Google Scholar 

  24. Rego, C., Mathew, F., Glover, F.: RAMP for the capacitated minimum spanning tree problem. Ann. Oper. Res. 181, 661–681 (2010). doi:10.1007/s10479-010-0800-4

    Article  MathSciNet  MATH  Google Scholar 

  25. Gamboa, D.: Adaptive memory algorithms for the solution of large scale combinatorial optimization problems. Ph.D. thesis (in portuguese). Instituto Superior Técnico, Universidade Técnica de Lisboa (2008)

    Google Scholar 

  26. Riley, C., Rego, C., Li, H.: A simple dual-RAMP algorithm for resource constraint project scheduling. In: ACM Southeast Region Conference, p. 67 (2010)

    Google Scholar 

  27. Martello, S., Pisinger, D., Toth, P., et al.: New trends in exact algorithms for the 0–1 knapsack problem. Eur. J. Oper. Res. 123, 325–332 (2000). doi:10.1016/S0377-2217(99)00260-X

    Article  MathSciNet  MATH  Google Scholar 

  28. Beasley, J.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. 65, 1069–1072 (1990)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CIICESI, Escola Superior de Tecnologia e Gestão, Instituto Politécnico do Porto, Felgueiras, Portugal

    Telmo Matos & Dorabela Gamboa

Authors
  1. Telmo Matos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dorabela Gamboa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Telmo Matos or Dorabela Gamboa .

Editor information

Editors and Affiliations

  1. University of Perugia, Perugia, Italy

    Osvaldo Gervasi

  2. University of Basilicata, Potenza, Italy

    Beniamino Murgante

  3. Covenant University, Ota, Nigeria

    Sanjay Misra

  4. University of Trieste, Trieste, Italy

    Giuseppe Borruso

  5. Polytechnic University of Bari, Bari, Italy

    Carmelo M. Torre

  6. University of Minho, Braga, Portugal

    Ana Maria A.C. Rocha

  7. Monash University, Clayton, Victoria, Australia

    David Taniar

  8. Kyushu Sangyo University, Fukuoka, Japan

    Bernady O. Apduhan

  9. Saint Petersburg State University, Saint Petersburg, Russia

    Elena Stankova

  10. University of Trieste, Trieste, Italy

    Alfredo Cuzzocrea

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Matos, T., Gamboa, D. (2017). Dual-RAMP for the Capacitated Single Allocation Hub Location Problem. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2017. ICCSA 2017. Lecture Notes in Computer Science(), vol 10405. Springer, Cham. https://doi.org/10.1007/978-3-319-62395-5_48

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-62395-5_48

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-62394-8

  • Online ISBN: 978-3-319-62395-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation