基于蟻群算法的農(nóng)村公共交通線路研究

劉合偉，羅璟

（650504 云南省 昆明市 昆明理工大學(xué) 機(jī)電工程學(xué)院）

0 引言

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

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

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

1 方法介紹

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

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

在蟻群算法中常用參數(shù)：螞蟻數(shù)量m，信息素常量Q，迭代次數(shù)t，信息素因子α，啟發(fā)函數(shù)因子，β，信息素?fù)]發(fā)因子ρ。

在圖1 中需要計算狀態(tài)概率，以選擇下一節(jié)點(diǎn)，計算狀態(tài)概率公式一般為：

圖1 中信息素濃度更新為

式中：τij（t+1）——第t+1 次迭代后i 到j(luò) 節(jié)點(diǎn)上的信息素量；（1-ρ）——信息素殘留系數(shù)。

式中：Lk——第k 只螞蟻一次循環(huán)的總路徑，當(dāng)?shù)螖?shù)達(dá)到要求迭代次數(shù)時停止，輸出最終最優(yōu)解。

2 改進(jìn)蟻群算法及算例分析

2.1 問題描述

由于交通線路的復(fù)雜性，將開通農(nóng)村公共交通線路問題在圖上用相應(yīng)的節(jié)點(diǎn)及線段表示，構(gòu)建一個簡單的圖用以說明，如圖2 所示。

圖2 農(nóng)村線路模擬圖Fig.2 Rural route mimic map

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

2.2 改進(jìn)蟻群算法求解

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

式中：H——從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)所經(jīng)過的路徑總數(shù)；dij——端點(diǎn)i，j 之間的路徑長度；gij——i，j 兩點(diǎn)間的流量長度；h——兩端所連接節(jié)點(diǎn)之間最短路徑；μ和v——路徑長度和流量長度的權(quán)重系數(shù)，其滿足關(guān)系μ+v=1。

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

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

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

2.3 最優(yōu)路徑MATLAB 實(shí)現(xiàn)

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

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

從圖3 可以看到目標(biāo)值隨迭代次數(shù)的變化情況，最后目標(biāo)值穩(wěn)定在25。

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

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

從圖4 中可以看到，在引入流量路徑后，其目標(biāo)值穩(wěn)定在19 個單位。在加入人口流量優(yōu)化后的蟻群算法后，其與優(yōu)化前相比，其最優(yōu)路徑從3條變?yōu)? 條。將優(yōu)化后的路徑A-D-E-G 與優(yōu)化前的路徑A-B-E-G 和A-D-F-G 進(jìn)行對比可以發(fā)現(xiàn)，盡管這3 條路徑其長度一樣，但優(yōu)化后求得的路徑A-D-E-G 其經(jīng)過的節(jié)點(diǎn)人流明顯高于另外2 條。從以上分析中可以看出，在傳統(tǒng)蟻群算法中引入人流參數(shù)可以在某種程度上對線路的規(guī)劃研究發(fā)揮一定的作用。

3 結(jié)論

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