施工現場設施布局優化問題的新型啟發式算法

王家 王洋 鄧鐵軍 劉可心

摘? ?要：施工現場設施布局的合理性直接關系到項目成本等目標的實現.針對涉及設施較多的施工現場布局優化問題，首先將該離散變量優化問題轉換為高維空間的隨機抽樣問題，進而利用過渡馬爾可夫鏈蒙特卡羅方法的思想，提出一種高效的全局優化啟發式算法.與針對連續型高維概率密度分布函數進行隨機取樣的過渡馬爾可夫鏈蒙特卡羅方法相比，本文提出的啟發式算法的框架基礎需從概率密度分布函數轉變為概率分布函數，進而需在馬爾可夫鏈狀態點的產生方法上進行修正，以適應離散型變量優化問題的不同特性.通過實例驗證，與目前應用較廣的遺傳算法相比，本文提出的新型啟發式算法在全局最優解的獲取穩定性上有較大改進.

關鍵詞：施工現場設施布局優化;啟發式算法;全局優化算法;過渡馬爾可夫鏈蒙特卡羅;遺傳算法

中圖分類號：TU721.2? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標志碼：A

文章編號：1674—2974（2020）09—0128—09

Abstract：Layout of construction site facilities has great impact on the project objectives， such as project cost. In this paper， the problem of the construction site facilities layout with many facilities， which is an optimization problem with discrete variables， is considered. Firstly， the problem is transformed to a high-dimensional random sampling problem， and then addressed by a novel meta-heuristic algorithm based on transitional Markov chain Monte Carlo （TMCMC）.? Different from original TMCMC developed for optimization problems with continuous variables， the proposed meta-heuristic algorithm is based on introducing a sequence of probability distribution functions instead of probability density functions， and thus the method for iteratively generating states of Markov chains is modified in the proposed algorithm， in order to meet the specifics of optimization problems with discrete variables. As shown in an illustrative example， compared with the widely used genetic algorithm， the proposed meta-heuristic algorithm can obtain higher improvement in the stability of achieving global optimal solution.

Key words：construction site facilities layout optimization;meta-heuristic algorithm;global optimization algorithm;transitional Markov Chain Monte Carlo;genetic algorithm

施工現場設施布局是施工組織設計的重要任務，其目的是在滿足場地約束條件下，為一組特定的臨時設施分配適當的位置[1]. 施工現場設施布局的科學性和合理性直接關系到施工現場的生產效率和成本節約，進而影響項目成本等目標的實現[2]. 在傳統的工程實踐中，施工現場設施布局決策主要依靠施工人員的經驗，決策的效率較低、不確定性較高[3]. 為提高施工現場設施布局的效率和科學性，國內外的相關學者從不同角度入手，進行了大量的研究工作.

施工現場設施布局問題為組合優化問題，一般利用二次分配問題（Quadratic Assignment Problem，QAP）的模型進行分析，其復雜程度隨布局設施的數量增加而急速上升[4].當問題涉及的設施個數較多時，難以采用枚舉法或解析方法獲得最優解，一般采用元啟發式算法（如遺傳算法、蟻群算法、粒子群算法等）來得到問題的最優解或近似最優解[5]. 針對施工現場設施布局問題，遺傳算法是應用較廣的一種元啟發式算法.Li和Love針對施工現場設施布局優化問題提出了一種以修飾的邊緣重組算子作為交叉算子、以對稱基因交換算子作為變異算子的遺傳算法[6].Adrian等人比較了遺傳算法、粒子群優化算法和蟻群優化算法在不同施工現場設施布局優化問題實例中的性能和效率，結果顯示三種算法在解決施工現場設施布局優化問題時的性能和效率相當[7]. 元啟發式算法具有隨機性，其每次運行獲得的最優解不一定相同（不穩定），但現有元啟發式算法在全局最優解獲取的穩定性上仍有較大的改進空間.

本文基于過渡馬爾可夫鏈蒙特卡羅方法，提出一種針對施工現場設施布局優化問題的新型啟發式全局優化算法. 具體而言，針對涉及設施較多的施工現場設施布局優化問題，本文首先將優化問題轉換為高維空間的隨機抽樣問題，進而利用過渡馬爾可夫鏈蒙特卡羅方法的思想，提出一種高效的全局優化啟發式算法. 通過實例驗證，與應用較廣的遺傳算法相比，本文提出的優化算法在全局最優解獲取的穩定性上有較好的改進.

1? ?施工現場設施布局優化問題模型

施工現場設施布局優化的目的，在于為一組臨時設施分配施工現場的合適位置，以提高施工現場的工作效率，節約成本. 如圖1所示，考慮n個臨時設施和n個預先確定的施工現場位置，并假定任一預先確定的施工現場位置均足以容納任一臨時設施.以降低臨時設施間物流的總移動距離為目的，施工現場設施布局優化問題模型可描述如下：

表1為針對5個臨時設施、5個位置的一個布局方案的置換矩陣表示. 置換矩陣的每一行和每一列中均只有一個元素為1，其他元素均為0，該特性可保證公式（1）中的約束條件自動滿足. 從物理意義上看，公式（1）中約束條件的含義為：一個位置只能布置一個臨時設施，而一個臨時設施也只能被分配到一個位置.

上述模型亦適用于將m個臨時設施分配至n個位置（n > m）的布局優化問題. 此時，可添加（n - m）個虛擬設施，并將與虛擬設施相關的物流頻次fxy賦值為0. 在這種處理方法下，虛擬設施的引入不會影響最終布局優化的結果.

2? ?施工現場設施布局優化問題的新型啟發式算法

針對公式（1）描述的施工現場設施布局優化問題，首先將布局方案的置換矩陣表示轉變為向量表示，進而通過建立適當的概率分布函數，將施工現場設施布局優化這一組合優化問題轉化為根據給定的高度集中、高維概率分布進行隨機抽樣的問題，最后給出利用過渡馬爾可夫鏈蒙特卡羅（Transitional Markov Chain Monte Carlo，TMCMC）方法完成隨機取樣、獲取優化問題最優解的方法.本文考慮的施工現場設施布局優化問題為離散型變量優化問題，故其求解過程需解決的是離散型隨機概率分布的抽樣問題，與原始的TMCMC方法針對的隨機抽樣問題（針對連續型高維概率密度分布）不同.

因此，在利用TMCMC方法建立施工現場設施布局優化問題的新型啟發式算法過程中，需對隨機抽樣對象以及由此引起的馬爾可夫鏈的構造方法進行修改，以適應施工現場設施布局優化問題的不同特性.

2.1? ?布局方案的向量表示

描述施工現場設施布局優化模型的公式（1）中，布局方案表示為n × n的置換矩陣.為便于應用本文所提出的啟發式方法，布局方案采用含有n個元素的行向量θ = [θ1，θ2，…，θn]來表示，其中行向量的第i個元素代表第i個設施被分配的位置標號. 布局方案的向量表示與置換矩陣表示存在一一對應關系.例如，表1的布局方案可表示為[3，5，2，1，4]，即將臨時設施1，2，3，4，5分別分配至位置3，5，2，1，4處.

為滿足公式（1）中的約束條件，布局方案行向量中的所有元素需從n個位置標號中選取，且不允許重復，因此可行布局方案的個數為n！. 對應于任一可行布局方案行向量θ = [θ1，θ2，…，θn]，為計算其在公式（1）中的目標函數值g（θ），可先將布局方案行向量轉化為對應的置換矩陣，進而利用公式（1）中的目標函數表達式進行計算.

2.2? ?組合優化問題與隨機抽樣問題的聯系

本文考慮的施工現場設施布局優化這一組合優化問題，與給定概率分布的隨機抽樣問題存在密切的聯系. 在布局方案的向量表示下，可在可行布局方案集合上定義如下概率分布：

式中：g0為預先選定的無量綱化常數，g（θ）為給定可行布局方案θ下的目標函數值，T為溫度參數.

在公式（2）定義的概率分布下，具有較小目標函數值（θ）的布局方案θ對應于較大的概率分布. 當溫度參數T趨近0時，上述的概率分布（趨近）完全集中在擁有最小目標函數值的可行布局方案（集）上.如對此時的概率分布（對應T趨于0）進行隨機抽樣，進而在隨機抽樣的布局方案中選取最優，則可得到施工現場設施布局優化問題的最優解.但是針對高度集中的概率分布，一般的馬爾可夫鏈蒙特卡羅（Markov Chain Monte Carlo，MCMC）方法的抽樣效率較差，需經過大量過渡階段的樣本才能得到服從目標概率分布的馬爾可夫鏈樣本[8].

2.3? ?過渡馬爾可夫鏈蒙特卡羅方法

過渡馬爾可夫鏈蒙特卡羅（Transitional Markov Chain Monte Carlo，TMCMC）方法是由Ching和Chen提出的、適用于高度集中的高維概率密度分布函數的高效抽樣方法[9]. 該方法在借鑒模擬退火算法[10]思想的基礎上，引入了自適應溫度下降策略和重抽樣方法，以提高算法的抽樣性能.針對公式（2）的離散型概率分布的隨機抽樣問題，利用TMCMC方法，可通過改變溫度參數T，引入一組過渡階段的概率分布（定義在可行布局方案集合上）：

2.4? ?基于TMCMC的新型啟發式優化算法

針對研究的施工現場設施布局優化問題，基于TMCMC，提出的啟發式優化算法的流程如下：

3）重復步驟2，直到滿足迭代終止原則.本文的迭代終止原則取為達到預先設定的迭代次數.

3? ?案例分析

為檢驗基于TMCMC的建議優化算法的性能，并與施工現場設施布局優化領域中采用較廣的遺傳算法進行對比分析，本文采用兩個工程實例進行驗證.驗證模擬實驗使用的計算機硬件配置為處理器 Intel（R）Core（TM）i7-7700、內存16G，軟件配置為MATLAB R2017b.

3.1? ?工程實例一（11項臨時設施）

本實例采用文獻[6]中的施工現場設施布局優化問題，該問題涉及11個臨時設施和11個用以分配臨時設施的位置，并假定每個預定位置都足以容納任一臨時設施. 表2提供了11個臨時設施的具體信息和編號. 設施中的側門（設施8）和正門（設施11）通常在開始施工之前就已經確定，在設施分配過程中正門和側門的位置不會發生變化.但是其它設施與正門及側門的相對位置仍會影響布局的物流移動總距離（模型的目標函數），因此側門和正門不能從模型的考察設施中排除，仍需作為模型中的一種特殊約束存在.

該施工現場設施布局優化問題的模型可根據公式（1）建立. 其中，設施間物流頻次（一天內）參數fxy（x，y = 1，…，11）如表3所示，例如，設施1（現場辦公室）與設施2（臨時支架車間）一天內的物流頻次為f12 = 5，設施6與設施8一天內的物流頻次為f68 = 8. 位置間的距離參數dij（i，j = 1，…，11）如表4所示，例如，位置1與位置7間的距離為d17 = 47米，位置4與位置5間的距離為d45 = 7米. 在該案例的布局優化模型中，側門（設施8）和正門（設施11）固定安排在位置1和位置10內，要求公式（1）增加約束條件δ8，1 = 1和δ11，10 = 1，對應的布局方案向量表示θ = [θ1，θ2，…，θ11]中要求元素θ8 = 1，θ11 = 10.

該設施布局優化問題需考慮將9個設施分配在9個位置，故問題的可行解（布局方案）個數為9！=362 880.通過枚舉法可得到問題的最優目標函數值為6 273 m.針對本實例問題，基于TMCMC的建議優化算法的參數中，無量綱化常數g0取值10 000，樣本變異系數取0.3.圖2描述了基于TMCMC的建議優化算法一次典型求解過程（每一階段的樣本個數取100）中最優目標函數值隨迭代階段的變化，圖3描述了該求解過程中溫度參數隨迭代階段的變化.

為檢驗基于TMCMC的施工現場設施布局優化算法的穩定性，表5給出了針對案例問題的500次建議優化算法求解的統計結果. 作為對比，表5也提供了遺傳算法（Genetic Algorithm，GA）的500次求解的統計結果.本文采用的遺傳算法為雙交叉算子遺傳算法，其與傳統遺傳算法相比，更適用于組合優化問題，且性能更優[14]. 其交叉操作采用交叉掩碼和部分映射雜交算子作為雙交叉算子，既能保護優質染色體，又不影響劣質染色體的進化，從而提高種群的收斂速度.其變異操作采用染色體內部變異的方式，即隨機選擇染色體內的兩個基因進行交換.考慮到計算資源對兩種優化算法性能的影響，兩種算法的迭代終止原則均取為迭代次數不超過20代.

