公交网络路径规划问题中的一种高效索引方法

摘要

TTL是在公交网络中求解最早到达路径、最晚出发路径和最短耗时路径的一种高效索引.TTL采用Time-dependent为核心算法构建索引,存在两个不足:a)大量的昂贵的出堆操作拖慢了建立索引的效率;b)所求得的路径具有较多的换乘次数.针对这两个不足,提出了一种基于旅程的索引TAIL.TAIL预先生成部分路径,在查询阶段通过匹配部分路径得到最优解,避免在原图上进行查询,提高效率.TAIL并不是基于图结构,而是以旅程为单位存储公交数据.在生成路径时,首先扫描路过起点的旅程,找到从起点直达的站点;然后扫描从直达站点出发的旅程,找到一次换乘可达的站点;如是这般,从可达站点出发扫描旅程,发现更多的可达站点.为了在早期找到最早到达路径,从而减少旅程的扫描量,TAIL并没有严格按照换乘次数的顺序扩展站点.这种方法避免了昂贵的堆操作,也保留了旅程的完整性.在真实数据集上测试表明,与TTL相比,TAIL有较短的建立索引的时间,生成的路径的换乘次数也较少.