本文關(guān)鍵詞：基于時(shí)刻表的旅客出行路徑推薦算法研究

  更多相關(guān)文章： 時(shí)刻表 路徑推薦算法 深度優(yōu)先搜索 雙目標(biāo)聯(lián)程路徑

【摘要】：隨著航空業(yè)的迅速發(fā)展,形成了龐大的航線網(wǎng)絡(luò),為人們出行帶來了很大的便利。人們在選擇出行路徑時(shí),總是希望根據(jù)自己的需求選擇出行方案。因此根據(jù)旅客的偏好和交通工具的運(yùn)行時(shí)刻表為旅客推薦可能滿足其出行需求的路徑是一個(gè)復(fù)雜而又迫切解決的問題。航班網(wǎng)絡(luò)與其他公共交通一樣,其顯著的特征是其運(yùn)行受到時(shí)刻表的約束。因此,本文研究基于時(shí)刻表最優(yōu)路徑推薦問題的算法,主要包括以下三方面內(nèi)容:第一,結(jié)合航班和鐵路時(shí)刻表的特點(diǎn),構(gòu)建了基于航班時(shí)刻表的時(shí)間擴(kuò)展網(wǎng)絡(luò)(time-expanded)模型。第二,采用深度優(yōu)先策略對基于航班時(shí)刻表的時(shí)間擴(kuò)展網(wǎng)絡(luò)進(jìn)行搜索以得到最優(yōu)的前K條路徑供旅客選擇。并結(jié)合航線網(wǎng)絡(luò)空間跨度大的特點(diǎn),提出了一種動(dòng)態(tài)限制搜索區(qū)域的深度優(yōu)先(DFS)搜索算法(PRDFS_D)以提高路徑搜索效率。理論上,搜索區(qū)域松弛因子?、換乘時(shí)間μ及換乘次數(shù)λ將直接影響路徑的搜索效率。通過實(shí)驗(yàn)分析了這些因素對推薦出行路徑的正確性影響程度,驗(yàn)證了該算法從全程用時(shí)最短角度能夠很好地滿足旅客出行路徑推薦的需要。第三,針對單目標(biāo)PRDFS_D算法無法滿足旅客多目標(biāo)路徑選擇的需求,提出了考慮最早到達(dá)和路徑可靠性雙目標(biāo)的聯(lián)程路徑搜索算法。依據(jù)航班和列車時(shí)刻表,運(yùn)用可靠度理論建立換乘節(jié)點(diǎn)的換乘時(shí)間可靠度模型,并將該模型和PRDFS_D算法相結(jié)合。首先由PRDFS_D算法求出滿足條件的路徑集,繼而利用構(gòu)造的輔助函數(shù)在路徑集內(nèi)多次迭代逐漸求出最早到達(dá)、次早到達(dá)等前K條最早到達(dá)路徑。通過實(shí)驗(yàn)驗(yàn)證了輔助函數(shù)、雙目標(biāo)函數(shù)與調(diào)節(jié)因子α的關(guān)系。同時(shí)驗(yàn)證了求解K條最早到達(dá)路徑時(shí)所需迭代次數(shù)與閥值L的關(guān)系,這一關(guān)系與理論分析結(jié)論相吻合。
【關(guān)鍵詞】：時(shí)刻表 路徑推薦算法 深度優(yōu)先搜索 雙目標(biāo)聯(lián)程路徑
【學(xué)位授予單位】：中國民航大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O224
【目錄】：

• 摘要5-6
• Abstract6-10
• 第一章 緒論10-17
• 1.1 研究背景與意義10-12
• 1.1.1 課題研究背景10-11
• 1.1.2 課題研究意義11-12
• 1.2 國內(nèi)外動(dòng)態(tài)分析12-15
• 1.3 本文主要工作及章節(jié)安排15-17
• 第二章 基于時(shí)刻表路徑搜索算法相關(guān)基礎(chǔ)17-26
• 2.1 圖的相關(guān)概念17-18
• 2.2 相關(guān)最短路徑算法18-20
• 2.2.1 Dijkstra算法18
• 2.2.2 Bellman-Ford算法18-19
• 2.2.3 A~*算法19
• 2.2.4 智能算法19-20
• 2.3 KSP、KCSP相關(guān)算法20-21
• 2.3.1 標(biāo)號算法20
• 2.3.2 刪除路徑算法20-21
• 2.4 KMCSP相關(guān)算法21-22
• 2.4.1 多約束剪枝算法21
• 2.4.2 改進(jìn)MPS算法21-22
• 2.5 基于時(shí)刻表的路徑搜索模型及相關(guān)算法22-25
• 2.5.1 時(shí)間擴(kuò)展模型22-23
• 2.5.2 時(shí)間依賴模型23-24
• 2.5.3 基于時(shí)刻表的相關(guān)算法24-25
• 2.6 本章小結(jié)25-26
• 第三章 基于經(jīng)緯度限制搜索區(qū)域的路徑搜索算法26-38
• 3.1 動(dòng)態(tài)限制搜索區(qū)域26-27
• 3.2 基于運(yùn)行時(shí)刻表的時(shí)間擴(kuò)展模型的構(gòu)建27-30
• 3.3 基于經(jīng)緯度動(dòng)態(tài)限制搜索區(qū)域的搜索策略30-37
• 3.3.1 基于有界DFS搜索策略30-31
• 3.3.2 基于經(jīng)緯度動(dòng)態(tài)限制搜索區(qū)域31-32
• 3.3.3 算法的描述與實(shí)現(xiàn)32-34
• 3.3.4 算法時(shí)間復(fù)雜度分析34
• 3.3.5 實(shí)驗(yàn)結(jié)果與分析34-37
• 3.4 本章小結(jié)37-38
• 第四章 基于雙目標(biāo)路徑誘導(dǎo)下的聯(lián)程路徑搜索算法38-51
• 4.1 路徑搜索算法中多目標(biāo)問題簡介38-39
• 4.2 雙目標(biāo)下的路徑搜索算法39-41
• 4.2.1 換乘時(shí)間可靠模型的建立39
• 4.2.2 現(xiàn)有換乘可靠度模型39-40
• 4.2.3 基于時(shí)刻表的換乘時(shí)間可靠度模型40-41
• 4.3 考慮可靠性與最早到達(dá)問題的雙目標(biāo)優(yōu)化模型的建立41-50
• 4.3.1 雙目標(biāo)優(yōu)化模型的建立42
• 4.3.2 輔助函數(shù)的構(gòu)造及其性質(zhì)42-44
• 4.3.3 算法的描述與實(shí)現(xiàn)44
• 4.3.4 算法時(shí)間復(fù)雜度分析44-45
• 4.3.5 實(shí)驗(yàn)結(jié)果與分析45-50
• 4.4 本章小結(jié)50-51
• 第五章 結(jié)束語51-53
• 5.1 工作總結(jié)51-52
• 5.2 展望52-53
• 參考文獻(xiàn)53-57
• 致謝57-58
• 發(fā)表論文與參與科研項(xiàng)目情況58

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前1條

1 ;Minimizing Maximum Risk for Fair Network Connection with Interval Data[J];Acta Mathematicae Applicatae Sinica(English Series);2010年01期

，

本文編號：806517