1、毕业设计文献综述 计算机科学与技术 城市公交换乘指南系统设计 一 . 前言部分 我国经济的持续发展必然加快城市化、机动化速度，更何况我国城市化水平本来就低于相应的经济发展水平。汽车进入家庭、城市扩张可能带来的郊区化趋势，与城市化一起成为21 世纪我国城市交通发展的大背景。我国私人汽车的迅速发展给城市交通系统带来了严重的影响。如何考虑私人小汽车和公共交通系统的竞争关系并建立一个有竞争力的公共交通系统；如何选择交通政策等，都影响这个城市的交通模式、城市建设。 城市的各种交通政策的选择和实施必须考虑城市的特性和资源、代价和 效果。因此有必要在可持续发展的目标下，借鉴国外城市的成功经验和失败教训，重新
2、检查城市交通系统的规划和建设，从而充分利用有限的交通资源，体现“无缝接驳”的人性化理念 1。目前乘客可以获得的公交信息很少，而且方式主要是常规手段。我国乘客一般获得公交信息的方式局限与电话，交通地图，向他人问询等常规方式。除去线路、站点等基本信息以外，有关班次，车辆到离站时间的信息基本上没有。 城市客运交通是由多种交通工具和交通方式组 成的立体化大系统。 除私人交通方式外， 通常情况下， 采用一种交通工具或同一路线， 不可能完 成所有的门到门服务， 因而， 各交通工具之间或同一工具不同路线间的相互转换是不可避免的。换乘是公共交通的一大特点， 也是与私人交通的不同之处。城市交通的换乘方式主要有停
3、车场换乘和乘车换乘两种。停车场换乘也叫存车换乘， 是指将自备车存放后， 改乘公共交通工具到达目的地的交通方式；乘车换乘是指从一种公共交通工具或一条线路，转换到另一种公共交通工具或另一条线路上的换乘方式， 这是一种前后衔接的连续转乘方式 2。下面通过以下两点说明公交换乘系统的必要性和重要性： .以百万人口占地一百平方公里的城市为例，若每平方公里 划分一个交通小区，其各点均直接联系需要 4 950 条线路，显然，这既无可能也无必要，必须用换乘的方式来解决 3；如果采用不同的交通工具，换乘更是大量存在。 公交以其覆盖面广、经济快捷的特点，目前仍然是绝大数出行者的首选方式。也是各地城市政府大力发展的交
4、通方式，如果能提供一种服务，为乘客的特别是外来旅游、出差等急需了解本地道路情况的人提供方便、快捷、经济、高效地利用公交线路的方案将方便他们的出行和生活，同时减少不必要 的交通流量提高交通运输的效率和城市的地位，便于广大乘客乘车合理而有效的安排行程，快捷简单的就可 以知道自己所需要乘坐的车次 我国实施城市的可持续发展之路，当然包括城市交通的可持续发展。所以大力倡导改善客运结构，大力发展公共交通乃当务之急。 二、主题部分 交通问题一直是城市管理的难题之一，而交通问题直接影响到人民的工作和生活。 随着国民经济的高速发展和城市化进程的加快 ,城市公交系统飞速发展 ,高效合理的公交线路选择系统对城市交通
5、的发展至关重要 4。国外较发达的国家的公交查询信息系统发展地相对成熟，他们采用结合所有城市交通工具及其所经的路线、并且与每一站点周围的建筑和公共设施联系起来的方式进行信息查询，确实 大大方便了市民的工作及生活。我国目前的公交查询系统也在不断完善，从无到有，从原始的人工查询发展到现在的网络信息查询，其变化之大，亦不可小觑。为了进一步实现公交系统信息化与广泛化，我国有些地方政府还与电讯公司签订智能交通信息化战略合作项目，足以见得交通信息化对社会发展的重要性。 在西方国家 (如美国、日本等 )，在城市公交网络系统上投入了极大的财力，构建了利用计算机网络和先进的通信系统的智能运输系，从而实现了大范围内
6、全方位发挥的实时、准确、高效的运输综合管理，使人、车、路密切配合，和谐统一，大大改善了交通环境等 5。 国内在这方面的起步较晚，但是各地政府都给予了极大的重视，相继建立了网上公交查询系统，但是效果不甚理想。主要存在以下一些问题： 其一是在公交查询设计时没有充分考虑乘客的各种需求 ;其二是没有考虑地铁和步行出行方式 ;其三是计算换乘次数的效率低 ,无论是广度优先还是深度优先 ,都是基于穷举搜索法 ,一般只能提供换乘两次以内的查询 ,这样不能适应城市快速发展的趋势和各种查询需求。特别是 ,如果要与现代通信相结合 ,让人们在任何时间、任何地点都能及时地获得可视化的最佳公交信息 ,更是需要查询的高效
7、6。 综合以上存在的一些问 题情况，可以具体设计一个基于 Web 的城市公交换乘指南系统设计来完善当前公交查询的功能，可具体实现以下功能：根据某一城市既有公交网络，为公交出行者提供换乘线路选择。公交换乘问题是多目标优化问题，需要同时满足两个或者多个目标要求以达到高效换乘的目标。本设计要求建立城市公交网络多目标优化模型，在此基础上建立换乘次数最少和乘车站点总数最少的双目标优化模型。但要做到真正人性化 ,还要作以努力 :其一 ,除准确了解公汽线路信息表、地铁线路信息表、换乘信息表、步行信息表外 ,还要调查了解乘客的各种需求 ,比如换乘时的步行距离长短 以及每路车的拥挤情况、服务态度等 ;其二 ,要
8、与 GSM 移动通信系统、城市电子地图、短信业务联合。本方法不仅可用于城市公交查询 ,稍作修改便可用于各种交通系统查询 ,因而具有较大实用价值和市场前景 7。 在设计城市公交查询时必须了解公交乘客出行时所考虑的因素，通过对公交乘客的出行心理和行为的研究来来设计高效的公交查询系统 1。因此城市公交换乘指南系统应该包括四个主要模块：线路查询模块、站点查询模块、公交换乘模块、后台管理模块。 线路查询模块 用户可以向系统提供自己要乘坐的公交线路 , 查询得到本路公交车经过的所有站点 8。基于 web的线路查询系统模块与用户有良好的交互性，使用者只需将所需查询线路输入线路查询区域后点击查询按钮即可得到该
9、线路所有的站点信 息。 站点查询模块用户可以根据某个站点名 , 通过系统查询出所有经过该站点的公交车线路 8。基于 web的站点查询系统模块同样与用户具有良好的交互性，使用者只需将所需查询的站点名称输入到站点查询区域，然后点击查询按钮即可得到所有经过该站点线路的信息。 公交换乘模块通过输入所查询的站点获得换乘次数最少的最优公交线路 9。目前，已经有许多的研究者在公交最优路径选择问题中做出了 相关研究。王建林提出一种基于换乘次数最少的城市公交网络最优路径算法，文中充分考虑了乘客乘车时的心理因素，并指出换乘次数最少是乘客出行时考虑的首要因素 9；胡霍真等人将最短路径算法应用到公交车网络中，并通过实
10、验验证该算法取了较好的查询结果 10；李洪波等人提出了一种动态优化的 Floyd 最短路径算法，提高了算法的运行效率 11。也提出了 Sudhakaran 遗传算法和 PSO 扑杀米为杂交技术经济调度问题 12和 一个实数编码的改进遗传算法及其应用 13。 目前对于公交换乘系统的算法已有很多种，总得 来说各有优缺点，一下算法思想在很多时候被广泛运用，也是值得研究的。如 基于最少换乘次数的算法思想 ：考虑从 A地到达 B地的公交换乘方案时 , 首先搜索 n次换乘方案 ( n为零表示直达 ) , 如果搜索不到 n次换乘方案 , 则继续搜索 n+1次换乘方案 ; 如果找到 n次换乘方案 , 就不再搜
11、索 n+1次换乘方案。当 n0时 , 程序采用递归算法搜索方案。当然搜索出的 n次换乘方案很可能不止一条 , 在这种情况下我们按代价从小到大排序 , 最多选择代价最小的前五种换乘方案给用户。首先 , 求出通过起始站点所经过的线路的集合以及经过目的站点所经 过的线路集合 , 求两个集合得交集 , 当交集不为空时 , 即存在直达线路。通过比较各条直达线路得代价 , 按代价由小到大排列 , 得到最优得五条线路 , 算法结束。其次 , 如果交集为空 , 则不存在直达路线 , 则需进行换乘 ,首先考虑一次换乘。通过以起始站点后站的所有站点集合内站点为起始站点 , 按照直达线路得搜索方式进行下一次搜索 ,
12、 求得各线路集合于目的站点线路集合得交集 , 按照各线路代价排序 , 即得到相应一次换乘路线。算法结束。再次 , 如果一次换乘交集为空 , 即没有一次换乘线路 , 则需进行二次换乘。具体算法与一次换乘相 同 , 即通过重复算法进行集合交集得求解。对于 3次换乘、 4次换乘、 5次换乘 , 则依次重复调用该方法。最后 , 如果超过五次换乘仍然交集为空 , 从实际角度考虑 , 基本已超出人们的心理承受次数 , 因此即认为没有从起始站到目的站的换乘方式。在实际公交线路中 , 据统计超过 90%站点间的线路不会超过 3次换乘 , 只有少部分需要进行 4次或 5次换乘，具体如下图所示。 后台管理模块可以
13、通过管理员对数据库系统进行添加、修改、删除公交线路等操作。在整个系统正常运行之前 , 需要对各个相关站点数据进行维护 , 确保系统的安全、 数据的完整以及站点的及时更新。进入系统管理模块前需要登陆系统 , 根据用户名和密码检测账号的合法性。当用户名和密码不正确时 , 返回登陆界面重新登陆。反之 , 表示验证成功 , 进入管理员管理界面 14。数据库系统是储存某种科学事实的计算机软件系统 15，因此该部分是整个公交查询系的主体部分，所有的查询数据都在储存在数据库系统中。 三、 总结部分 近几年来，城市的公交系统有了很大的发展。公交运输的覆盖面越来越广，公交 线路也日益增多，公共交通逐渐成为绝大多
14、数出行者的首选方式。发达的城市公交系统 使得公 众的出行更加通畅、便利，同时也给人们出行乘车线路的选择带来了一定的困扰。 方便、快捷、经济的公交出行线路方案，不仅可以方便公众的出行，同时也为城市交通 减少了不必要的交通流量，有利于提高城市交通的运行效率，展现城市的现代化风貌。经过查找一定的文献，个人觉得要实现以上基础的公交查询功能，关键在于使用合适的算法，一个好的算法能使各种功能的实现更加的简便。 公交换乘问题是多目标优化问题，需要同时满足两个或者多个目标要求以达到高效换乘的目标。本设计要求建立城市公交网络多目标优化模型，在此基础上建立换乘次数最少和乘车 站点总数最少的双目标优化模型。 本设计
15、最终将 根据某一城市既有公交网络，为公交出行者提供换乘线路选择。 目前也有很多公交换乘系统利用生物免疫系统中免疫行为可以保持种群多样性这一特性 ,在公交线网优化中应用免疫遗传算法。所采用的免疫遗传算法与一般的免疫遗传算法的不同之处在于 :首先 ,在遗传操作中加入了免疫疫苗的提取。其次 ,给出了算法可能陷入局部最优的条件。再次 ,采用动态疫苗接种。动态疫苗接种伴随了免疫选择的过程 ,所以不仅可以提高个体的适应度值和种群的多样性 ,而且可以防止陷入局部最优 ,加快算法整体的收敛速度。为了 保证全局收敛 ,本文在选择新算法时采用了杰出者保留策略 ,让全局最优个体不参加交叉、变异 ,以保证最优个体的全
16、部基因信息毫无破坏地被保留到下一代。通过测试路网的验证 ,免疫遗传算法能够在公交线网优化中取得令人满意的效果。 本设计的最终目标是实现在知道每条公交线上的站点的基础上 ,首先以换乘次数最少作为最优标准 ,当换乘次数相同时再以站点数最少为最优标准 ,用集合的方法给出了任意两站点之间的最优公交线路的查询算法 ;并给出了 ,选择换乘次数多 ,但站点数少的公交线路的条件 . 四、参考文献 1 关志宏， 刘小明 . 停车场规划 设计与管理 M. 北京： 人民交通出版社， 2003. 2 陆化普 . 交通规划理论与方法 M. 北京 ： 清华大学出版社 ， 1998. 3 陆锡明 . 综合交通规划 M.上海
17、 ： 同济大学出版社 ， 1999. 4 周 潜，欧宜贵 .公交线路查询算法的设计与实现 J.海南大学学报， 2010， 28（ 2）：105-107 5 曹桂发，傅俏梅 . 城市交通信息系统的设计研制 J.系统工程理论与实践 1997， (1),105-109. 6牟联明，刘高峰 .在一种城市公交查询算法 J.计算机应用与软件 ,2010， 27（ 8）： 79-91 7 景丽荣，马尚才，沈亮 . 基于最少换乘路径选择算法的改进 J.三西财经大学学报 ,2010， 1（ 2）： 168-170 8胡云峰 . 公交换乘系统的数据库结构及算法优化 J.文山学院报 ,2010,23(9):104-
18、107 9 王建林 .基于换乘次数最少的城市公交网络最优路径算法 J.经济地理 ,2005,25(5):673-676. 10 胡霍真 ,戴光明 ,李颖 .公交车网络的最短路径算法及实现 J.微机发展 ,2005,15(9):21-22. 11 李洪 波，王茂波 .Floyd 最短路径算法的动态优化 J.计算机工程与应用 ,2006,34:60-63. 12 蔡自兴 ,徐光佑 .人工智能及其应用 M.北京：清华大学出版社 .2003： 17-18 13胡云峰 . 公交换乘系统的数据库结构及算法优化 J.文山学院报 .2010,6(2):104-105 14 Sudhakaran M.GA an
19、d PSO culled hybrid technique for economic dispatch problem with prohibited operating zonesJ. Journal of Zhejiang University.2007.8(6):896-903 15 * Zhong-Lai Wang,Ping Yang. An Improved Real-Coded Genetic Algorithm and Its ApplicationJ. Journal of Electronic Science and Technology of China .2008.3(6):43-46
