土方工程路基箱铺设和道路合并的数字化实时解决方案

黄月勤 （上海华建工程建设咨询有限公司， 上海 200041）

2022年北京冬奥会高山滑雪赛道场地地貌的设计规划吸收了采用弗洛伊德算法所得的土方车辆运输优化结果，使总运输成本较使用传统方式最小化。可以肯定的是，本文作者所指出的基于改良遗传算法的车辆路径规划和全局搜索，在自适应机制下通过递归寻优得到最优方案，降低了非线性环境下车辆的运输成本。这种动态规划思想在建筑工程土方调配中应用可以大大优化土方工程耗费的成本，这已经得到了现代众多学者的认可。然而，在土方调配过程中，可能涉及对土体的剥离再加工、土质归类、土方晾晒回填、土方工程管理上的统筹安排、多标段多方参与、车辆停留装卸，以及气候变化等复杂因素。人、材、机时空的交错叠加更需要压缩重叠的闲置时间。另外，由于土方工程在整个建筑工程中前置性的特点，一旦场地上的主要施工便道修筑完毕后，随意变更已修筑的施工便道需要付出更大的成本代价。前期算法对车辆路径规划的提示依然没有将道路布置成本考虑在内，尤其是对路基箱铺设吊装所耗费成本的考虑。许多算法所得到的结果以得到车辆主要途径路径为目标，却忽略了使用路基箱完成“最后一公里”成本的累积。本文考虑到部分土方工程中主要便道的前置设计和变更代价，结合路基箱铺设移动的灵活性，将局部土方调配动态化应用不同算法，提供一种现代化土方调配新模式，即土方工程路基箱铺设和道路合并的数字化实时解决方案。

1.1 A＊/D＊ 算法的遇障调整优势

土方调配过程中的障碍如堆土/借土场地、河流、建筑物等等将成为算法中的非法地形。在规划路基箱铺设路径过程中，可对于单条线路根据不同的基于搜索的路径规划算法寻找最短路径。很多算法例如基于启发式搜索的 A＊ 家族算法（F=G+H）和基于增量式搜索的 D＊ 等算法，将距离与土方量综合考虑后折算入移动代价（G 和 H），能够有效、实时、快速地在布置路径时根据实际情况避开障碍，根据实际情况变换路径，寻找效率最高的有效最短路径。场地环境随着施工进度不断变化，使用这类算法即可高效地引导路基箱的铺设，在局部区域内实时保障挖填土运输的最佳路径。

1.2 就近搜索算法在小范围土方调配中的应用

就近搜索算法是场地工程土方就近调度路径生成的一种方法。首先，在对场地进行划分网格后，完成网格内填挖量消抵后得到的网格挖填属性；
然后选取起始挖区，通过广度优先搜索的方式搜索起始挖区网格周围与之属性相反且邻近的多个网格。利用深度优先搜索的方式确定算法中联通路及联通路中末端网格节点，并计算次节点对应的末端节点由所述联通路到达所述主节点的距离，按照距离由短到长的顺序将所述次节点的信息排序，生成调度路径信息。当起始挖区阈值（即土方量）就近分配完毕后，将起始挖区切换至下一个属性相反且需要调度的网格，以此类推，迭代计算，直至最后一个网格的土方量分配完毕。通过在搜索过程中，利用最短路径算法中寻找一条最短联通路的计算过程记录就近搜索过程中形成的前驱路径，生成便道。该算法对目标值的影响是通过遍历不同的挖区，生成多个不同的道路方案，并通过计算最终结果，进行比较，选择较优方案。

需要指出的是，由于土方调配的数学模型依然属于运筹学的线性规划问题，其中，运输问题是特殊的线性规划问题，一定能够找到最优解。就近搜索算法所得的结果是特解，因此，包括其他一些采用动态规划思想寻求最优解的算法中，所得出结果也不一定是最优解。故该种算法适用于小范围土方调配而不引起最终的结果值与近优值之间存在过大差距的情况。

1.3 Prim/Kruskal 算法

当把道路抽象为边，挖填目标区抽象为节点时，应用 Prim 算法求解最小生成树规划路径更为便捷合适。在进一步考虑挖填量时，通过节点与边的重要度计算得出路网布置方案，进而依据所得方案快速布置路基箱。采用 Kruskal 算法虽然容易得到与 Prim 算法类似的结果，且在时间复杂度上较 Prim 算法具有一定优势。在实际应用中，土方场地状况瞬息万变，需要根据边数的实时变化来确定采取相适应的算法。

