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

Política para Periódicos de Acesso Livre


Autores que publicam nesta revista concordam com os seguintes termos:
  1. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
  2. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
  3. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
  4. Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
 
Propriedade intelectual

Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.