基于时刻表的旅客出行路径推荐算法研究

发布时间：2017-09-07 01:08

  本文关键词：基于时刻表的旅客出行路径推荐算法研究

  更多相关文章： 时刻表 路径推荐算法 深度优先搜索 双目标联程路径

【摘要】：随着航空业的迅速发展,形成了庞大的航线网络,为人们出行带来了很大的便利。人们在选择出行路径时,总是希望根据自己的需求选择出行方案。因此根据旅客的偏好和交通工具的运行时刻表为旅客推荐可能满足其出行需求的路径是一个复杂而又迫切解决的问题。航班网络与其他公共交通一样,其显著的特征是其运行受到时刻表的约束。因此,本文研究基于时刻表最优路径推荐问题的算法,主要包括以下三方面内容:第一,结合航班和铁路时刻表的特点,构建了基于航班时刻表的时间扩展网络(time-expanded)模型。第二,采用深度优先策略对基于航班时刻表的时间扩展网络进行搜索以得到最优的前K条路径供旅客选择。并结合航线网络空间跨度大的特点,提出了一种动态限制搜索区域的深度优先(DFS)搜索算法(PRDFS_D)以提高路径搜索效率。理论上,搜索区域松弛因子?、换乘时间μ及换乘次数λ将直接影响路径的搜索效率。通过实验分析了这些因素对推荐出行路径的正确性影响程度,验证了该算法从全程用时最短角度能够很好地满足旅客出行路径推荐的需要。第三,针对单目标PRDFS_D算法无法满足旅客多目标路径选择的需求,提出了考虑最早到达和路径可靠性双目标的联程路径搜索算法。依据航班和列车时刻表,运用可靠度理论建立换乘节点的换乘时间可靠度模型,并将该模型和PRDFS_D算法相结合。首先由PRDFS_D算法求出满足条件的路径集,继而利用构造的辅助函数在路径集内多次迭代逐渐求出最早到达、次早到达等前K条最早到达路径。通过实验验证了辅助函数、双目标函数与调节因子α的关系。同时验证了求解K条最早到达路径时所需迭代次数与阀值L的关系,这一关系与理论分析结论相吻合。
【关键词】：时刻表 路径推荐算法 深度优先搜索 双目标联程路径
【学位授予单位】：中国民航大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O224
【目录】：

• 摘要5-6
• Abstract6-10
• 第一章 绪论10-17
• 1.1 研究背景与意义10-12
• 1.1.1 课题研究背景10-11
• 1.1.2 课题研究意义11-12
• 1.2 国内外动态分析12-15
• 1.3 本文主要工作及章节安排15-17
• 第二章 基于时刻表路径搜索算法相关基础17-26
• 2.1 图的相关概念17-18
• 2.2 相关最短路径算法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相关算法20-21
• 2.3.1 标号算法20
• 2.3.2 删除路径算法20-21
• 2.4 KMCSP相关算法21-22
• 2.4.1 多约束剪枝算法21
• 2.4.2 改进MPS算法21-22
• 2.5 基于时刻表的路径搜索模型及相关算法22-25
• 2.5.1 时间扩展模型22-23
• 2.5.2 时间依赖模型23-24
• 2.5.3 基于时刻表的相关算法24-25
• 2.6 本章小结25-26
• 第三章 基于经纬度限制搜索区域的路径搜索算法26-38
• 3.1 动态限制搜索区域26-27
• 3.2 基于运行时刻表的时间扩展模型的构建27-30
• 3.3 基于经纬度动态限制搜索区域的搜索策略30-37
• 3.3.1 基于有界DFS搜索策略30-31
• 3.3.2 基于经纬度动态限制搜索区域31-32
• 3.3.3 算法的描述与实现32-34
• 3.3.4 算法时间复杂度分析34
• 3.3.5 实验结果与分析34-37
• 3.4 本章小结37-38
• 第四章 基于双目标路径诱导下的联程路径搜索算法38-51
• 4.1 路径搜索算法中多目标问题简介38-39
• 4.2 双目标下的路径搜索算法39-41
• 4.2.1 换乘时间可靠模型的建立39
• 4.2.2 现有换乘可靠度模型39-40
• 4.2.3 基于时刻表的换乘时间可靠度模型40-41
• 4.3 考虑可靠性与最早到达问题的双目标优化模型的建立41-50
• 4.3.1 双目标优化模型的建立42
• 4.3.2 辅助函数的构造及其性质42-44
• 4.3.3 算法的描述与实现44
• 4.3.4 算法时间复杂度分析44-45
• 4.3.5 实验结果与分析45-50
• 4.4 本章小结50-51
• 第五章 结束语51-53
• 5.1 工作总结51-52
• 5.2 展望52-53
• 参考文献53-57
• 致谢57-58
• 发表论文与参与科研项目情况58

【参考文献】

中国期刊全文数据库 前1条

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

，

本文编号：806517