KIT | KIT-Bibliothek | Impressum | Datenschutz

Visit Places on YourWay: A Skyline Approach in Time-Dependent Networks

Taghizadeh, Saeed; Elekes, Abel; Schäler, Martin

Many people take the same path every day, such as taking a specific autobahn to get home from work. However, one needs to frequently divert from this path, e.g., to visit a Point of Interest (POI) from a category like the category of restaurants or ATMs. Usually, people want to minimize not only their overall travel cost but also their detour cost, i.e., one wants to return to the known path as fast as possible. Finding such a POI minimizing both costs efficiently is highly challenging in case one considers time-dependent road networks which are the case in real-world scenarios. For such road networks time decency means the time a user needs to traverse a road, heavily depends on the user’s arrival time on that road. Prior works have several limitations, such as assuming that travel costs are coming from a metric space and do not change over time. Both assumptions hardly match real-world requirements: Just think of traffic jams at the rush hour. To overcome these limitations, we study how to solve this problem considering time-dependent road networks relying on linear skylines. Our main contribution is an efficient algorithm called STACY to find all non-dominated paths. ... mehr

Open Access Logo

Volltext §
DOI: 10.5445/IR/1000129375
Veröffentlicht am 05.02.2021
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Forschungsbericht/Preprint
Publikationsmonat/-jahr 02.2021
Sprache Englisch
Identifikator ISSN: 2190-4782
KITopen-ID: 1000129375
Verlag Karlsruher Institut für Technologie (KIT)
Umfang [12] S.
Serie Karlsruhe Reports in Informatics ; 2021,1
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page