由表5可知，當優化算法每代的樣本數取50時，基于TMCMC的建議優化算法的500次獨立運行結果中，有72.4%的頻率可獲得真實最優解（對應目標函數值6273 m），而基于GA的優化算法的相應頻率僅為32.8%.當每代的樣本數增加到100、150和200時，兩種優化算法獲得真實最優解的頻率都隨著樣本數的增加而提高，且基于TMCMC的優化算法獲得真實最優解的頻率更高，這表明基于TMCMC的優化算法具有更好的求解穩定性.

此外，表5也提供了兩種算法獲得的最優解的目標函數值的統計結果（最大值、最小值、平均值及標準差）. 對比可知，在每代樣本數相同的情況下，基于TMCMC的優化算法獲得最優解的目標函數值的最大值（最差情況下）小于基于GA的優化算法的相應數值，且樣本標準差更小，這再次驗證了基于TMCMC的優化算法的求解穩定性. 同時，在每代不同樣本數下兩種算法的單次運行平均耗時如表5中的第8列所示.對比可見，在每代樣本數相同的情況下，基于TMCMC的建議優化算法單次運行平均耗時更短，但性能（獲取全局最優解的穩定性）更優，說明基于TMCMC的優化算法更為高效（與GA算法相比）.

3.2? ?工程實例二（16項臨時設施）

本實例來源于某房地產工程項目，該項目總建筑面積約17.88萬m2，其中地上建筑面積12.88萬m2，地下建筑面積5萬m2. 在主體施工階段需考慮將16個臨時設施分配至16個預定位置內，同樣假定每個預定位置都足以容納任一臨時設施. 16個臨時設施的具體信息和編號如表6所示. 一天內臨時設施間的物流頻次如表7所示，所涉及的位置間的距離如表8所示. 因正門和側門的位置預先已確定，分別分配在位置1（設施8，側門）和位置10（設施11，正門）內.該優化問題需考慮將14個臨時設施分配在14個位置，故問題的可行解個數為14！=8.718 × 1010.

針對本實例問題，基于TMCMC的建議優化算法的參數中，無量綱化常數g0取500 000，樣本變異系數取值0.1.圖4描述了基于TMCMC的建議優化算法一次典型求解過程（每一階段樣本數取1 000）中最優目標函數值隨迭代階段的變化，圖5描述了該求解過程中溫度參數隨迭代階段的變化.為比較建議優化算法和GA算法的性能，表9給出了針對本實例問題的500次建議優化算法和GA算法求解的統計結果. 兩種算法的迭代終止原則均取迭代次數不超過100代. 由于本實例問題可行解的個數過多（14！=8.718×1010），無法采用枚舉法來得到問題的真實最優解，故采用考察中優化算法（建議優化算法和GA算法每代采用不同樣本，獨立運行500次）所有求出“最優解”中的最優者作為“真實全局最優解”，其目標函數值267 577（表9中第5列-最小值中的最小數）作為“真實最優目標函數值”，并以此作為比較建議優化算法和GA算法的基礎.同時，與實例一的問題相比，實例二的設施布局優化問題中可行解的個數為實例一的240 240 （即14！/9?。┍叮瑔栴}復雜程度急劇上升，故在建議優化算法和GA算法中每代的樣本數取較大數值，即表9中的500、1 000、1 500、2 000.

通過對比表9和表5的結果可知，基于TMCMC的建議優化算法和GA算法在實例二中的求解統計結果不如實例一中的結果理想.但考慮到兩個實例問題中差距巨大的可行解個數和復雜程度，上述的結果也較為合理. 同時，由表9可知，當每代的樣本數取500時，基于TMCMC的建議優化算法的500次獨立運行結果中，有41.0%的頻率可獲得“真實全局最優解”（對應目標函數值267 577 m），且其獲得“真實全局最優解”的頻率隨著樣本數的增加而提高. 當每代樣本數取2 000時，其獲得“真實全局最優解”的頻率為80.4%. 作為對比，GA優化算法在每代樣本數取500、1 000、1 500、2 000時獲得“真實全局最優解”的頻率幾乎全部為0，最高值僅為0.6%.此外，由表9可知，在每代樣本數相同的情況下，基于TMCMC的建議優化算法獲得的最優目標函數值的平均值更接近2 675 577 m，且標準差大大小于GA算法的相應數值.由此可見，與GA算法相比，基于TMCMC的優化算法在獲取全局最優解的穩定性上有較大的改進.同時，由表9中第8列兩種算法的單次運行平均耗時的對比可見，與GA算法相比，基于TMCMC的建議優化算法計算效率更高，能夠以更短的單次運行平均耗時獲得更優的性能（獲取全局最優解的穩定性）.

