土方工程路基箱鋪設和道路合并的數字化實時解決方案

黃月勤 （上海華建工程建設咨詢有限公司， 上海 200041）

2022年北京冬奧會高山滑雪賽道場地地貌的設計規劃吸收了采用弗洛伊德算法所得的土方車輛運輸優化結果，使總運輸成本較使用傳統方式最小化。可以肯定的是，本文作者所指出的基于改良遺傳算法的車輛路徑規劃和全局搜索，在自適應機制下通過遞歸尋優得到最優方案，降低了非線性環境下車輛的運輸成本。這種動態規劃思想在建筑工程土方調配中應用可以大大優化土方工程耗費的成本，這已經得到了現代眾多學者的認可。然而，在土方調配過程中，可能涉及對土體的剝離再加工、土質歸類、土方晾曬回填、土方工程管理上的統籌安排、多標段多方參與、車輛停留裝卸，以及氣候變化等復雜因素。人、材、機時空的交錯疊加更需要壓縮重疊的閑置時間。另外，由于土方工程在整個建筑工程中前置性的特點，一旦場地上的主要施工便道修筑完畢后，隨意變更已修筑的施工便道需要付出更大的成本代價。前期算法對車輛路徑規劃的提示依然沒有將道路布置成本考慮在內，尤其是對路基箱鋪設吊裝所耗費成本的考慮。許多算法所得到的結果以得到車輛主要途徑路徑為目標，卻忽略了使用路基箱完成“最后一公里”成本的累積。本文考慮到部分土方工程中主要便道的前置設計和變更代價，結合路基箱鋪設移動的靈活性，將局部土方調配動態化應用不同算法，提供一種現代化土方調配新模式，即土方工程路基箱鋪設和道路合并的數字化實時解決方案。

1 算法應用

1.1 A＊/D＊ 算法的遇障調整優勢

土方調配過程中的障礙如堆土/借土場地、河流、建筑物等等將成為算法中的非法地形。在規劃路基箱鋪設路徑過程中，可對于單條線路根據不同的基于搜索的路徑規劃算法尋找最短路徑。很多算法例如基于啟發式搜索的 A＊ 家族算法（F=G+H）和基于增量式搜索的 D＊ 等算法，將距離與土方量綜合考慮后折算入移動代價（G 和 H），能夠有效、實時、快速地在布置路徑時根據實際情況避開障礙，根據實際情況變換路徑，尋找效率最高的有效最短路徑。場地環境隨著施工進度不斷變化，使用這類算法即可高效地引導路基箱的鋪設，在局部區域內實時保障挖填土運輸的最佳路徑。

1.2 就近搜索算法在小范圍土方調配中的應用

就近搜索算法是場地工程土方就近調度路徑生成的一種方法。首先，在對場地進行劃分網格后，完成網格內填挖量消抵后得到的網格挖填屬性；然后選取起始挖區，通過廣度優先搜索的方式搜索起始挖區網格周圍與之屬性相反且鄰近的多個網格。利用深度優先搜索的方式確定算法中聯通路及聯通路中末端網格節點，并計算次節點對應的末端節點由所述聯通路到達所述主節點的距離，按照距離由短到長的順序將所述次節點的信息排序，生成調度路徑信息。當起始挖區閾值（即土方量）就近分配完畢后，將起始挖區切換至下一個屬性相反且需要調度的網格，以此類推，迭代計算，直至最后一個網格的土方量分配完畢。通過在搜索過程中，利用最短路徑算法中尋找一條最短聯通路的計算過程記錄就近搜索過程中形成的前驅路徑，生成便道。該算法對目標值的影響是通過遍歷不同的挖區，生成多個不同的道路方案，并通過計算最終結果，進行比較，選擇較優方案。

需要指出的是，由于土方調配的數學模型依然屬于運籌學的線性規劃問題，其中，運輸問題是特殊的線性規劃問題，一定能夠找到最優解。就近搜索算法所得的結果是特解，因此，包括其他一些采用動態規劃思想尋求最優解的算法中，所得出結果也不一定是最優解。故該種算法適用于小范圍土方調配而不引起最終的結果值與近優值之間存在過大差距的情況。

1.3 Prim/Kruskal 算法

當把道路抽象為邊，挖填目標區抽象為節點時，應用 Prim 算法求解最小生成樹規劃路徑更為便捷合適。在進一步考慮挖填量時，通過節點與邊的重要度計算得出路網布置方案，進而依據所得方案快速布置路基箱。采用 Kruskal 算法雖然容易得到與 Prim 算法類似的結果，且在時間復雜度上較 Prim 算法具有一定優勢。在實際應用中，土方場地狀況瞬息萬變，需要根據邊數的實時變化來確定采取相適應的算法。

2 道路合并

無論是就近搜索算法還是 Prim 算法，亦或其他算法，道路歸并的問題很大程度上不可避免，合并后的結果對目標值影響較大，特別是在網格密集的情況下，使用任何一種道路生成方法得到的初步結果，可能都會遇到需要進行道路合并的情況。發生道路合并事件的概率與數據樣本數量有關，隨場地范圍的逐漸擴大而提高，隨著網格劃分的減小而增加。在發生道路合并時，有更多的算法可以選擇，例如：聚類算法、羊毛算法、面積迭代法等。

當路徑布置密而緊湊時，多次鋪設距離相近且散發的路基箱是多余的，對降低成本無益。以聚類算法為例，聚類算法是首先通過特征選擇或變換后形成數據集，再通過聚類算法選擇 或設計獲得聚類結果，并對其結果進行評價。通過聚類算法合并道路，是一種較好的方案。

3 項目案例

本案例選取第十屆中國花博會（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＊ 算法同樣適用。

4 結語

對主展區采用不同的算法可以得出不同的結果，對結果的擇優選擇可以確定所采用的對應算法。根據場地環境的變化，即土方調配場地隨進度迭代縮小計算范圍，通過重新劃定調配邊界，識別障礙，配合土方高程 BIM 模型的掃描重建，算法給予了土方道路合并和路基箱布置的實時性。花博會的案例表明，基于算法的路基箱實時布置和場地調配數字化可以激發調配方案的靈活性。依據計算機擬合結果，隨用隨鋪，多頭并進，進一步降低路基箱的吊裝運輸成本以及土方調配的成本。基于算法的道路合并則進一步提高了算法對周邊環境的適應性。這種方法也可推廣至其他領域。