Uma Aplicação da Meta-heurística Híbrida Simulated Annealing-Iterated Local Search ao Problema de Fluxo Multiproduto sob o Espaço Capacitado
DOI:
https://doi.org/10.5540/tema.2008.09.01.0165Abstract
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.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.