A solution algorithm for a dynamic deterministic user equilibrium assignment model with departure time choice

Abstract

A route-based combined model of dynamic deterministic route and departure time choice and a solution method for many origin and destination pairs is proposed. The divided linear travel time model is used to calculate the link travel time and to describe the propagation of flow over time. For the calculation of route travel times, the predictive ideal route travel time concept is adopted. Solving the combined model of dynamic deterministic route and departure time choice is shown to be equivalent to solving simultaneously a system of non-linear equations. A Newton-type iterative scheme is proposed to solve this problem. The performance of the proposed solution method is demonstrated using a version of the Sioux Falls network. This shows that the proposed solution method produces good equilibrium solutions with reasonable computational cost.     

Discretised link travel time models based on cumulative flows: Formulations and properties

In the research area of dynamic traffic assignment, link travel times can be derived from link cumulative inflow and outflow curves which are generated by dynamic network loading. In this paper, the profiles of cumulative flows are piecewise linearized. Both the step function (SF) and linear interpolation (LI) are used to approximate cumulative flows over time. New formulations of the SF-type and LI-type link travel time models are developed. We prove that these two types of link travel time models ensure first-in-first-out (FIFO) and continuity of travel times with respect to flows, and have other desirable properties. Since the LI-type link travel time model does not satisfy the causality property, a modified LI-type (MLI-type) link travel time model is proposed in this paper. We prove that the MLI-type link travel time model ensures causality, strong FIFO and travel time continuity, and that the MLI-type link travel time function is strictly monotone under the condition that the travel time of each vehicle on a link is greater than the free flow travel time on that link. Numerical examples are set up to illustrate the properties and accuracy of the three models.     

The estimation of a time-dependent OD trip table with vehicle trajectory samples

Abstract

In this paper we discuss a dynamic origin–destination (OD) estimation problem that has been used for identifying time-dependent travel demand on a road network. Even though a dynamic OD table is an indispensable data input for executing a dynamic traffic assignment, it is difficult to construct using the conventional OD construction method such as the four-step model. For this reason, a direct estimation method based on field traffic data such as link traffic counts has been used. However, the method does not account for a logical relationship between a travel demand pattern and socioeconomic attributes. In addition, the OD estimation method cannot guarantee the reliability of estimated results since the OD estimation problem has a property named the ‘underdetermined problem.’ In order to overcome such a problem, the method developed in this paper makes use of vehicle trajectory samples with link traffic counts. The new method is applied to numerical examples and shows promising capability for identifying a temporal and spatial travel demand pattern.     

Some features of non-linear travel time models for dynamic traffic assignment

Abstract

This paper investigates some features of non-linear travel time models for dynamic traffic assignment (DTA) that adopt traffic on the link as the sole determinant for the calculation of travel time and have explicit relationships between travel time and traffic on the link. Analytical proofs and numerical examples are provided to show first-in-first-out (FIFO) violation and the behaviour of decreasing outflow with increasing traffic in non-linear travel time models. It is analytically shown that any non-linear travel time model could violate FIFO in some circumstances, especially when inflow drops sharply, and some convex non-linear travel time models could show behaviour with outflow decreasing as traffic increases. It is also shown that the linear travel time model does not show these behaviours. A non-linear travel time model in general form was used for analytical proofs and several existing non-linear travel time models were adopted for numerical examples. Considering the features addressed in this study, non-linear travel time models seem to have limitations for use in DTA in practical terms and care should be taken when they are used for modelling time-varying transportation networks.     

A methodology to estimate travel time using dynamic traffic assignment (DTA) under incident conditions

This paper presents results from a research case study that examined the distribution of travel time of origin–destination (OD) pairs on a transportation network under incident conditions. Using a transportation simulation dynamic traffic assignment (DTA) model, incident on a transportation network is executed under normal conditions, incident conditions without traveler information availability, and incident conditions assuming that users had perfect knowledge of the incident conditions and could select paths to avoid the incident location. The results suggest that incidents have a different impact on different OD pairs. The results confirm that an effective traveler information system has the potential to ease the impacts of incident conditions network wide. Yet it is also important to note that the use of information may detriment some OD pairs while benefiting other OD pairs. The methodology demonstrated in this paper provides insights into the usefulness of embedding a fully calibrated DTA model into the analysis tools of a traffic management and information center.     

