Geodesic
Simulated annealing based algorithm for the rectangular bin packing problem with impurities
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 4, pp. 43-66

Voir la notice de l'article provenant de la source Math-Net.Ru

A two dimensional rectangular bin packing problem with impurities is considered. This problem generalizes the classical rectangular bin packing problem. It is NP-hard in strong sense. Encoding schemes for guillotine and non-guillotine cases of packing are proposed. To solve the problem a tailored simulated annealing algorithm based on the proposed encoding schemes has been developed. The initial solution is built by greedy heuristic. It allows the algorithm to start with low temperature. An unload procedure is performed when the temperature is changed. It unloads some bins by packing other bins more compactly. The experimental results show high efficiency of the new encoding schemes and low deviations from the optimum. Ill. 2, tab. 5, bibliogr. 11.
Keywords: bin packing, representation schemes, simulated annealing. 
@article{DA_2010_17_4_a3,
     author = {A. S. Rudnev},
     title = {Simulated annealing based algorithm for the rectangular bin packing problem with impurities},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {43--66},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_4_a3/}
}
TY  - JOUR
AU  - A. S. Rudnev
TI  - Simulated annealing based algorithm for the rectangular bin packing problem with impurities
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 43
EP  - 66
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_4_a3/
LA  - ru
ID  - DA_2010_17_4_a3
ER  - 
%0 Journal Article
%A A. S. Rudnev
%T Simulated annealing based algorithm for the rectangular bin packing problem with impurities
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 43-66
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_4_a3/
%G ru
%F DA_2010_17_4_a3
A. S. Rudnev. Simulated annealing based algorithm for the rectangular bin packing problem with impurities. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 4, pp. 43-66. http://geodesic.mathdoc.fr/item/DA_2010_17_4_a3/