一种基于区域规划换乘点查找的公交换乘方案算法

王杉

摘要：该算法针对城市公交路网的特点，充分利用城市公交基础数据库，基于对城市公交区域规划，查找经行起终站点的公交线路的换乘点，根据换乘点类型和数量进行换乘方案的计算，按优化规则换乘方案的优先权值后获得最优方案。在很大程度上降低了公交换乘算法的时间复杂度，并提高了方案的准确率。

关键词：公交换乘；算法研究

中图分类号：TP311文献标识码：A

1 绪论

公交乘车方案也叫公交换乘方案，主要目的是为用户提供从甲地到乙地如何乘坐公交车的方案，给用户出行带来方便。一个城市的公交线路网是一个典型的图结构，公交站点作为图的结点，站点与站点之间有多条线路相联系。从甲地到乙地的公交换乘在图结构中可描述为两结点间最短路径的查找，其典型算法为求取图中最短路径的Dijikstra算法和Floyd算法。此类算法及其改进算法都常被用于公交换乘方案的求取。但是，Dijikstra算法和Floyd算法也存在局限性，当问题规模较大时，算法循环及穷举次数较多，其算法的时间复杂度高，将会降低查询的效率。同时，求取的路径虽然是最短路径，但有可能会产生多次公交的换乘，这在实际生活中是完全不适用的。[1][2]

因此，以昆明市为例，经过对城市公交路网的分析，认为大多数中型规模以上的城市在城市公交路网的建设上都具备较好的规模，公交线路覆盖率较高，在主城区公交路网辐射范围内，90%以上的任意两个站点，最多只需一次换乘即可到达。能保证主城区范围内任意站点最多两次换乘可到达。

考虑以上两个因素，提出一种基于区域规划换乘点查找的公交换乘方案算法，基于城市公交路网的特点，对路网数据进行分析和整理，实现了较为快速的公交换乘方案查询。

2 算法思路

设A点为起始点，B点为终到点，A点和B点均有若干线路经过。经过A点的线路设为LA={La1、La2、……LaN}，经过B点的线路设为LB={Lb1、Lb2、……LbN}，且有La∈LA，Lb∈LB，则A点到达B点的路径有以下三种情况：

① La=Lb，即La与Lb为同一条线路，则表示A点到B点为一线到达，不需要换乘。

② La≠Lb，但La和Lb有交点，即La和Lb至少存在一个相同的经过站点F，此站点即为“换乘点”，那么A点经过La到达F点，再经过Lb到达B点。

③ La和Lb之间没有交点，即不能通过一次换乘使A点到达B点，那么换乘点数量将会大于等于二。基于实际情况，若换乘点数量大于二，说明该路程较复杂，需要进行2次以上的换乘，总乘坐线路数会在4趟以上，已不适合乘坐公交车，通常建议选择其他交通方式。因此这里只考虑换乘点数量等于二的情况，即存在C点和D点和线路Lc，并使A点能经过La到达C点，在C点经过Lc到达D点，再从D点经过Lb到达B点。

A点到达B点的路径上所有经过的站点，计为方案共经站点数PassCount，作为方案性能判断的主要标准。最终的方案性能将由换乘点数量、共经站点数、换乘点权值、线路权值按规则进行计算。一般情况下，换乘点数和共经站点数少的方案为较优方案。

3 按区域规划换乘点

通常在中大型城市的建设过程中，城市都会被划分为区，每个区都会有相应路网的规划特点。同时，公交线路的设计与运营也是符合区划与路网特点的。以昆明市为例，城市区划与公交线路有较鲜明的特征，通过对昆明市300条公交线路及2000个站点进行数据分析，能得出以下几点结论：

·公交运营线路有区域性，每一条线路都可以分析出其行驶的主要区域。按公交路网的运行区划昆明市可划分为9个区域。为：北市区片区（北区）、东站片区（东区）、滇池路片区（南区1）、关上片区（南区2）、梁家河片区（西区1）、眠山片区（西区2）、市中心1区、市中心2区、呈贡新区。

·每一个区域都有称为“公交枢纽点”的站点，这些站点的特点是停靠或行经的线路较多，甚至有个别站点行经了该区域的所有线路。比较典型的例如：黄土坡站、北市区公交枢纽站、金马坊站、小西门站、东站站、昆明站站、潘家湾站、小菜园立交站等。

·如果在枢纽点进行换乘时，将会有较多的线路进行选择，能提供更为优化的换乘方案。

因此在本算法中，把公交线路按区域规划，同时在查找换乘点时对枢纽站进行优先取权计算，可快速地得到换乘方案，并能做到方案的最优性。

4 算法实现

