ALT SINIR TEMELİNE DAYALI AĞIRLIKLI TAVLAMA YÖNTEMİ İLE KUTULAMA PROBLEMİNİN ÇÖZÜMÜ
Journal Title: Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi - Year 2018, Vol 5, Issue 3
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. EXTENDED SUMMARY Background The bin packing problem, which is a combinatorial optimization problem with some similarities with the classical knapsack problems, is defined in different forms such as stock-cutting, vehicle loading, air cargo loading, container loading, scheduling, knapsack problem depending on the application being discussed. The bin packing problem, which is the problem of how to best locate the objects with the least usable length, area or volume, is classified as one, two or three dimensional according to the number of dimensions used. Regardless of the size of the bin packing problem, the solution is a non-polynomial NP-hard problem. This problem is confronted in many areas such as logistics, textile, and computer science in real life. While there are exact solutions for small scale problems, it is not possible to find an exact solution for large scale problems. Heuristic methods such as genetic algorithms, simulated annealing, weighted simulated annealing, tabu search are the most used solution approaches in the literature to obtain optimal or near optimal solutions for large scale problems. Research Problem In this study, one-dimensional bin-packing problem is considered where it is aimed to place objects in a single dimension with a minimum length within a certain length in one dimensional bin packing problems. Methodology In this study, a new two-stage, heuristic and hybrid solution method is presented for one dimensional bin packing problem. A heuristic initial solution algorithm based on the lower bound is used to create the initial solution. As the second stage of the problem solution phase, weights were assigned to the elements together with the weighted annealing method and the initial solutions were rearranged using swapping operations. Along with the weighted annealing and swapping operations, fewer number of bins have been used than the total number of bins used for the initial solution. In this study, Swap (1,0), Swap (1,1) and Swap (1,2) algorithms are used as swapping operations. Literature Review For the one dimensional bin-packing problem, a similar two-stage solution method is used by Loh et al (2006) where the initial solutions are obtained by using first fit decreasing, a weighted annealing method is used with swapping operations whereas Swap(2,2) is also used. In our study, the point of origin is to show that better results in a shorter time could be obtained than the results given in Loh et al (2006). Results and Conclusions 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. In comparisons with Loh et al (2006), it has been observed that the proposed heuristic method achieves the solutions in a shorter time. In addition, two solutions of the solved test set yielded better solutions than the best known solution of Loh et al (2006). In this context, the analysis suggested that the proposed two-stage, heuristic and hybrid solution approach is a promising approach. As a further study, this method can be investigated for two-dimensional and three-dimensional bin packing problems. In addition, it may contribute to the development of a new perspective in the research studies on the solutions of combinatorial problems such as traveling salesman problem, knapsack problem, maximum satisfaction problem and vehicle routing problem.
Authors and Affiliations
Neriman İNAK, Sezai TOKAT, Kenan KARAGÜL
Keywords
Related Articles
- EP ID EP445428
- DOI 10.30798/makuiibf.414467
- Views 143
- Downloads 0
YÖNETİM KURULU ÇEŞİTLİLİĞİNİN FİRMA DEĞERİNE ETKİSİ: TÜRKİYE ÖRNEĞİ
ÖZ Geçtiğimiz son on yılda dünyanın önde gelen firmalarında meydana gelen finansal başarısızlıklar, kurumsal yönetim (kurumsal yönetişim) kavramına her zamankinden daha fazla önem verilmesine neden olmuştur. Yönetim kuru...
BATIK MALİYET, POTANSİYEL REKABET VE YARIŞILABİLİRLİK: DENİZYOLU TAŞIMACILIĞI PİYASASI ÖRNEĞİ
Yarışılabilir Piyasalar teorisi, bir piyasada az sayıda ve büyük hacimli firmaların piyasa etkinliği açısından dezavantaj oluşturmayabileceğini ileri sürmektedir. Yoğunlaşma ve ölçek ekonomilerini tekelci gücün kaynağı o...
YEREL PAZARLARDAKİ ÜRÜN ÇEŞİTLENDİRME İLE ULUSLARARASILAŞMA DERECESİ ARASINDAKİ İLİŞKİ: KURUMSAL YÖNETİŞİM MEKANİZMALARININ DÜZENLEYİCİ ETKİLERİ
Çalışmanın amacı, gelişmekte olan ülke kökenli çokuluslu şirketlerin uluslararasılaşma faaliyetlerini daha iyi anlamak ve tanımlamak amacıyla, ürün çeşitlendirme düzeyi ile uluslararasılaşma derecesi arasındaki ilişkiyi...
KÂR PAYI DAĞITIM POLİTİKALARININ FİRMA DEĞERİ ÜZERİNE ETKİSİ: BİST 30 ENDEKSİ ÜZERİNE BİR ARAŞTIRMA
Günümüzde işletmelerin nihai amacı sadece kâr elde etmek değil, aynı zamanda firma değerini maksimum yapmaktır. Firma değeri maksimizasyonu, hem işletmenin hem de işletme ile ilişkisi bulunan kişi ve kuruluşların menfaat...
FİNANSAL RİSKLER İLE FİRMA DEĞERİ ARASINDAKİ İLİŞKİNİN BELİRLENMESİ: BORSA İSTANBUL FİRMALARI ÜZERİNE BİR UYGULAMA
Çalışmada, finansal riskler ile firma değeri arasındaki ilişkiyi ortaya çıkarmak amaçlanmıştır. Bu bağlamda, 2012-2017 yılları arasında Borsa İstanbul 100 Endeksinde pay senetleri devamlı olarak işlem gören firmalara ili...