質群演算法於組合型時間成本最佳化問題之研究

Using PSO to solve combinatorial time-cost trade-off problems

陳柏村(Po-Chun Chen)

指導教授 ： 楊亦東

淡江大學/工學院/土木工程學系碩士班/碩士(2006年)

https://doi.org/10.6846/TKU.2006.00971

摘要

工程專案中的作業可藉著機具與人力的增減來控制作業的天數，若要壓縮工期，一般須分派較高的資源或人力，也代表較多資金的投入。其中專案工期與直接成本之對應關係稱為時間成本權衡。了解工期與成本可能的組合，將協助規劃者決定各作業的最佳施工天數與資源需求。
各作業之時間成本關係函數一般可分為線性、非線性及組合型式，其中線性、非線性已能有效的以線性規劃或非線性規劃求解。但由於營建工程機具與人力均為有限且間斷的組合，組合式的時間成本關係較為接近實際的營建工程狀況。但也因此提高了求解的困難度及複雜度，再加上專案中作業項目的增加，將使得傳統啟發法與解析法無法很有效率地求得最佳解。
本研究發展質群演算法（PSO）以求解組合式時間成本權衡問題。主要利用群體智慧的概念，在可行解範圍的空間中搜尋最佳解。進一步分析領導策略、切割方式及回彈模式，以決定最適合之質群演算法。驗證部份則與窮舉法結果比較，以證明可有效求得最佳解。

關鍵字

質群演算法 ； 時間成本權衡 ； 間斷型 ； 組合式

並列摘要

Tasks in a construction project can often be accelerated using labor and equipment with higher efficiency and greater capacity. Such acceleration, however, is associated with higher cost. Thus it is important for project managers to choose among possible time-cost options to suit management needs, such as prespecified deadline. This problem is coined as the “time-cost tradeoff problem”.
For each task, the time-cost functions may be in linear, nonlinear, and discrete forms. Since the options of labor and equipment are practically finite and discrete, this study focuses on the time-cost tradeoff problem with discrete time-cost functions. The discrete time-cost tradeoff problem cannot be efficiently solved by traditional methods because the number of variables would exponentially explode as the number of tasks increases.
This study develops a new particle swarm optimization (PSO) algorithm, a class of stochastic search, to find the direct time-cost curve, which can be further used to obtain the total time-cost curve with consideration of indirect cost, delay penalty, and early bonus. The proposed PSO algorithm investigates three schemes: particle communication strategy, space zoning plan, and domain error prevention. Through a numerical case, it has been validated that the best design of the PSO algorithm consists of three schemes: (1) pair-wise swarm inter-communication; (2) single zoning, and (3) particle bouncing in domain error. The performance is measured in terms of effectiveness, efficiency, converging speed, and robustness. The proposed PSO algorithm has also been compared with exhaustive search and genetic algorithms to show its performance.

並列關鍵字

PSO ； time-cost tradeoff problem ； discrete ； combinatorial

參考文獻

【6】李世炳、鄒忠毅，「簡介導引模擬退火法及其應用」，物理雙月刊，24卷2期307-319 （2002年4月）。

【22】葉思緯（2004），「應用粒子群最佳化演算法於多目標存貨分類之研究」，元智大學工業工程與管理學系研究所碩士論文。

【28】Angeline, P.J. （1998）, ”Using selection to improve particle swarm optimization,” In: Proceedings of the IEEE Congress on Evolutionary Computation, Anchorage, Alaska.

【31】Clerc, M. (1999), ”The swarm and the queen: towards a deterministic and adaptive particle swarm optimization,” Proc. I999 Congress on Evolutionary Computation,Washington, DC, Vol. 3, pp.1-1957.

【35】Eberhart, R.C. and Y. Shi.,（1998）, ”Comparison between genetic algorithms and particle swarm optimization,” Annual Conference on Evolutionary Programming, San Diego.