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

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

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

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

Shortest

Path

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