朱云虹，袁 一

(1.南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003；2.南京大學(xué) 地理與海洋科學(xué)學(xué)院，江蘇 南京 210093)

0 引 言

近年來，隨著地圖應(yīng)用和導(dǎo)航技術(shù)的迅速發(fā)展，在覆蓋GPS的移動(dòng)設(shè)備上(例如手機(jī)和汽車)利用地圖應(yīng)用程序來搜索目的地路線的行為已經(jīng)越來越普遍。當(dāng)輸入初始地點(diǎn)和目的地后，幾秒鐘最短路線將顯示在移動(dòng)設(shè)備上。目前地圖應(yīng)用程序通過路網(wǎng)進(jìn)行搜索，通常有兩個(gè)重要功能，分別是距離查詢和路徑查詢。距離查詢是查詢地圖中兩點(diǎn)之間的最短距離，路徑查詢是查詢地圖中兩點(diǎn)之間具有最短距離的路徑。

最短路徑[1]作為路網(wǎng)中的焦點(diǎn)問題之一，目前已在計(jì)算機(jī)通信、運(yùn)籌學(xué)以及地理信息系統(tǒng)等領(lǐng)域得到廣泛應(yīng)用，主要涉及智能交通[2]、地理信息系統(tǒng)[3]、路徑規(guī)劃[4]、計(jì)算機(jī)網(wǎng)絡(luò)[5]等。從20世紀(jì)50年代起，研究者們就對最短路徑問題展開了深入探索，研究最短路徑問題的目標(biāo)是在網(wǎng)絡(luò)中搜索兩個(gè)節(jié)點(diǎn)之間最有效的最短路徑。一系列經(jīng)典算法的誕生奠定了最短路徑算法的基礎(chǔ)，主要包括：計(jì)算一個(gè)節(jié)點(diǎn)到全部任意節(jié)點(diǎn)之間最短路徑的Dijkstra算法[6]，計(jì)算任意對節(jié)點(diǎn)間最短路徑的Floyd算法[7]，以及智能A*算法[8]。

大多數(shù)路網(wǎng)的研究通常都集中在如何減少最短路徑查詢的計(jì)算時(shí)間上面。例如，基于覆蓋的算法[9]減少了查詢的預(yù)處理時(shí)間，比普通A*算法和Dijkstra算法的查詢速度快10倍；一種稱為動(dòng)態(tài)層次結(jié)構(gòu)的算法(AH)通過縮小理論與實(shí)踐之間差距的指標(biāo)體系來優(yōu)化路網(wǎng)上的最短路徑和距離查詢時(shí)間[10]。但是上述算法僅僅能夠優(yōu)化查詢的計(jì)算時(shí)間，并不能改善最短路徑實(shí)際消耗的行程時(shí)間。

RoadRank算法是在城市道路網(wǎng)中計(jì)算每個(gè)路段的影響分?jǐn)?shù)算法，并能根據(jù)總體分?jǐn)?shù)進(jìn)行排序，通過在每個(gè)時(shí)間點(diǎn)提供最新的交通數(shù)據(jù)，不斷隨時(shí)間增量更新影響分?jǐn)?shù)。RoadRank算法可用作動(dòng)態(tài)城市道路網(wǎng)絡(luò)的交通擁堵和影響估計(jì)[11]，給出了每個(gè)路段的影響分?jǐn)?shù)。該算法考慮到了擁擠，但忽略了每個(gè)節(jié)點(diǎn)上的交通燈。

交通燈是城市交通網(wǎng)絡(luò)的重要組成部分[12]，隨著城市流量的增加，人們因?yàn)榈却煌粝牡臅r(shí)間越來越長。目前，部分大城市的交通堵塞問題十分嚴(yán)峻，已成為社會(huì)待解決的一大難題，極大影響了群眾的正常出行。因此，交通燈對最短路徑的影響不可忽視。地圖應(yīng)用程序提供的最短路線并不一定是想要的路線，在實(shí)際路網(wǎng)中用戶消耗大量時(shí)間等待交通燈和道路擁擠。傳統(tǒng)的A*算法通常忽略了交通燈的問題，其能夠獲得距離最短的路線，但行程時(shí)間不一定最短。

解決這些問題的關(guān)鍵在于修改地圖應(yīng)用中傳統(tǒng)A*算法的啟發(fā)式函數(shù)，因此提出了一種基于新的啟發(fā)式函數(shù)的改進(jìn)A*算法。

1 基本概念

