In this paper we present an algorithm for optimal processing of time-dependent sequenced route queries in road networks, i.e., given a road network where the travel time over an edge is time-dependent and a given ordered list of categories of interest, we find the fastest route between an origin and destination that passes through a sequence of points of interest belonging to each of the specified categories of interest. Our approach uses the A* search paradigm equipped with an admissible heuristic function, thus guaranteed to yield the optimal solution, along with a pruning scheme for further reducing the search space. Our experiments using a real data set have shown our proposed solution to be up to two orders of magnitude faster than a previous solution extended to handle time-dependency.
['Camila F. Costa', 'Mario A. Nascimento', 'José Antônio Fernandes de Macêdo', 'Yannis Theodoridis', 'Nikos Pelekis', 'Javam C. Machado']
Optimal time-dependent sequenced route queries in road networks