Finding the k reliable shortest paths under travel time uncertainty

This paper investigates the problem of finding the K reliable shortest paths (KRSP) in stochastic networks under travel time uncertainty. The KRSP problem extends the classical K loopless shortest paths problem to the stochastic networks by explicitly considering travel time reliability. In this study, a deviation path approach is established for finding K α-reliable paths in stochastic networks. A deviation path algorithm is proposed to exactly solve the KRSP problem in large-scale networks. The A^* technique is introduced to further improve the KRSP finding performance. A case study using real traffic information is performed to validate the proposed algorithm. The results indicate that the proposed algorithm can determine KRSP under various travel time reliability values within reasonable computational times. The introduced A^* technique can significantly improve KRSP finding performance.     

Identifying optimal data aggregation interval sizes for link and corridor travel time estimation and forecasting

With the recent increase in the deployment of ITS technologies in urban areas throughout the world, traffic management centers have the ability to obtain and archive large amounts of data on the traffic system. These data can be used to estimate current conditions and predict future conditions on the roadway network. A general solution methodology for identifying the optimal aggregation interval sizes for four scenarios is proposed in this article: (1) link travel time estimation, (2) corridor/route travel time estimation, (3) link travel time forecasting, and (4) corridor/route travel time forecasting. The methodology explicitly considers traffic dynamics and frequency of observations. A formulation based on mean square error (MSE) is developed for each of the scenarios and interpreted from a traffic flow perspective. The methodology for estimating the optimal aggregation size is based on (1) the tradeoff between the estimated mean square error of prediction and the variance of the predictor, (2) the differences between estimation and forecasting, and (3) the direct consideration of the correlation between link travel time for corridor/route estimation and forecasting. The proposed methods are demonstrated using travel time data from Houston, Texas, that were collected as part of the automatic vehicle identification (AVI) system of the Houston Transtar system. It was found that the optimal aggregation size is a function of the application and traffic condition.

Traffic state estimation through compressed sensing and Markov random field

This study focuses on information recovery from noisy traffic data and traffic state estimation. The main contributions of this paper are: i) a novel algorithm based on the compressed sensing theory is developed to recover traffic data with Gaussian measurement noise, partial data missing, and corrupted noise; ii) the accuracy of traffic state estimation (TSE) is improved by using Markov random field and total variation (TV) regularization, with introduction of smoothness prior; and iii) a recent TSE method is extended to handle traffic state variables with high dimension. Numerical experiments and field data are used to test performances of these proposed methods; consistent and satisfactory results are obtained.     

Real time traffic flow outlier detection using short-term traffic conditional variance prediction

Outliers in traffic flow series represent uncommon events occurring in the roadway systems and outlier detection and investigation will help to unravel the mechanism of such events. However, studies on outlier detection and investigations are fairly limited in transportation field where a vast volume of traffic condition data has been collected from traffic monitoring devices installed in many roadway systems. Based on an online algorithm that has the ability of jointly predict the level and the conditional variance of the traffic flow series, a real time outlier detection method is proposed and implemented. Using real world data collected from four regions in both the United States and the United Kingdom, it was found that outliers can be detected using the proposed detection strategy. In addition, through a comparative experimental study, it was shown that the information contained in the outliers should be assimilated into the forecasting system to enhance its ability of adapting to the changing patterns of the traffic flow series. Moreover, the investigation into the effects of outliers on the forecasting system structure showed a significant connection between the outliers and the forecasting system parameters changes. General conclusions are provided concerning the analyses with future work recommended to investigate the underlying outlier generating mechanism and outlier treatment strategy in transportation applications.     

Distribution models for start-up lost time and effective departure flow rate

