以改良粒子群演算法求解鋼筋裁切最佳化問題

Improving Particle Swarm Optimization to Solve the Cutting Steel Bars Problem

歐淑民(Shu-min Ou)

指導教授 ： 吳獻堂

朝陽科技大學/理工學院/營建工程系/碩士(2011年)

摘要

鋼筋裁切計畫是一個組合最佳化問題(Combinatorial Optimization Problem )，探討在已知數量及長度之原料鋼筋中，如何裁切出特定數量及長度之需求鋼筋，而使得餘料最少或成本最低。近年來，原物料的價格波動大，若能降低鋼筋的餘料量，對於營建成本的控制有莫大的助益。
本研究主要目的在於以改良式粒子群演算法(Particle Swarm Optimization)求解鋼筋裁切模式最佳化問題。粒子的編碼設計，採用2倍需求鋼筋數量維度之實數向量以決定裁切順序。以下次適應裝箱法(Next Fit)進行裝箱作業，計算目標函數值，並決定鋼筋裁切計畫、記憶優秀鋼筋裁切順序。採用「優秀裁切順序」擾動機制來避免粒子陷入局部最佳解並增加粒子搜尋到更好解的機會。
研究結果顯示，本研究所建立之鋼筋裁切模式，可更快速且獲得更佳最適解。

關鍵字

一維裁切 ； 鋼筋裁切 ； 下次適應裝箱法 ； 粒子群演算法

並列摘要

The steel bars cutting plan is a combinational optimization problem, which discuss how to cut the specific quantities and length of steel bars and to make the rest of the raw steel bars at least. In recent years, the price of the raw material fluctuated very much. If we can reduce the quantities of the rest of the raw steel bars, it is more helpful to control the cost in construction.
The objective of the study is to solve steel bars cutting optimization with improving particle swarm algorithm. The design of the particle coding is used to determine the steel bars cutting order by the real number vector of the 2 times dimension of requiring steel bars quantities. The next fit packing method is used to carry out the packing operation, calculate objective function value, determine the steel bars cutting plan, and memorize excellent order of the cutting steel bars.
The excellent cutting order pertubation mechanism is to avoid particles falling into the local optimal solution and to increase the opportunity of the particles in search of better solution.
The results show that the study in cutting steel bars mode can get most suitable solution more quickly and better.

並列關鍵字

Cutting stock problem ； Next fit ； Particle swarm optimization ； Cutting steel bars problem

參考文獻

03、 李佩玲，「以混合基因與粒子群演算法求解旅行銷售員問題」，碩士論文，中原大學資訊管理學系，2006。

04、 李冠廷，「質群演算法應用於鋼筋裁切最佳化問題之研究」，碩士論文，淡江大學土木工程學系，2007。

13、 盧立昕，「BH 型鋼裁切問題之啟發式解法」，碩士論文，成功大學土木工程學研究所，2010。

09、 堯敦瀚，「粒子尋優法效能改進及其在旅行商問題之應用」，碩士論文，成功大學航空太空工程學系，2008。

06、 張瀚文，「鋼筋裁切順序最佳化模式」，碩士論文，成功大學土木工程學研究所，2005。