以加入升溫機制之模擬退火演算法求解單原片方形物件排列問題

Solving a Two-Dimensional Packing Problem Using a Simulated Annealing Algorithm with a Rising Temperature Mechanism

工業界莫不亟思要如何精減人力以提昇效率，全面降低生產成本。然而在如此競爭的環境裡，尚有部分產業仍利用人工方式來處理原物料切割／排列等相關作業。此類複雜之「物件切割」問題需要有合適之演算法來迅速求得原物料切割計畫。由於模擬退火演算法(SA)利用機率性攀爬搜尋演算法則，來搜尋能量函數之總體最小值，且使用者亦能輕易地針對不同的問題發展其適合的演算架構，因此已被大量運用於求解困難的決策問題。雖然SA 藉著使用波茲曼函數來接受品質較差之解，以期能跳脫區域解而達到搜尋全域最佳解之目標。但當退火過程進行、溫度越降越低時，SA陷入區域解之機率越來越大。因此實有必要發展進一步之機制，以維持SA能跳脫區域解之功能。本研究因此藉著導入升溫機制之觀念，讓SA跳脫區域解之能力不致因溫度高低不同而受太大之影響，並應用此SA演算法於快速時間內求算出最佳或近似最佳之單原片方形物件排列計畫。

In this study, a simulated annealing (SA)-based algorithm is proposed for nesting of two-dimensional rectangular parts on a material plate. The traditional SA is well known for its capability to escape from being trapped in local optima. However, this capability decreases as the annealing process proceeds. We hence modify the annealing procedure by adding a rising temperature mechanism. Whenever the signal of solutions being trapped is detected, the annealing temperature is then raised to escape the local trap. Promising computational results are obtained and reported by running examples from the literature.