旅游路线规划是一项具有挑战性的工作,它需同时考虑时间和空间两个维度上的旅游数据。一方面需获取旅游兴趣点在景区中的空间分布,另一方面需考虑游客在景区游览过程中的游览行为。因此,旅游路线规划除需要采集景区中各景点的属性信息,还需大量游客的游览行为数据。本文通过对上述数据进行采集,从中提取游客在景点间的旅行行为信息,提出衡量游客旅行行为的重要指标。在综合考虑这些指标的基础上,以大幅降低景点间旅行耗时为实验目标,提出旅行路线规划算法(TRP)。实验得出了未做旅行路线规划和旅行路线规划后两种截然不同的旅行路线规划结果和相应的旅行耗时。同时,通过进一步对路线规划进行优化,得到优化前后在旅行耗时的对比结果。结果表明,旅行路线规划算法不仅能大幅节省旅行耗时,而且对于如何设置观光车的停靠位置有较好的应用参考价值。与当前具有代表性的三种路径规划算法相比,文中算法在响应时间和平均求解质量上均具有显著优势。
Tourist route planning is a challenging task that requires considering both temporal and spatial dimensions of tourism data. On one hand, it involves obtaining the spatial distribution of tourist attractions within the scenic area, and on the other hand, it takes into account the tourists' visiting behaviors during their exploration of the area. Therefore, in addition to collecting attribute information of various attractions in the scenic area, tourism route planning also requires a significant amount of data on tourists' visiting behaviors. This paper collects the aforementioned data and extracts the travel behavior information of tourists between attractions, proposing important indicators for measuring tourist travel behavior. Based on a comprehensive consideration of these indicators, the Travel Route Planning algorithm (TRP) is introduced with the aim of significantly reducing travel time between attractions. The experiments yield distinct results and corresponding travel times between scenarios without travel route planning and scenarios with travel route planning. Furthermore, by further optimizing the route planning, a comparison of travel times before and after optimization is obtained. The results indicate that the Travel Route Planning algorithm not only greatly reduces travel time but also provides valuable insights for determining optimal locations for tourist buses to make stops. Compared to three representative path planning algorithms currently available, the algorithm proposed in this paper exhibits significant advantages in response time and average solution quality.
[1] Taylor K, Lim K H, Chan J. Travel itinerary recommendations with must-see points-of-interest [C]//Companion Proceedings of the Web Conference, 2018: 1198-1205.
[2] Bart T, David A S, Gerald F, et al. YFCC100M: The new data in multimedia research [J]. Communications of the ACM, 2016, 59(2): 64-73.
[3] Bochar L, Radi B. A new approach to treat the selective travelling salesman problem [J]. International Mathematical Forum, 2016, 11: 757-768.
[4] Feillet D, Dejax P, Gendreau M. Traveling salesman problems with profits [J]. Transportation Science, 2005, 39(2): 188-205.
[5] Gunawan A, Lau H C, Vansteenwegen P. Orienteering problem: A survey of recent variants, solution approaches and applications [J]. European Journal of Operational Research, 2016, 255(2): 315-332.
[6] Theodore T. Heuristic methods applied to orienteering [J]. Journal of the Operational Research Society, 1984, 35(9): 797-809.
[7] Pieter V, Wouter S, Dirk V O. The orienteering problem: A survey [J]. European Journal of Operational Research, 2011, 209(1): 1-10.
[8] Laporte G, Martello S. The selective travelling salesman problem [J]. Discrete Applied Mathematics, 1990, 26(2-3): 193-207.
[9] Brilhante I, Macedo J A, Nardini F M, et al. Where shall we go today? Planning touristic tours with tripbuilder [C]//Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, 2013: 757-762.
[10] Brilhante I R, Macedo J A, Nardini F M, et al. On planning sightseeing tours with trip builder [J]. Information Processing and Management, 2015, 51(2): 1-15.
[11] De Choudhury M D, Feldman M, Amer-Yahia S, et al. Automatic construction of travel itineraries using social breadcrumbs [C]//Proceedings of the 21st ACM Conference on Hypertext and Hypermedia, 2010: 35-44.
[12] Lim K H, Chan J, Leckie C, et al. Towards next generation touring: Personalized group tours [C]//Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2017: 325-334.
[13] Lim K H, Chan J, Leckie C, et al. Next generation touring: Personalized group tours [C]//Proceedings of the 26th International Conference on Automated Planning and Scheduling, 2016: 412-420.
[14] Lim K H, Chan J, Leckie C, et al. Personalized trip recommendation for tourists based on user interests, points of interest visit durations and visit recency [J]. Knowledge and Information Systems, 2018, 54(2): 375-406.
[15] Mukhina K D, Rakitin S V, Visheratin A A. Detection of tourists attraction points using Instagram profiles [J]. Procedia Computer Science, 2017, 108: 315-332.
[16] Quercia D, Schifanella R, Aiello L M. The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city [C]//Proceedings of the 25th ACM Conference on Hypertext and Social Media, 2014: 116-125.
[17] Wang X, Leckie C A, Chan J, et al. Improving personalized trip recommendation by avoiding crowds [C]//Proceedings of the 25th ACM International Conference on Information and Knowledge Management, 2016: 25-34.
[18] Brilhante I, Macedo J A, Nardini F M, et al. TripBuilder: A tool for recommending sightseeing tours [C]//Proceedings of the 36th European Conference on Information Retrieval, 2014: 771- 774.
[19] Woerndl W, Hefele A. Through discovered places-of-interests for city trip planning [C]//Information and Communication Technologies in Tourism, 2016: 441-453.
[20] Leung K W T, Lee D L, Lee W C. CLR: A collaborative location recommendation framework based on co-clustering [C]//Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, 2011: 305-314.
[21] Shi Y, Serdyukov P, Hanjalic A, et al. Personalized landmark recommendation based on geotags from photo sharing sites [C]//Proceedings of the Fifth International Conference on Weblogs and Social Media, 2011: 622-625.
[22] Yao L, Sheng Q Z, Qin Y, et al. Context-aware point-of-interest recommendation using tensor factorization with social regularization [C]//Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2015: 1007-1010.
[23] Yuan Q, Cong G, Ma Z Y, et al. Time-aware point-of-interest recommendation [C]//Proceedings of the 36th International ACM SIGIR Conference on Research and development in Information Retrieval, 2013: 363-372.
[24] Benouaret I, Lenne D. A composite recommendation system for planning tourist visits [C]//IEEE/WIC/ACM International Conference on Web Intelligence, 2016: 626-631.
[25] Kofler C, Caballero L, Menendez M, et al. Near2me: An authentic and personalized social media-based recommender for travel destinations [C]//Proceedings of the 3rd ACM SIGMM International Workshop on Social Media, 2011: 47-52.
[26] Marinescu R, Lee J, Ihler A, et al. Anytime best+depth-first search for bounding marginal MAP [C]//Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017: 3775-3782.
[27] Lou Q, Dechter R, Ihler A. Anytime anyspace AND/OR best-first search for bounding marginal MAP [C]//Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018: 6392-6400.
[28] Wang J Y, Wu N, Zhao W X, et al. Empowering A* search algorithms with neural networks for personalized route recommendation [C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019: 539-547.
[29] Yang C X, Zhang J L, Gao X F, et al. MatTrip: Multi-functional attention based neural network for semantic travel route recommendation [C]//2021 IEEE International Conference on Web Services, 2021: 145-154.
北大中文核心期刊