Route Choice Models Used in the Stochastic User Equilibrium Problem: A Review

Several route choice models are reviewed in the context of the stochastic user equilibrium problem. The traffic assignment problem has been extensively studied in the literature. Several models were developed focusing mainly on the solution of the link flow pattern for congested urban areas. The behavioural assumption governing route choice, which is the essential part of any traffic assignment model, received relatively much less attention. The core of any traffic assignment method is the route choice model. In the wellknown deterministic case, a simple choice model is assumed in which drivers choose their best route. The assumption of perfect knowledge of travel costs has been long considered inadequate to explain travel behaviour. Consequently, probabilistic route choice models were developed in which drivers were assumed to minimize their perceived costs given a set of routes. The objective of the paper is to review the different route choice models used to solve the traffic assignment problem. Focus is on the different model structures. The paper connects some of the route choice models proposed long ago, such as the logit and probit models, with recently developed models. It discusses several extensions to the simple logit model, as well as the choice set generation problem and the incorporation of the models in the assignment problem.     

A day-to-day route flow evolution process towards the mixed equilibria

This study investigates a travelers’ day-to-day route flow evolution process under a predefined market penetration of advanced traveler information system (ATIS). It is assumed that some travelers equipped with ATIS will follow the deterministic user equilibrium route choice behavior due to the complete traffic information provided by ATIS, while the other travelers unequipped with ATIS will follow the stochastic user equilibrium route choice behavior. The interaction between these two groups of travelers will result in a mixed equilibrium state. We first propose a discrete day-to-day route flow adjustment process for this mixed equilibrium behavior by specifying the travelers’ route adjustment principle and adjustment ratio. The convergence of the proposed day-to-day flow dynamic model to the mixed equilibrium state is then rigorously demonstrated under certain assumptions upon route adjustment principle and adjustment ratio. In addition, without affecting the convergence of the proposed day-to-day flow dynamic model, the assumption concerning the adjustment ratio is further relaxed, thus making the proposed model more appealing in practice. Finally, numerical experiments are conducted to illustrate and evaluate the performance of the proposed day-to-day flow dynamic model.     

On the flexibility of using marginal distribution choice models in traffic equilibrium

Traffic equilibrium models are fundamental to the analysis of transportation systems. The stochastic user equilibrium (SUE) model which relaxes the perfect information assumption of the deterministic user equilibrium is one such model. The aim of this paper is to develop a new user equilibrium model, namely the MDM-SUE model, that uses the marginal distribution model (MDM) as the underlying route choice model. In this choice model, the marginal distributions of the path utilities are specified but the joint distribution is not. By focusing on the joint distribution that maximizes expected utility, we show that MDM-SUE exists and is unique under mild assumptions on the marginal distributions. We develop a convex optimization formulation for the MDM-SUE. For specific choices of marginal distributions, the MDM-SUE model recreates the optimization formulation of logit SUE and weibit SUE. Moreover, the model is flexible since it can capture perception variance scaling at the route level and allows for modeling different user preferences by allowing for skewed distributions and heavy tailed distributions. The model can also be generalized to incorporate bounded support distributions and discrete distributions which allows to distinguish between used and unused routes within the SUE framework. We adapt the method of successive averages to develop an efficient approach to compute MDM-SUE traffic flows. In our numerical experiments, we test the ability of MDM-SUE to relax the assumption that the error terms are independently and identically distributed random variables as in the logit models and study the additional modeling flexibility that MDM-SUE provides on small-sized networks as well as on the large network of the city of Winnipeg. The results indicate that the model provides both modeling flexibility and computational tractability in traffic equilibrium.     

A marginal utility day-to-day traffic evolution model based on one-step strategic thinking

Most deterministic day-to-day traffic evolution models, either in continuous-time or discrete-time space, have been formulated based on a fundamental assumption on driver route choice rationality where a driver seeks to maximize her/his marginal benefit defined as the difference between the perceived route costs. The notion of rationality entails the exploration of the marginal decision rule from economic theory, which states that a rational individual evaluates his/her marginal utility, defined as the difference between the marginal benefit and the marginal cost, of each incremental decision. Seeking to analyze the marginal decision rule in the modeling of deterministic day-to-day traffic evolution, this paper proposes a modeling framework which introduces a term to capture the marginal cost to the driver induced by route switching. The proposed framework enables to capture both benefit and cost associated with route changes. The marginal cost is then formulated upon the assumption that drivers are able to predict other drivers’ responses to the current traffic conditions, which is adopted based on the notion of strategic thinking of rational players developed in behavior game theory. The marginal cost based on 1-step strategic thinking also describes the “shadow price” of shifting routes, which helps to explain the behavioral tendency of the driver perceiving the cost-sensitivity to link/route flows. After developing a formulation of the marginal utility day-to-day model, its theoretical properties are analyzed, including the invariance property, asymptotic stability, and relationship with the rational behavioral adjustment process.     

A route-swapping dynamical system and Lyapunov function for stochastic user equilibrium

An analysis of the continuous-time dynamics of a route-swap adjustment process is presented, which is a natural adaptation of that presented in Smith (1984) for deterministic choice problems, for a case in which drivers are assumed to make perceptual errors in their evaluations of travel cost according to a Random Utility Model. We show that stationary points of this system are stochastic user equilibria. A Lyapnuov function is developed for this system under the assumption of monotone, continuously differentiable and bounded cost-flow functions and a logit-based decision rule, establishing convergence and stability of trajectories of such a dynamical system with respect to a stochastic user equilibrium solution.     

Investigating the irregularity of bus routes: highlighting how underlying assumptions of bus models impact the regularity results

A bus route is inherently unstable: when the system is uncontrolled, buses fail to maintain their time‐headways and tend to bunch. Several mathematical bus motion models were proposed to reproduce the bus behavior and assess management strategies. However, no work has established how the choice of a model impacts the irregularity of modeled bus systems, that is, the non‐respect of scheduled headways. Because of this gap, a large body of existing works assumes that the ability of these models to reproduce instability comes only from stochasticity, although the link between stochastic inputs and the level of irregularity remains unknown. Moreover, some recognized phenomena such as a change of travel conditions during a day or delays at signalized intersections are ignored. To address these shortcomings, this paper provides an overview of existing dynamic bus‐focused models and proposes a simple way to classify them. Commonly used deterministic and stochastic models are compared, which allows quantifying the relative influence of stochasticity of each model component on outputs. Moreover, we show that a change in the system equilibrium in a full deterministic system can lead to irregularity. Finally, this paper proposes a refinement of travel time models to account for non‐dynamic signals. In presence of traffic signals, we show that a bus system can be self‐regulated. Especially, these insights could help to calibrate bus model inputs to better reproduce real data. Copyright © 2014 John Wiley & Sons, Ltd.     

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.     

Solving a Dynamic User Equilibrium model based on splitting rates with Gradient Projection algorithms

This article shows how Gradient Projection (GP) algorithms are capable of solving with high precision a Dynamic User Equilibrium (UE) model based on Splitting Rates, i.e. turning movements fractions by destination.Dynamic Traffic Assignment (DTA) is formulated as a Variational Inequality problem defined on temporal profiles of arc conditional probabilities that express a sequence of deterministic route choices taken at nodes by road users directed toward each destination.Congestion is represented through a macroscopic traffic model capable to reproduce a range of phenomena having increasing complexity, from links with bottleneck to intersections with spillback. Different time discretizations, from few seconds to few minutes, are also possible, which allows a range of applications from planning to operation.This assignment model, which is fully link based, is proved to be equivalent to a path based formulation. It also allows for the computation of a handy gap function for analyzing convergence to equilibrium.Numerical experiments on test networks are presented, showing that the proposed GP algorithms converge to dynamic equilibrium in a reasonable number of iterations, outperforming the Method of Successive Averages (MSA).     

A reference-dependent user equilibrium model for activity-travel scheduling

Existing user equilibrium models of activity-travel scheduling generally fall short in representing travelers’ decision-making processes. The majority have either implicitly or explicitly assumed that travelers follow the principle of utility maximization. This assumption ignores the fact that individuals may be loss–averse when making activity-travel decisions. Allowing for the situation that travelers possess accurate information of the urban-transportation system due to modern technologies, studies on reference-dependent decision-making under near-perfect information are receiving increasing attention. In view of traveler heterogeneity, individuals can be divided into multiple classes according to their reference points. In this paper, we propose a reference-dependent multi-class user equilibrium model for activity-travel scheduling, which can be reformulated as a variational inequality problem. Moreover, comparative analyses are conducted on the equilibrium states between utility-maximization (no reference) and reference-dependency of exogenous and endogenous references. A numerical example regarding combined departure-time and mode choice for commuting is conducted to illustrate the proposed model. The simulated results indicate that reference points and loss aversion attitudes have significant effects on the choice of departure time and mode.     

Route swapping in dynamic traffic networks

A dynamic traffic assignment (DTA) model typically consists of a traffic performance model and a route choice model. The traffic performance model describes how traffic propagates (over time) along routes connecting origin-destination (OD) pairs, examples being the cell transmission model, the vertical queueing model and the travel time model. This is implemented in a dynamic network loading (DNL) algorithm, which uses the given route inflows to compute the link inflows (and hence link costs), which are then used to compute the route travel times (and hence route costs). A route swap process specifies the route inflows for tomorrow (at the next iteration) based on the route inflows today (at the current iteration). A dynamic user equilibrium (DUE), where each traveller on the network cannot reduce his or her cost of travel by switching to another route, can be sought by iterating between the DNL algorithm and the route swap process. The route swap process itself takes up very little computational time (although route set generation can be very computationally intensive for large networks). However, the choice of route swap process dramatically affects convergence and the speed of convergence. The paper details several route swap processes and considers whether they lead to a convergent system, assuming that the route cost vector is a monotone function of the route inflow vector.     

