施工现场设施布局优化问题的新型启发式算法

2020-10-11王家王洋邓铁军刘可心

湖南大学学报（自然科学版） 2020年9期

王家，王洋，邓铁军，2†，刘可心

（1.湖南大学土木工程学院，湖南长沙 410082；2.湖南大学设计研究院有限公司，湖南长沙 410082）

施工现场设施布局是施工组织设计的重要任务，其目的是在满足场地约束条件下，为一组特定的临时设施分配适当的位置[1].施工现场设施布局的科学性和合理性直接关系到施工现场的生产效率和成本节约，进而影响项目成本等目标的实现[2].在传统的工程实践中，施工现场设施布局决策主要依靠施工人员的经验，决策的效率较低、不确定性较高[3].为提高施工现场设施布局的效率和科学性，国内外的相关学者从不同角度入手，进行了大量的研究工作.

施工现场设施布局问题为组合优化问题，一般利用二次分配问题（Quadratic Assignment Problem，QAP）的模型进行分析，其复杂程度随布局设施的数量增加而急速上升[4].当问题涉及的设施个数较多时，难以采用枚举法或解析方法获得最优解，一般采用元启发式算法（如遗传算法、蚁群算法、粒子群算法等）来得到问题的最优解或近似最优解[5].针对施工现场设施布局问题，遗传算法是应用较广的一种元启发式算法.Li 和Love 针对施工现场设施布局优化问题提出了一种以修饰的边缘重组算子作为交叉算子、以对称基因交换算子作为变异算子的遗传算法[6].Adrian 等人比较了遗传算法、粒子群优化算法和蚁群优化算法在不同施工现场设施布局优化问题实例中的性能和效率，结果显示三种算法在解决施工现场设施布局优化问题时的性能和效率相当[7].元启发式算法具有随机性，其每次运行获得的最优解不一定相同（不稳定），但现有元启发式算法在全局最优解获取的稳定性上仍有较大的改进空间.

本文基于过渡马尔可夫链蒙特卡罗方法，提出一种针对施工现场设施布局优化问题的新型启发式全局优化算法.具体而言，针对涉及设施较多的施工现场设施布局优化问题，本文首先将优化问题转换为高维空间的随机抽样问题，进而利用过渡马尔可夫链蒙特卡罗方法的思想，提出一种高效的全局优化启发式算法.通过实例验证，与应用较广的遗传算法相比，本文提出的优化算法在全局最优解获取的稳定性上有较好的改进.

1 施工现场设施布局优化问题模型

施工现场设施布局优化的目的，在于为一组临时设施分配施工现场的合适位置，以提高施工现场的工作效率，节约成本.如图1 所示，考虑n 个临时设施和n 个预先确定的施工现场位置，并假定任一预先确定的施工现场位置均足以容纳任一临时设施.以降低临时设施间物流的总移动距离为目的，施工现场设施布局优化问题模型可描述如下：

其中任一布局方案可表示为一个n×n 的置换矩阵，δxi（x，i=1，…，n）代表置换矩阵第x 行第i 列的元素.当设施x 被分配至位置i 时，δxi=1，否则δxi=0.系数fxy（x，y=1，…，n）代表设施x 和y 之间物流的频次，系数dij（i，j=1，…，n）代表位置i 和j 之间的距离.

图1 典型施工场地及预定位置示意图Fig.1 Typical construction site and predetermined locations

表1 为针对5 个临时设施、5 个位置的一个布局方案的置换矩阵表示.置换矩阵的每一行和每一列中均只有一个元素为1，其他元素均为0，该特性可保证公式（1）中的约束条件自动满足.从物理意义上看，公式（1）中约束条件的含义为：一个位置只能布置一个临时设施，而一个临时设施也只能被分配到一个位置.

表1 典型布局方案的置换矩阵表示（5 个设施，5 个位置）Tab.1 Permutation matrix representation for a typical layout with 5 facilities and 5 locations

上述模型亦适用于将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，引入一组过渡阶段的概率分布（定义在可行布局方案集合上）：