1.1 標(biāo)題路網(wǎng)

路網(wǎng)定義為N=(I,R)，包括一系列道路交點(diǎn)I={i1,i2,…,in}(作為節(jié)點(diǎn))，通過一系列路段R={r1,r2,…,rn}連接上述節(jié)點(diǎn)。其中每個(gè)路段ri關(guān)聯(lián)了本身的特征值，包含不同交通狀況的衡量指標(biāo)。

1.2 啟發(fā)式函數(shù)

啟發(fā)式算法是一種基于直觀或經(jīng)驗(yàn)的局部優(yōu)化算法，也稱為智能算法、現(xiàn)代優(yōu)化算法[13]，已得到了深入研究和廣泛應(yīng)用，主要包括神經(jīng)網(wǎng)絡(luò)算法[14]、遺傳算法[15]等。A*算法也是一種啟發(fā)式算法。算法的共性是基于客觀世界中的一些自然現(xiàn)象，通過與組合優(yōu)化求解進(jìn)行類比，找出共性設(shè)計(jì)算法。啟發(fā)式算法的難點(diǎn)是建立符合實(shí)際問題的一系列啟發(fā)式規(guī)則(即啟發(fā)式函數(shù))，優(yōu)點(diǎn)在于比盲目型的搜索算法高效。一個(gè)經(jīng)過仔細(xì)設(shè)計(jì)的啟發(fā)式函數(shù)，通常能在較短時(shí)間內(nèi)獲得一個(gè)搜索問題的最優(yōu)解。

1.3 歐幾里德距離

歐幾里德距離(Euclidean distance)指在m維空間中兩個(gè)點(diǎn)之間的真實(shí)距離，或者向量的自然長度(即該點(diǎn)到原點(diǎn)的距離)。在二維和三維空間中的歐氏距離就是兩點(diǎn)間的實(shí)際距離[16]。在歐幾里德平面中，如果兩個(gè)點(diǎn)為p=(x1,y1)和q=(x2,y2)，則距離由式(1)給出：

(1)

1.4 曼哈頓距離

曼哈頓距離(Manhattan distance)由十九世紀(jì)的赫爾曼·閔可夫斯基所創(chuàng)[17]，用以標(biāo)明兩個(gè)點(diǎn)在標(biāo)準(zhǔn)坐標(biāo)系上的絕對軸距總和，是路網(wǎng)中啟發(fā)式方法通常使用的距離之一。在歐幾里德平面中，如果兩個(gè)點(diǎn)為p=(x1,y1)和q=(x2,y2)，則曼哈頓距離由式(2)給出：

d(p,q)=|x1-x2|+|y1-y2|

(2)

曼哈頓距離相比歐幾里德距離，對起點(diǎn)和目標(biāo)點(diǎn)之間的實(shí)際行駛距離會(huì)產(chǎn)生更為精確的估計(jì)，因?yàn)樵趯?shí)際情況中很少存在起點(diǎn)到目標(biāo)點(diǎn)之間的直接路徑，但有時(shí)曼哈頓距離也會(huì)高估實(shí)際距離。

2 A*算法

2.1 基本原理

A*算法是以Dijkstra為基礎(chǔ)的啟發(fā)式搜索方法，是廣泛已知的最佳搜索形式[18]。算法的關(guān)鍵創(chuàng)新點(diǎn)在于，在擴(kuò)展下一個(gè)節(jié)點(diǎn)時(shí)引入路網(wǎng)信息，對當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離進(jìn)行評估。

基于評估函數(shù)f(n)選擇節(jié)點(diǎn)進(jìn)行擴(kuò)展。評估函數(shù)解釋為成本估算，所以評估最低的節(jié)點(diǎn)首先被擴(kuò)展[19]。評估函數(shù)表示如下：

f(n)=g(n)+h(n)

(3)

其中，f(n)為從起始節(jié)點(diǎn)經(jīng)由當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)狀態(tài)的成本估計(jì)；g(n)為路徑從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實(shí)際成本；h(n)為啟發(fā)式函數(shù)，表示從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最佳路徑的估計(jì)成本。

對當(dāng)前節(jié)點(diǎn)n的評估方法有多種，如距離、方向、其他指標(biāo)以及各種指標(biāo)的綜合應(yīng)用，但是評估的基本原則是評估值與實(shí)際值越接近，評估函數(shù)的效果越好。

2.2 算法實(shí)現(xiàn)

A*算法的流程[20]如圖1所示。

