最近在做基于Android的公交查询系统的过程中，遇到一个很棘手的问题：换乘算法效率低。在直达查询和一次换乘查询的时候，问题体现的还不是很明显，能够在1s之内查询出乘车方案，而当进行二次查询的时候，基本要等一两分钟才能查询出换乘方案，这对于公交查询系统是绝对无法容忍的。于是找了大量的关于公交换乘算法方面的论文和资料进行研究，发现大多治标不治本，没有从根本上解决公交换乘算法效率低下的问题。公交换乘算法主要有以下三种思路：
1)基于数据库的查询；
2)采用Dijkstra或者Floyd算法或者改进的Dijkstra算法；
3)基于矩阵的运算；
由于在做这个系统之前就想过这个问题，是采用Dijkstra算法、矩阵运算还是基于数据库的查询。仔细分析之后还是选择了基于数据库的查询，因为对于大中型城市的公交网络，Dijkstra算法和矩阵运算根本不适用，尤其还是基于Android系统的公交查询系统(离线查询系统)，举个例子，像成都市的公交网络系统有将近500条公交线路，5000个公交站点，如果采用矩阵运算或者Dijkstra算法的话，就只是直达矩阵就得有5000*5000=25000000个数据，若数据采用int类型保存，则该矩阵得占用25000000*4/(1024*1024*8)=12M的内存空间，这个数据对于移动设备来说想而知，是不可取的办法。因此最后采用了基于数据库查询的方案。
在我的数据库中有两张表：cnbusw(线路表),cnbus(站点线路表)
cnbusw的字段：
id：线路编号，busw：线路名称，shijian：起始站和起始时间描述；
cnbus的字段：
zhan:站点名，xid：对应的线路编号，pm：在该线路中的位置，kind：线路类型(去程or返程or环形路线)
后来发现在进行一次换乘查询的时候需要直达站点信息，因此添加了一个视图direct
direct的字段：
start：起始站，end：终点站，route：对应的线路编号，stopcount：两站之间的站点数
在数据库中进行测试了一下：
1)直达方案的话，直接在direct中进行查询：
比如下面一条sql查询语句:
select * from direct where start='磨子桥' and end='春熙路南口'
查询耗时：119.05ms
2)一次换乘查询方案，通过direct的自连接进行查询：
比如下面一条sql查询语句：
select s1.start as start,s1.route as route1,s1.end as zhuan,s2.route as route2, s2.end as end,s1.stopcount as count1,s2.stopcount as count2,(s1.stopcount+s2.stopcount) as stopcount from direct s1,direct s2 where s1.start='崔家店' and s2.end='磨子桥' and s1.end=s2.start and s1.route!=s2.route order by (s1.stopcount+s2.stopcount)
查询耗时：415.32ms
上述查询时间都在能够接受的范围之内，然后我很自然地按照上面的思路写出了三次换乘的sql查询语句，结果在查询时发现等了一分钟还没等出结果，并且sqlite可视化管理工具界面卡死了，这个很明显地告诉我二次换乘直接使用这样的sql语句是绝对不可行的，于是我想了一些办法，比如：两次换乘相当于是A->B->C->D，那么先查询经过站点D的线路中站点序号比D小的站点集合U，然后就相当于查询A到U集合中所有站点的一次换乘查询，这样就方便了，但是用sql语句查询了一下，一般U集合的大小都在400左右，然后要进行400次一次换乘查询，耗时400ms*400=160000ms=160s，怎么也得2分多钟，显然不可取。在陷入了这样的僵局之后，想了很久没想到办法，因为数据库里面的数据量很大，简单地对sql语句进行改进无法解决根本性问题。只有从数据库本身着手，于是想到了索引，以前上数据库课程的时候，老师提到过索引对于大量数据查询的时候效率提升的很明显，于是就尝试了一下，发现查询耗时一下减少了很多。在建立索引的过程中，原本想在视图上建立索引，发现似乎sqlite不支持在视图上创建索引，于是删除了direct视图，建立了direct直达表，在建立索引的时候，考虑是建立多列索引还是单列索引，分析一次换乘查询发现要将start，end，route这三列同时作为查询条件，并且要对stopcount进行排序，因此选择创建多列索引：
create index directindex on direct(start,end,route,stopcount)
在创建索引之后，重新将上面的一次换乘查询语句执行了一次，耗时：5.59ms，查询速度提升了将近80倍，然后又将直达查询语句执行了一次，耗时0.49ms，也明显提升了不少。然后按照一次换乘的思路写出了二次换乘的sql语句进行执行，
select s1.start as start,s1.xid as route1,s1.end as zhuan1,s2.xid as route2 , s2.end as zhuan2,s3.xid as route3,s3.end as end,s1.stopcount,s2.stopcount,s3.stopcount, (s1.stopcount+s2.stopcount+s3.stopcount) from direct s1,direct s2,direct s3 where s1.start='川大路黄河路口' and s3.end='春熙路南口' and s1.end=s2.start and s2.end=s3.start and s1.xid!=s2.xid and s2.xid!=s3.xid order by s1.stopcount+s2.stopcount+s3.stopcount
耗时411.15ms，很好地解决查询效率低下的问题，从这里可以看出，在数据量很大的情况，建立索引和没有索引的区别简直是天壤之别，适当地建立索引能够使查询速度提升很大，关于索引的相关问题准备在后面进行进一步学习和研究。
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
重庆分公司
重庆分公司
