Estimating traversal time is an essential problem in urban computing. Traditional methods learn a predictive model from user traces collected in a central server, which potentially threatens the privacy of the users, and which may be hard to realize in an online setting where communication with large amounts of cars is needed. In this paper, we propose a new approach to solve these problems by proposing a a privacy-friendly algorithm requiring only local communication. First, we introduce a new optimisation-based formalisation, which can take into account user-specific driving styles and the homophily of the traffic in road networks. We then discuss how we can solve this problem in a decentralised setting, where each user stores his/her sensitive data locally (without uploading it to a central server) and only shares indirect information in a peer-to-peer manner. Finally, we discuss strategies to learn the model without revealing sensitive information such as locations and user identities.