遺傳演算法和啟發式裝箱演算法為基之單一容器裝填最佳化方法

An Optimization Method for Single Container Packing problems Based on A Genetic Algorithm and Heuristic Packing Algorithms

許冠文(Kwan-Wen Hsu)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2005年)

https://doi.org/10.6342/NTU.2005.01843

摘要

本研究以遺傳演算法為基提出四種啟發式裝箱演算法以求解單一容器裝填問題。本研究提示的裝箱演算法核心是一個裁切�延伸（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.

並列關鍵字

bin packing problem ； single container packing problem ； container loading problem ； spatial evolution technique ； genetic algorithm ； heuristic packing algorithm

參考文獻

21 House, R.L., and Dagli, C.H., 1992, “An approach to three-dimensional packing using genetic algorithm,” ANNIE’92,

7 Bischoff, E., and Dowsland, W.B., 1990, “A Comparative Evaluation of Heuristics for Container-loading,” European Journal

of Operational Research, Vol. 44, pp. 271-280.

8 Bischoff, E.E., and Ratcliff, M.S.W., 1995, “Issues in the development of approaches to container loading,” Omega, Vol.

9 Bischoff, E.E., Janetz, F., and Racliff, M.S.W., 1995, “Loading pallets with non-identical items,” European Journal of