交通網(wǎng)絡(luò)最優(yōu)路徑搜索的蟻群算法

周竹萍 易富君

1.南京理工大學(xué)，交通工程系，南京 210094

2.招商局重慶交通科研設(shè)計(jì)院有限公司，重慶 404100

0 引言

動(dòng)態(tài)最優(yōu)路徑搜索算法是智能交通系統(tǒng)（ITS）技術(shù)應(yīng)用的關(guān)鍵問題之一。目前的路徑誘導(dǎo)系統(tǒng)不夠高效，在路徑選擇算法方面還不完善，缺乏實(shí)時(shí)性高、有效性強(qiáng)的路徑搜索算法，故交通最優(yōu)路徑選擇問題一直是各國交通領(lǐng)域投資研究的重點(diǎn)問題。

最優(yōu)路徑選擇是指在給定的城市道路網(wǎng)中尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)之間的最優(yōu)路徑的問題。解決該問題的經(jīng)典算法是Dijkstra 算法，是一種靜態(tài)的局部最優(yōu)算法[1]。該算法簡(jiǎn)單、易于實(shí)現(xiàn)，但也存在如下的局限性：在網(wǎng)絡(luò)節(jié)點(diǎn)和路徑較多的情況下，搜索效率會(huì)大大降低，有時(shí)甚至找不到最短路徑，且對(duì)于路徑權(quán)值隨時(shí)間動(dòng)態(tài)變化的動(dòng)態(tài)網(wǎng)絡(luò)，如反映路徑堵塞和暢通信息的實(shí)時(shí)交通系統(tǒng)網(wǎng)絡(luò)就不適用。

隨著群智能技術(shù)的出現(xiàn)，基于群體仿生理論的蟻群算法為最短路徑選擇問題提供了一個(gè)新的解決方法。但是，由于蟻群算法本身的局限性，容易陷入局部最優(yōu)解，且其道路信息素初始值固定，使算法收斂速度較慢[2]。近年來，我國學(xué)者提出了一系列的改進(jìn)思路，如高尚、吳霜華等都考慮在蟻群算法中引入混沌理論[3-4]，黃貴玲則在原始算法中加入直線優(yōu)化啟發(fā)信息，趙寶江提出了一種基于自適應(yīng)路徑選擇和動(dòng)態(tài)信息素更新的蟻群算法[5]。國外的重要研究包括：Guenther Fuellerer，Yuvraj Gajpal等也在信息素局部更新中加入幾種其它啟發(fā)式算法以提高算法效率，Alberto V.Donati 通過改進(jìn)更新規(guī)則完成了兩個(gè)及多個(gè)目標(biāo)的優(yōu)化[6-8]等。本文分析了傳統(tǒng)蟻群算法的不足，改進(jìn)了信息素更新方式，使算法更滿足求解交通系統(tǒng)的最優(yōu)路徑問題。

1 問題概述與模型

如果把城市道路網(wǎng)中的道路起始點(diǎn)、目標(biāo)點(diǎn)和交叉路口等表示為節(jié)點(diǎn)，把道路表示為連接節(jié)點(diǎn)的弧（邊），把道路的長度、通行時(shí)間和擁塞程度等屬性表示為弧的權(quán)，那么道路網(wǎng)就可以被抽象成為一個(gè)帶權(quán)的有向圖，如圖，1 所示。

圖1 由節(jié)點(diǎn)和弧構(gòu)成的有向道路網(wǎng)絡(luò)圖Fig.1 Traffic network composed of nodes and arcs with direction

在賦權(quán)有向圖G 上，一條以i 為始點(diǎn)，j 為終點(diǎn)的路徑是一個(gè)弧的序列，其中前一個(gè)弧的終點(diǎn)是后一個(gè)弧的起點(diǎn)，且第一個(gè)弧的起點(diǎn)是i，最后一個(gè)弧的終點(diǎn)是j，可用一個(gè)有序的點(diǎn)集來描述一條路。一條路的費(fèi)用是這條路徑上所有弧的費(fèi)用之和。用賦權(quán)有向圖來表示路徑的費(fèi)用即為該賦權(quán)有向圖中這條路徑上所有路徑權(quán)值之和。

給定帶權(quán)有向圖G=(V,{E})，其中V 是包含n個(gè)頂點(diǎn)的頂點(diǎn)集，E 是包含m 條弧段的集合，＜v,w＞是從v 到w 的弧，c(v,w)是?。紇,w＞的非負(fù)權(quán)值，設(shè) vs，vt為V 中的頂點(diǎn)，Pst={vo=vs,v1=,…,vn=vt}為V 中由vs到 vt的一條路徑，則路徑 Pst的權(quán)值總和TW(Pst)可表示為[9]：

最優(yōu)路徑問題就是指在帶權(quán)有向圖中，尋找從指定起點(diǎn)到終點(diǎn)的一條具有最小權(quán)值總和的路徑問題，即尋找一條路徑使得TW(Pst)最小。

在交通路網(wǎng)最優(yōu)路徑選擇中進(jìn)行路徑選擇并不完全同于在賦權(quán)有向圖中求最短路徑問題的方法。在實(shí)際的交通中，路段的流量實(shí)時(shí)變化，單向行駛、交叉口轉(zhuǎn)向限制等也越來越復(fù)雜。伴隨著不同的實(shí)際應(yīng)用目的，最優(yōu)路徑規(guī)劃中也有很多優(yōu)化標(biāo)準(zhǔn)，如最短行車距離、最少行車時(shí)間、最低費(fèi)用等。同時(shí)還要求有較快的速度和較高的效率。這就對(duì)最優(yōu)路徑選擇算法本身提出了一定的要求。只有選擇合適的算法才能找到滿足條件的最優(yōu)路徑。

2 蟻群算法原理與模型

2.1 基本原理

蟻群優(yōu)化算法（簡(jiǎn)稱蟻群算法），1991 年由Marco Dorigo 和他的同事1991 年首先提出[10-11]。作為一種多agent 的方法，較好地解決了一些復(fù)雜的組合優(yōu)化問題，如 TSP（Traveling salesman problem）問題以及指派問題。蟻群算法主要模擬螞蟻的食物搜索行為，當(dāng)螞蟻在食物源和巢穴之間行走時(shí)，會(huì)在路上存儲(chǔ)信息素。螞蟻可以感知到環(huán)境中該物質(zhì)的存在及其強(qiáng)度，并在選擇移動(dòng)時(shí)，傾向于選擇信息素濃度高的方向。當(dāng)某條路徑較短時(shí)，會(huì)有較多的螞蟻使用這條路徑，使得該路徑上被存放較多的信息素，從而吸引更多的螞蟻使用這一路徑。最終，信息素濃度最高的路徑標(biāo)志出食物源和巢穴之間的最短路徑。

2.2 基本模型

以求解平面n 個(gè)城市的問題（用（0，1，…，n-1）表示城市序號(hào)）來說明基本蟻群算法。引入如下記號(hào)：m 為蟻群中的螞蟻數(shù)；dij為城市和城市之間的距離；τij(t)為t 時(shí)刻路徑(i,j)上的信息量，n為城市的數(shù)量。

初始時(shí)刻，各條路徑上的信息素相等，設(shè)τij(0)=C，（C 為常數(shù)），螞蟻 k(k=1,2,…,m)在運(yùn)動(dòng)過程中根據(jù)各條路徑上的信息素量決定轉(zhuǎn)移方向?；鞠伻核惴ㄋ褂玫臓顟B(tài)轉(zhuǎn)移規(guī)則被稱為隨機(jī)比例規(guī)則，它給出了位于城市i 的螞蟻轉(zhuǎn)移到城市j 的概率。為在t 時(shí)刻螞蟻k 由城市i 轉(zhuǎn)移到城市j 的狀態(tài)轉(zhuǎn)移概率：

式中：

α——螞蟻在行進(jìn)過程中所積累的信息素濃度對(duì)它已選擇路徑所起的作用大小，當(dāng)α=0 時(shí)，算法就是傳統(tǒng)的貪心算法；

β——ηij的重要程度，當(dāng)β=0 時(shí)，算法就成了純粹的正反饋的啟發(fā)式算法，可通過試驗(yàn)來確定參數(shù)α，β 的最優(yōu)組合；

ηij——由城市i 轉(zhuǎn)移到城市j 的期望程度，可根據(jù)某種啟發(fā)式算法而定，例如，可以取

