Estimation of Path Travel Time Distributions in Stochastic Time-Varying Networks with Correlations

Abstract

Transportation research has increasingly focused on the modeling of travel time uncertainty in transportation networks. From a user’s perspective, the performance of the network is experienced at the level of a path, and, as such, knowledge of variability of travel times along paths contemplated by the user is necessary. This paper focuses on developing approaches for the estimation of path travel time distributions in stochastic time-varying networks so as to capture generalized correlations between link travel times. Specifically, the goal is to develop methods to estimate path travel time distributions for any path in the networks by synthesizing available trajectory data from various portions of the path, and this paper addresses that problem in a two-fold manner. Firstly, a Monte Carlo simulation (MCS)-based approach is presented for the convolution of time-varying random variables with general correlation structures and distribution shapes. Secondly, a combinatorial data-mining approach is developed, which aims to utilize sparse trajectory data for the estimation of path travel time distributions by implicitly capturing the complex correlation structure in the network travel times. Numerical results indicate that the MCS approach allowing for time-dependence and a time-varying correlation structure outperforms other approaches, and that its performance is robust with respect to different path travel time distributions. Additionally, using the path segmentations from the segment search approach with a MCS approach with time-dependence also produces accurate and robust estimates of the path travel time distributions with the added benefit of shorter computation times.

The performance of transportation networks is susceptible to fluctuations that can be caused by a combination of sources, such as traffic incidents, work zones, weather conditions, special events, control devices, variations in demand, and so forth. ( 1 ) Such fluctuations cause uncertainty in the network and, as a result, the travel time between two points in the network can be viewed as a random variable with a non-stationary distribution. Travel time is stochastic in that its realized value can vary and only a range of travel times may be given with confidence, and its distribution is non-stationary since it changes with time or because of changes in exogeneous operational conditions. Networks characterized with such travel times are referred to as stochastic time-varying (STV) networks ( 2 ). The structure of the network and the presence of travel patterns and dependence of traffic flow between the links additionally impose spatio-temporal dependencies between travel times across the network.

Measuring travel times is crucial in assessing the operational efficiency of the network. Behavioral studies have also shown the importance of travel time reliability to users’ satisfaction with a network, as well as their resulting travel and activity choices ( 3 ). Therefore, measuring and modeling travel time reliability is an important aspect of modeling and evaluating transportation networks, and measures of travel time reliability should recognize the travelers’ experience of the transportation system, which is through routes or trajectories ( 4 , 5 ). A key question for a given user, whether a traveler or a goods shipping company, pertains to the variability of travel times along the paths contemplated by the user, rather than on individual links or in the network as a whole. Answering this question has led to another line of research focused on routing in STV networks based on reliability objectives. Studies in this body of literature often focus on finding paths with the least expected travel time (LET), or using reliability-based rules such as the shortest path problem with on-time arrival probability (SPOTAR) or minimum travel time budget paths (MTTBP) ( 2 , 6 – 13 ). Such studies rely on ability to estimate path travel time distributions for any path in the network ( 10 ).

Background

The question of estimating path travel time distributions can be answered in several ways, depending on the available information. A very large sample of trajectory data may allow for distributions to be constructed from experienced travel times for all users who have traveled the path of interest. However, to construct travel time distributions along any user-specified path, including those with very few observed vehicle traversals, it is necessary to identify vehicle traversals of segments or links along the path so as to synthesize the path’s travel time distribution. This study is concerned with the methodological challenge of how to efficiently combine link- (or segment)-level distributions from available trajectories to construct path travel time distributions when link travel times in the network are generally correlated over space and time. However, estimating path travel time distributions with general correlation patterns can be challenging. Firstly, estimating correlations requires many observations, especially for time-varying variables. Moreover, convolving the link-level distributions requires numerical integration or simulation techniques, since the convolution integrals for general distributions do not have closed-form analytical solutions.

Researchers have focused on the use of different types of data and various methods for estimating travel time distributions. Ramezani and Geroliminis use probe vehicles’ travel times along all links in an arterial route and estimate the route travel time distributions with a Markov chain approach where spatial correlations between successive links on a path are captured using transition probabilities ( 14 ). Such an approach is limited by the assumption that travel time dependencies exist only between consecutive links and that such transitions between different links are conditionally independent. Another study synthesizes route travel time distributions based on segment-level temporal and spatial distributions by adding percentile-by-percentile values of the travel times ( 15 ). However, this technique may not be appropriate for generalized correlation structures. In relation to estimating the moments of a travel time distribution, Eisele et al. devise a method for estimating the mean and variance of route travel times, while a study by Chen and Osorio presents an analytic approach for approximating the standard deviation of travel times ( 16 , 17 ). Chen et al. introduced a copula-based model for estimating path travel time distributions on urban arterials which was shown to be superior to convolution and distribution-fitting methods ( 18 ). However, the authors point out that the inputs to the proposed model are segment travel times, the marginal distributions for which need to be specified or estimated separately. A few other relevant studies use Markov Chain and Gaussian mixture models and specifically focus on incorporating signalized intersections ( 20 ).

Some studies that focus on the estimation of network travel time distributions may also be relevant. Specifically, Mahmassani et al. demonstrate that the mean and standard deviation of network travel times are highly positively correlated ( 21 ). Hunter et al. present a method for estimating travel time distributions in a network based on probe vehicle data, under the assumption that link travel times are follow a multivariate Gaussian distribution ( 22 ). Westgate et al. propose statistical methods to estimate travel time distributions on a road network using Markov chain Monte Carlo approaches using GPS-enabled ambulance data ( 23 ). However, being a special type of network travel, ambulance trip data may misrepresent the features of urban traffic networks. Rahmani et al. point out some potential pitfalls when estimating travel time distributions, specifically focusing on trajectories with incomplete traversal of the route, non-uniform coverage of the route in relation to the number of observations, and using a non-representative vehicle sample ( 19 ).

