遺傳演算法為基之任意外形營建工地設施佈置最佳化方法

A Genetic Algorithm Based Layout Optimization Method for Arbitrarily Shaped Construction Sites and Facilities

孫國治(Kuo-Chih Sun)

指導教授 ： 楊峰正

國立臺灣大學/工學院/工業工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.00753

摘要

本論文提示一以遺傳演算法(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.

並列關鍵字

construction site, ； genetic algorithms, ； real number coded genetic algorithms, ； non-grid-based plane, ； arbitrarily shaped, ； facility layout,

參考文獻

Bozer, Y. A., Meller, R. D., and Erlebacher, S. J., 1994, “An Improvement- Type Layout Algorithm for Single and Multiple Floor Facilities,” Management Science, Vol.40, No.7, pp. 918-932.

Camp, D. J. V., Carter, M. W., and Vannelli, A., 1991, “A Nonlinear Optimization Approach for Solving Facility Layout Problems,” European Journal of Operational Research, Vol.57, pp. 174-189.

Foulds, L. R., and Robinson, D. F., 1978, “Graph Theoretic Heuristics for the Plant Layout Problem,” International Journal of Production Research, Vol.16, No.1, pp. 27-37.

Hassan, M. M. D., Hogg, G. L., and Smith, D. R., 1986, “SHAPE：A Construction Algorithm for Area Placement Evaluation,” International Journal of Production Research, Vol.24, pp. 1283-1295.

Hegazy, T., and Elbeltagi, E., 1999, “EvoSite：Evolution-Based Model for Site Layout Planning,” Journal of Computing in Civil Engineering, ASCE, Vol.13, No.3, pp. 198-206.