4? ?結? ?論

本文針對涉及較多設施的施工現場布局優化問題，基于TMCMC方法進行啟發式優化算法的研究，主要研究結論如下：

1）在布局方案的向量表示下，可通過合理構造的概率分布函數，將施工現場設施布局優化問題轉化為高維空間中的隨機抽樣問題，進而利用TMCMC方法來進行隨機抽樣、并獲取最優解.

2）為適應離散型變量優化問題的不同特性，本文提出的啟發式算法的框架基礎需從原始TMCMC針對的連續型概率密度分布函數的隨機取樣轉變為離散型概率分布函數的隨機取樣，進而需修改其中的馬爾可夫鏈狀態點的產生方法.

3）通過實例驗證，與應用較廣的GA算法相比，基于TMCMC的啟發式優化算法在全局最優解的獲取穩定性上有較大改進.

參考文獻

[1]? ?YEH I C. Architectural layout optimization using annealed neural network[J]. Automation in Construction，2006，15（4）：531—539.

[2]? ? 宋興蓓. 基于BIM技術的施工現場動態布置研究[D].西安：長安大學經濟與管理學院，2017：2—5.

SONG X B. The study of dynamic construction site layout based on BIM technology application[D]. Xi'an：School of Economics and Management，Chang'an University，2017：2—5. （In Chinese）

[3]? ? 馬筠強. 基于BIM的施工現場布置優化研究[D]. 哈爾濱：哈爾濱工業大學經濟與管理學院，2016：1—6.

MA J Q. Research on construction site layout planning optimization based on BIM[D]. Harbin：School of Management，Harbin Institute of Technology，2016：1—6. （In Chinese）

[4]? ? TATE D M，SMITH A E. Unequal-area facility layout by genetic search [J]. IIE Transactions，1995，27（4）：465—472.

[5]? ? LIAO T W，EGBELU P J，SARKER B R，et al. Metaheuristics for project and construction management - A state-of-the-art review [J]. Automation in Construction，2011，20（5）：491—505.

[6]? ? LI H，LOVE P E D. Site-level facilities layout using genetic algorithms[J]. Journal of Computing in Civil Engineering，1998，12（4）：227—231.

[7]? ? ADRIAN A M，UTAMIMA A，WANG K J. A comparative study of GA，PSO，and ACO for solving construction site layout optimization [J]. KSCE Journal of Civil Engineering，2015，19（3）：520—527.

[8]? ? BECK J L，AU S K. Bayesian updating of structural models and reliability using Markov chain Monte Carlo simulation[J]. Journal of Engineering Mechanics，2002，128（4）：380—391.

[9]? ?CHING J，CHEN Y C. Transitional Markov chain Monte Carlo method for Bayesian model updating，model class selection and model averaging[J]. Journal of Engineering Mechanics，2007，133（7）：816—832.

[10]? KIRKPATRICK S，GELATT C D，VECCHI M P. Optimization by simulated annealing[J]. Science，1983，220（4598）：671—680.

[11]? WANG J，KATAFYGIOTIS L S. Reliability-based optimal design of linear structures subjected to stochastic excitations[J]. Structural Safety，2014，47（2）：29—38.

[12]? WANG J，KATAFYGIOTIS L S，NOORI M N. Reliability-based optimal structural design using transitional Markov chain Monte Carlo [C]// Proceeding of the Asian-Pacific Symposium on Structural Reliability and its Applications（APSSRA 2008）. Hong Kong：HKUST，2008：239—245.

[13]? HASTINGS W K. Monte Carlo sampling methods using Markov chains and their applications[J]. Biometrika，1970，57（1）：97—109.

[14]? WONG C K，FUNG I W，TAM C M. Comparison of using mixed-integer programming and genetic algorithms for construction site facility layout planning[J]. Journal of Construction Engineering and Management，2010，136（10）：1116—1128.