packing problemlerinin amacı, belirli boyutlardaki bir dizi öğeyi sabit packing sahip kapsayıcılarda paketlemenin en iyi yolunu bulmaktır. Tipik bir uygulama, kutuları teslimat kamyonlarına verimli bir şekilde yüklemektir. Genellikle kapasite kısıtlamaları nedeniyle tüm öğeleri paketlemek mümkün değildir. Bu durumda sorun, kapsayıcılara sığacak maksimum toplam boyuta sahip öğelerin alt kümesini bulmaktır.
Birçok türde paketleme sorunu vardır. En önemli iki sorun, sırt çantası problemleri ve kutu paketleme problemleridir.
Sırt çantası sorunları
Basit sırt çantası probleminde tek bir kapsayıcı (sırt çantası) vardır. Öğelerin bedenlerinin yanı sıra değerleri de vardır ve hedef, maksimum toplam değere sahip öğelerin bir alt kümesini paketlemektir.
Değerin boyuta eşit olduğu özel durumda hedef, paketlenmiş öğelerin toplam boyutunu en üst düzeye çıkarmaktır.
VEYA araçları, algoritma kitaplığında sırt çantası sorunları için çeşitli çözücüler sağlar.
Sırt çantası sorununun daha genel versiyonları da vardır. İşte birkaç örnek:
Öğelerin ağırlık ve hacim gibi birden fazla fiziksel miktarı olduğu ve sırt çantasının her miktar için kapasitesi olduğu çok boyutlu sırt çantası problemleri. Burada boyut terimi, her zaman yükseklik, uzunluk ve genişlik gibi her zamanki uzamsal boyutları ifade etmez. Bununla birlikte, bazı problemler uzamsal boyutlar içerebilir. Örneğin, dikdörtgen kutuları dikdörtgen bir depolama kutusuna paketlemenin en uygun yolunu bulmak gibi.
Çoklu sırt çantası problemleri: Birden fazla sırt çantası bulunur ve amaç tüm sırt çantalarındaki paketlenmiş öğelerin toplam değerini en üst düzeye çıkarmaktır.
Tek bir sırt çantasıyla ilgili çok boyutlu bir probleminiz veya tek bir boyutta birden çok sırt çantası sorunu olabileceğini unutmayın.
Çöp konteyneriyle ilgili sorun
En iyi bilinen paketleme problemlerinden biri, aynı kapasiteye sahip birden çok container'ın (bin-packing adı verilir) bulunduğu bin-packing işlemidir. Birden fazla sırt çantası sorunundan farklı olarak, kutu sayısı sabit değildir. Bunun yerine, amaç tüm öğeleri içerecek en küçük bölme sayısını bulmaktır.
Çoklu sırt çantası problemi ile çöp kutusuna yerleştirme problemi arasındaki farkı gösteren basit bir örnek aşağıda verilmiştir. Bir şirketin, her birinin 18.000 kg ağırlık kapasitesi ve 130.000 kg ürün teslim edecek şekilde teslimat kamyonları olduğunu varsayalım.
Birden fazla sırt çantası: Beş kamyonunuz var ve ürünlerin maksimum ağırlığı olan bir alt kümesini yüklemek istiyorsunuz.
Kutu paketleme: 20 kamyonunuz var (tüm eşyalarınızı tutmak için yeterliden fazla) ve bunların tümünü tutacak en az sayıda kamyonu kullanmak istiyorsunuz.
Aşağıdaki bölümlerde sırt çantası problemi ile başlayarak VEYA Araçları ile çeşitli paketleme problemlerinin nasıl çözüleceği gösterilmektedir.