公交换乘算法.docx

《公交换乘算法.docx》由会员分享，可在线阅读，更多相关《公交换乘算法.docx（7页珍藏版）》请在三一办公上搜索。

1、公交换乘算法三个表： 1，站点表stop(stop_id,stop_name) 2，路线表line(line_id,line_name) 3，路线站点表(点线路关系表)linestops( line_id, stop_id, seq )此处的seq指某站点在某线路中的顺序。 现在分析算法： 1，直达线路 首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2 然后查询 select line_id from (select line_id from linestops where stop_id = id1) A, (select line_id from linestops wh

2、ere stop_id = id2) B where A.line_id = B.line_id 即得到可直达的线路列表 2,一次换乘 首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2 然后搜寻两个站点通过直达方式各自能够到达的站点集合，最后他们的交集就是我们所需要的换乘站点。 select stop_id from ( select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id = id1) )A, ( select distinct

3、 stop_id from linestops where line_id in (select line_id from linestops where stop_id = id2) )B where A.stop_id= B.stop_id 得到换乘站后，剩下的就是显示能够到达换乘站的两边线路，这通过前面的直达查询即可。 3，二次换乘 首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2 算法的中心思想是：站点1能够通过直达到达的所有站点集合A，站点2能够通过直达到达的所有站点集合B，A和B之间有直达的线路。 一步一步来： 站点1能够通过直达到达的所有站点集合A： selec

4、t distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id = id1) 站点2能够通过直达到达的所有站点集合B： select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id = id2) 而直达的查询是 select line_id from (select line_id from linestops where sto

5、p_id = id1) C, (select line_id from linestops where stop_id = id2) D where C.line_id = D.line_id 我们把=id1和=id2换成 in (select .)A 和 in (select .)B 这样最后我们的查询是 select line_id from (select distinct line_id from linestops where stop_id in ) C, (select distinct line_id from linestops where stop_id in ) D wh

6、ere C.line_id = D.line_id 其中是 ，对列举的的每一条假设命名为X线，下一步就是找出可以从站点1到达X任意一个站点的直达线路、和可以从站点2到达X任意一个站点的直达线路即可。 那么与前面的算法相似，我们在站点1所有能够到达的站点中去寻找和线路X相交的站点，然后再去找这两个点的线路 select stop_id from (select distinct stop_id from linestops where line_id in (select line_id from linestops where stop_id = id1)A, (select stop_id

7、from linestops where line_id = X ) B where A.stop_id = B.stop_id 找到站点了，下面就是根据已经解决的直达查询找线路了。 站点2类似。 以上的算法有一个优点，全部是sql完成搜寻，所以asp代码只需寥寥几行循环而已。 但是缺点是：慢,毕竟可能涉及了数百次sql查询。而且只是用最简单的sql方法去算出所有可以换乘的方案，不涉及最优/最短的算法。如果是最短路径，那得用特殊结构和算法。 另外: 根据出行者输入的起点和终点，确定出行要选择的起始公交站点A和目的公交站点B。搜索数据库，查询站点A和站点B之间是否有相同的车经过，如果有一条或几条

8、直达线路，通过比较选择距离最短的公交线路推荐给出行者。如果没有，则计算站点A和站点B之间有没有一个公共站点C，从站点C可以换乘到达站点B。这就有两种情况：(1)如果有，属于一次换乘。计算站点A和公共站点C之间有没有相同的公交车经过并存入集合X；同样，计算站点B和公共站点C之间有没有相同的公交车经过并存入集合Y。将这两个集合比较后就可以得到从站点A经过公共站点C到达站点B的公交线路，在这些线路中进行比较，选择距离最短的推荐给出行者。如果没有公共站点C，就出现了要换乘两次的情况。将经过站点A的每条公交线路的所有站点存入集合O；同样，经过站点B的每条线路的所有站点存入集合P。比较这两个集合，先乘经过

9、站点A的某一路车到达某一站点D，计算站点D与站点B之间有没有公共站点E,如果有则站点D、E为换乘站点。这种方案可能有多种，比较选择距离最短的推荐给出行者。如果不存在公共站点E，说明经过两次换乘无法从站点A到达站点B，停止搜索计算。 公交出行最优路线具体算法： 1） 输入起始站点A和目的站点B； 2） 搜索系统数据库，经过起始站点A的公交线路存为X(i)(i=1,2,3,m,m为正整数)，经过目的站点B的公交线路存为Y(j)(j=1,2,3,n,.n为正整数)； 3） 判断是否有X(i)=Y(j)，将满足条件的存入Z。若Z1，则该条公交线路X(i)即Y(j)为从站点A到站点B的直达最优线路，输出

10、结果并结束运算。Z1，计算Z中各条线路的距离，选择一条距离最短的线路，输出结果并结束运算； 4） 搜索系统数据库，公交线路X(i)所包含的站点存为O(i,u)(u=1,2,3,g,g为正整数)公交线路Y(j)所包含的站点存为P(j,v)(v=1,2,3,h,h为正整数)； 5） 判断是否有O(i,u)= P(j,v)，将满足条件的存入W。若W1，则站点O(i,u)即P(j,v)为从站点A到站点B的一次换乘站点，公交线路X(i)，Y(j)为换乘一次的最优路线，输出结果并结束运算。若W1，分别计算每条换乘路线的距离，选择一条距离最短的线路，输出结果并结束运算； 6） 搜索系统数据库，经过站点O(i

11、,u)的公交线路存为R(k)(k=1,2,3,p,p为正整数)，公交线路R(k)所包含的站点存为G(k,t)(t=1,2,3,q,q为正整数)； 7）判断是否有G(k,t)=P(j,v)，将满足条件的存入S。若S1，则站点G(k,t)即P(j,v)为从站点A到站点B的二次换乘站点，公交线路X (i)，R(k)，Y(j)为换乘二次的最优路线，输出结果并结束运算。若S1，分别计算每条换乘二次的路线距离，选择一条距离最短的线路，输出结果并结束运算； 8） 以上步骤没有找到合适的公交线路,输出“没有找到换乘次数不超过两次的最优公交线路”，结束运算。 本文讨论的公交出行最优路线算法，主要是以距离为标准。

12、在得出了换乘方案之后，可以进一步考虑时间因素，从而找到更具优胜性的换乘方案，这有待进行进一步的探讨、研究。 一、公交换乘问题的算法分为两个步骤： 1、构造并求解换乘矩阵，获得公交换乘方案(即从起点到终点最少换乘次数，及换乘站点)。 有三种实现形式： 、求得所有节点T矩阵，两个节点直达设为1，两个节点不通或需要换乘设为0；参见公共交通系统最佳路径算法 求得所有线路的T矩阵，两条线路相交设为1，两个线路不相交设为0；参见基于邻接矩阵的公交换乘算法的研究(注该算法属于理想化算法) 通过上述第2个步骤缩小范围，然后用第一个步骤求得精确结果 2、根据最少换乘次数，缩小求解范围，求解起始站点与目标站点间的

13、最短路径，进而得到最佳路径。 最短路径获得有以下几种形式： 、最简单的实现方法：如果上面1的最少换乘次数、换乘站点都能求解出来，只需要查询换乘次数最少的情况下，所有可能的路径中站点数最少的线路即为所求(前提，假设所有站点之间的距离大致相等)； 、如果上面1只求出来最少换乘次数，这时需要用算法求最短路径，常用的方法是改进Dijkstra算法，也就是在Diskstra算法中增加了一条判断最少换乘算法的一项； 、在游戏设计程序中，经常要涉及到最短路径的上述，最常采用的算法是A*算法，参见游戏地图最短路径搜索设计与实现和A算法 、K(=3)条渐次短路径搜索算法，这种算法国外用的比较多，由于该算法比较麻

14、烦，国内研究不太多，参见K(3)条渐次短路径搜索算法的研究、一种新的Kth最短路径搜索算法和城市轨道交通换乘票务清分模型的研究(硕士论文) 、蚂蚁算法，参见一种仿Dijkstra的蚂蚁算法 其中，步骤中都需要依靠最少换乘次数来达到降低复杂度的目的。 二、上述算法如能得到很好的实现，需要建立一个好的数据结构 1、数据存储形式 我曾问过两个实际搞过这方面的人，一个人采用数组来存储，另外一个所采用链表与数组相结合的方式(即长链表采用数组，其它采用链表的方式)，其实，之所以有上述两个存储形式，主要是因为这两个人算法中侧重面不同，前一个侧重实现最少换乘次数，后一个则侧重最短路径的实现。 2、数据结构存储

15、，可参考城市公交网络出行路径选择的计算机算法研究、基于GIS的标准公交基础信息系统基于GIS的公交乘客出行路径选择模型，考虑到公交换乘，所以通常情况下，把相近的站点(站点名一样但地理位置不同的、站点名不一样但地理位置很接近的)作为公交网络拓扑结构中一个节点。 3、两个节点之间弧段权值的选取(计算最短路径需要)：通常情况下，用两个节点之间的距离代替，但也有人用公交车在这两个节点之间的速度或行车时间来作为权值。下图是沈阳公交网给出来的环路车参数，根据该参数和两个站点之间的距离可以求出站点之间的行车时间(正常)。当然因素考虑的越齐全，越人性化，但是程序上就增加了很多难度， 比如：考虑“等车时间、站点距离、线路的热度(通往商业区)、时间(上班高峰期等)”等因素，这些因素都很难量化，所以，通常情况下，最简单的方法用距离来作为两个节点之间弧段的权值。