Due to its importance, lots of investigations had been carried out in the last four decades to study the relationship between phase duration and vehicle departure amount. In this paper, we aim to build appropriate distribution models for start-up lost time and effective departure flow rate, by considering their relations with the frequently mentioned departure headway distributions. The motivation behind is that distribution models could provide richer information than the conventional mean value models and thus better serve the need of traffic simulation and signal timing planning. To reach this goal, we first check empirical data collected in Beijing, China. Tests show that the departure headways at each position in a discharging queue are very weakly dependent or almost independent. Based on this new finding, two distribution models are proposed for start-up lost time and effective flow rate, respectively. We also examine the dependences of departure headways that are generated by three popular traffic simulation software: VISSIM, PARAMICS and TransModeler. Results suggest that in VISSIM, the departure headways at different positions are almost deterministically dependent and may not be in accordance with empirical observations. Finally, we discuss how the dependence of departure headways may influence traffic simulation and signal timing planning.     

Modeling stochastic perception error in the mean-excess traffic equilibrium model

In this paper, we extend the α-reliable mean-excess traffic equilibrium (METE) model of Chen and Zhou (Transportation Research Part B 44(4), 2010, 493-513) by explicitly modeling the stochastic perception errors within the travelers’ route choice decision processes. In the METE model, each traveler not only considers a travel time budget for ensuring on-time arrival at a confidence level α, but also accounts for the impact of encountering worse travel times in the (1 − α) quantile of the distribution tail. Furthermore, due to the imperfect knowledge of the travel time variability particularly in congested networks without advanced traveler information systems, the travelers’ route choice decisions are based on the perceived travel time distribution rather than the actual travel time distribution. In order to compute the perceived mean-excess travel time, an approximation method based on moment analysis is developed. It involves using the conditional moment generation function to derive the perceived link travel time, the Cornish-Fisher Asymptotic Expansion to estimate the perceived travel time budget, and the Acerbi and Tasche Approximation to estimate the perceived mean-excess travel time. The proposed stochastic mean-excess traffic equilibrium (SMETE) model is formulated as a variational inequality (VI) problem, and solved by a route-based solution algorithm with the use of the modified alternating direction method. Numerical examples are also provided to illustrate the application of the proposed SMETE model and solution method.     

Aggregation and travel time calculation over large scale traffic networks: An empiric study on the Grenoble City

In this paper we consider aggregation technique to reduce the complexity of large-scale traffic network. In particular, we consider the city of Grenoble and show that, by clustering adjacent sections based on a similarity of speed condition, it is possible to cut down the complexity of the network without loosing crucial and intrinsic information. To this end, we consider travel time computation as a metric of comparison between the original graph and the reduced one: for each cluster we define four attributes (average speed, primary and secondary length and heading) and show that, in case of an aggregation rate of 95%, these attributes are sufficient in order to maintain the travel time error below the 25%.     

An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows

The solution of routing problems with soft time windows has valuable practical applications. Soft time window solutions are needed when: (a) the number of routes needed for hard time windows exceeds the number of available vehicles, (b) a study of cost-service tradeoffs is required, or (c) the dispatcher has qualitative information regarding the relative importance of hard time-window constraints across customers. This paper proposes a new iterative route construction and improvement algorithm to solve vehicle routing problems with soft time windows. Due to its modular and hierarchical design, the solution algorithm is intuitive and able to accommodate general cost and penalty functions. Experimental results indicate that the average run time performance is of order O(n²). The solution quality and computational time of the new algorithm has been compared against existing results on benchmark problems. The presented algorithm has improved thirty benchmark problem solutions for the vehicle routing problems with soft time windows.     

Experienced travel time prediction for congested freeways

Travel time is an important performance measure for transportation systems, and dissemination of travel time information can help travelers make reliable travel decisions such as route choice or departure time. Since the traffic data collected in real time reflects the past or current conditions on the roadway, a predictive travel time methodology should be used to obtain the information to be disseminated. However, an important part of the literature either uses instantaneous travel time assumption, and sums the travel time of roadway segments at the starting time of the trip, or uses statistical forecasting algorithms to predict the future travel time. This study benefits from the available traffic flow fundamentals (e.g. shockwave analysis and bottleneck identification), and makes use of both historical and real time traffic information to provide travel time prediction. The methodological framework of this approach sequentially includes a bottleneck identification algorithm, clustering of traffic data in traffic regimes with similar characteristics, development of stochastic congestion maps for clustered data and an online congestion search algorithm, which combines historical data analysis and real-time data to predict experienced travel times at the starting time of the trip. The experimental results based on the loop detector data on Californian freeways indicate that the proposed method provides promising travel time predictions under varying traffic conditions.     

