申 静

(陕西理工学院数学与计算机科学学院，陕西 汉中 723000)

0 引言

随着人们生活水平的提高和城市化进程的推进，城市规模不断扩大，城市公交系统也越来越发达。这就使得公交线路互连交汇、错综复杂，给当地居民和外地游客的出行带来了诸多不便。为了解决如何获取足够的公交出行信息、如何最便捷地获得到达某一目的地的最佳乘车线路等问题，研究和开发一个便捷、快速、准确的公交查询系统迫在眉捷。公交查询系统性能的好坏是一个城市现代化进程的一个重要标志，所以研发操作便捷、快速、准确的城市公交查询系统具有非常重要的意义。

对于公交查询系统的开发和研究，前人已经做了大量的工作，但大多数城市公交路线查询系统存在以下几个方面的不足［1－4］。

①查询结果复杂多样但有效线路十分有限:大部分查询系统生成了复杂的查询结果，例举了很多可能的出行方案，但实际上有些换乘路线绕行了很多弯路，甚至是不可达的，这对查询者很不利。

②查询速度较慢:由于公交查询运算速度与换乘次数是呈几何级数关系增长的，所以公交查询系统普遍存在查询速度慢的问题，这就导致现有查询系统一般只提供两次以内的换乘查询结果。

③与实际的查询结果存在差距:大部分系统提供的填入式每站查询和罗列式选择查询方式不具备区域查询和模糊查询功能。

本文针对实际情况，按照居民的出行习惯，一般以换乘次数最少的公交线路为最优乘车方案，提出了一种最少换乘算法，并探讨了以最少换乘次数为目标的公交查询系统的实现方案。

1 算法的设计与分析

1.1 算法假设

根据居民实际出行乘车交通的习惯，排除环境的外界干扰因素，对算法作了以下假设［5－8］。

①相邻公汽站点之间的平均行驶时间不变，即若任意两站点si和sj之间的路程长度为Sij，公汽的平均行驶速度为vij，则其站点si和站点sj之间的平均行驶时间tij=Sij/vij保持不变。。

②交通情况良好，各种交通工具的换乘时间保持不变。

③公汽环形路线即公汽的始发站和终点站之间的站点与终点站到始发站之间的站点是对应相同的，且公汽从终点站到始发站回行时按原路返回。

④优先考虑出行方案的换乘次数，其次考虑路程和费用等因素。

⑤根据实际情况，两次以内换乘较合理，超过两次换乘不予考虑。

以上各假设兼顾了给居民生活带来便利和确保系统高效运行这两方面的需求，从而保证了算法的可行性和有效性。

1.2 算法的理论基础

根据公交网络本身所具有的连通性、节点性以及有向性等特点，把车站各站点抽象为点，各公交线路抽象为线，公交网络就可以转化为一个由站点和线段组成的有向连通图，记为G(V，E)，其中V、E分别为G的站点集合和线段集合，从而可以利用图论理论对网络换乘进行分析［1，9－10］。

考虑到人们的乘车心理，大部分人把转乘次数少作为首要因素，则公交换乘可以归结为寻求图中给定一个始点vi及终点vj之间的最短路径问题。

目前，关于最短路径搜索算法的研究成果有很多。其中，1959年Dijkstra提出的单源问题算法是使用最广的、适合拓扑网络中两节点间最短路径搜索的算法之一。它不仅能求解出从始点到终点的最短路径，而且最后得到的路径实际上也是始点到各顶点的最短路径。该算法能适应网络拓扑的变化，同时对系统的内存空间占用少，因而在计算机网络拓扑路径选择以及地理信息系统(geographic information system，GIS)中得到了广泛的应用［1，7－10］。

基于以上Dijkstra算法适应网络拓扑变化且占用系统空间较少的特点，系统中的最少换乘算法即以Dijkstra算法为理论基础［2－3］，查询系统通过关键字的匹配，查找出任意两个相连通站点之间的最短路径。站点查询的速度较理想，且路线以动态的方式显示，完全能够满足查询信息系统的实际需求。

1.3 算法实现

