基于用户需求的景点路线利益规划算法  

Algorithm for scenario benefit route planning based on user's requests

作　　者：王楠[1,2,3] 周红磊 李金宝[1,2,3] 黎玲利 WANG Nan;ZHOU Honglei;LI Jinbao;LI Lingli(Key Laboratory of Database and Parallel Computing of Heilongjiang Province （Heilongjiang University）, Harbin 150080, China;School of Electronic Engineering, Heilongjiang University, Harbin 150080, China;School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China)

机构地区：[1]黑龙江省数据库与并行计算重点实验室(黑龙江大学),黑龙江哈尔滨150080 [2]黑龙江大学电子工程学院,黑龙江哈尔滨150080 [3]黑龙江大学计算机科学技术学院,黑龙江哈尔滨150080

出　　处：《通信学报》2018年第5期189-198,共10页Journal on Communications

基　　金：国家自然科学基金资助项目(No.61370222;No.61602159)~~

摘　　要：现有基于兴趣点(POI)路径规划的研究大部分只考虑POI的静态属性,而热门景点拥堵以及用户产生的不满意情绪会造成旅游质量大大下降。为了提升用户旅游的满意度,重点考虑了POI的动态属性,提出基于用户需求的景点路线利益规划算法。首先,设计了GM(1,1)马尔可夫景点人数预测算法,通过引入预测残差以及概率转移矩阵,使平均预测偏差比原GM(1,1)算法降低12.2%;其次,通过设计前向细化(FR)算法,在满足用户解决需求的前提下减少用户不必要的访问地点和时间,在相同的需求数下,前向细化算法的平均解决需求时间比TMT算法降低9.4%;最后,根据景点流行度、时间KL散度、地点访问次序以及路程时间等因素,提出了景点路线利益规划算法,在相同时间限制下景点路线利益算法平均拓展Rank 1-5的景点数量比Time_Based算法提高34.8%,比Rand_GA算法提高47.3%。Most of the existing research for point of interest route planning only consider the static properties of POI, however, the congestion of the hot spots and users＇ discontent may greatly reduce the travel quality. In order to increase the tourists＇ satisfaction, the dynamic attributes of POI was considered and a route planning algorithm based on user＇s requests was proposed. Firstly, Markov-GM（1,1） forecasting algorithm was designed to predict the number of people in each scenic spot. Markov-GM（1,1） could make the average predication error 12.2% lower than the GM（1,1） algorithm by introducing the predication residual. And then, the forward refinement（FR） algorithm was designed which could avoid visiting the unnecessary place and satisfy user＇s requests as well. The average solving time of forward refinement algorithm was 9.4% lower than TMT algorithm under the same amount of user＇s requests. Finally, based on the factors such as spot popularity, KL divergence of time, visiting order and distance et al, the scenic route profit planning algorithm which could make the number of Rank 1-5 spots 34.8% higher than Time_Based algorithm and 47.3% higher than Rand_GA algorithm.

关 键 词：兴趣点 景点利益 KL散度 路径规划 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]