Production
https://prod.org.br/article/doi/10.1590/0103-6513.20210031
Production
Thematic Section - Future of Energy-efficient Operations and Production Systems

A metaheuristic to support the distribution of COVID-19 vaccines

Augusto José da Silva Rodrigues; Gabriel Lopes Lima

Downloads: 6
Views: 539

Abstract

Paper aims: The aim is to develop a vaccine distribution routing model (VDRM) in order to support governments to mitigate the pandemic caused by COVID-19.

Originality: As far as we know, no metaheuristics has been developed for vaccine distribution, and specifically, to support the Brazilian government.

Research method: A metaheuristic is developed based on the combination and adaptation of GRASP (Greedy Randomized Adaptive Search Procedure) with VND (Variable Neighborhood Descent), considering different refinement operators. Finally, as a way of validating the model, a numerical application in the state of Pernambuco (Brazil) was performed.

Main findings: Metaheuristic proved to be effective for developing adequate planning for the allocation of ampoules with vaccines to combat COVID-19. Effective analysis was obtained in the evaluation of the proposed algorithm, both in terms of computational effort and the quality of the final solution. An efficiency of approximately 75% was obtained in relation to the current distribution procedure adopted by the state of Pernambuco.

Implications for theory and practice: To mitigate disease, adequate logistics for transporting and distributing vaccines is essential, especially in emergency situations to face pandemic crises. Thus, the developed metaheuristic can support governments and companies in any situation demanded, making the decision of how the distribution of the ampoules will be more agile.

Keywords

COVID-19, Vehicle routing, GRASP, VND

References

Bell, J. E., & McMullen, P. R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics, 18(1), 41-48. http://dx.doi.org/10.1016/j.aei.2004.07.001.

Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313. http://dx.doi.org/10.1016/j.cie.2015.12.007.

Brasil. Ministério da Saúde. (2017). Manual de Rede de Frio do Programa Nacional de Imunizações. Retrieved in 2021, April 30, from https://portalarquivos2.saude.gov.br/images/pdf/2017/dezembro/15/rede_frio_2017_web_VF.pdf

Campbell, A. M., & Wilson, J. H. (2014). Forty years of periodic vehicle routing. Networks, 63(1), 2-15. http://dx.doi.org/10.1002/net.21527.

Cordeau, J. F., Gendreau, M., Laporte, G., Potvin, J. Y., & Semet, F. (2002). A guide to vehicle routing heuristics. The Journal of the Operational Research Society, 53(5), 512-522. http://dx.doi.org/10.1057/palgrave.jors.2601319.

Cravo, G. L., & Amaral, A. R. (2019). A GRASP algorithm for solving large-scale single row facility layout problems. Computers & Operations Research, 106, 49-61. http://dx.doi.org/10.1016/j.cor.2019.02.009.

Den Besten, M., & Stützle, T. (2001). Neighborhoods revisited: an experimental investigation into the effectiveness of variable neighborhood descent for scheduling. In Proceedings of the MIC’2001–4th Metaheuristics International Conference (pp. 545-549). Porto, Portugal.

El-Sherbeny, N. A. (2010). Vehicle routing with time windows: an overview of exact, heuristic and metaheuristic methods. Journal of King Saud University-Science, 22(3), 123-131. http://dx.doi.org/10.1016/j.jksus.2010.03.002.

Feo, T. A., & Resende, M. G. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8(2), 67-71. http://dx.doi.org/10.1016/0167-6377(89)90002-3.

Feo, T. A., & Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2), 109-133. http://dx.doi.org/10.1007/BF01096763.

Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124. http://dx.doi.org/10.1002/net.3230110205.

Gendreau, M., & Tarantilis, C. D. (2010). Solving large-scale vehicle routing problems with time windows: the state-of-the-art. Montreal: Cirrelt.

Hansen, P., Mladenović, N., Brimberg, J., & Pérez, J. A. M. (2019). Variable neighborhood search. In M. Gendreau & J. Y. Potvin (Eds.), Handbook of metaheuristics (pp. 57-97). Cham: Springer. http://dx.doi.org/10.1007/978-3-319-91086-4_3.

Hansen, P., Mladenović, N., Todosijević, R., & Hanafi, S. (2017). Variable neighborhood search: basics and variants. EURO Journal on Computational Optimization, 5(3), 423-454. http://dx.doi.org/10.1007/s13675-016-0075-x.

Instituto Brasileiro de Geografia e Estatistica – IBGE. (2019). IBGE MAPS portal. Retrieved in 2021, April 12, from https://portaldemapas.ibge.gov.br/portal.php#homepage

Jabal-Ameli, M. S., Aryanezhad, M. B., & Ghaffari-Nasab, N. (2011). A variable neighborhood descent based heuristic to solve the capacitated location-routing problem. International Journal of Industrial Engineering Computations, 2(1), 141-154. http://dx.doi.org/10.5267/j.ijiec.2010.06.003.

Koirala, A., Joo, Y. J., Khatami, A., Chiu, C., & Britton, P. N. (2020). Vaccines for COVID-19: The current state of play. Paediatric Respiratory Reviews, 35, 43-49. http://dx.doi.org/10.1016/j.prrv.2020.06.010. PMid:32653463.

Kulkarni, R. V., & Bhave, P. R. (1985). Integer programming formulations of vehicle routing problems. European Journal of Operational Research, 20(1), 58-67. http://dx.doi.org/10.1016/0377-2217(85)90284-X.

Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. http://dx.doi.org/10.1016/0377-2217(92)90192-C.

Lara, M. A. (2021, July 5). Saiba como é realizada a distribuição da vacina Covid-19 para os estados. Brasília: Ministério da Saúde. Retrieved in 2021, April 12, from https://www.gov.br/saude/pt-br/assuntos/noticias/saiba-como-e-realizada-a-distribuicao-da-vacina-covid-19-para-os-estados

