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

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

Abstract


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.

References


[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.




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

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia