An Efficient Monte Carlo-Based Probabilistic Time-Dependent Routing Calculation Targeting a Server-Side Car Navigation System

• Tipo: Artigo em Revista Científica Internacional
• Data: 2021

Autores

Vitali, E (Autor) Outra; Gadioli, D (Autor) Outra; Palermo, G (Autor) Outra; Golasowski, M (Autor) Outra; João Bispo (Autor) FEUP; Pinto, P (Autor) Outra; Martinovic, J (Autor) Outra; Slaninova, K (Autor) Outra; João M. P. Cardoso (Autor) FEUP; Silvano, C (Autor) Outra

Revista

Título: IEEE Transactions on Emerging Topics in Computing

Vol. 9

Páginas: 1006-1019

ISSN: 2168-6750

Editora: IEEE

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 6 Citações

Outras Informações

ID Authenticus: P-00Q-A6Y

DOI: 10.1109/tetc.2019.2919801

Abstract (EN): Incorporating speed probability distribution to the computation of the route planning in car navigation systems guarantees more accurate and precise responses. In this paper, we propose a novel approach for selecting dynamically the number of samples used for the Monte Carlo simulation to solve the Probabilistic Time-Dependent Routing (PTDR) problem, thus improving the computation efficiency. The proposed method is used to determine in a proactive manner the number of simulations to be done to extract the travel-time estimation for each specific request, while respecting an error threshold as output quality level. The methodology requires a reduced effort on the application development side. We adopted an aspect-oriented programming language (LARA) together with a flexible dynamic autotuning library (mARGOt) respectively to instrument the code and to make decisions on tuning the number of samples to improve the execution efficiency. Experimental results demonstrate that the proposed adaptive approach saves a large fraction of simulations (between 36 and 81 percent) with respect to a static approach, while considering different traffic situations, paths and error requirements. Given the negligible runtime overhead of the proposed approach, the execution-time speedup is between 1.5x and 5.1x. This speedup is reflected at the infrastructure-level in terms of a reduction of 36 percent of the computing resources needed to support the whole navigation pipeline.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 14