Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A biased random-key genetic algorithm for the two-level hub location routing problem with directed tours

  • Original Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

In this article, a solution is proposed through a population-based metaheuristic for the Two-level Hub Location Routing Problem with Directed Tours (THLRP-DT). Hubs are facilities used to handle and dispatch resources on a given network. The goal of the THLRP-DT is to locate a set of hubs on a network and to route resources from sources to destinations, where the hubs are connected by means of an oriented cycle, and the spokes form clusters. Each cluster is composed of a unique hub, including none or some spoke nodes, connected in an oriented cycle structure. This problem appears in transportation logistics, where the flow of demands can be aggregated, resulting in economies of scale, and the orientations of arcs model a one way flow direction, which speeds up the distribution. We propose a Biased Random-Key Genetic Algorithm (BRKGA) metaheuristic, where the parameters have been calibrated using a machine learning package, which makes use of a machine learning mechanism. The results obtained using the BRKGA metaheuristic are of high quality compared to the ones found in the literature, improving solutions for instances with unknown optimal values.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Data Availability

The data used in the current study are third party data, freely available for research purposes in the site https://grafo.etsii.urjc.es/optsicom/uraphmp/.

Notes

  1. Instances available in https://grafo.etsii.urjc.es/optsicom/uraphmp/.

References

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

    Article  Google Scholar 

  • Andrade CE, Miyazawa FK, Mauricio GCR (2013) Evolutionary algorithm for the k-interconnected multi-depot multi-traveling salesmen problem. In: Proceedings of the 15th annual conference on genetic and evolutionary computation, New York, NY, USA, pp 463–470

  • Arefi MS, Rezaei H (2015) Problem solving of container loading using genetic algorithm based on modified random keys. J Adv Comput Sci Technol 4(1):190–197

    Article  Google Scholar 

  • Bean JC (1994) Genetic algorithms and random keys for sequencing and optimization. INFORMS J Comput 6(2):154–160

    Article  Google Scholar 

  • Beasley JE (1983) Route first-cluster second methods for vehicle routing. Omega 11(4):403–408

    Article  Google Scholar 

  • Camargo R, Miranda G, Løkketangen A (2013) A new formulation and an exact approach for the many-to-many hub location-routing problem. Appl Math Model 37:7465–7480

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Cunha CB, Silva MR (2007) A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil. Eur J Oper Res 179(3):747–758

    Article  Google Scholar 

  • Cunha C, Silva M (2007) A genetic algorithm for the problem of configuring a hub-and-spoke network for a LTL trucking company in Brazil. Eur J Oper Res 179:747–758

    Article  Google Scholar 

  • Da Costa Fontes FF (2017) Optimization models and algorithms for the design of global transportation networks. Ph.D. thesis, Artois University, Artois, France

  • Da Costa Fontes FF, Goncalves G (2019) A variable neighbourhood decomposition search approach applied to a global liner shipping network using a hub-and-spoke with sub-hub structure. Int J Prod Res 59:1–17

    Google Scholar 

  • Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J Oper Res Soc Am 2(4):393–410

    Google Scholar 

  • Drezner Z, Wesolowsky GO (1997) Selecting an optimum configuration of one-way and two-way routes. Transp Sci 31(4):386–394

    Article  Google Scholar 

  • Duhamel C, Aloise DJ, Santos AC, Freire de Oliveira TH (2016) Split procedure for graph partitioning: an application to the SONET ring problem. In: 8th IFAC conference on manufacturing modelling, management and control (MIM 2016), 49. Troyes, France, pp 763–768

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

    Article  Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Mathematical Sciences Series (1979)

  • Gonçalves J, Resende MG (2011) Biased random-key genetic algorithms for combinatorial optimization. J Heuristics 17:487–525

    Article  Google Scholar 

  • Ishfaq R, Sox CR (2012) Design of intermodal logistics networks with hub delays. Eur J Oper Res 220(3):629–641

    Article  Google Scholar 

  • Lalla-Ruiz E, González-Velarde JL, Melián-Batista B, Moreno-Vega JM (2014) Biased random key genetic algorithm for the tactical berth allocation problem. Appl Soft Comput 22:60–76

    Article  Google Scholar 

  • Lopes MC, de Andrade CE, de Queiroz TA, Resende MGC, Miyazawa FK (2016) Heuristics for a hub location-routing problem. Networks 68(1):54–90

    Article  Google Scholar 

  • López-Ibá nez M, Dubois-Lacoste J, PérezCáceres L, Stützle T, Birattari M, (2016) The IRACE package: iterated racing for automatic algorithm configuration. Oper Res Perspect 3:43–58

    Google Scholar 

  • Nagy G, Salhi S (1998) The many-to-many location-routing problem. Top 6:261–275

    Article  Google Scholar 

  • Nagy G, Salhi S (2007) Location-routing: issues, models and methods. Eur J Oper Res 177(2):649–672

    Article  Google Scholar 

  • O’Kelly ME (1986) The location of interacting hub facilities. Transp Sci 20(2):92–106

    Article  Google Scholar 

  • O’Kelly ME (1987) A quadratic integer program for the location of interacting hub facilities. Eur J Oper Res 32(3):393–404

    Article  Google Scholar 

  • Pessoa L, Santos AC, Resende M (2017) A biased random-key genetic algorithm for the tree of hubs location problem. Optim Lett 11(7):1371–1384

    Article  Google Scholar 

  • Prodhon C, Prins C (2014) A survey of recent research on location-routing problems. Eur J Oper Res 238(1):1–17

    Article  Google Scholar 

  • Rodríguez-Martín I, Salazar-González J-J, Yaman H (2016) The ring/k-rings network design problem: Model and branch-and-cut algorithm. Networks 68(2):130–140

    Article  Google Scholar 

  • Stefanello F, Buriol L, Hirsch M, Pardalos P, Querido T, Resende M, Ritt M (2017) On the minimization of traffic congestion in road networks with tolls. Ann Oper Res 249:119–139

    Article  Google Scholar 

  • Thomadsen T, Stidsen T (2005) Hierarchical ring network design using branch-and-price. Telecommun Syst 29:61–76

    Article  Google Scholar 

  • Villiam MS, Kenneth DJ (1991) On the virtues of parameterized uniform crossover. In: In proceedings of the fourth international conference on genetic algorithms, pp 230–236

  • Wang JJ, Cheng MC (2010) From a hub port city to a global supply chain management center: a case study of Hong Kong. J Transp Geogr 18(1):104–115

    Article  Google Scholar 

  • ZanjiraniFarahani R, Hekmatfar M, Boloori A, Nikbakhsh E (2013) Hub location problems: a review of models, classification, solution techniques, and applications. Comput Ind Eng 64:1096–1109

    Article  Google Scholar 

Download references

Acknowledgements

This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) The authors would like to thank the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions.

Author information

Authors and Affiliations

  1. Programa de Pós-Graduação em Ciência da Computação UERN/UFERSA, Universidade do Estado do Rio Grande do Norte (UERN), Universidade Federal Rural do Semi-Árido (UFERSA), Mossoró, RN, 100190, Brazil

    Caio César De Freitas, Dario José Aloise, Fábio Francisco Da Costa Fontes & Matheus Da Silva Menezes

  2. LITIS, ISEL, Université Le Havre Normandie, Le Havre, 76600, France

    Andréa Cynthia Santos

Authors
  1. Caio César De Freitas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dario José Aloise
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fábio Francisco Da Costa Fontes
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andréa Cynthia Santos
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Matheus Da Silva Menezes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andréa Cynthia Santos.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

De Freitas, C.C., Aloise, D.J., Da Costa Fontes, F.F. et al. A biased random-key genetic algorithm for the two-level hub location routing problem with directed tours. OR Spectrum 45, 903–924 (2023). https://doi.org/10.1007/s00291-023-00718-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-023-00718-y

Keywords

Search

Navigation