貨物運輸棧板裝載問題啟發式解法之應用

Abstract

一般企業之物品配送作業中大部份裝箱後之貨品以卡車、鐵路貨車、貨機和船舶運 送均是利用棧板來裝載，因此探討如何利用棧板裝載貨品，以使棧板面積使用率為 最大，節省倉庫之儲存空間及提高貨車裝載率，降低倉儲成本和運輸成本是物料管 理和物品配送作業中重要的一環。 棧板裝載問題依裝載貨箱(Box) 種類數不同可分為兩種型態：(1) 單一規格貨箱裝 載問題；(2) 多種規格貨箱裝載問題。而目前文獻中在探討棧板裝載問題，尚不考 慮貨箱之高度，只由貨箱之長、寬組合來決定棧板裝載型態(Pallet Loading Pat- tern) ，將問題簡化成二維裝載問題。本研內容著重於探討單一規格貨箱二維裝載 問題方面，發展出一整數規劃(Integer Programming-IP)啟發式解法迅速地求得一 近似解，並以此IP模式為基礎將其延伸應用在多種規格貨箱棧板裝載問題上。 單一規格貨箱棧板裝載問題在學術上是屬於難解的NP-complete 問題，無法在合理 的運算時間內解得一最佳解，因此，為了能簡單、迅速地找到一近似解，Steudel 提出最大周邊涵蓋觀念，利用動態規劃法求解，但所求得之起始解常為不可行（區 塊重疊）或很差的起始解（棧板中空面積太大），嚴重地影響解題效率和結果。本 研究針對此現象，建立一整數規劃模式求起始解，限制棧板裝載型態為至多三個區 塊(Blocks)存在之型態，可避免產生不可行和很差的起始解，不必再作進一步地處 理，所獲得之起始解即是結果很好的可行解。由各種不同貨箱類型的測試例題中之 執行結果顯示，IP啟發式解法均可獲得很好的結果。