Uma Aplicação da Meta-heurística Híbrida Simulated Annealing-Iterated Local Search ao Problema de Fluxo Multiproduto sob o Espaço Capacitado

Autores

  • C.A. Silva
  • S.R. de Souza

DOI:

https://doi.org/10.5540/tema.2008.09.01.0165

Resumo

Problemas de fluxo multiproduto possuem uma larga variedade de aplicações, sobretudo nas áreas de sistemas de transporte e telecomunicações. Devido à alta complexidade combinatorial dessa classe de problemas, métodos exatos apresentam dificuldades na tentativa de solucioná-los. Este fato motiva a utilização de técnicas heurísticas para o estudo do problema de fluxo multiproduto. Neste trabalho, é proposta uma aplicação das meta-heurísticas Simulated Annealing eIterated Local Search para resolver o problema de fluxo multiproduto inteiro capacitado.O objetivo é determinar o fluxo dos produtos pelos arcos da rede ao menor custo possível, respeitando-se as restrições de conservação de fluxo e capacidade. O espaço de restrição de capacidade será utilizado como espaço de busca para ameta-heurística híbrida proposta, penalizando-se, através de uma relaxação, a restrição de conservação de fluxo. Os resultados mostram soluções obtidas em tempo computacional aceitável e de boa qualidade.

Referências

[1] F.P. Alvelos, “Branch-and-Price and Multicommodity Flows”, Tese de Doutorado, EPS, Universidade do Minho, Portugal, 2005.

J.C. Becceneri, “Meta-heurísticas e otimização - curso de verão”, Grupo de Pesquisa Operacional, Laboratório Associado de Computação e Matemática Aplicada (LAC), pp. 8, INPE, 2007.

L.S. Buriol, “Roteamento do Tráfego na Internet: Algoritmos para Projeto e Operação de Redes com Protocolo OSPF”, Tese de Doutorado,FEEC/UNICAMP, SP, 2003.

J. Castro, Solving difficult multicommodity problems with a specialized interior-point algorithm, Annals of Operations Research, 124 (2003), 35-48.

D.R. Fulkerson, L.R. Ford, “Flows in Networks”, Princeton University Press, NJ, 1962.

T.C. Hu, Multicommodity network flows, Operations Research, 11 (1963), 344- 360.

Kirkpatrick Jr., C.S. Gelatt, M. Vecchi, Optimization by simulated annealing,

Decision Science, 220, No. 4598 (1983), 498-516.

H.R. Lourenço, O. Martin, T. Stuetzle, Iterated local search. In “The Handbook

in Metaheuristics” (F. Glover, G. Kochenberger, eds.), pp. 321–353, Kluwer Academic Publishers, 2002.

R.L. Milidiu, A.A. Pessoa, V. Braconi, E.S. Laber, P.A. Rey, Um algoritmo grasp para o problema de transporte de derivados de petróleo em oleodutos, em “XXXIII Simp´osio Brasileiro de Pesquisa Operacional”, pp. 237–246, SOBRAPO, 2001.

M.A. Santos, S. Bocanegra, F. Campos, Uma proposta de solução para o problema não linear de fluxo multiproduto utilizando pontos interiores, em “Semana de Ciência da Computação”, Lavras, MG, Vol. 1, pp. 69–73, UFL, 2000.

G.L. Schultz, R.R. Meyer, An interior point method for block angular optimization, SIAM Journal on Optmization, 42, No. 4 (1991), 583-602.

C.A. Silva, S.R. de Souza, Uma aplicação da metaheur´ıstica iterated local search ao problema de fluxo multiproduto inteiro sob o espaço de restrição de capacidade, em “XXXIX Simpósio Brasileiro de Pesquisa Operacional”, SOBRAPO, 2007.

Downloads

Publicado

2008-06-01

Como Citar

Silva, C., & de Souza, S. (2008). Uma Aplicação da Meta-heurística Híbrida Simulated Annealing-Iterated Local Search ao Problema de Fluxo Multiproduto sob o Espaço Capacitado. Trends in Computational and Applied Mathematics, 9(1), 165–174. https://doi.org/10.5540/tema.2008.09.01.0165

Edição

v. 9 n. 1 (2008)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.