First-best marginal cost toll for a traffic network with stochastic demand

First-best marginal cost pricing (MCP) in traffic networks has been extensively studied with the assumption of deterministic travel demand. However, this assumption may not be realistic as a transportation network is exposed to various uncertainties. This paper investigates MCP in a traffic network under stochastic travel demand. Cases of both fixed and elastic demand are considered. In the fixed demand case, travel demand is represented as a random variable, whereas in the elastic demand case, a pre-specified random variable is introduced into the demand function. The paper also considers a set of assumptions of traveler behavior. In the first case, it is assumed that the traveler considers only the mean travel time in the route choice decision (risk-neutral behavior), and in the second, both the mean and the variance of travel time are introduced into the route choice model (risk-averse behavior). A closed-form formulation of the true marginal cost toll for the stochastic network (SN-MCP) is derived from the variational inequality conditions of the system optimum and user equilibrium assignments. The key finding is that the calculation of the SN-MCP model cannot be made by simply substituting related terms in the original MCP model by their expected values. The paper provides a general function of SN-MCP and derives the closed-form SN-MCP formulation for specific cases with lognormal and normal stochastic travel demand. Four numerical examples are explored to compare network performance under the SN-MCP and other toll regimes.     

On the variance of recurrent traffic flow for statistical traffic assignment

This paper generalizes and extends classical traffic assignment models to characterize the statistical features of Origin-Destination (O-D) demands, link/path flow and link/path costs, all of which vary from day to day. The generalized statistical traffic assignment (GESTA) model has a clear multi-level variance structure. Flow variance is analytically decomposed into three sources, O-D demands, route choices and measurement errors. Consequently, optimal decisions on roadway design, maintenance, operations and planning can be made using estimated probability distributions of link/path flow and system performance. The statistical equilibrium in GESTA is mathematically defined. Its multi-level statistical structure well fits large-scale data mining techniques. The embedded route choice model is consistent with the settings of O-D demands considering link costs that vary from day to day. We propose a Method of Successive Averages (MSA) based solution algorithm to solve for GESTA. Its convergence and computational complexity are analyzed. Three example networks including a large-scale network are solved to provide insights for decision making and to demonstrate computational efficiency.     

Day-to-day traffic dynamics considering social interaction: From individual route choice behavior to a network flow model

Social interaction is increasingly recognized as an important factor that influences travelers’ behaviors. It remains challenging to incorporate its effect into travel choice behaviors, although there has been some research into this area. Considering random interaction among travelers, we model travelers’ day-to-day route choice under the uncertain traffic condition. We further explore the evolution of network flow based on the individual-level route choice model, though that travelers are heterogeneous in decision-making under the random-interaction scheme. We analyze and prove the existence of equilibrium and the stability of equilibrium. We also analyzed and described the specific properties of the network flow evolution and travelers’ behaviors. Two interesting phenomena are found in this study. First, the number of travelers that an individual interacts with can affect his route choice strategy. However, the interaction count exerts no influence on the evolution of network flow at the aggregate-level. Second, when the network flow reaches equilibrium, the route choice strategy at the individual-level is not necessarily invariable. Finally, two networks are used as numerical examples to show model properties and to demonstrate the two study phenomena. This study improves the understanding of travelers’ route choice dynamics and informs how the network flow evolves under the influence of social interaction.     

Interactions between driver information,route choice,and optimal signal timing on a simple network

The interaction between driver information, route choice, and optimal traffic signal settings was investigated using a simple two-route system with a single “T” intersection and a fixed O-D demand. The logit model and the method of successive averages (MSA) were used to calculate the route choice probabilities and the stochastic equilibrium assignment. Given an assignment, signal settings which minimized average intersection delay were calculated; flow reassignment and new optimal signal settings were then obtained and this iterative process continued until convergence. The calculations were performed either directly in a combined assignment/signal optimization model or in stages using the output flows of an assignment model as inputs to TRANSYT-7F and iterating between the two models. Results show that a unique joint signal timing/assignment equilibrium is reached in all cases provided that a certain precision in drivers' perceptions is not reached. If driver information increases to this precision (bifurcation point) and beyond, results show clearly that the unique joint signal timing/assignment equilibrium no longer exists. In fact, three joint equilibria points exist after the bifurcation point. Two of these points are stable and one is not. It was found that the system yields the lowest total intersection delay when the joint equilibrium is such that all traffic and hence the major part of green time is assigned to only one of the two routes. Although this may not be feasible to implement in practice, the results indicate clearly for this simple example that there is a trade-off between a system with minimum total delay but no unique joint signal-settings/assignment equilibrium (achieved when drivers have nearly perfect information about the system) and a system with a unique joint equilibrium but with higher total delay (achieved when drivers have reasonably good but somewhat limited information). In most cases the second system seems appropriate for a number of practical reasons.     