式中：hi（θ）为第i 阶段的概率分布（对应温度参数Ti），温度参数逐渐递减T0＞T1＞…＞Tm，由第0 阶段的温度参数T0=∞逐渐减小到目标的温度参数Tm=0+（正向接近0）.由式（3）可知，当T0=∞时，h0（θ）为均匀分布，其抽样较为简单，当Tm=0+时，hm（θ）高度集中于全局最优解，其抽样较为困难.TMCMC 以满足均匀分布h0（θ）的样本{θ10，θ20，…，θN0}为起点，通过下述的迭代操作，来得到服从概率分布hm（θ）的样本{θ1m，θ2m，…，θNm}，进而得到问题的最优解.

给定服从第i 阶段概率分布hi（θ）的样本{θ1i，θ2i，…，θNi}，迭代操作首先确定下一阶段的温度参数Ti+1，进而产生服从概率分布hi+1（θ）（对应Ti+1）的样本{θ1i+1，θ2i+1，…，θNi+1}[11，12].考虑给定样本{θ1i，θ2i，...，θNi}上概率分布函数hi+1（θ）与hi（θ）的比值：

当Ti+1与Ti相比降低较少时，比值函数在样本{θ1i，θ2i，…，θNi}上的取值差异很小，而当Ti+1与Ti相比降低较多时，比值函数在样本{θ1i，θ2i，…，θNi}上的取值差异较大.因此，TMCMC 采用比值函数值w（θki）（k=1，2，…，N）的样本变异系数（样本标准差与样本均值的比值）来动态控制相邻两阶段的温度降低幅度，即选择下一阶段的温度参数Ti+1，使得比值函数值w（θki）（k=1，2，…，N）的样本变异系数等于预先设定的常数.样本变异系数一般取0.01～0.5，当问题规模较小、需投入的计算资源较少时，宜取较大值，当问题规模较大、需投入的计算资源较多时，宜取较小值.

确定第i+1 阶段的温度参数Ti+1后，TMCMC 利用重抽样方法（Re-sampling Method）和MCMC 方法来产生服从第i+1 阶段概率分布的样本{θ1i+1，θ2i+1，…，θNi+1}.根据温度参数Ti+1可计算给定样本{θ1i，θ2i，…，θNi}对应的比值函数w（θki）（k=1，2，…，N），重抽样方法针对样本{θ1i，θ2i，…，θNi}按如下概率

进行重抽样来得到服从第i+1 阶段概率分布hi+1（θ）的样本{θ1i+1，θ2i+1，…，θNi+1}.即样本θki（k=1，2，…，N）被选中作为第i+1 阶段样本的概率为p（k）.在上述的N 次选择过程中，对应选中概率p（k）较大的样本θki有较大可能被选中多于一次.若θki被选中m ＞1 次，则利用MCMC 方法产生一个以θki为起点、以hi+1（θ）为稳态分布、具有m 个状态点的马尔可夫链，来代替被重复选中多次的样本θki，作为第i+1 阶段的m 个样本.

2.4 基于TMCMC 的新型启发式优化算法

针对研究的施工现场设施布局优化问题，基于TMCMC，提出的启发式优化算法的流程如下：

1）选定无量纲化常数g0，并根据公式（2）构造不同温度参数下的概率分布.随机产生服从第0 阶段概率分布h0（θ）（对应温度参数T0=∞，均匀分布）的N 个可行布局方案{θ10，θ20，…，θN0}.

2）根据当前阶段i（i=0，1，…）的温度参数Ti及服从概率分布hi（θ）的N 个可行布局方案{θ1i，θ2i，…，θNi}，确定第i+1 阶段的温度参数Ti+1，以确保在样本{θ1i，θ2i，…，θNi}上的比值函数w（θki）（k=1，2，…，N）的样本变异系数等于预先设定的常数.进而利用重抽样方法和MCMC 方法产生服从第i+1 阶段概率分布hi+1（θ）的N 个可行布局方案{θ1i+1，θ2i+1，…，θNi+1}.

如果在重抽样中，第i 阶段的样本θki被选中m＞1 次，则需解决以θki为起点、以hi+1（θ）为稳态分布、具有m 个状态点的马尔可夫链的构造问题.考虑到施工现场设施布局优化问题为离散变量优化问题，相应的随机抽样问题针对的是离散型概率分布，不能采用以高斯分布函数为“建议概率密度分布函数”的Metropolis 方法（原始TMCMC 方法中）来完成马尔可夫链{θ1，θ2，…}的构造工作[13].因此，需对马尔可夫链的构造方法进行修改，采用如下马尔可夫链{θ1，θ2，…}中状态点θk（k=1，2，…）到下一状态点θk+1的迭代操作：