(1)建立兩個(gè)列表存放節(jié)點(diǎn)數(shù)據(jù)(分別為開放列表和關(guān)閉列表)；

(2)將初始節(jié)點(diǎn)加入開放列表；

(3)尋找初始節(jié)點(diǎn)周圍所有可到達(dá)的節(jié)點(diǎn)，跳過關(guān)閉列表中的節(jié)點(diǎn)，加入到開放列表中；

(4)已訪問過的節(jié)點(diǎn)加入到關(guān)閉列表中；

(5)當(dāng)開始搜索下一節(jié)點(diǎn)時(shí)，從開放列表中尋找f值最小的作為下一個(gè)擴(kuò)展的節(jié)點(diǎn)(當(dāng)前節(jié)點(diǎn))；

(6)所有當(dāng)前節(jié)點(diǎn)可到達(dá)的節(jié)點(diǎn)再次加入開放列表之后，重新比較f值，并且根據(jù)f值的大小在開放列表中生成升序排列隊(duì)列。在搜索過程中，使用廣度優(yōu)先算法[21]依次選取隊(duì)列的首元素，計(jì)算可能子節(jié)點(diǎn)的g、h和f值，直到找到目標(biāo)節(jié)點(diǎn)或者沒有找到目標(biāo)節(jié)點(diǎn)開放列表已經(jīng)為空時(shí)算法結(jié)束。

圖1 A*算法流程

A*算法實(shí)現(xiàn)的具體步驟為：

(1)初始節(jié)點(diǎn)加入open表;

(2)從open表中尋找f值最小的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。當(dāng)前節(jié)點(diǎn)加入到close表的同時(shí)將其在open表中刪除;

(3)針對當(dāng)前節(jié)點(diǎn)的所有可達(dá)節(jié)點(diǎn)：(a)若該節(jié)點(diǎn)在close表，就跳過該節(jié)點(diǎn)，否則進(jìn)行b；(b)若該節(jié)點(diǎn)不在open表中，則將其加入并且使其父指針指向該節(jié)點(diǎn)。若該節(jié)點(diǎn)在open表中，則計(jì)算當(dāng)前g值，如果比原來g值小，則該節(jié)點(diǎn)滿足條件。修改其父指針指向新的節(jié)點(diǎn)，并計(jì)算新的f值和g值，對open表的f值重新進(jìn)行排序;

(4)在整個(gè)搜索過程中，當(dāng)目標(biāo)節(jié)點(diǎn)已加入close表時(shí)，即找到最短路徑，此時(shí)停止搜索?；蛘弋?dāng)沒有找到目標(biāo)節(jié)點(diǎn)而開放列表已經(jīng)為空時(shí)，即找不到路徑，此時(shí)也停止搜索;

(5)保存搜索路徑的軌跡。通過父指針由目標(biāo)節(jié)點(diǎn)回到初始節(jié)點(diǎn)。

3 改進(jìn)A*算法

算法根據(jù)實(shí)際路網(wǎng)的條件可以被修改，為了簡化路網(wǎng)中的交通燈問題，對于交通燈的假設(shè)如下：假設(shè)1：每個(gè)十字路口都有交通燈。假設(shè)2：初始時(shí)，交通燈從紅燈恰好變成綠燈。假設(shè)3：每個(gè)交通燈同時(shí)具有相同的顏色。假設(shè)4：紅燈需要1分鐘，綠燈需要1分鐘。假設(shè)5：右轉(zhuǎn)不需要等待交通燈可直接通行。假設(shè)6：汽車的平均行駛速度為60英里/小時(shí)。假設(shè)7：如果交通燈是綠燈，則汽車可以直接穿過該十字路口。

為了實(shí)現(xiàn)合理規(guī)避交通燈且具有最短行程時(shí)間的路徑，主要基于傳統(tǒng)的A*算法思想，改進(jìn)原有的距離啟發(fā)式函數(shù)。在改進(jìn)A*算法中，將總行程時(shí)間用作估計(jì)成本。估計(jì)的行程時(shí)間是駕駛時(shí)間和等待時(shí)間的總和。根據(jù)假設(shè)6，總駕駛時(shí)間可由總駕駛距離除以駕駛速度得到。總等待時(shí)間是路網(wǎng)中每個(gè)節(jié)點(diǎn)上的等待時(shí)間的總和。最佳路線是從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)需要最短時(shí)間的路徑。