Problem Statement and Contributions

The focus of this study is on approaches for the estimation of path travel time distributions in STV networks which capture generalized correlations between link travel times in the network. This study contributes to the existing literature in a two-fold manner. Firstly, it presents a Monte Carlo simulation (MCS)-based approach for the convolution of time-varying random variables with general correlation structures and distribution shapes. Secondly, it presents a combinatorial data-mining approach for utilizing sparse trajectory data for the estimation of path travel time distributions which implicitly captures the complex correlation structure in the network travel times. The remainder of this paper is organized as follows. The next section provides the problem definition and the section after that introduces the proposed methods for this problem. The penultimate section presents the numerical experiments and their results. The final section provides a discussion, draws conclusions, and points to future work with a view toward application.

Problem Definition

The primary focus of this study is the problem of efficient and accurate estimation of travel time distributions on user-specified paths across STV networks with generalized spatio-temporal dependencies. Since stochasticity of travel times in the network can be a result of several factors, capturing generalized spatio-temporal dependencies between link travel times relies on the availability of trajectory data. Therefore, assuming that some trajectory data is available, the methodological challenge of estimating path travel time distributions on any given route in the network is two-fold.

The first methodological challenge is one of probability modeling, where, given the distributions of individual random variables, the aim is to estimate the distribution of their sum by solving a convolution integral while allowing for generalized correlations. The fundamental problem is to formulate and solve a convoluting integral where random variables can be correlated and have varying distribution forms. A path P composed of N consecutive segments ${l_{1}, l_{2}, \dots, l_{N}}$ where travel time on segment $l_{i} \forall i \in {1, 2, \dots, N}$ is a random variable $θ_{i}$ whose distribution is denoted by $π_{i}$ . In this notation, the segments comprising path P can be sub-paths of varying lengths, where a special case would be to consider the individual links comprising the path. The distribution of travel times $Θ_{P}$ on the path P is obtained by solving the appropriate convolution integral. In the simplest case, assuming independent random variables, the convolution integral for two random variables can be written as:

(π_{i} * π_{j}) (T) = \int_{- \infty}^{\infty} π_{i} (τ) π_{j} (T - τ) d τ

If the random variables have time-varying distributions, so that $π_{i}$ is different at each time t, the convolution integral at time t becomes:

{(π_{i} * π_{j})}^{t} (T) = \int_{- \infty}^{\infty} π_{i}^{t} (τ) π_{j}^{t + τ} (T - τ) d τ

Additionally, for travel time random variables where $π_{i}$ are supported only on $[0, \infty)$ in general, or some specific range $[t_{\min}, t_{\max}]$ , the integral can be appropriately truncated. Dependencies between segment travel times can be specified in different ways depending on the application. Firstly, distributions may vary based on exogeneous conditions apart from time, such as weather or seasonal attributes, or different operational states that may be defined on day of the week or demand level. Without loss of specificity, let $ζ$ be an operational condition indicator, and suppose that operation conditions may be different, yet correlated, in different segments, then the integral is further specified by:

{(π_{i} * π_{j})}^{t} (T) = \int_{- \infty}^{\infty} π_{i}^{ζ_{i}, t} (τ) π_{j}^{ζ_{j} | ζ_{i}, t + τ} (T - τ) d τ

The final generalization involves the case where $θ_{i}^{t_{i}}, θ_{j}^{t_{j}}$ are jointly distributed in a time-varying manner so that that the joint distribution will vary over the combination of times $t_{i}, t_{j}$ . Throughout this study it becomes apparent that it is the correct estimation of the correlation structure between jointly distributed link travel times that presents the biggest challenge.

The second challenge, that is concerned with identifying appropriate segments that may be used to best synthesize the travel time distribution of a path, is a challenge of data mining. Identifying the appropriate segments depends on available trajectory data and the travel patterns captured in it, as well as the spatio-temporal dependencies in the network. A simple solution is to use link-level travel time distributions, but in some cases it may be useful to consider using sub-paths of the path in question so that some of the correlations between link travel times can be implicitly captured within known travel time distributions at the sub-path level.

Therefore, the problem of estimating travel time distributions along user-specified paths in this study will be addressed in two manners: firstly, by presenting simulation-based approaches to estimate the convolution of link travel time distributions that may have generalized correlation structures, and, secondly, by developing data-mining approaches for synthesizing trajectory data at the segment level so as to implicitly capture existing correlation structures.

Methodology

This section presents the methodology for the problem defined above. Firstly, simulation-based approaches for the estimation of the convolution of link travel time distributions with spatio-temporal dependencies are presented. Subsequently, a combinatorial data-mining search approach for synthesizing trajectory data is proposed. The former simulation-based estimation approaches are general and can be utilized for the convolution of link- or segment-level travel time distributions, including the path segmentations resulting from latter approach. However, it should be noted that the segment search approach is intended be used as an alternative to methods that involve correlation estimation, since it aims to implicitly capture spatial correlations so that simple convolution estimation methods—that is, assuming spatial independence—would be sufficient.

Simulation-Based Approaches for Convolution Estimation

