Determining structural route components from GPS traces

Analysis of GPS traces shows that people often do not use the least cost path through the transportation network while making trips. This leads to the question which structural path characteristics can be used to construct realistic route choice sets for use in traffic simulation models. In this paper, we investigate the hypothesis that, for utilitarian trips, the route between origin and destination consists of a small number of concatenated least cost paths. The hypothesis is verified by analyzing routes extracted from large sets of recorded GPS traces which constitute revealed preference information. Trips have been extracted from the traces and for each trip the path in the transportation network is determined by map matching. This is followed by a path decomposition phase for which the algorithm constitutes the first contribution of this paper. There are multiple ways to split a given path in a directed graph into a minimal number of subpaths of minimal cost. By calculating two specific path splittings, it is possible to identify subsets of the vertices (splitVertexSuites) that can be used to generate every possible minimum path splitting by taking one vertex from each such subset. As a second contribution, we show how the extracted information is used in microscopic travel simulation. The distribution for the size of the minimum decomposition, extracted from the GPS traces, can be used in constrained enumeration methods for route choice set generation. The sets of vertices that can act as boundary vertices separating consecutive route parts contain way points (landmarks) having a particular meaning to their user. The paper explains the theoretical aspects of route splitting as well as the process to extract splitVertexSuites from big data. It reports statistical distributions extracted from sets of GPS traces for both multimodal person movements and unimodal car trips.     

A new probability statistical model for traffic noise prediction on free flow roads and control flow roads

A new traffic noise prediction approach based on a probability distribution model of vehicle noise emissions and achieved by Monte Carlo simulation is proposed in this paper. The probability distributions of the noise emissions of three types of vehicles are obtained using an experimental method. On this basis, a new probability statistical model for traffic noise prediction on free flow roads and control flow roads is established. The accuracy of the probability statistical model is verified by means of a comparison with the measured data, which has shown that the calculated results of L_eq, L₁₀, L₅₀, L₉₀, and the probability distribution of noise level occurrence agree well with the measurements. The results demonstrate that the new method can avoid the complicated process of traffic flow simulation but still maintain high accuracy for the traffic noise prediction.     

Distributed computing approaches for large‐scale probit‐based stochastic user equilibrium problems

Applications of probit‐based stochastic user equilibrium (SUE) principle on large‐scale networks have been largely limited because of the overwhelming computational burden in solving its stochastic network loading problem. A two‐stage Monte Carlo simulation method is recognized to have satisfactory accuracy level when solving this stochastic network loading. This paper thus works on the acceleration of the Monte Carlo simulation method via using distributed computing system. Three distributed computing approaches are then adopted on the workload partition of the Monte Carlo simulation method. Wherein, the first approach allocates each processor in the distributed computing system to solve each trial of the simulation in parallel and in turns, and the second approach assigns all the processors to solve the shortest‐path problems in one trial of the Monte Carlo simulation concurrently. The third approach is a combination of the first two, wherein both different trials of the Monte Carlo simulation as well as the shortest path problems in one trial are solved simultaneously. Performances of the three approaches are comprehensively tested by the Sioux‐Falls network and then a randomly generated network example. It shows that computational time for the probit‐based SUE problem can be largely reduced by any of these three approaches, and the first approach is found out to be superior to the other two. The first approach is then selected to calculate the probit‐based SUE problem on a large‐scale network example. Copyright © 2011 John Wiley & Sons, Ltd.     

A Bayesian approach for modeling origin-destination matrices

The majority of origin destination (OD) matrix estimation methods focus on situations where weak or partial information, derived from sample travel surveys, is available. Information derived from travel census studies, in contrast, covers the entire population of a specific study area of interest. In such cases where reliable historical data exist, statistical methodology may serve as a flexible alternative to traditional travel demand models by incorporating estimation of trip-generation, trip-attraction and trip-distribution in one model. In this research, a statistical Bayesian approach on OD matrix estimation is presented, where modeling of OD flows derived from census data, is related only to a set of general explanatory variables. A Poisson and a negative binomial model are formulated in detail, while emphasis is placed on the hierarchical Poisson-gamma structure of the latter. Problems related to the absence of closed-form expressions are bypassed with the use of a Markov Chain Monte Carlo method known as the Metropolis-Hastings algorithm. The methodology is tested on a realistic application area concerning the Belgian region of Flanders on the level of municipalities. Model comparison indicates that negative binomial likelihood is a more suitable distributional assumption than Poisson likelihood, due to the great degree of overdispersion present in OD flows. Finally, several predictive goodness-of-fit tests on the negative binomial model suggest a good overall fit to the data. In general, Bayesian methodology reduces the overall uncertainty of the estimates by delivering posterior distributions for the parameters of scientific interest as well as predictive distributions for future OD flows.     

Bayesian inference for day-to-day dynamic traffic models

There is significant current interest in the development of models to describe the day-to-day evolution of traffic flows over a network. We consider the problem of statistical inference for such models based on daily observations of traffic counts on a subset of network links. Like other inference problems for network-based models, the critical difficulty lies in the underdetermined nature of the linear system of equations that relates link flows to the latent path flows. In particular, Bayesian inference implemented using Markov chain Monte Carlo methods requires that we sample from the set of route flows consistent with the observed link flows, but enumeration of this set is usually computationally infeasible.We show how two existing conditional route flow samplers can be adapted and extended for use with day-to-day dynamic traffic. The first sampler employs an iterative route-by-route acceptance–rejection algorithm for path flows, while the second employs a simple Markov model for traveller behaviour to generate candidate entire route flow patterns when the network has a tree structure. We illustrate the application of these methods for estimation of parameters that describe traveller behaviour based on daily link count data alone.     

Rural highway route corridor selection

The selection of a rural highway corridor between designated termini is approached as the simultaneous selection of line and grade of a particular alignment in the corridor. The selection is facilitated by the successive application of linear programming and shortest path techniques. A model is presented in which the inputs are terrain elevations, design constraints on overall grade, terminal grades and elevations, and restricted areas of passage. The output consists of a user‐specified number of alternative corridors, selected on the basis of minimum sum of the deviations of their representative profiles from the original ground. The model is applicable to situations where route selection is dominated by construction considerations. A hypothetical example and an actual application demonstrate the utility of the methodology.     

A stochastic transit assignment model using a dynamic schedule-based network

Using the schedule-based approach, in which scheduled time-tables are used to describe the movement of vehicles, a dynamic transit assignment model is formulated. Passengers are assumed to travel on a path with minimum generalized cost which consists of four components: in-vehicle time; waiting time; walking time; and a time penalty for each line change. With the exception of in-vehicle time, each of the other cost components is weighted by a sensitivity coefficient which varies among travelers and is defined by a density function. This time-dependent and stochastic minimum path is generated by a specially developed branch and bound algorithm. The assignment procedure is conducted over a period in which both passenger demand and train headways are varying. Due to the stochastic nature of the assignment problem, a Monte Carlo approach is employed to solve the problem. A case study using the Mass Transit Railway System in Hong Kong is given to demonstrate the model and its potential applications.     

Information metrics for improved traffic model fidelity through sensitivity analysis and data assimilation

We develop theoretical and computational tools which can appraise traffic flow models and optimize their performance against current time-series traffic data and prevailing conditions. The proposed methodology perturbs the parameter space and undertakes path-wise analysis of the resulting time series. Most importantly the approach is valid even under non-equilibrium conditions and is based on procuring path-space (time-series) information. More generally we propose a mathematical methodology which quantifies traffic information loss.In particular the method undertakes sensitivity analysis on available traffic data and optimizes the traffic flow model based on two information theoretic tools which we develop. One of them, the relative entropy rate, can adjust and optimize model parameter values in order to reduce the information loss. More precisely, we use the relative entropy rate as an information metric between time-series data and parameterized stochastic dynamics describing a microscopic traffic model. On the other hand, the path-space Fisher Information Matrix, (pFIM) reduces model complexity and can even be used to control fidelity. This is achieved by eliminating unimportant model parameters or their combinations. This results in easier regression of parametric models with a smaller number of parameters.The method reconstructs the Markov Chain and emulates the traffic dynamics through Monte Carlo simulations. We use the microscopic interaction model from Sopasakis and Katsoulakis (2006) as a representative traffic flow model to illustrate this parameterization methodology. During the comparisons we use both synthetic and real, rush-hour, traffic data from highway US-101 in Los Angeles, California.     

Sampling of alternatives in Logit Mixture models

Employing a strategy of sampling of alternatives is necessary for various transportation models that have to deal with large choice-sets. In this article, we propose a method to obtain consistent, asymptotically normal and relatively efficient estimators for Logit Mixture models while sampling alternatives. Our method is an extension of previous results for Logit and MEV models. We show that the practical application of the proposed method for Logit Mixture can result in a Naïve approach, in which the kernel is replaced by the usual sampling correction for Logit. We give theoretical support for previous applications of the Naïve approach, showing not only that it yields consistent estimators, but also providing its asymptotic distribution for proper hypothesis testing. We illustrate the proposed method using Monte Carlo experimentation and real data. Results provide further evidence that the Naïve approach is suitable and practical. The article concludes by summarizing the findings of this research, assessing their potential impact, and suggesting extensions of the research in this area.     

Continuity of the path delay operator for dynamic network loading with spillback

