隨著無線通訊網路和GPS的發展，相對的地理位置服務也迅速成長。譬如提供使用者兩地間的路線規劃的服務，如Google Map和Baidu Map。推薦使用者所在位置的活動或商家的服務資訊如Foursquare。除此之外，另有一類的服務，是將地圖的熱門地點標示為興趣點，並為這些興趣點分類。使用者可以根據需求選擇類別，而此服務則是為使用者所選擇的類別規劃一條經過相應類別之興趣點的路線。然而，直至目前為止，還沒有路線規劃相關的研究能夠完整和準確地考慮現實生活中跟時間有關的因素(興趣點的時間限制、停留時間、起始時間、活動與活動有先後順序和時間間隔)以及跟道路交通狀況有關的因素。因此，我們在本文中整合了這些因素，提出了一個新的路線查詢問題On Personal Tightest Trip Planning Query in Road Networks。這個查詢能夠更加符合使用者生活中的需求。接著，我們通過建立Cell-Based Index並提出四個演算法以效率和準確性為目標，合理地解決此問題。最後，我們用真實的資料和實驗來驗證其有效性。

With the development of wireless telecommunications networks and GPS, relative location-based services are growing rapidly. For example, there are some services that can provide route planning between two sites for users, such as Google Maps and Baidu Map. And other services that can recommend the activities or the service information about the business of users' locations. In addition, there is another service, that is marking the popular sites on a map as points of interest, and classifying these points of interest. Users can select the categories according to their requirements, and this service is planning a route visiting the points of interest of corresponding categories chosen by users. However, up to now, there is no route planning-related work can fully and exactly consider the time-related factors in real life (time constraints of points of interest, duration time, start time, activities have order constraints with temporal intervals with other activities) and the factors related to road traffic conditions. Therefore, we integrate these factors in this paper, and propose a new route query problem On Personal Tightest Trip Planning Query in Road Networks. This query can be more in line with the requirements of users' life. Then we reasonably solve this problem by building Cell-Based Index and proposing four algorithms with the goal of efficiency and accuracy. In the end, we use real data and experiments to verify their effectiveness.