Suppose a path P is composed of N consecutive segments ${l_{1}, l_{2}, \dots, l_{N}}$ where travel time on segment $l_{i} \forall i \in {1, 2, \dots, N}$ is a random variable $θ_{i}$ whose distribution is denoted by $π_{i}$ . Let $Θ_{P}$ be the travel time random variable for path P, with a corresponding cumulative distribution function (CDF) $U_{P}$ such that for any given travel time T, $U_{P} (T) = P (Θ_{P} \leq T)$ .

Assuming Independent Random Link Travel Times

Under the assumption that travel time distributions are time-invariant, then $U_{P}$ can be written as the following convolution:

\begin{matrix} U_{P} (T) = \int_{0}^{\infty} \dots (\int_{0}^{\infty} (\int_{0}^{\infty} π_{1} (τ_{1}) \cdot π_{2} (τ_{2} - τ_{1}) d τ_{1}) \cdot \\ π_{3} (τ_{3} - τ_{1} - τ_{2}) d τ_{2} \end{matrix}) \dots π_{N} (T - \sum_{j = 1}^{N - 1} τ_{j}) d τ_{N - 1}

In this case, an MCS approach for independent random variables, abbreviated MCS-I, can be used to obtain an estimation of the path travel time distribution:

For iterations $j \in {1, \dots M}$ :

Observations for link travel times ${\tilde{θ}}_{i}^{j} \forall i \in {1, 2, \dots, N}$ are sampled randomly and independently

Let ${\tilde{Θ}}_{P}^{j} = \sum_{i = 1}^{N} {\tilde{θ}}_{i}^{j}$

Then the sample ${\tilde{Θ}}_{P}^{j} \forall j \in {1, \dots, M}$ estimates the distribution of $Θ_{P}$ .

Assuming Random Link Travel Times with Time-Varying Distributions

Suppose now that the distributions of link travel times vary over time. If a planning horizon of length $T_{P}$ is being considered, over which the path travel time distribution is to be estimated, it is assumed that it is possible to identify a discretization of the time period $T_{P}$ into L time-bins of equal duration $δ$ so that link travel times for each time bin are given by $π_{i}^{t} \forall i \in {1, \dots, N}, t \in {0, \dots, L - 1}$ . Therefore, link travel time distributions are assumed to be constant within each time-bin but vary from one time-bin to the next. Then, the MCS approach can be extended to account for time dependence (abbreviated MCS-TD):

For iterations $j \in {1, \dots, M}$ :

A time-bin $t_{j}$ is chosen randomly from ${0, \dots, L - 1}$

For the first segment, a link travel time ${\tilde{θ}}_{1}$ is sampled from $π_{1}^{t_{1}}$ where $t_{1} = t_{j}$

For each next segment, a link travel time from ${\tilde{θ}}_{i}$ is sampled from $π_{i}^{t_{i}}$ where $t_{i} = \frac{\sum_{l = 0}^{i} {\tilde{θ}}_{l}}{δ}$ , that is, the next time-bin based on previously sampled travel times on the path.

Let ${\tilde{Θ}}_{P}^{j} = \sum_{i = 1}^{N} {\tilde{θ}}_{i}$

Assuming Random Correlated Link Travel Times with Time-Varying Distributions

