【毕业学位论文】（Word原稿）公共交通换乘算法研究及查询系统实现-数据挖掘数学

1 学号： 分 类 号： 密级： 公开 学校代码： 10636 四川师范大学 硕 士 学 位 论 文 公共交通换乘算法研究及查询系统实现 周道清 学 生 类 别 高 师 硕 士 培 养 单 位 四川师范大学数学与软件学院 指 导 教 师 冯 山 职称 教授 专 业 名 称 基础数学 研 究 方 向 数据挖掘方向 论文完成日期 2012 年 10 月 10 日 2 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师 冯山 指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品 或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥有学位论文的部分使用权，即： 1）已获学位的研究生必须按学校规定提交印刷版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库供检索； 2）为教学、科研和学术交流目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 （保密的学位论文在解密后适用本授权书） 学位论文作者签名： 导师签名： 签字日期： 年 月 日 签字日期： 年 月 日 1 公共交通查询系统算法研究及系统实现 高师硕士 基础数学专 业 研究生：周道清 指导教师：冯山 摘要 随着社会与经济的发展，城市规模的扩大，城市交通问题日益严重。要解决好交通问题，除了加强交通硬件投入外，还更应加强交通服务系统的建设。公共交通查询系统作为交通服务系统的重要部分，它给出行者提供准确的交通信息，提高公交出行的舒适度，这对缓解交通拥挤和降低城市尾气污染起到积极作用。 本文首先介绍了公共交通网络概念，介绍了公交网络优化的基本内容、约束条件，建立了最优路径模型和公交搜索模型。其中，在公交搜索模型中，作者给出了更适合 出行者需求的双目标优化模型，即第一目标是以换乘次数最少，第二目标为停靠站点数目最少。在传统搜索算法中，比如 法、 K 算法中，由于都需要回溯，当城市公交站点数目到达一定程度后，搜索效率非常低，而本文在直达、一次换乘、二次换乘情况中首次引入集合论思想，通过集合论的特性，大大降低搜索规模，提高搜索效率。 本系统的开发主要是基于 B/用 架开发， 并结合公交网络查询系统的特点，以及用户的心理，设计出自己的算法，并实现线路查询，站点查询，换 乘查询等功能。本架构按照 务层和数据层分离，设计原则是尽量降低各层之间的耦合度，从而提高开发速度和质量，便于以后升级。 关键词： 公共交通网络 最优路径 换乘查询 法 2 of of of in To we of As an of to of a of of s A of a is of is is of at a on of by of as in of of is , of to of In to 3 eb of is to of of s in of 4 目 录 第一章 绪论 . 6 . 6 内外研究现状 . 7 . 7 . 8 . 8 第二章 公交网络拓扑化 . 10 . 10 . 11 . 13 共交通网络分类 . 13 共交通构成要素 . 14 . 15 . 16 第三章 公共交通信息查询系统分析 . 18 共交通信息分析 . 18 共 交通线路分析 . 18 共交通站点分析 . 18 共交通网络抽象 . 19 共交通线路的抽象 . 19 共交通站点的抽象 . 20 共交通查询 . 21 路查询 . 21 点查询 . 22 乘查询 . 23 驳换乘 . 26 第四章 公共交通信息查询系统及算法研究 . 27 型的建立 . 27 . 28 交线网最优路径模型的建立 . 28 . 30 5 点换乘查询改进算法 . 33 达情况思想 . 33 次换乘思想 . 33 次换乘思想 . 34 进算法的流程图 . 34 . 36 第五章 公共交通查询系统的设计与实现 . 37 . 37 统需求分析 . 37 统总体设计 . 39 统开发流程 . 41 统数据库设计 . 42 据库访问流程 . 42 统数据库设计 . 42 名规则 . 44 . 44 统结构 . 44 询模块的功能的实现及测试 . 45 页显 示 . 45 线路查询 . 46 站点查询 . 47 乘查询 . 47 . 49 交线路管理 . 50 第六章 总结与展望 . 52 致 谢 . 54 参考文献 . 55 6 第一章 绪论 究背景 随着我国人民生活水平的提高，人们对汽车的需求日益增强，据汽车工业协会发布的数据 1， 2010年低挂牌行驶的汽车数量为 辆，并且每年以 10%的速度递增。汽车的增加导致交通拥挤、堵塞、尾气污染等严重问题，尤其 是交通拥挤已经造成城市公交速度减慢，以重庆为例，目前城市路面公交车辆平均速度为 15km/h2。要缓解交通拥挤问题，除增加交通等基础设施的投资外，还应该大力发展城市公共交通系统。 城市公共交通系统是各级政府倡导大力发展的，具有辐射的区域广、成本低的特点，目前是人们首选的出行方式，不管是北京、上海、广州等一线城市，还是二线城市以及区县城市，都已经形成比较完善的地面公交系统。但由于城市规模的扩大，常规地面公交网络已经无法满足人们出行需求，尤其是远距离出行，因此很多大城市大力发展轨道交通（如地铁、轻轨等），截止 到 2010年底，中国大陆已有地铁或已获国家批在建地铁的城市有北京、上海、天津、广州、深圳、南京、成都、沈阳、长春、大连、重庆、武汉、杭州、哈尔滨、西安、苏州、青岛、长沙、无锡、福州、东莞、宁波、济南、厦门、常州、郑州、南昌、南宁等 28个城市，中国大陆已有轻轨或已获国家批在建地铁的城市有上海、北京、天津、大连、南京、西安、沈阳、重庆等 8个城市。目前，很多城市公共交通系统已经包含了常规的地面公交、地上的轻轨，地下的地铁，彼此相互衔接，相互补充，为城市的快速流通起着重要的作用。 城市有了现代化的公共交通设施后，还 必须充分发挥这些设施的最大作用，才能有效改善城市的交通质量。要最大发挥交通设施的作用，还应该提高公共交通服务水平，提高交通服务质量，来吸引市民选择公交出行。影响城市服务水平的主要因素有：方便性、迅捷性、经济性、舒适性 3。根据以上四个因素，各级政府主要采取的措施有： 1. 优化布设公交网络。利用现代科学技术对整个公交网络线路进行优化，科学设置站点，认真分析区域公交网密度，全方位优化城市交通网络，使得城市站点连通度大，线路最短、运送的客流量最大。 2. 改善交通配套设施，如加载 立电子站牌等装置。 7 3. 提高车速，设立城市公交专用车道，提高运行速度。 4. 开发智能交通系统，利用计算机和通信技术，开发现代化的公交信息系统，有机地将出行者、交通管理者、交通工具联系起来，实现智能管理，为乘客提供准确交通信息 4。 目前，我们国家在交通建设、公交配套设施、提高车速等方面采取了有效措施，但我国公交系统普遍存在信息化管理落后，尤其是公交查询系统，人们在不熟悉区域仍然靠传统的询问路人的方式解决。 本文将基于轨道交通和常规交通等综合公共交通网络模型的最优路径算法进行研究。通过对 法进行改进，目标是 开发建立智能交通系统的公交查询系统，目的是在任意站点能够给乘客提供公交信息以及公交换乘信息，为乘客提供方便，提高出行效率。 内外研究现状 在实际应用方面，西方国家由于信息技术、通信技术、无线电技术的先进，美、欧、日等发达国家很早就开始开发建立智能交通系统（ 称 早在 1969 年，日本就开始在部分城市导入交通管理系统，采用广播和道路通告牌方式向行驶的汽车提供道路信息。 1996 年 7 月，日本制定了更加详细 体 构思，准备用 15到 20 年的时间让日本的道路更加智能化，实现人、车、路三者的和谐互动 5。截止到 2011年底，美国政府和私人公司共同投资 2000亿美元建造全国的 系统能够平均减少出行者 12%的出行时间，交通效果非常明显 6。 在理论研究方面， 1925年， 率先将启发式算法运用到公交网络设计中； 1979年 和 分别就直达以及单条线路进行了优化设计； 1995 年， 0等人采用人工智能算法，能够根据设计者和用户的要求设计选择方 案； 1994 年， 1对 算法进行改进，把算法推广到全国城市，搜索范围扩大，但仍然需要大量的人工干预； 2004 年， 用遗传算法，按费用最少进行公交网络优化； 2等解决公交方式换乘过程中计算换乘数目及换乘中的 8 非线性费用等。 研究的公交出行最优路径方式中的行为问题 13。这些理论算法的提出，为开发公交管理系统提供理论保障 14。 内研究现状 与西方国家相比，我国的公交事业发展相对落后。目前我国公交出行的分担率平均不足 10%，特大城市也不超过 20%，而美日本等国家的大城市有 40%人选择公交出行。由于汽车的增多，公交车的车速越来越低，目前据调查大城市平均车速为 0 15。而我国公交综合管理系统还处于起步阶段，轨道交通和常规公交部门各自为阵，发展进程中互不协调。在基本的城市公交查询系统中难以找到一个能够查询航空、铁路、地铁、轻轨、公交汽车等综合为一体的系统，往往使得乘客在查询交通信息时获得的公交信息少，获得综合交通信息的途径很少，同时，查询系统所提供的公交 信息常常也不能保障其完整性和准确性。 虽然我国公交查询系统应用上起步较晚，但是在相关基础理论研究领域发展还是较快，取得了一定的研究成果。例如：韩传峰提出的平均换乘次数概念能够很好地对城市公交网络的性能做出评价 16。翁敏、苏爱华等专家通过长期的研究和分析，结合图论的有关知识，基于传统的 17。同时，在 2008 年北京奥运会召开前夕的全国大学生数学建模竞赛中，竞赛委员会的专家们直接将北京市的公共交通换乘查询系统建设问题作为当年的竞赛题（ B 题），表明城市交通 中的公共交通的智能管理和查询系统的建设问题在我国已经引起管理部门的重视，尤其是大城市和特大城市中的公共交通线路查询问题。这一问题的提出直接导致国内很多相关的专家、学者开始针对城市公共交通智能查询这一问题同时展开了理论和应用方面的研究。在最近几年的硕士学位论文中，华中科技大学的邹明霞、长沙理工的夏单等都研究了基于不同技术开发公交查询系统的问题。 文的研究内容与技术路线 本论文将讨论轨道交通和常规交通网络各自特点，建立基于轨道交通和常规交通网络构建综合公交查询系统，具体的技术路线如下： 9 1、分析公交网络 的特点，给出公交网络的抽象和拓扑表示方法。 2、介绍公交信息查询系统的需求分析、系统功能分析、研究乘客出行的心理等。 3、建立公交最优路径搜索模型，介绍传统的求解算法，研究以时间和换乘方式作为规划目标的改进算法。同时在传统公交网络的一次换乘和二次换乘酸法以及考虑轨道交通后的驳接算法等。 4、详细介绍系统的设计与实现过程，对系统各个模块作具体的实现，同时以重庆市公交路线为数据，验证查询结果。 5、总结展望本论文优点与不足。 10 第二章 公交网络拓扑化 在城市道路中，马路和 公交站点都是相对固定，而依托城市道路的公家网络由这些马路和站点可以组合成庞大复杂的交通网络系统，如果把公交线路看成边，公交站点看成顶点，则公交网络就可以抽象成图论中一个有向图。 论的基本知识 一个图由两部分构成，一部分是节点，也称为顶点（ ,另一部分是顶点的偶对，称为边（ ,事实上，图论可以很好抽象成集合论中的二元关系，反过来任何一个能用二元关系描述的系统，都可以用图这种数据结构来表示。图论涉及到如下基本概念：如路径、加权图、连通性等。下面我们引入图论中的基本概念。 由点集 点之间的边集 ,( 为 图 ，用),( 表示。 。 图 2的构成 在图 2点集合 V=A,B,C,D，边集合为 E = 11 图 2向图 如果图中的边是有向的，称为有向图，如图 2示。图中的边是无向的，称为无向图，在无向图中，首尾相接的一边的集合称为路。在有向图中，顺时针方向的首尾相接的一串有向边集合称为有向路。通常，用顺序节点或边来表示 路或有向路。如图 2， 一条路，该路也可用 表示。 起点和终点相同的路称为回路（或圈）。在一个图中，如果任意两顶点间都存在一条路，则此图称为连通图。 若给图中任意边 ),( 赋一个数 ),( 该数值叫边的权。有向图的各边带权数后，则称为有向赋权图。根据不同的实际情况，权数的含义可以各不相同。在最短路中可以用权表示两个点之间的长短、距离等。 图的应用领域非常广泛，结构复杂，图的表示方法也比较多，常见的有图的邻接矩阵表示法和图的邻接表表示法。 1. 邻接矩阵 邻接矩阵是用矩阵来表示图中节点间有无连接的邻接关系。由于图中顶点之间的关系是 1对多的关系，如果图 G有 n 个节点，可以用一个 邻接矩阵 中，用i 和节点 j 之间是否有关联关系，具体表示方法如下 : 12 边若两个顶点之间不存在若两个顶点之间存在边01 例如，对图 2 图 2向图实例 其邻接矩阵的表示如下： 0100101101010110A 显然，对无向图的邻接矩阵表示一定是一个对称矩阵。 对于有向图来说，其邻接矩阵不一定是对称的。例如，对有向图图2 图 2向图实例 其邻接矩阵的表示结果如下： 1 2 3 4 4 1 2 3 13 0000101100000110A 共交通网络模型 共交通网络分类 城市公共交通主要包括轨道交通和常规地面公交两种类型，而轨道交通又分为地铁、轻轨、有轨电车、独轨交通、自动化导向交通、缆索轨道、磁悬浮交通等几种类型。 1. 地铁：也称为快轨交通，是大运量轨道交通的主要手段，特别适合于城市市区交通建设。地铁有专门车道，大部分在地下行驶，一般不占用地面空间，运营干扰小，运输能力大，是目前城市轨道交 通最主要手段之一，就连山城重庆，最近几年也大力发展地铁。 2. 轻轨交通：一种中等容量的快速交通系统，是现代化水平很高的有轨电车客运系统。整条线路可以在地面、高架区域或少量地下区域组。目前，轻轨系统被认为是空中的的快速公交系统。 轨道交通的其他几种形式如有轨电车是比较老式的交通方式，它会占据大量地面空间，目前已经被淘汰。对于独轨交通和自动化导向交通方式，目前在国际国内均无实际应用实例。缆索轨道多用于旅游观光之地，在大城市中，目前已经失去其交通运输的基本功能。例如，全国有名的重庆长江索道，由于其城市交 通中众多大桥的修建，原有的长江索道的交通运输功能逐渐失去。目前，它只是作为重庆市的一个城市符号，仅用于市民观光之用。磁悬浮交通由于对技术和投资要求高，目前仅限于在中国上海使用。它还不是城市轨道交通的主要形式。 综上所述，目前轨道交通的最普遍形式是地铁和轻轨。 城市公共交通的另外一种重要形式是常规地面公交方式。常规地面公交常见形式有 市快速公交系统简称）、常规公交和支线公交三种形式 18。 我们国家常规交通虽然形式多样，但是彼此之间的区分并不是很严格 14 的。本文在研究和讨论时将不严格区分这几种交通形式， 一律统称为地面公交。 共交通构成要素 理论上讲，不管是轨道交通，还是常规地面公交，它都是由一条条的交通线路组成，而每一条交通线路又是由若干的站点组成，所有这些由站点构成的线路实际上构成了一个连通图。在构成线路的这些站点中，根据人们完成一次交通旅行的乘坐的过程和特点，又将其分为起点站、终点站和中间站三种类型，中间站点可进一步分为换乘站点和一般中间站点。对公交线路的布局以及各线路上的站点的设置是十分重要的交通管理任务。合理地线路布局和科学的站点设置将有利于提高人们出行时选择公交手段的比例，从而提高公 共交通设施和运输工具的利用率，减少城市道路上机动车的数量 19，并由此减少二氧化碳等有害气体的排放量，达到有效节能和环保的效果。 公共交通线路中，站点和站点之间的连接方式有多种。它既可能是轨道交通形式中的站点，也有可能是常规交通形式中的站点。站点的方向既可以是单向的，也可以是双向的。按照交通线路网络中线路的性质划分，一般可以将其划分为地铁线路、轻轨线路以及公交线路等三种类型。 图 2型的公共交通线路网络图（局部） 21111 51111 41111 地铁 轻轨 公交线路 步行线路 15 从拓扑结 构上讲，一个公共交通网络一定是一个有向图，其中的各站点之间的连接路段的方向是一般来讲是双向的。 例如，对图 2设公共交通网络中的站点集合用 接路段的集合用 E 表示，则该公交网络可以表示成图 G(S,E)。其中，S= 7,.| 点之间的线路对应的是公交线路， 7 是公交线路之间的换乘站点， 间的换乘一般是通过步行换乘，一般步行时间不超过 10分钟。 交网络特点 要注意的是，公共交通网络与道路网络是不同的。公共交通网络具有以下特点 20 1. 连通性 在公交网络中，线路上的连接点可能是同一公交线路路段相连通，也可能是不同共交线路路段在同一个换乘站点实现连通，也可能是不同共交线路路段在不同站点之间的连通。一般来说，道路连通的不一定公交网络连通，因为，在道路的两个端点需要经过换乘方式的选择或者换乘站点的选择才能实现公交网络的连通。 2. 节点性质 一般而言，不同的公交线在路径上可以有一定的重叠，但是属于各自线路的站 点不可能完全一样。有些站点在一定距离内名字一样，因而，在作节点性质分析时需要做叠加分析，要求把空间上适当距离内的不同线路上的同名站点按一定原则抽象或合并成一个（逻辑）节点。 3. 弧段性质 在公交网络中，公交网络一般有单行线，双行线、环行线等类型，即实际的公交线路上的路段是有方向的。例如，在一个城市所布局的公交线路中，如果公交线路有 n 条，一般将该公交线路网中的线路抽象成 2n 条（逻辑）线路。根据线路方向上的起点和终点，可以把公交线路抽象成上行和下行两条线，以有效地避免单行线、双行线和环行线类型线路的差别所带来 的公交网络问题的分析难度。 16 交网络改进表示形式 根据上面章节对公交网络特性的阐述可知，城市交通网络常常用表示公交网络的相邻矩阵和邻接表工具进行表示。在交通网络查询系统的研究和开发中，我们提出了以连接矩阵为基础的适合公交网络算法研究的 以站点和线路概念为表述基础。 在 阵的每 1列对应的是站点位置，其在每 1行上的取值表示它是否在对应线路 (行 )上，如在则为 1，否则为 0。矩阵的每 1行代表一条线路，其在每 1列上的取值表示该列 对应的站点是否在该线路上。 可见，在此表示方法下，可以很好地表达出公交网络中各线路和各站点之间的完整关系，它可以方便我们求解有关共交网络的咨询问题、网络优化问题等。 例如，如图 2示，在该网络中有 10 个站点， 4 条线路（含一对上、下行线路）如下： 图 2共交通线路网络图例 2 9 7 11 5 17 线路 1L ： 上行： 1S 下行： 4S 线路 2L ：环行： 1S 线路 3L ：双行： 2S 0S 根据 2以将图 2 1S 2S 3S 4S 5S 6S 7S 8S 9S 10S 313021201110101100001010110000100000011101000001110101011010010110101001（ 矩阵） 可见， 阵有以下特点： (1) 它的行数总是偶数。因为，任意一条线路都被表示为两条线路：上行和下行，分别对应的第二维下标值是 0和 1。 (2) 它的列数包含了所有的公交网络中的站点值。 (3) 它的每一个矩阵元素的取值为 0或 1。 (4) 当公交网络很大时，该矩阵应该是一个稀疏矩阵。 18 第三章 公共交通信息查询系统分析 共交通信息分析 共交通线路分析 由前一章的城市公交网络拓扑分析可知，整个城市公交网络由若干条线路组成，而线路由许多站点组成。为了方便地进行公交网络系统的信息化，公交信息查询系统一般将公交线路网络分为以下几种类型加以分类和分析。 1. 上行下行线路重合 这种公交线路有一个起点站和终点站，起点站和终点站之间的站点即中间站。对于双向行车的线路具有如下特点：上行下行线路行走的道路一致，行使方向相反，中间站名字相同，但站点位置不同。目前，这种线路是城市公交中最主要的 形式。 2. 上行下行不一致 这种公交线路除起点和终点站外，中间站点集合中的某些站点的上行线和下行线是不一致的，或者线路的某些地方是单行道。 3. 环行线路 这种线路起点站和终点站处于同一个位置，它和中间站点一道构成一个环状线路，原则上没有上行和下行区别。但是，要注意的是环形线路的行使方向有两个。 可见，在数学模型的抽象中，对公交网络线路信息的准确完整的描述必须全面考虑线路的站点构成、线路的上行和下行站点的构成等因素。 共交通站点分析 1、位于不同地点的同名站点 城市交通线路网络依赖于城市道路 网络。在城市道路网络中，有些交通枢纽往往有多条公交线路经过，为了减少公交车在同一个站点停靠太多 19 车辆，通常的做法是在相隔不远的地方建立几个停靠站点，以停靠不同线路的公交车。这些站点之间应满足如下关系：彼此之间的物理距离不会太远，但可以用同一名字来表述该站点。在实际生活中，一般都将同名站点视为同一个站点，在公交网络线路查询系统开发中，也将这样的站点认为是同一个站点。 例如，图 3 2、位置紧邻的不同站名 两个站点是不同的，但 在道路上的物理距离很近。例如，两个站点距离不超过 100米，其步行只需要少量时间。图 3 共交通网络抽象 共交通线路的抽象 公共交通线路在交通网络中可以抽象成连接各点的有向边。根据对实际情况的分析，我们可以将其分为以下几类。 图 3点相邻但站点名不同的实例 (a) 十字路口站点 (b) 繁忙路段站点 图 3点位置不同但站点名字相同的线路站点实例 20 1. 完全的双向线路 公交车在两个端点（即起点站和终点站）之间行车，两个方