楊峰正臺灣大學：工業工程學研究所孫國治Sun, Kuo-ChihKuo-ChihSun2007-11-262018-06-292007-11-262018-06-292004http://ntur.lib.ntu.edu.tw//handle/246246/51220本論文提示一以遺傳演算法(genetic algorithms)為基的任意外形(arbitrarily shaped)營建工地(construction sites)設施佈置(facility layout)最佳化方法。採用非格位為基平面(non-grid-based plane)處理設施及工地外形，以多邊形端點、向量線段、多邊形區域、和參考座標變數等定義任意外形。規劃模式並加入設施穢韙閬鴩云瘍僂ヾA以擴展系統應用的實用性。此外，有別於過往研究求解設施佈置的遺傳演算模式普遍以格位編號進行染色體(chromosome)編碼(encoding)(屬離散式編碼)，本研究直接應用實數型遺傳演算法(real number coded genetic algorithms)編碼建構問題模型並行求解。 本研究使用C#程式語言、MS .Net Framework類別庫、與Evolver API動態鏈結程式庫(dynamic link library)，開發一套名為GAFLP的「遺傳演算法為基之營建工地設施佈置規劃系統」(GA-based Facility Layout Planning system for construction site)應用程式。GAFLP提供使用者在人機介面上以繪圖方式設定工地和設施外形，並提供多種參數設定(如：設施種類、設施關連程度等)以求解不同的問題。本研究並以多個實例驗證方法的可行性及系統的求解成效，驗證結果顯示提出的模式適用在大範圍基地中分散佈置(loosely arrangement)的營建工地設施佈置規劃上，並可快速獲得適當的解答。This thesis presents a study of current practices on solving the facility layout problem, incorporating a genetic algorithms (GA) procedure. This research presents a non-grid-based plane model that is more readily applicable to construction sites. This new facility layout model allows user to determine several parameters, such as irregular user-defined polygon of arbitrarily shapes, reference coordinates, and place orientation, which is more realistic in the construction engineering. Furthermore, previous research uses GA to solve the facility layout problem focus on grid-based site representation. They encode the chromosome by the position index of two-dimensional grid, namely discrete encoding. By contrast, this research applied real number coded genetic algorithms to define the application model. Based on the proposed model, a comprehensive system for a GA-based Facility Layout Planning system for construction site (GAFLP) is developed. GAFLP uses C# programming language, MS .Net Framework, and Evolver API to represent the site and the facilities, and automate the solution evolved. This set of algorithms employ the specific coding of facility shapes provides a more efficient tool to draw the shapes on man-machine interface. This proposed model also provides alternative settings for solve different construction layout problems, such as closeness relationship values, types of facilities, etc. The results show that the present model can be suitable for loosely arrangement in large base as construction site and it can quickly generates an appropriate planning of construction site layout.誌謝 i 摘要 ii Abstract iii 目錄 iv 圖目錄 vii 表目錄 ix 中英文名詞對照表 x 中英文名詞對照表(續) xi 符號說明 xii 第1章 緒論 1 1.1 研究動機 1 1.2 研究目的 2 1.3 預定研究方法 3 1.4 論文架構 7 第2章 文獻回顧 8 2.1 設施規劃問題相關文獻探討 8 2.1.1 設施規劃問題的定義及發展歷史 9 2.1.2 設施規劃問題的求解方法 11 數學模式： 12 啟發式方法： 12 人工智慧： 16 2.2 營建工地設施佈置問題陳述 17 2.3 遺傳演算法之原理 19 2.3.1 遺傳演算法之特點 19 2.3.2 遺傳演算法之基本原理 21 基因變數的編碼： 22 產生初始族群： 24 適應函數： 24 複製： 25 交配： 27 突變： 29 族群取代策略： 30 產生不可行解的解決方式： 30 終止條件： 31 2.3.3 遺傳演算法之演算流程 31 2.3.4 實數型遺傳演算法 32 實數型遺傳演算法的複製： 33 實數型遺傳演算法的交配： 33 實數型遺傳演算法的突變： 34 2.4 遺傳演算法求解營建工地設施佈置方法探討 34 第3章 營建工地設施佈置之遺傳演算最佳化法 38 3.1 營建工地設施佈置模型適用之範圍 38 3.2 工地與設施模型之建構 43 3.2.1 不規則外型之定義 44 3.2.2 座標轉換與圖形呈現 45 3.3 設施的種類與放置類型 48 3.4 設施間的關連程度 50 3.5 Evolver的遺傳演算法則 51 3.6 設施佈置的遺傳演算模式 55 3.6.1 染色體結構 55 3.6.2 不可行解的檢驗 58 3.6.3 適應函數值的計算 61 3.7 演算流程 64 第4章 模式之驗證與應用 68 4.1 GAFLP系統之介面與使用方法 68 4.1.1 人機操作環境 69 4.1.2 工地的設施佈置問題之設定 71 4.1.3 遺傳演算的控制與參數設定 75 4.2 案例驗證 79 4.2.1 最佳解的求解能力驗證 80 案例1： 80 案例2： 84 4.2.2 初始可行解的產生和設施穢韙閬鴘瘍褌5384188 bytesapplication/pdfen-US實數型遺傳演算法營建工地任意外形設施佈置遺傳演算法非格位為基平面construction sitegenetic algorithmsreal number coded genetic algorithmsnon-grid-based planearbitrarily shapedfacility layoutthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/51220/1/ntu-93-R91546008-1.pdf