A path-based flow formulation for the traffic assignment problem

In order to improve cooperation between traffic management and travelers, traffic assignment is the key component to achieve the objectives of both traffic management and route choice decisions for travelers. Traffic assignment can be classified into two models based on the behavioral assumptions governing route choices: User Equilibrium (UE) and System Optimum (SO) traffic assignment. According to UE and SO traffic assignment, travelers usually compete to choose the least cost routes to minimize their own travel costs, while SO traffic assignment requires travelers to work cooperatively to minimize overall cost in the road network. Thus, the paradox of benefits between UE and SO indicates that both are not practical. Thus, a solution technique needs to be proposed to balance UE and SO models, which can compromise both sides and give more feasible traffic assignments. In this paper, Stackelberg game theory is introduced to the traffic assignment problem, which can achieve the trade-off process between traffic management and travelers. Since traditional traffic assignments have low convergence rates, the gradient projection algorithm is proposed to improve efficiency.     

Dynamic system-optimal traffic assignment using a state space model

We propose a new mathematical formulation for the problem of optimal traffic assignment in dynamic networks with multiple origins and destinations. This problem is motivated by route guidance issues that arise in an Intelligent Vehicle-Highway Systems (IVHS) environment. We assume that the network is subject to known time-varying demands for travel between its origins and destinations during a given time horizon. The objective is to assign the vehicles to links over time so as to minimize the total travel time experienced by all the vehicles using the network. We model the traffic network over the time horizon as a discrete-time dynamical system. The system state at each time instant is defined in a way that, without loss of optimality, avoids complete microscopic detail by grouping vehicles into platoons irrespective of origin node and time of entry to network. Moreover, the formulation contains no explicit path enumeration. The state transition function can model link travel times by either impedance functions, link outflow functions, or by a combination of both. Two versions (with different boundary conditions) of the problem of optimal traffic assignment are studied in the context of this model. These optimization problems are optimal control problems for nonlinear discrete-time dynamical systems, and thus they are amenable to algorithmic solutions based on dynamic programming. The computational challenges associated with the exact solution of these problems are discussed and some heuristics are proposed.     

Formulating and solving the network design problem by decomposition

The optimal transportation network design problem is formulated as a convex nonlinear programming problem and a solution method based on standard traffic assignment algorithms is presented. The technique can deal with network improvements which introduce new links, which increase the capacity of existing links, or which decrease the free-flow (uncongested) travel time on existing links (with or without simultaneously increasing link capacity). Preliminary computational experience with the method demonstrates that it is capable of solving very large problems with reasonable amounts of computer time.     

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.     

Optimal speed detector density for the network with travel time information

In the expressway network, detectors are installed on the links for detecting the travel time information while the predicted travel time can be provided by the route guidance system (RGS). The speed detector density can be determined to influence flow distributions in such a way that the precision of the travel time information and the social cost of the speed detectors are optimized, provided that each driver chooses the minimum perceived travel time path in response to the predicted travel time information. In this paper, a bilevel programming model is proposed for the network with travel time information provided by the RGS. The lower-level problem is a probit-based traffic assignment model, while the upper-level problem is to determine the speed detector density that minimizes the measured travel time error variance as well as the social cost of the speed detectors. The sensitivity analysis based algorithm is proposed for the bilevel programming problem. Numerical examples are provided to illustrate the applications of the proposed model and of the solution algorithm.     

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 linear programming formulation for autonomous intersection control within a dynamic traffic assignment and connected vehicle environment

This paper develops a novel linear programming formulation for autonomous intersection control (LPAIC) accounting for traffic dynamics within a connected vehicle environment. Firstly, a lane based bi-level optimization model is introduced to propagate traffic flows in the network, accounting for dynamic departure time, dynamic route choice, and autonomous intersection control in the context of system optimum network model. Then the bi-level optimization model is transformed to the linear programming formulation by relaxing the nonlinear constraints with a set of linear inequalities. One special feature of the LPAIC formulation is that the entries of the constraint matrix has only {−1, 0, 1} values. Moreover, it is proved that the constraint matrix is totally unimodular, the optimal solution exists and contains only integer values. It is also shown that the traffic flows from different lanes pass through the conflict points of the intersection safely and there are no holding flows in the solution. Three numerical case studies are conducted to demonstrate the properties and effectiveness of the LPAIC formulation to solve autonomous intersection control.     

Mechanisms that govern how the Price of Anarchy varies with travel demand

