Simulated Annealing aplicado ao problema do empacotamento unidimensional
Resumo
O problema do empacotamento unidimensional (PEU) e um problema de otimização combinatória NP-difícil, e com varias aplicações no mundo real. Existem varios métodos e formas presentes na literatura para encontrar soluções para este tipo de problema. Neste trabalho, foi desenvolvida uma metaheurística Simulated Annealig para a resolução do PEU, e a utilizada do solver matematico Gurobi para a obtenção de soluções otimas. Experimentos computacionais foram conduzidos, e o SA proposto mostrou-se robusto ao resolver instancias da literatura.
Palavras-chave:
NP-Dificil, PEU, otimização
Referências
Alvim, A. C., Ribeiro, C. C., Glover, F., and Aloise, D. J. (2004). A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 10(2):205–229.
Baker, B. S. (1985). A new proof for the first-fit decreasing bin-packing algorithm. Journal of Algorithms, 6:49–70.
D´osa, G. (2007). The tight bound of first fit decreasing bin-packing algorithm is ffd (i) 11/9opt (i)+ 6/9. In International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, pages 1–11. Springer.
Dowsland, K. A. (1993). Some experiments with simulated annealing techniques for packing problems. European Journal of Operational Research, 68:389–399.
Hall, N. G., Ghosh, S., Kankey, R. D., Narasimhan, S., and Rhee, W. T. (1988). Bin packing problems in one dimension: heuristic solutions and confidence intervals. Computers & operations research, 15:171–177.
Karmarkar, N. and Karp, R. M. (1982). An efficient approximation scheme for the onedimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 312–320. IEEE.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598):671–680.
Optimization, G. (2018). Inc.,“gurobi optimizer reference manual,” 2015.
Rao, R. and Iyengar, S. (1994). Bin-packing by simulated annealing. Computers & Mathematics with Applications, 27(5):71–82.
Baker, B. S. (1985). A new proof for the first-fit decreasing bin-packing algorithm. Journal of Algorithms, 6:49–70.
D´osa, G. (2007). The tight bound of first fit decreasing bin-packing algorithm is ffd (i) 11/9opt (i)+ 6/9. In International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, pages 1–11. Springer.
Dowsland, K. A. (1993). Some experiments with simulated annealing techniques for packing problems. European Journal of Operational Research, 68:389–399.
Hall, N. G., Ghosh, S., Kankey, R. D., Narasimhan, S., and Rhee, W. T. (1988). Bin packing problems in one dimension: heuristic solutions and confidence intervals. Computers & operations research, 15:171–177.
Karmarkar, N. and Karp, R. M. (1982). An efficient approximation scheme for the onedimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 312–320. IEEE.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598):671–680.
Optimization, G. (2018). Inc.,“gurobi optimizer reference manual,” 2015.
Rao, R. and Iyengar, S. (1994). Bin-packing by simulated annealing. Computers & Mathematics with Applications, 27(5):71–82.
Publicado
25/09/2019
Como Citar
LIMA, José Guilherme P.; SILVA, Phillipe I. M.; DOS SANTOS, Walberto M.; CLÍMACO, Glaubos.
Simulated Annealing aplicado ao problema do empacotamento unidimensional. In: ESCOLA REGIONAL DE COMPUTAÇÃO DO CEARÁ, MARANHÃO E PIAUÍ (ERCEMAPI), 7. , 2019, São Luís/MA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 25-31.