Ak——螞蟻k 下一步允許走過的城市的集合，它隨螞蟻k 的行進(jìn)過程而動(dòng)態(tài)改變。

蟻群在覓食過程中，一方面通過螞蟻的行走會(huì)在路徑上留下新的信息素，另一方面隨著時(shí)間的推移已有的信息素會(huì)逐漸揮發(fā)，所以，各條路徑上的信息素會(huì)根據(jù)蟻群的行動(dòng)和時(shí)間變化不斷更新。經(jīng)過n 個(gè)時(shí)刻，螞蟻k 可走完所有的城市，完成一次循環(huán)。此時(shí)，要根據(jù)下式對(duì)各路徑上的信息素濃度作更新：

式中：

τij(t)——隨時(shí)間的推移會(huì)逐步衰減；

ρ——信息素?fù)]發(fā)參數(shù)，其作用是使個(gè)體螞蟻忘掉過去從蟻群搜索過程中獲得的一部分經(jīng)驗(yàn)，避免過早收斂于一個(gè)局部最優(yōu)解[12]，用1-ρ 表示它的衰減程度；

Δτij——路徑上信息素濃度的變化量，

式中，Δτijk表示螞蟻k 在本次循環(huán)中在城市i 和城市j 之間留下的信息素濃度，其計(jì)算方法根據(jù)計(jì)算模型而定。

Dorigo Macro 曾給出了不同的蟻群算法模型，分別稱為 ant-cycle 模型（亦稱蟻周系統(tǒng)模型）、ant-quantity 模型（亦稱蟻量系統(tǒng)模型）和ant-density模型（亦稱蟻密系統(tǒng)模型），它們的差別在于Δτijk(t)的求法不同[13-14]。蟻密系統(tǒng)模型信息素增量為固定值 Q；而在蟻量系統(tǒng)模型中，信息素增量的值為，與路徑(i,j)的長度有關(guān)；在蟻周系統(tǒng)模型中，信息素增量為，它與具體的 dij無關(guān)，只與 Q和搜索路線有關(guān)。這3 種模型中，ant-cycle 模型最適用于最短路徑問題[8]。在ant-cycle 模型中：

式中：Q 是信息素強(qiáng)度，它影響算法的收斂速度；Lk是第k 只螞蟻在本次循環(huán)中所走路徑的長度。

2.3 采用蟻群算法求解最優(yōu)路徑的可行性

蟻群算法本質(zhì)是一種并行的算法。螞蟻搜索的過程彼此獨(dú)立，只通過信息素進(jìn)行間接的通訊。由于大規(guī)模的并行計(jì)算，可以顯著減少計(jì)算時(shí)間。它是一種正反饋算法。正反饋的存在，使得搜索收斂速度加快。它很容易與多種啟發(fā)式算法結(jié)合，以改善算法的性能。它具有較強(qiáng)的魯棒性。對(duì)算法模型稍加修改，便可以應(yīng)用于其他問題。

蟻群算法已被成功地應(yīng)用于許多可表達(dá)在圖表上尋找最佳路徑的問題。交通系統(tǒng)的最優(yōu)路徑選擇與螞蟻覓食行為類似。將車輛的起始點(diǎn)看作蟻巢，目的地看作是螞蟻所要尋找的食物源，車輛在從起始點(diǎn)開始經(jīng)過一些路段、節(jié)點(diǎn)，最終到達(dá)目的地在路徑選擇的過程中，個(gè)體車輛根據(jù)本身的判斷選擇所需要的路徑行駛。在這里整個(gè)路網(wǎng)就是一個(gè)有向圖，車輛就是具有智能行為的人工螞蟻，并且該人工螞蟻只是找到從起始點(diǎn)到終止點(diǎn)的路徑，并不返回到原來的起始點(diǎn)[15]。通過對(duì)交通過程的抽象，將交通中實(shí)際的耗費(fèi)作為啟發(fā)信息，這樣可以建立起一個(gè)進(jìn)行最優(yōu)路徑選擇的人工蟻群系統(tǒng)。

3 基于信息素更新方式改進(jìn)的蟻群算法

為了克服基本蟻群算法的缺陷，通過自適應(yīng)地改變算法的信息素更新方式，可以在保證收斂速度的前提下提高解的全局性；通過改進(jìn)路徑選擇策略和模型，可以使該算法更符合交通網(wǎng)絡(luò)的運(yùn)行規(guī)律，提高算法的自適應(yīng)能力。

