摘  要: 目前中国正处于快速城市化阶段，城市人口快速增长，城市范围不断扩展，公交网络不断延伸，线路愈加密集，以往一直沿用的获取公交线路换乘方案的传统算法，逐渐显露出效率较低的尴尬，同时对换乘中转次数的限制，也很难保证得到可行的乘车方案。随着今后地铁、轻轨等乘车方式的普及，以及城市居民出行半径的扩大，这些问题将更加明显。为此，以对城市居民生活更具实用性的最少换乘次数算法为基础，提出站点合并为站组的理念，设计出可行的公交换乘算法优化方案，以改善传统方案的不足，提高计算效率。

关键词: 公交换乘; 算法优化; 公交系统; 站点; 站组

 

       随着城市化水平的提高，城市规模的不断扩大，城市的流动人口与机动车辆数目也不断增长。复杂的道路系统和出行选择，给千万的城市居民的日常生活带来不便和烦恼，也阻碍了城市社会经济的发展。优先发展公共交通已经被多数国家作为解决大、中城市交通问题的最佳策略，是城市可持续发展的保障，在国内各大城市建立高效率、功能强的城市公交系统势在必行。

 

      公交换乘系统是公交系统中一个必不可少的子系统，它的建设是现代公共交通系统中实现各种城市公共交通方式协调运营的有力保证。公交换乘子系统的核心是换乘算法，目前采用比较广泛的算法有 Dijkstra 算法，最少换乘次数算法^{［1 －2］}，以及相关的改进算法等。虽然这些算法都已经投入到了实际的使用当中，但是或多或少都有其局限性，传统算法随着换乘次数的增加，扫描的站点次数爆炸式的增加，因此很多公交系统不得不限制换乘次数最大为一次。算法的瓶颈，是由于一个站点可能同时经过多条线路，每条线路都能提供数十甚至上百个能够直达的站点，也就意味着每增加一次换乘次数，计算次数就扩大几十上百倍。因此，要优化算法提高计算效率，关键就在于抑制每次换乘次数添加时直达站点的个数。当前主流的公共公交查询网站，如 8684 公交网络查询系统、坐车网等，采用的算法都是最少换乘法。本文以公交管理系统 GIS 软件为平台，以目前运用最为广泛的最少换乘次数算法为基础，从减少每次换乘计算的可选择换乘站点个数这个思路出发提出优化方案。最少换乘次数算法的设计流程，如图 1 所示。

      要减少每个站点能够直达的站点个数，首先是能否缩减每条公交线路的实际有效站点个数。如果能够实现这个构想，那么每个站点所能直达的有效站点也将减少。由于算法的计算次数是直达站点个数的指数函数，减少底数对于效率的提高有显著作用，针对这个思路，本文提出站点组合的概念，来减少这个算法所关注的站点数目。假设一个简单的公交线路网络，如图2 所示。图中有 3 条公交线路( 都是双向来回，即在某些城市公交管理系统中，实际每条线路的存储都是分为上行和下行两条线路，共 6 条) 以及 A 至 L 12 个公交站点，其中以黑点表示的站点代表仅被一条线路经过，以短线表示的站点代表被多条线路经过，即在该站点可以换乘其他公交线路。之后考虑如何将该线路分组，以简化网络。

      按照前文的思路，应对几个站点进行合并分组。分组的实际意义就在于，将几个站点抽象成为一个站组，并且使站组这个概念成为公交系统研究中的“站点”。为保证站组能够正确的替代原系统中的单个站点，使得逻辑上意义相同，让算法得到正确的结果，对站点分组应遵循两个原则:

      1) 对系统作如下计算，随机从系统网络中的某个站点出发，到达站组的任意一个站点，所得到的所有公交换乘线路方案，在只改变最后一条乘车线路的经历站点个数但不改变所有乘车线路先后顺序和中间换乘点的情况下，也同样可以到达站组中其他的所有站点。

      2) 站组中的公交站点必须被所有经过它们的线路依次串联，且任意一条线路在经过该站组所有站点的过程中，中间不会经过该站组以外的其他站点，保证站组中的所有站点依次相邻。

      在遵循上述两项原则的前提下，对图 2 所描述的公交网络进行站点合并分组。如图 3 所示，分为 A 至 F 共 6 个组。

      从图 3 中可以很直观的看出，从同一个组内的任意站点出发，到同一个组外目的站点的公交线路相同，比如从组 A 出发到站点 H; 从同一个起始站点出发到同一个组内任意站点的公交线路也相同，比如从站点 E 出发到组 F; 而对于换乘而言，只要在组内某一站点可以换乘的线路，在同组其他站点同样可以换乘，比如在组 E 中由线路 1 换乘线路 2 或线路 3。由此可以说明，站组可以从逻辑上代替原系统中真实站点所表示的意义。当然，除上述的可能性之外，还有一种状况在上述中没有讨论到，即起点和终点同在一个站组的情况。在这种情况下，由之前分组的原则，能够保证同一站组内的站点之间只要有线路连接就可以互相直达，其运算也就很简单，可直接通过站组所经的线路得知乘车线路。

      从分组前后的对比来看，系统中分析的对象由 12 个站点变为 6 个站组。在真实情况中，对于很多郊区线路，首尾的站点经常是仅有该线路经过。例如，图 3 中线路 3 经过的组 C 和组 D，而且这一串线路中站点可能多达 10 个，还有城市的某些主干道，所有的公交车在这一条路上行经时所经站点由于道路特征的影响，也如组 E 的状况一样，形成一段共同路径。综合考虑以上情况，对站点分组之后，计算对象的数量可减少数倍，作为指数函数的底数而言，优化的效果是很明显的。

      算法的优化过程实际就是将原来关注的站点转变为新的站组数据。所有公交线路经过的逻辑单位为站组，计算扫描站点能够直达的考察目标为站组集合。以图 1，图 2 所表示的公交网络为例说明数据的存储和算法的具体流程。

      整个网络由 12 个站点和 3 条真实公交来回线路，即系统由6 条单向公交线路构成。在系统中录入站点和公交线路数据之后，系统将自动生成 6 个站组数据，记录站点、公交线路与站组的关系。最后是乘车站组线路关系数据。各个数据的详细记录信息，分别如表 1、表 2、表 3、表 4 所示。

      根据上述所建立的数据，就可以进行改进后的公交换乘的线路查询过程。对算法的修改，仅是将原算法中作为计算对象的站点数据替换成新生成的站组数据，得到换乘线路和换乘站所属的站组，并最终将站组转换成站点信息反馈给用户。具体计算过程，以从站点 K 到站点 E，站点 J 到站点 I 为例，详细说明优化后的计算步骤:

      1) 查询公交站点表，获得 K，E，J，I 所属的站组编号，得到 K属于组 F，组号为 6; E 属于组 C，组号为 3; J、I 同属于组 E，组号为 5。

      2) 判断起始站点是否属于同一组，如不同则转入下一步。判断结果 J、I 的组别相同，则根据相同组号 5 查询公交站组表中数据，根据数据中的组内站点序列所记录的站点编号顺序确定站组中 J 到 I 的方向属于顺序还是逆序，J、I 编号为 10、9，记录表示 E 组顺序为 9、10，因此得知应选择经过组 E 的逆序线路且两站之间仅间隔一站路。再根据逆序的结果选择停靠线路，得到“线路 1［下行］”、“线路 2［下行］”、“线路 3［下行］”3 条线路。计算结束，并返回结果: 从 J 到 I 可乘上述 3 条线路经 1 站到达。

      3) K 和 E 不属于同组。则将组 F 和组 C 的意义代替为 A站和 D 站，计算获得组别之间换乘的方案。获得的结果为从组F 到组 C，“线路 1［下行］”或“线路 2［下行］”经一个站组到达组 E，并在组 E 换乘“线路 3［下行］”经一个站组到达组 C。

      4) 将站组转换为现实意义的站点，并根据所行经的各个组别内的站点顺序和个数来获得整个线路的方向以及乘车间隔站点数。自此计算结束，最终得到结果: 从 K 到 E 可乘“线路1［下行］”( 或“线路 2［下行］”) 经 1 站到达站 J( 或经 2 站到达站I) ，再换乘线路“线路 3［下行］”经 3 站( 或两站) 到达。

      更新前换乘计算依据的单位个体为真实公交站点，某市真实公交站点总数为3 911个，而更新后所计算依据的单位个体为站组，依据上述算法所得站组总数为1 787个。计算过程中，优化前所要遍历查询的站点线路关系表数据记录为22 437个，优化后的站组线路关系表数据记录为9 622个。

      优化后的算法，相对传统的算法改进之处是有效的减少了每次换乘计算过程中所需考虑的中间换乘站点数，通过对系统的换乘查询功能优化前后对比，可以看出改进后的算法能够显著提高算法效率，并且随着换乘次数的增大，效率的提升幅度也随之增强。同时，对高换乘次数方案的高效优化，也能使传统的公交换乘查询过程中，由于换乘次数最大值设置得过小而无法获得换乘方案的可能性降低。