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 model and solution algorithm for dynamic deterministic user equilibrium assignment

Abstract

In this paper a route-based dynamic deterministic user equilibrium assignment model is presented. Some features of the linear travel time model are first investigated and then a divided linear travel time model is proposed for the estimation of link travel time: it addresses the limitations of the linear travel time model. For the application of the proposed model to general transportation networks, this paper provides thorough investigations on the computational issues in dynamic traffic assignment with many-to-many OD pairs and presents an efficient solution procedure. The numerical calculations demonstrate that the proposed model and solution algorithm produce satisfactory solutions for a network of substantial size with many-to-many OD pairs. Comparisons of assignment results are also made to show the impacts of incorporation of different link travel time models on the assignment results.     

Computing dynamic user equilibria for large-scale transportation networks

In this paper, we present an approach for determining dynamic user equilibria. The method is suitable for disaggregated microscopic and mesoscopic simulation-based models. It is a modification of the convex-simplex method, which disposes with the line search step, and controls the subset of travelers to be re-routed at each step while updating the link travel times after each assignment. To guarantee finite termination, a suitable stopping criterion is adopted. The proposed method is implemented within TRANSIMS, the Transportation Analysis and Simulation System, as a two-stage process that employs a combined use of link performance functions and a microsimulator in order to design a framework suitable for application to real transportation systems. To demonstrate this capability, we apply the developed methodology to a large-scale network, Bignet, which is part of the transportation city network of Portland, Oregon; and a medium-scale network, Blacksburg, Virginia; and provide some comparative analyses. Our results exhibit that an improved distribution of travelers is obtained while consuming less than 17–33% of the effort required by the current version of TRANSIMS.     

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.     

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.     

Approximate network loading and dual-time-scale dynamic user equilibrium

In this paper we present a dual-time-scale formulation of dynamic user equilibrium (DUE) with demand evolution. Our formulation belongs to the problem class that Pang and Stewart (2008) refer to as differential variational inequalities. It combines the within-day time scale for which route and departure time choices fluctuate in continuous time with the day-to-day time scale for which demand evolves in discrete time steps. Our formulation is consistent with the often told story that drivers adjust their travel demands at the end of every day based on their congestion experience during one or more previous days. We show that analysis of the within-day assignment model is tremendously simplified by expressing dynamic user equilibrium as a differential variational inequality. We also show there is a class of day-to-day demand growth models that allow the dual-time-scale formulation to be decomposed by time-stepping to yield a sequence of continuous time, single-day, dynamic user equilibrium problems. To solve the single-day DUE problems arising during time-stepping, it is necessary to repeatedly solve a dynamic network loading problem. We observe that the network loading phase of DUE computation generally constitutes a differential algebraic equation (DAE) system, and we show that the DAE system for network loading based on the link delay model (LDM) of Friesz et al. (1993) may be approximated by a system of ordinary differential equations (ODEs). That system of ODEs, as we demonstrate, may be efficiently solved using traditional numerical methods for such problems. To compute an actual dynamic user equilibrium, we introduce a continuous time fixed-point algorithm and prove its convergence for effective path delay operators that allow a limited type of nonmonotone path delay. We show that our DUE algorithm is compatible with network loading based on the LDM and the cell transmission model (CTM) due to Daganzo (1995). We provide a numerical example based on the much studied Sioux Falls network.     

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.     

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.     

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.     

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.     

A path-size weibit stochastic user equilibrium model

The aim of this paper is to develop a path-size weibit (PSW) route choice model with an equivalent mathematical programming (MP) formulation under the stochastic user equilibrium (SUE) principle that can account for both route overlapping and route-specific perception variance problems. Specifically, the Weibull distributed random error term handles the identically distributed assumption such that the perception variance with respect to different trip lengths can be distinguished, and a path-size factor term is introduced to resolve the route overlapping issue by adjusting the choice probabilities for routes with strong couplings with other routes. A multiplicative Beckmann’s transformation (MBec) combined with an entropy term are used to develop the MP formulation for the PSW-SUE model. A path-based algorithm based on the partial linearization method is adopted for solving the PSW-SUE model. Numerical examples are also provided to illustrate features of the PSW-SUE model and its differences compared to some existing SUE models as well as its applicability on a real-size network.     

Existence of simultaneous route and departure choice dynamic user equilibrium

This paper is concerned with the existence of the simultaneous route-and-departure choice dynamic user equilibrium (SRDC-DUE) in continuous time, first formulated as an infinite-dimensional variational inequality in Friesz et al. (1993). In deriving our existence result, we employ the generalized Vickrey model (GVM) introduced in Han et al., 2013a, Han et al., 2013b to formulate the underlying network loading problem. As we explain, the GVM corresponds to a path delay operator that is provably strongly continuous on the Hilbert space of interest. Finally, we provide the desired SRDC-DUE existence result for general constraints relating path flows to a table of fixed trip volumes without invocation of a priori bounds on the path flows.     

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 bi-objective user equilibrium model of travel time reliability in a road network

