近年來，由於無線網路與智慧型手機的興起，帶動適地性服務與應用的迅速發展。其中一個熱門的議題為多目標路徑規劃。雖然已經有不少的研究探討多目標路徑規劃議題，但多數的研究只考慮到這些目標的地理位置資訊，而沒有考慮到使用者拜訪這些目標的真正目的其實是有某些需求需要被滿足。除此之外，從複雜的交通情況中規劃出符合使用者需求的路徑，其運算的時間複雜度是非常的高，所以在相當要求即時性的路徑規劃系統中，如何提高運算效率成為一個相當關鍵的問題。本研究提出一個創新的路徑規劃問題，名為Multi-Requests Route Planning (MRRP)，並提出了四個有效率的方法來解決這個問題。此外，我們更進一步提出了路徑優化機制、刪減搜尋空間策略和快取技術來增進整體演算法的效能。就我們所知，本研究為第一篇在考慮一個節點可以提供數個服務的道路網路之下，提出有效率的方法來規劃滿足使用者多個需求的路徑。透過蒐集到的真實道路資料和我們所提出的節點模擬模型，我們進行了一系列完整的實驗，實驗結果顯示我們提出的方法不論是在路徑品質還是運算效能上都有相當優異的表現。

In recent years, with the rapid developments of wireless technologies, researches on Location-Based Services (LBSs) have attracted extensive attentions and one active topic among them is constraint-based route planning on a Point-Of-Interest (POI) network. Although a number of studies on this topic have been proposed in literatures, most of them primarily consider the geographic properties of the POIs in planning a route. In fact, the motivation of a user to visit a POI is frequently due to that the POI can provide some services meeting the user’s needs. Hence, user requests should be considered in route planning, especially in an urban area where a POI may provide various kinds of services. Besides, the efficiency of route planning is critical in such kind of real-time LBS applications. In this thesis, we address a novel route planning problem named Multi-Requests Route Planning (MRRP) and propose four approaches, namely kNN-MS, kMD-MS, EMB and kRA-MS to efficiently plan a time-saving route based on the user-specific requests. Furthermore, we propose two refinement mechanisms, three pruning strategies and two caching techniques to further enhance the route quality and planning efficiency for MRRP, respectively. To the best of our knowledge, this is the first work on route planning that considers multiple services provided by a POI and multiple requests specified by a user, simultaneously. Through extensive experimental evaluations, our approaches were shown to deliver excellent performance.

