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 computational model for the probit‐based dynamic stochastic user optimal traffic assignment problem

This paper focuses on computational model development for the probit‐based dynamic stochastic user optimal (P‐DSUO) traffic assignment problem. We first examine a general fixed‐point formulation for the P‐DSUO traffic assignment problem, and subsequently propose a computational model that can find an approximated solution of the interest problem. The computational model includes four components: a strategy to determine a set of the prevailing routes between each origin–destination pair, a method to estimate the covariance of perceived travel time for any two prevailing routes, a cell transmission model‐based traffic performance model to calculate the actual route travel time used by the probit‐based dynamic stochastic network loading procedure, and an iterative solution algorithm solving the customized fixed‐point model. The Ishikawa algorithm is proposed to solve the computational model. A comparison study is carried out to investigate the efficiency and accuracy of the proposed algorithm with the method of successive averages. Two numerical examples are used to assess the computational model and the algorithm proposed. Results show that Ishikawa algorithm has better accuracy for smaller network despite requiring longer computational time. Nevertheless, it could not converge for larger network. Copyright © 2010 John Wiley & Sons, Ltd.     

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 chance-constrained based stochastic dynamic traffic assignment model: Analysis, formulation and solution algorithms

This paper is concerned with the system optimum-dynamic traffic assignment (SO-DTA) problem when the time-dependent demands are random variables with known probability distributions. The model is a stochastic extension of a deterministic linear programming formulation for SO-DTA introduced by Ziliaskopoulos (Ziliaskopoulos, A.K., 2000. A linear programming model for the single destination system optimum dynamic traffic assignment problem, Transportation Science, 34, 1–12). The proposed formulation is chance-constrained based and we demonstrate that it provides a robust SO solution with a user specified level of reliability. The model provides numerous insights and can be a useful tool in producing robust control and management strategies that account for uncertainty in applications where SO-DTA is relevant (e.g. evacuation modeling, computing alternate routes around freeway incidents and establishing lower bounds on network performance).     

Quasi-dynamic traffic assignment with residual point queues incorporating a first order node model

Static traffic assignment models are still widely applied for strategic transport planning purposes in spite of the fact that such models produce implausible traffic flows that exceed link capacities and predict incorrect congestion locations. There have been numerous attempts to constrain link flows to capacity. Capacity constrained models with residual queues are often referred to as quasi-dynamic traffic assignment models. After reviewing the literature, we come to the conclusion that an important piece of the puzzle has been missing so far, namely the inclusion of a first order node model. In this paper we propose a novel path-based static traffic assignment model for finding a stochastic user equilibrium in general transportation networks. This model includes a first order (steady-state) node model that yields more realistic turn capacities, which are then used to determine consistent capacity constrained traffic flows, residual point (vertical) queues (upstream bottleneck links), and path travel times consistent with queuing theory. The route choice part of the model is specified as a variational inequality problem, while the network loading part is formulated as a fixed point problem. Both problems are solved using existing techniques to find a solution. We illustrate the model using hypothetical examples, and also demonstrate feasibility on large-scale networks.     

Preliminary analysis on dynamic route choice behavior: Using probe‐vehicle data

Dynamic traffic assignment models have been attracting increasing attention with the progress of traffic management policies based on information technology. These dynamic estimation tools, however, just apply static route choice models either at only origin node or at every arrival node. This paper aims at providing some knowledge on drivers' dynamic route choice behavior using probe‐vehicle data. The results of analyses show that route choice behavior relates to the distance from driver's position to the destination and that dynamic route choice behavior is modeled better by considering decision process during the trip.     

Dynamic activity-travel assignment in multi-state supernetworks

The integration of activity-based modeling and dynamic traffic assignment for travel demand analysis has recently attracted ever-increasing attention. However, related studies have limitations either on the integration structure or the number of choice facets being captured. This paper proposes a formulation of dynamic activity-travel assignment (DATA) in the framework of multi-state supernetworks, in which any path through a personalized supernetwork represents a particular activity-travel pattern (ATP) at a high level of spatial and temporal detail. DATA is formulated as a discrete-time dynamic user equilibrium (DUE) problem, which is reformulated as an equivalent variational inequality (VI) problem. A generalized dynamic link disutility function is established with the accommodation of different characteristics of the links in the supernetworks. Flow constraints and non-uniqueness of equilibria are also investigated. In the proposed formulation, the choices of departure time, route, mode, activity sequence, activity and parking location are all unified into one time-dependent ATP choice. As a result, the interdependences among all these choice facets can be readily captured. A solution algorithm based on the route-swapping mechanism is adopted to find the user equilibrium. A numerical example with simulated scenarios is provided to demonstrate the advantages of the proposed approach.     

Direct formulation and algorithms for the probit-based stochastic user equilibrium traffic assignment problem