If it is assumed that the link travel times not only have time-varying distributions but are also correlated with one-another, the sampling approach needs to be adjusted so that link travel times are sampled with correlation. However, when considering STV networks, the approach for estimating correlations between link travel times becomes an added source of difficulty. It could be assumed that, while the distributions of link travel times vary over time, the correlations are stationary. A stationary correlation would mean that, even though $θ_{i}^{t_{i}}$ and $θ_{i}^{t_{i}^{'}}$ for some link $i \in {1, \dots, N}$ and time periods $t_{i}, t_{i}^{'} \in {0, \dots, L - 1}$ have different distributions, the covariance between $θ_{i}^{t_{i}}$ and $θ_{j}^{t_{j}}$ is defined so that $cov (θ_{i}^{t_{i}}, θ_{j}^{t_{j}}) = cov (θ_{i}^{t_{i}^{'}}, θ_{j}^{t_{j}^{'}}) \forall i, j \in {1, \dots, N}, i \neq j, \forall t_{i}, t_{i}^{'}, t_{j}, t_{j}^{'} \in {0, \dots, L - 1}$ . Alternatively, it is possible to allow the travel time distribution to vary over time, along with the distributions themselves. That would mean that the covariance between the travel times on two links $i, j \in {1, \dots, N}$ is defined for each combination of time-bins $(t_{i}, t_{j})$ where $t_{i}, t_{j} \in {0, \dots, L - 1}$ are the time-bins associated with the traversal of links i and j, respectively, resulting in a total of $L \times L$ covariance values to be estimated for each pair of links.

While several techniques exist for sampling correlated random variables, they may not be directly applicable to the case with time-varying distributions. Therefore, an extension to the MCS algorithm for time-varying distributions described above is presented, to be used with stationary or time-varying covariance structures (abbreviated MCS-TD-S and MCS-TD-TS respectively).

MCS for Correlated Random Variables with Time-Varying Distributions

Step 1: Estimate the covariance:

For links $i, j \in$ ${1, \dots, N}, i \neq j$ , a sample of size S is selected from the set of trajectories traversing both i and j. These are the joint samples for the link travel times on $i, j$ .

For the stationary case, the covariance is estimated between all joint link travel times on the pair $(i, j)$ .

For the time-varying case, the covariance is estimated for each time-bin combination $(t_{i}, t_{j})$ where $t_{i}, t_{j} \in {0, \dots, L - 1}$ by computing the covariance of link travel times that occurred in the corresponding time-bins, as a matrix $Σ$ of size $N \times N \times L \times L$ where $Σ [i, j, t_{i}, t_{j}] = cov (θ_{i}^{t_{i}}, θ_{j}^{t_{j}})$

Step 2: Obtain the initial sample:

For iterations $s \in {1, \dots, M}$ :

A time-bin $t_{j}$ is chosen randomly from ${0, \dots, L - 1}$

For the first segment, a link travel time ${\tilde{θ}}_{1}$ is sampled from $π_{1}^{t_{1}}$ where $t_{1} = t_{s}$

Save the vector of samples ${\tilde{θ}}^{s} = {{\tilde{θ}}_{1}, {\tilde{θ}}_{2}, \dots, {\tilde{θ}}_{N}}$ and their corresponding time bins ${\tilde{t}}^{s} = {{\tilde{t}}_{1}, {\tilde{t}}_{2}, \dots, {\tilde{t}}_{N}}$

Step 3: Obtain a correlated sample:

For each sample $s \in {1, \dots, M}$ :

Multiply the ${\tilde{θ}}^{s} = {{\tilde{θ}}_{1}, {\tilde{θ}}_{2}, \dots, {\tilde{θ}}_{N}}$ by the covariance $Σ .$

If the covariance is time-varying then covariance is constructed so that $Σ [i, j] = cov (θ_{i}^{{\tilde{t}}_{i}}, θ_{j}^{{\tilde{t}}_{j}})$ where ${\tilde{t}}_{i}, {\tilde{t}}_{j}$ are as saved in ${\tilde{t}}^{s} = {{\tilde{t}}_{1}, {\tilde{t}}_{2}, \dots, {\tilde{t}}_{N}}$

This method for sampling correlated random variables is based on an approximate approach proposed by Lurie and Goldberg, but adjusted so as to allow for time-varying random variables with time-varying covariances ( 24 ).

Combinatorial Data-Mining Segment Search Approach

Each of the simulation-based approaches presented above can be applied for the convolution of travel time distributions of path segments. The special case typically employed in literature uses the segmentation of the path to the link level so as to synthesize a path travel time distribution from the link-level travel time distributions. In this section consideration is given to using sub-paths of the path in question, rather than links, so as to simplify the convolution process and allow for some of the correlations between link travel times to be implicitly captured within known sub-path level travel time distributions.

This section focuses on the approach to obtain an appropriate set of non-overlapping sub-paths that cover the full path. The heuristic is intended to find sub-paths that have sufficient sample size, in relation to the number of vehicle traversals, high estimated correlation between link travel times within the same sub-path, and low estimated correlation between links in different sub-paths. To ensure that the time-varying aspect is appropriately captured, the path segmentation needs to have consistency between the time periods covered in the sample for each sub-path. Furthermore, the devised segment search approach aims to utilize as much of the trajectory data information as possible. Synthesizing path travel time distributions from sub-path level observations limits the trajectory data utilized in the estimation and may lead to a biased result, since it only utilizes a portion of the trajectory data. Therefore, the segment search approach produces multiple groups of sub-paths, each group consisting of non-overlapping segments of the path that cover the entire path.

The combinatorial segment search approach is applied with a given time-period $T_{P}$ , the vehicle trajectory data available for all vehicles traversing any portion of the path in question, and the time-invariant covariance of link travel times, $Σ$ . Additionally, it requires the specification of a minimum number of observations required to construct a distribution. The combinatorial segment search approach is presented below and illustrated in Figure 1.

Figure 1.

Diagram illustrating the combinatorial segment search approach.

Combinatorial Segment Search Approach

Step 0: Create a directory of all sub-paths that satisfy the lower limit on sample size. Go to Step 1.

Step 1: Check if the sub-paths in the directory provide full coverage of the path. Simply, check if all links of the path are included in at least one sub-path. If yes, go to Step 2, otherwise Stop.

Step 2: Obtain a group of sub-paths:

Step 2.1: Initiate sub-path group. Call the Next Segment Search procedure to obtain the initial sub-path. Add the sub-path to the current group. Go to Step 2.2.

Step 2.2: Check if the current group covers the full path. If path is covered, go to Step 3. Otherwise, go to Step 2.3.

Step 2.3: Take a subset of the directory, only consisting of sub-paths not overlapping with any of the sub-paths already in the group. Go to Step 2.4.

Step 2.4: Search for the next segment and add it to the group. Go to Step 2.2.

Step 3: Modify the directory of sub-path to exclude all of the sub-paths in the complete group.

Step 4: Output the group of sub-paths. Go to Step 1.

The Next Segment Search heuristic called in Steps 2.1 and 2.4, is shown below. The purpose of this sub-step is to select the next segment in the group, or the first segment if this is the start of a new group. This heuristic selects the best segment, based on some qualifying criteria. The first criterion is that the sub-paths have traversals that cover 90% of the full peak-period, which will ensure a biased distribution is avoided. The next criterion computes and evaluates the total covariance magnitude within the segment and relative to links outside the segment. The purpose of this step is primarily to rank the segments so that the selected next segment is one for which the links within the segment are highly correlated to one another and not highly correlated with other links in the path. Since the segment search approach finds each of the segments one by one, it does not evaluate the spatial correlation of the travel time on any one segment with respect to all others. However, it does enforce that the selected segment has the characteristics explained above which would indicate a low correlation between individual segments. Finally, the selected segment is one with the highest number of vehicle traversals, to ensure that as much of the vehicle trajectory data as possible is being captured.

Next Segment Search

From the sub-path directory, select the sub-paths that have trajectory observations covering 90% of full peak period, if there are any.

For the selected sub-paths, compute the covariance difference as the difference between the sum of covariance magnitudes for links within the sub-path and the sum of covariance magnitudes for links outside the sub-path. Select the sub-paths that are in the 75th or higher percentile in their value for covariance difference.

Remove half of the sub-paths with the lowest number of vehicle traversals.

Select the longest sub-path in relation to the number of links. If there are multiple such sub-paths, select the one with the highest number of vehicle traversals.

Output the selected sub-path.

Other Distribution Estimation Approaches in the Literature

Literature on probability modeling and estimation provides a few approaches that may be used for estimating path travel time distributions with correlations, and two specific approaches are identified to be compared with the methods presented in this section.

The first is based on a Markov chain Monte Carlo sampling method to simulate multivariate distributions known as the Metropolis-Hastings (M-H) algorithm. Detailed exposition of the M-H algorithm itself can be found in Chib and Greenberg ( 25 ). For the application of sampling jointly distributed path travel time distributions used in this study, an issue of general affine invariance can be encountered when employing the standard M-H algorithm. Affine invariance in the M-H algorithm occurs when distributions may have high aspect ratios because of variations in scale. This issue has been addressed for general applications with affine invariance via the use of an ensemble sampler, as proposed in Goodman and Weare, where, instead of a single M-H walker, an ensemble of independent walkers are used ( 26 ). Therefore, an ensemble M-H sampler will be employed, according to the implementation in Foreman-Mackey et al. of the algorithm presented in Goodman and Weare ( 26 , 27 ). An important caveat of the M-H algorithm that translates to the ensemble sampler is that a candidate-generating density, also referred to as a proposal density, needs to be specified, and the entire walk of the M-H algorithm is based on the same underlying candidate-generating density. While this assumption may be appropriate for use with time-invariant random variables, additional adjustments would be needed to make it appropriate for time-varying distributions with time-varying dependencies.

The second approach is a commonly used approximation for the sum of correlated non-negative random variables via a lognormal distribution ( 28 ). This approach provides an analytical solution for estimating the parameters of a lognormal distribution as the fit for the distribution of a sum of generally correlated random variables. This approach is utilized in a few studies considering STV networks, and, here, the implementation presented by Chen et al. is followed ( 29 ).

Numerical Experiments

Study Sites and Data

To test the presented methods for the estimation of path travel time distributions on an urban network using trajectory data, this study used simulated trajectory data on the network of Chicago, U.S. The Chicago network used in this study has 1,578 nodes and 4,805 links. A total of 25 analysis scenarios were simulated using DYNASMART-P, based on five different daily demand scenarios and five weather condition scenarios, to provide variation in travel times in the simulated data ( 30 ). The simulation was calibrated using real data on the Chicago network, but this data set and calibration are out of the scope of this study and can be found in Yelchuru et al. ( 31 ).

From these simulations, the full trajectory information data was extracted for the morning peak period from 6:00 to 9:00 a.m. Based on operational scenarios defined in the simulation and observed variations in travel times in the resulting data, travel time distributions were estimated conditional on four weather conditions: clear weather, rain, snow, and low visibility.

To test the estimation accuracy of the presented methods, a set of 35 paths was selected from the network. The portions of the network covered by the selected paths are displayed on the network and map of Chicago in Figure 2. The paths were selected so as to have many vehicle traversals—that is, trajectory observations—across all four weather conditions, so that they could provide a reliable estimate of the path travel time distribution to be used as the ground truth. To find such paths, a trajectory clustering algorithm by Hong et al. was used, with the minimum number of observations set to 100 ( 32 ).

Figure 2.

The network of Chicago, with the portions covered by the selected paths shown in blue.

Experiment Design

The vehicle trajectory data, consisting of any vehicle trajectory observations traversing any portion of the paths considered, during the morning peak period were separated into the observations of full path traversals and partial path traversals for each of the paths. A total of 140 path travel time distributions were computed from the full vehicle traversals, to be used as ground truth, and the remaining vehicle trajectory data were used to test the estimation approaches presented in the Methodology section. Link-based estimation was performed using four Monte Carlo sampling approaches: MCS assuming independence (MCS-I), MCS assuming time-dependence (MCS-TD), MCS assuming time-dependence with stationary spatial correlations (MCS-TD-S) and with time-varying correlations (MCS-TD-TS). Each of the MCS-TD approaches was tested using a time-bin $δ = 10 \min$ . Because of restrictions in the data set, the time-varying correlation was estimated with a time bin $δ_{c} = 30 \min$ . The number of samples M for each of the MCS approaches was set to 1,000. The segment search approach was performed using a minimum-number-of-observations threshold at 30 and it was tested by using the resulting segments to estimate the path distributions using the MCS approach with independent random variables and assuming time-dependence only, which will be abbreviated as MCS-SS-I and MCS-SS-TD. The two approaches from the literature, the ensemble MCMC sampler with M-H walkers (abbreviated MCMC-MH), and the approach for approximating a sum of random variables via a lognormal (abbreviated LogN), were tested with the same data and for the same set of path travel time distributions ( 26 – 29 ).

Results and Analysis

The accuracy of each of the estimation approaches was tested via the closeness of the estimated distributions to the ground truth distribution for the corresponding path and weather-defined operational condition. This study uses the Kolmogorov–Smirnov (K-S) statistic as a goodness-of-fit measure. The K-S statistics is a supremum-based measure of closeness for two probability distributions ( 33 , 34 ). It can take values from 0 to 1, where a value closer to 0 signifies a better fit and is typically used to decide if a sample comes from a population with a specific distribution. The K-S statistic is used in this study, as it is the most commonly used goodness-of-fit measure of this kind for closeness of probability distributions. However, a noteworthy shortcoming of the K-S statistic is that it quantifies the largest distance between the two distributions, and, as such, does not capture the average or overall distance between the distributions,

The summary statistics for the K-S statistic values for each of the approaches on the 35 paths, averaged over the different weather operational conditions on each path, are shown in Table 1 and Figure 3.

Table 1.

Summary of the Kolmogorov–Smirnov (K-S) Values for Each Approach, Including the Mean, Minimum, and Maximum Values, and the Median and First and Third Quartile Values, over all 140 Path Travel Time Distributions

	Summary statistics of the K-S statistic value:	Mean	Minimum	Maximum	Q2	Q1	Q3
Distribution estimation approach	MCS-I	0.265	0.120	0.564	0.255	0.223	0.285
	MCS-TD	0.254	0.086	0.654	0.192	0.142	0.301
	MCS-TD-S	0.459	0.144	0.918	0.391	0.246	0.650
	MCS-TD-TS	0.196	0.087	0.480	0.179	0.133	0.214
	MCS-SS-I	0.251	0.082	0.628	0.199	0.154	0.313
	MCS-SS-TD	0.235	0.101	0.511	0.231	0.179	0.259
	MCMC M-H	0.482	0.149	1.000	0.345	0.305	0.619
	LogN	0.401	0.114	0.604	0.420	0.286	0.534

Note: Monte Carlo Sampling (MSC) approaches: MCS-I = MCS assuming independence; MCS-TD = MCS assuming time-dependence; MCS-TD-S = MCS assuming time-dependence with stationary spatial correlations; MCS-TD-TS = with time-varying correlations; MCS-SS-I = with independent random variables; MCS-SS-TD = time-dependence only; MCMC-MH = Ensemble Markov Chain Monte Carlo sampler with Metropolis-Hastings walkers; LogN = lognormal approximation.

Figure 3.

Box Plot of the Kolmogorov–Smirnov (K-S) statistic values for all of the estimation approaches.

These results show the variation of K-S statistic values for each of the methods. A few things of importance can be pointed out from these results. The approaches yielding the least variation in the K-S statistic value were the MCS-I, the MCS-TD and MCS-TD-TS, and MCS-SS-I. The approach with the most variation in the K-S statistic value is the MCS-TD-S approach. This approach results in some of the highest values of the K-S statistic, but also, in some cases, outperforms some of the other approaches. Since the data showed the time-varying property of the covariance between link travel times, assuming stationary covariance can lead to a biased distribution in a lot of cases.

MCS-TD-TS

The MCS-TD-TS approach on average outperforms all of the other approaches and is robust with respect to estimating travel time distributions on different paths and in various weather conditions, which indicates that it can estimate different distribution shapes. This result, especially in comparison with the corresponding approach with a stationary covariance structure, indicates that using a time-varying covariance significantly improves the accuracy in estimating the path travel time distribution. However, the drawback of using this approach is the computational effort required. Specifically, being a link-based approach and using a time-varying covariance structure, the MCS approach, even with the same number of iterations, performs the largest number of iterations compared with all other methods, and additionally requires the ability to compute a time-varying covariance structure. If computational time is not an issue—for example, for offline applications—this approach would be the most accurate and robust method for estimating path travel time distributions.

MCS-SS-TD

The MCS-SS-TD is the second approach that shows significant improvements in performance compared with the other approaches, with performance relatively close to the best-performing method. This shows that utilizing sub-path trajectory information can implicitly capture the complex covariance structure underlying the path travel time distribution. The segment search approach utilizes the stationary covariance structure to find the appropriate segmentation of the path by only relying on the overall magnitude of the covariance, and, as such, does not necessitate the computational effort required for determining the time-varying covariance structure. Additionally, the sub-path approach requires the least number of operations in computing the path travel time distribution within the MCS. Since the segment search itself can be performed before the distribution estimation, the sub-path approach with time dependence may be most appropriate for online applications.

Comparison with the Distribution Estimation Approaches Based on the Literature

The MCMC-MH approach and the LogN method are outperformed by all but one of the MCS approaches. The MCMC-MH approach can achieve relatively low K-S statistic values, but it also produces the highest deviations from the ground truth. Its performance can be compared with that of the MCS-TD-S approach, especially since the MCMC-MH method itself relies on a stationary covariance structure. An interesting question for future work may be to develop an approach to find ways to utilize the ensemble MCMC-MH approach with a time-varying covariance structure. The LogN method does not produce K-S statistic values as high as those of the MCMC-MH approach, but it is always outperformed by all but one of the MCS approaches, and, as such, would not be the recommended approach for estimating path travel time distributions on STV networks with general correlation structures.

Conclusion and Discussion

This paper addresses the question of estimating path travel time distributions in STV networks with generalized correlation structures. The problem is addressed in two manners. Firstly, building on existing MCS approaches, MCS approaches for random variables with time-varying distributions are presented for the cases assuming no correlations, stationary correlations, and time-varying correlations between link travel times. Secondly, to bypass the estimation of generalized time-varying correlations in an STV network, an alternative data-mining approach is presented for synthesizing trajectory data at the segment level.

The numerical experiments in this study are performed on a set of paths on the Chicago network, calibrated using real-world data so as to capture the variation of network performance with varying operational conditions. The presented approaches are tested for the estimation of a total of 140 path travel time distributions from 35 paths across four weather scenarios, and they are compared with the base case of using MCS under the assumption of independent and time-invariant link travel time distributions. Additionally, the methods are compared with an ensemble Markov chain Monte Carlo method using the M-H algorithm and an approach for approximating sums of random variables via a lognormal distribution. The numerical results and their analysis yield a few interesting insights:

Of the tested approaches, the MCS approach allowing for time-dependence and a time-varying correlation structure generally outperforms all of the other approaches, and its performance is robust with respect to the different path travel time distributions tested.

The MCS approach with sub-paths, using the segments from the combinatorial segment search approach, produces accuracy close to the MCS approach with time-dependence and time-varying correlations. The added benefit of this approach is the improvement in computational effort, and, as such, it may be appropriate for online applications, given that the segment search itself is performed a priori.

The MCS approach with time-dependence and time-invariant (or stationary) correlation structure yields to lower accuracy relative to its counterpart with no correlation, which indicates that assuming stationary correlations may lead to biased distribution results.

Future research can extend this work in multiple ways. Potential research directions may include testing for the appropriate or optimal time-discretization to be used for time-varying distributions or time-varying correlation structures. Further, reliability-based measures at the path level may be integrated in applications for system performance analysis or network design. The distribution estimation approaches may also be used for offline or online applications of reliability-based route choice and route guidance for travelers with different reliability objectives.

Footnotes

Acknowledgements

The authors have benefited from comments provided by Douglas Laird of FHWA, David Hale of Leidos, and Montasir Abbas of Virginia Tech.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: M. Filipovska, H. S. Mahmassani, A. Mittal; data collection: M. Filipovska, H. S. Mahmassani, A. Mittal; analysis and interpretation of results: M. Filipovska, H. S. Mahmassani, A. Mittal; draft manuscript preparation: M. Filipovska, H. S. Mahmassani, A. Mittal. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This paper is based in part on research funded by the U.S. Department of Transportation through Leidos Inc., as well as funding provided by the Northwestern University Transportation Center.

ORCID iDs

Monika Filipovska

Hani S. Mahmassani

Archak Mittal

The views expressed are those of the authors and do not necessarily reflect those of the sponsoring agencies.

References

Kim

Mahmassani

H. S.

Dong

Likelihood and Duration of Flow Breakdown Modeling the Effect of Weather. Transportation Research Record: Journal of the Transportation Research Board, 2010. 2188: 19–28.

Miller-Hooks

Mahmassani

H. S.

Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks. Transportation Science, Vol. 34, No. 2, 2003, pp. 198–215. https://doi.org/10.1287/trsc.34.2.198.12304.

Fosgerau

Karlström

The Value of Reliability. Transportation Research Part B: Methodological, Vol. 44, No. 1, 2010, pp. 38–49. https://doi.org/10.1016/j.trb.2009.05.002.

Mahmassani

H. S.

Kim

Chen

Stogios

Brijmohan

Vovsha

Incorporating Reliability Performance Measures into Operations and Planning Modeling Tools. Transportation Research Board, Washington, D.C., 2014.

Kim

Mahmassani

H. S.

Spatial and Temporal Characterization of Travel Patterns in a Traffic Network Using Vehicle Trajectories. Transportation Research Procedia, Vol. 9, 2015, pp. 164–184.

Miller-Hooks

Adaptive Least-Expected Time Paths in Stochastic, Time-Varying Transportation and Data Networks. Networks: An International Journal, Vol. 37, No. 1, 2001, pp. 35–52. https://doi.org/10.1002/1097-0037(200101)37:1<35::AID-NET4>3.0.CO;2-G.

Nie

Shortest Path Problem Considering On-Time Arrival Probability. Transportation Research Part B: Methodological, Vol. 43, No. 6, 2009, pp. 597–613. https://doi.org/10.1016/j.trb.2009.01.008.

Nie

Reliable a Priori Shortest Path Problem with Limited Spatial and Temporal Dependencies. In Transportation and Traffic Theory 2009: Golden Jubilee ( Lam

W. H. K.

Wong

S. C.

H. K.

, eds.), Springer, Boston, MA, 2009, pp. 169–195.

Nie

Implementation Issues for the Reliable a Priori Shortest Path Problem. Transportation Research Record: Journal of the Transportation Research Board, 2009. 2091: 51–60.

10.

Filipovska

Mahmassani

H. S.

Reliable Least-Time Path Estimation and Computation in Stochastic Time-Varying Networks with Spatio-Temporal Dependencies. Proc., 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC), Rhodes, Greece, IEEE, New York, 2020.

