開題報告文獻(xiàn)閱讀

文獻(xiàn)閱讀隨著我國經(jīng)濟(jì)的發(fā)展，城市交通在促進(jìn)各種資源交換發(fā)揮著越來越重要的作用．據(jù)統(tǒng)計中國每年因交通堵塞造成的GDP損失達(dá)到5％一8％．采取合理的交通路徑的規(guī)劃，能夠?qū)煌ǘ氯A(yù)防起到一定的積極作用．車輛路徑問題最早是由Dtzig和J．Ramser于1959年提出的．至此之后，國內(nèi)外學(xué)者對車輛路徑問題進(jìn)行了廣泛而深入的研究．特別是蟻群算法的提出，該算法與其他算法相比不僅能夠智能搜索全局最優(yōu)而且具有魯棒性、正反饋、分布式計算、易于與其他算法融合等優(yōu)點．蟻群算法求兩地之間的最優(yōu)路徑，必須考慮像天氣、路質(zhì)、路況車流、突發(fā)事件、司機(jī)個人偏好等許多不確定的因素，只有這樣才能給出滿足實際情況的方案．作為智能交通系統(tǒng)的重要組成部分，車載導(dǎo)航系統(tǒng)由于其在解決交通運(yùn)輸問題中的作用得到了廣泛的關(guān)注和不斷的發(fā)展，如緩解交通擁堵，提高交通效率，降低駕車出行成本等。許多國家相繼開展了在此領(lǐng)域的研究工作，并已產(chǎn)生了許多產(chǎn)品。車輛動態(tài)自主導(dǎo)航系統(tǒng)中的核心技術(shù)包括：數(shù)字地圖技術(shù)，最優(yōu)路徑規(guī)劃技術(shù)，地圖匹配及智能導(dǎo)航技術(shù)，無線數(shù)據(jù)傳輸技術(shù)?等。地理信息系統(tǒng)(GeographyInformationSystem，GIS)是管理和研究空間數(shù)據(jù)的技術(shù)系統(tǒng)，可以實現(xiàn)對空間數(shù)據(jù)按地理坐標(biāo)或空間位置的各種處理、對數(shù)據(jù)的有效管理等等。路徑規(guī)劃是車輛導(dǎo)航系統(tǒng)中最基本的功能之一，是幫助駕駛員在旅行前和旅行中尋找行駛路線的過程，是車輛導(dǎo)航的一個基本問題，也是實現(xiàn)導(dǎo)航功能的前提條件，其核心是對最優(yōu)路徑的求解。最優(yōu)路徑是指在道路網(wǎng)絡(luò)中滿足某些優(yōu)化條件的一條路，如距離最短、運(yùn)輸費(fèi)用最低、行駛時間最短等，通過路徑規(guī)劃找出最優(yōu)路徑，具有巨大的經(jīng)濟(jì)效益。隨著計算機(jī)處理速度以及無線通訊技術(shù)的快速發(fā)展，車輛導(dǎo)航系統(tǒng)歷經(jīng)了從靜態(tài)導(dǎo)航到動態(tài)導(dǎo)航的轉(zhuǎn)變過程，這兩者的最大區(qū)別是靜態(tài)導(dǎo)航系統(tǒng)進(jìn)行最優(yōu)路徑規(guī)劃及導(dǎo)航所用的是靜態(tài)的交通歷史數(shù)據(jù)或者是純粹的地理信息數(shù)據(jù)，而動態(tài)導(dǎo)航系統(tǒng)會利用實時更新的動態(tài)交通信息對車輛進(jìn)行路徑規(guī)劃和導(dǎo)航，從而使得導(dǎo)航的結(jié)果更加準(zhǔn)確合理口。動態(tài)導(dǎo)航系統(tǒng)的實施方式可以有：中心廣播式，交通信息中心只負(fù)責(zé)向一定區(qū)域范圍內(nèi)以廣播的方式發(fā)布公共的實時交通信息，車載單元自行接收這些信息并且進(jìn)行路徑規(guī)劃，中心對車輛沒有任何控制；中心控制式，交通信息中心按照車載單元的導(dǎo)航服務(wù)請求進(jìn)行路徑規(guī)劃，并且將結(jié)果返還給車載單元。靜態(tài)導(dǎo)航系統(tǒng)沒有對實時交通信息的利用，其具體內(nèi)容除了沒有利用實時交通信息外和動態(tài)導(dǎo)航系統(tǒng)大體類似。近幾年來，隨著國民經(jīng)濟(jì)的發(fā)展，城市中機(jī)動車輛漸漸增多，交通需求在不斷增加，公路交通流量也越來越大，由此導(dǎo)致了交通擁堵的頻繁發(fā)生，城市交通正面臨著越來越大的壓力。在這種形勢下，基于靜態(tài)地圖的自主導(dǎo)航雖然可為駕駛員規(guī)劃一條“最短”路徑，但卻無法避開前方道路可能發(fā)生的交通擁擠。而動態(tài)導(dǎo)航則不同，系統(tǒng)獲知出發(fā)點與目的地之問的交通狀況，經(jīng)過規(guī)劃得到一條滿足用戶需求的合理路徑。這種導(dǎo)航方式不僅可以有效的避開擁堵，節(jié)省出行成本，而且對整個路網(wǎng)有著良性影響。車輛導(dǎo)航系統(tǒng)中的最短路徑搜索問題可以歸結(jié)為圖論中的最短路徑問題,解決該問題的經(jīng)典算法是Dijkstra算法,該算法采用貪心策略,即每一步都選擇與源節(jié)點構(gòu)成局部路徑距離最短的節(jié)點作為當(dāng)前擴(kuò)展節(jié)點來形成當(dāng)前局部最短路徑,進(jìn)而得到全局的最短路徑。是一種靜態(tài)的局部最優(yōu)算法。該算法簡單、易于實現(xiàn),然而把該算法應(yīng)用在求車輛導(dǎo)航系統(tǒng)中的最短路徑搜索問題卻存在如下的局限性:首先,因為需要反復(fù)遍歷所有節(jié)點,在網(wǎng)絡(luò)節(jié)點和路徑較多的情況下,搜索效率就會大大降低,有時甚至找不到最短路徑,再者,對于路徑權(quán)值隨時間動態(tài)變化的動態(tài)網(wǎng)絡(luò),如反映路徑堵塞和暢通信息的實時交通系統(tǒng)網(wǎng)絡(luò)就不適用.蟻群算法是由意大利學(xué)者DorigoM等人于1991年從自然界螞蟻群體覓食行為得到啟發(fā),提出的一種模擬螞蟻行為的模擬進(jìn)化算法人工蟻群算法,簡稱蟻群算法。這種算法具有分布計算、信息正反饋和啟發(fā)式搜索的特征,算法具有模擬生物界群體覓食的能力,并且能夠在實際的路徑搜索過程中對外界的影響做出動態(tài)的響應(yīng),因而在交通最優(yōu)路徑選擇中具有極大的可能性和適應(yīng)性。然而使用傳統(tǒng)蟻群算法求最短路徑問題卻存在搜索速度慢,易于陷入局部最優(yōu)解等缺陷,為此本文針對交通網(wǎng)絡(luò)最短路徑問題的特點,在傳統(tǒng)蟻群算法中引入搜索方向機(jī)制和搜索熱區(qū)機(jī)制提高算法搜索性能。對于基于抽象的網(wǎng)絡(luò)圖的最短路徑問題(shortestPathProblem，簡稱sPP)的求解方法，由于其在通信、交通、計算機(jī)網(wǎng)絡(luò)、運(yùn)籌、管理等多門學(xué)科中的多種應(yīng)用需求，多年以來得到了充分的關(guān)注并取得了大量研究成果。在這諸多的研究中，大都是基于網(wǎng)絡(luò)圖路徑權(quán)值為常量的靜態(tài)算法。網(wǎng)絡(luò)路徑權(quán)值隨時間發(fā)生變化的動態(tài)最短路徑查找算法隨著計算機(jī)處理速度不斷提高以及應(yīng)用需求的不斷增加，近年來得到了更加廣泛的關(guān)注。在網(wǎng)絡(luò)圖中兩特定結(jié)點之間的最短路徑：此問題也即源點-匯點最短路徑問題，最經(jīng)典韻算法就是Dijkstra所提出的算法，此算法依照路徑的長度依次產(chǎn)生從起始結(jié)點到網(wǎng)絡(luò)圖中所有結(jié)點的最短路徑。自Dijkstra算法提出以后，又歷經(jīng)了多人在具體實施方法上的改進(jìn)，使其求解速度大幅提高。解決此問題其他常用的算法包括Bellman，F(xiàn)ord，Moore等人分別提出的動態(tài)規(guī)劃(DynamicProgramming)算法，也稱為Bellman—ford算法，該算法解決網(wǎng)絡(luò)中單源點最短路徑問題；Pape，Pallottino等人各自提出的增長圖(Graph．Growth)算法；Glover等人提出的結(jié)合以上各算法思想的域閥(Threshold)算法。Hart．eta1提出了A*啟發(fā)式搜索算法。對網(wǎng)絡(luò)圖中所有結(jié)點對之間的最短路徑問題：解決較好的兩個方法是Floyd提出的一個算法一一Floyd算法，以及另一個被Dantzig提出的算法。兩者的計算復(fù)雜度相同，都是可以優(yōu)先選擇的算法。Dijkstra算法只能解決無負(fù)邊權(quán)重的最短路徑問題，在歐幾米得網(wǎng)絡(luò)(例如交通路網(wǎng))中，通過對Dijkstra算法使用下限函數(shù)的方法稱為歐幾米得試探法，歐幾米得試探法解決歐幾米得圖中的源點-匯點最短路徑問題。歐幾米得試探法是A*算法的一個特例，Dijkstra算法是一種下限為O的A*。在網(wǎng)絡(luò)圖中計算源點到匯點間依照路徑長度產(chǎn)生的前k條最短路徑：對此問題最早的解決算法是Hofhnan，Pavley提出的，Dreyfus對此算法作了進(jìn)一步的改進(jìn)，另一個應(yīng)用廣泛的經(jīng)典的解決此問題的算法是Shier提出的。最近，Eppstein提出的采用k個最短路徑的隱式表達(dá)計算的最短路徑算法性能有了比較顯著的提高。從Dijkstra算法到Hoffman，Pavley提出的算法都為基于順序的算法。但ChandyandMisra算法是一種計算k個最短路徑問題的并行算法，其時間復(fù)雜度比順序算法要小。在網(wǎng)絡(luò)圖中計算起點和終點之間歷經(jīng)幾個中間結(jié)點的最短路徑：此類問題的經(jīng)典解決算法包括Dreyfus提出的算法以及Beardwood，Bajaj，Ibaraki等人提出的算法。這些經(jīng)典的最短路徑求解算法的研究成果解決了大量的相關(guān)基礎(chǔ)理論問題。近些年來，許多的工作集中在對算法在計算機(jī)上的具體實施方案的改進(jìn)上，以期有更好的運(yùn)行效率。還有就是對算法在特定的領(lǐng)域的應(yīng)用研究上，針對特定領(lǐng)域出現(xiàn)的新問題，將某些經(jīng)典算法加以適應(yīng)性的改進(jìn)從而得到理想的結(jié)果。如在交通網(wǎng)絡(luò)的應(yīng)用研究，就要考慮道路交通網(wǎng)絡(luò)中的交通限制信息以及交通狀況動態(tài)變化特性。 蟻群算法是模擬蟻群行為的一種隨機(jī)搜索優(yōu)化算法，主要由四個部分組成[5]：選擇策略；信息量的局部更新；求局部最優(yōu)解的局部搜索算法；信息量的全局更新。用基本的蟻群算法求解最短路徑問題的主要實現(xiàn)步驟如下:（1）信息初始化：算法開始運(yùn)行時，賦予每條邊上相等數(shù)量的信息量。（2）選擇策略：位于第i個節(jié)點的螞蟻I，按以下選擇策略選擇邊（i，j）：(1)其中，={和i相連的節(jié)點}-{螞蟻k已訪問過的節(jié)點}，即每個螞蟻對每個節(jié)點最多只允許訪問一次，對不連通的點，則賦給一個足夠大的懲罰值；argmaxt（i，s）表示在與i相關(guān)聯(lián)的邊的集合中，具有最大信息量的邊的另一節(jié)點；為給定參數(shù)，0<<1，q是（0，1）內(nèi)服從均勻分布的隨機(jī)變量；h依照以下概率在=-argmaxt（i，s）內(nèi)隨機(jī)取值：(2)（i，s）表示邊（i，s）上的信息量，式（2）采用輪盤賭的方式實現(xiàn)。若=0.9，式（1）表明和i相關(guān)聯(lián)的信息量最大的邊以高概率0.9被螞蟻選中，其余的邊以0.1的概率按式（2）參與選擇。（3）局部更新信息量：當(dāng)螞蟻選中邊（i，j）后，就更新邊（i，j）上的信息量：每當(dāng)螞蟻選中一條邊后，就按（3）式更新減少邊上的信息量，從而增加螞蟻選擇其它邊的概率。（4）局部搜索：當(dāng)m只螞蟻從S到T搜索完后，則求得m個解。為了盡可能遍歷所有解,分別在這些解的鄰域中，采用局部搜索算法（例如2-OPT），求出局部最優(yōu)解。（5）全局更新信息量：當(dāng)所有的m只螞蟻都得到局部最優(yōu)解后，全局更新邊上的信息量：是給定參數(shù)，0<<1，表示隨著時間的推移，以前留下的信息逐漸消逝，用參數(shù)1-表示信息消逝程度；是邊（i，j）上的信息增量；是螞蟻k求得的局部最優(yōu)解；wconst是常量。（6）求全局最優(yōu)解：到當(dāng)前迭代次數(shù)為止，所建立的所有局部最優(yōu)解中，值最小的解作為當(dāng)前迭代次數(shù)的全局最優(yōu)解。從一系列的實驗結(jié)果發(fā)現(xiàn)，用基本蟻群算法求解最短路徑過程中常出現(xiàn)兩個問題：搜索陷入局部最優(yōu)解，即搜索進(jìn)行到一定程度后，所有的個體發(fā)現(xiàn)的解基本完全一致，出現(xiàn)停滯現(xiàn)象，不能再對解空間進(jìn)一步搜索，導(dǎo)致可能無法找到全局最優(yōu)解；收斂到全局最優(yōu)解的時間長，求解結(jié)果反復(fù)在局部最優(yōu)解和全局最優(yōu)解之間振蕩。為了解決出現(xiàn)的問題，文章從蟻群算法的選擇策略、局部搜索算法以及信息量的全局修改三方面進(jìn)行改進(jìn)。（1）分析式（1）知，若參數(shù)值較大（如接近1），則多數(shù)螞蟻易選擇信息量最大的邊，這樣在搜索過程中可能容易出現(xiàn)多數(shù)螞蟻搜索到相同的路徑，使得搜索到的解空間較小，不利于發(fā)現(xiàn)全局最優(yōu)解，算法容易收斂到局部最優(yōu)解。若較?。ㄈ缃咏?），則信息量最大的邊被選擇的概率小，其它邊被選擇的概率大，能擴(kuò)大搜索到的解空間，但搜索呈現(xiàn)一定的盲目性，不容易收斂。綜合考慮這兩個方面，采用變參數(shù)，即的值和迭代次數(shù)cycle有關(guān)，是迭代次數(shù)的分段函數(shù)：(5)式中，分別為迭代次數(shù)；是最大迭代次數(shù)；0.8<<1，0<<0.4。式（5）表明，算法開始運(yùn)行時，以較大的概率選擇信息量最大的邊，直到迭代到第次。此后，為了防止搜索陷入局部最優(yōu)解，便于發(fā)現(xiàn)全局最優(yōu)解，以較大的概率在局部最優(yōu)解的鄰域中搜索其它解，直到迭代到第次。為了使算法收斂到全局最優(yōu)解，次后再以較大的概率選擇信息量最大的邊，直到運(yùn)行結(jié)束。（2）選擇合適的局部搜索算法，能擴(kuò)大搜索空間，有利于發(fā)現(xiàn)全局最優(yōu)解。受遺傳算法的啟發(fā)[7]，將變異思想引入到局部搜索算法，給出一個具有變異特征的局部搜索算法。設(shè)螞蟻I搜索到從S到T的路徑為：。分別為圖中的節(jié)點。給定變異概率，在n次循環(huán)中，產(chǎn)生n個（0，1）內(nèi)均勻分布的隨機(jī)數(shù)。若第個隨機(jī)數(shù)<，則第個節(jié)點要發(fā)生變異。設(shè)存在節(jié)點，和相連外，有w個節(jié)點，，…，，和相連。進(jìn)行w次循環(huán)，產(chǎn)生w個（0，1）內(nèi)勻分布的隨機(jī)數(shù)，若第個隨機(jī)數(shù)（為給定的選擇概率），則用代替，得到一個解。若路徑的值，則用作為螞蟻k搜索到的局部最優(yōu)解。如果該算法和常用的2-OPT局部搜索算法相結(jié)合，則更能加大對解空間的探測力度。（3）為了使算法較快地收斂到全局最優(yōu)解，采用下式對信息量全局更新：（6）是全局最優(yōu)解，即最短路徑的距離值。式（6）表明，經(jīng)過次迭代后，只修改全局最優(yōu)解邊上的信息量，使最短路徑邊上的信息量增加較快，算法容易收斂到全局最優(yōu)解。蟻群算法是一種模擬進(jìn)化算法，是受到對真實蟻群行為的研究的啟發(fā)而提出的。為了說明蟻群系統(tǒng)的原理，先簡介一下螞蟻搜索食物的具體過程。象螞蟻這類群居昆蟲，雖然單個昆蟲的行為極其簡單，但群體卻表現(xiàn)出復(fù)雜的行為，能找到由蟻巢到食物源的最短路徑。仿生學(xué)家經(jīng)過研究發(fā)現(xiàn)，螞蟻個體之間是通過一種稱為外激素（pheromone）的物質(zhì)進(jìn)行信息傳遞的。螞蟻在運(yùn)動過程中，能夠在它所經(jīng)過的路徑上留下該種物質(zhì)，而且在運(yùn)動過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動方向，螞蟻傾向于朝著物質(zhì)強(qiáng)度高的方向移動。因此，由大量螞蟻組成的群體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑越短，走過的螞蟻越多，路徑上留下的信息物質(zhì)越多，則后續(xù)螞蟻選擇該路徑的概率就越大，并且留下相應(yīng)的信息物質(zhì)。最后，螞蟻個體之間就是通過這種信息物質(zhì)交流，搜索到一條從蟻巢到食物源的最短路徑。最短路徑問題是智能交通中交通網(wǎng)絡(luò)分析中的一個重要問題，也是一個研究熱點。它是資源分配、路線設(shè)計及分析等優(yōu)化問題的基礎(chǔ)，具有重要理論意義和實際應(yīng)用價值。有許多研究者曾對最短路徑算法進(jìn)行了大量的研究，并取得了很大的進(jìn)展，提出了很多解決這類問題的方法。其中傳統(tǒng)的算法有，Dijkstra算法、A·算法及其改進(jìn)算法等等；還有近幾十年來，通過模擬或揭示某些自然現(xiàn)象而產(chǎn)生了一些新穎的啟發(fā)式智能算法，如遺傳算法，模擬退火算法，禁忌搜索算法、蟻群算法等。城市道路網(wǎng)有道路路線．交叉路口等物理屬性，同時也具有路線長度、通行時間、路況等各種其它邏輯屬性。用節(jié)點來表示城市道路網(wǎng)中的交叉路口，連接兩節(jié)點之間的邊表示路路線，并將路線的長度、通行時間，路況等屬性表示為該邊的權(quán)值，那么就可以把道路網(wǎng)絡(luò)抽象為一個帶權(quán)有向圖。給定一個帶權(quán)有向圖G為二元組G=(V，{E})，其中V是包含n個節(jié)點的集合，E是包含h條邊(弧段)的集合，<i，j>是E中從節(jié)點i至j的邊，w{{是邊<i，j>的非負(fù)權(quán)值。設(shè)s，T分別為V中的起始節(jié)點和目標(biāo)節(jié)點，則最優(yōu)路徑問題就是指在帶權(quán)有向圖G中，尋找從指定起始節(jié)點到目標(biāo)節(jié)點的一條具有最小權(quán)值總和的路徑。智能交通系統(tǒng)（IntelligentTransportationSystem,ITS）就是充分利用現(xiàn)代通信、定位、傳感器及其他與信息有關(guān)的技術(shù)來減少交通擁擠，提高道路通過量，改進(jìn)交通安全狀況，快速實現(xiàn)交通信息的采集和傳遞，在人、車、路之間構(gòu)造最優(yōu)時空模型，從而達(dá)到合理地分配交通資源，改善地面交通條件的目的。ITS的發(fā)展離不開地理信息系統(tǒng)GIS（GeographicInformationSystem）的支持.GIS是以地理空間數(shù)據(jù)庫為基礎(chǔ),在計算機(jī)軟件的支持下,對空間相關(guān)數(shù)據(jù)進(jìn)行采集、管理、操作、分析、模擬和顯示，適時地提供動態(tài)信息，因此GIS是支持ITS發(fā)展的一種關(guān)鍵技術(shù)。在GIS中，數(shù)字地圖不僅要以X、Y二維坐標(biāo)的形式表示出來，而且圖形要素之間具有拓?fù)潢P(guān)系，這是ITS中實現(xiàn)地圖匹配、路徑查詢、路徑引導(dǎo)等功能模塊的基礎(chǔ)。作為智能交通系統(tǒng)的重要組成部分，車載導(dǎo)航系統(tǒng)由于其在解決交通運(yùn)輸問題中的作用得到了廣泛的關(guān)注和不斷的發(fā)展，如緩解交通擁堵，提高交通效率，降低駕車出行成本等。許多國家相繼開展了在此領(lǐng)域的研究工作，并已產(chǎn)生了許多產(chǎn)品。車輛動態(tài)自主導(dǎo)航系統(tǒng)中的核心技術(shù)包括：數(shù)字地圖技術(shù)，最優(yōu)路徑規(guī)劃技術(shù)，地圖匹配及智能導(dǎo)航技術(shù)，無線數(shù)據(jù)傳輸技術(shù)?等。地理信息系統(tǒng)(GeographyInformationSystem，GIS)是管理和研究空間數(shù)據(jù)的技術(shù)系統(tǒng)，可以實現(xiàn)對空間數(shù)據(jù)按地理坐標(biāo)或空間位置的各種處理、對數(shù)據(jù)的有效管理等等。路徑規(guī)劃是車輛導(dǎo)航系統(tǒng)中最基本的功能之一，是幫助駕駛員在旅行前和旅行中尋找行駛路線的過程，是車輛導(dǎo)航的一個基本問題，也是實現(xiàn)導(dǎo)航功能的前提條件，其核心是對最優(yōu)路徑的求解。最優(yōu)路徑是指在道路網(wǎng)絡(luò)中滿足某些優(yōu)化條件的一條路，如距離最短、運(yùn)輸費(fèi)用最低、行駛時間最短等，通過路徑規(guī)劃找出最優(yōu)路徑，具有巨大的經(jīng)濟(jì)效益。隨著計算機(jī)處理速度以及無線通訊技術(shù)的快速發(fā)展，車輛導(dǎo)航系統(tǒng)歷經(jīng)了從靜態(tài)導(dǎo)航到動態(tài)導(dǎo)航的轉(zhuǎn)變過程，這兩者的最大區(qū)別是靜態(tài)導(dǎo)航系統(tǒng)進(jìn)行最優(yōu)路徑規(guī)劃及導(dǎo)航所用的是靜態(tài)的交通歷史數(shù)據(jù)或者是純粹的地理信息數(shù)據(jù)，而動態(tài)導(dǎo)航系統(tǒng)會利用實時更新的動態(tài)交通信息對車輛進(jìn)行路徑規(guī)劃和導(dǎo)航，從而使得導(dǎo)航的結(jié)果更加準(zhǔn)確合理口。動態(tài)導(dǎo)航系統(tǒng)的實施方式可以有：中心廣播式，交通信息中心只負(fù)責(zé)向一定區(qū)域范圍內(nèi)以廣播的方式發(fā)布公共的實時交通信息，車載單元自行接收這些信息并且進(jìn)行路徑規(guī)劃，中心對車輛沒有任何控制；中心控制式，交通信息中心按照車載單元的導(dǎo)航服務(wù)請求進(jìn)行路徑規(guī)劃，并且將結(jié)果返還給車載單元。靜態(tài)導(dǎo)航系統(tǒng)沒有對實時交通信息的利用，其具體內(nèi)容除了沒有利用實時交通信息外和動態(tài)導(dǎo)航系統(tǒng)大體類似。搜索熱區(qū)是指由源節(jié)點和目標(biāo)節(jié)點為對角節(jié)點所組成的矩形區(qū)域,在實際求最短路徑問題時,求得的最優(yōu)軌跡節(jié)點的位置,其落在由源節(jié)點和目標(biāo)節(jié)點為對角節(jié)點所形成的搜索熱區(qū)的概率往往要大大高于落在非搜索熱區(qū)內(nèi)的概率。因此在蟻群算法中引入搜索熱區(qū)的概念后不但使得搜索的速度大大提高,而且不易搜索陷入局部最優(yōu)解。參考文獻(xiàn)趙亦林編著《車輛定位與導(dǎo)航系統(tǒng)》北京：電子工業(yè)出版社1999．1陳述彭等．地理信息系統(tǒng)導(dǎo)論[M]．北京：科學(xué)出版社，1999．5顏波．車載動態(tài)自主導(dǎo)航系統(tǒng)中的動態(tài)最優(yōu)路徑規(guī)劃[D]．[碩士學(xué)位論文]．北京：清華大學(xué)汽車工程系，2004司功閃．地理信息系統(tǒng)中路徑分析系統(tǒng)的設(shè)計與實現(xiàn)[D]．[碩士學(xué)位論文]．湖南：國防科學(xué)技術(shù)大學(xué)研究生院，2003盧照敢，楊天行．地理信息系統(tǒng)中空間關(guān)系自動構(gòu)建技術(shù)研究[J]．長春工程學(xué)院學(xué)報(自然科學(xué)版)，V01．3，2002．4吳信才．地理信息系統(tǒng)原理與方法[M]．北京：電子工業(yè)出版社，2002．3鄒倫等．地理信息系統(tǒng)基礎(chǔ)一原理、方法和應(yīng)用[M]．北京：科學(xué)出版社，2001．2朱文興等．城市交通網(wǎng)絡(luò)中的路徑優(yōu)化研究[J]．山東大學(xué)學(xué)報(工學(xué)版)．2005．35(1)：74—77陸鋒，盧冬梅，崔偉宏．交通網(wǎng)絡(luò)限制搜索區(qū)域時間最短路徑算法[J]．中國圖像圖形學(xué)報，1999，4(10)：849—853陸鋒．最短路徑算法：分類體系與研究進(jìn)展[J]．測繪學(xué)報，2001，30(3)：269—275．王開義，趙春江，胥桂仙等．GIs領(lǐng)域最短路徑搜索問題的一種高效實現(xiàn)[J]．中國圖像圖形學(xué)報，2003，8(8)：95l一956．陳壁峰，陸吳娟，黃樟燦．車輛自導(dǎo)航系統(tǒng)的動態(tài)最優(yōu)路徑搜索模型及算法[J]．武漢理工大學(xué)學(xué)報(信息與管理工程版)，2002，24(3)：46—48．段莉瓊，朱建軍，王慶社，馬玲．改進(jìn)的最短路徑搜索A$算法的高效實現(xiàn)[J]．海洋測繪，2004，24(5)：20一22．許志海，張紹云．交通限制條件下的最短路徑算法分析與優(yōu)化[J]．信息過程大學(xué)測繪學(xué)院學(xué)報，2005，22(1)：62—64．工秋紅，趙忠杰．汽車駕駛智能化中路線規(guī)劃及導(dǎo)航的最佳路徑求解法[J]．西安公路交通大學(xué)學(xué)報，1999，19(3)：88—90彭飛，柳重堪，張其善．車輛定位與導(dǎo)航系統(tǒng)中的快速路徑規(guī)劃算法[J]．北京航空航天大學(xué)學(xué)報，2002，28(1)：70一73愛信艾達(dá)株式會社．路線搜索裝置以及路線搜索方法[D]．中國：cN1657877A，2005，8，24交通預(yù)測．com公司．一種提供旅行時間預(yù)測的方法[D]．中國：cN1434946A，2003，8，6張小國，王慶，萬德鈞．基于電子地圖的路徑最優(yōu)算法研究[J]．中國慣性技術(shù)學(xué)報，2001，9(1)：44～49陳曦，傅明．基于多Agent的動態(tài)路徑規(guī)劃方法研究[J]．計算機(jī)工程，2002，21：228—229，235丁勝昔，張其善．城市復(fù)雜道路網(wǎng)的路線規(guī)劃算法[J]．遙測遙控，2004，25(1)：36—39韓剛，蔣捷，陳軍，曹元大．車載導(dǎo)航系統(tǒng)中顧及道路轉(zhuǎn)向限制的Dijkstra算法[J]．測繪學(xué)報，2002，31(4)：366—368宋延，石建軍，許國華．適用于路徑規(guī)劃系統(tǒng)的動態(tài)路網(wǎng)描述模型[J]．交通與計算機(jī)，2004，22(5)：28—3l55]石小法等．交通信息影響下的動態(tài)路徑選擇模型研究[J]．公路交通科技，2000，17(4)：35—3754]劉彥良，王洪濤．復(fù)雜網(wǎng)絡(luò)的優(yōu)化模型及最短路徑求解[J]．天津理工大學(xué)學(xué)報，2006，22(1)：33—35Dijkstra．E．Anoteontwoproblemswithgraphs[J]．NumericalMathematics1959．Vl：267～271R．K．Ahuja，K．Mehlhorn，J．B．Orlin，eta1．FasterAlgorithmsfortheshortestpathproblem[J]．J．ACM．1990，V37：213～223R．K．Ahuja，K．Mehlhorn，J．B．Orlin，eta1．FasterAlgorithmsfortheshortestpathproblem[J]．J．ACM．1990，V37：213～223Cherkassky，B．V．，G01dberg，A．v．，Radzik，T．shortestPathsAlgorithms：TheoryandExperimentalEValuation[J]．ComputerscienceDepartment，StanfordUniversity’rechnicalReport．1993，V93·1480R．E．Be兒man．Onaroutingproblem[J]．Quart．Appl．Math．1958，V16：87～90L．R．Ford．NetworkFlowTheory[J]．TheRandcorporation：1956．p923U.Pape.ImplementationandemciencyofMoorealgorithmsfortheshortestrouteproblem[J]．MathProg．1974，V7：212～222T.Williams,R.J.Murphy,F.Walther《AFree-SpaceOpticalTerminalforFadingChannels》Free-SpaceLaserCommunications2009.07FrederickG.Walther,JohnD.Moores《AProcessforFree-SpaceLaserCommunicationsSystemDesign》Free-SpaceLaserCommunications2009.03ShlomiArnon《Anunderwateropticalwirelesscommunicationnetwork》Free-SpaceLaserCommunications2009.09K.KagawaandJ.Tanida《Free-spaceopticaldatatransmissionusingwavelength-divisionmultiplexingwithadedicatedCMOSimagesensorforindooropticalwirelessLAN》Free-SpaceLaserCommunications2009.04KaiyunCui,GangChen,QunfengHe,ZhengyuanXu《Indooropticalwirelesscommunicationbyultravioletandvisiblelight》Free-SpaceLaserCommunications2009.09RobertJ.Murphy,AliciaM.《AConicalScanFreeSpaceOpticalTrackingSystemforFadingChannels》Free-SpaceLaserCommunications2009.01FillardJP,M’timetH，LussertJM,et,al.Computersimulationofsuperresolutionpointsourceimagedetection.OptEng,1993cherkassky，B．V．，Goldberg，A．V．，Radzik，T．shortestPathsAlgorithmsTheoryandExperimentalEvaluation．ComputerScienceDepartmentStanfordUniversityTechnicalReport．1993，V93一1480Multithre