3.1 信息素限定原則

引入信息素限定規(guī)則，將每條邊上的信息量限定在[τmin,τmax]之間，即為Max-Min Ant System 的主要思路。設(shè)置了信息素強(qiáng)度的下限 τmin，所以選擇某些邊弧的概率雖然可能性非常小，但永遠(yuǎn)不會(huì)為零，這樣就減少了停滯行為出現(xiàn)的機(jī)會(huì)，從而使螞蟻能進(jìn)行更高程度的搜索；因?yàn)榛鞠伻核惴ㄔ趯ふ易顑?yōu)路徑時(shí)，并不像交通規(guī)劃一樣要考慮路網(wǎng)的承受能力，因此，改進(jìn)的蟻群算法中也設(shè)置了信息素強(qiáng)度的上限 τmax，使得這兩者信息素的差別不會(huì)趨向于無窮大。

3.2 信息素局部更新算法的改進(jìn)

道路網(wǎng)絡(luò)中還存在這樣的特性：某條路徑的出行時(shí)間會(huì)隨著交通流量的增加而增加。因此，將螞蟻行走過程中的信息素更新方式設(shè)置為局部更新原則。局部信息素更新的作用是使已選的邊對(duì)后來的螞蟻具有較小的吸引力，從而使螞蟻對(duì)沒有被選中的邊有更強(qiáng)的探索能力。實(shí)驗(yàn)表明，局部更新規(guī)則可以有效避免螞蟻收斂到同一路徑[16]。MMAS為TSP 問題的解決提出了信息素軌跡平滑機(jī)制，讓軌跡濃度的增加與最大濃度 τmax和當(dāng)前濃度 τij之間的差值成正比。信息素軌跡平滑機(jī)制較好地考慮了交通網(wǎng)絡(luò)中路徑的不同狀態(tài)特性，但是，計(jì)算較為復(fù)雜。本文采用了平滑機(jī)制的思路，根據(jù)不同狀態(tài)設(shè)置不同的模型形式，簡(jiǎn)化為用分段函數(shù)表示。當(dāng)螞蟻從城市i 轉(zhuǎn)移到城市j 后，路徑(i,j)上的信息素量按下式進(jìn)行更新：

式中：ξ∈[0,1]的一個(gè)參數(shù)；τ0為一個(gè)很小的數(shù)，經(jīng)驗(yàn)觀測(cè)值為；n 為城市數(shù)目；Lbest為該次循環(huán)中最短路徑長度；τm為臨界值，反映系統(tǒng)的狀態(tài)，根據(jù)具體的實(shí)驗(yàn)情況而定。

3.3 信息素全局更新模型的改進(jìn)

螞蟻根據(jù)信息素留下的多少選擇路段，而當(dāng)所有螞蟻都選擇某路段時(shí)，可能造成某路段的負(fù)荷過大，形成所謂的交通擁堵現(xiàn)象。雖然，在前述的局部信息修改的過程中考慮了路網(wǎng)容量的特性，但當(dāng)交通擁堵越嚴(yán)重，根據(jù)ant-cycle 模型公式（5）可得螞蟻在路網(wǎng)上留下的信息量仍然是最大的，即其它的螞蟻根據(jù)公式（2）繼續(xù)選擇該路段，最終造成該路段崩潰[17]?，F(xiàn)有研究較多的是對(duì)公式（4）做必要的調(diào)整，引進(jìn)路段上的阻抗函數(shù)。由于本文討論的是動(dòng)態(tài)最優(yōu)路徑搜索問題，所以要引進(jìn)能反映實(shí)時(shí)路況的廣義路阻來計(jì)算[18]。廣義路阻是在各種因素(如路段平均行駛速度、車輛行駛的通暢性、路段擁擠度、路口排隊(duì)長度和平均延誤等)影響下,路段行駛時(shí)間和路口延誤的綜合表征量。路段(i,j)上的廣義路阻 T(i,j)計(jì)算式為：