Selfish routing, represented by the User-Equilibrium (UE) model, is known to be inefficient when compared to the System Optimum (SO) model. However, there is currently little understanding of how the magnitude of this inefficiency, which can be measured by the Price of Anarchy (PoA), varies across different structures of demand and supply. Such understanding would be useful for both transport policy and network design, as it could help to identify circumstances in which policy interventions that are designed to induce more efficient use of a traffic network, are worth their costs of implementation.This paper identifies four mechanisms that govern how the PoA varies with travel demand in traffic networks with separable and strictly increasing cost functions. For each OD movement, these are expansions and contractions in the sets of routes that are of minimum cost under UE and minimum marginal total cost under SO. The effects of these mechanisms on the PoA are established via a combination of theoretical proofs and conjectures supported by numerical evidence. In addition, for the special case of traffic networks with BPR-like cost functions having common power, it is proven that there is a systematic relationship between link flows under UE and SO, and hence between the levels of demand at which expansions and contractions occur. For this case, numerical evidence also suggests that the PoA has power law decay for large demand.     

The impact of speed limits on traffic equilibrium and system performance in networks

Speed limits are usually imposed on roads in an attempt to enhance safety and sometimes serve the purpose of reducing fuel consumption and vehicular emissions as well. Most previous studies up to date focus on investigation of the effects of speed limits from a local perspective, while network-wide traffic reallocation effects are overlooked. This paper makes the first attempt to investigate how a link-specific speed limit law reallocates traffic flow in an equilibrium manner at a macroscopic network level. We find that, although the link travel time–flow relationship is altered after a speed limit is imposed, the standard traffic assignment method still applies. With the commonly adopted assumptions, the uniqueness of link travel times at user equilibrium (UE) remains valid, and the UE flows on links with non-binding speed limits are still unique. The UE flows on other links with binding speed limits may not be unique but can be explicitly characterized by a polyhedron or a linear system of equalities and inequalities. Furthermore, taking into account the traffic reallocation effects of speed limits, we compare the capability of speed limits and road pricing for decentralizing desirable network flow patterns. Although from a different perspective for regulating traffic flows with a different mechanism, a speed limit law may play the same role as a toll charge scheme and perform better than some negative (rebate) toll schemes under certain conditions for network flow management.     

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.     

Multi-objective optimization of a road diet network design

The present study focuses on the development of a model for the optimal design of a road diet plan within a transportation network, and is based on rigorous mathematical models. In most metropolitan areas, there is insufficient road space to dedicate a portion exclusively for cyclists without negatively affecting existing motorists. Thus, it is crucial to find an efficient way to implement a road diet plan that both maximizes the utility for cyclists and minimizes the negative effect on motorists. A network design problem (NDP), which is usually used to find the best option for providing extra road capacity, is adapted here to derive the best solution for limiting road capacity. The resultant NDP for a road diet (NDPRD) takes a bi-level form. The upper-level problem of the NDPRD is established as one of multi-objective optimization. The lower-level problem accommodates user equilibrium (UE) trip assignment with fixed and variable mode-shares. For the fixed mode-share model, the upper-level problem minimizes the total travel time of both cyclists and motorists. For the variable mode-share model, the upper-level problem includes minimization of both the automobile travel share and the average travel time per unit distance for motorists who keep using automobiles after the implementation of a road diet. A multi-objective genetic algorithm (MOGA) is mobilized to solve the proposed problem. The results of a case study, based on a test network, guarantee a robust approximate Pareto optimal front. The possibility that the proposed methodology could be adopted in the design of a road diet plan in a real transportation network is confirmed.     

A portfolio theory of route choice

Although many individual route choice models have been proposed to incorporate travel time variability as a decision factor, they are typically still deterministic in the sense that the optimal strategy requires choosing one particular route that maximizes utility. In contrast, this study introduces an individual route choice model where choosing a portfolio of routes instead of a single route is the best strategy for a rational traveler who cares about both journey time and lateness when facing stochastic network conditions. The proposed model is compared with UE and SUE models and the difference in both behavioral foundation and model characteristics is highlighted. A numerical example is introduced to demonstrate how such model can be used in traffic assignment problem. The model is then tested with GPS data collected in metropolitan Minneapolis–St. Paul, Minnesota. Our data suggest there is no single dominant route (defined here as a route with the shortest travel time for a 15 day period) in 18% of cases when links travel times are correlated. This paper demonstrates that choosing a portfolio of routes could be the rational choice of a traveler who wants to optimize route decisions under variability.     

Dynamic user optimal traffic assignment on congested multidestination networks

