基于最少换乘算法的公交查询系统

宋爽+张维石

摘要：分析公共交通网络结构的特征，基于图论的方法，明确公交网络中最短路径的意义。根据对公交乘客出行心理的调查，发现换乘次数最少是首要考虑的因素。从节省存储空间、提高运算速度出发，将最少换乘次数问题转化为最短路径问题，设计并实现了一个基于最少换乘算法的公交查询系统。以大连市具体的公共交通情况为例，证明系统是实用有效的。

关键词：公交查询；公交网络；最少换乘；最优路径；Dijstra算法

中图分类号：TP319 文献标识码：A 文章编号：1009-3044（2018）01-0096-03

Abstract： Analysing the characteristics of public transport network structure，and using method Based on graph theory，the significance of the shortest path in the public transport network is defined. According to the survey of bus passengers' travel psychology， it is found that the least number of transfers is the primary consideration. Starting from saving storage space and improving operation speed， the minimum transfer number problem is transformed into the shortest path problem，a bus inquiry system Based on least transfer algorithm is designed and implemented. Taking the specific public traffic in Dalian as an example， it is proved that the system is practical and effective.

Key words： public transport query； public transport network； least tranfer； optimal path；Dijstra algorithm

1 背景

在城市化水平不断提高的当代中国，各个城市的公共交通也随之快速发展。随着“低碳生活，绿色出行”概念的提出，以及大连市内各种私家车限行政策和公交车优惠政策的实行，使得人们更愿意选择公交车作为出行必要的交通工具。公共交通已经成为城市化发展和全面提高城市化水平的首要问题，是人们出行的首要选择，越来越多的公交路线被提供，给人们出行带来便利的同时，也给人们的选择带来了更大的困扰。在综合考虑时间、距离、票价等因素的基础上，人们更倾向于选择以换乘次数最少为第一基准、时间最短为第二基准的路线作为出行路线。以大连市现有的公共交通情况为例，基于Android平台，使用开源的、与操作系统无关的SQLite数据库，通过对百度地图API的调用，设计并实现了最少换乘算法下的移动公交查询系统。

2 系统设计与实现

2.1 系统总体设计

系统采用结构化的方法进行总体设计，即把一个复杂系统的功能实现过程分解成各个子模块的功能实现过程，这种分解过程是自顶向下、逐层分解，使得每个子模块实现的功能都控制在人们容易理解和处理的范围内，并能够保持子模块功能的独立性。系统主要分为两大功能模块，一是服务端后台管理模块，面向公交管理人员，主要实现了公交基本信息的管理，系统公告的管理、交互信息的管理等功能；二是客户端用户查询模块，面向普通用户，主要实现了公交信息基本查询、换乘查询、热点搜索、留言板等功能。

服务端后台管理模块中的公交基本信息管理主要用于添加、删除或修改正在营运的公交线路、站点、运行时间、票价等基础信息数据。系统公告管理主要用于发布重要事项和通知，例如线路站点临时变更信息、线路暂时停运信息等。交互信息管理主要用于对用户的意见建议进行反馈，提供人性化管理给用户。

客户端用户查询模块中的公交信息基本查询主要用于进行线路、站点、运行时间以及票价等的查询。换乘查询主要用于為用户提供起始站和目的站间最合适的路径规划。热点搜索主要用于搜索当前位置周边的KTV、饭店、商场等信息并在地图上显示给用户。留言板主要用于普通用户进行意见反馈、分享实时公交信息等。

2.2 数据库设计

客户端采用Android自带的轻量级关系型数据库，占用资源低，在嵌入式系统中，大概只需要几百K的内存，能够支持主流的操作系统，同时能够跟很多程序语言相结合，比起Mysql、PostgreSQL这两大开源的数据库，处理速度更快。

