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

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

1 算法應(yīng)用

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

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

1.2 就近搜索算法在小范圍土方調(diào)配中的應(yīng)用

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

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

1.3 Prim/Kruskal 算法

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

2 道路合并

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

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

3 項(xiàng)目案例

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

3.1 模型構(gòu)建

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

3.2 路徑分析

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

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

圖1 樹形圖和鏈表

圖2 路徑布置

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

3.3 算法優(yōu)化

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

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

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

4 結(jié)語

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