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

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

【摘要】：隨著航空業(yè)的迅速發(fā)展,形成了龐大的航線網(wǎng)絡(luò),為人們出行帶來了很大的便利。人們在選擇出行路徑時,總是希望根據(jù)自己的需求選擇出行方案。因此根據(jù)旅客的偏好和交通工具的運行時刻表為旅客推薦可能滿足其出行需求的路徑是一個復(fù)雜而又迫切解決的問題。航班網(wǎng)絡(luò)與其他公共交通一樣,其顯著的特征是其運行受到時刻表的約束。因此,本文研究基于時刻表最優(yōu)路徑推薦問題的算法,主要包括以下三方面內(nèi)容:第一,結(jié)合航班和鐵路時刻表的特點,構(gòu)建了基于航班時刻表的時間擴展網(wǎng)絡(luò)(time-expanded)模型。第二,采用深度優(yōu)先策略對基于航班時刻表的時間擴展網(wǎng)絡(luò)進行搜索以得到最優(yōu)的前K條路徑供旅客選擇。并結(jié)合航線網(wǎng)絡(luò)空間跨度大的特點,提出了一種動態(tài)限制搜索區(qū)域的深度優(yōu)先(DFS)搜索算法(PRDFS_D)以提高路徑搜索效率。理論上,搜索區(qū)域松弛因子?、換乘時間μ及換乘次數(shù)λ將直接影響路徑的搜索效率。通過實驗分析了這些因素對推薦出行路徑的正確性影響程度,驗證了該算法從全程用時最短角度能夠很好地滿足旅客出行路徑推薦的需要。第三,針對單目標PRDFS_D算法無法滿足旅客多目標路徑選擇的需求,提出了考慮最早到達和路徑可靠性雙目標的聯(lián)程路徑搜索算法。依據(jù)航班和列車時刻表,運用可靠度理論建立換乘節(jié)點的換乘時間可靠度模型,并將該模型和PRDFS_D算法相結(jié)合。首先由PRDFS_D算法求出滿足條件的路徑集,繼而利用構(gòu)造的輔助函數(shù)在路徑集內(nèi)多次迭代逐漸求出最早到達、次早到達等前K條最早到達路徑。通過實驗驗證了輔助函數(shù)、雙目標函數(shù)與調(diào)節(jié)因子α的關(guān)系。同時驗證了求解K條最早到達路徑時所需迭代次數(shù)與閥值L的關(guān)系,這一關(guān)系與理論分析結(jié)論相吻合。
【關(guān)鍵詞】：時刻表 路徑推薦算法 深度優(yōu)先搜索 雙目標聯(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)外動態(tài)分析12-15
• 1.3 本文主要工作及章節(jié)安排15-17
• 第二章 基于時刻表路徑搜索算法相關(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 標號算法20
• 2.3.2 刪除路徑算法20-21
• 2.4 KMCSP相關(guān)算法21-22
• 2.4.1 多約束剪枝算法21
• 2.4.2 改進MPS算法21-22
• 2.5 基于時刻表的路徑搜索模型及相關(guān)算法22-25
• 2.5.1 時間擴展模型22-23
• 2.5.2 時間依賴模型23-24
• 2.5.3 基于時刻表的相關(guān)算法24-25
• 2.6 本章小結(jié)25-26
• 第三章 基于經(jīng)緯度限制搜索區(qū)域的路徑搜索算法26-38
• 3.1 動態(tài)限制搜索區(qū)域26-27
• 3.2 基于運行時刻表的時間擴展模型的構(gòu)建27-30
• 3.3 基于經(jīng)緯度動態(tài)限制搜索區(qū)域的搜索策略30-37
• 3.3.1 基于有界DFS搜索策略30-31
• 3.3.2 基于經(jīng)緯度動態(tài)限制搜索區(qū)域31-32
• 3.3.3 算法的描述與實現(xiàn)32-34
• 3.3.4 算法時間復(fù)雜度分析34
• 3.3.5 實驗結(jié)果與分析34-37
• 3.4 本章小結(jié)37-38
• 第四章 基于雙目標路徑誘導(dǎo)下的聯(lián)程路徑搜索算法38-51
• 4.1 路徑搜索算法中多目標問題簡介38-39
• 4.2 雙目標下的路徑搜索算法39-41
• 4.2.1 換乘時間可靠模型的建立39
• 4.2.2 現(xiàn)有換乘可靠度模型39-40
• 4.2.3 基于時刻表的換乘時間可靠度模型40-41
• 4.3 考慮可靠性與最早到達問題的雙目標優(yōu)化模型的建立41-50
• 4.3.1 雙目標優(yōu)化模型的建立42
• 4.3.2 輔助函數(shù)的構(gòu)造及其性質(zhì)42-44
• 4.3.3 算法的描述與實現(xiàn)44
• 4.3.4 算法時間復(fù)雜度分析44-45
• 4.3.5 實驗結(jié)果與分析45-50
• 4.4 本章小結(jié)50-51
• 第五章 結(jié)束語51-53
• 5.1 工作總結(jié)51-52
• 5.2 展望52-53
• 參考文獻53-57
• 致謝57-58
• 發(fā)表論文與參與科研項目情況58

【參考文獻】

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

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

，

本文編號：806517