公共交通系统中的前K短路径算法的研究

【摘要】随着经济的快速发展，人们因为商务、旅游、探亲等因素产生的出行需求越来越大，交通运输问题变得日益严重。而铁路、公路、民航、水运等作为重要的交通方式，它们所承受的客流量也是越来越大。但随着交通系统中新的交通线路的不断开辟和扩展，在这种情况下仅凭售票员的记忆为旅客找到到达目的地的最佳线路是不可能的，而让旅客自己在海量的网络信息中查找最佳线路也是不智能的。因此，设计并开发一套快速并精准的公共交通线路查询系统，供出行者根据不同的需要查询所需的出行信息，是我国公共交通事业发展中亟需解决的问题。在本论文中，首先，分析了行人的出行需求，介绍了一个优秀的前K条最短路径算法——deletion算法和两种在公共交通系统中常用来解决前K条最优路径的算法：递归Dijkstra算法和遗传算法，经比较发现，deletion算法的时间消耗要小于递归Dijkstra算法和遗传算法，因此本文主要研究deletion算法在公共交通系统中的应用；其次，回顾了两个在公共交通系统建模时常用的经典模型：时间扩展模型和时间依赖模型，并以我国铁路运输系统为对象，研究和建立了以最早到达为目标的网络模型；最后，为了满足乘客的需求并且给乘客提供多种出行方案，本文在时间扩展模型上运用deletion算法求解了前K条最早到达、前K条最少换乘和前K条最短运行时间路线，此外，本文对deletion算法做了适当修改，并在时间依赖模型上求解了前K条最早到达路线；实验结果表明，修改后的deletion算法比原算法的时间消耗少，特别适合于大规模的公共交通系统中的前K条最优路径求解问题。本文从理论上研究了公共交通系统的模型，并考虑了实际出行时的多种换乘问题。此外，模型和算法的设计在理论上可以指导公共交通线路查询系统的开发。
【作者】杨洋；
【导师】徐炳吉；
【作者基本信息】中国地质大学（北京），控制理论与控制工程，2014，硕士
【关键词】公共交通系统模型；前K条最优路径算法；最早到达问题；最少换乘问题；最短运行时间问题；

