One-Way Search Algorithm for Multi-Request Route Planning

Abstract

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

Date of Award	2019
Original language	English
Supervisor	Hsueh-Chan Lu (Supervisor)