式（7）中，t(i,j)為路段(i,j)的行駛時(shí)間；r(i,j)為在路段(i,j)上的車輛平均延誤。式(8)中，t0(i,j)表示交通流為零時(shí)路段(i,j)的行駛時(shí)間；V 為路段交通量當(dāng)量值；C 為路段實(shí)用通行能力；k1、k2分別為回歸參數(shù)，根據(jù)道路交通量、車速調(diào)查數(shù)據(jù)用最小二乘法確定。式(9)中，r1為均勻延誤，r2為過飽和延誤，即隨機(jī)到達(dá)的增量延誤所引起的附加延誤：其中，k3、k4為常數(shù)；T 為周期長度；λ 為進(jìn)口道綠信比；X 為交叉口飽和度；C 為進(jìn)口道實(shí)用飽和通行能力；S 為路口影響修正系數(shù)。

所以，在全局信息素更新規(guī)則中公式（5）改進(jìn)為：

式中，T(i,j)是路段(i,j)上的廣義路阻。

式（10）作為信息素更新規(guī)則可以使廣義路阻較大的路段獲得的信息素更新量較小。

在廣義路阻的基礎(chǔ)上，運(yùn)用該算法可以完成最優(yōu)路徑規(guī)劃的多種優(yōu)化標(biāo)準(zhǔn)要求，如最短行車距離、最少行車時(shí)間、平均車速、最低費(fèi)用等。

4 計(jì)算機(jī)仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)算法

根據(jù)蟻群優(yōu)化算法的思想，本文的最優(yōu)路徑搜索過程分幾步進(jìn)行：首先，初始化起始節(jié)點(diǎn)、終止節(jié)點(diǎn)和交通量，確定循環(huán)次數(shù)，讓一定數(shù)量的人工螞蟻的每個(gè)螞蟻代表一定的交通量并分批置于交通出行始點(diǎn)上進(jìn)行循環(huán)，初始循環(huán)可以隨機(jī)地讓人工螞蟻進(jìn)行路徑的選擇。每循環(huán)一次人工螞蟻根據(jù)上一次循環(huán)信息素軌跡分布概率進(jìn)行路徑的選擇，逐個(gè)在路網(wǎng)上移動(dòng)，從起點(diǎn)到達(dá)終點(diǎn)的螞蟻成功完成一次循環(huán)，并在相應(yīng)路徑上留下成功的信息素軌跡，局部更新軌跡強(qiáng)度，并檢查信息素?cái)?shù)量是否處于規(guī)定的范圍之內(nèi)。然后，當(dāng)一批螞蟻完成循環(huán)后，尋找最優(yōu)路徑，再對(duì)軌跡強(qiáng)度全局更新。至此，完成了一次最優(yōu)路徑搜索。最后尋找全局最優(yōu)解，即到當(dāng)前迭代次數(shù)為止。在所建立的所有局部最優(yōu)解中，值最小的解作為當(dāng)前迭代次數(shù)的全局最優(yōu)解。當(dāng)有足夠的螞蟻數(shù)量和循環(huán)次數(shù)，交通系統(tǒng)將向平衡分配方向發(fā)展，結(jié)果亦更加趨近于最優(yōu)解。

針對(duì)本文將要解決的實(shí)際的動(dòng)態(tài)交通路徑問題，給出蟻群算法進(jìn)行路徑選擇的算法步驟如下：

Step 1 信息初始化 初始化將螞蟻逐個(gè)放置于起點(diǎn)；初始化α，β，k，tmax，τij(0)，m，Q等系數(shù)。其中 tmax為最大迭代次數(shù)。

蟻群算法中的參數(shù)設(shè)定目前尚無理論上的依據(jù)，參數(shù)Q，C，α，β，ρ 可以用實(shí)驗(yàn)確定其最優(yōu)組合。經(jīng)驗(yàn)結(jié)果為：1≤α≤5；1≤β≤5；0.5≤ρ≤0.99，ρ 取0.7 左右為佳；1≤Q≤10000[19]。

Step 2 選擇原則 對(duì)每只螞蟻用轉(zhuǎn)移概率在禁忌表中沒有的匯點(diǎn)中選擇要移動(dòng)的下一個(gè)匯點(diǎn)，位于第i 個(gè)節(jié)點(diǎn)的螞蟻k，按（3）式選擇策略選擇邊(i,j)。將所選匯點(diǎn)放入禁忌表每只螞蟻環(huán)游一圈后，計(jì)算這只螞蟻在此環(huán)游路徑的綜合系數(shù)值。