服务端采用SQL Server关系型数据库，具有使用方便、与相关软件集成度高等优点，已逐渐成为Windows平台下进行数据库应用开发较为理想的选择之一。而且，由于其易操作性及友好的界面，赢得了广大用户的青睐，尤其SQL Server与其他数据库如Access有良好的ODBC接口，可以将其转成SQL Server数据库。服务端主要设计三个数据表来存储公交信息，分别是线路表、站点表以及线路-站点表，其数据字典如表1、表2以及表3所示。

2.3 查询功能设计

公交查询系统中最主要的功能就是公交基本信息和换乘路径的查询，以下分别简单介绍线路查询模块、站点查询模块、换乘查询模块和到站时间预测模块。

2.3.1 线路查询模块

系统根据用户输入的线路在本地数据库进行查询，如果该线路存在，则直接显示查询结果；如果不存在，则联网进行查询，首先判断线路输入是否为空或不合法，如果是则弹出错误提示，否则在后台数据库中查询线路的所有信息，包括公交名称、始末车时间、站点总数和票价。如果存在查询结果，则将其显示，否则提示线路不存在。endprint

2.3.2 站点查询模块

系统根据用户输入的站点访问本地数据库，如果站点存在，则返回途经该站点的线路列表，用户选择一条指定线路后，返回途径该站点的线路列表；如果不存在，则进行联网查询，首先判断站点输入是否为空或不合法，如果是则弹出错误提示，否则在后台数据库中查询该站点，找到途经的所有线路。如果存在查询结果，则将其结果显示，否则提示站点不存在。

2.3.3 换乘查询模块

换乘查询功能是系统最重要的模块，用户输入起始站和目的站，系统查询数据库数据并根据最少换乘算法，设计合适的出行路线。系统首先访问本地数据库，判断起始站是否存在，如果起始站存在，则再次访本地数据库，判断目的站是否存在，如果目的站存在，则返回换乘路线供用户选择。用户选择其中一个路线，可显示该路线的具体方案。

2.3.4 到站时间预测模块

公交车辆到达时间预测主要利用GPS定位系统、乘客手机GPS定位系统来获取乘客和待乘公交车之间的距离，再根据公交车辆当前的速度，和具体道路交通状况，从而估算出公交差到乘客所在位置大致需要的时间，提前5-10分钟提醒乘客。

3 核心算法分析与实现

3.1 公交网络及最短路径

公交网络是由线路和站点组成的，一条公交线路需要经过若干个站点，一个公交站点又会有若干条公交线路经过，公交线路与线路之间通过共有的站点产生联系，而公交站点与站点之间则通过线路产生联系。将公交站点用有穷非空的点集合V来表示，公交线路用有向带权的边集合E来表示，构成的二元组G=（V， E）则可以表示一个公交网络数据模型。

最短路径问题是图论中研究的一个经典算法问题，旨在寻找图中任意两顶点之间的最短路径。公交网络中最短路径问题可以描述为从起始站点S出发到达目的站点E，其中S和E之间可行的线路往往不只一条，而是有很多条，那么这么多可行的线路中哪一条是最短的呢？这里的“最短”可以是指实际经过的路程最短，也可以拓展为许多方面的最高效率问题，比如时间最短、费用最少、线路利用率最高等标准。

3.2 传统的Dijkstra算法

经典的图论与计算机算法的有效结合，使得新的最短路径算法不断涌现。目前提出的最短路径算法中，使用最多、计算速度比较快，又比较适合于计算两点之间的最短路径问题的数学模型就是经典的Dijkstra算法。

Dijkstra算法是典型的单源最短路径算法，用于计算从一个顶点到其余各顶点的最短路径，由Dijkstra EW于1959年提出，适用于所有弧的权均为非负的情况，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。该算法的基本思想是：设G=（V， E）是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 ， 就将加入到集合S中，直到全部顶点都加入到S中，算法结束），第二组为其余尚未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

