Centre de documentation
scientifique

TARS: traffic-aware route search / Roy Levin in Geoinformatica, vol 18 n° 3 (July 2014)  

Public [article]  inGeoinformatica > vol 18 n° 3 (July 2014) . - pp 461-500 Titre : TARS: traffic-aware route search Type de document : Article/Communication Auteurs : Roy Levin, Auteur ; Yaron Kanza, Auteur Année de publication : 2014 Article en page(s) : pp 461-500 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Navigation et positionnement [Termes IGN] méthode heuristique [Termes IGN] navigation automobile [Termes IGN] requête spatiale [Termes IGN] système d'information géographique [Termes IGN] trafic routier Résumé : (Auteur) In a traffic-aware route search (TARS), the user provides start and target locations and sets of search terms. The goal is to find the fastest route from the start location to the target via geographic entities (points of interest) that correspond to the search terms, while taking into account variations in the travel speed due to changes in traffic conditions, and the possibility that some visited entities will not satisfy the search requirements. A TARS query may include temporal constraints and order constraints that restrict the order by which entities are visited. Since TARS generalizes the Traveling-Salesperson Problem, it is an NP-hard problem. Thus, it is unlikely to find a polynomial-time algorithm for evaluating TARS queries. Hence, we present in this paper three heuristics to answer TARS queries--a local greedy approach, a global greedy approach and an algorithm that computes a linear approximation to the travel speeds, formulates the problem as a Mixed Integer Linear Programming (MILP) problem and uses a solver to find a solution. We provide an experimental evaluation based on actual traffic data and show that using a MILP solver to find a solution is effective and can be done within a limited running time in many real-life scenarios. The local-greedy approach is the least effective in finding a fast route, however, it has the best running time and it is the most scalable. Numéro de notice : A2014-498 Affiliation des auteurs : non IGN Thématique : POSITIONNEMENT Nature : Article DOI : 10.1007/s10707-013-0185-z Date de publication en ligne : 07/07/2013 En ligne : https://doi.org/10.1007/s10707-013-0185-z Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=74090 [article]

Exemplaires(1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
057-2014031	RAB	Revue	Centre de documentation	En réserve L003	Disponible