This paper establishes the continuity of the path delay operators for dynamic network loading (DNL) problems based on the Lighthill–Whitham–Richards model, which explicitly capture vehicle spillback. The DNL describes and predicts the spatial-temporal evolution of traffic flow and congestion on a network that is consistent with established route and departure time choices of travelers. The LWR-based DNL model is first formulated as a system of partial differential algebraic equations. We then investigate the continuous dependence of merge and diverge junction models with respect to their initial/boundary conditions, which leads to the continuity of the path delay operator through the wave-front tracking methodology and the generalized tangent vector technique. As part of our analysis leading up to the main continuity result, we also provide an estimation of the minimum network supply without resort to any numerical computation. In particular, it is shown that gridlock can never occur in a finite time horizon in the DNL model.     

Prediction of vehicle CO2 emission and its application to eco-routing navigation

Transportation sector accounts for a large proportion of global greenhouse gas and toxic pollutant emissions. Even though alternative fuel vehicles such as all-electric vehicles will be the best solution in the future, mitigating emissions by existing gasoline vehicles is an alternative countermeasure in the near term. The aim of this study is to predict the vehicle CO₂ emission per kilometer and determine an eco-friendly path that results in minimum CO₂ emissions while satisfying travel time budget. The vehicle CO₂ emission model is derived based on the theory of vehicle dynamics. Particularly, the difficult-to-measure variables are substituted by parameters to be estimated. The model parameters can be estimated by using the current probe vehicle systems. An eco-routing approach combining the weighting method and k-shortest path algorithm is developed to find the optimal path along the Pareto frontier. The vehicle CO₂ emission model and eco-routing approach are validated in a large-scale transportation network in Toyota city, Japan. The relative importance analysis indicates that the average speed has the largest impact on vehicle CO₂ emission. Specifically, the benefit trade-off between CO₂ emission reduction and the travel time buffer is discussed by carrying out sensitivity analysis in a network-wide scale. It is found that the average reduction in CO₂ emissions achieved by the eco-friendly path reaches a maximum of around 11% when the travel time buffer is set to around 10%.     

Quantifying errors in micro-scale emissions models using a case-study approach

To quantify the level of uncertainty attached to forecasts of CO₂ emissions, an analysis of errors is undertaken; looking at both errors inherent in the model structure and the uncertainties in the input data. Both error types are treated in relation to CO₂ emissions modelling using a case-study from Brisbane, Australia. To estimate input data uncertainty, an analysis of traffic conditions using Monte Carlo simulation is used. Model structure induced uncertainties are also quantified by statistical analysis for a number of traffic scenarios. To arrive at an optimal overall CO₂ prediction, the interaction between the two components is taken into account. Since a more complex model does not necessarily yield higher overall accuracy, a compromise solution is found. The results suggest that the CO₂ model used in the analysis produces low overall uncertainty under free flow traffic conditions. When average traffic speeds approach congested conditions, however, there are significant errors associated with emissions estimates.     

Application of Lagrangian relaxation approach to α-reliable path finding in stochastic networks with correlated link travel times

This study investigates the important problem of determining a reliable path in a stochastic network with correlated link travel times. First, the distribution of path travel time is quantified by using trip records from GPS probe vehicles. Second, the spatial correlation of link travel time is explicitly considered by using a correlation coefficient matrix, which is incorporated into the α-reliable path problem by Cholesky decomposition. Third, the Lagrangian relaxation based framework is used to handle the α-reliable path problem, by which the intractable problem with a non-linear and non-additive structure can be decomposed into several easy-to-solve problems. Finally, the path-finding performance of this approach is tested on a real-world network. The results show that 15 iterations of calculation can yield a small relative gap between upper and lower bounds of the optimal solution and the average running time is about 5 s for most OD settings. The applicability of α-reliable path finding is validated by a case study.     

Finding time‐robust fuel‐efficient paths for a call‐taxi in a stochastic city road network

Intra‐city commuting is being revolutionized by call‐taxi services in many developing countries such as India. A customer requests a taxi via phone, and it arrives at the right time and at the right location for the pick‐up. This mode of intra‐city travel has become one of the most reliable and convenient modes of transportation for customers traveling for business and non‐business purposes. The increased number of vehicles on city roads and raising fuel costs has prompted a new type of transportation logistics problem of finding a fuel‐efficient and quickest path for a call‐taxi through a city road network, where the travel times are stochastic. The stochastic travel time of the road network is induced by obstacles such as the traffic signals and intersections. The delay and additional fuel consumption at each of these obstacles are calculated that are later imputed to the total travel time and fuel consumption of a path. A Monte‐Carlo simulation‐based approach is proposed to identify unique fuel‐efficient paths between two locations in a city road network where each obstacle has a delay distribution. A multi‐criteria score is then assigned to each unique path based on the probability that the path is fuel efficient, the average travel time of the path and the coefficient of variation of the travel times of the path. Copyright © 2016 John Wiley & Sons, Ltd.     