【参考文献】
[1]陈江涛.在温室效应学术讨论会上的讲话[J].上海环境科学.1990(09)
[2]李成,常向前,郑艳萍.拉扭组合轴圆周表面裂纹应力强度因子仿真[J].农业机械学报.2008(02)
[3]龚乃国.电热合金Cr20Ni80热变形行为及热加工图研究[D].兰州理工大学,材料加工工程,2014,硕士.
[4]杨园.基于多元统计分析的学生综合素质评价[D].清华大学,统计学,2013,硕士.
[5]王培英,张世全,王红霞.发展民办高等教育与增强综合国力[J].高等工程教育研究.2002(03)
[6]董柏举.丝素蛋白纳米纤维—纳米金复合材料的制备及性能研究[D].苏州大学,2014.
[7]缪竟鸿1,罗维1,李杰1,齐继2.三维微波成像中基于对比源反演的扩展方法*[J].系统工程与电子技术.
[8]王念.现代汉语言新生语言成份的规范化[D].武汉理工大学,外国语言学及应用语言学,2004,硕士.
[9]林友.上颈椎手法治疗颞下颌关节紊乱的基础和临床研究[D].南方医科大学,人体解剖与组织胚胎学,2014,博士.
[10]刘影.基于PDCA理论的重点实验室产业化导向管理模型研究[D].南方医科大学,社会医学与卫生事业管理学,2012,硕士.
[11]田磊.基于RFID技术的矿下智能监控系统设计与实现[D].南京理工大学,计算机应用技术,2013,硕士.
[12]韩昆仑.基于瞬时功率理论的电网无功功率补偿的研究[D].广西大学,农业电气化自动化,2004,硕士.
[13]史丹.我国经济增长过程中能源利用效率的改进[J].经济研究,2002,09:49-56+94.
[14]付荣.冠脉非支架段新发病变患者的预后影响因素分析[D].大连医科大学,流行病与卫生统计学,2012,硕士.
[15]曾正明.合成地震记录层位标定方法改进[J].石油地球物理勘探,2005,05:104-106+144+19.
[16]李阳.农村幼儿教师流动问题研究[D].长春工业大学,社会学,2013,硕士.
[17]陈录广.活体磁共振波谱中GABA含量测量方法研究[D].华东师范大学,无线电物理,2013,硕士.
[18]舒梦珵,王真理,崔蕊,朴永红,梁瑶,赵惊涛.潜山裂缝型油气藏综合描述方法[J].石油地球物理勘探,2014,04:766-775+6-7.
[19]修巧梅.低碳物流驱动因素的研究[D].大连海事大学,交通运输工程,2014,硕士.
[20]马锐.多孔炭材料电极电吸附脱盐性能研究[D].北京化工大学,材料科学与工程,2013,硕士.
[21]刘玉东,刘东方,黎文豪,周小三,胡光华.水基氧化石墨烯纳米流体的制备及稳定性研究[J].化工新型材料,2012,05:107-109.
[22]孙亚.改革开放以来中国电影产业组织政策内容研究[D].湖南大学,传播学,2010,硕士.
[23]练洁.博物馆专题性临时展览研究[D].山东大学,专门史,2012,硕士.
[24]范泓洋.冠状动脉左主干病变冠脉旁路移植术风险预测模型评估[D].北京协和医学院,临床医学,2014,博士.
[25]宋海龙.水弹道建模与仿真方法研究[D].哈尔滨工业大学,人机与环境工程,2014,硕士.
[26]高晓波.分段进水AO生物脱氮工艺优化运行研究[D].长安大学,环境工程,2013,硕士.
[27]张颖.当代大学生消费伦理问题研究[D].西安外国语大学,马克思主义基本原理（专业学位）,2014,硕士.
[28]杨伦.基于WIFI的无线便携式汽车轴重称重系统设计与实现[D].长安大学,交通运输工程（专业学位）,2013,硕士.
[29]张曼.审计方法推荐系统研究[D].河北师范大学,应用数学,2013,硕士.
[30]陈亮,韩正之.混沌系统时滞反馈控制综述[J].控制与决策,2004,01:1-6.
[31]兰鹏.中国棉花期货与现货市场间的动态相关性研究[D].新疆财经大学,金融学,2013,硕士.
[32]张凯峰.基于EAI的银行自助服务系统数据处理平台的研究[D].华北电力大学（北京）,计算机应用技术,2003,硕士.
[33]傅世善.青藏铁路信号系统方案的研究[J].中国铁路.2002(03)
[34]徐彦利.上海市医药零售市场顾客满意度影响因素研究[D].东华大学,企业管理,2004,硕士.
[35]璜塃.一维与二维铁电体超晶格中若干倍频效应的研究[D].南京大学,凝聚态物理,2013,博士.
[36]李志强.苊并杂环类化合物S1在急性髓系白血病中的分子药理机制研究[D].大连理工大学,生物化学与分子生物学,2013,硕士.
[37]冯齐山.农民合作经济组织现状和政府行为研究[D].中国农业科学院,农村与区域发展,2012,硕士.
[38]赵海,陈燕,张德干,张晓丹.相联规则的粗熵挖掘方法及其在肇事逃逸侦破中的应用[J].东北大学学报,2004,10:938-941.
[39]李宁.污水处理系统半挥发性有机污染物环境归趋研究[D].哈尔滨工业大学,环境科学与工程,2013,硕士.
[40]陈婷婷.多热源集中供热系统优化设计研究[D].山东建筑大学,动力工程（专业学位）,2013,硕士.
[41]赵言涛.城乡一体化公共交通规划研究[D].山东大学,建筑与土木工程,2013,硕士.
[42]邹琴.我国竞技健美操女子单人操技术水平与先进国家比较分析[D].宁波大学,体育教育训练学,2013,硕士.
[43]杜宝红.《快心编》研究[D].华中科技大学,中国古代文学,2013,硕士.
[44]张朝霞.论格式合同的利益冲突与平衡[D].中国社会科学院研究生院,民商法学,2003,硕士.
[45]胡笑形.重磅炸弹级农药及其中间体的市场与开发[J].精细与专用化学品,2014,02:1-8.
[46]于芳芳.胎盘中抑制素受体的表达及与胎儿生长受限的关系[D].苏州大学,妇产科学,2013,硕士.
[47]魏红刚.授信3PL企业动产质押融资业务决策问题研究[D].西安建筑科技大学,物流工程,2013,硕士.
[48]孙媛.含油气盆地盐构造演化过程数值模拟[D].中国地质大学（北京）,地球物理学,2013,硕士.
[49]沈永言.卫星因特网[J].现代电信科技.2001(09)
[50]王彩虹,薛龙彦.高校图书馆发表期刊论文的h指数关联因素比较研究[J].情报探索,2015,01:42-48.