基于时空序列搜索的最优个性化旅游规划

doi:10.11896/j.issn.1002-137X.2017.09.052

摘要/Abstract

摘要： 随着人们对高效、个性化服务的日益关注,其对旅游规划的要求也越来越高。然而,目前制定一个完美的、个性化的旅游规划很困难。一个合理的旅游规划应该包含以下特征:1)基于游客兴趣爱好的个性化推荐；2)覆盖尽可能多的兴趣景点；3)走最少的路程,花费最少的时间。由于每次旅游包含多个景点,因此该问题变成了每个景点都附有权值的时空序列优化问题。为了实现最优个性化旅游规划,首先,针对每个城市为每位游客提供一系列带有权值的景点；然后,综合考虑距离、权值、旅游时间和景点特色等因素,为游客推荐一个最优旅游序列。为此,提出了4种有效算法,使游客在旅游时间范围限制内走最少的路程来游览最想游览的景点。在社交网络的真实数据集上,通过实验验证了所提算法的有效性。

关键词: 时空,序列,社交网络,个性化,旅游规划

Abstract: Nowadays,due to the increasing user requirements of efficient and personalized services,a perfect trip planning is urgently needed.However,it is hard for people to make a personalized traveling plan at present.For a satisfactory trip planning,the following features are desired:i) personalized recommender based on the interest and habits of travelers；ii) maximal coverage of sites of interest；iii) minimal effort such as transporting time on the route.As a trip contains a sequence of stops at multiple scenes,the problem of trip planning becomes an optimized spatio-temporal sequence where each stop is weighted.For each city,this paper generated a set of weighted scenes for each user.Then it can retrieve the optimal sequence of scenes in terms of distance,weight,visiting time and scene features.We developed alternative algorithms for searching optimal sequences,with consideration of the weight of each scene,the preference of users,and the travel time constraint.The experiments demonstrate the efficiency of the proposed algorithms based on real datasets from social networks.

Key words: Spatio-temporal,Sequence,Social networks,Personalized,Trip planning

周春姐,曲海平,刘莉. 基于时空序列搜索的最优个性化旅游规划[J]. 计算机科学, 2017, 44(9): 277-285. https://doi.org/10.11896/j.issn.1002-137X.2017.09.052

ZHOU Chun-jie, QU Hai-ping and LIU Li. Optimal Personalized Trip Planning Based on Spatio-Temporal Sequence Searching[J]. Computer Science, 2017, 44(9): 277-285. https://doi.org/10.11896/j.issn.1002-137X.2017.09.052

参考文献

