基于蟻群算法的農村公共交通線路研究

劉合偉，羅璟

（650504 云南省 昆明市 昆明理工大學 機電工程學院）

0 引言

隨著社會經濟的不斷發展，道路交通相關問題成為廣大學者的研究熱點。研究城市交通的相關學術文獻不斷增多，學術成果不斷被應用。相比而言，農村交通方面的研究明顯不足。目前，農村交通方面的文獻大多是交通安全方面的，對于農村交通的研究廣度不夠。隨著近年來我國農村的不斷發展與新農村改造建設不斷推進，農村生活在各方面朝著城市靠近。一個地方良好的社會經濟狀況往往可以從交通方面體現。城市經過多年建設與發展，交通等各方面得以完善，人們出行更加便捷。農村發展相對滯后，交通落后于城市。隨著近幾年新農村建設，農村的變化日新月異。由于農村的經濟情況與私人交通工具的限制，人們的出行遠沒有城市方便，農村對公共交通的需求更加迫切，農村公共交通建設的線路規劃與研究是一個亟待探討的課題。

農村公共交通線路的規劃與研究遠沒有城市相關的研究充分，對城市公共交通相關的線路研究與農村獨特的環境背景相結合進行農村公共交通線路的研究也許會取得不錯的成果。對于交通線路路徑與線路的相關理論方法有廣度優先算法、狄克斯特拉算法、蟻群算法等，這些算法在相關研究上都取得了不錯的成果。潘星[1]對層次策略和廣度優先算法進行改進，使其更加貼合多模式公共交通路徑的研究；狄克斯特拉算法在路徑相關的研究，如AGV 路徑研究、最短線路問題研究等都取得相關成果[2-3]。而蟻群算法在路徑與線路相關的問題上，由于其智能性，使得其研究更加廣泛。例如物流配送路徑的優化研究上[4-5]，車間物料配送路徑上[6]，還有交通線路相關的問題上[7-8]等等。上述路徑相關的算法及其改進使得對于路徑與線路相關的問題得以解決。

公共交通線路問題是一個復雜的非線性的規劃問題，其求解需要將現代路徑研究方法與計算機相結合。蟻群算法是模擬蟻群覓食機制的智能算法，因其在解決路徑規劃問題中具備的優異性能而被廣泛應用[9-10]。但傳統的蟻群算法由于正反饋、單一搜索能力等原因，容易陷入局部最優解、收斂速度慢等情況[11]，且相關問題由于其獨特的環境背景使得傳統的蟻群算法不能完全適應。本文在結合農村公共交通建設相關的環境背景下，對傳統的蟻群算法進行改進，使其能對農村公共交通線路的研究進行更好的匹配。

1 方法介紹

蟻群算法（AG）是一種模擬螞蟻覓食行為的模擬優化算法，它是由意大利學者Dorigo 等于1991 年首先提出，并首先使用在解決TSP（旅行商問題）上[12]。經過多年的發展，其已經陸續滲透到其他領域中，比如圖著色問題[13-14]、集成電路問題[15-16]、通訊網絡中的問題[17]等。其算法基本流程如圖1 所示。

圖1 蟻群算法流程圖Fig.1 Flow chart of ant colony algorithm

在蟻群算法中常用參數：螞蟻數量m，信息素常量Q，迭代次數t，信息素因子α，啟發函數因子，β，信息素揮發因子ρ。

在圖1 中需要計算狀態概率，以選擇下一節點，計算狀態概率公式一般為：

圖1 中信息素濃度更新為

式中：τij（t+1）——第t+1 次迭代后i 到j 節點上的信息素量；（1-ρ）——信息素殘留系數。

式中：Lk——第k 只螞蟻一次循環的總路徑，當迭代次數達到要求迭代次數時停止，輸出最終最優解。

2 改進蟻群算法及算例分析

2.1 問題描述

由于交通線路的復雜性，將開通農村公共交通線路問題在圖上用相應的節點及線段表示，構建一個簡單的圖用以說明，如圖2 所示。

圖2 農村線路模擬圖Fig.2 Rural route mimic map

圖2 中，A 為公共交通起始點，B、C、D、E、F 為村莊，G 為終點。車輛需從A 經過多個村莊到達終點G。線段上數字為各節點之間距離，節點上字母后面數字為該村莊人流量單位數。一般公共交通線路其需要遵守線路覆蓋主要客流走廊的原則，線路長度適中原則。由于農村的特殊環境背景，使得建筑與人流量不像城市那么密集，通常以一個村莊為聚集點，在同等距離的情況下，人口多的村莊應比人口少的村莊優先選擇。由于線路需要遵守長度適中原則，在線路長度保證一定大于最高要求標準線路時，線路長度越短越好。即要使得從A 到G 線路長度最短，且盡量經過人口多的村莊。本文假設從A 到G 的任意路徑其長度都大于最高要求線路長度標準。