Lima, C. D. R., Goldbarg, M. C., & Goldbarg, E. F. G. (2004). A memetic algorithm for the heterogeneous fleet vehicle routing problem. Electronic Notes in Discrete Mathematics, 18, 171-176. http://dx.doi.org/10.1016/j.endm.2004.06.027.

Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. Y. (2014). Survey of green vehicle routing problem: past and future trends. Expert Systems with Applications, 41(4), 1118-1138. http://dx.doi.org/10.1016/j.eswa.2013.07.107.

López-Sánchez, A. D., Sánchez-Oro, J., & Hernández-Díaz, A. G. (2019). GRASP and VNS for solving the p-next center problem. Computers & Operations Research, 104, 295-303. http://dx.doi.org/10.1016/j.cor.2018.12.017.

Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097-1100. http://dx.doi.org/10.1016/S0305-0548(97)00031-2.

Moghdani, R., Salimifard, K., Demir, E., & Benyettou, A. (2020). The green vehicle routing problem: A systematic literature review. Journal of Cleaner Production, 123691. http://dx.doi.org/10.1016/j.jclepro.2020.123691.

Mohammed, M. A., Ghani, M. K. A., Hamed, R. I., Mostafa, S. A., Ibrahim, D. A., Jameel, H. K., & Alallah, A. H. (2017). Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution. Journal of Computational Science, 21, 232-240. http://dx.doi.org/10.1016/j.jocs.2017.04.012.

Montoya-Torres, J. R., Franco, J. L., Isaza, S. N., Jiménez, H. F., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115-129. http://dx.doi.org/10.1016/j.cie.2014.10.029.

Pernambuco. Governo do Estado. Secretaria da Saúde. (2021, July 7). Governo de Pernambuco conclui distribuição de mais 110.800 doses de vacina a todos os municípios. Retrieved in 2021, April 12, from https://www.pecontracoronavirus.pe.gov.br/governo-de-pernambuco-conclui-distribuicao-de-mais-110-800-doses-de-vacina-a-todos-os-municipios/

Petroianu, L. P. G., Zabinskya, Z. B., Zameer, M., Chu, Y., Muteia, M. M., Resende, M. G. C., Coelho, A. L., Wei, J., Purty, T., Draiva, A., & Lopes, A. (2020). A light-touch routing optimization tool (RoOT) for vaccine and medical supply distribution in Mozambique. International transactions in operational research : a journal of The International Federation of Operational Research Societies, 28(5), 2334-2358. http://dx.doi.org/10.1111/itor.12867. PMid:33883827.

QGIS. (2021, April 12). A Free and Open Source Geographic Information System. Retrieved in 2021, April 12, from https://www.qgis.org/en/site/index.html

Rayward-Smith, V. J., Osman, I. H., Reeves, C. R., & Smith, G. D. (1996). Modern heuristic search methods. Hoboken: Wiley.

Renaud, J., Laporte, G., & Boctor, F. F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers & Operations Research, 23(3), 229-235. http://dx.doi.org/10.1016/0305-0548(95)O0026-P.

Resende, M. G., & Ribeiro, C. C. (2010). Greedy randomized adaptive search procedures: advances, hybridizations, and applications. In M. Gendreau & J. Y. Potvin (Eds.),Handbook of metaheuristics (pp. 283-319). Boston, MA: Springer. http://dx.doi.org/10.1007/978-1-4419-1665-5_10.

Resende, M. G., & Ribeiro, C. C. (2019). Greedy randomized adaptive search procedures: advances and extensions. In M. Gendreau & J. Y. Potvin (Eds.),Handbook of metaheuristics (pp. 169-220). Cham: Springer. http://dx.doi.org/10.1007/978-3-319-91086-4_6.

Ribeiro, M. H., Plastino, A., & Martins, S. L. (2006). Hybridization of GRASP metaheuristic with data mining techniques. Journal of Mathematical Modelling and Algorithms, 5(1), 23-41. http://dx.doi.org/10.1007/s10852-005-9030-1.

Sohrabi, S., Ziarati, K., & Keshtkaran, M. (2020). A greedy randomized adaptive search procedure for the orienteering problem with hotel selection. European Journal of Operational Research, 283(2), 426-440. http://dx.doi.org/10.1016/j.ejor.2019.11.010.

Souza, M. J. F. (2011). Inteligência Computacional para Otimização. Universidade Federal de Ouro Preto. Retrieved in 2021, April 12, from http://www.decom.ufop.br/prof/marcone/Disciplinas/InteligenciaComputacional/InteligenciaComputacional.pdf

World Health Organization – WHO. (2021). WHO Coronavirus (COVID-19) Dashboard. Retrieved in 2021, April 12, from https://covid19.who.int/

Xiong, J., Lipsitz, O., Nasri, F., Lui, L. M. W., Gill, H., Phan, L., Chen-Li, D., Iacobucci, M., Ho, R., Majeed, A., & McIntyre, R. S. (2020). Impact of COVID-19 pandemic on mental health in the general population: a systematic review. Journal of Affective Disorders, 277, 55-64. http://dx.doi.org/10.1016/j.jad.2020.08.001. PMid:32799105.

Yang, Y., Bidkhori, H., & Rajgopal, J. (2021). Optimizing vaccine distribution networks in low and middle-income countries. Omega, 99, 102197. http://dx.doi.org/10.1016/j.omega.2020.102197.
 


Submitted date:
04/30/2021

Accepted date:
09/17/2021

616041ffa953957b6e4740a4 production Articles
Links & Downloads

Production

Share this page
Page Sections