Experimental research through randomness points as metaheuristics suboptimal local responses improvement
DOI:
https://doi.org/10.14488/1676-1901.v21i4.4398Keywords:
Metaheuristics, GRASP, GRASP*, Routing, Open-pit minesAbstract
Metaheuristic algorithms are widely used in the optimization of problems in different areas. Several studies have, for example, applied this method to the optimization of truck logistics in open pit mining. This research approaches an experimental analysisof the GRASP* metaheuristic through the variationof the randomness point, with metrics not yet explored in the literature, in order to verify the performance of the algorithm in relation to suboptimal solutions. After the analysis of the algorithmconvergencywith the changes on the randomness points, a study of its performance in relation to the amount of processing cycles was performed. Databases alreadyevaluated in other studies, added to 10 other reference databases present in the literature, were employed during the exploratory analysis of the GRASP* method. In addition, the results obtained by the GRASP* algorithm were compared with the NN* constructive heuristic. The results of this study demonstrate that the changes applied to the GRASP* method provided gains of more than 24% in performance for given values of randomness point and gains of more than 10% with varying numbers of cycles. Such a framework can be implemented for the optimization of logistical strategies that can drive million-dollarbusinesses, such asopen pit mining.
Downloads
References
ALOISE, D. J.;NORONHA, T. F.;MAIA, R. S.;BITTENCOURT, V. G. Heurísticas de colônia de formigas com path-relinking para o problema de otimização da alocação de sondas de produção terrestre–SPT. In: XXXIV SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 34.,Rio de Janeiro,2002.
ALVARENGA, G. B. Um Algoritmo Híbrido para os Problemas de Roteamento deVeículos Estático e Dinâmico com Janela deTempo.Tese de Doutorado.Universidade Federal de Minas Gerais,Belo Horizonte,2005,180 p.
ARROYO, J. E. C. Heurísticas e metaheurísticas para otimização combinatória multiobjetivo. Doutorado em Engenharia Elétrica (Tesede doutorado)-Faculdade de EngenhariaElétrica e de Computação da UniversidadeEstadual de Campinas,Campinas,2002.
CORMEN, T. Desmistificando algoritmos. 1ed. São Paulo: Elsevier Academic, 2015. 940p. ISBN 978-0-262-51880-2FEO, T. A.;RESENDE, M.G.C. GreedyRandomized Adaptive Search Procedures. Journal of Global Optimization, v. 6,p. 109-133. 1995.https://doi.org/10.1007/BF01096763
FESTA, P.;RESENDE, M. G. C. GRASP:basic components and enhancements. Telecommunication Systems, v. 46, n. 3, p. 253-271, 2011.https://doi.org/10.1007/s11235-010-9289-z
HART, J.P., SHOGAN, A.W. Semi-greedy heuristics: anempirical study. Operations Research Letters, v. 6, p.107–114, 1987.https://doi.org/10.1016/0167-6377(87)90021-6
LISBOA, A. C.;SOUZA, F. H. B.; RIBEIRO, C. M.;MAIA, C. A.;SALDANHA, R. R.;CASTRO, F. L. B.;VIEIRA, D. A. G. On Modelling and Simulating OpenPit Mine Through Stochastic Timed Petri Nets. IEEE Access,v. 7, p. 112821–112835, 2019. https://doi.org/10.1109/ACCESS.2019.2934718
LOSQUI, H. V. F.; SOUZA, F. H. B. Análise De Pontos De Aleatoriadade Como Estratégia Para Melhoria De Ótimos Locais Em Uma Heurística Construtiva.Revista Produção Online. Florianópolis, SC, v. 19, n. 3, p. 923-951, 2019.https://doi.org/10.14488/1676-1901.v19i3.3336
MARINAKIS, Y.; MARINAKI, M.; MATSATSINIS, N.A hybrid discrete artificial bee colony-GRASP algorithm for clustering. In: COMPUTERS & Industrial Engineering, 2009. International Conference onIEEE,p. 548-553, 2009.https://doi.org/10.1109/ICCIE.2009.5223810
MORAIS, T. G. M.; OLIVEIRA, J. P. F.; JÚNIOR, A. C. G.;GOMES, H. C. Análise da aplicação de Métodos Heurísticos na Resolução do Problema de Roteamento de Veículos com Frota Heterogênea. In: XL ENCONTRO NACIONAL DE ENGENHARIA DE PRODUÇÃO.Paraná,2020.https://doi.org/10.14488/ENEGEP2020_TN_STO_344_1771_40983
RESENDE, M. G. C.;RIBEIRO,C.C.Greedy randomized adaptive search procedures. Handbook of Metaheuristics.Kluwer Academic Publishers, p. 219-249, 2003.https://doi.org/10.1007/0-306-48056-5_8
RIBEIRO, C. C.Metaheuristics and applications.Monte Estoril, Portugal: Advanced School on Artificial Intelligence (Constraint Programming),1996.
SHUMAKER, B. P.;SINNOTT, R. W. Astronomical computing: 1. Computing under the open sky. 2. Virtuesof the haversine. Sky and telescope, v. 68, p. 158-159,1984.
SOUZA, F. H. B.;LISBOA, A. C.;MAIA, C. A.;SALDANHA, R. R. Randomization Control in Heuristics and Metaheuristics Applied to the Optimal Path Search in Open Pit Mines. In: SBPO –SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 49.,Blumenau,2017.
SOUZA, R. F. F. Planejamento da expansão de sistemas de distribuição usando a metaheurística de busca em vizinhança variável.2011. 106 f. Dissertação (mestrado) -Universidade Estadual Paulista, Faculdade de Engenharia de Ilha Solteira, 2011. Disponível em:http://hdl.handle.net/11449/87148.
SOUZA, F. H. B.;FERREIRA, N. C.;SOUZA, P.H. G.;MELLIM, R. D.;ROCHA, V. A. R. Análise e Aplicação de Heurísticas para Definição de Rotas com Solução Otimizada Aplicado em uma Indústria do Ramo Alimentício. In: CONGRESSO BRASILEIRO DE ENGENHARIA DE PRODUÇÃO, 40.,Ponta Grossa, 2019.
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Revista Produção Online
This work is licensed under a Creative Commons Attribution 4.0 International License.
The Journal reserves the right to make spelling and grammatical changes, aiming to keep a default language, respecting, however, the style of the authors.
The published work is responsibility of the (s) author (s), while the Revista Produção Online is only responsible for the evaluation of the paper. The Revista Produção Online is not responsible for any violations of Law No. 9.610 / 1998, the Copyright Act.
The journal allows the authors to keep the copyright of accepted articles, without restrictions
This work is licensed under a Creative Commons License .