This paper proposes simple and direct formulation and algorithms for the probit-based stochastic user equilibrium traffic assignment problem. It is only necessary to account for random variables independent of link flows by performing a simple transformation of the perceived link travel time with a normal distribution. At every iteration of a Monte-Carlo simulation procedure, the values of the random variables are sampled based on their probability distributions, and then a regular deterministic user equilibrium assignment is carried out to produce link flows. The link flows produced at each iteration of the Monte-Carlo simulation are averaged to yield the final flow pattern. Two test networks demonstrate that the proposed algorithms and the traditional algorithm (the Method of Successive Averages) produce similar results and that the proposed algorithms can be extended to the computation of the case in which the random error term depends on measured travel time.     

Multimodal,multiclass stochastic dynamic traffic assignment for evaluating information provision strategies

A multimodal, multiclass stochastic dynamic traffic assignment model was developed to evaluate pre‐trip and enroute travel information provision strategies. Three different information strategies were examined: user optimum [UO], system optimum [SO] and mixed optimum [MO]. These information provision strategies were analyzed based on the levels of traffic congestion and market penetration rate for the information equipment. Only two modes, bus and car, were used for evaluating and calculating the modal split ratio. Several scenarios were analyzed using day‐to‐day and within day dynamic models. From the results analyzed, it was found that when a traffic manager provides information for drivers using the UO strategy and drivers follow the provided information absolutely, the total travel time may increases over the case with no information. Such worsening occurs when drivers switch their routes and face traffic congestion on the alternative route. This phenomenon is the 'Braess Paradox'.     

The existence, uniqueness and computation of an arc-based dynamic network user equilibrium formulation

In this paper, a dynamic user equilibrium traffic assignment model with simultaneous departure time/route choices and elastic demands is formulated as an arc-based nonlinear complementarity problem on congested traffic networks. The four objectives of this paper are (1) to develop an arc-based formulation which obviates the use of path-specific variables, (2) to establish existence of a dynamic user equilibrium solution to the model using Brouwer's fixed-point theorem, (3) to show that the vectors of total arc inflows and associated minimum unit travel costs are unique by imposing strict monotonicity conditions on the arc travel cost and demand functions along with a smoothness condition on the equilibria, and (4) to develop a heuristic algorithm that requires neither a path enumeration nor a storage of path-specific flow and cost information. Computational results are presented for a simple test network with 4 arcs, 3 nodes, and 2 origin–destination pairs over the time interval of 120 periods.     

Comparative analysis of transit assignment: evidence from urban railway system in the Tokyo Metropolitan Area

This paper empirically compares the performance of six traffic assignment methods using the same empirical dataset of route choice. Multinomial logit (MNL), structured multinomial probit (SMNP), user equilibrium (UE), logit-based stochastic user equilibrium (SUE), probit-based SUE, and all-or-nothing (AON) assignment methods are applied to the comparative analysis. The investigated methods include those with three types of error components in their cost functions and two types of flow dependencies. Four methods of generating the route choice set are also compared for use as stochastic traffic assignment methods. The revealed preference data of urban rail route choice in the Tokyo Metropolitan Area are used for the case analysis. The empirical case analysis shows that probit-based SUE provides the best accuracy but requires the longest computation time. It also shows that the heuristics used to generate the choice set influence the method’s accuracy, while the incorporation of route commonality and in-vehicle congestion significantly improves its accuracy. Finally, the implications for practical rail planning are discussed on the basis of the analysis results.     

Transit Users’ Route‐Choice Modelling in Transit Assignment: A Review

Abstract

This paper reviews the main studies on transit users’ route choice in the context of transit assignment. The studies are categorized into three groups: static transit assignment, within‐day dynamic transit assignment, and emerging approaches. The motivations and behavioural assumptions of these approaches are re‐examined. The first group includes shortest‐path heuristics in all‐or‐nothing assignment, random utility maximization route‐choice models in stochastic assignment, and user equilibrium based assignment. The second group covers within‐day dynamics in transit users’ route choice, transit network formulations, and dynamic transit assignment. The third group introduces the emerging studies on behavioural complexities, day‐to‐day dynamics, and real‐time dynamics in transit users’ route choice. Future research directions are also discussed.     

General stochastic user equilibrium traffic assignment problem with link capacity constraints

This paper addresses a general stochastic user equilibrium (SUE) traffic assignment problem with link capacity constraints. It first proposes a novel linearly constrained minimization model in terms of path flows and then shows that any of its local minimums satisfies the generalized SUE conditions. As the objective function of the proposed model involves path‐specific delay functions without explicit mathematical expressions, its Lagrangian dual formulation is analyzed. On the basis of the Lagrangian dual model, a convergent Lagrangian dual method with a predetermined step size sequence is developed. This solution method merely invokes a subroutine at each iteration to perform a conventional SUE traffic assignment excluding link capacity constraints. Finally, two numerical examples are used to illustrate the proposed model and solution method.     

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.     

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.     

An integrated, dynamic approach to travel demand forecasting

