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

Nan WANG; Honglei ZHOU; Jinbao LI; Lingli LI

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

您当前的位置：

首页 >

文章列表页 >

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

Correspondences | 更新时间：2024-06-05

- Algorithm for scenario benefit route planning based on user’s requests
- Journal on Communications Vol. 39, Issue 5, Pages: 189-198(2018)
- 作者机构：
  
  1. 黑龙江省数据库与并行计算重点实验室（黑龙江大学），黑龙江哈尔滨 150080
  2. 黑龙江大学电子工程学院，黑龙江哈尔滨 150080
  3. 黑龙江大学计算机科学技术学院，黑龙江哈尔滨 150080
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61370222);The National Natural Science Foundation of China(61602159)
- DOI：10.11959/j.issn.1000-436x.2018089
  CLC： TP393
- Online First：2018-05，
  
  Published：25 May 2018
- 稿件说明：
移动端阅览
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：

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 .

Views

2596

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Keyword-aware optimal route planning method for large-scale graph data

Semantic Covert Communication Scheme Assisted by RIS and Adversarial Networks

Related Author

Ziyang LI

Pengcheng CHEN

Jiong YU

Yonglin PU

Zhenzhen HE

Xue LI

Shijie ZHENG

YI Yinxue

Related Institution

School of Software, Xinjiang University

School of Information Science and Engineering, Xinjiang University

School of Software, Nanjing University of Information Science and Technology

School of Communications and Information Engineering, Chongqing University of Posts and Telecommunications

School of Cyber Security and Information Law, Chongqing University of Posts and Telecommunications

AI问答

⁰