11.

Zockaie

Nie

Mahmassani

H. S.

Impacts of Correlations on Reliable Shortest Path Finding. Transportation Research Record: Journal of the Transportation Research Board, 2013. 2334: 1–9.

12.

Zockaie

Nie

Y. M.

Mahmassani

H. S.

Simulation-Based Method for Finding Minimum Travel Time Budget Paths in Stochastic Networks with Correlated Link Times. Transportation Research Record: Journal of the Transportation Research Board, 2015. 2467: 140–148.

13.

Zockaie

Mahmassani

H. S.

Nie

Path Finding in Stochastic Time Varying Networks with Spatial and Temporal Correlations for Heterogeneous Travelers. Transportation Research Record: Journal of the Transportation Research Board, 2016. 2567: 105–113.

14.

Ramezani

Geroliminis

On the Estimation of Arterial Route Travel Time Distribution with Markov Chains. Transportation Research Part B: Methodological, Vol. 46, No. 10, 2012, pp. 1576–1590. https://doi.org/10.1016/j.trb.2012.08.004.

15.

Isukapati

List

Williams

Karr

Synthesizing Route Travel Time Distributions from Segment Travel Time Distributions. Transportation Research Record: Journal of the Transportation Research Board, 2013. 2396: 71–81.

16.

Eisele

W. L.

Naik

Rilett

L. R.

Estimating Route Travel Time Reliability from Simultaneously Collected Link and Route Vehicle Probe Data and Roadway Sensor Data. International Journal of Urban Sciences, Vol. 19, No. 3, 2015, pp. 286–304.

17.

Chen

Osorio

Analytical Formulation of the Trip Travel Time Distribution. Transportation Research Procedia, Vol. 3, 2014, pp. 366–373.

18.

Chen

Wang

A Copula-Based Approach for Estimating the Travel Time Reliability of Urban Arterial. Transportation Research Part C: Emerging Technologies, Vol. 82, 2017, pp. 1–23. https://doi.org/10.1016/j.trc.2017.06.007.

19.

Rahmani

Jenelus

Koutsopoulos

. Non-Parametric Estimation of Route Travel Time Distributions from Low-Frequency Floating Car Data. Transportation Research Part C: Emerging Technologies, Vol. 58B, 2015, pp. 343–362.

20.

Koutsopoulos

H. N.

Ferreira

Mesbah

Estimation of Trip Travel Time Distribution Using a Generalized Markov Chain Approach. Transportation Research Part C: Emerging Technologies, Vol. 74, 2017, pp. 1–21. https://doi.org/10.1016/j.trc.2016.11.008.

