SOLUTION OF BIN PACKING PROBLEM WITH WEIGHTED ANNEALING METHOD BASED ON LOWER BOUND

Year 2018, , 549 - 567, 27.12.2018

Neriman İnak Sezai Tokat , Kenan Karagül

https://doi.org/10.30798/makuiibf.414467

Cited By: 2

Abstract

In this
study, a heuristic solution method is presented for one dimensional bin packing
problem. A heuristic initial solution algorithm based on the lower bound is
proposed to create the initial solution. In addition to the proposed
heuristics, other placement algorithms in the literature are discussed, and the
results obtained are compared with the results obtained in the literature. Swap
algorithms together with weighted annealing method are applied to the results
of the initial solutions, and the number of bins used are minimized. The test
sets in the literature are solved, the resolution times and the results
obtained are compared with the best known solution in the literature and other
developed methods. It has been observed that the heuristic method proposed in
the literature compares with the solution in a shorter time. It has also been
observed that in 2 samples of the solved test set a better solution is obtained
than the best known solution in the literature.

Keywords

Bin Packing Problem, Weighted Annealing

ALT SINIR TEMELİNE DAYALI AĞIRLIKLI TAVLAMA YÖNTEMİ İLE KUTULAMA PROBLEMİNİN ÇÖZÜMÜ

Abstract

Bu
çalışmada bir boyutlu kutulama problemi için melez yeni bir sezgisel çözüm
yöntemi sunulmuştur. Önerilen yaklaşımda, başlangıç çözümü oluşturmak için alt
sınıra dayalı sezgisel bir başlangıç çözüm algoritması önerilmiştir. Önerilen
sezgisel ile birlikte literatürde yer alan diğer yerleştirme algoritmaları ele
alınmış, elde edilen sonuçlar literatürde ulaşılan sonuçlarla karşılaştırılmıştır.
Başlangıç çözümü sonrası elde edilen çözüme ağırlıklı tavlama yöntemiyle
birlikte yer değiştirme algoritmaları uygulanmış ve kullanılan kutu sayısını
minimize etmek amaçlanmıştır. Literatürde yer alan test kümeleri çözülmüş,
çözüm süreleri ve elde edilen sonuçlar bilinen en iyi sonuçlarla ve
geliştirilen diğer yöntemlerle karşılaştırılmıştır. Literatür ile yapılan
karşılaştırmalarda önerilen sezgisel yöntemin daha kısa sürede çözüme ulaştığı
gözlemlenmiştir. Ayrıca çözülen test kümesinin 2 örneğinde literatürdeki en iyi
bilinen çözümden daha iyi bir çözüm elde edildiği gözlemlenmiştir.

Keywords

Kutulama Problemi, Ağırlıklı Tavlama

References

