文章基本信息

标题：An Efficient Monte Carlo-Based Probabilistic Time-Dependent Routing Calculation Targeting a Server-Side Car Navigation System
本地全文：下载
作者：Emanuele Vitali ; Davide Gadioli ; Gianluca Palermo 等
期刊名称：IEEE Transactions on Emerging Topics in Computing
印刷版ISSN：2168-6750
出版年度：2021
卷号：9
期号：2
页码：1006-1019
DOI：10.1109/TETC.2019.2919801
出版社：IEEE Publishing
摘要：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.
关键词：High performance computing;approximate computing;adaptive applications;smart cities;vehicle routing