||One-Way Search Algorithm for Multi-Request Route Planning
||Department of Geomatics
Multi-request route planning
Shortest path problem
One-way search algorithm
適地性服務（Location-Based Service，LBS）普遍存在於我們的日常生活當中，使得我們的生活更加便利。其中一項熱門的主題為城市中興趣點（Point of Interest，POI）的路線規劃，即給予一個起點和目的地，以及使用者想去的地點或類型，路線規劃服務會給予使用者一或數條在距離或時間等評估方面上好的路線。在過去的相關研究僅考慮POI屬於一種類別，然而，一個POI可以提供多種服務以滿足使用者的需求，而考慮此特性的路線規劃即稱為多需求路線規劃（Multi-Request Route Planning，MRRP）。由於此類服務注重查詢的即時性，在過去的研究僅提供最佳路線的近似解；在本文中，我們提出單向搜尋（One-Way Search）演算法回答MRRP查詢，它結合分支定界法（Branch and Bound）與貪心演算法（Greedy Algorithm）的特點，因此能快速返回一個可行解；然而，如果讓此方法持續計算，最後可以得到最優解。據我們所知，這是第一項以最優解的方式回答MRRP查詢的工作。在實驗中，我們與近年也是找最優解的APTS/ANA*演算法做比較，實驗結果顯示我們的方法在執行時間和記憶體使用量上優於競爭方法。
Location-based services (LBS) are ubiquitous in our daily lives, making our lives more convenient. One of the popular topics is the route planning of point of interest (POI) in the urban environment, that is, giving a starting point and a destination, and the locations or types requested by the user, the route planning service will give the user one or more routes that are good in terms of distance or time spent. In previous related research, it was considered that POI belongs to only one category; however, a POI may provide multiple services to solve the needs of users, and the route planning considering this feature is called multi-request route planning (MRRP). Since such services require the immediacy of query responses, previous studies only provided an approximate solution to the best route. In this thesis, we propose the one-way search algorithm to answer MRRP queries, which combines branch and bound (B&B) and greedy algorithms, hence it can quickly respond to a feasible solution; however, if this method continues to compute, the optimal solution can be obtained. As far as we know, this is the first work to answer MRRP query optimally. In the experiment, we compare with the APTS/ANA* algorithm which can also find the optimal solution. The experimental results show that our method outperforms the competitive method in terms of execution time and memory usage.
List of Tables VI
List of Figures VII
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 2
1.3 Problem Scenario 2
1.4 Contribution 4
1.5 Organization 4
Chapter 2 Related Work 5
2.1 Shortest Path Problem 5
2.2 User-Demand-Oriented Route Planning 6
2.2.1 Static Road Network 7
2.2.2 Dynamic Road Network 8
Chapter 3 Problem Statement 11
Chapter 4 Methodology 14
4.1 Fundamental 15
4.1.1 Node Equivalence 15
4.1.2 Forward & Backward & Estimate 17
4.2 Pruning 18
4.2.1 Filter 18
4.2.2 Potential 19
4.2.3 Petrifaction 20
4.3 Wilting 21
4.4 Selection 22
4.5 Reverse Update 23
4.6 Algorithm 24
4.7 An Example of One-Way Search Algorithm 28
Chapter 5 Experimental Evaluation 34
5.1 Data Collection 34
5.2 Method Tuning 35
5.2.1 Comparison of Selection Strategies 35
5.2.2 Effect of Reverse Update 36
5.2.3 Effect of Pruning 37
5.3 Method Competition 38
5.3.1 Impact of Number of Requests NR 38
5.3.2 Impact of Number of POIs NP 39
5.3.3 Impact of Common and Rare Requests 40
5.3.4 Impact of Origin-Destination Distance 40
5.3.5 Ratio of Optimal Solution 41
5.4 Experimental Summary 42
Chapter 6 Conclusion and Future Work 45
 Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios and Shang-Hua Teng, "On Trip Planning Queries in Spatial Databases," International Symposium on Spatial and Temporal Databases, Springer, Berlin, Heidelberg, Pages 273-290, August 2005.
 Sharifzadeh, Mehdi, Mohammad Kolahdouzan and Cyrus Shahabi, "The Optimal Sequenced Route Query," The VLDB Journal—The International Journal on Very Large Data Bases, Volume 17, Issue 4, Pages 765-787, 2008.
 Eric Hsueh-Chan Lu, Huan-Sheng Chen and Vincent S. Tseng. "An Efficient Framework for Multirequest Route Planning in Urban Environments," IEEE Transactions on Intelligent Transportation Systems, Volume 18, Issue 4, Pages 869-879, April 2017.
 Karl Menger, "Das Botenproblem," Ergebnisse Eines Mathematischen Kolloquiums, Volume 2, Pages 11-12, 1932.
 Edsger Wybe Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, Volume 1, Issue 1, Pages 269-271, 1959.
 Peter E. Hart , Nils J. Nilsson and Bertram Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics, Volume 4, Issue 2, Pages 100-107, July 1968.
 Peter E. Hart , Nils J. Nilsson and Bertram Raphael, "Correction to A Formal Basis for the Heuristic Determination of Minimum Cost Paths," ACM SIGART Bulletin, Issue 37, Pages 28-29, December 1972.
 Richard E. Korf, "Depth-First Iterative-Deepening: An Optimal Admissible Tree Search," Artificial Intelligence, Volume 27, Issue 1, Pages 97-109, September 1985.
 Stuart Russell, "Efficient Memory-Bounded Search Methods". Proceedings of the 10th European Conference on Artificial Intelligence, Vienna, Austria, Pages 1-5, 1992.
 Maxim Likhachev, Geoffrey J. Gordon and Sebastian Thrun, "ARA*: Anytime A* with Provable Bounds on Sub-Optimality," Advances in Neural Information Processing Systems, Pages 767-774, 2004.
 Roni Stern, Ariel Felner, Jur van den Berg, Rami Puzis, Rajat Shah and Ken Goldberg, "Potential-Based Bounded-Cost Search and Anytime Non-Parametric A⁎," Artificial Intelligence, Volume 214, Pages 1-25, September 2014.
 Roni Tzvi Stern, Rami Puzis and Ariel Felner, "Potential Search: A Bounded-Cost Search Algorithm," Twenty-First International Conference on Automated Planning and Scheduling, March 2011.
 Jur van den Berg, Rajat Shah, Arthur Huang and Ken Goldberg, "Anytime Nonparametric A," Twenty-Fifth AAAI Conference on Artificial Intelligence, August 2011.
 Donald Ervin Knuth, "The Art of Computer Programming," Reading MA: Addison-Wisley, Volume 3, 1973.
 Nick Roussopoulos, Stephen Kelley and Frédéric Vincent, "Nearest Neighbor Queries," ACM Sigmod Record, Volume 24, Issue 2, Pages 71-79, June 1995.
 Mehdi Sharifzadeh and Cyrus Shahabi, "Processing Optimal Sequenced Route Queries Using Voronoi Diagrams," GeoInformatica, Volume 12, Issue 4, Pages 411-433, December 2008.
 Xiaobin Ma, Shashi Shekhar, Hui Xiong and Pusheng Zhang, "Exploiting a Page-Level Upper Bound for Multi-Type Nearest Neighbor Queries," Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems, Pages 179-186, November 2006.
 Haiquan Chen, Wei-Shinn Ku, Min-Te Sun and Roger Zimmermann, "The Multi-Rule Partial Sequenced Route Query," Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Pages 1-10, November 2008.
 Jing Li, Yin David Yang and Nikos Mamoulis, "Optimal Route Queries with Arbitrary Order Constraints," IEEE Transactions on Knowledge and Data Engineering, Volume 25, Issue 5, Pages 1097-1110, February 2012.
 Yaron Kanza, Roy Levin, Eliyahu Safra and Yehoshua Sagiv, "Interactive Route Search in the Presence of Order Constraints," Proceedings of the VLDB Endowment, Volume 3, Issue 1-2, Pages 117-128, September 2010.
 Jochen Eisner and Stefan Funke, "Sequenced Route Queries: Getting Things Done on the Way Back Home," Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Pages 502-505, November 2012.
 Yutaka Ohsawa, Htoo Htoo, Noboru Sonehara and Masao Sakauchi, "Sequenced Route Query in Road Network Distance Based on Incremental Euclidean Restriction," International Conference on Database and Expert Systems Applications, Pages 484-491, Berlin, Heidelberg, September 2012.
 Tanzima Hashem, Tahrima Hashem, Mohammed Eunus Ali and Lars Kulik, "Group Trip Planning Queries in Spatial Databases," International Symposium on Spatial and Temporal Databases. Pages 259-276, Berlin, Heidelberg, August 2013.
 Tanzima Hashem, Sukarna Barua, Mohammed Eunus Ali, Lars Kulik and Egemen Tanin, "Efficient Computation of Trips with Friends and Families," Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, Pages 931-940, October 2015.
 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," 2015 16th IEEE International Conference on Mobile Data Management, Volume 1, June 2015.
 Elham Ahmadi and Mario A. Nascimento, "A Mixed Breadth-Depth First Search Strategy for Sequenced Group Trip Planning Queries," 2015 16th IEEE International Conference on Mobile Data Management. Volume 1, Pages 24-33, June 2015.
 Xiaobin Ma, Shashi Shekhar and Hui Xiong, "Multi-Type Nearest Neighbor Queries in Road Networks With Time Window Constraints," GIS, Pages 484-487, September 2009.
 Camila F. Costa, Mario A. Nascimento, José A. F. Macêdo, Yannis Theodoridis, Nikos Pelekis and Javam Machado, "Optimal Time-dependent Sequenced Route Queries in Road Networks," Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, November 2015.
 Xiang Lian and Lei Chen, "Trip Planner Over Probabilistic Time-Dependent Road Networks," IEEE Transactions on Knowledge and Data Engineering, Volume 26, Issue 8, Pages 2058-2071, August 2014.
 Yu Huang, Bo-Hau Lin and Vincent S. Tseng, "Efficient Multi-Destinations Route Planning with Deadlines and Cost Constraints," 2017 18th IEEE International Conference on Mobile Data Management, Pages 228-233, May 2017.