[1] R. Agrawal, C. Faloutsos, and A. N. Swami. " Efficient Similarity Search In Sequence Databases," in Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, pp. 69–84, 1993.
[2] E. M. Arkin and R. Hassin, "Approximation Algorithms for the Geometric Covering Salesman Problem," Discrete Appl. Math., vol. 55, pp. 197-218, 1995.
[3] M. de Berg, J. Gudmundsson, M. J. Katz, C. Lev-copoulos, M. H. Overmars and A. F. van der Stappen, "TSP with Neighborhoods of Varying Size," Journal of Algorithms, vol. 57, pp. 22-36, 2005.
[4] T. Brinkhoff, "Generating Network-Based Moving Objects," in Proceedings of the 12th International Conference on Scientific and Statistical Database Management, pp. 253, 2000.
[5] H. Chen, W.-S. Ku, M.-T. Sun and R. Zimmermann, "The Partial Sequenced Route Query with Traveling Rules in Road Networks," GeoInformatica, vol. 15, pp. 541-569, 2011.
[6] L. Chen, M. T. Özsu, and V. Oria. " Robust and Fast Similarity Search for Moving Object. Trajectories," in Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 491–502, 2005.
[7] Zaiben Chen, Heng-Tao Shen, Xiaofang Zhou, and Jeffrey-Xu Yu, "Monitoring Path Nearest Neighbor in Road Networks," in Proceedings of the 2009 ACM SIGMOD international conference on Management of data, pp. 591-602, 2009.
[8] G. Cong, H. Lu, B.-C. Ooi, D. Zhang and M. Zhang, "Efficient Spatial Keyword Search in Trajectory Databases," CoRR, abs/1205.2880, 2012.
[9] E.-W. Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, pp. 269-271, 1959.
[10] K. Elbassioni, A.-V. Fishkin and R. Sitters, "Approximation Algorithms for the Euclidean Traveling Salesman Problem with Discrete and Continuous Neighborhoods," International Journal of Computational Geometry and Applications, vol. 19, pp, 173-193, 2009.
[11] Facebook, http://www.facebook.com/
[12] Google Maps, https://maps.google.com/
[13] Gowalla, http://gowalla.com/
[14] P. Hart, N. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics, vol. 4, pp. 100-107, 1968.
[15] Hefez, Y. Kanza and R. Levin, "Tarsius: A System for Traffic-aware Route Search under Conditions of Uncertainty," in Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 517-520, 2011.
[16] F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios and S.-H. Teng, "On Trip Planning Queries in Spatial Databases," in Proceedings of the 9th international conference on Advances in Spatial and Temporal Databases, pp. 273-290, 2005.
[17] S. Lin and B. W. Kernighan, " An Effective Heuristic Algorithm for the Travelling-Salesman Problem," Operations Research, vol. 21, pp. 498-516, 1973.
[18] E. H.-C. Lu, W.-C. Lee and V. S. Tseng, "A Framework for Personal Mobile Commerce Pattern Mining and Prediction," IEEE Transactions on Knowledge and Data Engineering, vol. 24, pp. 769-782, May 2012.
[19] E. H.-C. Lu, C.-Y. Lin and V. S. Tseng, "Trip-Mine: An Efficient Trip Planning Approach with Travel Time Constraints," in Proceedings of IEEE International Conference on Mobile Data Management, pp. 152-161, 2011.
[20] E. H.-C. Lu, C.-C. Lin and V. S. Tseng, "Mining the Shortest Path within a Travel Time Constraint in Road Network Environments," in Proceedings of IEEE International Conference on Intelligent Transportation Systems, pp. 593-598, 2008.
[21] K. Martens, I. Benenson and N. Levy, "The Dilemma of On-Street Parking Policy: Exploring Cruising for Parking Using an Agent-Based Model," Geospatial Analysis and Modelling of Urban Structure and Dynamics, pp. 121-138, 2010
[22] K. Menger, "Das Botenproblem," Ergebnisse Eines Mathematischen Kolloquiums, vol. 2, pp. 11-12, 1932.
[23] J. S. B. Mitchell, "A PTAS for TSP with Neighborhoods among Fat Regions in the Plane," in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 11-18, 2007.
[24] OpenStreetMap http://www.openstreetmap.org/
[25] D. Papadias, J. Zhang, N. Mamoulis and Y. Tao, "Query Processing in Spatial Network Databases," in Proceedings of the 29th international conference on Very large data bases, pp. 802-813, 2003.
[26] M. Sharifzadeh, M. Kolahdouzan and C. Shahabi, "The Optimal Sequenced Route Query," in Proceedings of the 29th international conference on Very large data bases, pp. 765–787, 2008.
[27] M. Sharifzadeh and C. Shahabi, "Processing Optimal Sequenced Route Queries Using Voronoi Diagrams," GeoInformatica, vol. 12, pp. 411-433, 2008.
[28] Shekhar, Shashi, and Jin Soung Yoo, "Processing In-Route Nearest Neighbor Queries: A Comparison of Alternative Approaches," in Proceedings of the 11th ACM international symposium on Advances in geographic information systems, pp. 9-16, 2003.
[29] M. Vlachos, D. Gunopoulos, and G. Kollios. " Discovering Similar Multidimensional Trajectories," in Proceedings of the 18th International Conference on Data Engineering, pp. 673, 2002.
[30] Josh Jia-Ching Ying, Eric Hsueh-Chan Lu, Wen-Ning Kuo and Vincent S. Tseng, "Urban Point-of-Interest Recommendation by Mining User Check-in Behaviors," in Proceedings of the ACM SIGKDD International Workshop on Urban Computing, pp. 63-70, 2012.
[31] K. Zheng, S. Shang, N. J. Yuan and Y. Yang, "Towards Efficient Search for Activity Trajectories," in Proceedings of the 29th IEEE International Conference on Data Engineering, pp. 230-241, 2013.