Trade-off Aware Sequenced Routing Queries (or OSR Queries when POIs are not Free)
| Autor: | Francesco Lettich, Samiul Anwar, Mario A. Nascimento |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Skyline
Sequence Linear Skylines Theoretical computer science Settore INF/01 - Informatica Point of interest Trade-off Aware Sequenced Routing Computer science Total cost 02 engineering and technology Optimal Sequenced Routing Road Networks 020204 information systems 0202 electrical engineering electronic engineering information engineering Overhead (computing) 020201 artificial intelligence & image processing Pruning (decision trees) Routing (electronic design automation) Linear combination |
| Zdroj: | MDM |
| DOI: | 10.1109/mdm48529.2020.00027 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|