許輝

（中交一公局集團(tuán)華中工程有限公司，湖北武漢 430014）

0. 引言

傳統(tǒng)基建行業(yè)成本高、利潤薄、工期緊張，通過合理的手段進(jìn)行設(shè)計(jì)優(yōu)化、方案深化比選是工程建設(shè)必須考慮的問題。作為建筑施工項(xiàng)目的一個(gè)重要方面，在大型工程建設(shè)中土石方調(diào)配費(fèi)用占工程建安費(fèi)比例很高。但土石方運(yùn)輸作為土石方調(diào)配中的一個(gè)重要步驟，目前卻缺乏有效的針對土石方運(yùn)輸路徑的研究。因此如何合理的規(guī)劃土石方運(yùn)輸路徑，使其在滿足施工現(xiàn)場要求的前提下距離最短，施工成本最低是有必要的。

從20世紀(jì)70年代開始，國內(nèi)外學(xué)者就對線路選型，最短路徑搜尋展開了研究。孫興等通過對GIS系統(tǒng)進(jìn)行二次開發(fā)，建立土石方調(diào)運(yùn)系統(tǒng)，實(shí)現(xiàn)了調(diào)配過程及結(jié)果輸出的實(shí)時(shí)動態(tài)顯示，但其對于調(diào)配路徑的優(yōu)化研究較少。黃丙湖等以總成本最小為目標(biāo)函數(shù)建立模型，綜合考慮施工次序、方向和調(diào)配的土石方量，利用蟻群算法將模型轉(zhuǎn)化為求解最短路徑問題，但其調(diào)配的基本思路還是基于一維蟻群算法的TSP問題，并沒有考慮運(yùn)輸路線中存在的障礙物。繆鹍等基于蟻群算法研究了道路的縱斷面曲線，建立了離散的縱斷面曲線優(yōu)化算法模型，但這種方式計(jì)算速度慢，對于復(fù)雜地形情況下容易產(chǎn)生局部收斂的現(xiàn)象。

針對上述文獻(xiàn)中前人研究的成果，本文提出一種考慮障礙物條件的二維路徑優(yōu)化問題，目標(biāo)是在全局條件下繞過地形圖中設(shè)置的障礙物，自動搜尋一條最短的運(yùn)輸路徑。以荔玉高速21分部1#取土場土石方運(yùn)輸為算例，首先構(gòu)建二維無向網(wǎng)絡(luò)圖，然后通過Dijkstra算法進(jìn)行運(yùn)輸路徑的初始規(guī)劃，最后利用蟻群算法在初始規(guī)劃找尋的節(jié)點(diǎn)間進(jìn)行二次優(yōu)化得到最終的全局最優(yōu)路徑。

1. 初始路徑規(guī)劃研究

工程建設(shè)是一項(xiàng)系統(tǒng)性的、群策群力的活動，每一個(gè)環(huán)節(jié)都串聯(lián)著諸多行業(yè)，其中，物料運(yùn)輸扮演著關(guān)鍵的角色。對于場地活動范圍大、工程量大的施工項(xiàng)目，運(yùn)輸用的施工車輛往往占整體施工機(jī)械很大比例，這種現(xiàn)象在復(fù)雜場地條件下表現(xiàn)的尤為明顯。運(yùn)輸距離的長短、運(yùn)輸速度的快慢不僅影響施工成本，對施工工期也會造成一定的影響。因此，有必要在確定施工場地后規(guī)劃出若干條最優(yōu)的運(yùn)輸路線，縮短運(yùn)輸車輛行駛的距離，達(dá)到降低施工成本，提高施工進(jìn)度的目的。本文在MATLAB中構(gòu)建一套考慮障礙物的二維地形，建立全局最短路徑的數(shù)學(xué)模型，通過給定的出發(fā)點(diǎn)和到達(dá)點(diǎn)，程序能自動規(guī)劃出最短路徑。

荔玉高速公路是《廣西高速公路網(wǎng)規(guī)劃》“四縱六橫三支線”布局中“縱二”荔浦至鐵山港高速公路的組成部分，也是國家高速公路網(wǎng)G59廣西境段重要組成部分。荔玉21分部1#取土場位于藤縣境內(nèi)，平均坡度達(dá)到50%。與棄土點(diǎn)間東西向長度約6km，南北向長度約5km。取土場內(nèi)需要保護(hù)的樹木較多，用地紅線嚴(yán)格控制。因此，對該項(xiàng)目而言，場地內(nèi)土石方調(diào)配和運(yùn)輸是制約施工進(jìn)度的關(guān)鍵因素。

1.1 二維無向網(wǎng)絡(luò)圖建立

