伴隨著行動裝置的普及，適地性服務(Location-based service, LBS)日益增加也越來越多樣 化，在各種適地性服務中，旅行路線規劃是一項非常受歡迎的項目，使用者可以透過輸入起點 與終點的位置資訊，或是有哪些感興趣的 POI、商店等等的地點想在中途經過，再讓系統規劃 出一條最適合的路徑。以往的旅行路線規劃已有考慮許多不同的因素，像是最短路徑、商店時 間、路況、個人化的旅遊路線、動態道路網路等等的非常多樣化，但是這些旅行路線規劃的研 究中並沒有考慮到使用者只能搭乘大眾運輸工具的情況，使得系統的可用性降低。同樣的現有 的大眾運輸工具的路線推薦研究也考慮了許多不同的因素，像是根據公車 IC 卡歷史記錄、根 據 Real-time data、考慮 uncertain data 等等，但現有的系統僅依據輸入的起點與終點找出最快 抵達的路徑，而無法考慮到多個目的地的路徑之間的關聯性安排路徑。我們提出了多 POI 的大 眾運輸旅遊路線推薦的問題，探討使用者只能搭乘大眾運輸公具的特殊情況下的多 POI 旅遊 路線規劃，目標在於快速計算出一條搭乘大眾運輸的最佳路線並符合使用者的時間偏好，我們 共提出了三種演算法，並以台中市與波士頓的大眾運輸資料集來驗證方法的有效性。

With the increasing popularity of mobile devices, location-based services (LBS) are becoming more and more diverse. Travel route planning is a very popular project among various location-based services. Users can input the location information of the starting point and the ending point, and the locations of interested POIs (stores, restaurant, bank, etc.) that the user want to go en route, and let the system plan the most suitable path. In the past, travel route planning has been considered by different factors, such as the shortest path, store time, road conditions, personalized travel routes, dynamic road networks, and so on. However, the availability of these travel route planning studies is reduced by the fact that the user can only take the mass transit. On the other hand, the existing public transportation route recommendation study considers different factors, such as based on bus IC card history, based on Real-time data, considering uncertain data, etc., but is based only on the starting point and the end point to find the path of the fastest arrival. It does not consider the path of the association between the paths of multiple destinations. We put forward the issue of multi-POI public transportation travel route recommendation, and explore the multi-POI travel route plan under special circumstances that users can only take public transportation. The goal is to quickly calculate the best route for public transportation and meet the requirements of user's time preference. We propose three algorithms, and validate the effectiveness of the method using the real data set of Taichung and Boston.

[1] E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, 1:269–271, 1959.
[2] P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2): 100–107, 1968. [3] Chin-HungLiu “Using Improved Bidirectional A Algorithm to Achieve Optimal Path Planning”, 2012
[4] F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng. On trip planning queries in spatial databases. In SSTD, pp. 273–290, 2005.
[5] F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng. Trip planning queries in road network databases. In Encyclopedia of GIS, pp. 1176–1181. Springer 2008.
[6] M. Sharifzadeh, M. R. Kolahdouzan, and C. Shahabi. The optimal sequenced route query. In The VLDB Journal, 17(4):765–787, 2008.
[7] H. Chen, W.-S. Ku, M.-T. Sun, and R. Zimmermann. The multi-rule partial sequenced route query. In GIS, pp. 1–10, 2008.
[8] H. Chen, W.-S. Ku, M.-T. Sun, and R. Zimmermann. The partial sequenced route query with traveling rules in road networks. Journal of Geoinformatica. doi:10.1007/s10707-010-0115-2, 2011.
[9] J. Li, Y. D. Yang, and N. Mamoulis. Optimal Route Queries with Arbitrary Order Constraints. IEEE Trans. Computers, vol. 25, no. 5, pp. 1097- 1110, 2013.
[10] R. Levin, Y. Kanza, E. Safra, and Y. Sagiv. Interactive route search in the presence of order constraints. In PVLDB, vol. 3, no. 1, pp. 117–128, 2010.
[11] T. Hashem, M. E. Ali, and L. Kulik. Group trip planning queries in spatial databases. In SSTD, pp. 259–276, 2013.
[12] S. Samrose, T. Hashem, S. Barua, M. E. Ali, M. H. Uddin, and M. I. Mahmud. Efficient computation of group optimal sequenced routes in road networks. In MDM, pp. 122–127, 2015.
[13] T. Hashem, S. Barua, M. Eunus Ali, L. Kulik, and E. Tanin. Efficient computation of trips with friends and families. In MDM, pp. 931–940, 2015.
[14] X. Cao, L. Chen, G. Cong, and X. Xiao. Keyword-aware optimal route search. In PVLDB, 5(11):1136–1147, 2012.
[15] C. Zhu, J. Xu, C. Liu, P. Zhao1, A. Liu, and L. Zhao. Efficient Trip Planning for Maximizing User Satisfaction. In DASFAA, 2015.
[16] J. Dai, C. Liu, J. Xu, and Z. Ding. On personalized and sequenced route planning. In World Wide Web, 19(4):679–705, 2016.
[17] M. Li, X. Li, and J. Yin. TORD problem and its solution based on big trajectories data. In TITS, pp. 1666-1677, 2015.
[18] Nick Roussopoulos, Stephen Kelley and Frédéric Vincent, “Nearest neighbor queries”, in ACM SIGMOD, pp. 71-79, 1995.
[19] R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis, “Nearest neighbor and reverse nearest neighbor queries for moving objects”, in VLDB Journal, vol. 15, no. 3, pp. 229–249, 2006.
[20] Reynold Cheng, Lei Chen, Jinchuan Chen, Xike Xie, “Evaluating probability threshold k-nearest-neighbor queries over uncertain data”, in EDBT, pp. 672-683, 2009.
[21] Jiajia Li, Botao Wang, and Guoren Wang, “Efficient Probabilistic Reverse k-Nearest Neighbors Query Processing on Uncertain Data”, in DASFAA, pp. 456-471, 2013.
[22] Papadopoulos and Y. Manolopoulos, “Multiple range query optimization in spatial databases”, in ADBIS, pp. 71–82, 1998.
[23] Iwerks, H. Samet, and K. Smith, “Continuous k-nearest neighbor queries for continuously moving points with updates”, in VLDB, pp. 512–523, 2003.
[24] Zhi-Jie Wang, Dong-Hua Wang, Bin Yao, and Minyi Guo, “Probabilistic Range Query over Uncertain Moving Objects in Constrained Two-Dimensional Space”, in TKDE, pp. 866-879, 2014.
[25] E. H.-C. Lu, C.-Y. Lin, and V. S. Tseng. Trip-Mine: An Efficient Trip Planning Approach with Travel Time Constraints. In MDM, pp. 152-161, 2011.
[26] E. H.-C. Lu, C.-Y. Chen, and V. S. Tseng. Personalized trip recommendation with multiple constraints by mining user check-in behaviors. In ACM SIGSPATIAL, 2012.
[27] H.-P. Hsieh, C.-T. Li, and S.-D. Lin. Exploiting large-scale check-in data to recommend time-sensitive routes. In Proc. of the ACM SIGKDD Int Workshop on Urban Computing, UrbComp ’12, pp. 55–62, Beijing, China, 2012. ACM.
[28] H.-P. Hsieh and C.-T. Li. Mining and planning time-aware routes from check-in data. In ACM CIKM, 2014.
[29] S.-H. Fang, E. H.-C. Lu, and V. S. Tseng. Trip recommendation with multiple user constraints by integrating point-of-interests and travel packages. In Proc. 15th IEEE Int. Conf. Mobile Data Manage., Jul. 2014, pp. 33–42.
[30] E. Kanoulas, Y. Du, T. Xia, and D. Zhang. Finding fastest paths on a road network with speed patterns. In Proc. ICDE, 2006.
[31] B. Ding, J. Yu, and L. Qin. Finding time-dependent shortest paths over large graphs. In Proc. EDBT, pp. 205–216. ACM, 2008.
[32] V.M.V. Gunturi, E. Nunes, K. Yang, and S. Shekhar. A Critical-Time-Point Approach to all-Start-Time Lagrangian Shortest Paths: A Summary of Results. In: Pfoser, D., Tao, Y., Mouratidis, K., Nascimento, M.A., Mokbel, M., Shekhar, S., Huang, Y. (eds.) SSTD 2011. LNCS, vol. 6849, pp. 74–91. Springer, Heidelberg 2011.
[33] J. Xu, L. Guo, Z. Ding, X. Sun, and C. Liu. Traffic aware route planning in dynamic road networks. In
DASFAA, pp. 576–591, Busan, South Korea, 2012.
[34] D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning in road networks. Transportation Science, 2015. URL: http://dx.doi.org/10.1287/trsc.2014.0579.
[35] P. S. Rathore, and A. Chaudhary. Algorithm for Route Planning via Facilities with Time Dependent. In IJCA, 2013.
[36] C. F. Costa, M. A. Nascimento, J. A. F. Macedo, Y. Theodoridis, N. Pelekis, and J. Machado. Optimal time-dependent sequenced route queries in road networks. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 56. ACM, 2015.
[37] Jiashun Liu, Yu Yuan, Feng Li and Wei Ding “Bus Trip Planning Service Based On Real Time Data” in Annual SRII Global Conference 2011.
[38] Guo, D., Zhao, Z., Xu, W., Lan, J., Zhang, T., Liu, S., Li, J. and Zhou, Y., 2015. How to Find a Comfortable Bus Route - Towards Personalized Information Recommendation Services. Data Science Journal, 14, p.14. DOI: http://doi.org/10.5334/dsj-2015-014
[39] Chen, Y., Yang, S., Hu, M. et al. “A reliability-based transit trip planning model under transit network uncertainty” in Public Transp (2016) 8: 477. https://doi.org/10.1007/s12469-016-0134-y
[40] R. Raymond, T. Sugiura, and K. Tsubouchi. Location recommendation based on location history and spatio-temporal correlations for an on-demand bus system. In Proceedings 19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (ACM-GIS), pages 377–380, Chicago, IL, 2011.
[41] S. S. Srivastava, S. Kumar, R. C. Garg, and P. Sen. Generalized traveling salesman problem through n sets of nodes. Can. Oper. Res. Soc. J., vol. 7, pp. 97–101, 1969.
[42] E. Balas. The prize collecting traveling salesman problem. Networks, vol. 19, no. 6, pp. 621–636, Oct. 1989.
[43] J. N. Tsitsiklis. Special cases of traveling salesman and repairman problems with time windows. Networks, vol. 22, no. 3, pp. 263–282, May 1992.
[44] Dumitrescu, I., Ropke, S., Cordeau, JF. et al. The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm. Math. Program. (2010) 121: 269. https://doi.org/10.1007/s10107-008-0234-9
[45] Huanhuan Wu, James Cheng, Silu Huang, Yi Lu, Yiping Ke, Yanyan Xu. Path Problems in Temporal Graphs. Proceedings of the VLDB Endowment Volume 7 Issue 9, May 2014 Pages 721-732.
[46] Z. Liu, C. Wang, and Y. Chen, “Keyword search on temporal graphs,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 8, pp. 1667–1680, Aug. 2017.
[47] King Lum Cheung, Ada Wai-Chee ,"Enhanced Nearest Neighbour Search on the R-tree",FuPublished in SIGMOD Record 1998 DOI:10.1145/290593.290596
[48] Bo Tang, Man Lung Yiu, Kai Wang,” Efficient Motif Discovery in Spatial Trajectories Using Discrete Fréchet Distance”,Published in EDBT 2017 DOI:10.5441/002/edbt.2017.34
[49] F. Costa C., Nascimento M.A. (2017) Towards Spatially- and Category-Wise k-Diverse Nearest Neighbors Queries. In: Gertz M. et al. (eds) Advances in Spatial and Temporal Databases. SSTD 2017. Lecture Notes in Computer Science, vol 10411. Springer, Cham
[50] Tanzima Hashem and Mohammed Eunus Ali : Trip Planning and Scheduling Queries in Spatial Databases: A Survey. In BDA 2017: Big Data Analytics pp 164-178.
[51] Y. Tian, K. C. K. Lee, and W.-C. Lee. Finding skyline paths in road networks. In GIS, pages 444–447, 2009
[52] https://www.google.com.tw/maps/
[53] https://play.google.com/store/apps/details?id=nexti.android.bustaiwan&hl=zh_TW