Fast estimation of point-to-point travel times for real-time vehicle routing

To provide the optimal allocation of requests to the available fleet vehicles, routing algorithms typically assume the availability of complete and correct information about point-to-point travel times. Actually, in real applications non-recurrent events and traffic conditions make the estimation and the prediction of such travel times a difficult task, further complicated in real-time applications by the dynamicity of the information and the number of needed estimates. In this paper we present a complete methodology to achieve a computation of point-to-point travel times on a large network which proves to be both extremely fast and consistent with dynamically updated traffic information.