請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36157
標題: | 遺傳演算法和啟發式裝箱演算法為基之單一容器裝填最佳化方法 An Optimization Method for Single Container Packing problems Based on A Genetic Algorithm and Heuristic Packing Algorithms |
作者: | Kwan-Wen Hsu 許冠文 |
指導教授: | 楊烽正 |
關鍵字: | 裝箱問題,單一容器裝填問題,空間演化,遺傳演算法,啟發式裝箱演算法, bin packing problem,single container packing problem,container loading problem,spatial evolution technique,genetic algorithm,heuristic packing algorithm, |
出版年 : | 2005 |
學位: | 碩士 |
摘要: | 本研究以遺傳演算法為基提出四種啟發式裝箱演算法以求解單一容器裝填問題。本研究提示的裝箱演算法核心是一個裁切�延伸(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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36157 |
全文授權: | 有償授權 |
顯示於系所單位: | 工業工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 2.33 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。