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.     

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.     

The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems

Dynamic user optimal simultaneous route and departure time choice (DUO-SRDTC) problems are usually formulated as variational inequality (VI) problems whose solution algorithms generally require continuous and monotone route travel cost functions to guarantee convergence. However, the monotonicity of the route travel cost functions cannot be ensured even if the route travel time functions are monotone. In contrast to traditional formulations, this paper formulates a DUO-SRDTC problem (that can have fixed or elastic demand) as a system of nonlinear equations. The system of nonlinear equations is a function of generalized origin-destination (OD) travel costs rather than route flows and includes a dynamic user optimal (DUO) route choice subproblem with perfectly elastic demand and a quadratic programming (QP) subproblem under certain assumptions. This study also proposes a solution method based on the backtracking inexact Broyden–Fletcher–Goldfarb–Shanno (BFGS) method, the extragradient algorithm, and the Frank-Wolfe algorithm. The BFGS method, the extragradient algorithm, and the Frank-Wolfe algorithm are used to solve the system of nonlinear equations, the DUO route choice subproblem, and the QP subproblem, respectively. The proposed formulation and solution method can avoid the requirement of monotonicity of the route travel cost functions to obtain a convergent solution and provide a new approach with which to solve DUO-SRDTC problems. Finally, numeric examples are used to demonstrate the performance of the proposed solution method.     

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.     

Accommodating user preferences in ad hoc shared ride trip planning using GIS

Ad hoc shared ride trip planning (SRTP) utilizes mobile devices, geo-sensors and wireless networks to match on-the-fly individual travel demand with transport supply. It represents one of many alternatives to single occupancy vehicle use. This paper outlines a SRTP approach via a two-phase algorithm based on user preferences in a time-dependent routing. Whereas current algorithms use minimization of travel time as the only optimization criterion in trip planning, in the framework presented here, the user can specify multiple trip preferences including travel time, walking time, number of transfers between cars and trip length. Various scenarios are simulated in the city of Tehran (Iran) to demonstrate how preference settings affect the routes of ad hoc shared journeys.     

Comparative analysis of three user equilibrium models under stochastic demand

Recent empirical studies on the value of time and reliability reveal that travel time variability plays an important role on travelers' route choice decision process. It can be considered as a risk to travelers making a trip. Therefore, travelers are not only interested in saving their travel time but also in reducing their risk. Typically, risk can be represented by two different aspects: acceptable risk and unacceptable risk. Acceptable risk refers to the reliability aspect of acceptable travel time, which is defined as the average travel time plus the acceptable additional time (or buffer time) needed to ensure more frequent on‐time arrivals, while unacceptable risk refers to the unreliability aspect of unacceptable late arrivals (though infrequent) that have a travel time excessively higher than the acceptable travel time. Most research in the network equilibrium based approach to modeling travel time variability ignores the unreliability aspect of unacceptable late arrivals. This paper examines the effects of both reliability and unreliability aspects in a network equilibrium framework. Specifically, the traditional user equilibrium model, the demand driven travel time reliability‐based user equilibrium model, and the α‐reliable mean‐excess travel time user equilibrium model are considered in the investigation under an uncertain environment due to stochastic travel demand. Numerical results are presented to examine how these models handle risk under travel time variability.     

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.     

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 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.     

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.     

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.     

Boundedly rational user equilibria (BRUE): Mathematical formulation and solution sets

Boundedly rational user equilibria (BRUE) represent traffic flow distribution patterns where travellers can take any route whose travel cost is within an ‘indifference band’ of the shortest path cost. Those traffic flow patterns satisfying the above condition constitute a set, named the BRUE solution set. It is important to obtain all the BRUE flow patterns, because it can help predict the variation of the link flow pattern in a traffic network under the boundedly rational behavior assumption. However, the methodology of constructing the BRUE set has been lacking in the established literature. This paper fills the gap by constructing the BRUE solution set on traffic networks with fixed demands. After defining ε-BRUE, where ε is the indifference band for the perceived travel cost, we formulate the ε-BRUE problem as a nonlinear complementarity problem (NCP), so that a BRUE solution can be obtained by solving a BRUE–NCP formulation. To obtain the BRUE solution set encompassing all BRUE flow patterns, we propose a methodology of generating acceptable path set which may be utilized under the boundedly rational behavior assumption. We show that with the increase of the indifference band, the acceptable path set that contains boundedly rational equilibrium flows will be augmented, and the critical values of indifference band to augment these path sets can be identified by solving a family of mathematical programs with equilibrium constraints (MPEC) sequentially. The BRUE solution set can then be obtained by assigning all traffic demands to the acceptable path set. Various numerical examples are given to illustrate our findings.     

Global optimization methods for the discrete network design problem

