基于路網(wǎng)的路徑查詢問題的研究

38/392基于路網(wǎng)的路徑查詢問題的研究1引言1.1研究背景隨著經(jīng)濟(jì)和技術(shù)的飛速發(fā)展，越來越多的人們購(gòu)置私家車作為交通工具。這大大提高了人們出行的自主性和舒適度。人們不再局限于公共交通的時(shí)間和空間限制，可以自由選擇出行時(shí)間和路線。與此同時(shí)道路設(shè)施也在迅猛發(fā)展中，用以保障人們出行的暢通并且為人們出行提供多重選擇。龐大繁復(fù)的城市道路系統(tǒng)和多變的路況情況使得地圖應(yīng)用成為人們?nèi)粘Ｉ钪蟹浅Ｖ匾姆?wù)與應(yīng)用。在地圖服務(wù)中，不同的用戶對(duì)于路徑有著不同的要求。隨著路徑查詢問題研究的不斷深入，解決各種路徑查詢問題的新算法不斷涌現(xiàn)。在線地圖應(yīng)用和基于位置的服務(wù)（LBS：locationbasedservices）的迅猛發(fā)展，使得地圖上的信息進(jìn)一步豐富。人們可以通過移動(dòng)設(shè)備的GPS定位對(duì)生活中的建筑和商店信息加入到地圖應(yīng)用中，如百度旅游，大眾點(diǎn)評(píng)網(wǎng)等等。這些基于用戶的興趣點(diǎn)信息（PoI：PointofInterest）的豐富使得之前一度被忽略的基于關(guān)鍵字的路徑查詢問題再次獲得了研究者的青睞，有了進(jìn)一步的進(jìn)展。這種查詢與普通路徑查詢的不同在于用戶可以通過關(guān)鍵字說明他們對(duì)于路徑的興趣點(diǎn)?；陉P(guān)鍵字的路徑查詢問題不斷細(xì)化出各種變種，解決各種變種問題的新算法也層出不窮。然而，城市交通的發(fā)展中的一個(gè)新的問題是由于汽車的井噴式增長(zhǎng)城市的交通擁堵情況日益嚴(yán)重，人們常常并不能根據(jù)地圖應(yīng)用規(guī)劃的最短路徑按時(shí)到達(dá)指定終點(diǎn)，大大降低了人們的出行舒適度。智能交通（ITS：IntelligentTransportSystem）被公認(rèn)為是解決交通擁堵問題的重要手段。目前大部分大中城市在高速路段的各個(gè)路段設(shè)有線圈測(cè)速以及事件記錄裝置?；谶@些歷史數(shù)據(jù)有越來越多的研究致力于改善人們的出行質(zhì)量。研究包括對(duì)車輛進(jìn)行實(shí)時(shí)導(dǎo)航，為用戶進(jìn)行出行前的路徑查詢和對(duì)路徑的時(shí)間進(jìn)行估計(jì)預(yù)測(cè)等等。1.2研究?jī)?nèi)容基于關(guān)鍵字的路徑查詢問題研究的經(jīng)典問題為空間數(shù)據(jù)庫(kù)中的TPQ問題（TripPlanQuery）。在TPQ問題（TripPlanQuery）中，用戶可以指定一組關(guān)鍵字，TPQ搜索從起始點(diǎn)到終點(diǎn)最短的覆蓋所有關(guān)鍵字的路徑。這是一個(gè)NP難問題。OSR（OptimalSequencedRoute）查詢用以找到一條以某一順序經(jīng)過某些給定節(jié)點(diǎn)的路徑，這條路徑使他行走的距離或者花費(fèi)的時(shí)間最短。和TPQ問題同時(shí)的MTNN（Multi-typeNearestNeighbor）查詢提出了解決問題解決的精確算法。基于OSR查詢的MSPSR（Multi-rulePartialSequencedRoute）查詢可以個(gè)性化指定一些順序的要求，如先經(jīng)過加油站再經(jīng)過咖啡館和電影院而不要求經(jīng)過咖啡館和電影院的順序?？紤]到用戶輸入關(guān)鍵字有時(shí)與相應(yīng)PoI上的關(guān)鍵字不同的情況，文獻(xiàn)[]提出了MARK（Multi-appropriate-keyword）查詢。文獻(xiàn)[]提出的KOR（Keyword-awareoptimalroute）查詢可以找到一條覆蓋用戶指定關(guān)鍵字，滿足預(yù)算條件（比如，時(shí)間，花費(fèi)）并使得總共的受歡迎程度最高。Skyline查詢是找到至少有一個(gè)屬性優(yōu)于其他所有元素的skyline對(duì)象。即Skyline查詢是找到不能被其他對(duì)象支配的對(duì)象。這在數(shù)據(jù)庫(kù)中有著廣泛的應(yīng)用。如，Branch-and-BoundSkyline算法是一個(gè)Skyline查詢中的漸進(jìn)最優(yōu)算法。文獻(xiàn)[]研究了如何找到不被到查詢起點(diǎn)的距離和到已有路徑的迂回路徑長(zhǎng)度支配的興趣點(diǎn)。文獻(xiàn)[]提出了兩個(gè)空間Skyline查詢算法，基于R樹的BS和基于Voronoi圖的VS。MPP（Multi-preferencePathPlanning）問題是基于路網(wǎng)的路徑Skyline查詢，屬性包括距離，行駛時(shí)間，路過的交通燈等等。在路網(wǎng)上的多目標(biāo)優(yōu)化路徑查詢研究中，優(yōu)化目標(biāo)為邊上的不同參數(shù)，如花費(fèi)，長(zhǎng)度，時(shí)間和可信度等等[]。MSPP（Multi-objectiveShortestPathProblem）研究路網(wǎng)上不被支配的路徑，也稱為ParetoPath。意為對(duì)于查詢結(jié)果的對(duì)象如果不降低其中一個(gè)對(duì)象的任何一個(gè)參數(shù)那么就不能得到另外一個(gè)處于查詢結(jié)果的對(duì)象。這被證明在最壞情況下可能有指數(shù)級(jí)個(gè)數(shù)的解[]。標(biāo)號(hào)算法研究了這個(gè)問題的精確全集解[]。算法基于路段排名[]和Mote算法[]。MSPP是一個(gè)總和最優(yōu)或者最小值最大的優(yōu)化問題。智能交通系統(tǒng)包括車輛控制系統(tǒng)、交通監(jiān)控系統(tǒng)、運(yùn)營(yíng)車輛高度管理系統(tǒng)和旅行信息系統(tǒng)等。研究包括基于實(shí)時(shí)數(shù)據(jù)和定位的車輛導(dǎo)航、基于歷史數(shù)據(jù)和實(shí)時(shí)數(shù)據(jù)通過預(yù)測(cè)的車輛導(dǎo)航、基于動(dòng)態(tài)網(wǎng)絡(luò)的最短路徑算法的改進(jìn)與近似?；趯?shí)時(shí)數(shù)據(jù)和定位的車輛導(dǎo)航通過汽車定位、實(shí)時(shí)路況信息和用戶輸入的終點(diǎn)給出一條最短路徑。文獻(xiàn)[]基于歷史數(shù)據(jù)進(jìn)行多步時(shí)間預(yù)測(cè)和動(dòng)態(tài)Dijkstra最短路徑算法求得由起始位置到終點(diǎn)的動(dòng)態(tài)最短路徑，并且在車輛行進(jìn)過程中對(duì)路徑進(jìn)行修正。1.3本文工作本文從兩個(gè)方面進(jìn)行研究即基于關(guān)鍵字的支配路徑查詢問題的研究和基于短時(shí)交通預(yù)測(cè)的動(dòng)態(tài)路徑查詢問題的研究本文提出一種帶關(guān)鍵字的、多查詢點(diǎn)的空間査詢,叫帶關(guān)鍵字的聚集路徑查詢,是一類空間關(guān)鍵字的匹配查詢。本文分布從多路徑與樹結(jié)構(gòu)的角度出發(fā)定義了該查詢。與其他空間關(guān)鍵字查詢不一樣,該查詢關(guān)注多用戶的行程規(guī)劃。帶關(guān)鍵字的聚柴路徑查詢問題是NP-hard。為了獲取查詢結(jié)果,本文提出一種基于樹狀索引的精確算法。該精確算法需要重復(fù)進(jìn)行查找分配和任務(wù)完成兩個(gè)階段的工作。查找分配階段的主要工作有三點(diǎn):獲取聚集點(diǎn)、確定候選任務(wù)點(diǎn)集合、給查詢點(diǎn)分配任務(wù)。查找分配階段首選通過增量式算法按序獲取聚集點(diǎn),避免訪問不必要的點(diǎn)。為了減少任務(wù)點(diǎn)集的大小,算法使用了橢圓范圍查詢確定候選點(diǎn)。本文根據(jù)最小包圍矩形與橢圓的關(guān)系改進(jìn)了橢圓范圍查詢的算法。接下來,算法開始迭代式給查詢點(diǎn)分配相應(yīng)的任務(wù)。為了加快査詢處理,查找分配階段始終維護(hù)著結(jié)果的上下界。到任務(wù)完成階段時(shí),精確算法使用一種啟發(fā)式的算法,利用最小堆維護(hù)拓展的路徑。通過動(dòng)態(tài)規(guī)劃的方法維護(hù)一張路徑的表格,算法減少了最小堆的大小并且過濾了不必要的路徑。利用空間換取時(shí)間的方法,算法保存得到的最優(yōu)路徑以減少重復(fù)的查詢。接下來,本文驗(yàn)證了精確算法的正確性。對(duì)于查詢點(diǎn)或者關(guān)鍵字個(gè)數(shù)龐大的情況下,精確算法難以在可接受時(shí)間內(nèi)返回結(jié)果。針對(duì)這種情況,本文提出了查詢的近似算法。基于中心分配的算法考慮到用戶聚集的地點(diǎn)通常距離其中心點(diǎn)很近,可以在中心點(diǎn)附近順便完成任務(wù)。該算法主要使用基礎(chǔ)的查詢算法,因此速度非?？?。而擴(kuò)展樹算法則基于查詢的另外一種關(guān)于樹的定義方式,在結(jié)果偏差率中有較穩(wěn)定的表現(xiàn)。為了避免聚集點(diǎn)選錯(cuò)后影響結(jié)果偏差率,本文還分別對(duì)兩個(gè)近似算法進(jìn)行拓展。最后,本文使用了真實(shí)數(shù)據(jù)集驗(yàn)證了算法的效率。1.4文章結(jié)構(gòu)本文一共分成6章,內(nèi)容與章節(jié)安排如下：第1章“引言”,該部分介紹空間關(guān)鍵字查詢的背景知識(shí),還有空間關(guān)鍵字查詢的研究?jī)?nèi)容,并介紹了本文的主要工作內(nèi)容。第2章“相關(guān)工作”,該部分首先介紹了傳統(tǒng)的數(shù)據(jù)庫(kù)的主要索引技術(shù),例如R-tree、kd-tree,和一些預(yù)處理技術(shù),比如Voronoi圖、TEDI樹,還有傳統(tǒng)空間查詢,比如最近查詢、聚集最近鄰查詢等。接下來,該部分介紹了空間關(guān)鍵字查詢的索引技術(shù),如R2-tree、IR-tree等,還有一些空間關(guān)鍵字匹配查詢還有排序查詢。第3章“背景知識(shí)”,該部分首先引入了多關(guān)鍵的路徑查詢,說明了研究精確關(guān)鍵字匹配的目的所在。接著正式介紹了本文所研究的主要問題-帶關(guān)鍵字的聚集路徑查詢問題,給出了該問題的兩種定義方式,最后證明了該問題是NP-hard的。第6章“總結(jié)與展望”,該部分總結(jié)了本文的主要工作與成果,并給出了下一步的主要工作。