Investigating the effect of travel time variability on drivers' route choice decisions in Shanghai,China

Abstract

This paper investigates the effect of travel time variability on drivers' route choice behavior in the context of Shanghai, China. A stated preference survey is conducted to collect drivers' hypothetical choice between two alternative routes with designated unequal travel time and travel time variability. A binary choice model is developed to quantify trade-offs between travel time and travel time variability across various types of drivers. In the model, travel time and travel time variability are, respectively, measured by expectation and standard deviation of random travel time. The model shows that travel time and travel time variability on a route exert similarly negative effects on drivers' route choice behavior. In particular, it is found that middle-age drivers are more sensitive to travel time variability and less likely to choose a route with travel time uncertainty than younger and elder drivers. In addition, it is shown that taxi drivers are more sensitive to travel time and more inclined to choose a route with less travel time. Drivers with rich driving experience are less likely to choose a route with travel time uncertainty.     

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.     

Estimating freeway route travel time distributions with consideration to time‐of‐day,inclement weather,and traffic incidents

This paper develops an efficient probabilistic model for estimating route travel time variability, incorporating factors of time‐of‐day, inclement weather, and traffic incidents. Estimating the route travel time distribution from historical link travel time data is challenging owing to the interactions among upstream and downstream links. Upon creating conditional probability function for each link travel time, we applied Monte Carlo simulation to estimate the total travel time from origin to destination. A numerical example of three alternative routes in the City of Buffalo shows several implications. The study found that weather conditions, except for snow, incur minor impact on off‐peak and weekend travel time, whereas peak travel times suffer great variations under different weather conditions. On top of that, inclement weather exacerbates route travel time reliability, even when mean travel time increases moderately. The computation time of the proposed model is linearly correlated to the number of links in a route. Therefore, this model can be used to obtain all the origin to destination travel time distributions in an urban region. Further, this study also validates the well‐known near‐linear relation between the standard deviation of travel time per unit distance and the corresponding mean value under different weather conditions. Copyright © 2016 John Wiley & Sons, Ltd.     

Complementarity formulations for the cell transmission model based dynamic user equilibrium with departure time choice, elastic demand and user heterogeneity

In this paper we formulate the dynamic user equilibrium problem with an embedded cell transmission model on a network with a single OD pair, multiple parallel paths, multiple user classes with elastic demand. The formulation is based on ideas from complementarity theory. The travel time is estimated based on two methods which have different transportation applications: (1) maximum travel time and (2) average travel time. These travel time functions result in linear and non-linear complementarity formulations respectively. Solution existence and the properties of the formulations are rigorously analyzed. Extensive computational experiments are conducted to demonstrate the benefits of the proposed formulations on various test networks.     

Multiple equilibria in a dynamic traffic network

This study provides an example in which the dynamic user equilibrium (DUE) assignment of a congested road network with bottlenecks is non-unique. In previous studies, the uniqueness of DUE assignments with the bottleneck model has been shown in limited cases such as single-origin and single-destination networks. Consequently, it is still an important issue whether or not uniqueness is a general property of DUE assignments. The present study describes a network in which multiple patterns of link travel time are found, thus providing a negative answer to this question. The network has a loopy structure with multiple bottlenecks and multiple origin-destination (OD) pairs. Given a certain demand pattern of departure times for vehicles leaving their origins, a non-convex set of equilibria with a non-unique pattern of link travel times is shown to exist.     

A reliability‐based traffic assignment model for multi‐modal transport network under demand uncertainty

