A*-based Solutions for KNN Queries with Operating Time Constraints in Time-Dependent Road Networks

We consider the problem of finding the k nearest points of interest from a given location in time-dependent road networks, i.e., One where travel time along each edge is a function of the departure time, and where the operating times of the points of interest are also taken into consideration. More specifically, we address the following query: find the k points of interest in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the point of interest and the waiting time, if it is closed. Previous works have proposed solutions to answer kNN queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters.