臺灣博碩士論文加值系統

鋼筋裁切計畫是一個組合最佳化問題(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.

目錄
摘要 I
ABSTRACT II
誌謝 III
圖目錄 VIII
表目錄 X
數學符號表 XII
第1章 緒論 1
1.1 研究動機及目的 1
1.2 研究流程 2
1.3 研究範圍 4
1.4 論文架構 5
第2章 文獻回顧 6
2.1 原料裁切問題 6
2.2 粒子群演算法 8
第3章 理論介紹與研究方法 11
3.1 最佳化問題 11
3.2 粒子群演算法 12
3.2.1 演算公式 13
3.2.2 演算流程 14
3.2.3 參數分析 17
3.3 下次適應裝箱法 19
3.4 研究問題陳述 20
3.5 研究方法與求解步驟 21
3.5.1 研究方法 21
3.5.2 求解步驟 27
第4章 數值模擬與測試 29
4.1 範例驗證 29
4.1.1 範例說明 29
4.1.2 範例結果與分析 30
4.2 測試案例 35
4.2.1 測試案例說明 35
4.2.2 案例結果與分析 36
4.3 算法效能分析 41
4.3.1 測試方法與說明 41
4.3.2 結果與分析 42
4.3.3 與文獻比較 49
第5章 結論與未來展望 51
5.1 結論 51
5.2 未來展望 52
參考文獻 53
中文部分 53
英文部分 55

圖目錄
圖1-1、研究流程圖 3
圖3-1、第I個粒子位置移動示意圖 14
圖3-3、下次適應裝箱法裝箱操作示意圖 20
圖3-4、組別表編號對應圖 23
圖3-5、擾動機制A流程的示意圖 25
圖3-6、「優秀裁切順序」及隨機裁切順序的示意圖 26
圖3-7、擾動機制B流程的示意圖 27
圖4-1、裁切結果示意圖(案例一) 34
圖4-2、目標函數值與迭代代數關係之收斂圖(案例二) 38
圖4-3、裁切結果示意圖(案例二) 38
圖4-4、六種策略及粒子數組合之目標函數值收斂圖 43
圖4-5、六種策略及粒子數組合之目標函數值收斂圖(N=1000) 44
圖4-6、六種策略及粒子數組合之目標函數值收斂圖(N=500) 44
圖4-7、六種策略及粒子數組合之目標函數值收斂圖(N=100) 45
圖4-8、六種策略及粒子數組合之目標函數值收斂圖(N=20) 45
圖4-9、迭代次數與目標函數值收斂圖(策略一) 46
圖4-10、迭代次數與目標函數值收斂圖(策略二) 47
圖4-11、迭代次數與目標函數值收斂圖(策略三) 47
圖4-12、迭代次數與目標函數值收斂圖(策略四) 48
圖4-13、迭代次數與目標函數值收斂圖(策略五) 48
圖4-14、迭代次數與目標函數值收斂圖(策略六) 49
圖4-15、目標函數值與迭代次數之收斂情形比較圖 50
表目錄
表3-1、粒子編碼 與順序表R之對照表 22
表3-2、粒子編碼 與組別表G之對照表 23
表3-3、「優秀裁切順序」及隨機裁切順序的目標函數值變化表 26
表4-1、原料鋼筋編號表(案例一) 29
表4-2、需求鋼筋編號表(案例一) 30
表4-3、最佳解之順序表G及組別表R 30
表4-4、各組別依裁切順序排列之需求鋼筋編號表 31
表4-5、原料鋼筋裁切情形明細表 32
表4-6、原料鋼筋裁切情形彙整表 32
表4-7、目標函數值計算表(案例一) 33
表4-8、鋼筋裁切計畫表(案例一) 35
表4-9、原料鋼筋編號表(案例二) 36
表4-10、需求鋼筋編號表(案例二) 36
表4-11、目標函數值計算表(案例二) 37
表4-12、鋼筋裁切計畫表(案例二) 39
表4-12、鋼筋裁切計畫表(續一) 40
表4-12、鋼筋裁切計畫表(續二) 41
表4-13、六種策略及粒子數組合之最佳目標函數值彙整表 42

中文部分
01、吳忠倫，「以粒子群優化法求解多模資源受限的專案排程問題」，碩士論文，勤益科技大學電子工程研究所，2009。
02、吳偉仕，「新的應用於一維儲料切割問題之循序啟發式程序」，碩士論文，台灣海洋大學系統工程暨造船學系，2006。
03、李佩玲，「以混合基因與粒子群演算法求解旅行銷售員問題」，碩士論文，中原大學資訊管理學系，2006。
04、李冠廷，「質群演算法應用於鋼筋裁切最佳化問題之研究」，碩士論文，淡江大學土木工程學系，2007。
05、沈宇晟，「鋼筋裁切問題之啟發式解法」，碩士論文，成功大學土木工程學研究所，2005。
06、張瀚文，「鋼筋裁切順序最佳化模式」，碩士論文，成功大學土木工程學研究所，2005。
07、紀震、廖惠達、吳青華，粒子群算法及應用，科學出版社，北京，第1-4頁，2009。
08、陳俊元，「以線性規劃法做鋼筋物料裁切之研究」，碩士論文，逢甲大學環境資訊科技研究所，2007。
09、堯敦瀚，「粒子尋優法效能改進及其在旅行商問題之應用」，碩士論文，成功大學航空太空工程學系，2008。
10、曾兆堂，「粒子群最佳化演算法於排程問題之研究」，博士論文，台灣科技大學企業管理系，2006。
11、劉清祥，「粒子群演算法於結構設計及零工式排程之研究」，碩士論文，台灣海洋大學系統工程暨造船系，2005。
12、鄭瑞富、李宇欣，「考慮切割順序之一維鋼材裁切模式」，中國土木水利工程學刊，第19卷，第二期，第257-287頁，2007。
13、盧立昕，「BH 型鋼裁切問題之啟發式解法」，碩士論文，成功大學土木工程學研究所，2010。
14、賴德忠，「最佳化型鋼構件裁切之研究」，碩士論文，中央大學土木工程學研究所，2010。
15、蘇明健，「應用啟發式演算法求解多目標型鋼切割計畫之研究」，碩士論文，中山大學資訊管理研究所，2009。

英文部分
01、Angeline, P. J., “Using selection to improve paticle swarm optimization.” IEEE World Congress on Computational Intelligence, pp.84-89, 1998.
02、Clerc, M., “The swarm and the queen:Towards a deterministic and adaptive particle swarm optimization.” Proc. 1999 Congress on Evolutionary Computation, Vol. 3,pp.1951-1957, 1999.
03、Eberhart, R. C. and Kennedy, J., “A new optimizer using particle swarm theory.” Proc. Sixth International Symposium on Micro Machine and Human Science, pp.39-43, 1995.
04、Gilmore,P.C., and Gomory, R.E., “A Linear Programming Approach to the Cutting Stock Problem.” Operations Research, Vol.9, pp. 849-859, 1963.
05、Kennedy, J. and Mendes, R., “Population structure and particle swarm performance” Proceedings of the 2002 Congress on Evolutionary Computation, Vol. 2, pp.1671-1676, 2002.
06、Kennedy, J., and Eberhart, R. C., “Particle swarm optimization.” Proc. IEEE International Conference on Neural Networks, pp.1942-1948, 1995.
07、Kennedy, J., and Eberhart, R. C., “A discrete Binary version of the particle swarm algorithm.” Proc. IEEE The Conference on System, Cybernetics and Informatics..pp4104-4109, 1997.
08、Shi, Y. and Eberhart, R. C., “A modified particle swarm optimizer.” IEEE Int. Conference on Evolutionary Programming, pp.69-73, 1998.
09、Shi, Y. and Eberhart, R. C., “Empirical study of particle swarm optimization.” Proceedings of the Evolutionary Computation 1999 Congress, Vol. 3, pp.1945-1950, 1999.