Stochastic user equilibrium with equilibrated choice sets: Part I – Model formulations under alternative distributions and restrictions

The aim of this paper is to remove the known limitations of Deterministic and Stochastic User Equilibrium (DUE and SUE), namely that only routes with the minimum cost are used in DUE, and that all permitted routes are used in SUE regardless of their costs. We achieve this by combining the advantages of the two principles, namely the definition of unused routes in DUE and of mis-perception in SUE, such that the resulting choice sets of used routes are equilibrated. Two model families are formulated to address this issue: the first is a general version of SUE permitting bounded and discrete error distributions; the second is a Restricted SUE model with an additional constraint that must be satisfied for unused paths. The overall advantage of these model families consists in their ability to combine the unused routes with the use of random utility models for used routes, without the need to pre-specify the choice set. We present model specifications within these families, show illustrative examples, evaluate their relative merits, and identify key directions for further research.     

Multi-class percentile user equilibrium with flow-dependent stochasticity

Travelers often reserve a buffer time for trips sensitive to arrival time in order to hedge against the uncertainties in a transportation system. To model the effects of such behavior, travelers are assumed to choose routes to minimize the percentile travel time, i.e. the travel time budget that ensures their preferred probability of on-time arrival; in doing so, they drive the system to a percentile user equilibrium (UE), which can be viewed as an extension of the classic Wardrop equilibrium. The stochasticity in the supply of transportation are incorporated by modeling the service flow rate of each road segment as a random variable. Such stochasticity is flow-dependent in the sense that the probability density functions of these random variables, from which the distribution of link travel time are constructed, are specified endogenously with flow-dependent parameters. The percentile route travel time, obtained by directly convolving the link travel time distributions in this paper, is not available in closed form in general and has to be numerically evaluated. To reveal their structural properties, percentile UE solutions are examined in special cases and verified with numerical results. For the general multi-class percentile UE traffic assignment problem, a variational inequality formulation is given and solved using a route-based algorithm. The algorithm makes use of the diagonal elements in the Jacobian of percentile route travel time, which is approximated through recursive convolution. Preliminary numerical experiments indicate that the algorithm is able to achieve highly precise equilibrium solutions.     

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 discrete dynamical system of formulating traffic assignment: Revisiting Smith’s model

Through relaxing the behavior assumption adopted in Smith’s model (Smith, 1984), we propose a discrete dynamical system to formulate the day-to-day evolution process of traffic flows from a non-equilibrium state to an equilibrium state. Depending on certain preconditions, the equilibrium state can be equivalent to a Wardrop user equilibrium (UE), Logit-based stochastic user equilibrium (SUE), or boundedly rational user equilibrium (BRUE). These equivalence properties indicate that, to make day-to-day flows evolve to equilibrium flows, it is not necessary for travelers to choose their routes based on actual travel costs of the previous day. Day-to-day flows can still evolve to equilibrium flows provided that travelers choose their routes based on estimated travel costs which satisfy these preconditions. We also show that, under a more general assumption than the monotonicity of route cost function, the trajectory of the dynamical system converges to a set of equilibrium flows by reasonably setting these parameters in the dynamical system. Finally, numerical examples are presented to demonstrate the application and properties of the dynamical system. The study is helpful for understanding various processes of forming traffic jam and designing an algorithm for calculating equilibrium flows.     

Dynamic user equilibrium with side constraints for a traffic network: Theoretical development and numerical solution algorithm

This paper investigates a traffic volume control scheme for a dynamic traffic network model which aims to ensure that traffic volumes on specified links do not exceed preferred levels. The problem is formulated as a dynamic user equilibrium problem with side constraints (DUE-SC) in which the side constraints represent the restrictions on the traffic volumes. Travelers choose their departure times and routes to minimize their generalized travel costs, which include early/late arrival penalties. An infinite-dimensional variational inequality (VI) is formulated to model the DUE-SC. Based on this VI formulation, we establish an existence result for the DUE-SC by showing that the VI admits at least one solution. To analyze the necessary condition for the DUE-SC, we restate the VI as an equivalent optimal control problem. The Lagrange multipliers associated with the side constraints as derived from the optimality condition of the DUE-SC provide the traffic volume control scheme. The control scheme can be interpreted as additional travel delays (either tolls or access delays) imposed upon drivers for using the controlled links. This additional delay term derived from the Lagrange multiplier is compared with its counterpart in a static user equilibrium assignment model. If the side constraint is chosen as the storage capacity of a link, the additional delay can be viewed as the effort needed to prevent the link from spillback. Under this circumstance, it is found that the flow is incompressible when the link traffic volume is equal to its storage capacity. An algorithm based on Euler’s discretization scheme and nonlinear programming is proposed to solve the DUE-SC. Numerical examples are presented to illustrate the mechanism of the proposed traffic volume control scheme.     

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 link-node complementarity model and solution algorithm for dynamic user equilibria with exact flow propagations

In this paper, we propose a link-node complementarity model for the basic deterministic dynamic user equilibrium (DUE) problem with single-user-class and fixed demands. The model complements link-path formulations that have been widely studied for dynamic user equilibria. Under various dynamic network constraints, especially the exact flow propagation constraints, we show that the continuous-time dynamic user equilibrium problem can be formulated as an infinite dimensional mixed complementarity model. The continuous-time model can be further discretized as a finite dimensional non-linear complementarity problem (NCP). The proposed discrete-time model captures the exact flow propagation constraints that were usually approximated in previous studies. By associating link inflow at the beginning of a time interval to travel times at the end of the interval, the resulting discrete-time model is predictive rather than reactive. The solution existence and compactness condition for the proposed model is established under mild assumptions. The model is solved by an iterative algorithm with a relaxed NCP solved at each iteration. Numerical examples are provided to illustrate the proposed model and solution approach. We particularly show why predictive DUE is preferable to reactive DUE from an algorithmic perspective.     

A route-based solution algorithm for dynamic user equilibrium assignments

The aim of this study is to establish a method to calculate good quality user equilibrium assignments under time varying conditions. For this purpose, it introduces a dynamic network loading method that can maintain correct flow propagation as well as flow conservation, and it shows a novel route-based solution algorithm. This novel algorithm turns out to be convenient and logically plausible compared to the conventional [Frank, M., Wolfe, P., 1956. An algorithm for quadratic programming. Naval Research Logistics Quarterly 3, 95–110] algorithm, because the former does not require evaluation of an objective function and it finds solutions maintaining correct flow propagation in the time-varying network conditions. The application of novel dynamic network loading method and solution algorithm to test networks shows that we can find high quality dynamic user equilibrium assignment. This is illustrated in an example network using the deterministic queuing model for a link performance function and associating costs and flows in a predictive way in discrete time.     

Airport system planning—a U.K. study

There is growing public pressure, from environmentalist groups and others, for the imposition of lorry bans in urban areas. In the U.K. such bans have so far only been imposed as through‐route bans by small towns, such as Windsor, where the overall impact on operators and on road freight costs is limited. The Greater London Council's response to the pressure for lorry bans has been to set up a Committee of Inquiry to examine the impact of an access ban on the heaviest lorries in the London area. The proposed ban would apply to an area enclosed by the M25 orbital motorway within which vehicles above a specified gross tonnage would not be allowed to operate. A number of metropolitan authorities elsewhere in the U.K. are thought to be considering similar restrictions on lorries.

In this paper, the impact of area lorry bans on goods vehicle operating costs is discussed. It is suggested that practices based on “direct distribution” techniques may prove less costly than the operating alternatives that have been evaluated in the past which include public transhipment depots and the exclusive use of small vehicles.