以模擬退火演算法求解不規則物件排列問題

A Simulated Annealing Approach for Solving Packing Problems Involving Objects with Irregular Shapes

吳泰熙(Tai-Hsi Wu) ； 葉進儀(Jinn-Yi Yeh) ； 黃玟錫(Wen-Shi Huarng)

《技術學刊》 19卷3期 (2004/09) Pp. 213-220

https://doi.org/10.29507/JT.200409.0001

摘要

本研究建立一模擬退火演算模式來求解不規則物件之排列問題，配合三個有效的移步法則，並依據各物件的不同特性與物料原片是否為一均質規則原片等相關考量，提出傳統型不規則物件排列與非均質及不規則外型原片等兩種解題模式，在合適的起始溫度、馬可夫鍊長度、冷卻率與目標函數值的設定下，以求獲致理想之排列結果。實驗結果發現針對均質規則原片與非均質及不規則外型原片之排列問題，本研究所提出之模擬退火演算法皆能在可允許的時間內得到不錯之排列結果。

關鍵字

不規則物件排列問題 ； 模擬退火法

並列摘要

A simulated annealing-based (SA) algorithm is developed for solving packing problems involving objects with irregular shapes. In addition to traditional problems which assume that material plates used are rectangular in shape, and uniform without any defective areas, another type of problem conforming to more realistic situations is considered in this study. Three effective neighborhood searches are designed, accompanied by the mechanism of the SA method, such as setting of a cooling process, and the Markov chain length. Computational results show that the SA algorithm developed can find good solutions in an acceptable amount of time for both types of packing problems.

並列關鍵字

simulated annealing ； irregular packing problems