In densely populated and congested urban areas, the travel times in congested multi‐modal transport networks are generally varied and stochastic in practice. These stochastic travel times may be raised from day‐to‐day demand fluctuations and would affect travelers' route and mode choice behaviors according to their different expectations of on‐time arrival. In view of these, this paper presents a reliability‐based user equilibrium traffic assignment model for congested multi‐modal transport networks under demand uncertainty. The stochastic bus frequency due to the unstable travel time of bus route is explicitly considered. By the proposed model, travelers' route and mode choice behaviors are intensively explored. In addition, a stochastic state‐augmented multi‐modal transport network is adopted in this paper to effectively model probable transfers and non‐linear fare structures. A numerical example is given to illustrate the merits of the proposed model. Copyright © 2012 John Wiley & Sons, Ltd.     

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.     

Modeling Travel Time Under ATIS Using Mixed Linear Models

The objective of this paper is to model travel time when drivers are equipped with pre-trip and/or en-route real-time traffic information/advice. A travel simulator with a realistic network and real historical congestion levels was used as a data collection tool. The network included 40 links and 25 nodes. This paper presents models of the origin-to-destination travel time and en-route short-term route (link) travel time under five different types and levels of advanced traveler information systems (ATIS). Mixed linear models with the repeated observation's technique were used in both models. Different covariance structures (including the independent case) were developed and compared. The effect of correlation was found significant in both models. The trip travel time analysis showed that as the level of information increases (adding en-route to the pre-trip and advice to the advice-free information), the average travel time decreases. The model estimates show that providing pre-trip and en-route traffic information with advice could result in significant savings in the overall travel time. The en-route short-term (link) travel time analysis showed that the en-route short-term (link) information has a good chance of being used and followed. The short-term qualitative information is more likely to be used than quantitative information. Learning and being familiar with the system that provides the information decreases en-route short-term delay.     

Application of the support vector machine and heuristic k-shortest path algorithm to determine the most eco-friendly path with a travel time constraint

This study aims to determine an eco-friendly path that results in minimum CO₂ emissions while satisfying a specified budget for travel time. First, an aggregated CO₂ emission model for light-duty cars is developed in a link-based level using a support vector machine. Second, a heuristic k-shortest path algorithm is proposed to solve the constrained shortest path problem. Finally, the CO₂ emission model and the proposed eco-routing model are validated in a real-world network. Specifically, the benefit of the trade-off between CO₂ emission reduction and the travel time budget is discussed by carrying out sensitivity analysis on a network-wide scale. A greater spare time budget may enable the eco-routing to search for the most eco-friendly path with higher probability. Compared to the original routes selected by travelers, the eco-friendly routes can save an average of 11% of CO₂ emissions for the trip OD pairs with a straight distance between 6 km and 9 km when the travel time budget is set to 10% above the least travel time. The CO₂ emission can also be reduced to some degree for other OD pairs by using eco-routing. Furthermore, the impact of market penetration of eco-routing users is quantified on the potential benefit for the environment and travel-time saving.     

A multi‐class mean‐excess traffic equilibrium model with elastic demand

Recent empirical studies have revealed that travel time variability plays an important role in travelers' route choice decisions. To simultaneously account for both reliability and unreliability aspects of travel time variability, the concept of mean‐excess travel time (METT) was recently proposed as a new risk‐averse route choice criterion. In this paper, we extend the mean‐excess traffic equilibrium model to include heterogeneous risk‐aversion attitudes and elastic demand. Specifically, this model explicitly considers (1) multiple user classes with different risk‐aversions toward travel time variability when making route choice decisions under uncertainty and (2) the elasticity of travel demand as a function of METT when making travel choice decisions under uncertainty. This model is thus capable of modeling travelers' heterogeneous risk‐averse behaviors with both travel choice and route choice considerations. The proposed model is formulated as a variational inequality problem and solved via a route‐based algorithm using the modified alternating direction method. Numerical analyses are also provided to illustrate the features of the proposed model and the applicability of the solution algorithm. Copyright © 2012 John Wiley & Sons, Ltd.     

A framework for neighbour links travel time estimation in an urban network

This paper proposes a solution to the problem of limited network sensor coverage caused by insufficient sample size of probe vehicles or inadequate numbers of fixed sensors. A framework is proposed to estimate link travel times using available data from neighbouring links. Two clues are used for real-time travel time estimation: link historical travel time data and online travel time data from neighbour links. In the absence of online travel time data from neighbour links, historical records only have to be relied upon. However, where the two types of data are available, a data fusion scheme can be applied to make use of the two clues. The proposed framework is validated using real-life data from the City of Vancouver, British Columbia. The estimation accuracy is found to be comparable to the existing literature. Overall, the results demonstrate the feasibility of using neighbour links data as an additional source of information that might not have been extensively explored before.     