2.2 改進蟻群算法求解

由于線路的研究涉及距離與客流量，單純的蟻群算法求最短路徑不能夠完全滿足公共交通線路需遵守的原則，應在求最短路徑時加入客流量這個變量，即要滿足路徑較短的情況下經過客流量盡量大的地區。由于路徑與流量是2 個不同的變量，將人口流量與路徑長度相關聯，使其轉化為可以比較的變量。例如可以假設20 個單位的人口流量為1 個單位的長度，40 個單位的人口流量為2 個單位長度等，人口越多其長度越大，在此稱其為流量長度。再將路徑長度與流量長度按照不同的權重來進行路線的規劃。優化后的目標函數為

式中：H——從起始節點到目標節點所經過的路徑總數；dij——端點i，j 之間的路徑長度；gij——i，j 兩點間的流量長度；h——兩端所連接節點之間最短路徑；μ和v——路徑長度和流量長度的權重系數，其滿足關系μ+v=1。

傳統蟻群算法在解決TSP（旅行商問題）上通常以路徑長度最短為最優目標，本文所提農村公共交通路徑的優化其以路徑與人口流量關聯后的最小值為目標，其目標值如式（4）所示。為了使蟻群算法能夠按既定的目標進行優化搜索，需要根據優化后的目標值對信息啟發因子的計算方法進行改進，其計算方法改進后如式（5）所示：

另外，在一般蟻群算法中，揮發因子ρ的取值對信息素濃度的大小有十分重大的影響。在信息素濃度更新過程中，若揮發因子ρ的取值過大，將導致還未被選取過的路徑上的信息素濃度快速減小到0，容易導致較優路徑被排除，這樣就較大程度地限制了蟻群算法的全局搜索能力；若揮發因子ρ的取值過小，將會使得各路徑上信息素含量差別較小，導致算法的收斂速度降低[5]。因此，本文在蟻群算法迭代計算過程中動態調整揮發因子大小，使其盡量減小揮發因子過大或者過小造成的問題。在對信息素濃度進行動態改進后，其更新方法如式（6）、式（7）：

在式（6）與式（7）中，φ（t）為關于迭代次數t 的正比例函數，φ（t）的值伴隨著迭代次數t 的增加而增加。

2.3 最優路徑MATLAB 實現

對于農村公交線路問題的模擬圖2 進行求解，在只考慮路徑的情況下，排除人流量的影響后，對圖2 進行蟻群算法求解。使用MATLAB 進行程序運行后，可以得到最優路徑為A-B-E-G，或者A-D-E-G，或者A-D-F-G，這3條路徑其長度相同，總路徑為25 個單位。在進行蟻群算法的多次迭代后可以得到迭代次數與目標值的迭代關系圖，如圖3 所示。

圖3 蟻群算法迭代圖Fig.3 Ant colony algorithm iteration graph

從圖3 可以看到目標值隨迭代次數的變化情況，最后目標值穩定在25。

在考慮人流量后，將人流量參數加入蟻群算法求解。根據實際情況將人口流量轉化為流量長度，再根據式（4）—式（7）對原蟻群算法進行優化。根據對路徑長度與流量的重視程度，可以分別對這2 個變量進行權重賦值。本文假設路徑與人口流量的權重分別為0.8 與0.2。在通過計算后，將得到的參數與值代入螞蟻算法中，然后在MATLAB 上對路徑進行求解，可以得到最優路徑為A-D-E-G。在進行蟻群算法的多次迭代后，可以得到迭代次數與目標值的迭代關系圖，如圖4 所示。

圖4 引入人流量的蟻群算法迭代圖Fig.4 Ant colony algorithm iterative diagram introducing human traffic

從圖4 中可以看到，在引入流量路徑后，其目標值穩定在19 個單位。在加入人口流量優化后的蟻群算法后，其與優化前相比，其最優路徑從3條變為1 條。將優化后的路徑A-D-E-G 與優化前的路徑A-B-E-G 和A-D-F-G 進行對比可以發現，盡管這3 條路徑其長度一樣，但優化后求得的路徑A-D-E-G 其經過的節點人流明顯高于另外2 條。從以上分析中可以看出，在傳統蟻群算法中引入人流參數可以在某種程度上對線路的規劃研究發揮一定的作用。

3 結論

本文以一簡單網圖模擬農村公共交通線路為例，針對公共交通線路需遵守的人流量原則，在原蟻群算法的基礎上引入人流量參數對農村公共交通線路進行研究。從中可以看到，在結合人流量后，最優路徑發生改變，說明引入人流量的蟻群算法對于農村公共交通線路的研究非常必要。然而由于農村公共交通的建設涉及多線路、多班次，以及人口流量的復雜化等問題，如何合理地將多線路、多班次及人口流量相結合以對農村公共交通問題進行優化，仍有待進一步研究。