[1] HALPIN H,ROBU V,SHEPHERD H.The Complex Dynamics of Collaborative Tagging[C]∥The 16th International Confe-rence on World Wide Web (WWW).2007:211-220.
[2] SOO V W,LIANG S H.Recommending a Trip Plan by Negotiation with a Software Travel Agent[J].Cooperative Information Agents,2001,2:32-37.
[3] CASTILLO L,ARMENGOL E,ONAINDIA E,et al.Samap:An User-oriented Adaptive System for Planning Tourist Visits[J].Expert Systems with Applications,2008,34(2):1318-1332.
[4] YU C C,CHANG H P.Personalized Location-Based Recom-mendation Services for Tour Planning in Mobile Tourism Applications[J].E-Commerce and Web Technologies,2009,5692:38-49.
[5] NIARAKI A S,KIM K.Ontology based Personalized RoutePlanning System using a Multi-criteria Decision Making Approach[J].Expert Systems with Applications,2009,36(2):2250-2259.
[6] YOON H,ZHENG Y,XIE X,et al.Smart Itinerary Recommendation Based on User-Generated GPS Trajectories[C]∥Proceedings of the International Conference on Ubiquitous Intelligence and Computing.2010:19-34.
[7] KISILEVICH S,KEIM D,ROKACH L.A Novel Approach to Mining Travel Sequences Using Collections of Geotagged Photos[C]∥Proceedings of the 13th AGILE International Conference on Geographic Information Science.2010:163-182.
[8] LU X,WANG C,YANG J M,et al.Photo2Trip:GeneratingTravel Routes from Geo-Tagged Photos for Trip Planning[C]∥Proceedings of the ACM International Conference on Multimedia.2010:143-152.
[9] YU J,ASLAM J A,KARAMAN S,et al.Optimal Tourist Problem and Anytime Planning of Trip Itineraries.http://xxx.tall.ac.il/pdf/1409.8536v1.
[10] XIE M,LAKSHMANAN L V S,WOOD P T.IPS:An Interactive Package Configuration System for Trip Planning[J].PVLDB,2013,6(12):1362-1365.
[11] JOSEPH R.Real-time Trip Planning with the Crowd[M].CHI Extended Abstracts,2013:2743-2748.
[12] GEORGIOS A L,AMIR A S,POLVCHRONIS K.A New Location-Aware Calendar-Based Application for Dynamic Minimum Path Trip Planning[J].Wireless Personal Communications (WPC),2014,78(1):29-44.
[13] OHSAWA Y,HTOO H,WIN T N.Continuous Trip RoutePlanning Queries[M]∥Book:Advances in Databases and Information Systems.Volume 9809 of the series Lecture Notes in Computer Science.Springer International Publishing.2016:198-211.
[14] XIE M,LAKSHMANAN L V S, WOOD P T.IPS:An Interactive Package Configuration System for Trip Planning[J].PVLDB,2013,6(12):1362-1365.
[15] LEE C S,CHANG Y C,WANG M H.Ontological Recommendation Multi-Agent for Tainan City Travel[J].Expert Systems with Applications,2009,36(3):6740-6753.
[16] SOUFFRIAU W,VANSTEENWEGEN P.Tourist Trip Plan-ning Functionalities:State-of-the-Art and Future[C]∥Procee-dings of the 10th International Conference on Web Engineering (ICWE).2010:474-485.
[17] FOSCA G,MIRCO N,DINO P,et al.Trajectory Pattern Mining[C]∥Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning (KDD).2007:330-339.
[18] MAMOULIS N,et al.Indexing and Quering Historical Spatiotemporal Data[C]∥Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning (KDD).2004:236-245.
[19] GIRARDIN F,DAL F,BLAT J,et al.Understanding of Tourist Dynamics from Explicitly Disclosed Location Information[C]∥Proceedings of the 4th International Symposium on LBS and Telecartography.2007.
[20] CHEN Z,SHEN H T,ZHOU X,et al.Searching Trajectories by Locations-An Efficiency Study[C]∥Proceedings of the 36th SIGMOD International Conference on Management of Data (SIGMOD).2010:255-266.
[21] GEORGIOS A L,AMIR A S, POLVCHROIS K.A New Location-Aware Calendar-Based Application for Dynamic Minimum Path Trip Planning[J].Wireless Personal Communications (WPC),2014,78(1):29-44.
[22] YOON H,ZHENG Y,XIE X,et al.Social Itinerary Recommendation from User-generated Digital Trails[J].Personal and Ubiquitous Computing,2012,16(5):469-484.
[23] IGO R B,JOSE A F,FRANCO M N.Where Shall We Go Today?:Planning Touristic Tours with Tripbuilder[C]∥CIKM.2013:757-762.
[24] JOSEPH R.Real-time Trip Planning with the Crowd[J].CHI Extended Abstracts,2013:2743-2748.
[25] ZHU C,XU J,LIU C,et al.Efficient Trip Planning for Maximizing User Satisfaction[C]∥20th International Conference(DASFAA 2015).Hanoi,Vietnam,Part I,2015:260-276.
[26] BORIS C.Improved Trip Planning by Learning from Travelers’ Choices[C]∥ICML Workshop Mining Urban Mobiltiy.At Lille,France,July,2015:17-26.
[27] POPESCU A,GREFENSTETTE G.Deducing Trip Related Information from Flickr[J].International Conference on World Wide Web,2009,25(1):1183-1184.
[28] TAO Y,PAPADIAS D,SHEN Q.Continuous Nearest Neighbor Search[C]∥Proceedings of 28th International Conference on Very Large Data Bases (VLDB).2002:287-298.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed