Üç boyutlu palet yükleme probleminin karışık tam sayılı programlama (MILP) ve hibrit genetik algoritma ile çözümü
Solving the 3D-pallet loading problem by a mixed integer linear programming and a hybrid genetic algorithm
- Tez No: 545644
- Danışmanlar: PROF. DR. HARUN REŞİT YAZĞAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Genetik algoritmalar, Karışık tam sayılı doğrusal programlama, Lojistik, Genetic algorithms, Mixed integer linear programming, Logistics
- Yıl: 2019
- Dil: Türkçe
- Üniversite: Sakarya Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu tez çalışmasında, konteyner yükleme problemlerinin (KYP) bir çeşidi olan üç boyutlu palet yükleme problemi (3B-PYP), problemin doğası gereği göz önüne alınması gereken kısıtların yanı sıra, kontrollü döndürme kısıtı, kırılganlık kısıtı, yüke dayanım kısıtı ve bağlantılı nesnelerin bir arada olması kısıtı gibi ek yükleme kısıtları altında ele alınmıştır. Ele alınan 3B-PYP'nin optimum çözümü için bir karışık tam sayılı doğrusal programlama (MILP) modeli geliştirilmiştir. Geliştirilen model, küçük ölçekli 3B-PYP'yi optimize etmek için kullanılabilmekte fakat müşteri sayısı, nesne sayısı ve palet yükleme oranı gibi problem parametrelerindeki artışlara bağlı olarak büyük ölçekli gerçek hayat problemlerinin optimizasyonu için kabul edilebilir bir sürede cevap verememektedir. Bu sebeple büyük ölçekli problemlerin çözümü için biri yığın oluşturma tabanlı, diğeri yatay katman oluşturma tabanlı olmak üzere iki farklı sezgisel yaklaşım ile hibritlenmiş bir hibrit genetik algoritma (HGA) geliştirilmiştir. Önerilen HGA'daki yığın oluşturma tabanlı sezgisel yaklaşım, yüklenecek olan nesnelerden en az iki boyutu birbirine eşit olanları genetik algoritma (GA) arama yapısını kullanarak belirler ve bu nesneleri birbiriyle birleştirerek, iki nesneyi de kapsayan yeni bir nesne olarak tanımlar. Bu şekilde yerleştirilecek nesne sayısının azaltılması sağlanmış olur. Birleştirme işlemleri yapılırken GA'daki kromozom uzunlukları bozulabilir. Bu sebepten dolayı literatürdeki mevcut çaprazlama operatörleri kullanılamamaktadır ve akıllı dinamik çaprazlama operatörü (A-DÇO) adı verilen bir çaprazlama operatörü geliştirilmiştir. Önerilen HGA'daki bir diğer sezgisel algoritma da literatürde var olan en dip alt sol doldurma (DASD) algoritmasıdır. Bu algoritmanın adımları sayesinde tüm nesnelerin paletlere nihai yüklemesi yapılır ve tüm nesnelerin paletler üzerindeki koordinatları belirlenir. Önerilen HGA'nın klasik DASD ile test problemleri üzerinde karşılaştırılması yapılmış ve daha iyi çözümler verdiği istatistiksel olarak gösterilmiştir. Ayrıca önerilen HGA, literatürde var olan bir parçacık sürü eniyileme algoritması (PSO) ve HGA-L adı verilen bir başka HGA ile de test problemleri üzerinde karşılaştırılmıştır. Önerilen HGA'nın bu algoritmalardan da daha iyi sonuçlar verdiği istatistiksel olarak gösterilmiştir. Sonuç olarak, ele alınan 3B-PYP için önerilen HGA, daha iyi sonuçlar vermekte ve özellikle gerçek hayatta robot kolları vasıtası yapılan otomatik paletleme operasyonları için kullanılması önerilmektedir.
Özet (Çeviri)
In this thesis, the three-dimensional pallet loading problem (3D-PLP), which is a kind of container loading problems (CLP), was studied under the constraints as rotation, fragility, load-bearing strength, relative positioning as well as the constraints that should be considered due to the nature of the problem. A mixed integer linear programming (MILP) model was developed for the optimal solution of the studied 3D-PLP. The developed model can be used to optimize small-scale 3D-PLP. However, due to increase in some problem parameters as the number of customers, the number of objects and the pallet loading rate, it cannot be solved in an acceptable time for large-scale real-life problems. For this reason, a new hybrid genetic algorithm (HGA) was developed for solving large-scale problems. It was hybridized with two different heuristic approaches, one of them is based on a stack-building approach and the other one is based on a layer building approach. The stack-building approach determines the objects which have at least two equal dimensions by searching structure of genetic algorithm (GA). This operation reduces the number of objects to be placed. The chromosome lengths in the GA may change because of the combining operation. For this reason, existing crossover operators in the literature cannot be employed. And a crossover operator called the intelligent dynamic crossover operator (I-DCO) was developed. Another heuristic approach in the proposed HGA is deepest bottom left fill (DBLF) approach which is available in the literature. Under favor of the steps of DBLF, all objects can be loaded to the pallets and the coordinates of all objects on the pallets are determined. The proposed HGA was compared with classical DBLF on test problems and it was shown that the proposed HGA produced better solutions statistically. In addition, the proposed HGA was compared with two existing meta-heuristic algorithms on test problems. It was shown that the proposed HGA achieved better results than these algorithms. As a result, the proposed HGA for the 3D-PLP yielded much better results.
Benzer Tezler
- Fonksiyonel derecelendirilmiş kirişlerin mekanik analizi
Mechanical analysis of functionally graded beams
UĞUR ÖZMEN
Doktora
Türkçe
2021
Mühendislik BilimleriManisa Celal Bayar ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. BOZKURT BURAK ÖZHAN
- Üç boyutlu stok kesme probleminin matematiksel programlama teknikleri ile optimizasyonu ve sünger endüstrisinde bir uygulama
Three-dimensional cutting stock problem optimization in using mathematical programming techniques and an application in foam industry
AYŞE KÜTAHNECİ
Yüksek Lisans
Türkçe
2013
Endüstri ve Endüstri MühendisliğiErciyes ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. LALE ÖZBAKIR
- An application of pallet loading problem
Palet yükleme problemi
ÖZLEM AKMAN
Yüksek Lisans
İngilizce
2013
Endüstri ve Endüstri MühendisliğiYaşar ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ADALET ÖNER
- Discrete vortex method simulation of Karman vortex street-edge interaction
Karman Girdap caddesi-cisim etkileşiminin ayrık girdap yöntemiyle incelenmesi
METİN O. KAYA
Doktora
İngilizce
1992
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak Mühendisliği Ana Bilim Dalı
DOÇ. DR. C. RUHİ KAYKAYOĞLU
- Topology and bandwidth adaptation in optical WDM backbone networks with dynamic traffic
Değişken veri trafikli optik WDM omurga ağlarında topoloji ve bant genişliği uyarlama
AYŞEGÜL GENÇATA
Doktora
İngilizce
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET BÜLENT ÖRENCİK