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.     

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.     

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.     

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.     

Dynamic user equilibrium based on a hydrodynamic model

In this paper we present a continuous-time network loading procedure based on the Lighthill–Whitham–Richards model proposed by Lighthill and Whitham, 1955, Richards, 1956. A system of differential algebraic equations (DAEs) is proposed for describing traffic flow propagation, travel delay and route choices. We employ a novel numerical apparatus to reformulate the scalar conservation law as a flow-based partial differential equation (PDE), which is then solved semi-analytically with the Lax–Hopf formula. This approach allows for an efficient computational scheme for large-scale networks. We embed this network loading procedure into the dynamic user equilibrium (DUE) model proposed by Friesz et al. (1993). The DUE model is solved as a differential variational inequality (DVI) using a fixed-point algorithm. Several numerical examples of DUE on networks of varying sizes are presented, including the Sioux Falls network with a significant number of paths and origin–destination pairs (OD).The DUE model presented in this article can be formulated as a variational inequality (VI) as reported in Friesz et al. (1993). We will present the Kuhn–Tucker (KT) conditions for that VI, which is a linear system for any given feasible solution, and use them to check whether a DUE solution has been attained. In order to solve for the KT multiplier we present a decomposition of the linear system that allows efficient computation of the dual variables. The numerical solutions of DUE obtained from fixed-point iterations will be tested against the KT conditions and validated as legitimate solutions.     

A bi-level model of dynamic traffic signal control with continuum approximation

This paper proposes a bi-level model for traffic network signal control, which is formulated as a dynamic Stackelberg game and solved as a mathematical program with equilibrium constraints (MPEC). The lower-level problem is a dynamic user equilibrium (DUE) with embedded dynamic network loading (DNL) sub-problem based on the LWR model (Lighthill and Whitham, 1955; Richards, 1956). The upper-level decision variables are (time-varying) signal green splits with the objective of minimizing network-wide travel cost. Unlike most existing literature which mainly use an on-and-off (binary) representation of the signal controls, we employ a continuum signal model recently proposed and analyzed in Han et al. (2014), which aims at describing and predicting the aggregate behavior that exists at signalized intersections without relying on distinct signal phases. Advantages of this continuum signal model include fewer integer variables, less restrictive constraints on the time steps, and higher decision resolution. It simplifies the modeling representation of large-scale urban traffic networks with the benefit of improved computational efficiency in simulation or optimization. We present, for the LWR-based DNL model that explicitly captures vehicle spillback, an in-depth study on the implementation of the continuum signal model, as its approximation accuracy depends on a number of factors and may deteriorate greatly under certain conditions. The proposed MPEC is solved on two test networks with three metaheuristic methods. Parallel computing is employed to significantly accelerate the solution procedure.     

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.     

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

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.     

Dynamic charging infrastructure deployment for plug-in hybrid electric trucks

Inspired by the rapid development of charging-while-driving (CWD) technology, plans are ongoing in government agencies worldwide for the development of electrified road freight transportation systems through the deployment of dynamic charging lanes. This en route method for the charging of plug-in hybrid electric trucks is expected to supplement the more conventional charging technique, thus enabling significant reduction in fossil fuel consumption and pollutant emission from road freight transportation. In this study, we investigated the optimal deployment of dynamic charging lanes for plug-in hybrid electric trucks. First, we developed a multi-class multi-criteria user equilibrium model of the route choice behaviors of truck and passenger car drivers and the resultant equilibrium flow distributions. Considering that the developed user equilibrium model may have non-unique flow distributions, a robust deployment of dynamic charging lanes that optimizes the system performance under the worst-case flow distributions was targeted. The problem was formulated as a generalized semi-infinite min-max program, and a heuristic algorithm for solving it was proposed. This paper includes numerical examples that were used to demonstrate the application of the developed models and solution algorithms.     

Formulating the within-day dynamic stochastic traffic assignment problem from a Bayesian perspective

This study proposes a formulation of the within-day dynamic stochastic traffic assignment problem. Considering the stochastic nature of route choice behavior, we treat the solution to the assignment problem as the conditional joint distribution of route traffic, given that the network is in dynamic stochastic user equilibrium. We acquire the conditional joint probability distribution using Bayes’ theorem. A Metropolis–Hastings sampling scheme is developed to estimate the characteristics (e.g., mean and variance) of the route traffic. The proposed formulation has no special requirements for the traffic flow models and user behavior models, and so is easily implemented.     

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.     

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.     

A dynamic traffic assignment model for a continuum transportation system

A predictive continuum dynamic user-optimal (PDUO-C) model is formulated in this study to investigate the dynamic characteristics of traffic flow and the corresponding route-choice behavior of travelers within a region with a dense urban road network. The modeled region is arbitrary in shape with a single central business district (CBD) and travelers continuously distributed over the region. Within this region, the road network is represented as a continuum and travelers patronize a two-dimensional continuum transportation system to travel to the CBD. The PDUO-C model is solved by a promising solution algorithm that includes elements of the finite volume method (FVM), the finite element method (FEM), and the explicit total variation diminishing Runge-Kutta (TVD-RK) time-stepping method. A numerical example is given to demonstrate the utility of the proposed model and the effectiveness of the solution algorithm in solving this PDUO-C problem.     

Continuum modelling of spatial and dynamic equilibrium in a travel corridor with heterogeneous commuters—A partial differential complementarity system approach

This paper studies on modelling and solving spatial and dynamic equilibrium travel pattern in a travel corridor. Consider a travel corridor connecting continuously distributed commuters to the city centre. The traffic is subject to flow congestion and the commuter heterogeneity is captured. The traffic flow dynamics is described by flow continuity equation and the equilibrium travel pattern is assumed to follow trip-timing condition. The continuous spatial and dynamic equilibrium travel pattern is formulated into a partial differential complementarity system, which is then solved through Godunov scheme. The proof of solution existence is provided, and a set of numerical experiments are demonstrated.     

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.     

A combined activity/travel choice model for congested road networks with queues

This paper presents a combined activity/travel choice model and proposes a flow-swapping method for obtaining the model's dynamic user equilibrium solution on congested road network with queues. The activities of individuals are characterized by given temporal utility profiles. Three typical activities, which can be observed in morning peak period, namely at-home activity, non-work activity on the way from home to workplace and work-purpose activity, will be considered in the model. The former two activities always occur together with the third obligatory activity. These three activities constitute typical activity/travel patterns in time-space dimension. At the equilibrium, each combined activity/travel pattern, in terms of chosen location/route/departure time, should have identical generalized disutility (or utility) experienced actually. This equilibrium can be expressed as a discrete-time, finite-dimensional variational inequality formulation and then converted to an equivalent "zero-extreme value" minimization problem. An algorithm, which iteratively adjusts the non-work activity location, corresponding route and departure time choices to reach an extreme point of the minimization problem, is proposed. A numerical example with a capacity constrained network is used to illustrate the performance of the proposed model and solution algorithm.