采用邻接矩阵M表示带权有向公交系统网络图G，以游客当前所在站点为出发点，记为S。在算法中，首先产生从S到S自身的路径，这条路径的长度为0，记为l=0;再依次产生从S到图G中其余站点的最短路径，并相互比较，找出其中最短路径，记为lmin;依此类推，产生图G中任意出发点si与可达的目标地sj之间的最短路径lmin(si，sj)，用初始换乘矩阵M0(即邻接矩阵)表示交通网络图G，交通网络模拟图如图1所示。

图1 交通网络模拟图Fig.1 Simulation diagram of the transport network

在交通网络模拟过程中，设置初始矩阵为M0。

在算法实现的过程中，还需考虑赋权问题，即在公交系统网络图G中，将任意站点si与sj之间的道路集合记为{Li，j}，其中最短路径为 lmin(si，sj)。考虑赋权因素，w［si，sj］表示查询站点 si到达目标站点 sj的最短加权路径。在算法描述中，用d［j］数组的每个分量表示。在寻求最短路径的同时，考虑赋权因素对换乘矩阵进行分析，即在一次选乘不成功的前提下，出行旅客就会考虑到换乘，这时对初始矩阵M0通过一定的变换规则进行变换。根据图1的交通网络情况，可得到经过一次换乘的矩阵M1;在一次换乘不成功的前提下，同理可得到经过两次换乘的矩阵M2;最终得到基于最少换乘算法的最短线路。各算法具体描述如下。

1.3.1 最短路径算法

最短路径算法的具体步骤如下。

① 初始状态 S={s0}，d［i］=w［s0，si］，vi∈V(G)。

② 选择 sk，使 d［k］=Min{d［i］|si∈V－ S，si∈V(G)}，则站点sk是目前求得的一条从站点s0出发的最短路径的终点，令S=S+{sk}。

③修改所有不在S中的站点的最短路径长度，即如果 d［sk］+w ［sk，si］＜ d［si］，则 d［si］=d［sk］+w［sk，si］。

④重复步骤②和③共(n－1)次，即可求得由查询站点到其他站点之间的最短路径。

1.3.2 最少换乘算法

最少换乘算法的具体步骤如下。

①在最短路径算法的基础上，设置初始矩阵为M0，并输入所有n个站点;对于任何两站点si、sj，如果这两站点之间可以直达，则 M0(i，j)=1;否则，M0(i，j)=0，计算出初始矩阵M0。

② 一次换乘矩阵M1:在M0中，如果M0(i，j)=1，则M1(i，j)=M0(i，j)，表示不需要换乘;如果 M1(i，j)=0，并且存在点 k，使得 M0(i，k)=1、M0(k，j)=1，则M1(i，j)=2，表示从站点 si到 sj需经过1 次换乘;否则，M1(i，j)=0，如此计算即可得1次换乘矩阵M1。

③ 二次换乘矩阵M2:在M1中，如果M1(i，j)=1或2，则 M2(i，j)=M1(i，j);如果 M2(i，j)=0，且存在点k，使得 M1(i，k)=1、M1(k，j)=2，则 M2(i，j)=3，表示从站点 si到 sj需经过两次换乘;否则，M2(i，j)=0。

④结合最短路径算法，在可达的最短路径的前提下，输出最少换乘路线Li，j;否则，转步骤⑤。

⑤无换乘路线，停止计算，输出相应的提示信息。

矩阵 M0、M1、M2的表达式如下。

以图1所示的交通网络模拟图为例，图1所对应的站点初始矩阵如式(1)中的 M0矩阵，其中 s1、s2、s3、s4、s5、s6代表矩阵的6行6列的行号和列号，其行列交汇处的值代表两个站点之间的直达信息。若M0为1，则说明两站点可以直达;若M0为0，则两个站点之间不可直达，需要换乘。根据最少换乘算法，对M0经过1次换乘所得的矩阵为M1，对M1再经过2次换乘所得矩阵为M2。

对式(1)中的矩阵元素可作如下解释，M0(s1，s2)=1，说明s1行和s2列相交汇处的值为1，代表s1和s2两站点之间可直达;而M0(s2，s3)=0，说明s2行和s3列相交汇处的值为0，代表s2和s3两站点不可直达。在M0中，所有不可直达的站点经一次换乘后成为矩阵M1，依据最少换乘算法，如 M0(s3，s1)=1，M0(s1，s2)=1，则M1(s2，s3)=2，说明s2和s3站点之间需要一次换乘。类似矩阵M2中有M2(s3，s4)=3，则说明在站点s3和s4之间要经过两次换乘才能到达。