• Alvim, A. C. E., Ribeiro, C. C., Glover, F., & Aloise, D. . (2001). A hybrid improvement heuristic for the one-dimensional bin packing problem. In In Extended Abstracts of the 4th Metaheuristics International Conference (pp. 63–68).
• Alvim, A. C. F., Glover, F., & Aloise, J. J. (2004). A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 10, 205–229.
• Aydın, İ.(2013). Tavlama Benzetimi Algoritması (Simulated Annealing), Fırat Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Anabilim Dalı.
• Beasley, J. . (1990). OR-Library. Retrieved April 6, 2016, from http://people.brunel.ac.uk/~mastjjb/jeb/orlib/binpackinfo.html
• Beisiegel, B., Kallrath, J., Kochetov, Y., & Rudnev, A. (2005). Simulated annealing based algorithm for the 2D bin packing problem with impurities. Operations Research Proceedings 2005.
• Bhatia, A. K., & Basu, S. K. (2004). Packing bins using multi-chromosomal genetic representation and better fit heuristic. Lecture Notes in Computer Science, 181–186.
• Brandão, F. (n.d.). Arc-flow Formulation (w/ graph compression) Results. Retrieved from http://www.dcc.fc.up.pt/~fdabrandao/
• Caprara, A., & Pferschy, U. (2004). Worst-case analysis of the subset sum algorithm for bin packing. Operations Research Letters, 32(2), 159–166.
• Caprara, A., & Pferschy, U. (2005). Modified subset sum heuristics for bin packing. Information Processing Letters, 96(1), 18–23.
• Carvelho, J. M. V. (1999). Exact solutions of bin-packing problems using column generation and branch and bound. Annals of Operations Research, 86, 629 – 659.
• Coffman, Garey, M. ., & Johnson, D. . (1997). Approximation algorithms for bin packing problems: A survey. PWS Publishing, Boston, Massachusetts.
• Dantzig, G. B., & Philip, W. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101–111.
• Delorme, M., Iori, M., & Martello, S. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255(1).
• Eilon, S., & Christofides, N. (1971). The loading problem. Manag Ement Science, 259–268.
• Elidan, G., Ninio, M., & Friedman, N. (2002). Data perturbation for escaping local maxima in learning. AAAI/IAAI, 132–139.
• Ensari, M. (2007). Konteynır yükleme problemine sezgisel bir yaklaşım. Gazi Üniversitesi.
• Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2, 5–30.
• Fekete, S. P., & Schepers, J. (2001). New classes of fast lower bounds for bin packing problems. Mathematical Programming, 91(1), 11–31.
• Fleszar, K., & Hindi, K. S. (2002). New heuristics for one-dimensional bin-packing. Computers & Operations Research, 29(7), 821–839.
• Ford, L. R. J., & Fulkerson, D. R. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849–859.
• Garey, M. R., & Johnson, D. S. (1979). A guide to the theory of NP-completeness. Computers and Intractability. W.H. Freeman and Company, San Francisco, California.
• Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849–859.
• Gourgand, M., Grangeon, N., & Klement, N. (2014). Activities planning and resource assignmenton multi-place hospital system: Exactand approach methods adapted from the bin packing problem. In 7th International Conference on Health Informatics, Angers, France (pp. 117–124).
• Gourgand, M., Grangeon, N., & Klement, N. (2014). An analogy between bin packing problem and permutation problem: A new encoding scheme. IFIP International Conference on Advances in Production Management Systems, 572–579.
• Hansen, P., & Mladenović, N. (1999). An introduction to variable neighborhood search (Metaheuris). Doudrecht,.
• Hashim, N. A., Zulkipli, F., Januri, S. S., & Shariff, S. S. R. (2014). An alternative heuristics for bin packing problem. In Proceedings of the International Conference on Industrial Engine (p. 1560).
• Ho, J. C., & Gupta, J. N. D. (1999). A new heuristic algorithm for the one-dimensional bin-packing problem. Production Planning and Control, 10(6), 598–603.
• Hübscher, R., & Glover, F. (1994). Applying tabu search with influential diversification to multiprocessor scheduling. Computers & Operations Research, 21(8), 877–884.
• Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974). Worst-case performance bounds for simple one-dimensional packing algorithm. SIAM J Ournal of Computing, 3, 299–326.
• Kantorovich, L. V. (1960). Mathematical methods of organizing and planning production. Management Science, English Translation of a 1939 Paper Written in Russian, 6(4), 366–422.
• Kirkpatrick, S., L., Gelatt, C.D., Vecchi, M.P. (1983). Optimization by Simulated Annealing, Science, New Series, 220, 671-680.
• Loh, K.-H., Golden, B., & Wasil, E. (2006). Weighted annealing heuristics For solving bin packing and other combinatorial optimization problems: Concepts, algorithms, and computational results. University of Maryland.
• Martello, S., Pisinger, D., & Vigo, D. (2000). The three-dimensional bin packing problem. Operations Research.
• Martello, S., & Toth, P. (1987). Algorithms for knapsack problems. North-Holland Mathematics Studies, 132, 213–257.Ninio, M., & Schneider, J. J. (2004). Weight annealing. Physica A.
• Oliveira, J. . (2003). ESICUP. Retrieved April 20, 2016, from https://paginas.fe.up.pt/~esicup/datasets
• Ozcan, S. O., Dokeroglu, T., Cosar, A., & Yazici, A. (2016). A novel grouping genetic algorithm for the one-dimensional bin packing problem on GPU. In Computer and Information Sciences (pp. 52–60).
• Poli, R., Woodward, J., & Burke, E. K. (2007). A histogram-matching approach to the evolution of bin-packing strategies. In IEEE Congress on Evolutionary Computation 2007 (CEC 2007) (pp. 3500–3507).
• Rohlfshagen, P., & Bullinaria, J. (2007). A genetic algorithm with exon shuffling crossover for hard bin packing problems. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (pp. 1365–1371).
• Scholl, A., Klein, R., & Jürgens, C. (1997). BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers & Operations Research, 24(7), 627–645.
• Schwerin, P., & Wäscher, G. (1999). A new lower bound for the bin packing problem and its integration into MTP. Pesquisa Operational, 19, 111–129.Singh, A., & Gupta, A. K. (2007). Two heuristics for the one-dimensional bin-packing problem. OR Spectrum, 29(4).
• Vanderbeck, F. (1999). Computational study of a column generation algorithm for bin packing and cutting stock problems. Maths Programming, 86, 565 – 594.