Dijkstra算法存在的局限性：实现Dijkstra算法的核心步骤是从未标记的点中选择一个权值最小的弧段，这是一个循环比较的过程，必须把所有的点都扫描一遍。在大数据量的情况下，由于传统的Dijkstra算法求解最短路径问题运用了关联矩阵、邻接矩阵和距离矩阵，在存储图形数据和进行运算时，需定义N×N的数组，其中N为网络的结点数，当网络的结点数较大时，将占用大量的计算机内存，同时大数组运算起来是很浪费时间的。

3.3 基于最少换乘的最优路径选择算法

最少换乘算法的一个明显缺陷是随着换乘次数的增加，搜索速度会越来越慢，因此根据大连市公交线路的实际情况，本文认为三次及以内的转车是比较合理的，超过三次的转车情况在这里不予考虑。算法具体步骤如下：

1） 直达：设经过起点S或其附近的线路为集合Ls，对应的经过终点E或其附近的线路为集合Le，寻找Ls与Le的交集，如果有则存在从起点S到终点E的直达线路，输出结果，结束运算，如果没有则进行下一步。

2） 一次换乘：设起点S乘车能直达的站点为集合Ms，Ms中的站点及其邻近站点所经过的路线为集合Lms，寻找Lms与Le的交集，如果有则存在从起点S到终点E的一次换乘线路，输出结果，结束运算，如果没有则进行下一步。当搜索到的方案数目达到设定的最大方案数目maxCase时，结束搜索。

3） 二次换乘：设能够直达终点E的站点为集合Me，Me中的站点及其邻近站点所经过的路线为集合Lme，求Lms与Lme的交集，如果有则存在从起点S到终点E的二次换乘线路，输出结果，结束运算，如果没有则进行下一步。当搜索到的方案数目达到设定的最大方案数目maxCase时，结束搜索。

4） 三次换乘：设起点S通过一次换乘所能到达的站点为集合Mms，Mms中的站点及其邻近站点所经过的路线为集合Lm，求Lm 与Lme的交集，如果有则存在从起点S到终点E的三次换乘线路，输出结果，结束运算，如果没有则进行下一步。当搜索到的方案数目达到设定的最大方案数目maxCase时，结束搜索。

4 结束语

根据城市公交运行的实际情况以及人们出行的具体需求，以大连市为例，基于Android平台，利用Java和JSP编程语言，设计开发了基于百度地图的移动公交查询系统，实现了对公交的线路信息、站点信息、换乘信息的查询以及个性化定制服务，例如：语音搜索、到站提醒等功能，为用户出行选择高效快速的乘车路线提供了帮助。

参考文献：

[1] 崔琳. 城市公交线路查询系统的设计与实现[J]. 宿州学院学报， 2011， 26（8）：46-48.

[2] 文斌. 基于Android的移动公交辅助导航系统设计与实现[J]. 成都信息工程学院学报， 2012， 27（5）：437-442.

[3] 何苑， 郝梦岩. 基于百度地图的移动公交查询系统的设计与实现[J]. 山西电子技术， 2015（5）：45-47.

[4] 程璐瑶， 马宏琳. 城市公交线路信息查询系统的设计与实现[J]. 科技创新与应用， 2017（27）：110-111.

[5] 王進. 实时公交查询系统的优化设计和实现[D]. 北京： 北京邮电大学， 2013： 32-38.

[6] 罗在文. 基于移动智能平台的公交查询系统[D]. 重庆： 电子科技大学， 2015.

[7] 刘茂华， 韩卯， 王岩， 等. 移动GIS公交查询系统的实现分析[J]. 辽宁工程技术大学学报：自然科学版， 2015（3）.

[8] 石岩.公交车自助线路查询系统的开发与测试[D]. 北京： 北京邮电大学， 2010.

[9] 陶佩枫. 城市公交查询系统的设计与实现[D]. 长沙： 中南大学， 2008.

[10] 鲍江宏， 关毅璋. 基于矩阵运算的公交查询高效算法[J]. 计算机工程与应用， 2008， 44（10）：198-200.endprint