隨著經濟和科技的快速發展，生活步調變得更緊促，人們往往更注重休閒旅遊等活動，來提升生活的品質。同時也因為無線通訊技術與智慧型行動裝置普及，使得與使用者位置有關的適地性服務（Location-Based Services，LBSs）研究與相關應用吸引許多學界與業界的關注。那麼如何規劃旅程和甚麼樣的旅程才是最好的？已經有很多旅遊規劃問題的相關研究，我們大致將其分為兩種，一種是根據旅客提出的旅遊需求找到最低成本(時間、距離、價錢等)的旅遊路徑(例：TPQ、OSR)；另一種多考慮旅客喜好，找出滿足旅客可旅遊的時間限制下最高分的旅遊路徑(例：Trip-Mine)。然而先前的相關研究僅考慮單一旅客或是將旅客群視為一體，旅行途中只能前往相同的地點。2013年由TPQ延伸的團體旅遊規畫問題(GTP)第一次被提出。但並沒有考慮到每位同行旅客偏好的差異。眾所周知，單人旅行計劃TPQ和Trip-Mine都是NP難問題，基於此查詢的擴展查詢也是NP難問題。因此，很難保證我們能夠在有限的時間內找到最佳解決方案。基於上述動機，我們提出了一個新的問題查詢稱為具有旅行時間和比例限制的群體旅程規劃方法。考慮到旅行時間約束，群體共同行動比率，每位旅客對每一景點的偏好分數以及景點之間的移動和停留時間，目的為在所有條件下找到群體總偏好得分最高的旅遊路徑，並盡可能減少查詢時間。另外，為了降低執行時間和記憶體使用量我們提出三個優化策略。實驗結果顯示，我們的方法在群體給定的任何共遊比例約束下，皆具有優勢。且大幅度的勝過由現有單人旅遊演算法擴充而成的Naïve演算法，由此可見規劃一個針對群體旅遊規劃的演算法之必要性。

With rapidly developing society of economy and technology, people often pay more attention to leisure travel and other activities to regulate the quality of life. Besides, due to wireless communication technology and smart mobile devices are popularized, Location-Based Services (LBSs) research and related applications related to user location have attracted the attention of many academics and industry. We roughly divide trip planning related research into two categories. One type is to find a travel path that takes the shortest distance or time in accordance with the constraints of Points-Of-Interest (POIs) proposed by the user (e.g., TPQ, OSR). Another type is to find a travel plan with the highest preference score, in compliance with the time constraint proposed by the user (e.g., Trip-Mine). However, previous related studies only considered a single traveler or a group of travelers as one. The Group Trip Planning (GTP) query was first proposed in 2013. The GTP is to expand the single-person trip planning problem (TPQ) into a group trip planning problem. However, this study doesn't consider the differences in preferences of each traveler. As we all know, the TPQ and Trip-Mine are both NP-hard problems, and the extended query based on this query is also NP-hard. Therefore, it is hard to guarantee that we can find an optimal solution within a limited time. Based on the above motivation, we propose a new query called Group Trip Planning with Travel Time and Ratio Constraints. We consider the travel time constraint, ratio constraint, and the preference scores of each traveler for each attraction and the movement and stay time between the attractions. The purpose of the query is to find the optimal trip with the highest total score of the group's total preference under the conditions and reduce the query time and memory cost as much as possible. In addition, in order to reduce execution time and memory usage, we propose three optimization strategies. The experimental results show that our method has advantages in any ratio constraint given by the travel group. And greatly better than the Naïve algorithm extended by the existing single trip planning algorithm. This shows the necessity and importance of planning an algorithm for group travel planning.

[1] Haitham Masaud Amar, and Otman A. Basir, "A Bargaining-Based Solution to the Team Mobility Planning Game," IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 3, pp. 854-867, 2017.
[2] Elham Ahmadi, Camila F. Costa, and Mario A. Nascimento, "Best-Compromise in-Route Nearest Neighbor Queries," Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2017.
[3] Elham Ahmadi, and Mario A. Nascimento, "A Mixed Breadth-Depth First Search Strategy for Sequenced Group Trip Planning Queries," 16th IEEE International Conference on Mobile Data Management, vol. 1, pp. 24-33, 2015.
[4] Elham Ahmadi, and Mario A. Nascimento, " k-Optimal Meeting Points Based on Preferred Paths," Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2016.
[5] Elham Ahmadi, and Mario A. Nascimento, "IBS: An Efficient Stateful Algorithm for Optimal Sequenced Group Trip Planning Queries," 18th IEEE International Conference on Mobile Data Management (MDM), pp. 212-221, 2017.
[6] Sukarna Barua, Roksana Jahan, and Toufique Ahmed, "Weighted Optimal Sequenced Group Trip Planning Queries," 18th IEEE International Conference on Mobile Data Management (MDM), pp. 222-227, 2017.
[7] Jinling Bao, BinWang, Shuchao Yan, and Xiaochun Yang, "Multi-constrained Optimal Path Search Algorithms," Asia-Pacific Web Conference. Springer, Cham, pp. 355-366, 2014.
[8] Xin Cao, Lisi Chen, Gao Cong, and Xiaokui Xiao, "Keyword-aware Optimal Route Search," Proceedings of the VLDB Endowment, vol. 5, no. 11, pp. 1136-1147, 2012.
[9] Haiquan Chen, Wei-Shinn Ku, Min-Te Sun, and Roger Zimmermann, "The Partial Sequenced Route Query with Traveling Rules in Road Networks," GeoInformatica, vol. 15, no. 3, pp. 541-569, 2011.
[10] Guochen Cai, Kyungmi Lee, and Ickjai Lee, "Itinerary Recommender System with Semantic Trajectory Pattern Mining from Geo-Tagged Photos. Expert Systems with Applications, vol. 94, pp. 32-40, 2018.
[11] Gao Cong, Hua Lu, Beng Chin Ooi, Dongxiang Zhang, and Meihui Zhang, "Efficient spatial keyword search in trajectory databases," arXiv preprint arXiv:1205.2880, 2012.
[12] Liyue Fan, Luca Bonomi, Cyrus Shahabi, and Li Xiong, "Multi-user Itinerary Planning for Optimal Group Preference," International Symposium on Spatial and Temporal Databases. Springer, Cham, pp. 3-23, 2017.
[13] Liyue Fan, Luca Bonomi, Cyrus Shahabi, and Li Xiong, "Optimal Group Route Query: Finding Itinerary for Group of Users in Spatial Databases," GeoInformatica, vol. 22, no. 4, pp. 845-867, 2018.
[14] Long Guo, Jie Shao, Kian-Lee Tan, and Yang Yang, "WhereToGo: Personalized Travel Recommendation for Individuals and Groups," IEEE 15th International Conference on Mobile Data Management, pp. 49-58, 2014.
[15] Yuxia Huang, and Ling Bian, "A Bayesian Network and Analytic Hierarchy Process Based Personalized Recommendations for Tourist Attractions Over the Internet," Expert Systems with Applications, vol. 36, no.1, pp. 933-943, 2009.
[16] Tanzima Hashem, Sukarna Barua, Mohammed Eunus Ali, Lars Kulik, and Egemen Tanin, "Efficient Computation of Trips with Friends and Families," Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 931-940, 2015.
[17] Tanzima Hashem, Tahrima Hashem, Mohammed Eunus Ali, and Lars Kulik, "Group Trip Planning Queries in Spatial Databases," International Symposium on Spatial and Temporal Databases, Springer, Berlin, Heidelberg, pp. 259-276, 2013.
[18] Tanzima Hashem, Tahrima Hashem, Mohammed Eunus Ali, Lars Kulik, and Egemen Tanin, "Trip Planning Queries for Subgroups in Spatial Databases," Australasian Database Conference. Springer, Cham, pp. 110-122, 2016.
[19] Tanzima Hashem, Lars Kulik, and Rui Zhang, "Privacy Preserving Group Nearest Neighbor Queries," Proceedings of the 13th International Conference on Extending Database Technology. ACM, pp. 489-500, 2010.
[20] Hsun-Ping Hsieh, and Cheng-Te Li, "Mining and Planning Time-aware Routes from Check-in Data," Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. pp. 481-490, 2014.
[21] Roksana Jahan, Tanzima Hashem, and Sukarna Barua, "Scheduling Multiple Trips for a Group in Spatial Databases," 2017.
[22] Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua Teng, "On Trip Planning Queries in Spatial Databases," International symposium on spatial and temporal databases. Springer, Berlin, Heidelberg, pp. 273-290, 2005.
[23] Huiping Liu, Cheqing Jin, Bin Yang, and Aoying Zhou, "Finding Top-k Optimal Sequenced Routes--Full Version," arXiv preprint arXiv:1802.08014, 2018.
[24] Eric Hsueh-Chan Lu, Chih-Yuan Lin, and Vincent S. Tseng, "Trip-Mine: An Efficient Trip Planning Approach with Travel Time Constraints," IEEE 12th International Conference on Mobile Data Management, pp. 152-161, 2011.
[25] Xin Lu, Changhu Wang, Jiang-Ming Yang, Yanwei Pang, and Lei Zhang, "Photo2Trip: Generating Travel Routes from Geo-Tagged Photos for Trip Planning," Proceedings of the 18th ACM international conference on Multimedia. pp. 143-152, 2010.
[26] Feifei Li, Bin Yao, and Piyush Kumar, "Group Enclosing Queries," IEEE Transactions on Knowledge and Data Engineering, vol. 23, no. 10, pp.1526-1540, 2010.
[27] Jing Li, Yin David Yang, and Nikos Mamoulis, "Optimal Route Queries with Arbitrary Order Constraints," IEEE Transactions on Knowledge and Data Engineering, vol.25, no. 5, pp.1097-1110, 2012.
[28] Maytham Safar, "Group K-Nearest Neighbors Queries in Spatial Network Databases," Journal of geographical systems, vol. 10, no. 4, pp. 407-416, 2008.
[29] Shuo Shang, Lisi Chen, Zhewei Wei, Christian S. Jensen, Ji-Rong Wen, and Panos Kalnis, "Collective Travel Planning in Spatial Networks," IEEE Transactions on Knowledge and Data Engineering, vol.28, no.5, pp.1132-1146, 2015.
[30] Samiha Samrose, Tanzima Hashem, Sukarna Barua, Mohammed Eunus Ali, Mohammad Hafiz Uddin, and Md. Iftekhar Mahmud, "Efficient Computation of Group Optimal Sequenced Routes in Road Networks," 16th IEEE international conference on mobile data management. pp. 122-127, 2015.
[31] Mehdi Sharifzadeh, Mohammad Kolahdouzan, and Cyrus Shahabi, The Optimal Sequenced Route Query," The VLDB Journal—The International Journal on Very Large Data Bases, vol. 17, no.4, pp. 765-787, 2008.
[32] Mehdi Sharifzadeh, and Cyrus Shahabi, "Processing Optimal Sequenced Route Queries Using Voronoi Diagrams," GeoInformatica, vol. 12, no. 4, pp. 411-433, 2008.
[33] Anika Tabassum, Sukarna Barua, Tanzima Hashem, and Tasmin Chowdhury, "Dynamic Group Trip Planning Queries in Spatial Databases," Proceedings of the 29th international conference on scientific and statistical database management. ACM. no. 38, 2017.
[34] Chunjie Zhou, and Xiaofeng Meng, "STS: Complex Spatio-Temporal Sequence Mining in Flickr," International Conference on Database Systems for Advanced Applications. Springer, Berlin, Heidelberg. pp. 208-223, 2011.