Travel time estimation from sparse floating car data with consistent path inference: A fixed point approach

• Published in: Transportation research. Part C, Emerging technologies Emerging technologies, 2017-12, Vol.85, p.628-643
• Main Authors: Rahmani, Mahmood, Koutsopoulos, Haris N., Jenelius, Erik
• Format: Article
• Language: English
• Subjects: Fixed point problem; Floating car data; Path inference; Travel time estimation
• ISSN: 0968-090X; 1879-2359; 1879-2359
• DOI: 10.1016/j.trc.2017.10.012

•A method for increased accuracy of link travel time estimation from sparse FCD.•A fixed point formulation of the path inference and travel time estimation problem.•Iterations converge quickly to solution with consistent paths and travel times.•Validation shows fixed point algorithm improves shortest path finding.•Impact can be significant for links representing local and side streets. Estimation of urban network link travel times from sparse floating car data (FCD) usually needs pre-processing, mainly map-matching and path inference for finding the most likely vehicle paths that are consistent with reported locations. Path inference requires a priori assumptions about link travel times; using unrealistic initial link travel times can bias the travel time estimation and subsequent identification of shortest paths. Thus, the combination of path inference and travel time estimation is a joint problem. This paper investigates the sensitivity of estimated travel times, and proposes a fixed point formulation of the simultaneous path inference and travel time estimation problem. The methodology is applied in a case study to estimate travel times from taxi FCD in Stockholm, Sweden. The results show that standard fixed point iterations converge quickly to a solution where input and output travel times are consistent. The solution is robust under different initial travel times assumptions and data sizes. Validation against actual path travel time measurements from the Google API and an instrumented vehicle deployed for this purpose shows that the fixed point algorithm improves shortest path finding. The results highlight the importance of the joint solution of the path inference and travel time estimation problem, in particular for accurate path finding and route optimization.