基于蟻群算法的二維場地土石方運輸路徑優化研究

許輝

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

0. 引言

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

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

針對上述文獻中前人研究的成果，本文提出一種考慮障礙物條件的二維路徑優化問題，目標是在全局條件下繞過地形圖中設置的障礙物，自動搜尋一條最短的運輸路徑。以荔玉高速21分部1#取土場土石方運輸為算例，首先構建二維無向網絡圖，然后通過Dijkstra算法進行運輸路徑的初始規劃，最后利用蟻群算法在初始規劃找尋的節點間進行二次優化得到最終的全局最優路徑。

1. 初始路徑規劃研究

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

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

1.1 二維無向網絡圖建立

對于目標求解的最優路徑問題，需要對原始的地形圖信息進行抽象化建模，首先提取1#取土場地形圖中的障礙物信息、通道信息等建立多邊形圖，圖中黑色部分為障礙物區域，車輛不能通行。白色區域為車輛可通行區域，如圖1所示。

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

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

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

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

圖2 1#取土場無向網絡圖

1.2 基于Dijkstra算法的初始路徑規劃

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

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

圖3 Dijkstra初始規劃路徑結果

2. 蟻群算法路徑優化研究

2.1 蟻群算法路徑優化流程

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

圖4 蟻群算法流程圖

蟻群算法優化尋找路徑參數集合（h1，h2，...，hd），使得在離散化的空間里得到最短的路徑。假設共有m只螞蟻從起點出發到達終點，當螞蟻在鏈線Li上搜索下一個節點Li+1時，方法為：

選擇所有螞蟻經過路徑中長度最短的一段，更新該條路徑上每一個點的信息素，即。其中，為最短路徑的長度，ρ為[0，1]區間的可調參數。

2.2 工程算例與優化分析

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

圖5 路徑優化結果圖

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

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

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

從經濟性上說，原規劃的次優汽車運輸路徑長度為5.14km，通過蟻群算法的二次優化，將汽車運輸路徑長度縮減至4.077km。路線長度減少20.7%，能取得較好的經濟效益。當汽車運輸路線復雜途徑障礙物較多時，通過蟻群算法優化后的路線長度優勢更為明顯。可以為今后汽車運輸路線優化提供理論依據。

3. 結論

本文從運輸路線建模，土石方運輸路線初始規劃和土石方運輸路線二次優化調整等3個階段展開施工過程中汽車運輸路線規劃研究。首先利用地形信息進行建模，產生擴展的凸多邊形無向網絡圖。其次利用Maklink圖和Dijkstra算法獲得初始規劃路徑。最后采用蟻群算法對路徑進行進一步優化得到滿足要求的汽車運輸線路[3]。

由仿真結果可知，本文采用的蟻群算法可以快速實現路線規劃，與傳統的手動進行路線規劃相比，本文采用的路線規劃方法能從全局的角度出發得到最短的路線，取得較好的效果。但本文僅考慮車輛在二維平面內的運輸路線，并未考慮場地高程給汽車運輸帶來的路程增加影響，這將在下一步繼續進行研究。