Aggregate Nearest Neighbor Queries With Service Time Constraints In Time-Dependent Road Network

Aggregate nearest neighbor(ANN)queries are to find the point of interest(POI)with the smallest aggregation function(SUM or MAX)from multiple query points in space,which is one of the common spatiotemporal queries.The travel time of the same segment in the road network is often different at different departure times.The spatiotemporal queries under the time dependent road network have received more and more attention.Existing studies on ANN queries mostly focus on Euclidean space and static road network.The method of calculating the centroid of the query points or pre-calculation based on the shortest path is used by most of the existing technologies.However,in a time dependent road network,the edge weight changes over time,thus the centroid of the query points changes dynamically.In addition,the shortest path in time dependent road network also changes dynamically.Those technologies cannot be directly applied to solve time dependent ANN(TDANN)queries.In this paper,we consider the waiting time caused by the constraints of the service time of POI,and define the TDANN queries with service time constraints.Given a time dependent road network,a POI set including both the locations and service times,a queries set and a departure time t.TDANN queries are to find the best POI which minimizes the aggregate value for all the queries,the aggregate value is the sum of the travel time from each query point to the POI and the waiting time to be served.Firstly,the time dependent lower bound graph is used to perform spatial pruning on the road network to obtain a set of candidate POIs based on the service time of POI.Secondly,combined with the incremental network expansion(INE)and the A* algorithm,the road network is expanded from each query point until a common POI is found.The traveling time and waiting time are considered in the heuristic function.In addition,in order to make the heuristic value closer to the actual value,according to the change rule of the edge weight,an improved algorithm based on multiple lower bound graphs is proposed.The performance of the proposed algorithm is evaluated under real road network.Experimental results show that the query time of the proposed algorithm is 73.61% lower than existed algorithm,and the query time of the improved algorithm based on multiple lower bound graphs is reduced by 22.9%.