Development and evaluation of a hybrid travel time forecasting model

The purpose of this paper is to develop and evaluate a hybrid travel time forecasting model with geographic information systems (GIS) technologies for predicting link travel times in congested road networks. In a separate study by You and Kim (cf. You, J., Kim, T.J., 1999b. In: Proceedings of the Third Bi-Annual Conference of the Eastern Asia Society for Transportation Studies, 14–17 September, Taipei, Taiwan), a non-parametric regression model has been developed as a core forecasting algorithm to reduce computation time and increase forecasting accuracy. Using the core forecasting algorithm, a prototype hybrid forecasting model has been developed and tested by deploying GIS technologies in the following areas: (1) storing, retrieving, and displaying traffic data to assist in the forecasting procedures, (2) building road network data, and (3) integrating historical databases and road network data. This study shows that adopting GIS technologies in link travel time forecasting is efficient for achieving two goals: (1) reducing computational delay and (2) increasing forecasting accuracy.     

Effect of traffic information on commuters' propensity to change route and departure time

Considerable public and private resources are devoted to the collection and dissemination of real-time traffic information in the Chicago area. Such information is intended to help individuals make more informed travel decisions, yet its effect on behavior remains largely unexplored. This study evaluates the effect of traffic information on travelers' route and departure time changes and provides a stronger basis for developing advanced information systems. Downtown Chicago automobile commuters were surveyed during the AM peak period. The results indicate that a majority of the respondents access, use and respond to information. For example, individuals use travel information to reduce their anxiety—even if they do not change travel decisions; this indicates that information may have “intrinsic” value. That is, simply knowing traffic conditions is valued by travelers. More than 60% of the respondents had used traffic information to modify their travel decisions. Multivariate analysis using the ordered probit model showed that individuals were more likely to use traffic reports for their route changes if they perceived traffic reports to be accurate and timely, and frequently listened to traffic reports. Respondents were more likely to change their departure times if they perceived traffic reports to be accurate and relevant, and frequently listened to traffic reports. The implication for Advanced Traveler Information Systems are that they may be designed to support both enroute and pre-trip decisions. ATIS performance, measured in terms of accuracy, relevance and timeliness would be critical in the success of such systems. Further, near-term prediction of traffic conditions on congested and unreliable routes (where conditions change rapidly) and incident durations is desirable.     

A spatiotemporal correlative k-nearest neighbor model for short-term traffic multistep forecasting

The k-nearest neighbor (KNN) model is an effective statistical model applied in short-term traffic forecasting that can provide reliable data to guide travelers. This study proposes an improved KNN model to enhance forecasting accuracy based on spatiotemporal correlation and to achieve multistep forecasting. The physical distances among road segments are replaced with equivalent distances, which are defined by the static and dynamic data collected from real road networks. The traffic state of a road segment is described by a spatiotemporal state matrix instead of only a time series as in the original KNN model. The nearest neighbors are selected according to the Gaussian weighted Euclidean distance, which adjusts the influences of time and space factors on spatiotemporal state matrices. The forecasting accuracies of the improved KNN and of four other models are compared, and experimental results indicate that the improved KNN model is more appropriate for short-term traffic multistep forecasting than the other models are. This study also discusses the application of the improved KNN model in a time-varying traffic state.     

Reducing bias in probe-based arterial link travel time estimates

The use of probe vehicles to provide estimates of link travel times has been suggested as a means of obtaining travel times within signalized networks for use in advanced traveler information systems. Previous research has shown that bias in arrival time distributions of probe vehicles will lead to a systematic bias in the sample estimate of the mean. This paper proposes a methodology for reducing the effect of this bias. The method, based on stratified sampling techniques, requires that vehicle count data be obtained from an in-road loop detector or other traffic surveillance method. The effectiveness of the methodology is illustrated using simulation results for a single intersection approach and for an arterial corridor. The results for the single intersection approach indicate a correlation (R²) between the biased estimate and the population mean of 0.61, and an improved correlation between the proposed estimation method and the population mean of 0.81. Application of the proposed method to the arterial corridor resulted in a reduction in the mean travel time error of approximately 50%, further indicating that the proposed estimation method provides improved accuracy over the typical method of computing the arithmetic mean of the probe reports.     