[1] Egon Balas, “The prize collecting traveling salesman problem, ”. in Networks, vol. 19, no. 6, pp. 621-636, 1989.
[2] Xin Cao, Lisi Chen, Gao Cong, and Xiaokui Xiao, “Keyword-aware optimal route search,” in Keyword-aware optimal route search, 5(11):1136-1147, 2012.
[3] Haiquan Chen, Wei-Shinn Ku, Min-Te Sun, and Roger Zimmermann, “The multirule partial sequenced route query,” in Proceedings of the 16th ACM SIGSPATIAL
international conference on Advances in geographic information systems, pp. 1-10, 2008.
[4] Haiquan Chen, Wei-Shinn Ku, Min-Te Sun, and Roger Zimmermann, “The partial sequenced route query with traveling rules in road networks,” in Journal of
Geoinformatica, 15(3):541-569, 2011.
[5] Camila F. Costa, Mario A. Nascimento, Joss A. F. Macedo, Yannis Theodoridis, Nikos Pelekis, and Javam 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, 2015.
[6] Jian Dai, Bin Yang, Chenjuan Guo and Zhiming Ding, “Personalized route recommendation using big trajectory data,” in IEEE 31st International Conference on Data Engineering, pp. 543-554, 2015.
[7] Jian Dai, Chengfei Liu, Jiajie Xu, and Zhiming Ding, “On personalized and sequenced route planning,” in World Wide Web, 19(4):679-705, 2016.
[8] Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F.Werneck, “Customizable route planning in road networks,” in Transportation Science, 2015.
[9] Bolin Ding, Jeffrey Xu Yu, and Lu Qin, “Finding time-dependent shortest paths over large graphs,” in Proceedings of the 11th international conference on Extending database technology: Advances in database technology, pp. 205-216, 2008.
[10] Irina Dumitrescu, Stefan Ropke, Jean-Francois Cordeau, and Gilbert Laporte, “The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm,” in Mathematical Programming, vol. 121, no. 2, pp. 269-305, 2010.
[11] Shih Hsin Fang, Eric Hsueh Chan Lu, and Vincent S. Tseng, “Trip recommendation with multiple user constraints by integrating point-of-interests and travel packages,” in IEEE 15th International Conference on Mobile Data Management, pp. 33-42, 2014.
[12] Venkata M. V. Gunturi, Ernesto Nunes, KwangSoo Yang, and Shashi Shekhar, “A Critical-Time-Point Approach to all-Start-Time Lagrangian Shortest Paths: A
Summary of Results,” in Advances in Spatial and Temporal Databases, pp. 74-91, 2011.
[13] Tanzima Hashem, Tahrima Hashem, Mohammed Eunus Ali, and Lars Kulik, “Group trip planning queries in spatial databases,” in Proceedings of the 13th international conference on Advances in Spatial and Temporal Databases, pp. 259-276, 2013.
[14] Tanzima Hashem, Sukarna Barua, Mohammed Eunus Ali, Lars Kulik, and Egemen Tanin, “Efficient computation of trips with friends and families,” in Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 931-940, 2015.
[15] Hsun-Ping Hsieh, Cheng-Te Li, and Shou-De Lin, “Exploiting large-scale check-in data to recommend time-sensitive routes,” in Proceedings of the ACM SIGKDD International Workshop on Urban Computing, pp. 55-62, 2012.
[16] Hsun-Ping Hsieh and Cheng-Te Li, “Mining and planning time-aware routes from check-in data,” in Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pp. 481-490, 2014.
[17] E. Kanoulas, Yang Du, Tian Xia, and Donghui Zhang, “Finding fastest paths on a road network with speed patterns,” in Proceedings of the 22nd International Conference on Data Engineering, 2006.
[18] Yaron Kanza, Roy Levin, Eliyahu Safra, and Yehoshua Sagiv, “Interactive route search in the presence of order constraints,” in Proceedings of the VLDB Endowment, vol. 3, no. 1, pp. 117-128, 2010.
[19] Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua 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.
[20] Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios, and Shang-Hua Teng, “Trip planning queries in road network databases,” in Encyclopedia of GIS, pp. 1176-1181, 2008.
[21] Jing Li, Yin Yang, and Nikos Mamoulis, “Optimal Route Queries with Arbitrary Order Constraints,” in IEEE Transactions on Knowledge and Data Engineering, vol. 25, no. 5, pp. 1097-1110, 2013.
[22] Mengting Li, Xiang Li, and Jian Yin, “TORD problem and its solution based on big trajectories data,” in IEEE Transactions on Intelligent Transportation Systems, pp. 1666-1677, 2015.
[23] Eric Hsueh-Chan Lu, Ching-Yu Chen, and Vincent S. Tseng, “Trip-Mine: An Efficient Trip Planning Approach with Travel Time Constraints,” in 12th IEEE International Conference on Mobile Data Management, pp. 152-161, 2011.
[24] Eric Hsueh-Chan Lu, Ching-Yu Chen, and Vincent S. Tseng, “Personalized trip recommendation with multiple constraints by mining user check-in behaviors,” in Proceedings of the 20th International Conference on Advances in Geographic Information Systems, pp. 209-218, 2012.
[25] Rathore, Pramod Singh, and Atul Chaudhary, “Algorithm for Route Planning via Facilities with Time Dependent,” in International Journal of Computer Applications, 19(4), 2013.
[26] 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,” in 16th IEEE International Conference on Mobile Data Management, pp. 122-127, 2015.
[27] Mehdi Sharifzadeh, Mohammad Kolahdouzan, and Cyrus Shahabi, “The optimal sequenced route query,” in the International Journal on Very Large Data Bases, 17(4):765-787, 2008.
[28] S. S. Srivastava, S. Kumar, R. C. Garg, and P. Sen, “Generalized traveling salesman problem through n sets of nodes,” in Canadian Operational Research Society Journal, vol. 7, pp. 97-101, 1969.
[29] John N. Tsitsiklis, “Special cases of traveling salesman and repairman problems with time windows,” in Networks, vol. 22, no. 3, pp. 263-282, 1992.
[30] Jiajie Xu, Limin Guo, Zhiming Ding, Xiling Sun, and Chengfei Liu, “Traffic aware route planning in dynamic road networks,” in International Conference on Database Systems for Advanced Applications, pp. 576-591, 2012.
[31] Chenghao Zhu, Jiajie Xu, Chengfei Liu, Pengpeng Zhao, An Liu, and Lei Zhao, “Efficient Trip Planning for Maximizing User Satisfaction,” in International Conference on Database Systems for Advanced Applications, pp. 260-276, 2015.
[32] “Accommodation & traval in London,” https://cregyptology.org.uk/?page id=371.
[33] “Google Maps,” https://maps.google.com/.
[34] “Real Datasets for Spatial Databases: Road Networks and Points of Interest,”
https://www.cs.utah.edu/ lifeifei/SpatialDataset.htm.
[35] https://zh.wikipedia.org/wiki/%E8%88%88%E8%B6%A3%E9%BB%9E.