本論文探討了群體路徑規劃（group trip planning；GTP），以及群體路徑排程（group trip scheduling；GTS）。當一群使用者要一起出遊時，便可以使用GTP來規劃旅遊路徑。例如，有三位使用者分屬不同公司，下班後他們想要一起去吃飯，看電影，之後去pub放鬆，最後再回家。這便可以使用GTP來規劃路徑。在GTP應用的情境中，使用者要「一起」拜訪所有的地點，然而，在GTS的應用中則假設每位使用者可以「獨立地」拜訪這些地點。舉例來說，有四位使用者想要下班後一起去餐廳吃飯，有兩位要去銀行先領錢，一位要去超市採買，最後一位直接先去餐廳點餐，最後大家再集中到餐廳集合。在這個例子中，就適合使用GTS的方式來排程行程。
我們提出了一個新的GTS問題，稱為Group Purchase Trip Scheduling (GPTS) 問題。在過去GTS的問題中，往往只考慮「距離」最小化的結果，導致運用在現實場景中並不那麼完美，例如：我們想要在兩間飲料店做選擇。其中一間是距離1公里但價格超貴的飲料店。另外一間是距離100公里但價格非常便宜的飲料店。兩間飲料店相比之下，系統可能會推薦出距離1公里的飲料店。但對於預算不夠的使用者來說，卻不是最理想的推薦。因此本論文將「keyword value」也納入群組路徑規劃的考量，綜合考量距離與keyword value的群組路徑規劃引發了更多可能的應用。舉例來說，家庭成員可能會被指派要到超市買蔬果、到藥局買藥、到便當店買晚餐等等，而他們需要分工合作到各處去完成任務；同樣的場景也可以應用在工廠要派員工出去採購各部件材料的情況。本論文所探討的問題，給定n個成員的起始位置與群組的集合地點，我們希望給與該群組n段行程，這些行程必須讓群組成員共同完成該群組的需求，並且使得群組總行程距離與總keyword value最小化。這個問題能夠更加符合現實生活中的需求。我們提出了三個演算法來解決此問題，並以實驗來驗證其有效性。

In the thesis, we study the problems of group trip planning (GTP) and group trip scheduling (GTS). Consider three persons who work for different companies. After leaving their offices, they plan to go to a restaurant for dinner, then to go see a movie, and finally go for drinks at a pub. In this scenario, they can use a GTP tool to plan their trip so that the trip can satisfy their constraints while minimizing the total distance travelled by everyone. In a GTP problem, we assume all the members visit all the locations (i.e., the pub or the restaurant in the previous example) "together". However, in the GTS application, we assume that each member visits a number of locations "independently" such that the aggregate travel distance of the group members is minimized. For example, a group of four friends want to go for dinner after getting off work. Two of the members will go to a bank. One of the members will go to a supermarket to shop. One of them will go directly to a restaurant to order food in advance. At the end, all the three persons will join together at the restaurant.
We introduce Group Purchase Trip Scheduling (GPTS) queries, a novel query type in the spatial database. In the past, GTS problem only considered the result of "minimizing distance" but it is still far from optimal. For example, when we want to purchase a drink, we need to choose between two drink shops. One of the drink shops is 1 km away but the price is extremely expensive. The other drink shop is 100 km away but the price is very cheap. In contrast to the two drink shops, the system may recommend a drink shop located 1 km away. However, it is not the best recommendation for users with insufficient budget. Therefore, in this thesis, " keyword value " is also included in the consideration of GTP. The comprehensive consideration of distance and keyword value in GTP has triggered more possible applications. For instance, family members normally be assigned to purchase vegetables and fruits in supermarkets, purchase medicines in pharmacies, purchase dinners in bento shops, and so on. They need to divide and cooperate to complete the task. The same scenario can also be applied to the factory dispatch employees to purchase parts and materials. Then introduce the GPTS problem. Given the source locations of n group members and a destination. A GPTS query enables n group members to schedule n individual trips such that n trips together visit required types of POIs and the group total travel distance and total cost of n group member is minimized. GPTS query can better meet the needs in real life. We propose three algorithms to achieve GPTS query. We perform experiments using semi-real and synthetic datasets and show that our approach outperforms a straightforward approach with a large margin.

