Estimation of trip travel time distribution using a generalized Markov chain approach

The increasing availability of opportunistic and dedicated sensors is transforming a once data-starved transport field into one of the most data-rich. While link-level travel time information can be derived or inferred from this data, methods fokestimation of trip travel times between an origin and a destination pair are still evolving and limited, especially in the context of probability distribution estimation. This paper proposes a generalized Markov chain approach for estimating the probability distribution of trip travel times from link travel time distributions and takes into consideration correlations in time and space. The proposed approach consists of three major components, namely state definition, transition probabilities estimation and probability distribution estimation. A heuristic clustering method, based on Gaussian mixture models, has been developed to cluster link travel time observations with regard to their homogeneity and underlying traffic conditions. A transition probability estimation model is developed as a function of link characteristics and trip conditions using a logit model. By applying a Markov chain procedure, the probability distribution of trip travel times is estimated as the combination of Markov path travel time distributions weighted by their corresponding occurrence probabilities. The link travel time distribution is conditioned on the traffic conditions of the current link that can be estimated from historical observations. A moment generating function based algorithm is used to approximate the Markov path travel time distribution as the sum of correlated link travel time distributions conditional on traffic conditions. The proposed approach is applied in a transit case study using automatic vehicle location data. The results indicate that the method is effective and efficient, especially when correlations and multimodal distributions exist. (C) 2016 Elsevier Ltd. All rights reserved.