Abstract: Location-based social networks have generated a mass of data that can reflect user’s preference and the regularity of popular routes. These data have provided a new mode in searching travel route. The existing research on group travel route search usually aggregates user’s preference and then performs the search by using individual user route recommendation algorithm. In real life, when group users browse a global route, individual user wants to select different attractions in the local area of attractions in the route. Based on this requirement, this paper proposes the problem of local distributed group travel route search with the goal of getting a travel route which has local distributed POI (point of interest) and can make high satisfaction for the overall group. The search finds the optimal route using transfer graph which generated by the check-in data. In order to improve the efficiency, this paper proposes a double-hierarchy transfer graph generated with the popularity and metastasis of POI, and achieves hierarchical query. Designing an optimization algorithm based on branch and bound search strategy further improves the searching efficiency by using the controlled relationship between nodes. Using check-in data sets from Gowalla and Foursquare social networking websites, this paper evaluates the proposed algorithms with extensive experiments on the route profit and searching efficiency, and verifies the effectiveness of the algorithms.

Key words: route search, group recommendation, check-in data, location-based social networks

摘要： 基于位置的社交网络产生了大量反映用户喜好及路线流行规律的数据，为旅游路线搜索提供了新的模式。现有的群体旅游路线搜索通过将多个用户的偏好进行聚合，之后利用个体推荐算法进行搜索。现实生活中存在群体整体上浏览一条线路时，个体用户可以根据需要选择局部不同景点进行访问的需求。基于此需求，提出了群体用户局部分散式旅游路线搜索问题。该问题结合群体用户的个人偏好，发现一条带有局部分散POI（point of interest）的且群体收益最大的访问路线。采用签到数据，通过用户在POI间的转移情况生成POI转移关系图，在关系图上进行路线搜索。为了提高搜索效率，根据POI的流行度与转移关系设计了双层转移关系图，对POI进行了概化，实现了分级查询。设计了基于分支限界搜索策略的优化算法，利用结点间的控制关系进行剪枝，进一步提高了算法的搜索效率。利用Gowalla和Foursquare社交网站真实的签到数据集进行了充分实验，对搜索出的路线收益及算法的运行效率进行了对比，验证了所提出方法的有效性。

关键词: 路线搜索, 群体推荐, 签到数据, 基于位置的社交网络