Simulated Annealing Applied to One-Dimensional Packaging Problem
Abstract
The one-dimension bin packing problem (PEU) is an NP-hard combinatorial optimization problem, with several applications in the real world. There are several methods and forms present in the literature to find solutions to this type of problem. In this paper, a Simulated Annealing metaheuristic was developed for the resolution of the PEU, and mathematical solver Gurobi was used to obtain optimal solutions. Computational experiments were conducted, and the proposed SA proved to be robust in solving instances from the literature
Keywords:
NP-Hard, PEU, optimization
References
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.
Published
2019-09-25
How to Cite
LIMA, José Guilherme P.; SILVA, Phillipe I. M.; DOS SANTOS, Walberto M.; CLÍMACO, Glaubos.
Simulated Annealing Applied to One-Dimensional Packaging Problem. In: REGIONAL SCHOOL ON COMPUTING OF CEARÁ, MARANHÃO, AND PIAUÍ (ERCEMAPI), 7. , 2019, São Luís/MA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 25-31.