This paper addresses the discrete network design problem (DNDP) with multiple capacity levels, or multi-capacity DNDP for short, which determines the optimal number of lanes to add to each candidate link in a road network. We formulate the problem as a bi-level programming model, where the upper level aims to minimize the total travel time via adding new lanes to candidate links and the lower level is a traditional Wardrop user equilibrium (UE) problem. We propose two global optimization methods by taking advantage of the relationship between UE and system optimal (SO) traffic assignment principles. The first method, termed as SO-relaxation, exploits the property that an optimal network design solution under SO principle can be a good approximate solution under UE principle, and successively sorts the solutions in the order of increasing total travel time under SO principle. Optimality is guaranteed when the lower bound of the total travel time of the unexplored solutions under UE principle is not less than the total travel time of a known solution under UE principle. The second method, termed as UE-reduction, adds the objective function of the Beckmann-McGuire-Winsten transformation of UE traffic assignment to the constraints of the SO-relaxation formulation of the multi-capacity DNDP. This constraint is convex and strengthens the SO-relaxation formulation. We also develop a dynamic outer-approximation scheme to make use of the state-of-the-art mixed-integer linear programming solvers to solve the SO-relaxation formulation. Numerical experiments based on a two-link network and the Sioux-Falls network are conducted.     

Pareto-improving congestion pricing and revenue refunding with multiple user classes

This study investigates Pareto-improving congestion pricing and revenue refunding schemes in general transportation networks, which make every road user better off as compared with the situation without congestion pricing. We consider user heterogeneity in value of time (VOT) by adopting a multiclass user model with fixed origin–destination (OD) demands. We first prove that an OD and class-based Pareto-improving refunding scheme exists if and only if the total system monetary travel disutility is reduced. In view of the practical difficulty in identifying individual user’s VOT, we further investigate class-anonymous refunding schemes that give the same amount of refund to all user classes traveling between the same OD pair regardless of their VOTs. We establish a sufficient condition for the existence of such OD-specific but class-anonymous Pareto-improving refunding schemes, which needs information only on the average toll paid and average travel time for trips between each OD pair.     

Modeling the evolutions of day‐to‐day route choice and year‐to‐year ATIS adoption with stochastic user equilibrium

Suppose that in an urban transportation network there is a specific advanced traveler information system (ATIS) which acts for reducing the drivers' travel time uncertainty through provision of pre‐trip route information. Because of the imperfect information provided, some travelers are not in compliance with the ATIS advice although equipped with the device. We thus divide all travelers into three groups, one group unequipped with ATIS, another group equipped and in compliance with ATIS advice and the third group equipped but without compliance with the advice. Each traveler makes route choice in a logit‐based manner and a stochastic user equilibrium with multiple user classes is reached for every day. In this paper, we propose a model to investigate the evolutions of daily path travel time, daily ATIS compliance rate and yearly ATIS adoption, in which the equilibrium for every day's route choice is kept. The stability of the evolution model is initially analyzed. Numerical results obtained from a test network are presented for demonstrating the model's ability in depicting the day‐to‐day and year‐to‐year evolutions.     

Modelling rain effects on risk‐taking behaviours of multi‐user classes in road networks with uncertainty

This paper proposes a new travel time reliability‐based traffic assignment model to investigate the rain effects on risk‐taking behaviours of different road users in networks with day‐to‐day demand fluctuations and variations in travel time. A generalized link travel time function is used to capture the rain effects on vehicle travel times and road conditions. This function is further incorporated into daily demand variations to investigate those travel time variations arising from demand uncertainty and rain condition. In view of these rain effects, road users' perception errors on travel times and risk‐taking behaviours on path choices are incorporated in the proposed model with the use of a logit‐based stochastic user equilibrium framework. This new model is formulated as a variational inequality problem in terms of path flows. A numerical example is used to illustrate the application of the proposed model for assessment of the rain effects on road networks with uncertainty.     

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.     

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.     

Solving a discrete multimodal transportation network design problem

This paper investigates the multimodal network design problem (MMNDP) that optimizes the auto network expansion scheme and bus network design scheme in an integrated manner. The problem is formulated as a single-level mathematical program with complementarity constraints (MPCC). The decision variables, including the expanded capacity of auto links, the layout of bus routes, the fare levels and the route frequencies, are transformed into multiple sets of binary variables. The layout of transit routes is explicitly modeled using an alternative approach by introducing a set of complementarity constraints. The congestion interaction among different travel modes is captured by an asymmetric multimodal user equilibrium problem (MUE). An active-set algorithm is employed to deal with the MPCC, by sequentially solving a relaxed MMNDP and a scheme updating problem. Numerical tests on nine-node and Sioux Falls networks are performed to demonstrate the proposed model and algorithm.     

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.