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

摘要

Most of the existing research for point of interest route planning only consider the static properties of POI, how-ever, the congestion of the hot spots and users' discontent may greatly reduce the travel quality. In order to increase the tour-ists' 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 unneces-sary 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 diver-gence 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.%现有基于兴趣点(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%.