21.

Mahmassani

H. S.

Hou

Dong

Characterizing Travel Time Variability in Vehicular Traffic Networks: Deriving a Robust Relation for Reliability Analysis. Transportation Research Record: Journal of the Transportation Research Board, 2012. 2315: 141–152.

22.

Hunter

Hofleitner

Reilly

Krichene

Thai

Kouvelas

Abbeel

Bayen

Arriving on Time: Estimating Travel Time Distributions on Large-Scale Road Networks. arXiv Preprint arXiv:1302.6617, 2013.

23.

Westgate

B. S.

Woodard

D. B.

Matteson

D. S.

Henderson

S. G.

Travel Time Estimation for Ambulances Using Bayesian Data Augmentation. Annals of Applied Statistics, Vol. 7, No. 2, 2013, pp. 1139–1161. https://doi.org/10.1214/13-AOAS626

24.

Lurie

P. M.

Goldberg

M. S.

An Approximate Method for Sampling Correlated Random Variables from Partially-Specified Distributions. Management Science, Vol. 44, No. 2, 1998, pp. 203–218. https://doi.org/10.1287/mnsc.44.2.203.

25.

Chib

Greenberg

Understanding the Metropolis-Hastings Algorithm. The American Statistician, Vol. 49, No. 4, 1995, pp. 327–335.

