楊烽正臺灣大學：工業工程學研究所許冠文Hsu, Kwan-WenKwan-WenHsu2007-11-262018-06-292007-11-262018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/51183本研究以遺傳演算法為基提出四種啟發式裝箱演算法以求解單一容器裝填問題。本研究提示的裝箱演算法核心是一個裁切╱延伸（clip-extened）為基的空間演化技術，名為「裁伸空間演化法」。此演化法最多化地且最大化地更新容器內的候選空間，此候選空間演化法提供裝箱演算法在執行裝填物件作業時有更多更寬大的候選空間選擇。本研究並建立一數值化評估指標稱為–空間吻合度，善用物件與候選空間的尺寸、體積等資訊，使裝箱演算法選取最適候選空間並以最適擺置方位裝填物件。同時使用C#程式語言運用Microsoft Visual Studio .Net 2003和Evolver動態鏈結程式庫 (Dynamic Linking Library, DLL)等軟體工具實作上述求解模式。透過小型自創範例和過往文獻標竿問題的比較。確認本研究的四種求解模式能成功地求解單一容器裝填問題，且本研究的求解模式3及模式4，在Loh 和 Nee (1992)以及鄧景豐(2000)等文獻上的問題，整體而言，獲得較其他文獻上的啟發式和人工智慧方法更佳的求解結果。This research presents genetic algorithm (GA) based four heuristic packing algorithms to solve single container packing problems. The core of heuristic packing algorithms is a “clip-extened based spatial evolution technique”, which dynamically defines usable spaces of container (to be called candidated space) during the packing procedure. This research presents a digitally evaluated formula “space match” to evaluate similarity between objects and candidated spaces. Try to place objects on fit space, and get better solutions. In addition, this research uses C# programming language, Microsoft Visual Studio .Net 2003, and Evolver API to implement the proposed models. Finally, this research compares presented packing algorithms with benchmark single container packing problems to verify performance. The results show that the proposed models can generate appropriate solutions.目錄.........................................................................i 圖目錄.....................................................................iii 表目錄......................................................................iv 中英文名詞對照表.............................................................v 符號列表...................................................................vii 第1章 緒論...................................................................1 1.1 研究背景和動機........................................................1 1.2 研究目的..............................................................2 1.3 研究方法..............................................................3 1.4 章節概要..............................................................6 第2章 文獻探討...............................................................7 2.1 容器裝填問題..........................................................7 2.1.1 裝填問題常見的類型..............................................7 2.1.2 容器裝填問題的求解方法.........................................11 2.2 遺傳演算法之原理.....................................................17 2.2.1 遺傳演算法之基本演算流程.......................................19 2.2.2 遺傳演算法之基本運算子.........................................21 2.3 Evolver的遺傳演算法簡介..............................................30 2.4 文獻探討小結.........................................................33 第3章 單一容器裝填之遺傳演算最佳化法........................................35 3.1 容器裝填問題模式及求解架構...........................................36 3.1.1 容器裝填問題...................................................37 3.1.2 容器裝填問題求解模式的主要流程.................................38 3.1.3 容器裝填問題求解模式的求解系統架構.............................41 3.2 物件與候選空間模型之建構.............................................45 3.2.1 物件資料結構及其擺置方位之定義.................................46 3.2.2 候選空間資料結構和裁伸空間演化法...............................52 3.3 使用遺傳演算法求解單一容器裝填問題...................................85 3.3.1 物件裝填順序為基優化模式–模式1................................88 3.3.2 物件裝填順序暨方位為基優化模式–模式2.........................102 3.3.3 物件批量批次循環裝填優化模式–模式3...........................109 3.3.4 物件批量批次循環裝填暨預覽不可行候選空間的優化模式–模式4.....118 3.4 小結................................................................131 第4章 演算法設計效能分析及範例驗證.........................................133 4.1 演算法穩健性測試....................................................133 4.1.1 小型自創範例問題測試..........................................133 4.2 標竿題目測試........................................................141 4.2.1 與傳統式啟發式演算法比較......................................141 4.2.2 與其他人工智慧演算法比較......................................147 4.3 小結................................................................149 第5章 結論與未來研究建議...................................................150 5.1 結論................................................................150 5.2 未來研究方向與建議..................................................151 參考文獻 1532388888 bytesapplication/pdfen-US裝箱問題單一容器裝填問題空間演化遺傳演算法啟發式裝箱演算法bin packing problemsingle container packing problemcontainer loading problemspatial evolution techniquegenetic algorithmheuristic packing algorithmthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/51183/1/ntu-94-R92546002-1.pdf