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

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

【文章頁數(shù)】：65 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖２．２?９個結(jié)點(diǎn)的標(biāo)準(zhǔn)Ｖｏｒｏｎｏｉ圖??Ｆｉｇ．?２．２?Ｔｈｅ?ｓｔａｎｄａｒｄ?Ｖｏｒｏｎｏｉ?ｄｉａｇｒａｍ?ｏｆ?９?ｖｅｔｅｃｓ??１１??

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

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

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

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



本文編號：3268641