An Hybrid NSGA-II Algorithm for the Bi-objective Mobile Mammography Unit Routing Problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

An Hybrid NSGA-II Algorithm for the Bi-objective Mobile Mammography Unit Routing Problem

  • Conference paper
  • First Online:
Artificial Intelligence and Soft Computing (ICAISC 2023)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 14125))

Included in the following conference series:

  • 457 Accesses

Abstract

This work deals with the Mobile Mammography Unit Routing Problem in Brazil. The problem is a Multi-depot Open Vehicle Routing Problem variant. In this problem, there are a fixed number of depots, each with a limited number of Mobile Mammography Units (MMUs). Each MMU has a known screening capacity and a set of candidate cities it can serve with known demands for screening. The objective is to define the cities visiting order for each MMU, maximizing the served screening demand and minimizing the total travel distance. We introduce a mathematical programming formulation and two algorithms based on Non-dominated Sorting Genetic Algorithm II (NSGA-II). They differ from each other by the use of a local search. One version has a Local Search as a mutation operator, and the other does not. Both algorithms were tested on benchmark based on real data from Minas Gerais state, Brazil. We used the hypervolume metric to analyze the performance of the proposed algorithms considering different scenarios. The results indicate that using multiple crossover operators and adding a local search as a mutation operator to the algorithm brings better results.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 9380
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 11725
Price includes VAT (Japan)
  • 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

Notes

  1. 1.

    All used instances are available at https://bit.ly/3mxnIbl.

References

  1. Amaral, P., Luz, L., Cardoso, F., Freitas, R.: Spatial distribution of mammography equipment in brazil. Revista Brasileira de Estudos Urbanos e Regionais 19(2), 326 (2017). https://doi.org/10.22296/2317-1529.2017v19n2p326

    Article  Google Scholar 

  2. Audet, C., Bigeon, J., Cartier, D., Le Digabel, S., Salomon, L.: Performance indicators in multiobjective optimization. Eur. J. Oper. Res. 292(2), 397–422 (2021). https://doi.org/10.1016/j.ejor.2020.11.016

    Article  MathSciNet  MATH  Google Scholar 

  3. Bellmore, M., Nemhauser, G.L.: The traveling salesman problem: a survey. Oper. Res. 16(3), 538–558 (1968). https://doi.org/10.1287/opre.16.3.538

    Article  MathSciNet  MATH  Google Scholar 

  4. de Campos, M.V.A., de Sá, M.V.S.M., Rosa, P.M., Penna, P.H.V., de Souza, S.R., Souza, M.J.F.: A mixed linear integer programming formulation and a simulated annealing algorithm for the mammography unit location problem. In: ICEIS, pp. 428–439 (2020). https://doi.org/10.5220/0009420704280439

  5. de Carvalho, L.R., do Amaral, P.V.M., Mendes, P.S.: Matrizes de distâncias e tempo de deslocamento rodoviário entre os municípios brasileiros : uma atualização metodológica para 2020. Textos para Discussão Cedeplar-UFMG 630, Cedeplar, Universidade Federal de Minas Gerais (2021). https://ideas.repec.org/p/cdp/texdis/td630.html

  6. Corrêa, V.H.V., Costa Lima, B.J., Silva-e-Souza, P.H., Penna, P.H.V., Souza, M.J.F.: Localização de mamógrafos: um estudo de caso na rede pública de saúde. In: Anais do Simpósio Brasileiro de Pesquisa Operacional, p. 84874. Rio de Janeiro, Brazil (2018). http://bit.ly/3ZDmusx

  7. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002). https://doi.org/10.1109/4235.996017

    Article  Google Scholar 

  8. Ferlay, J., et al.: International agency for research on cancer (2020). https://gco.iarc.fr/today. Accessed 18 Mar 2023

  9. Fonseca, C., Paquete, L., Lopez-Ibanez, M.: An improved dimension-sweep algorithm for the hypervolume indicator. In: 2006 IEEE International Conference on Evolutionary Computation, pp. 1157–1163 (2006). https://doi.org/10.1109/CEC.2006.1688440

  10. Hansen, P., Mladenović, N., Todosijević, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Opt. 5(3), 423–454 (2017). https://doi.org/10.1007/s13675-016-0075-x

    Article  MathSciNet  MATH  Google Scholar 

  11. Hussain, A., Muhammad, Y., Nauman Sajid, M., Hussain, I., Mohamd Shoukry, A., Gani, S.: Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Computational Intelligence and Neuroscience 2017, pp. 1–7 (2017). https://doi.org/10.1155/2017/7430125

  12. IBGE: Áreas territoriais (2021). https://bit.ly/3Mh1TqO. Accessed 23 Mar 2023

  13. INCA: A situação do câncer de mama no brasil: síntese de dados dos sistemas de informação (2019). https://bit.ly/3ocLOZt

  14. INCA: Estatísticas de câncer (2022). https://www.inca.gov.br/numeros-de-cancer. Accessed 3 Jul 2022

  15. Lalla-Ruiz, E., Mes, M.: Mathematical formulations and improvements for the multi-depot open vehicle routing problem. Optim. Lett. 15(1), 271–286 (2020). https://doi.org/10.1007/s11590-020-01594-z

    Article  MathSciNet  MATH  Google Scholar 

  16. Lenstra, J.K., Kan, A.R.: Complexity of vehicle routing and scheduling problems. Networks 11(2), 221–227 (1981). https://doi.org/10.1002/net.3230110211

    Article  Google Scholar 

  17. López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L.P., Birattari, M., Stützle, T.: The Irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43–58 (2016). https://doi.org/10.1016/j.orp.2016.09.002

    Article  MathSciNet  Google Scholar 

  18. Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 31(12), 1985–2002 (2004). https://doi.org/10.1016/S0305-0548(03)00158-8

    Article  MathSciNet  MATH  Google Scholar 

  19. Prins, C., Lacomme, P., Prodhon, C.: Order-first split-second methods for vehicle routing problems: a review. Transp. Res. Part C Emer. Technol. 40, 179–200 (2014). https://doi.org/10.1016/j.trc.2014.01.011

    Article  Google Scholar 

  20. Rosa, O.A.S., Rosa, P.M., Penna, P.H.V., Souza, M.J.F.: Um algoritmo construtivo para o problema de roteamento de unidades móveis de mamografia. Simpósio Brasileiro de Pesquisa Operacional (2020). http://bit.ly/3lVa5Ck

  21. Souza, M.J.F., Coelho, I.M., Ribas, S., Santos, H.G., Merschmann, L.H.C.: A hybrid heuristic algorithm for the open-pit-mining operational planning problem. Eur. J. Oper. Res. 207(2), 1041–1051 (2010). https://doi.org/10.1016/j.ejor.2010.05.031

    Article  MATH  Google Scholar 

  22. Souza, M.J.F., Penna, P.H.V., Moreira de Sá, M.V.S., Rosa, P.M.: A vns-based algorithm for the mammography unit location problem. In: International Conference on Variable Neighborhood Search. pp. 37–52. Springer (2020). DOI: 10.1007/978-3-030-44932-2_3

    Google Scholar 

  23. Souza, M., Penna, P., Sá, M., Rosa, P., Monteiro, J., Lisboa, M.: Localização de mamógrafos: formulações e estudo preliminar de caso de Rondônia. In: Anais do LI Simpósio Brasileiro de Pesquisa Operacional, vol. 51, p. 107698. SOBRAPO, Galoá, Limeira (SP) (2019). https://bityli.com/HAEBCtEkv. Accessed 31 Aug 2022

  24. Srinivas, N., Deb, K.: Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol. Comput. 2(3), 221–248 (1994). https://doi.org/10.1162/evco.1994.2.3.221

    Article  Google Scholar 

  25. Subramanian, A., Drummond, L., Bentes, C., Ochi, L., Farias, R.: A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Comput. Oper. Res. 37(11), 1899–1911 (2010). https://doi.org/10.1016/j.cor.2009.10.011

    Article  MATH  Google Scholar 

  26. SUS: Série parâmetros sus - volume 1 - caderno 1 - republicado 1 (2017). https://bit.ly/41tfmjD

  27. SUS: Cnes - recursos físicos (2019). http://bit.ly/40BKfm9. Accessed 28 Mar 2023

  28. WHO: Cancer, February 2022. https://www.who.int/news-room/fact-sheets/detail/cancer. Accessed 18 Mar 2023