Vehicle reidentification and travel time measurement on congested freeways

The paper presents an algorithm for matching individual vehicles measured at a freeway detector with the vehicles’ corresponding measurements taken earlier at another detector located upstream. Although this algorithm is potentially compatible with many vehicle detector technologies, the paper illustrates the method using existing dual-loop detectors to measure vehicle lengths. This detector technology has seen widespread deployment for velocity measurement. Since the detectors were not developed to measure vehicle length, these measurements can include significant errors. To overcome this problem, the algorithm exploits drivers’ tendencies to retain their positions within dense platoons. The otherwise complicated task of vehicle reidentification is carried out by matching these platoons rather than individual vehicles. Of course once a vehicle has been matched across neighboring detector stations, the difference in its arrival time at each station defines the vehicle’s travel time on the intervening segment.Findings from an application of the algorithm over a 1/3 mile long segment are presented herein and they indicate that a sufficient number of vehicles can be matched for the purpose of traffic surveillance. As such, the algorithm extracts travel time data without requiring the deployment of new detector technologies. In addition to the immediate impacts on traffic monitoring, the work provides a means to quantify the potential benefits of emerging detector technologies that promise to extract more detailed information from individual vehicles.     

Forecasting journey time distribution with consideration to abnormal traffic conditions

Travel time is an important index for managers to evaluate the performance of transportation systems and an intuitive measure for travelers to choose routes and departure times. An important part of the literature focuses on predicting instantaneous travel time under recurrent traffic conditions to disseminate traffic information. However, accurate travel time prediction is important for assessing the effects of abnormal traffic conditions and helping travelers make reliable travel decisions under such conditions. This study proposes an online travel time prediction model with emphasis on capturing the effects of anomalies. The model divides a path into short links. A Functional Principal Component Analysis (FPCA) framework is adopted to forecast link travel times based on historical data and real-time measurements. Furthermore, a probabilistic nested delay operator is used to calculate path travel time distributions. To ensure that the algorithm is fast enough for online applications, parallel computation architecture is introduced to overcome the computational burden of the FPCA. Finally, a rolling horizon structure is applied to online travel time prediction. Empirical results for Guangzhou Airport Expressway indicate that the proposed method can capture an abrupt change in traffic state and provide a promising and reliable travel time prediction at both the link and path levels. In the case where the original FPCA is modified for parallelization, accuracy and computational effort are evaluated and compared with those of the sequential algorithm. The proposed algorithm is found to require only a piece rather than a large set of traffic incident records.     

Identifying the onset of congestion rapidly with existing traffic detectors

From an operations standpoint the most important function of a traffic surveillance system is determining reliably whether the facility is free flowing or congested. The second most important function is responding rapidly when the facility becomes congested. These functions are complicated by the fact that conventional vehicle detectors are only capable of monitoring discrete points along the roadway while incidents may occur at any location on the facility. The point detectors are typically placed at least one-third of a mile apart and conditions between the detectors must be inferred from the local measurements.This paper presents a new approach for traffic surveillance that addresses these issues. It uses existing dual loop detector stations to match vehicle measurements between stations and monitor the entire roadway. Rather than expending a considerable effort to detect congested conditions, the research employs a relatively simple strategy to look for free flow traffic. Whenever a unique vehicle passes the downstream station, the algorithm looks to see if a similar vehicle passed the upstream station within a time window that is bounded by feasible travel times. The approach provides vehicle reidentification and travel time measurement on freeways during free flow and through the onset of congestion. If desired, other algorithms can be used with the same detectors to provide similar measurements during congested conditions. The work should prove beneficial for traffic management and traveler information applications, while promising to be deployable in the short term.     