根据算法思路，该算法实现换乘方案计算的核心就在于对换乘点的查找，根据起终站点及经行的线路进行分析，然后判断换乘点数量，并根据换乘点数量进行换乘方案的计算，最后按优化规则计算换乘方案的优先权值，排序后可获得最优方案。

Step1.確定查询的起始站点和终到站点（如果客户端提交的是“地点——地点”，那么通过地点信息查询获得地点周边的站点，再把这些站点作为查询的起始站点和终到站点）。声明QueryStation类型的起始站点对象StartSat和终到站点对象EndSat

Step2.获得行经起点的线路集合QueryLine[]StartQl和行经终点的线路集合QueryLine[]EndQl，对这两个线路对象数组进行遍历，判断线路的换乘点数量

for（int i = 0； i < StartQl.Length； i++）

{

for（intj = 0； j < EndQl.Length； j++）

{

if（StartQl[i]== EndQl[j]）

{换乘点数量为0，一线直达无需要换乘，方案最优，权值为1×PassCount+线路权值}

else

{查找换乘点，声明QueryCrossSatation对象，请求getCrossSat（）方法，计算换乘点数量}

Step3.若換乘点数量大于0，查找换乘点并计算换乘点数量。首先确定行经起点的线路和行经终点的线路的划分区域，按区域查找该区域的枢纽站点S，如果行经起点的线路A和行经终点的线路B均通过了该枢纽站点，则换乘点数量为1，需乘线路A在枢纽站点换乘线路B，通过一次换乘到达目的地，此时的方案权值为2×PassCount+线路权值。

Step4.若在上一步中行经起点的线路A和行经终点的线路B没有共同经过任何站点，也即两条线路无交点，那么意味着起点和终点间将需要进行多次换乘，换乘点数量大于1。首先首先确定行经起点的线路A和行经终点的线路B的划分区域，分别查找区域内的线路A经过的枢纽站点Sa和线路B经过的枢纽站点Sb。然后再确定枢纽站点Sa与枢纽站点Sb之间的线路C，若C存在，那么方案为在起点乘线路A到达站点Sa，换乘线路C到达站点Sb，再换乘线路B到达终点，此时换乘点数量为2，方案权值为3×PassCount+线路权值。若线路C不存在，则表示起点至终点需要经过3次以上的换乘才能到达，已不适合选择共交车方式，查询返回方案无法确定的消息，客户端会建议用户选择其他的交通出行方式。

Step5.进行换乘点查找并获得方案后，形成方案集合，以方案权值对方案集合进行由小到大的排序，并顺序输出，形成按最优排序的方案。

5 结论与示例

该算法被应用于“昆明市智能公交项目”中，为系统提供了公交换乘方案的查询。经过三个月的系统试运行，以短信、网页、APP等方式完成了近14000次公交换乘查询，得到有效结果的查询比例为98.7%，查询的平均响应时间在一秒以内，用户反应良好。

以下示例展示了两类有效的公交换乘查询，得到了准确的结果。

①查询“南屏步行街”到“昆明世博园”：

·获得“南屏步行街”应选择的站点“南屏街东口”，“昆明世博园”应选择的站点“世博园”；

·行经“南屏街东口”的线路有71路、108路、118路，行经“世博园”的线路有47、69、71、95、182、194、A1等线路。

·其中有相同路线71路，因此“南屏街东口”到“世博园”可一线直达，无需任何换乘，此为最优方案：“在“南屏街东口”站乘坐<71路>（回程）至“世博园”站。”

②查询“南屏步行街”到“昆医附二院”：

·获得“南屏步行街”应选择的站点“南屏街西口”，“昆医附二院”应选择的站点“西园路口（昆瑞路）”；

·行经“南屏街西口”的线路有10路、82路、84路，行经“西园路口（昆瑞路）”的线路有26、55、90、106、113、127路。

·其中无相同路线，需要换乘，确定以上线路的区域，并查找区域内的枢纽站，得到结果“小西门”站、“黄土坡”站等。

·通过计算发现10路和26路均经行“小西门”站，因此选择“小西门”站作为换乘点，得到最优方案：“在‘南屏街西口站乘坐<10路>（去程）至‘小西门站，换乘<26路>（回程）至‘西园路口（昆瑞路）站。”

以上的示例是基于昆明市的公交路网数据库，如果对其他城市的公交路网数据进行分析与整理，本算法也可适用于其他类似大中型城市的公交换乘方案查询。

参考文献：

[1]韩慧玲，胡红萍.公交换乘最短路径算法研究[J].硅谷，2012（4）：9192.

[2]高岚.一种改进的最短路径算法在公交查询系统中的应用研究[J].科技视界，2015（25）：33.