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

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

Abstract

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.

Key words: point of interest, scenario benefit, KL divergence, route planning

CLC Number:

TP393

Nan WANG,Honglei ZHOU,Jinbao LI,Lingli LI. Algorithm for scenario benefit route planning based on user’s requests[J]. Journal on Communications, 2018, 39(5): 189-198.

Figures/Tables 17

References 16

[1]	GOERIGK M , SCHMIDT M . Line planning with user-optimal route choice[J]. European Journal of Operational Research, 2016,259(2): 1-23.
[2]	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.
[3]	LI H , YANG T . Queues with a variable number of servers[J]. European Journal of Operational Research, 2000,124(3): 615-628.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	GAVALAS D , KASAPAKIS V , KONSTANTOPOULOS C ,et al. Scenic route planning for tourists[J]. Personal ＆ Ubiquitous Computing, 2017,21(1): 137-155.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	陈淑燕, 陈家胜 . 一种改进的灰色模型在交通量预测中的应用[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.
[16]	许博闻 . 环境感知的智能场景分析技术的研究[D]. 哈尔滨:黑龙江大学, 2015.
	XU B W . Research on intelligent scene analysis technology of envi-ronmental perception[D]. Harbin:Heilongjiang University, 2015.

Metrics

Recommended 0

No Suggested Reading articles found!

符号	描述
r,R	r代表某个需求，R代表需求集合
R′	R′代表用户的需求集合
p,P	p代表某个POI，P代表POI集合
s,d	s代表起点，d代表终点
ρ ,,μτ	停留时间，行走时间，路程时间
PSR (),RSP()	某个需求的POI集合，某个POI的需求
M ,E	区域网络，网络中的路径
?	规划路径

状态	状态值	残差值
1	1	δ (t)>0
2	0	δ (t)=0
3	?1	δ (t)<0

状态转移	S_i?>S ₁	S_i?>S ₂	S_i?>S₃
转移概率	p(s ₁\|s_i)	p(s₂\|s_i)	p(s ₃\|s_i)
符号	p_{i 1}	p_{i 2}	p_{i 3}

实验数据	默认值
需求服务时间/min	3
网络区域中点的个数	100
用户的需求种类个数	10
总服务种类个数	25
α	0.02
k	2

利益项	取值
景区流行度	Rank 1-2(5)、Rank 3-5(4)、Rank 6-9(3)
时间KL散度	0,3](5)、(3,6](4)、(6,10](3)
访问次序	0.7,1](5)、[0.4,0.6](4)、[0-0.3](3)
时间限制/min	120、240、360
排队服务时间（QS_Time）/(人·分钟^?1)	5
景点人数到达速度μ/(人·分钟^?1)	2~8
路程时间	time×α

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 17

References 16

Related Articles 15

Metrics

Recommended 0

[1]	Jingbo LI, Li MA, Yang LI, Yingxun FU, Dongchao MA. Optimized design of sensing transmission and computing collaborative industrial Internet [J]. Journal on Communications, 2023, 44(6): 12-22.
[2]	Shiqi ZHAO, Xiaohong HUANG, Zhigang ZHONG. Research and implementation of reputation-based inter-domain routing selection mechanism [J]. Journal on Communications, 2023, 44(6): 47-56.
[3]	Zhen CHEN, Wenhui CHEN, Xiaowei LIU, Dianlong YOU, Linlin LIU, Limin SHEN. Functional complementarity relationship enhanced cloud API recommendation method [J]. Journal on Communications, 2023, 44(6): 125-137.
[4]	Debin WEI, Chengsheng PAN, Li YANG, Zuoren YAN. Adaptive random early detection algorithm based on network traffic level grade prediction [J]. Journal on Communications, 2023, 44(6): 154-166.
[5]	Yuancheng LI, Yongtai QIN. Deep reinforcement learning based algorithm for real-time QoS optimization of software-defined security middle platform [J]. Journal on Communications, 2023, 44(5): 181-192.
[6]	Yingjie XIA, Siyu ZHU, Xuejiao LIU. Research on efficient cross trust-domain group authentication with conditional privacy of vehicle platoon under blockchian architecture [J]. Journal on Communications, 2023, 44(4): 111-123.
[7]	Renchao XIE, Wen WEN, Qinqin TANG, Yunlong LIU, Gaochang XIE, Tao HUANG. Survey on rail transit mobile edge computing network security [J]. Journal on Communications, 2023, 44(4): 201-215.
[8]	Zhiyong LUO, Yu ZHANG, Qing WANG, Weiwei SONG. Study of SDN intrusion intent identification algorithm based on Bayesian attack graph [J]. Journal on Communications, 2023, 44(4): 216-225.
[9]	Yifeng WANG, Yuanbo GUO, Qingli CHEN, Chen FANG, Renhao LIN, Yongliang ZHOU, Jiali MA. Method based on contrastive incremental learning for fine-grained malicious traffic classification [J]. Journal on Communications, 2023, 44(3): 1-11.
[10]	Jin ZHANG, Qiang GE, Weihai XU, Yiming JIANG, Hailong MA, Hongtao YU. Design, implementation and formal verification of BGP proxy for mimic router [J]. Journal on Communications, 2023, 44(3): 33-44.
[11]	Pujie JING, Liangmin WANG, Xuewen DONG, Yushu ZHANG, Qian WANG, Sohail Muhammad. CHA: cross-chain based hierarchical architecture for practicable blockchain regulatory [J]. Journal on Communications, 2023, 44(3): 93-104.
[12]	Jian SHU, Jiawei SHI, Linlan LIU, Al-Kali Manar. Topology prediction for opportunistic network based on spatiotemporal convolution [J]. Journal on Communications, 2023, 44(3): 145-156.
[13]	Dongbin WANG, Dongzhe WU, Hui ZHI, Kun GUO, Xu ZHANG, Jinqiao SHI, Yu ZHANG, Yueming LU. Preventing flow table overflow against denial of service attack in software defined network [J]. Journal on Communications, 2023, 44(2): 1-11.
[14]	Haiyan KANG, Molan LONG. Research on network attack analysis method based on attack graph of absorbing Markov chain [J]. Journal on Communications, 2023, 44(2): 122-135.
[15]	Yuntao ZHANG, Binxing FANG, Chunlai DU, Zhongru WANG, Zhijian CUI, Shouyou SONG. Container escape detection method based on heterogeneous observation chain [J]. Journal on Communications, 2023, 44(1): 49-63.