Cost scaling based successive approximation algorithm for the traffic assignment problem

This paper presents a cost scaling based successive approximation algorithm, called ε-BA (ε-optimal bush algorithm), to solve the user equilibrium traffic assignment problem by successively refining ε-optimal flows. As ε reduces to zero, the user equilibrium solution is reached. The proposed method is a variant of bush-based algorithms, and also a variant of the min-mean cycle algorithm to solve the min-cost flow by successive approximation. In ε-BA, the restricted master problem, implying traffic equilibration restricted on a bush, is solved to ε-optimality by cost scaling before bush reconstruction. We show that ε-BA can reduce the number of flow operations substantially in contrast to Dial’s Algorithm B, as the former operates flows on a set of deliberately selected cycles whose mean values are sufficiently small. Further, the bushes can be constructed effectively even if the restricted master problem is not solved to a high level of convergence, by leveraging the ε-optimality condition. As a result, the algorithm can solve a highly precise solution with faster convergence on large-scale networks compared to our implementation of Dial’s Algorithm B.     

Development of origin–destination matrices using mobile phone call data

In this research, we propose a methodology to develop OD matrices using mobile phone Call Detail Records (CDR) and limited traffic counts. CDR, which consist of time stamped tower locations with caller IDs, are analyzed first and trips occurring within certain time windows are used to generate tower-to-tower transient OD matrices for different time periods. These are then associated with corresponding nodes of the traffic network and converted to node-to-node transient OD matrices. The actual OD matrices are derived by scaling up these node-to-node transient OD matrices. An optimization based approach, in conjunction with a microscopic traffic simulation platform, is used to determine the scaling factors that result best matches with the observed traffic counts. The methodology is demonstrated using CDR from 2.87 million users of Dhaka, Bangladesh over a month and traffic counts from 13 key locations over 3 days of that month. The applicability of the methodology is supported by a validation study.     

A flexible traffic stream model and its three representations of traffic flow

To connect microscopic driving behaviors with the macro-correspondence (i.e., the fundamental diagram), this study proposes a flexible traffic stream model, which is derived from a novel car-following model under steady-state conditions. Its four driving behavior-related parameters, i.e., reaction time, calmness parameter, speed- and spacing-related sensitivities, have an apparent effect in shaping the fundamental diagram. Its boundary conditions and homogenous case are also analyzed in detail and compared with other two models (i.e., Longitudinal Control Model and Intelligent Driver Model). Especially, these model formulations and properties under Lagrangian coordinates provide a new perspective to revisit the traffic flow and complement with those under Eulerian coordinate. One calibration methodology that incorporates the monkey algorithm with dynamic adaptation is employed to calibrate this model, based on real-field data from a wide range of locations. Results show that this model exhibits the well flexibility to fit these traffic data and performs better than other nine models. Finally, a concrete example of transportation application is designed, in which the impact of three critical parameters on vehicle trajectories and shock waves with three representations (i.e., respectively defined in x-t, n-t and x-n coordinates) is tested, and macro- and micro-solutions on shock waves well agree with each other. In summary, this traffic stream model with the advantages of flexibility and efficiency has the good potential in level of service analysis and transportation planning.     

Travel time prediction and departure time adjustment behavior dynamics in a congested traffic system

This paper examines two heuristic rules proposed for describing urban commuters' predictions of travel time as well as the adjustments of departure time in response to unacceptable arrivals in their daily commute under limited information. It is based on the notion that the magnitude of the predicted travel time depends on each commuter's own experience, including recallable travel time, schedule delay, and difficulties in searching for a satisfactory departure time. An explanatory analysis is first performed to compare these two rules, based on the information provided by a set of commuters interacting over 24 days through a simulated traffic system. A more elaborate model specification which captures the dynamic interrelation between the commuter's cumulative and recent experience with the traffic system's performance is then proposed. The model parameters are estimated with explicit consideration of the serial correlation arising from repeated decisions by the same individuals and the contemporaneous interaction with other system users' decisions through the traffic system's performance.