對于目標(biāo)求解的最優(yōu)路徑問題，需要對原始的地形圖信息進(jìn)行抽象化建模，首先提取1#取土場地形圖中的障礙物信息、通道信息等建立多邊形圖，圖中黑色部分為障礙物區(qū)域，車輛不能通行。白色區(qū)域?yàn)檐囕v可通行區(qū)域，如圖1所示。

圖1 1#取土場地形提取圖

根據(jù)Maklink圖論理論，通過構(gòu)造若干條自由鏈接線線可以將二維空間分割成若干不相交的區(qū)域，但要求二維空間中創(chuàng)建的圖形都是凸多邊形[1]。圖1中創(chuàng)建的多邊形并不完全是凸多邊形，不滿足Maklink圖創(chuàng)建的條件，因此需要將該多邊形進(jìn)行凸化。一般而言，凸化方式為在現(xiàn)有的黑色障礙物多邊形基礎(chǔ)上向外擴(kuò)展s長度。將擴(kuò)展后的障礙物定義為含有緩沖區(qū)的障礙，即在實(shí)際汽車運(yùn)輸過程中，即使車輛沿著黑色障礙物區(qū)域邊界行使也不會與實(shí)際障礙物發(fā)生碰撞。

一般而言，構(gòu)造的Maklink自由鏈接線時(shí)應(yīng)滿足如下要求：（1）任意的2個(gè)凸多邊形的連線不得與障礙物有交點(diǎn)；（2）每一個(gè)凸多邊形頂點(diǎn)至少需要引出一條鏈接線與一個(gè)多邊形頂點(diǎn)相交；（3）鏈線之間不得交叉；（4）凸多邊形頂點(diǎn)可以與空間邊界相交。在凸化后的模型上，作頂點(diǎn)到邊界的垂線及相鄰2個(gè)凸多邊形障礙物頂點(diǎn)之間的連線，構(gòu)建Maklink圖。

構(gòu)建完Maklink圖后選取所有自由鏈接線的中點(diǎn)、平面邊界點(diǎn)、起點(diǎn)和終點(diǎn)，互相兩兩連接，就構(gòu)成無向網(wǎng)絡(luò)圖。1#取土場無向網(wǎng)絡(luò)圖如圖2所示。

圖2 1#取土場無向網(wǎng)絡(luò)圖

1.2 基于Dijkstra算法的初始路徑規(guī)劃

建立包含土石方運(yùn)輸出發(fā)點(diǎn)和到達(dá)點(diǎn)的1#取土場無向網(wǎng)絡(luò)圖后，為了避免后期蟻群算法進(jìn)行二次優(yōu)化時(shí)計(jì)算量過大，需先對無向網(wǎng)絡(luò)圖進(jìn)行初始路徑規(guī)劃，以確定車輛行駛的大致方向。Dijkstra算法是典型的兩點(diǎn)間最短路徑算法，用于計(jì)算非負(fù)權(quán)值圖中一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。引入2個(gè)距離集合（S、U），其中S集合包含已求出的最短路徑的點(diǎn)，U集合包含未求出最短路徑的點(diǎn)。初始化2個(gè)集合，從U集合中找出路徑最短的點(diǎn)，加入S集合中并更新U集合路徑。循環(huán)執(zhí)行上述步驟，直至遍歷所有節(jié)點(diǎn)，得到節(jié)點(diǎn)之間的最短路徑。

在凸化后的無向網(wǎng)絡(luò)圖采用Dijkstra算法得到初始路徑經(jīng)過的鏈路為：S→V14→V9→V11→V13→V3→V8→V12→V5→T，初始化后的路徑規(guī)劃結(jié)果如圖3所示（圖中黃色線段為采用Dijkstra算法初始規(guī)劃的二維空間次優(yōu)路線）。

圖3 Dijkstra初始規(guī)劃路徑結(jié)果

2. 蟻群算法路徑優(yōu)化研究

2.1 蟻群算法路徑優(yōu)化流程

蟻群算法是由Dorigo.M等人在20世紀(jì)90年代初通過模擬螞蟻在搜尋食物時(shí)的行為開發(fā)出的一套算法，用螞蟻行走的路徑表示代求問題的可行解。行走路徑較短的螞蟻由于能首先獲得食物，因此在沿途中釋放的信息素較多。后方的螞蟻總是趨向于沿著信息素較多的路徑前進(jìn)，隨著迭代次數(shù)的增加，較短路徑上聚積的信息素濃度逐漸增加。選擇該路徑的螞蟻個(gè)數(shù)也增加[2]。最終，整個(gè)螞蟻群體都會在正反饋的激勵(lì)下聚集到最短路徑上，此時(shí)對應(yīng)待求解問題的最優(yōu)解。蟻群算法最優(yōu)路徑搜尋邏輯如圖4所示。