Download references

Acknowledgments

The authors are grateful for the support provided by the Universidade Federal de Ouro Preto, and by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES, Finance Code 001), Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, grants 428817/2018-1 and 303266/2019-8), and Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG, grant PPM CEX 676/17).

Author information

Authors and Affiliations

  1. Departamento de Computação, Universidade Federal de Ouro Preto (UFOP), Campus Universitário, Morro do Cruzeiro, Ouro Preto, MG, 35.400-000, Brazil

    Thiago Giachetto de Araujo, Puca Huachi Vaz Penna & Marcone Jamilson Freitas Souza

Authors
  1. Thiago Giachetto de Araujo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Puca Huachi Vaz Penna
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marcone Jamilson Freitas Souza
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thiago Giachetto de Araujo .

Editor information

Editors and Affiliations

  1. Systems Research Institute of the Polish Academy of Sciences, Warsaw, Poland

    Leszek Rutkowski

  2. Częstochowa University of Technology, Częstochowa, Poland

    Rafał Scherer

  3. Częstochowa University of Technology, Częstochowa, Poland

    Marcin Korytkowski

  4. University of Alberta, Edmonton, AB, Canada

    Witold Pedrycz

  5. AGH University of Krakow, Kraków, Poland

    Ryszard Tadeusiewicz

  6. University of Louisville, Louisville, KY, USA

    Jacek M. Zurada

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

de Araujo, T.G., Penna, P.H.V., Souza, M.J.F. (2023). An Hybrid NSGA-II Algorithm for the Bi-objective Mobile Mammography Unit Routing Problem. In: Rutkowski, L., Scherer, R., Korytkowski, M., Pedrycz, W., Tadeusiewicz, R., Zurada, J.M. (eds) Artificial Intelligence and Soft Computing. ICAISC 2023. Lecture Notes in Computer Science(), vol 14125. Springer, Cham. https://doi.org/10.1007/978-3-031-42505-9_29

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-42505-9_29

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-42504-2

  • Online ISBN: 978-3-031-42505-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation