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

王楠; 周红磊; 李金宝; 黎玲利

doi:10.11959/j.issn.1000-436x.2018089

您当前的位置：

首页 >

文章列表页 >

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

学术通信 | 更新时间：2024-06-05

- 基于用户需求的景点路线利益规划算法
- Algorithm for scenario benefit route planning based on user’s requests
- 通信学报 2018年39卷第5期页码：189-198
- 作者机构：
  
  1. 黑龙江省数据库与并行计算重点实验室（黑龙江大学），黑龙江哈尔滨 150080
  2. 黑龙江大学电子工程学院，黑龙江哈尔滨 150080
  3. 黑龙江大学计算机科学技术学院，黑龙江哈尔滨 150080
- 作者简介：
  
  [ "王楠（1980-），女，黑龙江哈尔滨人，黑龙江大学博士生，主要研究方向为数据挖掘、无线传感器网。" ]
  [ "周红磊（1992-），男，浙江金华人，黑龙江大学硕士生，主要研究方向为物联网。" ]
  [ "李金宝（1969-），男，黑龙江庆安人，博士，黑龙江大学教授、博士生导师，主要研究方向为无线传感器网络、社交网络、移动计算。" ]
  [ "黎玲利（1986-），女，四川广元人，博士，黑龙江大学副教授，主要研究方向为数据质量、大数据管理。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61370222);国家自然科学基金资助项目(61602159)
- DOI：10.11959/j.issn.1000-436x.2018089
  中图分类号： TP393
- 网络出版日期：2018-05，
  
  纸质出版日期：2018-05-25
- 稿件说明：
移动端阅览
王楠, 周红磊, 李金宝, 等. 基于用户需求的景点路线利益规划算法[J]. 通信学报, 2018,39(5):189-198.

Nan WANG, Honglei ZHOU, Jinbao LI, et al. Algorithm for scenario benefit route planning based on user’s requests[J]. Journal on communications, 2018, 39(5): 189-198.
王楠, 周红磊, 李金宝, 等. 基于用户需求的景点路线利益规划算法[J]. 通信学报, 2018,39(5):189-198. DOI： 10.11959/j.issn.1000-436x.2018089.

Nan WANG, Honglei ZHOU, Jinbao LI, et al. Algorithm for scenario benefit route planning based on user’s requests[J]. Journal on communications, 2018, 39(5): 189-198. DOI： 10.11959/j.issn.1000-436x.2018089.

摘要

现有基于兴趣点（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%。

Abstract

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.

关键词

Keywords

references

GOERIGK M , SCHMIDT M . Line planning with user-optimal route choice [J ] . European Journal of Operational Research , 2016 , 259 ( 2 ): 1 - 23 .

LU E H C , CHEN H S , TSENG V S . Efficient approaches for multi-requests route planning in urban areas [C ] // IEEE 14th International Conference on Mobile Data Management (MDM) . 2013 : 36 - 45 .

LI H , YANG T . Queues with a variable number of servers [J ] . European Journal of Operational Research , 2000 , 124 ( 3 ): 615 - 628 .

BRAJDIC A , HARLE R . Walk detection and step counting on unconstrained smartphones [C ] // The 2013 ACM International Joint Conference on Pervasive and Ubiquitous Computing . 2013 : 225 - 234 .

CHEN C , CHEN X , WANG Z , et al . Scenic planner:planning scenic travel routes leveraging heterogeneous user-generated digital footprints [J ] . Frontiers of Computer Science , 2017 , 11 ( 1 ): 1 - 14 .

VANAJAKSHI L , SUBRAMANIAN S C , SIVANANDAN R . Travel time prediction under heterogeneous traffic conditions using global positioning system data from buses [J ] . Intelligent Transport Systems Iet , 2009 , 3 ( 1 ): 1 - 9 .

YU Y , SZETO K Y . Minimize the average mean first passage time of random walk in complex networks by genetic algorithm [C ] // Evolutionary Computation . 2016 : 2352 - 2359 .

CARRABS F , CERRONE C , CERULLI R , et al . A novel discretization scheme for the close enough traveling salesman problem [J ] . Computers ＆ Operations Research , 2017 , 78 ( 2 ): 163 - 171 .

GAVALAS D , KASAPAKIS V , KONSTANTOPOULOS C , et al . Scenic route planning for tourists [J ] . Personal ＆ Ubiquitous Computing , 2017 , 21 ( 1 ): 137 - 155 .

DE PAOLA A , FERRARO P , GAGLIO S , et al . Context-awareness for multi-sensor data fusion in smart environments [M ] // AI* IA 2016 Advances in Artificial Intelligence.Springer International Publishing . 2016 : 377 - 391 .

HSIEH H P , LI C T , LIN S D . Exploiting large-scale check-in data to recommend time-sensitive routes [C ] // The ACM SIGKDD International Workshop on Urban Computing . 2015 : 55 - 62 .

VANSTEENWEGEN P , SOUFFRIAU W , BERGHE G V , et al . The city trip planner:an expert system for tourists [J ] . Expert Systems with Applications , 2016 , 38 ( 6 ): 6540 - 6546 .

QUERCIA D , SCHIFANELLA R , AIELLO L M . The shortest path to happiness:recommending beautiful,quiet,and happy routes in the city [C ] // ACM Conference on Hypertext and Social Media . 2014 : 116 - 125 .

GAVALAS D , KONSTANTOPOULOS C , MASTAKAS K , et al . A survey on algorithmic approaches for solving tourist trip design problems [J ] . Journal of Heuristics , 2014 , 20 ( 3 ): 291 - 328 .

陈淑燕 , 陈家胜 . 一种改进的灰色模型在交通量预测中的应用 [J ] . 公路交通科技 , 2014 , 21 ( 2 ): 81 - 83 .

CHEN S Y , CHEN J S . Application of an improved grey model in traffic prediction [J ] . Highway Traffic Technology , 2014 , 21 ( 2 ): 81 - 83 .

许博闻 . 环境感知的智能场景分析技术的研究 [D ] . 哈尔滨:黑龙江大学 , 2015 .

XU B W . Research on intelligent scene analysis technology of envi-ronmental perception [D ] . Harbin:Heilongjiang University , 2015 .

浏览量

1312

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向大规模图数据的关键词覆盖最优路径规划方法