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

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

1 算法應用

1.1 A＊/D＊ 算法的遇障調整優(yōu)勢

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

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

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

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

1.3 Prim/Kruskal 算法

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

2 道路合并

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

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

3 項目案例

本案例選取第十屆中國花博會（2021年，上海崇明）主展區(qū)場地前期某一時段的土方調配進行方案研究?；ú﹫@是中國規(guī)模較高的花卉展覽，崇明花博園規(guī)劃了“三區(qū)、一心、一軸、六館、六園”的功能布局，場地占地面積廣，土方調配是前期重要的工作之一。

3.1 模型構建

模型建立包括土方調配數(shù)學模型建立和土方 BIM 場地模型建立。數(shù)學模型的建立以線性規(guī)劃模型為基礎（Z＝,建立運距與土方工程量之間的目標函數(shù)，即土方工程量與相應運距的乘積之和最小。為了使 BIM 場地模型更好地服務于基于算法的土方調配，需要定期建立實時土方數(shù)字高程模型，可采用無人機、三維掃描等方式。主要流程如下：模型建立→范圍劃定→確定節(jié)點形狀→應用算法→計算結果→重復迭代。其中，在模型建立之初借助 Civil 3D 軟件計算挖填總量、確定盈余，在邊界處設置虛擬挖區(qū)，模擬借土入園。通過劃分網(wǎng)格確定每個網(wǎng)格區(qū)域內挖填屬性及方量，并對網(wǎng)格進行編號。

3.2 路徑分析

在實施算法前，先將路徑初始化，將填區(qū)到填區(qū)、挖區(qū)到挖區(qū)之間的距離設置為無窮大。

在就近搜索算法中以（9）號網(wǎng)格為起始挖區(qū)，采用鏈表形式的數(shù)據(jù)結構，生成便道布置路徑圖。通過遍歷計算，不同的起始挖區(qū)可形成不同的路徑方案。圖 1 為樹形圖和鏈表，圖 2 為路徑布置。

圖1 樹形圖和鏈表

圖2 路徑布置

在以（5）號網(wǎng)格為起始點的路徑布置方案中有道路合并事件發(fā)生，可采取垂直投影分解路徑的方法，也可應用聚類算法，提取需要歸并的多條線段兩端的坐標點，形成二維圓形聚類簇。使用歐式距離作為距離度量方法，分別計算尋找兩端坐標點其中一個點到其他所有點的距離之和最小，定位這兩個端點并相連，最后將兩個端點同其他點以發(fā)散的方式連接可以在一定程度上整合路基箱資源。

3.3 算法優(yōu)化

就近搜索算法具有同時生成路徑和方量的特點，但由于其結果作為特解的原因，可以對每一起始網(wǎng)格分別進行布置方案計算，選取最優(yōu)結果。其他影響計算結果的因素還有邊界進場點位選擇、網(wǎng)格大小、算法選擇等。對結果的比較本質是對算法的選擇。本案例中，最終在包括西南展區(qū)在內的全局算法應用中，通過遍歷不同的起始挖區(qū)作為評價指標得出若干種不同的目標值，通過路徑距離乘以每條路徑上分配的土方量加總計算，計算得出近優(yōu)值 Z = 17496 348。圖 3為基于 Prim 的就近搜索算法便道路徑。

圖3 基于 Prim 的就近搜索算法便道路徑

鑒于主展區(qū)有河流貫穿，位于底部 1/4 處，以圖 6 為例顯示有 4 條路徑需要穿越河流，而在設計圖紙上，大花核心區(qū)僅一處設計有花舞雙橋。另造橋梁成本巨大，因此，這 4 條路徑均需通過花舞雙橋。此時采用 A＊ 算法或 D＊ 算法，通過障礙設置，能夠得出通過梁橋的最佳路徑。同樣，在外借土進場時，展區(qū)邊界成為土方車輛進場路線的邊界障礙，A＊ 或 D＊ 算法同樣適用。

4 結語

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