改進(jìn)A*與傳統(tǒng)A*算法之間的關(guān)鍵差異在于增加了等待時(shí)間的因素。傳統(tǒng)A*算法中，假設(shè)汽車可直接通過每個(gè)節(jié)點(diǎn)而不用等待，然而在實(shí)際路網(wǎng)情況中幾乎不可能。同時(shí)，等待時(shí)間與駕駛時(shí)間相比不是一個(gè)可忽略的時(shí)間，特別是在市中心以及道路交通擁堵時(shí)(同一個(gè)交通燈的等待次數(shù)變多)。

假設(shè)d(n)是從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的總行程時(shí)間，可通過計(jì)算到達(dá)節(jié)點(diǎn)n前的行程時(shí)間總和得到，即從上一節(jié)點(diǎn)到節(jié)點(diǎn)n的行程時(shí)間以及從上一節(jié)點(diǎn)到節(jié)點(diǎn)n的等待時(shí)間。如果汽車進(jìn)行右轉(zhuǎn)彎，則節(jié)點(diǎn)的等待時(shí)間為0。否則，將判斷該節(jié)點(diǎn)的交通燈是否為紅燈。根據(jù)假設(shè)3和4可知，如果行程時(shí)間的上限是一個(gè)奇整數(shù)，則交通燈是綠燈；否則，交通燈是紅燈。當(dāng)交通燈為紅燈，必須等到轉(zhuǎn)向綠燈后繼續(xù)行程。因此，如果行程是從節(jié)點(diǎn)u到節(jié)點(diǎn)n，可以通過以下函數(shù)計(jì)算：

d(n)=

(4)

其中，c(u,v)為從節(jié)點(diǎn)u到節(jié)點(diǎn)v的駕駛時(shí)間，可由邊長度除以駕駛速度計(jì)算得到；w(u)為節(jié)點(diǎn)u處的等待時(shí)間，可通過開始時(shí)間和當(dāng)前路徑從起始節(jié)點(diǎn)到節(jié)點(diǎn)u的行程時(shí)間計(jì)算得到。在實(shí)驗(yàn)中，假設(shè)在初始節(jié)點(diǎn)處的交通燈從紅燈變成綠燈，不考慮初始時(shí)間的影響。

用x來表示節(jié)點(diǎn)u的父節(jié)點(diǎn)，定義兩個(gè)向量Vector(x,u)和Vector(u,v)，計(jì)算出兩個(gè)向量的旋轉(zhuǎn)角度。如果是右轉(zhuǎn)彎，轉(zhuǎn)角小于0；如果是左轉(zhuǎn)彎，轉(zhuǎn)角大于0。為了避免直線產(chǎn)生一個(gè)角度，定義右轉(zhuǎn)彎角度范圍為-135°～-45°。

對于啟發(fā)式函數(shù)，使用曼哈頓距離除以行駛速度作為駕駛時(shí)間的估計(jì)或者歐幾里德距離除以行駛速度作為駕駛時(shí)間的估計(jì)。

4 實(shí)驗(yàn)結(jié)果

利用Minneapolis地圖數(shù)據(jù)作為基礎(chǔ)數(shù)據(jù)，地圖共有2 326個(gè)邊和946個(gè)節(jié)點(diǎn)，邊的平均駕駛時(shí)間為1.95分鐘。地圖原始數(shù)據(jù)使用map.txt存放，其中每一行表示一條邊，第一個(gè)整數(shù)代表道路是否是單行道，后4個(gè)數(shù)字分別代表一條邊的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)。通過程序讀取此地圖并生成道路網(wǎng)絡(luò)。實(shí)驗(yàn)中的Minneapolis地圖如圖2所示，其中淺黑線表示單行道和深黑線代表雙行道。

圖2 Minneapolis地圖

由于邊的平均駕駛時(shí)間為1.95分鐘，因此交通燈的等待時(shí)間是一個(gè)不可忽略的值。實(shí)驗(yàn)對比分析了傳統(tǒng)的A*算法與改進(jìn)的A*算法的實(shí)現(xiàn)效果，兩種算法均分別使用曼哈頓距離和歐氏距離作為啟發(fā)式函數(shù)。算法的對比性能指標(biāo)是最短路徑搜索的運(yùn)行時(shí)間，節(jié)點(diǎn)的擴(kuò)展數(shù)量和路徑的行程時(shí)間。