A comparison of stochastic and deterministic traffic assignment over congested networks

The similarity between link flows obtained from deterministic and stochastic equilibrium traffic assignment models is investigated at different levels of congestion. A probit-based stochastic assignment is used (over a congested network) where the conditions for equilibrium are those given by Daganzo and Sheffi (1977). Stochastic equilibrium flows are generated using an iterative procedure with predetermined step sizes, and the resulting assignment is validated on the basis of the equilibrium criteria. The procedure is intended to assist in the choice of the most appropriate assignment algorithm for a given level of congestion.     

Estimation of origin-destination matrices from link traffic counts on congested networks

Conventional methods for estimating origin-destination (O-D) trip matrices from link traffic counts assume that route choice proportions are given constants. In a network with realistic congestion levels, this assumption does not hold. This paper shows how existing methods such as the generalized least squares technique can be integrated with an equilibrium traffic assignment in the form of a convex bilevel optimization problem. The presence of measurement errors and time variations in the observed link flows are explicitly considered. The feasibility of the model is always guaranteed without a requirement for estimating consistent link flows from counts. A solution algorithm is provided and numerical simulation experiments are implemented in investigating the model's properties. Some related problems concerning O-D matrix estimation are also discussed.     

Examining the scaling effect and overlapping problem in logit-based stochastic user equilibrium models

The purpose of this paper is to examine the scaling effect and overlapping problem in a route choice context using the logit-based stochastic user equilibrium (SUE) principle to explicitly account for the congestion effect. Numerical experiments are performed on nine models: the deterministic user equilibrium model, the multinomial logit SUE model with and without scaling, the C-logit SUE model with and without scaling, the path-size logit SUE model with and without scaling, and the paired combinatorial logit SUE model with and without scaling. Sensitivity analysis is conducted to examine the effects of route sets, congestion levels, dispersion intensities, and network asymmetries. A real transportation network in the City of Winnipeg, Canada is also used to compare the network equilibrium flow allocations of different SUE models. The results of the sensitivity analysis and the Winnipeg network reveal that both scaling effect and overlapping problem can have a significant impact on the network equilibrium flow allocations.     

Tollroads are only part of the overall trip: the error of our ways in past willingness to pay studies

With rare exception, actual tollroad traffic in many countries has failed to reproduce forecast traffic levels, regardless of whether the assessment is made after an initial year of operation or as long as 10 years after opening. Pundits have offered many reasons for this divergence, including optimism bias, strategic misrepresentation, the promise to equity investors of early returns on investment, errors in land use forecasts, and specific assumptions underlying the traffic assignment models used to develop traffic forecasts. One such assumption is the selection of a behaviourally meaningful value of travel time savings (VTTS) for use in a generalised cost or generalised time user benefit expression that is the main behavioural feature of the traffic assignment (route choice) model. Numerous empirical studies using stated choice experiments have designed choice sets of alternatives as if users choose a tolled route or a free route under the (implied) assumption that the tolled route is tolled for the entire trip. Reality is often very different, with a high incidence of use of a non-tolled road leading into and connecting out of a tolled link. In this paper we recognise this feature of route choice and redesign the stated choice experiment to account for it. Furthermore, this study is a follow up to a previous study undertaken before a new toll road was in place, and it benefits from real exposure to the new toll road. We find that the VTTS is noticeably reduced, and if the VTTS is a significant contributing influence on errors on traffic forecasts, then the lower estimates make sense behaviourally.     

Consistent formulation of network equilibrium with stochastic flows

Traffic flows in real-life transportation systems vary on a daily basis. According to traffic flow theory, such variability should induce a similar variability in travel times, but this “internal consistency” is generally not captured by existing network equilibrium models. We present an internally-consistent network equilibrium approach, which considers two potential sources of flow variability: (i) daily variation in route choice and (ii) daily variation in origin–destination demand. We particularly aspire to a flexible formulation that permits alternative statistical assumptions, which allows the best fit to be made to observed variability data in particular applications. Joint probability distributions of route—and therefore link—flows are derived under several assumptions concerning stochastic driver behavior. A stochastic network equilibrium model with stochastic demands and route choices is formulated as a fixed point problem. We explore limiting cases which allow an equivalent convex optimization problem to be defined, and finally apply this method to a real-life network of Kanazawa City, Japan.