论文导读：采用了了基于n次公交换乘的算法。基于换乘次数最少的最优路径算法——n次公交换乘算法是比较符合人们出门时选择公交线路时的实际要求的。最优路径，公交乘换分析的算法设计与实现。
关键词：n次公交换乘，最优路径
1 引言
目前，公交换乘算法大多是以“空间距离”最短作为第一考虑要素，如Dijkstra算法，遗传算法，A*算法和燃烧算法等算法，这些算法不适合公交网络的特点和人们在选择公交乘车方案时往往把公交换乘次数最为第一考虑要素的实际情况，本论文在分析和总结公交站点、公交线路等公交数据的特点基础之上，采用了了基于n次公交换乘的算法，使系统更方便，更好的满足了生活中人们的实际需求和提高了查询的效率。
2 公交乘换数据分析与抽象
2.1 公交数据的分析
数据是GIS的核心部分，数据的组合结构的设计决定了系统功能实现的程度。
①公交数据的种类.公交数据简单的可以分为两类：公交数据主要有公交站点、公交线路、以及公交路段等数据组成。论文参考，最优路径。
②公交站点、线路分析.这里为了讨论方便，对公交站点、线路都做简单的处理。默认公交站点唯一，并不存在站点同名等。默认公交线路为完全的单向线路，不存在双线，单双线结合，单环行线和双环行线等。
2.2 公交数据的抽象
同一公交线路两个方向上的同名站点的抽象在同一公交线路上的同一个站点，还有其他的一些较复杂的情况都抽象成简单的情况。
3 公交乘换算法设计
对于公交换乘的算法，很多学者都进行了一些研究，得出了最优的路线查询，但对于最优路线有着不同的理解：基于最短路径的（如:Dijkstra算法、遗传算法、A*算法和燃烧算法等），还有部分算法是基于换乘时间最少，所用费用最少，换乘次数等。论文参考，最优路径。论文参考，最优路径。但对公交乘客的心理调查表明:在公交换乘方案的选取上，首先要考虑的因素是到达目的地的换乘次数要最少，其次才是要求路径最短。因此，基于最短路径的的公交换乘算法并不能满足实际的需要。在目前的公交换乘算法中，基于换乘次数最少的最优路径算法——n次公交换乘算法是比较符合人们出门时选择公交线路时的实际要求的。
根据人们的出行习惯以换乘次数最少为约束条件进行设计基于换乘次数最少的最优路径算法——n次公交换乘算法描述。
整个最少换乘算法的思想是一个递归的过程，从搜索经过起点站或目的站点的线路开始,由线路查找该线路经过的所有站点,再从这些站点查找经过它们的所有线路,不断迭代,直至找到终点站为止。算法的描述如下:
步骤1 输入乘车的起始站点和目的站点；
步骤2 对起始站点A进行站点所在公交线路搜索，得到线路集合LA, 同时对目的站点所在公交线路进行搜索，得到线路集合LB；
步骤3 判断交集Result=LA∩LB：如果Result! =null，则Result即为从A站点到B站点的直达线路，输出结果并结束运算；
步骤4 如果Result==null，将LA中各线路中A站点以后所有站点不重复地加入集合UA，将集合内每个站点作为起始站点，B作为目的站点，重新按照步骤2、3进行搜索；
步骤5 如果Result!=null，则得到一次换乘的方案，输出结果并结束运算；
步骤6 如果Result==null，则重复步骤4，依次进行。设定换乘次数的上界N，然后以不大于N次换乘的方案得到可行路径。当换乘次数超过N时，Result仍然为null，则表示从站点A没有可到达目的站点B的公交方案，算法结束。论文参考，最优路径。本算法的主要思想可由图1表达：
图1 公交换乘算法流程图
4 公交乘换算法的实现
本公交换乘算法的实现过程为：输入所要查询的起始站点A和结束站点B，首先，查询站点A和站点B之间是是否有直达线路，如有则返回直达线路并退出查询；如过A、B之间没有直达线路，返回站点A能够直达的站点集合S，接着判断集合S中是否有站点C能够直达B，如存在站点C能够直达B则返回站点C并退出查询，如果不存在站点能够直达B，接着查询集合S中的站点C能够直达的站点集合S1，依次递归，直到存在换乘方案使站点A能够到达站点B或达到最大换乘次数是退出查询。论文参考，最优路径。
5 结语
本算法从分析，设计到实现的过程中，是以到达目的地的换乘次数要最少为第一原则，路径最短为第二原则，利用n次公交换乘，进行算法的描述和设计，全面阐述了公交乘换算法的原理、特点，以及公交乘换的研究现状，同时结合人们的出行习惯，总结了公交乘换算法的研究方式，实现了n次公交乘换算法。论文参考，最优路径。本文研究了简化情况下的公交乘换算法，在现实复杂其情况下的公交乘换算法则更加复杂，例如考虑单双线问题等，尚有很多问题值得我们去探索和研究。
参考文献
[1]尹志华,罗小龙,刘少华.荆州电子地图公交查询算法与分析[J]，测绘与空间地理信息,2008,31(1):141-143.
[2]邵燕林,许晓宏,郑爱玲.公交乘换分析的数据库设计与算法实现[J].计算机时代,2004,(3):16~19.
|
