TY - GEN
T1 - An Efficient Method for Multi-request Route Search
AU - Lu, Eric Hsueh Chan
AU - Syu, Sin Sian
N1 - Funding Information:
Acknowledgement. This research was supported by Ministry of Science and Technology, Taiwan, R.O.C. under grant no. MOST 109-2121-M-006-013-MY2 and MOST 109-2121-M-006-005-.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - Location-based services are ubiquitous in our daily lives, which make our lives more convenient. One of the popular topics is the route planning for Point of Interest in the urban environments. In this article, we study on Multi-Request Route Planning. The previous research only provided an approximate solution to this problem. In this work, we investigate the possibility of finding the best route within a reasonable time and propose the One-way Search algorithm. This method expands the node in one direction in one search, and each search will reduce the candidate nodes for the next search. In the experiment, we compare our method with the Anytime Potential Search/Anytime Non-Parametric A* algorithm, which was proposed in recent years and is also an optimal solution. The evaluation is based on two real-world datasets, and the results show that our method outperforms the competition method in terms of execution time and memory usage.
AB - Location-based services are ubiquitous in our daily lives, which make our lives more convenient. One of the popular topics is the route planning for Point of Interest in the urban environments. In this article, we study on Multi-Request Route Planning. The previous research only provided an approximate solution to this problem. In this work, we investigate the possibility of finding the best route within a reasonable time and propose the One-way Search algorithm. This method expands the node in one direction in one search, and each search will reduce the candidate nodes for the next search. In the experiment, we compare our method with the Anytime Potential Search/Anytime Non-Parametric A* algorithm, which was proposed in recent years and is also an optimal solution. The evaluation is based on two real-world datasets, and the results show that our method outperforms the competition method in terms of execution time and memory usage.
UR - http://www.scopus.com/inward/record.url?scp=85104739026&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85104739026&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-73280-6_51
DO - 10.1007/978-3-030-73280-6_51
M3 - Conference contribution
AN - SCOPUS:85104739026
SN - 9783030732790
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 643
EP - 652
BT - Intelligent Information and Database Systems - 13th Asian Conference, ACIIDS 2021, Proceedings
A2 - Nguyen, Ngoc Thanh
A2 - Chittayasothorn, Suphamit
A2 - Niyato, Dusit
A2 - Trawiński, Bogdan
PB - Springer Science and Business Media Deutschland GmbH
T2 - 13th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2021
Y2 - 7 April 2021 through 10 April 2021
ER -