【作者】 杨洋；

【导师】 徐炳吉；

【作者基本信息】 中国地质大学（北京） ， 控制理论与控制工程， 2014， 硕士

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

【Abstract】 With the rapid development of economy, people have much more requirement for travelbecause of business, tourism and visiting so that the traffic problems become increasinglyserious. So much more people will choose to travel by railway, highway, flight and ship.Due to the well-developed public transportation system, it is impossible to find the bestitineraries for passengers only by searching the memory of the conductors. It is also notintelligent to find the itineraries by passengers themselves in the huge transport networkinformation. Therefore, it is necessary to build a data model for the time-table informationof public transportation system and provide convenient, fast and accurate trafficinformation for travelers.In this paper, firstly, we analyze the travel requirement of passengers and introduce anexcellent algorithm: deletion algorithm, and two general top-K shortest path algorithmsused in public transportation system: recursive Dijkstra algorithm and genetic algorithm.After the comparative analysis, we found that the time consumption in deletion algorithm isless than either recursive Dijkstra algorithm or genetic algorithm. So we mainly study theapplication of the deletion algorithm in public transportation system. Secondly, we reviewtwo typical models used in modeling the public transport system: the time expanded modeland time dependent model, and focused on China’s railway transportation system weestablish the network model for solving the earliest arrival problem. Finally, in order tomeet the demand of passengers and provide a variety of travel itineraries for passengers, wesolve the top-K earliest arrival itineraries, the top-K shortest travel time itineraries and thetop-K minimal number of transfer itineraries problems by using the deletion algorithm inthe time expanded model, meanwhile we modify the deletion algorithm, so that themodified algorithm can be used to solve the top-K earliest arrival itineraries problem in the time dependent model. The experimental results show that the time consumption of themodified deletion algorithm is less than the original deletion algorithm. It is particularlysuitable to solve the top-K shortest paths problem in large-scale public transportationsystem. In this paper we study the network model for public transportation systemtheoretically with considering a variety of transfer problems in reality. The models and thealgorithms can provide a theoretical method for the research and development of publictraffic system.更多还原