Neriman İNAK, Sezai TOKAT, Kenan KARAGÜL

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

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.

Anahtar Kelimeler:

Kutulama Problemi, Ağırlıklı Tavlama

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

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,

PDF

___

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.