This paper presents a unified approach for improving travel demand models through the application and extension of supernetwork models of multi-dimensional travel choices. Proposed quite some time ago, supernetwork models solved to stochastic user equilibrium can provide a simultaneous solution to trip generation, distribution, mode choice, and assignment that is consistent with disaggregate models and predicts their aggregate effects. The extension to incorporate the time dimension through the use of dynamic equilibrium assignment methods is proposed as an enhancement that is necessary in order to produce realistic models. A variety of theoretical and practical problems are identified whose solution underlies implementation of this approach. Recommended future research includes improved algorithms for stochastic and dynamic equilibrium assignment, new methods for calibrating assignment models, and the use of Geographic Information Systems (GIS) technology for data and model management.     

Multi-scenario optimization approach for assessing the impacts of advanced traffic information under realistic stochastic capacity distributions

In this study, to incorporate realistic discrete stochastic capacity distribution over a large number of sampling days or scenarios (say 30–100 days), we propose a multi-scenario based optimization model with different types of traveler knowledge in an advanced traveler information provision environment. The proposed method categorizes commuters into two classes: (1) those with access to perfect traffic information every day, and (2) those with knowledge of the expected traffic conditions (and related reliability measure) across a large number of different sampling days. Using a gap function framework or describing the mixed user equilibrium under different information availability over a long-term steady state, a nonlinear programming model is formulated to describe the route choice behavior of the perfect information (PI) and expected travel time (ETT) user classes under stochastic day-dependent travel time. Driven by a computationally efficient algorithm suitable for large-scale networks, the model was implemented in a standard optimization solver and an open-source simulation package and further applied to medium-scale networks to examine the effectiveness of dynamic traveler information under realistic stochastic capacity conditions.     

A dynamic stochastic assignment model for the analysis of general networks

The paper adopts the framework employed by the existing dynamic assignment models, which analyse specific network forms, and develops a methodology for analysing general networks. Traffic conditions within a link are assumed to be homogeneous, and the time varying O-D travel times and traffic flow patterns are calculated using elementary relationships from traffic flow theory and link volume conservation equations. Each individual is assumed to select a departure time and a route by trading off the travel time and schedule delay associated with each alternative. A route is considered as reasonable if it includes only links which do not take the traveller back to the origin. The set of reasonable routes is not consistant but depends on the time that an individual decides to depart from his origin. Equilibrium distributions are derived from a Markovian model which describes the evolution of travel patterns from day to day. Numerical simulation experiments are conducted to analyse the impact of different work start time flexibilities on the time dependent travel patterns. The similarity between link flows and travel times obtained from static and dynamic stochastic assignment is investigated. It is shown that in congested networks the application of static assignment results in travel times which are lower than the ones predicted by dynamic assignment.     

Network user equilibrium of battery electric vehicles considering flow-dependent electricity consumption

This paper addresses the equilibrium traffic assignment problem involving battery electric vehicles (BEVs) with flow-dependent electricity consumption. Due to the limited driving range and the costly/time-consuming recharging process required by current BEVs, as well as the scarce availability of battery charging/swapping stations, BEV drivers usually experience fear that their batteries may run out of power en route. Therefore, when choosing routes, BEV drivers not only try to minimize their travel costs, but also have to consider the feasibility of their routes. Moreover, considering the potential impact of traffic congestion on the electricity consumption of BEVs, the feasibility of routes may be determined endogenously rather than exogenously. A set of user equilibrium (UE) conditions from the literature is first presented to describe the route choice behaviors of BEV drivers considering flow-dependent electricity consumption. The UE conditions are then formulated as a nonlinear complementarity model. The model is further formulated as a variational inequality (VI) model and is solved using an iterative solution procedure. Numerical examples are provided to demonstrate the proposed models and solution algorithms. Discussions of how to evaluate and improve the system performance with non-unique link flow distribution are offered. A robust congestion pricing model is formulated to obtain a pricing scheme that minimizes the system travel cost under the worst-case tolled flow distribution. Finally, a further extension of the mathematical formulation for the UE conditions is provided.     

Walking infrastructure design assessment by continuous space dynamic assignment modeling

For the planning and design of walking infrastructure, characterized by the fact that the pedestrians can choose their paths freely in two‐dimensional space, applicability of traditional discrete network models is limited. This contribution puts forward an approach for user‐optimal dynamic assignment in continuous time and space for analyzing for instance walking infrastructure in a two‐dimensional space. Contrary to network‐based approaches, the theory allows the traffic units to choose from an infinite non‐countable set of paths through the considered space. The approach first determines the continuous paths using a path choice model. Then, origin‐destination flows are assigned and traffic conditions are calculated. The approach to determine a user‐optimal assignment is heuristic and consists of a sequence of all‐or‐nothing assignments. An application example is presented, showing dynamic user equilibrium traffic flows through a realistic transfer station. The example is aimed at illustrating the dynamic aspects of the modeling approach, such as anticipation on expected flow conditions, and predicted behavior upon catching or missing a connection.