Step 3 局部更新原則 當(dāng)螞蟻選中邊(i,j)后，就更新邊(i,j)上的信息量，即每當(dāng)螞蟻選中一條邊后，就按（7）式更新減少邊上的信息量，從而增加螞蟻選擇其它邊的概率。

Step 4 局部搜索 當(dāng)m 只螞蟻從起點(diǎn)到終點(diǎn)搜索完后，則求得m 個(gè)解。為了盡可能遍歷所有解，分別在這些解的鄰域中，采用局部搜索算法，求出局部最優(yōu)解。

Step 5 全局更新原則 當(dāng)所有的m 只螞蟻都得到局部最優(yōu)解后（否則跳入Step2），按照（4）、（5）、（11）式全局更新信息量，即全局更新路段流量，更新路段阻抗。比較所有環(huán)游得出的系數(shù)值，找出最好的環(huán)游路徑。

Step 6 求全局最優(yōu)解 到當(dāng)前迭代次數(shù)為止，在所建立的所有局部最優(yōu)解中，值最小的解作為當(dāng)前迭代次數(shù)的全局最優(yōu)解。

Step 7 不斷迭代直到滿足停止的條件。

4.2 算例仿真

給定一個(gè)如圖2 所示的路網(wǎng)，為簡(jiǎn)化計(jì)算，路網(wǎng)直接標(biāo)定了實(shí)時(shí)的廣義路阻值（邊上的數(shù)字），求該時(shí)刻從起點(diǎn)①到終點(diǎn)?在該時(shí)刻的最優(yōu)路徑。

圖2 示例的路網(wǎng)Fig.2 Example network

按照4.1 中的算法步驟進(jìn)行計(jì)算，參數(shù)取值見表1。在軟件Matlab 7.0 環(huán)境下實(shí)現(xiàn)，迭代5 次即搜索到了最優(yōu)路徑：①→②→⑦→?→?→?。說明本文改進(jìn)的螞蟻算法因其本質(zhì)并行特性用于路徑尋優(yōu)中具有較高搜索效率和一定準(zhǔn)確性，能夠?qū)崿F(xiàn)快速的全面尋優(yōu)。

表1 參數(shù)值Tab.1 Parameter values

與基本蟻群算法相比，改進(jìn)后的算法的探索新路徑點(diǎn)則是在局部更新規(guī)則的作用下出現(xiàn)的,算法經(jīng)過一定的循環(huán)次數(shù)后收斂于一個(gè)最優(yōu)解，為避免此最優(yōu)解為局部最優(yōu)解，在局部更新規(guī)則的作用下，不斷地減少此最優(yōu)路徑上的信息素，從而促使螞蟻跳出局部最優(yōu)解，尋找一條新的路徑。在算法的準(zhǔn)確度和效率方面，本文的算法也有優(yōu)勢(shì)。

另外，文中給出的示例網(wǎng)絡(luò)不算復(fù)雜，很快就能搜索到正確的最短路徑。當(dāng)交通網(wǎng)絡(luò)相對(duì)比較復(fù)雜時(shí)或者是動(dòng)態(tài)變化時(shí)，雖然可能在規(guī)定的較短時(shí)間內(nèi)搜索不到最短路徑，但可通過迭代的方式，在較少迭代次數(shù)下搜索到的“次優(yōu)”路徑將也能夠避開交通稠密地區(qū)，滿足路徑誘導(dǎo)要求。而且對(duì)于動(dòng)態(tài)路徑誘導(dǎo)。該算法對(duì)目標(biāo)函數(shù)、初始數(shù)據(jù)和模型復(fù)雜程度均無特殊要求，特別是當(dāng)目標(biāo)函數(shù)為非線性時(shí)，其優(yōu)勢(shì)更為明顯，因此更適用于動(dòng)態(tài)最優(yōu)路徑的搜索。

5 結(jié)束語

