裝箱問題

出自 MBA智库百科(https://wiki.mbalib.com/)

裝箱問題（Bin Packing）

　　把一些箱子裝入容器中是一個在工業生產中經常遇到的數學難題，比如集裝箱的裝箱問題。裝箱問題是一個經典的組合優化問題，有著廣泛的應用，在日常生活中也屢見不鮮。

　　設有許多具有同樣結構和負荷的箱子B₁，B₂，… ，其數量足夠供所達到目的之用。每個箱子的負荷（可為長度、重量等等.）為 C ，今有 n 個負荷為 wj，0 < wj < C ， j = 1，2，…，n 的物品 J₁，J₂，…，J_n 需要裝入箱內。裝箱問題就是指尋找一種方法，使得能以最小數量的箱子數將J₁，J₂，…，J_n 全部裝入箱內。

　　裝箱問題可分為一維裝箱問題，二維裝箱問題，三維裝箱問題三種。現實生活中常見的應該是三維裝箱問題。

　　一維裝箱問題只考慮一個因素，比如重量、體積、長度等。

　　二維裝箱問題考慮兩個因素——給定一張矩形的紙（布料、皮革），要求從這張紙上剪出給定的大小不一的形狀，求一種剪法使得剪出的廢料的面積總和最小。常見問題包括堆場中考慮長和寬進行各功能區域劃分、停車場區位劃分、包裝材料裁切時考慮怎樣裁切使得材料浪費最少、服裝布料裁切、皮鞋製作中的皮革裁切等。

　　三維裝箱問題考慮三個因素——一般指長、寬、高。裝車、裝船、裝集裝箱等要考慮這三個維度都不能超。

　　根據目標的不同,三維裝箱問題可分成以下幾類：

　　箱櫃裝載問題(Three-Dimensional Bin Packing Problem，簡稱3D-BPP)：給定一些不同類型的方型箱子和一些規格統一的方型容器，問題是要把所有箱子裝入最少數量的容器中。

　　容器裝載問題(Three-Dimensional Container-Packing Problems，簡稱3D-CPP)：在該問題中，所有箱子要裝入一個不限尺寸的容器中，目標是要找一個裝填，使得容器體積最小。

　　背包裝載問題(Three-Dimensional Knapsack Loading Problems，簡稱3D-KLP)：每個箱子有一定的價值，背包裝載是選擇箱子的一部分裝入容器中，使得裝入容器中的箱子總價值最大。如果把箱子的體積作為價值，則目標轉化為使容器浪費的體積最小。