Boundedly rational user equilibria (BRUE): Mathematical formulation and solution sets

Boundedly rational user equilibria (BRUE) represent traffic flow distribution patterns where travellers can take any route whose travel cost is within an ‘indifference band’ of the shortest path cost. Those traffic flow patterns satisfying the above condition constitute a set, named the BRUE solution set. It is important to obtain all the BRUE flow patterns, because it can help predict the variation of the link flow pattern in a traffic network under the boundedly rational behavior assumption. However, the methodology of constructing the BRUE set has been lacking in the established literature. This paper fills the gap by constructing the BRUE solution set on traffic networks with fixed demands. After defining ε-BRUE, where ε is the indifference band for the perceived travel cost, we formulate the ε-BRUE problem as a nonlinear complementarity problem (NCP), so that a BRUE solution can be obtained by solving a BRUE–NCP formulation. To obtain the BRUE solution set encompassing all BRUE flow patterns, we propose a methodology of generating acceptable path set which may be utilized under the boundedly rational behavior assumption. We show that with the increase of the indifference band, the acceptable path set that contains boundedly rational equilibrium flows will be augmented, and the critical values of indifference band to augment these path sets can be identified by solving a family of mathematical programs with equilibrium constraints (MPEC) sequentially. The BRUE solution set can then be obtained by assigning all traffic demands to the acceptable path set. Various numerical examples are given to illustrate our findings.     

Simulation of fixed route bus travel time

Travel time on fixed route urban bus route is discussed. Given that the travel time is a function of three basic variables, Monte Carlo procedure is used to simulate trips during a specific time interval. Each variable is assumed to have a specific probability distribution with known or estimatable parameters. It is shown that this micro-computer simulation model can be used for examining the effects of traffic management schemes, number of stops and passenger demand on travel time, and subsequently fleet size and level of service.     

Statistical inference on transit route‐level origin–destination flows using automatic passenger counter data

We consider inferring transit route‐level origin–destination (OD) flows using large amounts of automatic passenger counter (APC) boarding and alighting data based on a statistical formulation. One critical problem is that we need to enumerate the OD flow matrices that are consistent with the APC data for each bus trip to evaluate the model likelihood function. The OD enumeration problem has not been addressed satisfactorily in the literature. Thus, we propose a novel sampler to avoid the need to enumerate OD flow matrices by generating them recursively from the first alighting stop to the last stop of the bus route of interest. A Markov chain Monte Carlo (MCMC) method that incorporates the proposed sampler is developed to simulate the posterior distributions of the OD flows. Numerical investigations on an operational bus route under a realistic OD structure demonstrate the superiority of the proposed MCMC method over an existing MCMC method and a state‐of‐the‐practice method. Copyright © 2015 John Wiley & Sons, Ltd.     

Reliable route guidance: A case study from Chicago

Reliable route guidance can be obtained by solving the reliable a priori shortest path problem, which finds paths that maximize the probability of arriving on time. The goal of this paper is to demonstrate the benefits and applicability of such route guidance using a case study. An adaptive discretization scheme is first proposed to improve the efficiency in computing convolution, a time-consuming step used in the reliable routing algorithm to obtain path travel time distributions. Methods to construct link travel time distributions from real data in the case study are then discussed. Particularly, the travel time distributions on arterial streets are estimated from linear regression models calibrated from expressway data. Numerical experiments demonstrate that optimal paths are substantially affected by the reliability requirement in rush hours, and that reliable route guidance could generate up to 5-15% of travel time savings. The study also verifies that existing algorithms can solve large-scale problems within a reasonable amount of time.     

Statistical models of discrete choice processes

A number of problems studied in the transportation literature, such as automobile choice, motorist route choice, and transportation mode choice, involve an agent who makes a series of discrete choices over time. This paper presents statistical models and estimation methods for such discrete choice processes, and illustrates potential applications of these methods to the transportation literature.     

A simulation‐based reliability assessment approach for congested transit network

This paper is an attempt to develop a generic simulation‐based approach to assess transit service reliability, taking into account interaction between network performance and passengers' route choice behaviour. Three types of reliability, say, system wide travel time reliability, schedule reliability and direct boarding waiting‐time reliability are defined from perspectives of the community or transit administration, the operator and passengers. A Monte Carlo simulation approach with a stochastic user equilibrium transit assignment model embedded is proposed to quantify these three reliability measures of transit service. A simple transit network with a bus rapid transit (BRT) corridor is analysed as a case study where the impacts of BRT components on transit service reliability are evaluated preliminarily.