2 查询系统的实现

根据上述基于最少换乘算法的公交模型，以汉中市的公交系统为实例进行试验，实现了汉中市公交线路查询系统。该系统能查询出该网络任意两公交点的换乘路线，如21路所经过的站点为:“北街口—莲湖路—北大商城—北门口—邮电大楼—火车站—三里村—石马坡”，23路所经过的站点为:“风景路—南门—卫校—钟楼—北街口—北大商城—北门口—陈家营—前进路—黄家塘”，若乘客所在的位置为21路的站点“莲湖路”，要乘车到目的地“前进路”站点，虽然21路不能直达，但通过系统的搜索匹配，23路可到达“前进路”站点，且23路和21路有相交汇的站点“北大商城”，则乘客可乘21路车到“北大商城”，再在“北大商城”站点处换乘23路到达“前进路”站点，即可到达乘车目的地。

试验结果表明，用户输入需要查询的公交线路，系统通过相应的线路路段中相应的字段或者车次号，获取该车次所经过的所有站点;也可以根据给出的一个站点，查询出经过该站点的所有公交车，从而为用户提供更多的公交信息。

在系统运行环境中，系统的数据流查询是用户通过各种不同的关键字向数据库传递查询请求。查询时，后台接收到用户发出的请求，系统根据用户的请求，以一定的策略在数据库中找出用户需要的信息进行反馈，从而获得所查车次的所有站点。以查询的结果为例，在车次查询界面输入要查询的车次102，根据系统所存储的路径情况，系统自动调出该车次所经的所有站点。若输入不同的站点，系统会输出所有包含该站点的路线信息，并在最少换乘算法的支持下，为用户提供中转查询，且尽可能地在可达目的地的最短路径的前提下获得换乘次数最少的路线。

由于系统数据模型以公交站点及站点间的线段为基础，当已有的公交路线需要更改或增加新的公交路线时，只需要对相应的公交站点和线段进行修改，而无需对整个数据库进行修改，因而系统具有很好的扩展性。系统的构造模型对于类似公交站点之间的出行方式也同样适用，因此系统具有很好的通用性。

3 结束语

根据实际生活中人们以最少换乘作为首要考虑因素，以Dijkstra算法为理论基础的最少换乘算法，有效地解决了公交查询系统中所遇到的问题，并通过试验验证了算法的科学性与正确性。在实现环境中，通过对复杂语句的设置支持模糊查询，以有利于对公交线路或站点不熟悉的乘客，使居民对城市公交信息的获得不单单局限于静态和单一的信息获取，同时还提供了动态的公交信息发布，为居民的出行提供了便利。针对大中型城市公交查询系统，一般应配置有一台比较大型的服务器存放数据，以提供更为详尽多样的查询方式，并利用合理的线路评价机制得出最优线路。日后，这方面的工作还有待更进一步的研究。

［1］常青.车辆导航定位方法及应用［M］.北京:机械工业出版社，2005.

［2］倪华芳.GIS系统及其在化工企业管理中的应用［J］.自动化仪表，2005，26(3):64－66.

［3］Yang Yahong，Gao Jingchang.Application of design patterns for GIS platform software［J］.Journal of Jilin University:InformationScience Edition，2003，21(2):153－155.

［4］刘洪玮，石红瑞.遗传算法在汽车巡航控制系统中的应用［J］.自动化仪表，2009，30(11):48－50.

［5］申静，姚军财.基于多Agent协商的决策支持系统的研究［J］.微电子学与计算机，2009，26(5):76－79.

［6］于小平，杨国东，王凤艳，等.城市公交查询系统的设计与实现［J］.吉林大学学报:信息科学版，2005，23(6):675－678.

［7］张延林，佟德军.BP神经网络的汽车故障诊断系统［J］.自动化仪表，2009，30(4):11－13.

［8］陈箫枫，蔡秀云，唐德强.最短路径算法分析及其在公交查询的应用［J］.工程图学学报，2001(3):20－24，788－793.

［9］梁虹，袁小群，刘蕊.一种新的公交数据模型与公交查询系统实现［J］.计算机工程与应用，2007，43(3):234－238.

［10］李响，张睿智.公交查询系统的数学模型［J］.黑龙江大学自然科学学报，2008，25(4):554－557.