Travel time, travel time reliability and monetary cost have been empirically identified as the most important criteria influencing route choice behaviour. We concentrate on travel time and travel time reliability and review two prominent user equilibrium models incorporating these two factors. We discuss some shortcomings of these models and propose alternative bi-objective user equilibrium models that overcome the shortcomings. Finally, based on the observation that both models use standard deviation of travel time within their measure of travel time reliability, we propose a general travel time reliability bi-objective user equilibrium model. We prove that this model encompasses those discussed previously and hence forms a general framework for the study of reliability related user equilibrium. We demonstrate and validate our concepts on a small three-link example.     

Algorithms for logit-based stochastic user equilibrium assignment

The paper proposes an efficient algorithm for determining the stochastic user equilibrium solution for logit-based loading. The commonly used Method of Successive Averages typically has a very slow convergence rate. The new algorithm described here uses Williams’ result [ Williams, (1977) On the formation of travel demand models and economic evaluation measures of user benefit. Environment and Planning 9A(3), 285–344] which enables the expected value of the perceived travel costs S_rs to be readily calculated for any flow vector x. This enables the value of the Sheffi and Powell, 1982 objective function [Sheffi, Y. and Powell, W. B. (1982) An algorithm for the equilibrium assignment problem with random link times. Networks 12(2), 191–207], and its gradient in any specified search direction, to be calculated. It is then shown how, at each iteration, an optimal step length along the search direction can be easily estimated, rather than using the pre-set step lengths, thus giving much faster convergence. The basic algorithm uses the standard search direction (towards the auxiliary solution). In addition the performance of two further versions of the algorithm are investigated, both of which use an optimal step length but alternative search directions, based on the Davidon–Fletcher–Powell function minimisation method. The first is an unconstrained and the second a constrained version. Comparisons are made of all three versions of the algorithm, using a number of test networks ranging from a simple three-link network to one with almost 3000 links. It is found that for all but the smallest network the version using the standard search direction gives the fastest rate of convergence. Extensions to allow for multiple user classes and elastic demand are also possible.     

A semi-analytical approach for solving the bottleneck model with general user heterogeneity

This paper proposes a novel semi-analytical approach for solving the dynamic user equilibrium (DUE) of a bottleneck model with general heterogeneous users. The proposed approach makes use of the analytical solutions from the bottleneck analysis to create an equivalent assignment problem that admits closed-form commute cost functions. The equivalent problem is a static and asymmetric traffic assignment problem, which can be formulated as a variational inequality problem (VIP). This approach provides a new tool to analyze the properties of the bottleneck model with general heterogeneity, and to design efficient solution methods. In particular, the existence and uniqueness of the DUE solution can be established using the P-property of the Jacobian matrix. Our numerical experiments show that a simple decomposition algorithm is able to quickly solve the equivalent VIP to high precision. The proposed VIP formation is also extended to address simultaneous departure time and route choice in a single O–D origin-destination network with multiple parallel routes.     

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.     

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.     

Modeling user adoption of advanced traveler information systems: dynamic evolution and stationary equilibrium

This paper models the growth rate and the saturation market penetration level for advanced traveler information system (ATIS) products/services with heterogeneous drivers. The price of using and the benefit gained from ATIS services are considered two key factors in explaining the growth of adoption of ATIS products. The information benefit is measured as the travel time saving between equipped and unequipped drivers and evaluated by a mixed stochastic and deterministic network equilibrium model. A modified logistic type growth model is adopted to describe the cumulative adoption of ATIS products over years. The final stationary equilibrium level of ATIS market penetration is so determined that the value of the information provided will decline to the point at which no new users will find it advantageous to purchase that service. The endogenous growth and stationary equilibrium model of market penetration of ATIS services is useful for forecasting the growth process and the impacts on the system performance of ATIS.     

A simulation framework for evaluating airport gate assignments

There are many factors that affect gate assignments in an airport's operations. These factors include static gate assignments, stochastic flight delays and real-time gate assignments. Most research on gate assignments in the past has laid stress on improving the performance of static gate assignments. None has analyzed the interrelationship between static gate assignments and real-time gate assignments as affected by the stochastic flight delays that occur in real operations. In addition, none has designed flexible buffer times for static gate assignments to effectively absorb stochastic delays in real-time gate assignments. This research proposes a simulation framework, that is not only able to analyze the effects of stochastic flight delays on static gate assignments, but can also evaluate flexible buffer times and real-time gate assignment rules. Finally, a simulation based on Chiang Kai-Shek airport operations is performed to evaluate the simulation framework.