Estudo experimental dos pontos de aleatoriedade como estratégia para melhoria de ótimos locais em metaheurística

Autores

  • Flávio Henrique Batista de Souza Universidade Federal de Minas Gerais (UFMG), Belo Horizonte, Minas Gerais, MG https://orcid.org/0000-0002-7157-1535
  • Diva de Souza e Silva Rodrigues Centro Universitário de Belo Horizonte (UNIBH), Belo Horizonte, Minas Gerais, MG
  • Vladimir Alexei Rodrigues Rocha Universidade Federal de Minas Gerais (UFMG), Belo Horizonte, Minas Gerais, MG
  • Renata Duarte Mellim Centro Universitário de Belo Horizonte (UNIBH), Belo Horizonte, Minas Gerais, MG
  • Lucas Alberto Queiroz Marcatti Centro Universitário de Belo Horizonte (UNIBH), Belo Horizonte, Minas Gerais, MG
  • Daniela Ferreira dos Santos Centro Universitário de Belo Horizonte (UNIBH), Belo Horizonte, Minas Gerais, MG
  • Ana Gabriela Furbino Ferreira Universidade Federal de Minas Gerais (UFMG), Belo Horizonte, Minas Gerais, MG

DOI:

https://doi.org/10.14488/1676-1901.v21i4.4398

Palavras-chave:

Metaheurística, GRASP, GRASP*, Roteamento, Minas a Céu Aberto

Resumo

Algoritmos de metaheurísticasão largamente empregados na otimizaçãode problemasem diferentesáreas.Diversos estudos têm, por exemplo, aplicado esse método naotimizaçãoda logística de caminhões em mina a céu aberto.Esta pesquisa abordauma análise experimental da metaheurística GRASP* por meio do deslocamento do ponto de aleatoriedade, com métricas ainda não exploradas na literatura, a fim de severificar o desempenhodo algoritmo em relaçãoarespostassubótimas. Após a análise do comportamento do algoritmo com a alteração dos pontos de aleatoriedade, foi realizadoum estudode seu desempenhoem relação aquantidade dos ciclos de processamento. Basesde dadosjá avaliadas em outras pesquisas, somadas a 10 outras bases de referência presentes naliteratura,foram empregadasdurante aanálise exploratória do método GRASP*.Alémdisso, os resultadosobtidos peloalgoritmo GRASP* foramcomparadoscomaheurística construtiva NN*. Os resultados do presenteestudodemonstram que as alterações aplicadas aométodo GRASP* proporcionaramganhos de mais de 24% em desempenho para determinados valoresde deslocamento de pontos de aleatoriedadee ganhos de mais de 10% com a variação de números de ciclos.Talestrutura pode ser implementadapara a otimização de estratégias logísticasque podem conduzir negócios de milhões de dólares, como a mineração a céu aberto.

Downloads

Não há dados estatísticos.

Referências

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.

Downloads

Publicado

25-03-2022

Como Citar

Souza, F. H. B. de, Rodrigues, D. de S. e S., Rocha, V. A. R., Mellim, R. D., Marcatti, L. A. Q., Santos, D. F. dos, & Ferreira, A. G. F. (2022). Estudo experimental dos pontos de aleatoriedade como estratégia para melhoria de ótimos locais em metaheurística. Revista Produção Online, 21(4), 2185–2208. https://doi.org/10.14488/1676-1901.v21i4.4398

Edição

v. 21 n. 4 (2021)

Seção

Artigos

Licença

Copyright (c) 2022 Revista Produção Online

Creative Commons License
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.

A Revista se reserva no direito de efetuar, no artigo publicado, alterações de ordem normativa, ortográfica e gramatical, com vistas a manter o padrão culto da língua, respeitando, porém, o estilo dos autores.

A obra publicada é de inteira responsabilidade do(s) autor(es), cabendo à Revista Produção Online apenas a avaliação da obra, na qualidade de veículo de publicação científica. A Revista Produção Online não se responsabiliza por eventuais violações à Lei nº 9.610/1998, Lei de Direito Autoral.

A revista Produção Online permite que o autor detenha o copyright dos artigos aceitos para publicação, sem restrições.

Esta obra está licenciada sob uma Licença Creative Commons.