[1] S.Tiwari, S.Kaushik, P.Jagwani, andS.Tiwari, “A survey on LBS: System architecture, trends and broad research areas,” 2011. doi: 10.1007/978-3-642-25731-5_18.
[2] “Google 地圖.” https://www.google.com/maps (accessed Apr. 13, 2020).
[3] E.Ahmadi andM. A.Nascimento, “A Mixed Breadth-Depth First Search Strategy for Sequenced Group Trip Planning Queries,” in Proceedings - IEEE International Conference on Mobile Data Management, Sep. 2015, vol. 1, pp. 24–33, doi: 10.1109/MDM.2015.49.
[4] T.Hashem, S.Barua, M. E.Ali, L.Kulik, andE.Tanin, “Efficient computation of trips with friends and families,” in International Conference on Information and Knowledge Management, Proceedings, Oct. 2015, vol. 19-23-Oct-2015, pp. 931–940, doi: 10.1145/2806416.2806433.
[5] F.Ayala-Gomez, B.Daróczy, M.Mathioudakis, A.Benczúr, andA.Gionis, “Where could we go? Recommendations for groups in location-based social networks,” WebSci 2017 - Proc. 2017 ACM Web Sci. Conf., pp. 93–102, 2017, doi: 10.1145/3091478.3091485.
[6] R.Jahan, T.Hashem, andS.Barua, “Scheduling multiple trips for a group in spatial databases,” Adv. Database Technol. - EDBT, vol. 2017-March, pp. 390–401, 2017, doi: 10.5441/002/edbt.2017.35.
[7] Y.Rayhan, T.Hashem, R.Jahan, andM. A.Cheema, “Efficient scheduling of generalized group trips in road networks,” ACM Trans. Spat. Algorithms Syst., vol. 5, no. 2, 2019, doi: 10.1145/3325915.
[8] T.Hashem, T.Hashem, M. E.Ali, andL.Kulik, “Group trip planning queries in spatial databases,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, vol. 8098 LNCS, pp. 259–276, doi: 10.1007/978-3-642-40235-7_15.
[9] S.Samrose, T.Hashem, S.Barua, M. E.Ali, M. H.Uddin, andM. I.Mahmud, “Efficient Computation of Group Optimal Sequenced Routes in Road Networks,” in Proceedings - IEEE International Conference on Mobile Data Management, 2015, vol. 1, pp. 122–127, doi: 10.1109/MDM.2015.68.
[10] A.Tabassum, S.Barua, T.Hashem, andT.Chowdhury, “Dynamic group trip planning queries in spatial databases,” in ACM International Conference Proceeding Series, Jun. 2017, vol. Part F128636, pp. 1–6, doi: 10.1145/3085504.3085584.
[11] E.Ahmadi andM. A.Nascimento, “K-optimal meeting points based on preferred paths,” in GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, Oct. 2016, pp. 1–4, doi: 10.1145/2996913.2996994.
[12] E.Ahmadi andM.Nascimento, “Optimal meeting points for public transit users,” Proceedings - IEEE International Conference on Mobile Data Management, 2018. https://ieeexplore.ieee.org/document/8411257 (accessed Apr. 13, 2020).
[13] A.Anagnostopoulos, R.Atassi, L.Becchetti, A.Fazzone, andF.Silvestri, “Tour recommendation for groups,” Data Min. Knowl. Discov., vol. 31, no. 5, pp. 1157–1188, Sep.2017, doi: 10.1007/s10618-016-0477-7.
[14] L.Fan, L.Bonomi, C.Shahabi, andL.Xiong, “Multi-user itinerary planning for optimal group preference,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2017, vol. 10411 LNCS, pp. 3–23, doi: 10.1007/978-3-319-64367-0_1.
[15] L.Fan, L.Bonomi, C.Shahabi, andL.Xiong, “Optimal group route query: Finding itinerary for group of users in spatial databases,” Geoinformatica, vol. 22, no. 4, pp. 845–867, Oct.2018, doi: 10.1007/s10707-018-0331-8.
[16] S. N.Kumar andR.Panneerselvam, “A Survey on the Vehicle Routing Problem and Its Variants,” Intell. Inf. Manag., vol. 04, no. 03, pp. 66–74, 2012, doi: 10.4236/iim.2012.43010.
[17] T.Bektas, “The multiple traveling salesman problem: An overview of formulations and solution procedures,” Omega, vol. 34, no. 3, pp. 209–219, 2006, doi: 10.1016/j.omega.2004.10.004.
[18] J.Borràs, A.Moreno, andA.Valls, “Intelligent tourism recommender systems: A survey,” Expert Systems with Applications, vol. 41, no. 16. pp. 7370–7389, 2014, doi: 10.1016/j.eswa.2014.06.007.
[19] C.Zhang, Y.Zhang, W.Zhang, andX.Lin, “Inverted Linear Quadtree: Efficient Top K Spatial Keyword Search,” IEEE Trans. Knowl. Data Eng., vol. 28, no. 7, pp. 1706–1721, 2016, doi: 10.1109/TKDE.2016.2530060.
[20] J.Zhao, Y.Gao, G.Chen, C. S.Jensen, R.Chen, andD.Cai, “Reverse Top-k geo-social keyword queries in road networks,” in Proceedings - International Conference on Data Engineering, May 2017, pp. 387–398, doi: 10.1109/ICDE.2017.97.
[21] D.Zhang, K. L.Tan, andA. K. H.Tung, “Scalable top-k spatial keyword search,” in ACM International Conference Proceeding Series, 2013, pp. 359–370, doi: 10.1145/2452376.2452419.
[22] D.Zhang, Y.Li, X.Cao, J.Shao, andH. T.Shen, “Augmented keyword search on spatial entity databases,” VLDB J., vol. 27, no. 2, pp. 225–244, Apr.2018, doi: 10.1007/s00778-018-0497-6.
[23] J.Xu, Y.Gao, C.Liu, L.Zhao, andZ.Ding, “Efficient route search on hierarchical dynamic road networks,” Distrib. Parallel Databases, vol. 33, no. 2, pp. 227–252, Jun.2015, doi: 10.1007/s10619-014-7146-x.
[24] J.Xu, L.Guo, Z.Ding, X.Sun, andC.Liu, “Traffic aware route planning in dynamic road networks,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, vol. 7238 LNCS, no. PART 1, pp. 576–591, doi: 10.1007/978-3-642-29038-1_41.
[25] H. F.Xu, Y.Gu, J. Z.Qi, J. Y.He, andG.Yu, “Diversifying Top-k Routes with Spatial Constraints,” J. Comput. Sci. Technol., vol. 34, no. 4, pp. 818–838, Jul.2019, doi: 10.1007/s11390-019-1944-6.
[26] C.Zhang, Y.Zhang, W.Zhang, X.Lin, M. A.Cheema, andX.Wang, “Diversified spatial keyword search on road networks,” Adv. Database Technol. - EDBT 2014 17th Int. Conf. Extending Database Technol. Proc., pp. 367–378, 2014, doi: 10.5441/002/edbt.2014.34.
[27] S.Ghafurian andN.Javadian, “An ant colony algorithm for solving fixed destination multi-depot multiple traveling salesmen problems,” Appl. Soft Comput. J., vol. 11, no. 1, pp. 1256–1262, Jan.2011, doi: 10.1016/j.asoc.2010.03.002.
[28] F.Li, D.Cheng, M.Hadjieleftheriou, G.Kollios, andS. H.Teng, “On trip planning queries in Spatial Databases,” in Lecture Notes in Computer Science, 2005, vol. 3633, pp. 273–290, doi: 10.1007/11535331_16.
[29] H.Liu, C.Jin, B.Yang, andA.Zhou, “Finding top-k optimal sequenced routes,” Proc. - IEEE 34th Int. Conf. Data Eng. ICDE 2018, pp. 569–580, 2018, doi: 10.1109/ICDE.2018.00058.
[30] Y.Kanza, E.Safra, Y.Sagiv, andY.Doytsher, “Heuristic algorithms for route-search queries over geographical data,” in GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2008, pp. 75–84, doi: 10.1145/1463434.1463449.
[31] S. B.Roy, G.Das, S.Amer-Yahia, andC.Yu, “Interactive itinerary planning,” in Proceedings - International Conference on Data Engineering, 2011, pp. 15–26, doi: 10.1109/ICDE.2011.5767920.
[32] X.Cao, L.Chen, G.Cong, andX.Xiao, “Keyword-aware optimal route search,” Proc. VLDB Endow., vol. 5, no. 11, pp. 1136–1147, 2012, doi: 10.14778/2350229.2350234.
[33] A.Gionis, T.Lappas, K.Pelechrinis, andE.Terzi, “Customized tour recommendations in urban areas,” in WSDM 2014 - Proceedings of the 7th ACM International Conference on Web Search and Data Mining, 2014, pp. 313–322, doi: 10.1145/2556195.2559893.
[34] C.Zhu, J.Xu, C.Liu, P.Zhao, A.Liu, andL.Zhao, “Efficient trip planning for maximizing user satisfaction,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2015, vol. 9049, pp. 260–276, doi: 10.1007/978-3-319-18120-2_16.
[35] A.Anwar andT.Hashem, “Optimal obstructed sequenced route queries in spatial databases,” in Advances in Database Technology - EDBT, 2017, vol. 2017-March, pp. 522–525, doi: 10.5441/002/edbt.2017.60.
[36] S. C.Soma, T.Hashem, M. A.Cheema, andS.Samrose, “Trip planning queries with location privacy in spatial databases,” World Wide Web, vol. 20, no. 2, pp. 205–236, Mar.2017, doi: 10.1007/s11280-016-0384-2.
[37] H.Chen, W. S.Ku, M.TeSun, andR.Zimmermann, “The multi-rule partial sequenced route query,” in GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 2008, pp. 65–74, doi: 10.1145/1463434.1463448.
[38] G.Laporte, “A concise guide to the Traveling Salesman Problem,” J. Oper. Res. Soc., vol. 61, no. 1, pp. 35–40, Jan.2010, doi: 10.1057/jors.2009.76.
[39] T.Hashem, S.Barua, M. E.Ali, L.Kulik, andE.Tanin, “Efficient computation of trips with friends and families,” in International Conference on Information and Knowledge Management, Proceedings, Oct. 2015, vol. 19-23-Oct-, pp. 931–940, doi: 10.1145/2806416.2806433.
[40] A.Tabassum, S.Barua, T.Hashem, andT.Chowdhury, “Dynamic group trip planning queries in spatial databases,” in ACM International Conference Proceeding Series, Jun. 2017, vol. Part F1286, pp. 1–6, doi: 10.1145/3085504.3085584.
[41] M. D.Arango andC. A.Serna, “A Memetic Algorithm for the Traveling Salesman Problem,” 2015. doi: 10.1109/TLA.2015.7332148.
[42] B.Bontoux, C.Artigues, andD.Feillet, “A Memetic Algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem,” Comput. Oper. Res., vol. 37, no. 11, pp. 1844–1852, Nov.2010, doi: 10.1016/j.cor.2009.05.004.
[43] M. N.Rice andV. J.Tsotras, “Engineering generalized shortest path queries,” in Proceedings - International Conference on Data Engineering, 2013, pp. 949–960, doi: 10.1109/ICDE.2013.6544888.
[44] D.Manerba, R.Mansini, andJ.Riera-Ledesma, “The Traveling Purchaser Problem and its variants,” Eur. J. Oper. Res., vol. 259, no. 1, pp. 1–18, 2017, doi: 10.1016/j.ejor.2016.12.017.
[45] "內政部地政司衛星測量中心─國家坐標系統之訂定(GPS9)."http://www.gps.moi.gov.tw/SSCenter/Introduce/IntroducePage.aspx?Page=GPS9 (Accessed: 2020-06-29).