基于路网的群体出行计划查询算法

来源：计算机应用杂志2015年第11期北京时间：

作者：朱海泉, 李文根, 张毅超, 关佶红

单位：同济大学 计算机科学与技术系, 上海 201804

摘要：群体出行计划(GTP)查询旨在为一组用户查找共同的活动地点(通常以兴趣点(PoI)表示)以达到整体的出行开销最小.当前,对群体出行计划查询的研究大多仅限于欧氏空间,然而人们真实的出行却受到道路网络的约束.针对该问题,提出了两个基于路网的群体出行计划查询算法NE-GTP和ER-GTP.其中,NE-GTP通过扩展每个用户所在的边,来迭代地找到这组用户感兴趣的PoI; ER-GTP则是利用R树索引和欧氏距离是路网距离的下界这一条件来快速搜索满足关键词条件的PoI.实验结果表明,ER-GTP方法在查询速度上总体要比NE-GTP快一个数量级左右; 而且,当数据量很大时,ER-GTP也有很好的可扩展性.

关键词：路网,欧氏空间,群体,兴趣点,群体出行计划查询

基金资助：国家自然科学基金资助项目(61373036).