On the goods-activities technical relations in the time allocation theory

In areas like household production and travel choice, time assigned to the different activities plays a key role in addition to consumption as the main variables in utility within the consumer behaviour framework. However, a comprehensive conceptual structure to understand the technological relations between goods consumption and the assignment of time to activities is still lacking. In this paper the problem is reviewed and all possible relations between goods and time are re-formulated. Two general functions are defined and proposed to account for all these relations, forming a new taxonomy for the technical constraints. The resulting consumer behaviour model is used to obtain general expressions for both the value of saving time in constrained activities like travel, and the value of leisure.     

Performance measure for reliable travel time of emergency vehicles

Travel time is very critical for emergency response and emergency vehicle (EV) operations. Compared to ordinary vehicles (OVs), EVs are permitted to break conventional road rules to reach the destination within shorter time. However, very few previous studies address the travel time performance of EVs. This study obtained nearly 4-year EV travel time data in Northern Virginia (NOVA) region using 76,000 preemption records at signalized intersections. First, the special characteristics of EV travel time are explored in mean, median, standard deviation and also the distribution, which display largely different characteristics from that of OVs in previous studies. Second, a utility-based model is proposed to quantify the travel time performance of EVs. Third, this paper further investigates two important components of the utility model: benchmark travel time and standardized travel time. The mode of the distribution is chosen as benchmark travel time, and its nonlinear decreasing relationship with the link length is revealed. At the same time, the distribution of standardized travel time is fitted with different candidate distributions and Inv. Gaussian distribution is proved to be the most suitable one. Finally, to validate the proposed model, we implement the model in case studies to estimate link and route travel time performance. The results of route comparisons also show that the proposed model can support EV route choice and eventually improve EV service and operations.     

An empirical study to determine freight travel time at a major port

Abstract

This paper examines the reliability measures of freight travel time on urban arterials that provide access to an international seaport. The findings indicate that the reliability index calculated by the median of travel time, which is less sensitive to extreme values in a highly skewed distribution, is more appropriate. This paper also examines several statistical distributions of travel time to determine the best fit to the data of freight trips. The results of goodness-of-fit tests indicate that the log-logistic is the best statistical function for freight travel time during the midday off-peak period. However, the lognormal distribution represents a better fit to arterials with heavily congested traffic during peak periods. Additionally, travel time prediction models identify the relationships between travel time, speeds and other factors that affect travel time reliability. The analysis suggests that incident-induced delays and speed fluctuations primarily contributed to the unreliability of freight movement on the urban arterials.     

Multiclass fuzzy user equilibrium with endogenous membership functions and risk‐taking behaviors

Over the last decades, several approaches have been proposed in the literature to incorporate users' perceptions of travel costs, their bounded rationality, and risk‐taking behaviors into network equilibrium modeling for traffic assignment problem. While theoretically advanced, these models often suffer from high complexity and computational cost and often involve parameters that are difficult to estimate. This study proposes an alternative approach where users' imprecise perceptions of travel times are endogenously constructed as fuzzy sets based on the probability distributions of random link travel times. Two decision rules are proposed accordingly to account for users' heterogeneous risk‐taking behaviors, that is, optimistic and pessimistic rules. The proposed approach, namely, the multiclass fuzzy user equilibrium, can be formulated as a link‐based variational inequality model. The model can be solved efficiently, and parameters involved can be either easily estimated or treated as factors for calibration against observed traffic flow data. Numerical examples show that the proposed model can be solved efficiently even for a large‐scale network of Mashhad, Iran, with 2538 links and 7157 origin–destination pairs. The example also illustrates the calibration capability of the proposed model, highlighting that the model is able to produce much more accurate flow estimates compared with the Wardropian user equilibrium model. Copyright © 2016 John Wiley & Sons, Ltd.