本文嘗試用蟻群算法來求解最優(yōu)路徑選擇問題，并根據(jù)交通網(wǎng)絡(luò)的要求對(duì)基本模型進(jìn)行了改進(jìn)，且通過實(shí)驗(yàn)仿真取得了較為滿意的效果。同時(shí)也證明了該方法具有一定的理論參考價(jià)值和實(shí)際意義。將蟻群算法應(yīng)用于交通網(wǎng)絡(luò)最優(yōu)路徑的選擇過程中，能充分發(fā)揮算法的協(xié)作性、正反饋和分布式并行計(jì)算的特點(diǎn)。但由于蟻群算法的發(fā)展還在起步和探索階段，目前仍存在一些待研究的問題，如算法的收斂性、參數(shù)的合理設(shè)置及如何降低時(shí)間復(fù)雜度等。而且，對(duì)于動(dòng)態(tài)交通網(wǎng)絡(luò)中如何應(yīng)用蟻群算法，如何通過迭代的方法求出最短路徑，也是值得進(jìn)一步深入研究的問題。但是，可以肯定的是，隨著蟻群算法的深入開展，它必將成為交通規(guī)劃和交通組織網(wǎng)絡(luò)化的優(yōu)化算法，從而促進(jìn)整個(gè)交通網(wǎng)絡(luò)優(yōu)化的發(fā)展。

[1]殷 超.基于改進(jìn)Dijkstra 算法的最短路徑搜索仿真[J].山東理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，24(6)：33-36.

[2]黃貴玲，高西全，靳松杰，談飛洋.基于蟻群算法的最短路徑問題的研究和應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(13)：233-235.

[3]高 尚.解旅行商問題的混沌蟻群算法[J].系統(tǒng)工程理論與實(shí)踐，2005，(9)：100-104.

[4]吳霜華，付 洋，葛 亮，基于混沌蟻群算法的最短路徑選擇研究[J].重慶交通大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，26：126-128.

[5]趙寶江，李士勇，金 俊.基于自適應(yīng)路徑選擇和信息素更新的蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(3)：12-15.

[6]Fuellerera Guenther,Doernera Karl F.,Hartla Richard F.,Iorib Manuel.Ant colony optimization for the two-dimensional loading vehicle routing problem[J].Computers &Operations Research,2009,36(3):655-673.

[7]Yuvraj Gajpal,PrakashAbad.An ant colony system(ACS)for vehicle routing problem with simultaneous delivery and pickup[J].Computers &Operations Research,2009,36(2):3215-3223.

[8]Donati Alberto V.,Montemanni Roberto,Casagrande Norman et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal of Operational Research,2008,185(3):1174-1191.

[9]Sheffi Yosef.Urban transportation networks:equilibrium analysis with mathematical programming methods[M].New Jersey,USA:PRENTICEHALL,INC.,1985.

[10]Dorigo M.Optimization,learning and natural algorithms[D].Milano,Italy:Dipartimento di Elettronica,Politecnico di Milano,1992.

[11]Dorigo M.,Gambardella L.M.Ant colony system:a cooperative learningapproach to the traveling salesman problem[J].IEEE Transactionson Evolutionary Computation,1997,1(1):53-66.

[12]陳小強(qiáng)，杜呈欣，熊偉清.蟻群算法求解函數(shù)優(yōu)化中的參數(shù)設(shè)置[J].計(jì)算機(jī)工程與應(yīng)用，2008,44(17):53-55.

[13]Bonabeau E.,Dorigo M.,Theraulaz G.Inspiration for optimization from social insect behavior[J].Nature,2000,406(6):39-42.

[14]靳凱文，李春葆，秦前清.基于蟻群算法的最短路徑搜索方法研究[J].公路交通科技，2006,3(23):128-134.

[15]夏立民.交通系統(tǒng)中最優(yōu)路徑選擇算法的研究[D].北京:首都師范大學(xué),2007.

[16]方麗君.基于蟻群算法的交通分配模型研究[D].南京:河海大學(xué)土木與交通學(xué)院,2006.

[17]王 勇，雷 黎，紀(jì)壽文，趙 琳等.基于改進(jìn)蟻群算法的交通分配研究[J].公路交通技術(shù)，2007,6(3)：159-161.

[18]陸 駿，王小平，曹立明.一種基于蟻群算法的車輛導(dǎo)航系統(tǒng)模擬模型[J].計(jì)算機(jī)應(yīng)用與軟件，2005,22(4):17-19.

[19]馬 良.全局優(yōu)化的一種新方法[J].系統(tǒng)工程與電子技術(shù),2000,22(9):62-64.