適地性服務（Location-Based Service，LBS）已成為日常生活中不可或缺的一部份，其中一個重要的LBS為路徑規劃。有別於傳統路徑規劃問題，多需求路徑規劃（Multi-Request Route Planning，MRRP）考慮一個興趣點（Point of Interest，POI）可以包含多種使用者需要的服務，如吃飯，領錢等。然而MRRP沒有考慮查詢時間，無法反應使用者需求的急迫性與店家營業時間等問題。本研究認為MRRP除了要考慮POI有多種服務的特性外，也應該考慮查詢時間特性。由於加入時間維度，MRRP的目標是將從單一維度的最短路徑搜尋調整為多重維度的最佳路徑搜尋，在決策支援系統中，當無法定義多重維度好壞時，天際線查詢適合用於搜尋不同維度上不被支配的解。因此本論文提出一個具時間限制之多需求路徑規劃（MRRP with Time Urgency，MRRP-TU）問題，為了有效地搜尋具時間限制之多需求路徑，我們設計了具有天際線查詢之MRRP-TU隨時演算法（Anytime Algorithm），其中結合優先權佇列、天際線修剪策略與潛在成本估計，透過最短路徑與延遲時間，使用者可以在多條路徑中去選擇自己偏好的路徑。在實驗中，我們使用了台南的POI資料，在最佳解演算法中，我們的方法可以大幅的增加我們的查詢速度，也顯示出能夠快速返回解的能力，在近似解的實驗，也顯示我們提出的方法可以在短時間內返回高品質的解。

Location-Based Service (LBS) has become an integral part of daily life. An important part of LBS is route planning. Unlike classical route planning problems, Multi-Request Route Planning (MRRP) Consider a Point of Interest (POI), MRRP can include various services that users need, such as eating meals, getting money, etc. However, MRRP does not consider the query time, which does not respond to the urgency of users' requests or the opening hours of stores. In this study, we consider that MRRP should consider POI with multiple services and query time. With time dimension, MRRP aims to move from single-dimension shortest path searches to multi-dimension optimal paths searches. When there is no defined multi-dimensional advantage or disadvantage in decision support systems, skyline queries are suitable for searching for solutions that are not dominated by each other in different dimensions. Therefore, we address a problem called MRRP with Time-Urgency (MRRP-TU). To effectively solve MRRP-TU, we propose an MRRP-TU with multi-objective query anytime algorithm, It combines priority queues, dominate pruning strategy, and potential cost estimation. Users can choose their favorite route in the solution set through the length of the route and delay time. In the experiment, we used the Tainan city's POI data. In the optimal solution algorithm, our method can significantly increase our queries' speed and show the ability to return solutions quickly. Experiments on approximate solutions also show that our method can return high-quality solutions in a short time.