无论是就近搜索算法还是 Prim 算法，亦或其他算法，道路归并的问题很大程度上不可避免，合并后的结果对目标值影响较大，特别是在网格密集的情况下，使用任何一种道路生成方法得到的初步结果，可能都会遇到需要进行道路合并的情况。发生道路合并事件的概率与数据样本数量有关，随场地范围的逐渐扩大而提高，随着网格划分的减小而增加。在发生道路合并时，有更多的算法可以选择，例如：聚类算法、羊毛算法、面积迭代法等。

当路径布置密而紧凑时，多次铺设距离相近且散发的路基箱是多余的，对降低成本无益。以聚类算法为例，聚类算法是首先通过特征选择或变换后形成数据集，再通过聚类算法选择 或设计获得聚类结果，并对其结果进行评价。通过聚类算法合并道路，是一种较好的方案。

本案例选取第十届中国花博会（2021年，上海崇明）主展区场地前期某一时段的土方调配进行方案研究。花博园是中国规模较高的花卉展览，崇明花博园规划了“三区、一心、一轴、六馆、六园”的功能布局，场地占地面积广，土方调配是前期重要的工作之一。

3.1 模型构建

模型建立包括土方调配数学模型建立和土方 BIM 场地模型建立。数学模型的建立以线性规划模型为基础（Z＝,建立运距与土方工程量之间的目标函数，即土方工程量与相应运距的乘积之和最小。为了使 BIM 场地模型更好地服务于基于算法的土方调配，需要定期建立实时土方数字高程模型，可采用无人机、三维扫描等方式。主要流程如下：模型建立→范围划定→确定节点形状→应用算法→计算结果→重复迭代。其中，在模型建立之初借助 Civil 3D 软件计算挖填总量、确定盈余，在边界处设置虚拟挖区，模拟借土入园。通过划分网格确定每个网格区域内挖填属性及方量，并对网格进行编号。

3.2 路径分析

在实施算法前，先将路径初始化，将填区到填区、挖区到挖区之间的距离设置为无穷大。

在就近搜索算法中以（9）号网格为起始挖区，采用链表形式的数据结构，生成便道布置路径图。通过遍历计算，不同的起始挖区可形成不同的路径方案。图 1 为树形图和链表，图 2 为路径布置。

图1 树形图和链表

图2 路径布置

在以（5）号网格为起始点的路径布置方案中有道路合并事件发生，可采取垂直投影分解路径的方法，也可应用聚类算法，提取需要归并的多条线段两端的坐标点，形成二维圆形聚类簇。使用欧式距离作为距离度量方法，分别计算寻找两端坐标点其中一个点到其他所有点的距离之和最小，定位这两个端点并相连，最后将两个端点同其他点以发散的方式连接可以在一定程度上整合路基箱资源。

3.3 算法优化

就近搜索算法具有同时生成路径和方量的特点，但由于其结果作为特解的原因，可以对每一起始网格分别进行布置方案计算，选取最优结果。其他影响计算结果的因素还有边界进场点位选择、网格大小、算法选择等。对结果的比较本质是对算法的选择。本案例中，最终在包括西南展区在内的全局算法应用中，通过遍历不同的起始挖区作为评价指标得出若干种不同的目标值，通过路径距离乘以每条路径上分配的土方量加总计算，计算得出近优值 Z = 17496 348。图 3为基于 Prim 的就近搜索算法便道路径。

图3 基于 Prim 的就近搜索算法便道路径

鉴于主展区有河流贯穿，位于底部 1/4 处，以图 6 为例显示有 4 条路径需要穿越河流，而在设计图纸上，大花核心区仅一处设计有花舞双桥。另造桥梁成本巨大，因此，这 4 条路径均需通过花舞双桥。此时采用 A＊ 算法或 D＊ 算法，通过障碍设置，能够得出通过梁桥的最佳路径。同样，在外借土进场时，展区边界成为土方车辆进场路线的边界障碍，A＊ 或 D＊ 算法同样适用。

对主展区采用不同的算法可以得出不同的结果，对结果的择优选择可以确定所采用的对应算法。根据场地环境的变化，即土方调配场地随进度迭代缩小计算范围，通过重新划定调配边界，识别障碍，配合土方高程 BIM 模型的扫描重建，算法给予了土方道路合并和路基箱布置的实时性。花博会的案例表明，基于算法的路基箱实时布置和场地调配数字化可以激发调配方案的灵活性。依据计算机拟合结果，随用随铺，多头并进，进一步降低路基箱的吊装运输成本以及土方调配的成本。基于算法的道路合并则进一步提高了算法对周边环境的适应性。这种方法也可推广至其他领域。