2支配路徑查詢問題研究2.1相關(guān)工作在基于關(guān)鍵字的路徑查詢問題的變種中，研究比較成熟的主要有TPQ、OSR、KOR等問題，這些變種的定義與性質(zhì)不盡相同，適用的算法也不一樣。下面分別論述TPQ、OSR和KOR問題以及解決每類變種的算法。2.1.1TPQ問題概述在TPQ問題（TripPlanQuery）中，用戶可以指定一組關(guān)鍵字，TPQ搜索從起始點(diǎn)到終點(diǎn)最短的覆蓋所有關(guān)鍵字的路徑。TPQ的概念最早誕生于空間數(shù)據(jù)庫(kù)領(lǐng)域。近幾十年，空間數(shù)據(jù)庫(kù)受到各大數(shù)據(jù)庫(kù)生產(chǎn)廠商與科研機(jī)構(gòu)的追捧，大量科研人員對(duì)其進(jìn)行了深入研究。在這一研究熱潮中，大量新的數(shù)據(jù)模型、空間索引技術(shù)和查詢處理基礎(chǔ)等新技術(shù)不斷涌現(xiàn)。然而，這些新的索引以及查詢技術(shù)往往僅限于簡(jiǎn)單的維度，大部分都可以視為最近鄰查詢或者其變種，這些技術(shù)無法滿足新的現(xiàn)實(shí)空間模型以及新型空間數(shù)據(jù)庫(kù)發(fā)展的需求。TPQ即誕生于此背景之下。TPQ概念如下：假定一個(gè)數(shù)據(jù)庫(kù)存儲(chǔ)的是各種空間對(duì)象的位置信息，這些位置信息都取自一個(gè)固定的類別集合C。指定空間中的任意兩點(diǎn)（起點(diǎn)S和終點(diǎn)T）、類別集合C的一個(gè)子集R，TPQ的目標(biāo)是查詢自起點(diǎn)S出發(fā)，經(jīng)過R集合中的所有點(diǎn)并最終到達(dá)終點(diǎn)T的最優(yōu)路徑。比如復(fù)旦大學(xué)的一名學(xué)生計(jì)劃從復(fù)旦大學(xué)張江校區(qū)去往復(fù)旦大學(xué)楊浦校區(qū)，他希望途中經(jīng)過一個(gè)理發(fā)店理發(fā)、一個(gè)餐館吃飯和一個(gè)書店買書。針對(duì)這一特定場(chǎng)景，TPQ會(huì)輸出起點(diǎn)為復(fù)旦大學(xué)張江校區(qū)，終點(diǎn)為復(fù)旦大學(xué)楊浦校區(qū)，途經(jīng)理發(fā)店、餐館和書店的最優(yōu)路徑。當(dāng)然，最優(yōu)不同最優(yōu)路徑標(biāo)準(zhǔn)的不同可能會(huì)導(dǎo)致最終輸出路徑的不同，比如最短距離路徑或者最短時(shí)間路徑。TPQ查詢問題可以被視為旅行售貨員（TSP）問題的一般化。由于TSP問題是NP難的，TSP問題又可以規(guī)約為TPQ查詢問題，所以TPQ查詢問題也是NP難的。TSP問題向TPQ查詢問題規(guī)約的過程如下：假定每個(gè)類別只包含唯一的一個(gè)點(diǎn)，TSP問題約定遍歷所有的點(diǎn)，由于每個(gè)類別只包含一個(gè)點(diǎn)，此時(shí)TSP問題等價(jià)于約定遍歷所有的類別，顯然滿足TPQ問題的約定條件，TSP問題是TPQ問題的特例。TPQ問題類似連續(xù)最近鄰查詢問題，然而，用于解決連續(xù)最近鄰查詢問題的算法并不能產(chǎn)生很好的TPQ路徑。專門處理TPQ問題的算法研究工作非常必要。由于TPQ查詢問題是NP難的，不存在多項(xiàng)式復(fù)雜度之內(nèi)的算法，有效地解決TPQ查詢問題主要依靠近似算法，近似比率的依據(jù)主要是類別的數(shù)量m和類別的最大維度p，因此TPQ查詢問題的近似算法主要包括基于類別數(shù)量m的近似算法和機(jī)遇類別最大維度p的近似算法。基于類別數(shù)量m的近似算法主要有最近鄰算法（ANN）和最小距離算法（AMD）。最近鄰算法的思想非常簡(jiǎn)單，從起點(diǎn)開始，每次訪問距離當(dāng)前已經(jīng)訪問節(jié)點(diǎn)最近的類別中的鄰居節(jié)點(diǎn)，并且保證該最近鄰居節(jié)點(diǎn)尚未被訪問。形式化定義如下：給定部分路徑Tk,(k<m)，Tk+1是通過訪問距離當(dāng)前節(jié)點(diǎn)vtk最近的尚未被訪問過的類別中的節(jié)點(diǎn)vtk+1獲得的。最終，最近鄰算法將重點(diǎn)加入路徑中。最小距離算法分兩階段來進(jìn)行，第一階段選取一個(gè)節(jié)點(diǎn)集合{v1,…vm}，每個(gè)類別取且僅取一個(gè)節(jié)點(diǎn)，并且保證取得的節(jié)點(diǎn)是該類別中保證開銷c(S,vi)+c(vi,E)最小的那個(gè)節(jié)點(diǎn)。第二階段以最近鄰順序來遍歷第一階段選取的節(jié)點(diǎn)集合，生成一條從起點(diǎn)E到終點(diǎn)E并經(jīng)過每個(gè)類別中一個(gè)節(jié)點(diǎn)的路徑?；陬悇e最大維度p的近似算法是一種線性規(guī)劃算法。假定TPQ問題約定起點(diǎn)S和終點(diǎn)E相同，并把新的問題稱為循環(huán)TPQ問題，即LTPQ問題。傳統(tǒng)TPQ問題可以通過添加添加僅包含終點(diǎn)E的類別來轉(zhuǎn)化為循環(huán)TPQ問題，如果可以找到解決循環(huán)TPQ問題的線性規(guī)劃算法，那最終也可以通過該算法的變種來解決TPQ問題。令A(yù)=(aji)為給定圖G的m*(n+1)矩陣，行m代表類別的數(shù)量，列n+1代表節(jié)點(diǎn)數(shù)量。矩陣A中的元素以如下順序來安排：如果vi屬于類別Rj，則aji=1，否則aji=0。在這種條件下，顯然每個(gè)類別最多包含p個(gè)節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)v在某一給定的路徑中時(shí)，令示性函數(shù)y(v)=1，否則令y(v)=0。同理，當(dāng)邊e在某一給定的路徑中時(shí)，令示性函數(shù)x(e)=1，否則令x(e)=0。對(duì)于任何集合S，S是V的子集，令delta(S)為割（S，V\S）中的邊的集合，則LTPQ問題的線性約束如下： 在此約束條件之下，求得令取最小值的解即可解決LTPQ問題。一旦解決了LTPQ問題，自然就可以解決傳統(tǒng)TPQ問題。2.1.2OSR問題概述 最近鄰查詢只在找到距離給定點(diǎn)最近的鄰居節(jié)點(diǎn)，比如查詢距離某人所處位置最近的飯店、書店等等。最近鄰查詢的重要性顯而易見，然而，更多時(shí)候用戶更關(guān)心的是能不能找到一條以某一順序經(jīng)過某些給定節(jié)點(diǎn)的路徑，這條路徑使他行走的距離或者花費(fèi)的時(shí)間最短。此類查詢不僅在導(dǎo)航系統(tǒng)、在線地圖服務(wù)等應(yīng)用甚廣，在只能防御系統(tǒng)等要求快速響應(yīng)的系統(tǒng)中也有重要應(yīng)用。 假定以如下順序駕車穿過一個(gè)城鎮(zhèn)：第一步離開車庫(kù)前往加油站給汽車加油，第二步前往書店買一本需求已久的書，最后一步前往郵局郵遞一個(gè)包裹。當(dāng)然，每個(gè)駕駛員都希望途經(jīng)這些目的地所行駛的距離最短或者花費(fèi)的時(shí)間最短。換句話說，要找到一條經(jīng)過加油站、書店、郵局的路徑，這條路徑的距離或者花費(fèi)的時(shí)間最短。尋找此類路徑的問題即OSR查詢問題。 OSR查詢問題的算法主要分為基于向量空間的算法和基于矩陣空間的算法，最基本的算法為基于Dijkstra的算法。假設(shè)在給定起點(diǎn)p，順序M和節(jié)點(diǎn)集合{Um1,Um2…Umn}的網(wǎng)絡(luò)中做OSR查詢。首先根據(jù)給定的網(wǎng)絡(luò)構(gòu)建一個(gè)加權(quán)有向圖G，圖G的節(jié)點(diǎn)集合，圖G的邊按如下規(guī)則生成：起點(diǎn)p有指向集合Um1中所有點(diǎn)的邊，對(duì)于1<=i<m-1，任意Umi集合中的點(diǎn)都有指向Umi+1集合中的所有點(diǎn)的邊，如圖：圖G中每條邊的權(quán)重是根據(jù)連接該邊的兩個(gè)節(jié)點(diǎn)之間的距離來分配的，該圖其實(shí)枚舉了在給定順序M和集合U的條件下所有可能的路徑。根據(jù)OSR的定義，OSR路徑其實(shí)是使得開銷最小的那條路徑。具體到圖G而言，OSR查詢其實(shí)就是查詢從起點(diǎn)p到集合Umm中所有節(jié)點(diǎn)的最短路徑，返回所有路徑中開銷最短的路徑即可。Dijkstra算法可以找到起點(diǎn)p到集合Umm中所有節(jié)點(diǎn)的最短路徑，輔之以線性復(fù)雜度的搜索算法即可找到所有路徑中開銷最短的一條，即OSR路徑。2.1.3KOR問題概述KOR（Keyword-awareOptimalRoute）查詢?yōu)榱颂岣哂脩粼诓樵冎械撵`活性，可以找到一條覆蓋用戶指定關(guān)鍵字，滿足預(yù)算條件（比如，時(shí)間，花費(fèi)）并使得總共的受歡迎程度最高。比如，可以通過KOR查詢查找一條經(jīng)過電影院和書店的不超過3小時(shí)的最受歡迎的路徑。其中每個(gè)PoI（Pointofinterest）都有一個(gè)自己的用戶評(píng)分，來源可以是TripAdvisor，F(xiàn)ourSquare等等。KOR查詢問題是NP難問題，不存在多項(xiàng)式時(shí)間復(fù)雜度之內(nèi)的精確算法。暴力搜索解空間可以解決KOR查詢問題，但是其時(shí)間復(fù)雜度為指數(shù)級(jí)，在實(shí)際應(yīng)用中價(jià)值甚微。要想在合理的時(shí)間限制之內(nèi)解決KOR查詢問題，只能依靠近似算法。近似算法的思想很簡(jiǎn)單，大都是以當(dāng)前所獲路徑為基礎(chǔ)，根據(jù)近似策略選取剩余節(jié)點(diǎn)中最適合的節(jié)點(diǎn)作為下一節(jié)點(diǎn)，將這一節(jié)點(diǎn)添加到路徑中，直到終點(diǎn)也被添加到路徑中。不同的近似算法往往具有不同的精度和效率。一般而言，近似算法相對(duì)查詢空間的偏差越大，算法的效率越高，但是所獲結(jié)果的精度越低；近似算法相對(duì)查詢空間的偏差越小，所獲結(jié)果的精度越高，但是算法的效率越低。在實(shí)際應(yīng)用中，必須權(quán)衡算法的精度和效率，針對(duì)特定的需求選擇特定的近似算法。KOR查詢問題是NP難問題，不存在多項(xiàng)式時(shí)間復(fù)雜度之內(nèi)的精確算法。暴力搜索解空間可以解決KOR查詢問題，但是其時(shí)間復(fù)雜度為指數(shù)級(jí)，在實(shí)際應(yīng)用中價(jià)值甚微。要想在合理的時(shí)間限制之內(nèi)解決KOR查詢問題，只能依靠近似算法。近似算法的思想很簡(jiǎn)單，大都是以當(dāng)前所獲路徑為基礎(chǔ)，根據(jù)近似策略選取剩余節(jié)點(diǎn)中最適合的節(jié)點(diǎn)作為下一節(jié)點(diǎn)，將這一節(jié)點(diǎn)添加到路徑中，直到終點(diǎn)也被添加到路徑中。不同的近似算法往往具有不同的精度和效率。一般而言，近似算法相對(duì)查詢空間的偏差越大，算法的效率越高，但是所獲結(jié)果的精度越低；近似算法相對(duì)查詢空間的偏差越小，所獲結(jié)果的精度越高，但是算法的效率越低。在實(shí)際應(yīng)用中，必須權(quán)衡算法的精度和效率，針對(duì)特定的需求選擇特定的近似算法。KOR查詢問題是NP難問題，不存在多項(xiàng)式時(shí)間復(fù)雜度之內(nèi)的精確算法。暴力搜索解空間可以解決KOR查詢問題，但是其時(shí)間復(fù)雜度為指數(shù)級(jí)，在實(shí)際應(yīng)用中價(jià)值甚微。要想在合理的時(shí)間限制之內(nèi)解決KOR查詢問題，只能依靠近似算法。近似算法的思想很簡(jiǎn)單，大都是以當(dāng)前所獲路徑為基礎(chǔ)，根據(jù)近似策略選取剩余節(jié)點(diǎn)中最適合的節(jié)點(diǎn)作為下一節(jié)點(diǎn)，將這一節(jié)點(diǎn)添加到路徑中，直到終點(diǎn)也被添加到路徑中。不同的近似算法往往具有不同的精度和效率。一般而言，近似算法相對(duì)查詢空間的偏差越大，算法的效率越高，但是所獲結(jié)果的精度越低；近似算法相對(duì)查詢空間的偏差越小，所獲結(jié)果的精度越高，但是算法的效率越低。在實(shí)際應(yīng)用中，必須權(quán)衡算法的精度和效率，針對(duì)特定的需求選擇特定的近似算法。2.2KDR查詢2.2.1引言一個(gè)KOR查詢只返回將所有關(guān)鍵字的重要程度同樣對(duì)待的一條路徑。然而，用戶可能有著對(duì)于關(guān)鍵字不同的重視程度。比如一個(gè)用戶可能認(rèn)為電影院的受歡迎程度更重要，而另外的一個(gè)用戶認(rèn)為書店的評(píng)分更重要。KOR查詢不能個(gè)性化對(duì)待不同的用戶。假設(shè)用戶想要找到一條“從所住賓館到機(jī)場(chǎng)，經(jīng)過電影院，咖啡館和書店的一條行程時(shí)間不超過6個(gè)小時(shí)”的路徑，并且希望所經(jīng)過的電影院咖啡館和書店在大眾點(diǎn)評(píng)上評(píng)分較高。圖一：找到從s到t的個(gè)性化偏好路徑如圖所示，s和t表示起始點(diǎn)和目的的。每個(gè)結(jié)點(diǎn)上的數(shù)字表示大眾點(diǎn)評(píng)上的評(píng)分。每條實(shí)線上的數(shù)字表示這條路徑需要的時(shí)間。結(jié)點(diǎn)的不同形狀代表他們不同的關(guān)鍵字，即不同類型的店鋪。從上一個(gè)需求來看，路徑查詢的要求是：始于s，目的地是t，經(jīng)過電影院，咖啡館和書店。這里有三條路徑，route1,2,3均滿足這些必要條件。如果這個(gè)用戶更重視書店的評(píng)分，Route2對(duì)她來說是最好的選擇。如果用戶相比于書店更重視咖啡館，Route3則更好。然而，KOR查詢只會(huì)返回Route2作為最優(yōu)路徑。為了解決這個(gè)問題，一個(gè)直接的解決方法是要求用戶是輸入每個(gè)關(guān)鍵字的權(quán)重。但是，這樣降低了用戶友好型，因?yàn)槠帽旧聿⒉蝗菀妆恢苯恿炕?。另外一種解決方法是，找到用戶可能想要的所有路徑，如找到Route2和route3作為最終的結(jié)果。這樣用戶可以根據(jù)自己的喜好在結(jié)果在進(jìn)行進(jìn)一步的選擇。這是一種新型的路徑查詢方法，我們稱之為支配路徑查詢（keyword-awaredominantroute）。支配路徑查詢的定義是（1）可行路徑需要滿足要求的起始結(jié)點(diǎn)和目的節(jié)點(diǎn)，經(jīng)過制定的關(guān)鍵字，不超過該制定的預(yù)算限制。（2）在所有的可行路徑中，KDR返回其中的一個(gè)支配路徑的子集，即子集中的任何一條路徑不被剩余的可行路徑所支配。這樣，可以保證用戶需要的路徑一定在此子集中。與KOR問題類似，KDR也是NP難問題。對(duì)于KDR問題，具體以精確算法DR和啟發(fā)式算法FDR進(jìn)行實(shí)現(xiàn)并實(shí)驗(yàn)驗(yàn)證。2.2.2支配路徑查詢定義我們使用有向圖表示路網(wǎng)[1]，其中V表示結(jié)點(diǎn)的集合，即PoI。表示邊的集合。雖然本文中G為有向圖，但是可以通過簡(jiǎn)單的更改適應(yīng)于無向圖中。邊E表示兩個(gè)結(jié)點(diǎn)的一條直接的路徑，其中從到的路徑表示為。表示這條路徑的預(yù)算值，如時(shí)間花費(fèi)，路徑長(zhǎng)度。路徑表示順序經(jīng)過到的一條路徑。路徑R的預(yù)算值BS定義為R上所有邊上的預(yù)算分?jǐn)?shù)的總和，即 每一個(gè)結(jié)點(diǎn)表示一個(gè)包含關(guān)鍵字集合（）的結(jié)點(diǎn)，包含一個(gè)評(píng)分表示該結(jié)點(diǎn)的受歡迎程度。路徑R覆蓋的關(guān)鍵字集合可以表示為一個(gè)KDR（Keyword-awareDominantRoute）查詢可以表示為一個(gè)四元組Q=(s,t,,)，其中s為源點(diǎn)，t是目標(biāo)點(diǎn)，為關(guān)鍵字集合，是預(yù)算值限制。我們用Rs,t表示從s到t點(diǎn)的所有路徑的集合。如果一條路徑屬于Rs,t并且預(yù)算值小于預(yù)算值限制，覆蓋了所有指定的關(guān)鍵字，我們可以將其視為一條可行路徑，可行路徑的集合使用表示。為了定義基于關(guān)鍵字的路徑支配，先進(jìn)行目標(biāo)向量的定義。定義一：目標(biāo)向量給定一條路徑和一個(gè)關(guān)鍵字集合,的目標(biāo)向量表示針對(duì)于的路徑評(píng)分。路徑R的目標(biāo)向量的每一項(xiàng)表示每一個(gè)關(guān)鍵字覆蓋的R上的結(jié)點(diǎn)對(duì)應(yīng)的最大目標(biāo)值，即,，其中表示查詢關(guān)鍵字集合的大小,表示根據(jù)字母序的第i個(gè)關(guān)鍵字。圖：路網(wǎng)G如圖所示，這是一個(gè)路網(wǎng)示例圖G，其中有五種關(guān)鍵字，t1,t2,……t5，每個(gè)用不同的形狀代表。為了簡(jiǎn)化，每個(gè)節(jié)點(diǎn)有一個(gè)關(guān)鍵字和一個(gè)評(píng)分（標(biāo)示與每個(gè)結(jié)點(diǎn)旁邊的括號(hào)中）。每條邊上有一個(gè)數(shù)字標(biāo)示這段路徑的預(yù)算值。則對(duì)于和有和。定義二：可行路徑間的支配關(guān)系給定一個(gè)KDR查詢，可行路徑和的目標(biāo)向量分別為和。我們認(rèn)為被支配（）如果1)對(duì)所有成立并且存在使得；或者2)構(gòu)成和的目標(biāo)向量的結(jié)點(diǎn)是相同的，即和相同，并且。KDR查詢是在可行路徑中篩選支配路徑。定義三：已知關(guān)鍵字的支配路徑給定一個(gè)KDR查詢,支配路徑滿足不存在且的可行路徑。我們用表示查詢Q對(duì)應(yīng)的支配路徑集合，同樣的，被支配的路徑集合使用表示。如圖所示，給定一個(gè)KDR查詢，支配路徑為和。其中目標(biāo)向量和，預(yù)算值分別為和。證明：KDR問題是NP難問題這個(gè)問題可以從GTSP（generalizedtravelingsalesmanproblem）問題推導(dǎo)得到。其中GTSP屬于NP難問題。GTSP問題是從起始點(diǎn)到終點(diǎn)找到一條經(jīng)過了所有組的路徑，其中所有的結(jié)點(diǎn)都被分組。如果我們將KDR問題中的結(jié)點(diǎn)評(píng)分設(shè)為一個(gè)固定值，則這個(gè)問題就被轉(zhuǎn)化為GTSP問題。故而KDR問題是NP難問題。2.3DR算法傳統(tǒng)的路徑查詢算法一般基于深度優(yōu)先遍歷和廣度優(yōu)先遍歷。從初始結(jié)點(diǎn)出發(fā)，不停的在路徑的末端增加相鄰的結(jié)點(diǎn)，直到到達(dá)終點(diǎn)。經(jīng)過所有的遍歷之后，從所有的可行路徑中選出支配路徑作為最終的結(jié)果。然而，這種查詢對(duì)于路網(wǎng)對(duì)應(yīng)的圖而言計(jì)算量太大，時(shí)間和空間復(fù)雜度太高。為了在保證準(zhǔn)確性的情況下，降低算法的時(shí)間和空間復(fù)雜度，KDR問題可以用一種新的方案解決，我們稱之為DR算法。在DR算法中，初始的路徑為從初始結(jié)點(diǎn)到終點(diǎn)的最短路徑，再不停的向路徑中添加帶有關(guān)鍵字的結(jié)點(diǎn)從而得到最終的支配路徑。下面在介紹DR算法之前，先進(jìn)行一些必要的定義。定義四：關(guān)鍵字結(jié)點(diǎn)給定一個(gè)KDR查詢,我們用表示對(duì)應(yīng)的關(guān)鍵字集合，中的每一個(gè)結(jié)點(diǎn)被稱為一個(gè)關(guān)鍵字結(jié)點(diǎn)。每一條路徑可以用關(guān)鍵字結(jié)點(diǎn)分割為小段。比如，中為關(guān)鍵字結(jié)點(diǎn)，可以被分為和。定義五：關(guān)鍵字結(jié)點(diǎn)路徑給定一個(gè)KDR查詢,關(guān)鍵字結(jié)點(diǎn)集合為,如果一條路徑被其關(guān)鍵字結(jié)點(diǎn)分割后的子路徑均為從其起始結(jié)點(diǎn)到終點(diǎn)的最短路徑，我們稱之為關(guān)鍵字結(jié)點(diǎn)路徑。中所有的關(guān)鍵字結(jié)點(diǎn)路徑組成一個(gè)集合我們使用表示。如果一條路徑為支配路徑，那么很明顯，這一條路徑一定是一條關(guān)鍵字結(jié)點(diǎn)路徑。如果一條關(guān)鍵字結(jié)點(diǎn)路徑所經(jīng)過的關(guān)鍵字結(jié)點(diǎn)是確定的，那么這條路徑是確定的。比如，路徑可以被表示為關(guān)鍵字結(jié)點(diǎn)序列(KN-sequence)。定義六：潛在路徑如果一條路徑滿足,and，那么這條路徑可以被稱為一條潛在路徑。我們用表示從到的最短路徑。對(duì)于一個(gè)關(guān)鍵字路徑R，其關(guān)鍵字結(jié)點(diǎn)序列為，其關(guān)鍵字結(jié)點(diǎn)序列預(yù)算值可以計(jì)算為目標(biāo)向量為：,關(guān)鍵字結(jié)點(diǎn)序列KS的預(yù)算值是序列中所有連續(xù)的兩個(gè)結(jié)點(diǎn)的最短距離的總和，和R的預(yù)算值相等。KS的目標(biāo)向量的計(jì)算方法和R類似。如，給定一個(gè)KDR查詢，是一條對(duì)應(yīng)著關(guān)鍵字序列為初始路徑。其中對(duì)應(yīng)著關(guān)鍵字序列為的路徑的目標(biāo)向量為。定義七：路徑修正操作我們使用路徑修正操作來將關(guān)鍵字結(jié)點(diǎn)插入到關(guān)鍵字結(jié)點(diǎn)路徑R中，通過調(diào)整已有的關(guān)鍵字結(jié)點(diǎn)的順序來得到最小的預(yù)算分?jǐn)?shù)。對(duì)于一條屬于KR的路徑且關(guān)鍵字結(jié)點(diǎn)序列為和關(guān)鍵字結(jié)點(diǎn)v,,,，(=0表示結(jié)點(diǎn))經(jīng)過一些路徑修正操作，一個(gè)潛在路徑R可能成為一個(gè)可行路徑。定義八：潛在路徑祖先對(duì)于屬于KR的路徑和,如果，則我們認(rèn)為路徑是的父母路徑如果可以由通過一系列的路徑修正操作得到，即,，我們認(rèn)為是的祖先路徑。給定一個(gè)KDR查詢,最終提供的結(jié)果路徑必須覆蓋所有的關(guān)鍵字。最初的路徑的關(guān)鍵字結(jié)點(diǎn)序列由初始結(jié)點(diǎn)和結(jié)束結(jié)點(diǎn)構(gòu)成，然后不停的添加關(guān)鍵字結(jié)點(diǎn)到路徑中直至覆蓋到所有的關(guān)鍵字。在插入關(guān)鍵字結(jié)點(diǎn)的過程中，我們暫時(shí)不考慮兩個(gè)相鄰的關(guān)鍵字結(jié)點(diǎn)中間經(jīng)過的結(jié)點(diǎn)（兩點(diǎn)間的最短路徑）。在得到支配路徑的關(guān)鍵字結(jié)點(diǎn)序列之后，我們使用最短路徑算法算出相鄰結(jié)點(diǎn)間的最短路徑[4]。為了減少路徑修正的計(jì)算量，我們找到了幾個(gè)有效的剪枝策略。（a）剪枝策略一KDR問題的一個(gè)約束是預(yù)算限制——如果一條路徑的預(yù)算分?jǐn)?shù)超出了預(yù)算限制，那么這條路徑需要被刪除并且不能夠繼續(xù)進(jìn)行修正因?yàn)樗淖訉O路徑一定也違背了這個(gè)要求，證明如下。證明：如果且,則.將路徑和的關(guān)鍵字結(jié)點(diǎn)序列分別表示為和。因?yàn)槭墙?jīng)過的最短路徑。路徑（）滿足。的預(yù)算分?jǐn)?shù)可以計(jì)算為由此可得（b）剪枝策略二在一些特定的情況下，一個(gè)潛在路徑可以被可行路徑剪枝。如果這個(gè)潛在路徑已匹配關(guān)鍵字部分對(duì)應(yīng)的目標(biāo)向量被對(duì)應(yīng)的可行路徑支配，且此可行路徑在未匹配關(guān)鍵字部分對(duì)應(yīng)的目標(biāo)向量是全圖最大值。對(duì)于一個(gè)潛在路徑,如果存在可行路徑使得在上，且對(duì)于是全圖最大值,那么被支配。基于這些策略的DR算法偽代碼見下圖。在DR算法中，首先新建一個(gè)以關(guān)鍵字結(jié)點(diǎn)序列為元的隊(duì)列Q，向隊(duì)列Q插入關(guān)鍵字結(jié)點(diǎn)序列。然和，當(dāng)Q不為空的時(shí)候，不斷的從Q中提取潛在路徑并且用一個(gè)沒有被覆蓋的關(guān)鍵字的相應(yīng)結(jié)點(diǎn)插入到序列中（6-9行）。如果這條新的路徑滿足預(yù)算值限制并且不被已有的可行路徑支配（FdominatePR(F,R)值為假），則將此路徑添加到隊(duì)列中（8-9行）。否則，如果這條路徑是可行路徑，通過FdominatePR(F,R)函數(shù)檢驗(yàn)是否R被路徑F所支配，從而篩選掉隊(duì)列中所有被R支配的可行路徑（13-14行）。在隊(duì)列Q為空之后，我們輸出所有的可行路徑，此時(shí)的可行路徑即為支配路徑。算法的復(fù)雜度為，其中n是擁有最多數(shù)量的關(guān)鍵字對(duì)應(yīng)的結(jié)點(diǎn)數(shù)目，k是關(guān)鍵字的個(gè)數(shù)。證：DR算法的正確性由于支配路徑必為關(guān)鍵詞節(jié)點(diǎn)路徑，所以整個(gè)搜索空間應(yīng)該等價(jià)于不盡興任何剪枝操作的關(guān)鍵詞節(jié)點(diǎn)全排列。不管引理2和引理3采用的剪枝策略，DR算法的搜索空間是滿足如下條件的關(guān)鍵詞節(jié)點(diǎn)的組合：在具有相同關(guān)鍵詞節(jié)點(diǎn)的路徑之中，潛在路徑擁有最小的開銷。根據(jù)定義2，開銷不是最小的路徑應(yīng)該被別的路徑支配，這些路徑應(yīng)當(dāng)在改進(jìn)之后被刪除。因此，得證。2.3FDR算法FDR算法是基于DR算法的啟發(fā)式算法。FDR算法的基本思路來源于現(xiàn)實(shí)生活中人們?cè)诼窂皆O(shè)定中會(huì)朝著一個(gè)方向走而不會(huì)折返。FDR算法的對(duì)已有的不完全路徑的擴(kuò)充方法是在最后一個(gè)結(jié)點(diǎn)后面添加一個(gè)更接近于終點(diǎn)的結(jié)點(diǎn)。即，每一次擴(kuò)充都使得這條路徑的最終結(jié)點(diǎn)距離終點(diǎn)更近。具體說來就是，當(dāng)我們選擇一個(gè)未被覆蓋的關(guān)鍵字結(jié)點(diǎn)作為下一個(gè)結(jié)點(diǎn)時(shí)，這個(gè)結(jié)點(diǎn)到終點(diǎn)的距離小于上一個(gè)擴(kuò)充的結(jié)點(diǎn)。基于這個(gè)策略，F(xiàn)DR可以迅速篩選掉一些不需要考慮的結(jié)點(diǎn)。給定一個(gè)KDR查詢,對(duì)于一個(gè)關(guān)鍵字結(jié)點(diǎn)序列為的關(guān)鍵字結(jié)點(diǎn)路徑R，如果，則其為不完全路徑。對(duì)R的一次從到的擴(kuò)充，如果，則我們認(rèn)為這是一次有效的前向擴(kuò)充。這里表示一次嚴(yán)格的前向擴(kuò)充。當(dāng)，表示只需要滿足寬松的，向后不超過的前向擴(kuò)充要求即可。圖：前向擴(kuò)充如圖所示，給定一個(gè)終點(diǎn)t，對(duì)于一個(gè)目前到的不完全路徑R，兩條平行線和將圖G分為三部分。當(dāng)，左側(cè)的結(jié)點(diǎn)違背了前向擴(kuò)充的要求，，右側(cè)的結(jié)點(diǎn)是擴(kuò)充的候選結(jié)點(diǎn)。表示的情況。對(duì)于對(duì)應(yīng)關(guān)鍵字結(jié)點(diǎn)序列為的路徑R，我們用來表示下一個(gè)結(jié)點(diǎn)是v的前向擴(kuò)充。并且，R的擴(kuò)充后的關(guān)鍵字結(jié)點(diǎn)序列為?；谇跋驍U(kuò)充機(jī)制，我們選擇一個(gè)未被覆蓋的關(guān)鍵字對(duì)應(yīng)的結(jié)點(diǎn)是的當(dāng)前路徑更加接近終點(diǎn)直到此路徑覆蓋所有關(guān)鍵字成為一條可行路徑。如圖所示，給定一個(gè)KDR查詢，對(duì)應(yīng)關(guān)鍵字結(jié)點(diǎn)序列為的路徑R，的最終結(jié)點(diǎn)是，如果，則只有為候選擴(kuò)充結(jié)點(diǎn)?；谶@個(gè)機(jī)制，我們可以得到一個(gè)新的剪枝策略。剪枝策略（未完成路徑的相互支配）對(duì)于未完成路徑和，分別對(duì)應(yīng)的關(guān)鍵字結(jié)點(diǎn)序列為和如果，，且，則支配。如圖所示，對(duì)于分別對(duì)應(yīng)于和的和，他們的最終結(jié)點(diǎn)均為，覆蓋的關(guān)鍵字集合相同。且小于。這樣無論下一個(gè)結(jié)點(diǎn)是哪個(gè)，得到的最終的可行路徑一定可以支配最終的可行路徑。FDR算法的偽代碼的框架結(jié)構(gòu)和DR算法類似。在FDR算法中，根據(jù)前向擴(kuò)充機(jī)制，F(xiàn)DR算法不斷向未完成路徑添加未匹配關(guān)鍵字的結(jié)點(diǎn)從而更接近終點(diǎn)。與DR算法類似，我們從隊(duì)列Q中獲取一條未完成路徑并且進(jìn)行前向擴(kuò)充。如果新的路徑滿足預(yù)算值限制并且不被已有的可行路徑支配（FdominatePR(F,R)函數(shù)返回值為假）則，我們將其加入到Q中（12行）。否則，如果路徑已經(jīng)是可行路徑，我們使用FdominateFR（F,R）來監(jiān)測(cè)可行路徑之間有木有互相支配的情況。如果沒有，將此路徑加入到F中。如果F中的任何一條路徑被新的可行路徑支配，則將其從F中刪除（16行）。FDR算法在最壞情況下的時(shí)間復(fù)雜度和DR相同，但是實(shí)際情況中，F(xiàn)DR需要的運(yùn)算量遠(yuǎn)小于DR。2.4實(shí)驗(yàn)評(píng)估為了檢驗(yàn)算法，我們使用openstreetmap中的真實(shí)路網(wǎng)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。數(shù)據(jù)集采用上海市的路網(wǎng)數(shù)據(jù)，包括6050個(gè)有著經(jīng)緯度信息的PoI。這些PoI被標(biāo)記為9個(gè)不同的類別包括飲食，娛樂等等。從中抽取出3個(gè)數(shù)據(jù)集分別包含2000個(gè)PoI，4000個(gè)PoI和6000個(gè)PoI，分別用Node2000，Node4000，Node6000表示。使用距離大小作為圖中邊上的預(yù)算值。PoI的評(píng)分我們隨機(jī)從1到5的數(shù)字對(duì)其進(jìn)行賦值。這些評(píng)分代表著目標(biāo)分值，分值越大表示受歡迎程度越高。我們使用不同的預(yù)算分?jǐn)?shù)限制，關(guān)鍵字結(jié)點(diǎn)個(gè)數(shù)，查詢關(guān)鍵字個(gè)數(shù)，數(shù)據(jù)集對(duì)兩個(gè)算法進(jìn)行性能和準(zhǔn)確性上的評(píng)估。其中，預(yù)算分?jǐn)?shù)限制從10000到50000。關(guān)鍵字結(jié)點(diǎn)個(gè)數(shù)從100到500。查詢關(guān)鍵字個(gè)數(shù)從2到5。數(shù)據(jù)集從2000個(gè)點(diǎn)到6000個(gè)點(diǎn)。默認(rèn)值為=20000,=200和=3。默認(rèn)數(shù)據(jù)集為Node4000.。每種情況允許50個(gè)查詢。初始結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)隨機(jī)生成。在滿足的情況下，查詢關(guān)鍵字隨機(jī)生成。程序采用VC++完成并且在Intel(R)Core(TM)i7-3770CPU@3.40GHZ平臺(tái)下運(yùn)行。2.4.1性能評(píng)估首先對(duì)兩個(gè)算法在不同預(yù)算值限制，關(guān)鍵字結(jié)點(diǎn)數(shù)目，查詢關(guān)鍵字?jǐn)?shù)目和數(shù)據(jù)集下的性能表現(xiàn)進(jìn)行評(píng)估。圖：不同預(yù)算值比較不同的預(yù)算值限制圖4表示在Node4000數(shù)據(jù)集下不同預(yù)算值限制的實(shí)驗(yàn)結(jié)果。即當(dāng)關(guān)鍵字個(gè)數(shù)為3時(shí)，預(yù)算值限制分別為10,000，20,000,30,000,40,000,和50,000時(shí)查詢的響應(yīng)時(shí)間。隨著預(yù)算值限制的增加，DR和FDR算法的運(yùn)行時(shí)間越來越長(zhǎng)，因?yàn)橐粋€(gè)較大的預(yù)算值限制對(duì)應(yīng)于更多的候選關(guān)鍵字結(jié)點(diǎn)。與DR算法相比，F(xiàn)DR算法的響應(yīng)時(shí)間增速較慢因?yàn)镕DR的前向剪枝策略使得其復(fù)雜度是線性的而DR為指數(shù)級(jí)別的。圖：不同不同的關(guān)鍵字結(jié)點(diǎn)數(shù)目圖5表示不同對(duì)應(yīng)的不同執(zhí)行時(shí)間。隨著關(guān)鍵字個(gè)數(shù)的增長(zhǎng)，DR算法越來越慢，但是FDR的變慢并不如此顯著。這是因?yàn)镈R算法的復(fù)雜度隨著關(guān)鍵字結(jié)點(diǎn)個(gè)數(shù)的增長(zhǎng)呈指數(shù)增長(zhǎng)而FDR算法可以進(jìn)行更加直接的剪枝從而降低運(yùn)算量。不同的查詢關(guān)鍵字個(gè)數(shù)圖6表示查詢關(guān)鍵字個(gè)數(shù)從2到5的情況下兩個(gè)算法的執(zhí)行時(shí)間對(duì)比。DR和FDR隨著關(guān)鍵字個(gè)數(shù)的增加而執(zhí)行時(shí)間變長(zhǎng)是因?yàn)殛P(guān)鍵字個(gè)數(shù)增加而關(guān)鍵字結(jié)點(diǎn)個(gè)數(shù)不變帶來了更多關(guān)鍵字結(jié)點(diǎn)的組合的數(shù)目。不同的數(shù)據(jù)集圖7表示不同數(shù)據(jù)集（Node2000，Node4000，Node6000）下的執(zhí)行時(shí)間的變化?？梢钥闯觯藭r(shí)時(shí)間變化并沒有顯著的規(guī)律。執(zhí)行時(shí)間的變化可能來源于不同數(shù)據(jù)集對(duì)于查詢關(guān)鍵字，預(yù)算值限制，初始結(jié)點(diǎn)終止結(jié)點(diǎn)等選擇的差異。小結(jié)這些結(jié)果表示準(zhǔn)確算法DR在關(guān)鍵字和關(guān)鍵字結(jié)點(diǎn)個(gè)數(shù)較少的情況下運(yùn)行良好。但是當(dāng)關(guān)鍵字和關(guān)鍵字結(jié)點(diǎn)個(gè)數(shù)太多的情況下，啟發(fā)式算法FDR更合適。FDR算法在大多數(shù)情況下可以找到一些路徑供用戶進(jìn)行選擇。兩個(gè)用戶對(duì)于數(shù)據(jù)集的大小的影響都很小，這是因?yàn)樗麄兊膹?fù)雜度與數(shù)據(jù)集的大小無關(guān)。2.4.2返回路徑我們對(duì)DR和FDR的返回路徑個(gè)數(shù)進(jìn)行比較。不同的預(yù)算值限制圖8表示在Node4000數(shù)據(jù)集下不同預(yù)算值限制的實(shí)驗(yàn)結(jié)果。查詢關(guān)鍵字個(gè)數(shù)設(shè)為3。因?yàn)轭A(yù)算值限制的增加允許更多關(guān)鍵字結(jié)點(diǎn)的組合所以DR和FDR的返回路徑個(gè)數(shù)均相應(yīng)的增加。不同的查詢關(guān)鍵字個(gè)數(shù)圖9表示查詢關(guān)鍵字個(gè)數(shù)從2到5的情況下返回路徑個(gè)數(shù)的變化。FDR算法在查詢關(guān)鍵字個(gè)數(shù)增加時(shí)返回路徑個(gè)數(shù)顯著減少。當(dāng)查詢關(guān)鍵字個(gè)數(shù)太大時(shí)，F(xiàn)DR可能不能找到滿足條件的路徑。

3基于預(yù)測(cè)的最小時(shí)間路徑查詢問題研究隨著經(jīng)濟(jì)和技術(shù)的飛速發(fā)展，越來越多的人們購(gòu)置私家車作為交通工具。這大大提高了人們出行的自主性和舒適度。同時(shí)道路設(shè)施也在迅猛發(fā)展中，盡可能的保障人們出行的暢通并且為人們出行提供多重選擇。但是道路的建設(shè)并不能趕上汽車數(shù)量的井噴式增加。這帶來了城市尤其是大城市的不定時(shí)擁堵，進(jìn)而影響了人們的出行體驗(yàn)。傳統(tǒng)的路徑查詢和車輛導(dǎo)航系統(tǒng)根據(jù)靜態(tài)路網(wǎng)給出從指定起始點(diǎn)到終點(diǎn)的最短路徑。然而，在實(shí)際生活中，由于擁堵現(xiàn)象在不同地點(diǎn)和不同時(shí)間的發(fā)生，路網(wǎng)中的最短路徑并不是對(duì)于用戶的最優(yōu)路徑。用戶往往需要在指定起點(diǎn)、終點(diǎn)和出發(fā)時(shí)間后得到一條時(shí)間最短的路徑，即最小時(shí)間路徑。目前已有工作基于實(shí)時(shí)數(shù)據(jù)進(jìn)行車輛導(dǎo)航（），然而，根據(jù)實(shí)時(shí)路況進(jìn)行導(dǎo)航可能會(huì)出現(xiàn)出發(fā)時(shí)設(shè)計(jì)的是一條暢通的路徑，但是當(dāng)用戶到達(dá)路徑的中點(diǎn)時(shí)，從此處到終點(diǎn)的路徑發(fā)生擁堵。實(shí)際交通情況有著復(fù)雜性和規(guī)律性，如上下班高峰期和雨雪天擁堵頻率大大高于其他情況。合理的使用歷史數(shù)據(jù)能夠大大提高預(yù)測(cè)的準(zhǔn)確性。制約基于預(yù)測(cè)的最小時(shí)間路徑查詢的發(fā)展的一個(gè)重要問題是作為移動(dòng)應(yīng)用，需要滿足響應(yīng)時(shí)間的要求和運(yùn)算空間限制。在實(shí)際路網(wǎng)環(huán)境中，基于龐大的靜態(tài)路網(wǎng)和繁多的歷史數(shù)據(jù)，傳統(tǒng)的改進(jìn)最短路徑的動(dòng)態(tài)路徑算法無法處理如此海量的數(shù)據(jù)，也沒辦法在可以接受的時(shí)間之內(nèi)給出最小時(shí)間路徑。最小時(shí)間路徑的求解方法可以分解為對(duì)路段的基于歷史數(shù)據(jù)的短時(shí)交通預(yù)測(cè)和基于路段行駛時(shí)間預(yù)測(cè)的動(dòng)態(tài)路徑查詢。3.1相關(guān)工作3.1.1短時(shí)交通預(yù)測(cè)算法交通預(yù)測(cè)是指在控制變量決策的時(shí)刻t對(duì)下一決策時(shí)刻t+1甚至t+1之后的若干連續(xù)時(shí)刻的交通流量做出預(yù)測(cè)。一般情況下，當(dāng)時(shí)刻t和時(shí)刻t+1之間的預(yù)測(cè)間隔小于15分鐘時(shí)的交通預(yù)測(cè)是短時(shí)交通預(yù)測(cè)。實(shí)際路網(wǎng)系統(tǒng)是一個(gè)復(fù)雜的時(shí)變混沌系統(tǒng)，其最重要的特征就是時(shí)變性和高度的模糊性。時(shí)變性是指即刻路況對(duì)時(shí)間的依賴程度非常高，不同時(shí)刻的路況信息差異很大，路況信息的慣性非常小，可能當(dāng)前時(shí)刻路況很好，車輛占有率很低，下一時(shí)刻或者幾個(gè)時(shí)刻后的路況會(huì)突然變得很差，車輛占有率也突然變高。模糊性是指影響具體路況的因素非常多，各因素對(duì)路況好壞的影響程度很難界定。比如天氣對(duì)路況的影響，定性方面看，雨雪天氣等比較差的天氣路況通常比較差，晴朗天氣等較好的天氣路況比較好，然而沒有方法可以定量地分析路況比較差時(shí)雨雪天氣的影響程度，路況比較好時(shí)晴朗天氣的影響程度。當(dāng)然，阻礙交通預(yù)測(cè)的不僅只有是實(shí)際路網(wǎng)系統(tǒng)的時(shí)變性和模糊性，還有其他方面如人為因素和非人為因素等。人為因素有交通故障、司機(jī)駕駛技術(shù)、不同性別的司機(jī)的突發(fā)情況的處理技巧不同等。非人為因素主要是指自然因素，比如天氣等一些不可抗因素。這些因素對(duì)交通預(yù)測(cè)帶來了困難，尤其是短時(shí)交通預(yù)測(cè)。短時(shí)交通不同于較長(zhǎng)時(shí)期的交通預(yù)測(cè)，干擾因素對(duì)其的影響更大，規(guī)律性更加模糊。實(shí)際路網(wǎng)系統(tǒng)的時(shí)變性和模糊性限制了長(zhǎng)期預(yù)測(cè)的準(zhǔn)確性，實(shí)際路網(wǎng)系統(tǒng)中長(zhǎng)期預(yù)測(cè)的實(shí)用價(jià)值不高。與長(zhǎng)期交通預(yù)測(cè)不同，短時(shí)交通預(yù)測(cè)致力于根據(jù)當(dāng)前時(shí)刻路況來預(yù)測(cè)未來15分鐘甚至是5分鐘的路況，誤差率相對(duì)于長(zhǎng)期預(yù)測(cè)要低的多，預(yù)測(cè)的準(zhǔn)確性也比較高。根據(jù)短時(shí)交通預(yù)測(cè)確定短時(shí)路況信息，輔之以路徑搜索算法，是實(shí)際動(dòng)態(tài)路網(wǎng)系統(tǒng)中查找最小時(shí)間路徑的標(biāo)準(zhǔn)解決方法。用于進(jìn)行短時(shí)交通預(yù)測(cè)的方法主要有兩類，即參數(shù)回歸和非參數(shù)回歸。參數(shù)回歸的模型在參數(shù)成立的前提之下，參數(shù)回歸的預(yù)測(cè)精度非常高，對(duì)于小樣本的預(yù)測(cè)效果也比較好。然而，參數(shù)回歸設(shè)定回歸函數(shù)的形式已知，回歸模型限制也比較多，比如要求樣本數(shù)據(jù)服從某種數(shù)據(jù)分布、隨機(jī)變量與誤差之間獨(dú)立等，而實(shí)際數(shù)據(jù)往往無法嚴(yán)格滿足這些要求。另外一種預(yù)測(cè)方法是非參數(shù)回歸方法。非參數(shù)回歸對(duì)輸入數(shù)據(jù)沒有嚴(yán)格的限定，它依賴于根據(jù)歷史數(shù)據(jù)來確定輸入和輸出之間的關(guān)系。非參數(shù)回歸的回歸函數(shù)限制比較少，形式自由，對(duì)數(shù)據(jù)的分布沒有強(qiáng)制性要求，模型的預(yù)測(cè)精度也比較高，對(duì)非線性、非齊次的預(yù)測(cè)問題具有很好的效果。新采集到的數(shù)據(jù)可以方便地添加到歷史數(shù)據(jù)之中，形成非參數(shù)預(yù)測(cè)的新數(shù)據(jù)源，而不像參數(shù)回歸那樣需要對(duì)各種參數(shù)進(jìn)行費(fèi)時(shí)的調(diào)整。另外，非參數(shù)回歸不對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，保持了數(shù)據(jù)的完整性，相對(duì)于參數(shù)回歸預(yù)測(cè)更加準(zhǔn)確。參數(shù)回歸主要包括歷史平均、時(shí)間序列、卡爾曼濾波、小波理論和神經(jīng)網(wǎng)絡(luò)等。歷史平均包括等權(quán)重歷史平均算法和加權(quán)歷史平均算法。等權(quán)重歷史平均算法通過將歷史數(shù)據(jù)相加并將和除以歷史數(shù)據(jù)的個(gè)數(shù)計(jì)算得到。加權(quán)歷史平均通過對(duì)不同的數(shù)據(jù)分配不同的權(quán)重，將數(shù)據(jù)乘以權(quán)重并求和得到。加權(quán)歷史平均回歸模型受權(quán)重分配因素的影響非常大，不同的權(quán)重分配得到的回歸結(jié)果相差很大。然而，沒有標(biāo)準(zhǔn)的權(quán)重分配算法來保證權(quán)重分配的合理性，權(quán)重分配必須要通過不斷地迭代調(diào)整來達(dá)到最優(yōu)。時(shí)間序列模型是根據(jù)觀測(cè)得到的時(shí)間序列數(shù)據(jù)（按時(shí)間次序觀測(cè)到的一系列時(shí)刻的數(shù)據(jù)），通過最大似然法等參數(shù)估計(jì)模型來進(jìn)行。最著名的時(shí)間序列模型是ARMA(AutoRegressionMovingAverage)模型，ARMA模型全稱是自回歸移動(dòng)平均模型。當(dāng)時(shí)間序列本身不平穩(wěn)的時(shí)候，ARMA模型無能為力，因此又提出了ARIMA模型，即自回歸和移動(dòng)平均模型。ARIMA模型可以有效應(yīng)對(duì)不平穩(wěn)的時(shí)間序列。卡爾曼濾波（KalmanFiltering）通過系統(tǒng)輸入輸出觀測(cè)數(shù)據(jù)，利用線性系統(tǒng)狀態(tài)方程對(duì)系統(tǒng)狀態(tài)進(jìn)行最優(yōu)估計(jì)的算法。因?yàn)橥ㄟ^系統(tǒng)觀測(cè)的數(shù)據(jù)包括系統(tǒng)中得干擾和噪聲，因此最有估計(jì)也可以看做是濾波過程。小波理論將系統(tǒng)狀態(tài)變化視為小得波形的波動(dòng)，通過分析波形的變動(dòng)趨勢(shì)來預(yù)測(cè)。小波理論認(rèn)為系統(tǒng)狀態(tài)的變動(dòng)具有衰減性和波動(dòng)性，具有振幅正負(fù)相間的震蕩形式。神經(jīng)網(wǎng)絡(luò)模型的靈感來源于動(dòng)物特別是大腦的中樞神經(jīng)系統(tǒng)的工作方式，神經(jīng)網(wǎng)絡(luò)模型被用于估計(jì)依賴于大量輸入的未知近似函數(shù)，它可以根據(jù)輸入的計(jì)算值，通過機(jī)器學(xué)習(xí)、模式識(shí)別等構(gòu)建自適應(yīng)預(yù)測(cè)系統(tǒng)，以預(yù)測(cè)之后的趨勢(shì)。非參數(shù)回歸主要包括k近鄰算法、正交回歸、樣條光滑等。k近鄰算法一種用來進(jìn)行分類或者回歸的非參數(shù)方法。無論是分類還是回歸，k近鄰算法的輸入特征空間都k個(gè)最近的訓(xùn)練樣本，輸出則取決于k近鄰是用來分類還是用來回歸。當(dāng)k近鄰用于分類時(shí)，輸出是類屬。一個(gè)對(duì)象的最終類屬由其鄰居投票的多少來決定，最終標(biāo)記為投票最多的類屬。當(dāng)k為1時(shí)，k近鄰?fù)嘶癁樽罱?，此時(shí)其類屬為其最近的鄰居。當(dāng)k近鄰用于回歸時(shí)，輸出是對(duì)象的屬性值，其值得大小為k個(gè)最近鄰居的屬性平均值。k近鄰算法是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一，它是一種基于實(shí)例的學(xué)習(xí)方法（延遲學(xué)習(xí)），該算法的輸出只保證局部最優(yōu)，對(duì)全局最優(yōu)沒有任何承諾，它將所有的計(jì)算推遲到分類或者回歸的最后時(shí)刻。k近鄰算法作為一種有監(jiān)督的機(jī)器學(xué)習(xí)算法，并沒有明顯的訓(xùn)練過程，然而它要求其鄰居的類屬或者屬性值已知。不管是分類k近鄰還是回歸k近鄰，不同鄰居的權(quán)重往往不同，距離目標(biāo)對(duì)象最近的鄰居占有的權(quán)重應(yīng)該較大，距離目標(biāo)對(duì)象較遠(yuǎn)的鄰居占有的權(quán)重應(yīng)該較小，如此才能保證在最終的決策過程中，距離目標(biāo)對(duì)象較近的鄰居的貢獻(xiàn)較大，距離目標(biāo)對(duì)象較遠(yuǎn)的鄰居的貢獻(xiàn)較小。一個(gè)常用的分配權(quán)重策略是賦予每個(gè)鄰居的權(quán)重為1/d，d為到目標(biāo)對(duì)象的距離。正交回歸用于檢驗(yàn)兩個(gè)連續(xù)變量即響應(yīng)變量和預(yù)測(cè)變量之間的線性關(guān)系。不同于簡(jiǎn)單的線性回歸，正交回歸中得響應(yīng)變量和預(yù)測(cè)變量包含測(cè)量誤差。而在簡(jiǎn)單的線性回歸中，只有響應(yīng)變量包含測(cè)量誤差，預(yù)測(cè)變量不包含測(cè)量誤差。樣條光滑通過擬合不同的樣條曲線來平滑回歸方程，比如擬合B曲線來平滑回歸方程。k近鄰算法思想簡(jiǎn)單，容易實(shí)現(xiàn)，不需要復(fù)雜的參數(shù)估計(jì)，也不需要費(fèi)時(shí)的初期訓(xùn)練。k近鄰的耗時(shí)計(jì)算主要在于求得待分類或者回歸的目標(biāo)的k個(gè)最近鄰居，然后根據(jù)這k個(gè)最近鄰居來決定目標(biāo)的分類或者屬性值，求k個(gè)最近鄰居的方法很多，適合的數(shù)據(jù)結(jié)構(gòu)也很多，比如堆，因此實(shí)現(xiàn)k近鄰算法也比較簡(jiǎn)單。k近鄰算法適合用于對(duì)稀有事件進(jìn)行分類。當(dāng)一個(gè)時(shí)間的發(fā)生概率很小時(shí)，稱該事件為稀有時(shí)間。k近鄰算法特別適用于對(duì)小概率事件進(jìn)行分類。當(dāng)除了待分類的目標(biāo)事件之外其他事件的發(fā)生概率分布比較均勻，此時(shí)待分類目標(biāo)的鄰居的分布也比較均勻，大部分鄰居都使得目標(biāo)向著一個(gè)方向靠攏，不會(huì)出現(xiàn)歧義性分類。當(dāng)對(duì)象具有多個(gè)類別標(biāo)簽時(shí)，k近鄰的表現(xiàn)效果要遠(yuǎn)遠(yuǎn)好于支持向量機(jī)等其他分類算法。k近鄰算法在某些情況下是一種非常優(yōu)雅的無參數(shù)分類或者回歸算法，然而，另一些情況下有其局限性。k近鄰算法最大的一點(diǎn)局限就是當(dāng)樣本非常不平衡時(shí)，大樣本有很大的概率會(huì)支配最終的結(jié)果。比如一個(gè)類的樣本容量非常大，其他類的樣本容量相對(duì)小，當(dāng)輸入一個(gè)新的樣本時(shí)，新樣本的k個(gè)最近鄰居中大容量樣本中得元素占大多數(shù)，大容量樣本最終支配了分類結(jié)果。k近鄰算法的另一個(gè)局限就是算法的計(jì)算量非常大，對(duì)于每一個(gè)待分類的樣本都需要計(jì)算該樣本到所有樣本之間的距離，然后才可以求得該樣本的k個(gè)最近的鄰居，重復(fù)進(jìn)行了很多計(jì)算，時(shí)間復(fù)雜度非常高。3.1.2動(dòng)態(tài)最短路徑查詢算法根據(jù)不同算法依賴的不同前置條件，可以將動(dòng)態(tài)最短路徑查詢算法分為三大類。第一類是分時(shí)段的動(dòng)態(tài)路徑查詢算法；第二類是小間隔時(shí)段動(dòng)態(tài)路徑查詢算法；第三類是將動(dòng)態(tài)路網(wǎng)建模為時(shí)間依賴網(wǎng)絡(luò)，利用求解單點(diǎn)到單點(diǎn)最短路徑的算法如ALT算法來求解。第一類算法考慮車輛的出發(fā)時(shí)刻，針對(duì)車輛不同時(shí)刻的不同位置，重新進(jìn)行路徑查詢，如此迭代循環(huán)動(dòng)態(tài)路徑查詢的過程，直到到達(dá)終點(diǎn)。第一類算法的典型代表是動(dòng)態(tài)分時(shí)段改進(jìn)的Dijkstra算法。第二類算法的基本思想是當(dāng)時(shí)間間隔較小時(shí)，動(dòng)態(tài)的路網(wǎng)可以近似地視為靜態(tài)路網(wǎng)，此時(shí)可以利用靜態(tài)的路徑查詢算法求解該時(shí)段的最短路徑。第三類問題國(guó)外學(xué)者稱為TDSPP問題，即Time-dependent

Shortest

Path

Problem。通過將動(dòng)態(tài)路網(wǎng)建模為時(shí)間以來的網(wǎng)絡(luò)，利用成熟的點(diǎn)到點(diǎn)的最短路徑算法來求解。動(dòng)態(tài)Dijkstra算法動(dòng)態(tài)路網(wǎng)不同于靜態(tài)路網(wǎng)，對(duì)于不同的時(shí)段，每個(gè)路段的行駛時(shí)間是不同的，動(dòng)態(tài)路網(wǎng)中每個(gè)路段的行駛時(shí)間對(duì)到達(dá)該路段入口的時(shí)刻依賴非常嚴(yán)重，一個(gè)顯而易見的實(shí)例是早高峰和空閑時(shí)段通過同一路段的時(shí)間相差頗多，空閑時(shí)段只需要十分鐘，可能早高峰時(shí)通過該路段需要40分鐘甚至更多。因此，動(dòng)態(tài)分時(shí)段改進(jìn)的Dijkstra算法不同于靜態(tài)路段的Dijkstra算法，靜態(tài)路段的Dijkstra算法假設(shè)對(duì)于同一路段，所有的時(shí)段的行駛時(shí)間都相同，因此靜態(tài)路段的Dijkstra算法不受時(shí)段的影響。然而，時(shí)段因素對(duì)動(dòng)態(tài)分時(shí)段的Dijkstra算法有明顯的影響，某一路段的行駛時(shí)間強(qiáng)烈依賴于到達(dá)該路段入口的時(shí)間。動(dòng)態(tài)分時(shí)段改進(jìn)的Dijkstra算法通過引入一個(gè)依賴時(shí)間的函數(shù)cost(i,j,t)來加入時(shí)段因素的影響，函數(shù)cost(i,j,t)表示在時(shí)段t通過由i和j組成的路段所耗費(fèi)的時(shí)間。以不同時(shí)段的不同路段的行駛時(shí)間為基礎(chǔ)，改進(jìn)靜態(tài)路段的Dijkstra算法即可得到動(dòng)態(tài)分時(shí)段改進(jìn)的Dijkstra算法。動(dòng)態(tài)分時(shí)段改進(jìn)的Dijkstra算法的流程如下圖：動(dòng)態(tài)分時(shí)段的Dijkstra算法流程圖中S表示集合變量，具體指包含最優(yōu)路徑的節(jié)點(diǎn)集合；s(v)是表示節(jié)點(diǎn)v是否已找到最短路徑的布爾標(biāo)識(shí)，s(v)=true表示已經(jīng)找到了開始節(jié)點(diǎn)到節(jié)點(diǎn)v的最短路徑，s(v)=false表示還沒有找到開始節(jié)點(diǎn)到節(jié)點(diǎn)v的最短路徑；dist(v)表示起點(diǎn)到節(jié)點(diǎn)v的最優(yōu)路徑所耗費(fèi)的時(shí)間。動(dòng)態(tài)分時(shí)段的Dijkstra算法可以根據(jù)車輛的路段位置進(jìn)行不同時(shí)段的動(dòng)態(tài)路徑查詢，最終找出最短路徑。然而，由于時(shí)段跨度往往比較大，該算法無法應(yīng)對(duì)時(shí)間敏感的突發(fā)事件，比如天氣突變、交通事故等，在這種情況下使用該算法得到的最短路徑不是實(shí)際情況下的最短路徑，因?yàn)榇藭r(shí)它沒有放映突發(fā)事件對(duì)最終路徑的影響，因此該算法在突發(fā)事件頻發(fā)的路段中應(yīng)用價(jià)值有限。小間隔時(shí)段動(dòng)態(tài)路徑查詢算法小間隔時(shí)段的路況信息具有連續(xù)性，此時(shí)可認(rèn)為某一路段的行駛時(shí)間是固定的，因此可以在小間隔時(shí)段內(nèi)調(diào)用靜態(tài)Dijkstra算法來進(jìn)行路徑查詢，當(dāng)下一個(gè)時(shí)段到來時(shí)，該路段的行駛時(shí)間發(fā)生變化，依據(jù)變化之后的數(shù)據(jù)重新利用靜態(tài)Dijkstra算法來進(jìn)行路徑查詢。小間隔時(shí)段動(dòng)態(tài)路徑查詢算法通常將時(shí)段長(zhǎng)度設(shè)置為5分鐘到15分鐘之間，此時(shí)的時(shí)段長(zhǎng)度適中，交通信息反饋比較及時(shí)，最終得到的規(guī)劃路徑也比較準(zhǔn)確。小間隔時(shí)段動(dòng)態(tài)路徑查詢算法有效利用了實(shí)時(shí)的交通信息，可以有效應(yīng)對(duì)突發(fā)天氣、交通事故等因素，因此在突發(fā)事故比較多的路段實(shí)用價(jià)值比較高。然而，小間隔時(shí)段動(dòng)態(tài)路徑查詢算法利用實(shí)時(shí)數(shù)據(jù)，由于實(shí)時(shí)數(shù)據(jù)存在延時(shí)、衰減等破壞數(shù)據(jù)完整新的缺點(diǎn)，小間隔時(shí)段動(dòng)態(tài)路徑查詢算法也存在其局限性。其一為實(shí)時(shí)采集的數(shù)據(jù)的延時(shí)導(dǎo)致最新的交通信息并沒有反映在當(dāng)前路徑查詢算法找到的路徑中，此時(shí)地路徑具有時(shí)滯性，對(duì)于實(shí)時(shí)性要求比較高的用戶來說，具有時(shí)滯性的路徑的實(shí)用價(jià)值不大。其二為小間隔時(shí)段動(dòng)態(tài)路徑查詢算法只依賴于當(dāng)前數(shù)據(jù)進(jìn)行路徑查詢，不考慮未來若干時(shí)間段之內(nèi)的交通信息，容易導(dǎo)致最終規(guī)劃出得路徑偏離最優(yōu)路徑。比如根據(jù)當(dāng)前信息，1小時(shí)之后到達(dá)的路段的路況良好，然而當(dāng)車輛在1小時(shí)之后行駛至該路段時(shí)，可能由于上下班高峰等因素此路段已經(jīng)非常擁堵，此時(shí)規(guī)劃出得路徑不符合用戶的預(yù)期。其三為在交通比較繁忙的時(shí)段，路況信息的波動(dòng)比較大，每個(gè)小時(shí)段規(guī)劃出得路徑都不同。用戶期望獲得是變動(dòng)較小的最優(yōu)路徑，頻繁變動(dòng)的規(guī)劃路徑可能會(huì)給用戶帶來困擾，最終耗盡他們的耐心。TDSPP問題動(dòng)態(tài)路徑查詢算法的第三種類型是時(shí)間依賴網(wǎng)絡(luò)中的最短路徑問題，該模型最早由Cooke,Halsey在1966年提出。在時(shí)間依賴的網(wǎng)絡(luò)模型中，網(wǎng)絡(luò)中依賴時(shí)間而變化的一些特性是可以預(yù)期的。時(shí)間依賴網(wǎng)絡(luò)模型最初被用來解決根據(jù)當(dāng)前路網(wǎng)數(shù)據(jù)規(guī)劃的最短路徑?jīng)]有考慮可預(yù)期的路況數(shù)據(jù)變化問題，比如高峰時(shí)段等。在時(shí)間依賴網(wǎng)絡(luò)最短路徑查詢模型中，通過某一路段的時(shí)間是從該路段出發(fā)的時(shí)段的函數(shù)，并且所有這些函數(shù)都是已知的。時(shí)間依賴最短路徑查詢的具體流程是：在當(dāng)前時(shí)刻，對(duì)路網(wǎng)中所有路段進(jìn)行多步預(yù)測(cè)，確定之后每個(gè)路段的具體行程時(shí)間，將路網(wǎng)建模為基于預(yù)測(cè)行程時(shí)間的時(shí)間依賴網(wǎng)絡(luò)。普適的時(shí)間依賴最短路徑是NP難的，不存在多項(xiàng)式時(shí)間復(fù)雜度之內(nèi)的求解算法，因此實(shí)際應(yīng)用中價(jià)值有限。然而，通過重新限制其前置條件，可以保證在多項(xiàng)式時(shí)間之內(nèi)求解該問題，而前置條件也符合實(shí)際情況。比如通過限制通過順序?qū)r(shí)間依賴網(wǎng)絡(luò)建模為FIFO網(wǎng)絡(luò)，即先進(jìn)先出網(wǎng)絡(luò)，F(xiàn)IFO符合現(xiàn)實(shí)路網(wǎng)的通過順序。在FIFO網(wǎng)絡(luò)中，時(shí)間依賴最短路徑呈現(xiàn)出很多有用的性質(zhì)，利用這些性質(zhì)可以設(shè)計(jì)多項(xiàng)式時(shí)間復(fù)雜度的求解算法。BrianC.Deany研究了FIFO時(shí)間依賴網(wǎng)絡(luò)的性質(zhì)并率先提出了多項(xiàng)式時(shí)間復(fù)雜度的求解算法。將實(shí)際路網(wǎng)建模為時(shí)間依賴網(wǎng)絡(luò)，之后進(jìn)行最短路徑查詢，這是求解動(dòng)態(tài)路徑查詢問題的有效方法，也是實(shí)際路徑導(dǎo)航系統(tǒng)普遍使用的方法。該方法充分整合了第一類動(dòng)態(tài)路徑查詢算法和第二類動(dòng)態(tài)路徑查詢算法，有效利用歷史數(shù)據(jù)和實(shí)時(shí)數(shù)據(jù)，通過對(duì)未來若干時(shí)段進(jìn)行預(yù)測(cè)，可以應(yīng)對(duì)道路占有率突然升高等突發(fā)狀況。不同于小間隔時(shí)段動(dòng)態(tài)路徑查詢算法，時(shí)間依賴最短路徑算法預(yù)測(cè)得到的未來若干時(shí)段的路況信息波動(dòng)不大，最終規(guī)劃得到的最短路徑也不會(huì)頻繁變動(dòng)，不會(huì)給用戶造成困擾。然而，基于多步預(yù)測(cè)的時(shí)間依賴最短路徑算法存在如下局限：其一，也是最重要的一點(diǎn)是當(dāng)預(yù)測(cè)的跨度很大時(shí)，預(yù)測(cè)的精度下降很快，依據(jù)預(yù)測(cè)的路況數(shù)據(jù)規(guī)劃的最短路徑也越偏離實(shí)際最短路徑；其二為多步預(yù)測(cè)的最佳預(yù)測(cè)步長(zhǎng)比較模糊，不存在一致的最佳步長(zhǎng)，每個(gè)實(shí)際路網(wǎng)的最佳步長(zhǎng)也能都不同，這給選擇步長(zhǎng)帶來了挑戰(zhàn)。選擇合理的步長(zhǎng)，必須通過實(shí)際路網(wǎng)中的不斷迭代嘗試，而大型路網(wǎng)的迭代嘗試是非常耗時(shí)的。其三是歷史數(shù)據(jù)的選取標(biāo)準(zhǔn)不明確。同當(dāng)前時(shí)刻較近的歷史數(shù)據(jù)對(duì)未來時(shí)段交通情況的關(guān)聯(lián)性較大，同當(dāng)前時(shí)刻較遠(yuǎn)的歷史數(shù)據(jù)對(duì)未來時(shí)段交通情況的關(guān)聯(lián)性較小，考慮所有歷史數(shù)據(jù)涉及的數(shù)據(jù)量太大，無法在可以接受的時(shí)間內(nèi)規(guī)劃出合理的路徑?？紤]最近的歷史數(shù)據(jù)可能會(huì)造成最終路徑被若干數(shù)據(jù)支配，影響最終規(guī)劃路徑的準(zhǔn)確性。3.1.3其他相關(guān)工作3.2算法設(shè)計(jì)3.2.1基于改進(jìn)k近鄰的短時(shí)交通預(yù)測(cè)算法基于改進(jìn)k近鄰的短時(shí)交通預(yù)測(cè)算法是非參數(shù)回歸預(yù)測(cè)算法的一種，通過選擇同當(dāng)前觀測(cè)的狀態(tài)向量最相似的k個(gè)鄰居狀態(tài)向量來預(yù)測(cè)未來的路段行駛速度和通過時(shí)間。傳統(tǒng)的基于k近鄰的短時(shí)交通預(yù)測(cè)根據(jù)當(dāng)前的實(shí)時(shí)速度和歷史速度進(jìn)行比較，從相似度較高的歷史數(shù)據(jù)中的下一時(shí)刻的數(shù)據(jù)預(yù)測(cè)當(dāng)前時(shí)間下一時(shí)刻的交通情況。而我們考慮到在不能獲知實(shí)時(shí)速度而歷史數(shù)據(jù)豐富時(shí)的，考慮到交通的規(guī)律性，我們從出行時(shí)的日期，時(shí)刻，星期，天氣角度，對(duì)任意時(shí)刻的交通情況進(jìn)行預(yù)測(cè)。算法框架具體而言，基于改進(jìn)k近鄰的短時(shí)交通預(yù)測(cè)算法包含5個(gè)組成部分：（1）構(gòu)建歷史數(shù)據(jù)庫(kù)。 （2）確定狀態(tài)向量。 （3）確定預(yù)測(cè)函數(shù)。 （4）從歷史數(shù)據(jù)庫(kù)搜索當(dāng)前狀態(tài)向量的k個(gè)最近鄰居。（5）根據(jù)k個(gè)最近鄰居，利用預(yù)測(cè)函數(shù)預(yù)測(cè)行駛速度和通過時(shí)間?；诟倪M(jìn)k近鄰的短時(shí)交通預(yù)測(cè)算法的具體流程如下圖： 采用改進(jìn)k近鄰的短時(shí)交通預(yù)測(cè)算法進(jìn)行交通預(yù)測(cè)的基礎(chǔ)是數(shù)據(jù)屬性豐富且有大量真實(shí)有效的歷史數(shù)據(jù)。歷史數(shù)據(jù)應(yīng)該包含影響交通情況的各個(gè)屬性如天氣、日期、時(shí)刻等等的因素從而實(shí)時(shí)數(shù)據(jù)可以根據(jù)當(dāng)前的情況找到和歷史數(shù)據(jù)相似度最高的數(shù)據(jù)。大量真實(shí)有效的數(shù)據(jù)是當(dāng)前數(shù)據(jù)在歷史數(shù)據(jù)中有相似項(xiàng)的保證。然而，一方面龐大的歷史數(shù)據(jù)需要合理的設(shè)計(jì)歷史數(shù)據(jù)庫(kù)，從而減少數(shù)據(jù)冗余、提高查詢速度。另一方面歷史數(shù)據(jù)中存在著測(cè)量誤差、記錄丟失和干擾數(shù)據(jù)等等情況，在歷史數(shù)據(jù)庫(kù)形成前我們需要對(duì)原始數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，降低誤差，提高預(yù)測(cè)準(zhǔn)確度。狀態(tài)向量定義狀態(tài)向量確定了當(dāng)前數(shù)據(jù)特征從而可以在歷史數(shù)據(jù)庫(kù)找到相似數(shù)據(jù)。在沒有實(shí)時(shí)交通流速情況下，我們可以根據(jù)交通情況的規(guī)律性和復(fù)雜性，通過對(duì)狀態(tài)向量選擇可以將人們主觀的結(jié)論和歷史數(shù)據(jù)結(jié)合起來，對(duì)短時(shí)交通進(jìn)行預(yù)測(cè)。根據(jù)[/traffic/]可知，城市交通擁堵問題嚴(yán)重且規(guī)律性明顯，同時(shí)影響不同城市的特征差異很大，如北京的交通受到會(huì)議活動(dòng)影響較大。哈爾濱的城市交通季節(jié)特征明顯。上海由于氣候平穩(wěn)、無特殊道路交通事件，所以沒有和北京哈爾濱相似的特征。但是上海地區(qū)晴雨天交通差別明顯，高峰時(shí)段交通擁堵情況顯著，節(jié)假日部分交通路段與平時(shí)差距較大。在此，我們選擇上海作為研究城市，根據(jù)上海的交通規(guī)律制定相應(yīng)的狀態(tài)向量。因此選取日期，時(shí)間，星期，天氣組成狀態(tài)向量。即其中，表示路徑查詢當(dāng)天的日期。表示歷史數(shù)據(jù)對(duì)應(yīng)的日期。表示當(dāng)前時(shí)間。表示當(dāng)前的星期，如星期一，星期六。表示路徑查詢當(dāng)天的天氣，如晴，雨。分別表示歷史數(shù)據(jù)對(duì)應(yīng)的時(shí)間、星期和天氣。距離度量準(zhǔn)則 距離度量準(zhǔn)則用來衡量當(dāng)前采集數(shù)據(jù)同歷史數(shù)據(jù)庫(kù)中得數(shù)據(jù)的匹配程度，通過距離函數(shù)來實(shí)現(xiàn)。對(duì)于給定的域，上的距離函數(shù)為映射對(duì)于域中的所有，距離函數(shù)需要滿足如下條件：（1）非負(fù)性，即。（2）當(dāng)且僅當(dāng)。（3）對(duì)稱性，即。（4）三角不等式。 常用的距離函數(shù)有曼哈頓距離和歐拉距離，這兩種距離函數(shù)在我們?cè)O(shè)計(jì)的狀態(tài)向量下不能直接使用。我們使用 預(yù)測(cè)算法經(jīng)過上述的近鄰匹配機(jī)制，假設(shè)在歷史數(shù)據(jù)庫(kù)中找到K個(gè)近鄰，實(shí)際數(shù)據(jù)和這K個(gè)近鄰的距離為，這些近鄰所對(duì)應(yīng)的時(shí)刻的流量為。預(yù)測(cè)算法包括等權(quán)重和帶權(quán)重的預(yù)測(cè)算法。其中等權(quán)重的預(yù)測(cè)算法為： 這里并沒有考慮當(dāng)前觀測(cè)值和歷史數(shù)據(jù)庫(kù)中不同近鄰距離的不同，僅僅將各個(gè)近鄰對(duì)于的流量取簡(jiǎn)單算數(shù)平均作為當(dāng)前時(shí)刻的預(yù)測(cè)值。帶權(quán)重的預(yù)算算法為：帶權(quán)重的預(yù)測(cè)算法認(rèn)為與當(dāng)前觀測(cè)的實(shí)時(shí)數(shù)據(jù)距離較小的歷史數(shù)據(jù)庫(kù)中的數(shù)據(jù)系列相似度較大，從而在預(yù)測(cè)算法中，這些距離近的近鄰對(duì)預(yù)測(cè)值的權(quán)重較大。所以，通過對(duì)距離取倒數(shù)來確定權(quán)值。本文采用帶權(quán)重的預(yù)測(cè)算法進(jìn)行預(yù)測(cè)。3.2.2基于A*的動(dòng)態(tài)路徑查詢算法A*算法A*算法是一種在在圖中的節(jié)點(diǎn)之間尋找最短路徑的高效算法。在靜態(tài)網(wǎng)絡(luò)中，A*算法的性能很高，如果可以保證啟發(fā)式估價(jià)函數(shù)對(duì)每個(gè)節(jié)點(diǎn)的估值不高于其實(shí)際值，A*算法確定可以找到一條最短路徑。A*算法最早由PeterHart,NilsNilsson和BertramRaphael于1968年提出，最初是作為EdsgerDijkstra于1959年提出的Dijkstra算法的一種推廣，通過啟發(fā)式搜索來提高算法效率。由于A*算法的高效率和精度，A*算法被廣泛應(yīng)用于游戲路徑查詢中，如在線游戲的BOT移動(dòng)計(jì)算