An equivalent continuous time optimal control problem is formulated to predict the temporal evolution of traffic flow pattern on a congested multiple origin-destination network, corresponding to a dynamic generalization of Wardropian user equilibrium. Optimality conditions are derived using the Pontryagin minimum principle and given economic interpretations, which are generalizations of similar results previously reported for single-destination networks. Analyses of sufficient conditions for optimality and of singular controls are also given. Under the steady-state assumptions, the model is shown to be a proper dynamic extension of Beckmann's mathematical programming problem for a static user equilibrium traffic assignment.     

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

Traffic signal timing problems with environmental and equity considerations

Traffic signal timings in a road network can not only affect total user travel time and total amount of traffic emissions in the network but also create an inequity problem in terms of the change in travel costs of users traveling between different locations. This paper proposes a multi‐objective bi‐level programming model for design of sustainable and equitable traffic signal timings for a congested signal‐controlled road network. The upper level of the proposed model is a multi‐objective programming problem with an equity constraint that maximizes the reserve capacity of the network and minimizes the total amount of traffic emissions. The lower level is a deterministic network user equilibrium problem that considers the vehicle delays at signalized intersections of the network. To solve the proposed model, an approach for normalizing incommensurable objective functions is presented, and a heuristic solution algorithm that combines a penalty function approach and a simulated annealing method is developed. Two numerical examples are presented to show the effects of reserve capacity improvement and green time proportion on network flow distribution and transportation system performance and the importance of incorporating environmental and equity objectives in the traffic signal timing problems. Copyright © 2013 John Wiley & Sons, Ltd.     

An optimization method for sustainable traffic control in urban areas

The optimization of traffic signalization in urban areas is formulated as a problem of finding the cycle length, the green times and the offset of traffic signals that minimize an objective function of performance indices. Typical approaches to this optimization problem include the maximization of traffic throughput or the minimization of vehicles’ delays, number of stops, fuel consumption, etc. Dynamic Traffic Assignment (DTA) models are widely used for online and offline applications for efficient deployment of traffic control strategies and the evaluation of traffic management schemes and policies. We propose an optimization method for combining dynamic traffic assignment and network control by minimizing the risk of potential loss induced to travelers by exceeding their budgeted travel time as a result of deployed traffic signal settings, using the Conditional Value-at-Risk model. The proposed methodology can be easily implemented by researchers or practitioners to evaluate their alternative strategies and aid them to choose the alternative with less potential risk. The traffic signal optimization procedure is implemented in TRANSYT-7F and the dynamic propagation and route choice of vehicles is simulated with a mesoscopic dynamic traffic assignment tool (DTALite) with fixed temporal demand and network characteristics. The proposed approach is applied to a reference test network used by many researchers for verification purposes. Numerical experiments provide evidence of the advantages of this optimization method with respect to conventional optimization techniques. The overall benefit to the performance of the network is evaluated with a Conditional Value-at-Risk Analysis where the optimal solution is the one presenting the least risk for ‘guaranteed’ total travel times.     

Transport Network Design Problem under Uncertainty: A Review and New Developments

This paper aims to provide a state-of-the-art review of the transport network design problem (NDP) under uncertainty and to present some new developments on a bi-objective-reliable NDP (BORNDP) model that explicitly optimizes the capacity reliability and travel time reliability under demand uncertainty. Both are useful performance measures that can describe the supply-side reliability and demand-side reliability of a road network. A simulation-based multi-objective genetic algorithm solution procedure, which consists of a traffic assignment algorithm, a genetic algorithm, a Pareto filter, and a Monte-Carlo simulation, is developed to solve the proposed BORNDP model. A numerical example based on the capacity enhancement problem is presented to demonstrate the tradeoff between capacity reliability and travel time reliability in the NDP.     

A methodology to control urban traffic noise under the constraint of environmental capacity: A case study of a double-decision optimization model

This paper presents a novel methodology to control urban traffic noise under the constraint of environmental capacity. Considering the upper limits of noise control zones as the major bottleneck to control the maximum traffic flow is a new idea. The urban road network traffic is the mutual or joint behavior of public self-selection and management decisions, so is a typical double decision optimization problem.The proposed methodology incorporates theoretically model specifications. Traffic noise calculation model and traffic assignment model for O–D matrix are integrated based on bi-level programming method which follows an iterated process to obtain the optimal solution. The upper level resolves the question of how to sustain the maximum traffic flow with noise capacity threshold in a feasible road network. The user equilibrium method is adopted in the lower layer to resolve the O–D traffic assignment.The methodology has been applied to study area of QingDao, China. In this illustrative case, the noise pollution level values of optimal solution could satisfy the urban environmental noise capacity constraints. Moreover, the optimal solution was intelligently adjusted rather than simply reducing the value below a certain threshold. The results indicate that the proposed methodology is feasible and effective, and it can provide a reference for a sustainable development and noise control management of the urban traffic.     

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