實(shí)驗(yàn)隨機(jī)選擇4個(gè)測試樣本。在第一個(gè)測試樣本中，初始點(diǎn)坐標(biāo)為(1 121,7 568)，目標(biāo)點(diǎn)坐標(biāo)為(2 179,8 595)。在第二個(gè)測試樣本中，初始點(diǎn)坐標(biāo)為(1 121,7 568)，目標(biāo)點(diǎn)坐標(biāo)為(1 455,7 920)。在第三個(gè)測試樣本中，初始點(diǎn)坐標(biāo)為(2 197,8 966)，目標(biāo)點(diǎn)坐標(biāo)為(1 961,7 800)。在第四個(gè)測試樣本中，初始點(diǎn)坐標(biāo)為(2 197,8 966)，目標(biāo)點(diǎn)坐標(biāo)為(2 085，8 543)。

通過使用曼哈頓距離和歐幾里德距離作為啟發(fā)式函數(shù)的傳統(tǒng)A*算法和改進(jìn)A*算法，來搜索相同樣本的最短路徑。4種算法的性能實(shí)驗(yàn)結(jié)果如表1～4所示。第三個(gè)測試樣本中利用4種算法搜索的最短路徑結(jié)果如圖3所示，其中粗灰色線代表最短路徑。

5 結(jié)果分析

對實(shí)驗(yàn)結(jié)果的綜合分析發(fā)現(xiàn)：4種算法的運(yùn)行時(shí)間均在大致相同的規(guī)模內(nèi)(毫秒級)。運(yùn)行時(shí)間的結(jié)果和節(jié)點(diǎn)擴(kuò)展數(shù)量表明，改進(jìn)A*算法與傳統(tǒng)A*算法能在類似的時(shí)間范圍內(nèi)執(zhí)行計(jì)算，并擴(kuò)展相同數(shù)量的節(jié)點(diǎn)；傳統(tǒng)A*算法比改進(jìn)A*算法運(yùn)行時(shí)間更快，分析其原因是：考慮到交通燈等待時(shí)間之后，改進(jìn)A*算法中有更復(fù)雜的g(n)和h(n)需要計(jì)算，略微(在毫秒級)影響了算法的運(yùn)行時(shí)間;(3)兩種使用曼哈頓的算法與兩種使用歐幾里德的算法相比在距離上擴(kuò)展了較少的節(jié)點(diǎn)，且運(yùn)行時(shí)間較短，表明曼哈頓距離相比歐幾里德距離在運(yùn)行時(shí)間方面具有更好的估計(jì)效果。

表1 節(jié)點(diǎn)(1 121,7 568)到節(jié)點(diǎn)(2 179,8 595)的實(shí)驗(yàn)結(jié)果

表2 節(jié)點(diǎn)(1 121,7 568)到節(jié)點(diǎn)(1 455,7 920)的實(shí)驗(yàn)結(jié)果

表3 節(jié)點(diǎn)(2 197,8 966)到節(jié)點(diǎn)(1 961,7 800)的實(shí)驗(yàn)結(jié)果

表4 節(jié)點(diǎn)(2 197,8 966)到節(jié)點(diǎn)(2 085,8 543)的實(shí)驗(yàn)結(jié)果

圖3 搜索結(jié)果

上述表明：傳統(tǒng)A*算法與改進(jìn)A*算法均能夠?qū)崿F(xiàn)最短路徑的搜索，且運(yùn)行時(shí)間和擴(kuò)展節(jié)點(diǎn)數(shù)量相差不大，在這兩方面性能相似。為了縮短用戶在路網(wǎng)的行程時(shí)間，文中著重關(guān)注兩類算法在性能-總行程時(shí)間上的差異(min級)。

結(jié)合分析第3個(gè)和第4個(gè)測試樣本，實(shí)驗(yàn)發(fā)現(xiàn)：使用歐幾里德距離的啟發(fā)式函數(shù)的改進(jìn)A*算法能搜索到最少行程時(shí)間的路徑，改進(jìn)A*算法的總行程時(shí)間與傳統(tǒng)A*算法相比減少約5%，表明文中提出的方法在總行程時(shí)間方面更有效。分析其原因是：文中算法改進(jìn)了等待交通燈的時(shí)間，其次是由于曼哈頓距離相對于歐幾里德距離會(huì)產(chǎn)生一部分過高估計(jì)，從而影響到算法的行程時(shí)間。

因此最好使用歐幾里德距離作為啟發(fā)式函數(shù)的改進(jìn)A*算法，其始終能提供最佳行程時(shí)間路徑。從圖3中看出，不同方法搜索到的最短路徑是不同的，而最優(yōu)路徑會(huì)有一些右轉(zhuǎn)彎，以避免交通燈的等待時(shí)間。