26.

Goodman

Weare

Ensemble Samplers with Affine Invariance. Communications in Applied Mathematics and Computational Science, Vol. 5, No. 1, 2010, pp. 65–80.

27.

Foreman-Mackey

Hogg

D. W.

Lang

Goodman

Emcee: The MCMC Hammer. Publications of the Astronomical Society of the Pacific, Vol. 125, No. 925, 2013, p. 306.

28.

Mehta

N. B.

Molisch

A. F.

Zhang

Approximating a Sum of Random Variables with a Lognormal. IEEE Transactions on Wireless Communications, Vol. 6, No. 7, 2007, pp. 2690–2699. https://doi.org/10.1109/TWC.2007.051000.

29.

Chen

Tong

Wang

Reliable Shortest Path Finding in Stochastic Time-Dependent Road Network with Spatial-Temporal Link Correlations: A Case Study from Beijing. Expert Systems with Applications, Vol. 147, 2020, p. 113192. https://doi.org/10.1016/j.eswa.2020.113192.

30.

Mahmassani

H. S.

Sbayti

Zhou

DYNASMART-P: Intelligent Transportation Network Planning Tool: Version 1.0 Users Guide. Maryland Transportation Initiative, University of Maryland, College Park, 2004.

31.

Yelchuru

Kamalanathsharma

Mahmassani

H. S.

Hong

Mittal

Analysis, Modeling, and Simulation (AMS) Testbed Framework for Dynamic Mobility Applications (DMA) and Active Transportation and Demand Management (ATDM) Programs. US Department of Transportation, Washington, D.C., 2017.

32.

Hong

Chen

Mahmassani

H. S.

Recognizing Network Trip Patterns Using a Spatio-Temporal Vehicle Trajectory Clustering Algorithm. IEEE Transactions on Intelligent Transportation Systems, Vol. 19, No. 8, 2018, pp. 2548–2557. https://doi.org/10.1109/TITS.2017.2754401.

33.

Chakravarty

I. M.

Roy

J. D.

Laha

R. G.

Handbook of Methods of Applied Statistics. McGraw-Hill, New York, NY, 1967.

34.

Daniel

W. W.

Kolmogorov–Smirnov One-Sample Test. Applied Nonparametric Statistics, Vol. 2, 1990.