a）随机交换状态点θk中的两个元素，以得到备选状态点ξ.该操作相当于选取“建议概率分布函数”p*（ξ|θk）为离散型均匀分布，可满足对称性要求p*（ξ|θk）=p*（θk|ξ）.

b）计算备选状态点ξ 和当前状态点θk对应的稳态概率分布函数的比值：

c）若比值r≥1，则下一状态点θk+1=ξ；若比值r＜1，则下一状态点θk+1以r 的概率取值为ξ，以（1-r）的概率取值为θk.

3）重复步骤2，直到满足迭代终止原则.本文的迭代终止原则取为达到预先设定的迭代次数.

3 案例分析

为检验基于TMCMC 的建议优化算法的性能，并与施工现场设施布局优化领域中采用较广的遗传算法进行对比分析，本文采用两个工程实例进行验证.验证模拟实验使用的计算机硬件配置为处理器Intel（R）Core（TM）i7-7700、内存16G，软件配置为MATLAB R2017b.

3.1 工程实例一（11 项临时设施）

本实例采用文献[6]中的施工现场设施布局优化问题，该问题涉及11 个临时设施和11 个用以分配临时设施的位置，并假定每个预定位置都足以容纳任一临时设施.表2 提供了11 个临时设施的具体信息和编号.设施中的侧门（设施8）和正门（设施11）通常在开始施工之前就已经确定，在设施分配过程中正门和侧门的位置不会发生变化.但是其它设施与正门及侧门的相对位置仍会影响布局的物流移动总距离（模型的目标函数），因此侧门和正门不能从模型的考察设施中排除，仍需作为模型中的一种特殊约束存在.

表2 临时设施信息（实例一）Tab.2 Information of temporary facilities（Example 1）

该施工现场设施布局优化问题的模型可根据公式（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.

表3 设施间的移动频率fxy（次）（实例一）Tab.3 Movement frequency fxy between facilities（Example 1）

表4 位置间的距离dij（实例一）米Tab.4 Distance dij between locations（Example 1）meter

该设施布局优化问题需考虑将9 个设施分配在9 个位置，故问题的可行解（布局方案）个数为9!=362 880.通过枚举法可得到问题的最优目标函数值为6 273 m.针对本实例问题，基于TMCMC 的建议优化算法的参数中，无量纲化常数g0取值10 000，样本变异系数取0.3.图2 描述了基于TMCMC 的建议优化算法一次典型求解过程（每一阶段的样本个数取100）中最优目标函数值随迭代阶段的变化，图3 描述了该求解过程中温度参数随迭代阶段的变化.

图2 典型求解过程中最优目标函数值随迭代阶段的变化（实例一）Fig.2 Optimal objective function value at different stages in a typical optimization run（Example 1）

图3 典型求解过程中温度参数随迭代阶段变化（实例一）Fig.3 Temperature parameter at different stages in a typical optimization run（Example 1）

为检验基于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独立运行500 次的统计结果（实例一）Tab.5 Statistical results of 500 independent runs using GA and TMCMC-based proposed optimization algorithm（Example 1）

此外，表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.

表6 临时设施信息（实例二）Tab.6 Information of temporary facilities（Example 2）

针对本实例问题，基于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.

表7 设施间的移动频率fxy（次）（实例二）Tab.7 Movement frequency fxy between facilities（Example 2）

表8 位置间的距离dij（实例二）米Tab.8 Distance dij between locations（Example 2） meter

图4 典型求解过程中最优目标函数值随迭代阶段的变化（实例二）Fig.4 Optimal objective function value at different stages in a typical optimization run（Example 2）

图5 典型求解过程中温度参数随迭代阶段变化（实例二）Fig.5 Temperature parameter at different stages in a typical optimization run（Example 2）

表9 基于TMCMC 的建议优化算法和GA 独立运行500 次的统计结果（实例二）Tab.9 Statistical results of 500 independent runs using GA and TMCMC-based proposed optimization algorithm（Example 2）

通过对比表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 的建议优化算法计算效率更高，能够以更短的单次运行平均耗时获得更优的性能（获取全局最优解的稳定性）.