圖4 蟻群算法流程圖

蟻群算法優(yōu)化尋找路徑參數(shù)集合（h1，h2，...，hd），使得在離散化的空間里得到最短的路徑。假設(shè)共有m只螞蟻從起點(diǎn)出發(fā)到達(dá)終點(diǎn)，當(dāng)螞蟻在鏈線Li上搜索下一個(gè)節(jié)點(diǎn)Li+1時(shí)，方法為：

選擇所有螞蟻經(jīng)過路徑中長度最短的一段，更新該條路徑上每一個(gè)點(diǎn)的信息素，即。其中，為最短路徑的長度，ρ為[0，1]區(qū)間的可調(diào)參數(shù)。

2.2 工程算例與優(yōu)化分析

以1#棄土場為例，模擬單次車輛運(yùn)輸最短路徑。其中出發(fā)點(diǎn)位于G2地塊S點(diǎn)，目的地位于D3地塊T點(diǎn)。由前文Maklink圖和Dijkstra算法得到的二維初始規(guī)劃路徑圖引入蟻群算法，對每一個(gè)Dijkstra節(jié)點(diǎn)進(jìn)行二次優(yōu)化，其中選擇的螞蟻種群數(shù)量20，信息素選擇概率為0.8，循環(huán)次數(shù)500次。得到的圖像如圖5所示。

圖5 路徑優(yōu)化結(jié)果圖

圖中省略了障礙物之間的Maklink線，并標(biāo)注了各地塊的相對位置。圖中黃線部分為蟻群算法優(yōu)化前的次優(yōu)運(yùn)輸路徑（即只通過Dijkstra算法在二維空間中規(guī)劃的路徑）。圖中紅線部分為經(jīng)過蟻群算法優(yōu)化后的最短運(yùn)輸路線圖。通過在MATLAB中的計(jì)算，得出的從出發(fā)點(diǎn)S到終點(diǎn)T的最短距離為4.077km。從圖中看出，最短的路徑為從G2地塊的S點(diǎn)出發(fā)，直線切過G1G2地塊交匯處，連接G1地塊拐點(diǎn)后貼著北側(cè)向下經(jīng)過D2地塊，從D2地塊沿直線到達(dá)終點(diǎn)T。

從算法性能上說，迭代500次時(shí)計(jì)算消耗時(shí)間3.6363s。通過蟻群算法，在前50次迭代過程中搜尋的路徑長度迅速收斂，在第240次迭代后，搜尋的路徑長度趨于穩(wěn)定，算法整體性能較高。蟻群算法迭代搜尋示意圖如圖6所示。

圖6 蟻群算法迭代搜尋示意圖

從經(jīng)濟(jì)性上說，原規(guī)劃的次優(yōu)汽車運(yùn)輸路徑長度為5.14km，通過蟻群算法的二次優(yōu)化，將汽車運(yùn)輸路徑長度縮減至4.077km。路線長度減少20.7%，能取得較好的經(jīng)濟(jì)效益。當(dāng)汽車運(yùn)輸路線復(fù)雜途徑障礙物較多時(shí)，通過蟻群算法優(yōu)化后的路線長度優(yōu)勢更為明顯?？梢詾榻窈笃囘\(yùn)輸路線優(yōu)化提供理論依據(jù)。

3. 結(jié)論

本文從運(yùn)輸路線建模，土石方運(yùn)輸路線初始規(guī)劃和土石方運(yùn)輸路線二次優(yōu)化調(diào)整等3個(gè)階段展開施工過程中汽車運(yùn)輸路線規(guī)劃研究。首先利用地形信息進(jìn)行建模，產(chǎn)生擴(kuò)展的凸多邊形無向網(wǎng)絡(luò)圖。其次利用Maklink圖和Dijkstra算法獲得初始規(guī)劃路徑。最后采用蟻群算法對路徑進(jìn)行進(jìn)一步優(yōu)化得到滿足要求的汽車運(yùn)輸線路[3]。

由仿真結(jié)果可知，本文采用的蟻群算法可以快速實(shí)現(xiàn)路線規(guī)劃，與傳統(tǒng)的手動進(jìn)行路線規(guī)劃相比，本文采用的路線規(guī)劃方法能從全局的角度出發(fā)得到最短的路線，取得較好的效果。但本文僅考慮車輛在二維平面內(nèi)的運(yùn)輸路線，并未考慮場地高程給汽車運(yùn)輸帶來的路程增加影響，這將在下一步繼續(xù)進(jìn)行研究。