6 結(jié)束語

文中致力于改進(jìn)和完善傳統(tǒng)的最短路徑搜索A*算法，克服路網(wǎng)中交通燈的等待問題，在啟發(fā)式函數(shù)中加入交通燈的等待時(shí)間，并融合到傳統(tǒng)的A*算法中進(jìn)行最短路徑搜索。通過傳統(tǒng)算法與改進(jìn)A*算法的對比實(shí)驗(yàn)證明，文中提出的算法能實(shí)現(xiàn)最短路徑的搜索且具有較短的行程時(shí)間，并與傳統(tǒng)算法能夠在同一運(yùn)行時(shí)間限制下實(shí)現(xiàn)。對基于A*算法的研究具有一定的理論價(jià)值，并且豐富了路網(wǎng)最短路徑搜索領(lǐng)域的內(nèi)容。

參考文獻(xiàn)：

[1] SHEHZAD F,SHAH M A A.Evaluation of shortest paths in road network[J].Pakistan Journal of Commerce & Social Sciences,2009,3:67-79.

[2] FARO A,GIORDANO D.Algorithms to find shortest and alternative paths in free flow and congested traffic regimes[J].Transportation Research Part C Emerging Technologies,2016,73:1-29.

[3] ZHANG X,GUO X,JING G,et al.Research of improved shortest path algorithm in campus GIS[J].Open Cybernetics & Systemics Journal,2015,9(1):1060-1063.

[4] XU W,HE S,SONG R,et al.Finding the K shortest paths in a schedule-based transit network[J].Computers & Operations Research,2012,39(8):1812-1826.

[5] YANG H H,CHEN Y L.Finding K shortest looping paths in a traffic-light network[J].Computers & Operations Research,2005,32(3):571-581.

[6] WANG S X.The improved Dijkstra’s shortest path algorithm and its application[J].Procedia Engineering,2012,29:1186-1190.

[7] 趙禮峰,梁 娟.最短路問題的Floyd改進(jìn)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(8):31-34.

[8] SHAHZADA A,ASKAR K.Dynamic vehicle navigation:an A* algorithm based approach using traffic and road information[C]//International conference on computer applications and industrial electronics.[s.l.]:IEEE,2011:514-518.

[9] GUTMAN R J.Reach-based routing:a new approach to shortest path algorithms optimized for road networks[C]//Workshop on algorithm engineering & experiments & the first workshop on analytic algorithmics & combinatorics.[s.l.]:[s.n.],2004:100-111.

[10] ZHU A D,MA H,XIAO X,et al.Shortest path and distance queries on road networks:towards bridging theory and practice[C]//ACM SIGMOD international conference on management of data.New York,NY,USA:ACM,2013:857-868.

[11] ANWAR T,LIU C,VU H L,et al.RoadRank:traffic diffusion and influence estimation in dynamic urban road networks[C]//ACM international conference on information and knowledge management.New York,NY,USA:ACM,2015:1671-1674.

[12] 王先美.交通燈控制系統(tǒng)的設(shè)計(jì)[J].科技傳播,2010(23):114.

[13] 陳 萍.啟發(fā)式算法及其在車輛路徑問題中的應(yīng)用[D].北京:北京交通大學(xué),2009.

[14] 馮立穎.改進(jìn)的BP神經(jīng)網(wǎng)絡(luò)算法及其應(yīng)用[J].計(jì)算機(jī)仿真,2010,27(12):172-175.

[15] 馬永杰,云文霞.遺傳算法研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究,2012,29(4):1201-1206.

[16] 徐士英.關(guān)于歐幾里得空間Ed中的二距離集[J].中國計(jì)量學(xué)院學(xué)報(bào),2002,13(1):16-18.

[17] 李 彬.基于相對曼哈頓距離的Web聚類算法研究[J].電子商務(wù),2013(11):57-58.

[18] 熊 偉,張仁平,劉奇韜,等.A*算法及其在地理信息系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2007,16(4):14-17.

[19] 劉 浩,鮑遠(yuǎn)律.A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用[J].計(jì)算機(jī)仿真,2008,25(4):253-257.

[20] 楊銀濤.基于A*算法的避障應(yīng)用仿真[D].鄭州:鄭州大學(xué),2014.

[21] 歐陽圣，胡望宇．幾種經(jīng)典搜索算法研究與應(yīng)用[J]．計(jì)算機(jī)系統(tǒng)應(yīng)用,2011,20(5):243-247.