隨著道路網絡與移動通訊的迅猛發(fā)展,基于位置的服務在人們生活中發(fā)揮著重要作用。而路徑規(guī)劃一直是基于位置的服務與在線地圖服務應用中基礎而且重要的問題,為人們出行提供了重要參考。隨著城鎮(zhèn)化水平不斷提高,道路網絡規(guī)模不斷增長,面對處理大型復雜道路網絡和時間依賴道路網絡的挑戰(zhàn)時,傳統(tǒng)的路徑查詢算法因其局限性而不能滿足大數據時代的需求。因此,需要設計高效算法來解決路網中的路徑查詢問題。本文在兩種道路網絡情況下對支配路徑查詢進行研究:基于靜態(tài)路網的支配路徑查詢問題研究和基于時間依賴路網的多約束支配路徑查詢研究。同時隨著用戶個性化需求的增加,用戶不再滿足于現有在線地圖路徑規(guī)劃的單一維度路徑查詢,因而本文研究的問題同時考慮路徑花費與結點分數兩個維度,尋找不受其他路徑支配的支配路徑集合。首先,本文研究靜態(tài)路網中的多偏好順序路徑Skyline查詢。分析現有的構造權重Voronoi圖的算法在預處理和查詢過程存在的局限性。為了提高查詢效率,提出基于過程支配的精確算法,定義未完成路徑間的支配關系,對查詢進行路徑花費的花費上界預算,并提出增加剪枝策略。通過以終點為導向的消耗估計策略,進一步減小搜索空間。同時在保證算... 

【文章來源】：沈陽建筑大學遼寧省

【文章頁數】：65 頁

【學位級別】：碩士

【部分圖文】：

圖２．２?９個結點的標準Ｖｏｒｏｎｏｉ圖??Ｆｉｇ．?２．２?Ｔｈｅ?ｓｔａｎｄａｒｄ?Ｖｏｒｏｎｏｉ?ｄｉａｇｒａｍ?ｏｆ?９?ｖｅｔｅｃｓ??１１??

式化定義ＭＰＳＲＳ問題；然后介紹問題相關定義并介紹現有算法并給出解決該問題的算??法：最后通過在真實路網上進行實驗，證明所提算法有效性和高效性。??３．１問題描述??多偏好順序路徑?Ｓｋｙｌｉｎｅ?查詢（Ｍｕｌｔｉ－Ｐｒｅｆｅｒｅｎｃｅ?Ｓｅｑｕｅｎｃｅ?Ｒｏｕｔｅ?Ｓｋｙｌｉｎｅ?ｑｕｅｒｙ），簡??稱為ＭＰＳＲＳ查詢問題［｜２】。給定二維道路網絡圖Ｇ，起始結點ｓ和終止結點用戶的??偏好設罝尸，一組順序關鍵字序列義。ＭＰＳＲＳ查詢尋找一組從起始結點ｓ出發(fā)，途經指??定順序關鍵字的類別中一個興趣點，在終止結點ｄ結束的Ｓｋｙｌｉｎｅ路徑集合＼，使得任??意路徑的路程花費ｖｖ（Ａ）和路徑的用戶指定偏好總花費〇〇／？）兩個維度不受任??何其他可行路徑兒支配，？?ｇｐ：對于任意／？＇，。??

ａ＞？＞６??時，可得ＰＫ，，?匕，因此，當％＝？時，關鍵字結點ｖ，被選擇。??１８ｋｍ?１４￥?１７ｋｍ?７５５?；?Ｉ８ｋｍ?Ｊ３￥?????▲．?．［１．馨■?．?■０＾２?漏４??????｜．．．．．．．．Ｕｋｎｖｌ７ｉ．．．．．．．．．．｜．．．．．．Ｔ４Ｍ＇＼８￥＼．．．．．??＾?ＨＩ｜?Ｈ???????Ｓ??１６ｋｉｎ?１３￥?１６ｌｄｎ?Ｊ?ＳＳ?＼?Ｔ＾ｎ?１４￥＇?｝??ｒ．?？?ｇ．＾Ａ?ｍ；Ｂ?????圖３．２預處理階段示例圖??Ｆｉｇ．?３．２?Ｐｒｅｐｒｏｃｅｓｓｉｎｇ?ｓｔａｇｅ?ｅｘａｍｐｌｅ??基于上述引理，本文不再需要多次迭代選擇關鍵字結點，例如迭代１００次。相反，??本文只需要比較消耗函數％兩個極端值，當％＝?１和％＝?０時的優(yōu)先級分數／和。??如果％?＝?１和％＝?０時均選擇了?Ｖ，結點則無需再進行其他迭代，例如：如圖３．２所示，??當％＝?１時餐館類別選擇的是＆結點（１３＜１５），當％＞＝０時餐館類別選擇的仍是／＊２結??點（１６＜１７），因此本文不需要洱在丨０，?１］再進行迭代來尋找一個優(yōu)先級分數更低的結點??了。選擇了?Ｘ鍵字結點即組成了證據路徑。??（２）查詢處理階段??預處理階段是選擇山關鍵字結點，形成了證據路徑，但是具有相同證據路徑的路徑??集合也會具冇不同的路程消耗。為了提高遍歷效率，快速形成路Ｎ中真實路徑從而得到??查詢處理階段需要查詢Ｓｋｙｌｉｎｅ路徑集合，木文提出快速選擇組成路徑的路Ｎ中其它結??點的距離估箅方法：從△？到△／的Ｍ近一次旅行中添加關鍵字結點的最近鄰結點。對于真??實的靜態(tài)路Ｈ，在每次迭代

【參考文獻】：
期刊論文
[1]面向時間依賴路網的空間索引方法[J]. 李佳佳,臧寅旭,劉向宇,夏秀峰,朱睿.  計算機工程. 2019(05)
[2]基于A*算法的最短路徑尋優(yōu)數學方法研究[J]. 張婷娟.  科技通報. 2015(06)
[3]基于分層的改進A算法在路徑規(guī)劃中的應用[J]. 錢紅昇,葛文鋒,鐘鳴,葛銘.  計算機工程與應用. 2014(07)

博士論文
[1]大規(guī)模圖上的最短路徑問題研究[D]. 張鐘.中國科學技術大學 2014



本文編號：3268641