Trade-off Aware Sequenced Routing Queries (or OSR Queries when POIs are not Free)

The well-known Optimal Sequenced Routing (OSR) query considers a traveller that needs to stop by some cost-free points of interest (POIs), each belonging to a given strict sequence of categories of interest (COIs), while minimizing only the distance traveled. In this paper we extend the OSR query by adding the constraint that (1) each POI yields a non-null cost and that (2) the traveller wishes to minimize the travel distance as well as the total cost of POIs he/she stops by. We name this new query as Trade-Off Aware Sequenced Routing (TASeR). The challenging aspect of this query is that it is not always possible to optimize both travel distance and total POI cost simultaneously. As well, combining both criteria into a single one with predetermined weights may not be desirable or even feasible. As our main contribution we make use of the linear skyline paradigm, along with provably correct pruning criteria, to propose an approach that finds all optimal solutions for any linear combination of the two competing criteria very efficiently. Our experiments using real city-scale data show that our proposed approach can obtain optimal linear skyline sets in sub-second processing time for reasonably sized instances of the TASeR query. Moreover, we show that any instance of the traditional OSR query can be easily modeled as a TASeR query, hence, our proposed approach can also solve OSR queries at the expense of negligible overhead.