[1] C. S. Jensen, J. Kolářvr, T. B. Pedersen and I. Timko, "Nearest Neighbor Queries in Road Networks," In ACM GIS, pp. 1-8, Nov. 2003.
[2] E. W. Dijkstra, "A Note on Two Problems in Connection with Graphs," Numerische Mathematik, 1(1): 269-271, 1959.
[3] P. E. Hart, N. J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Trans. on Systems Science and Cybernetics, 4(2): 100-107, Feb. 2007.
[4] K. Menger, "Das Botenproblem," Ergebnisse Eines Mathematischen Kolloquiums, 2: 11-12, 1932.
[5] M. Albayraka and N. Allahverdib, "Development A New Mutation Operator to Solve the Traveling Salesman Problem by Aid of Genetic Algorithms," Expert Systems with Applications, 38(3): 1313-1320, Mar. 2011.
[6] J. Dai, B. Yang, C. Guo and Z. Ding, "Personalized Route Recommendation using Big Trajectory Data," In IEEE ICDE, pp. 543-554, Apr. 2015.
[7] F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios and S.-H. Teng, "On Trip Planning Queries in Spatial Databases," In SSTD, pp. 273-290, Aug. 2005.
[8] M. Sharifzadeh, M. Kolahdouzan and C. Shahabi, "The Optimal Sequenced Route Query," VLDB Journal, 17(4): 765-787, Jul. 2008.
[9] H. Chen, W. S. Ku, M. T. Sun and R. Zimmermann, "The Multi-Rule Partial Sequenced Route Query," In ACM GIS, Article No. 10. Nov. 2008.
[10] H. Liu, C. Jin, B. Yang and A. Zhou, "Finding Top-k Optimal Sequenced Routes," In IEEE ICDE, pp. 569-580, Feb. 2018.
[11] E. H. C. Lu, H. S. Chen and V. S. Tseng, "An Efficient Framework for Multirequest Route Planning in Urban Environments," IEEE Trans. on Intelligent Transportation Systems, 18(4): 869-879. Apr. 2017.
[12] Z. Song and N. Roussopoulos, "K-Nearest Neighbor Search for Moving Query Point," In SSTD, pp. 79-96, Jul. 2001.
[13] Y. Tao, D. Papadias and Q. Shen, "Continuous Nearest Neighbor Search," In VLDB, pp. 287-298, Aug. 2002.
[14] 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 IEEE ITSC, pp. 593-598, Oct. 2008.
[15] C.-C Lee, Y.-H. Wu and A. L. P. Chen. "Continuous Evaluation of Fastest Path Queries on Road Networks," In SSTD, pp. 20-37, Jul. 2007.
[16] E. H.-C. Lu, C.-W. Huang and V. S. Tseng, "Continuous Fastest Path Planning in Road Networks by Mining Real-Time Traffic Event Information," In ISII, pp. 969-974, Sept. 2009.
[17] J. Xu, Y. Gao, C. Liu, L. Zhao and Z. Ding, "Efficient Route Search on Hierarchical Dynamic Road Network," Distributed and Parallel Databases, 33: 227-252, Mar. 2014.
[18] I. Hefez, Y. Kanza and R. Levin, "Tarsius: A System for Traffic-aware Route Search under Conditions of Uncertainty," In ACM GIS, pp. 517-520, Nov. 2011.
[19] U. Demiryurek, F. Banaei-Kashani, C. Shahabi and A. Ranganathan, "Online Computation of Fastest Path in Time-Dependent Spatial Networks," In SSTD, pp. 92-111, Aug. 2011.
[20] X. Ma, S. Shekhar and H. Xiong, "Multi-Type Nearest Neighbor Queries in Road Networks with Time Window Constraints," In ACM GIS, pp. 484-487, Nov. 2009.
[21] X. Cao, L. Chen, G. Cong, J. Guan, N.-T. Phan and X. Xiao, "KORS: Keyword-aware Optimal Route Search System," In IEEE ICDE, pp. 1340-1343, Apr. 2013.
[22] C. F. Costa, M. A. Nascimento, J. A. Macêdo, Y. Theodoridis, N. Pelekis and J. Machado, "Optimal Time-Dependent Sequenced Route Queries in Road Networks," In ACM GIS, Article No. 56, Nov. 2015.
[23] Y. Huang, B. H. Lin and V. S. Tseng, "Efficient Multi-Destinations Route Planning with Deadlines and Cost Constraints," In IEEE MDM, pp. 228-233, May 2017.
[24] F. Luan, Q. Li, K. Cao and L. Wang, "Multi-Constrained Dominate Route Queries in Time-Dependent Road Networks," In Big Data, pp. 135-148, Oct. 2018.
[25] J. Li, J. Hu, V. Engel, C. Zong and X. Xia, "An Efficient Multi-request Route Planning Framework Based on Grid Index and Heuristic Function," In ADMA, pp 737-749, Nov. 2019.
[26] S. Borzsonyi, D. Kossmann and K. Stocker, "The Skyline Operator," In IEEE ICDE, pp. 421-430, Apr. 2001.
[27] X. Huang and C. S. Jensen, "In-Route Skyline Querying for Location-Based Services," In W2GIS, pp. 120-135, Nov. 2004.
[28] M. Sharifzadeh and C. Shahabi, "The Spatial Skyline Queries," In VLDB, pp. 751-762, Sept. 2006.
[29] Z. Huang, H. Lu, B. C. Ooi and A. Tung, "Continuous Skyline Queries for Moving Objects," IEEE Trans. on Knowledge and Data Engineering, 18(12): 1645-1658, Dec. 2006.
[30] K. Deng, X. Zhou and H. T. Shen, "Multi-Source Skyline Query Processing in Road Networks," In IEEE ICDE, pp. 796-805, Apr. 2007.
[31] B. Zheng, K. C. K. Lee, W.-C. Lee, "Location-Dependent Skyline Query," In IEEE MDM, pp. 148-155, Apr. 2008.
[32] H. P. Kriegel, M. Renz and M. Schubert, "Route Skyline Queries: A Multi-Preference Path Planning Approach," In IEEE ICDE, pp. 261-272, Mar. 2010.
[33] Y. K. Huang, C. H. Chang and C. Lee, "Continuous Distance-Based Skyline Queries in Road Networks," Information Systems, 37(7): 611-633, Nov. 2012.
[34] B. Yang, C. Guo, C. S. Jensen, M. Kaul and S. Shang, "Stochastic Skyline Route Planning under Time-Varying Uncertainty," In IEEE ICDE, pp. 136-147, Apr. 2014.
[35] M. Shekelyan, G. Josse and M. Schubert, "Linear Path Skylines in Multicriteria Networks," In IEEE ICDE, pp. 459-470, Apr. 2015.
[36] Q. Gong, H. Cao and P. Nagarkar, "Skyline Queries Constrained by Multi-cost Transportation Networks," In IEEE ICDE, pp. 926-937, Apr. 2019.
[37] P. Yawalkar and S. Ranu, "Route Recommendations on Road Networks for Arbitrary User Preference Functions," In IEEE ICDE, pp. 602-613, Apr. 2019.