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.     

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.     

Ant Colony Routing algorithm for freeway networks

Dynamic traffic routing refers to the process of (re)directing vehicles at junctions in a traffic network according to the evolving traffic conditions. The traffic management center can determine desired routes for drivers in order to optimize the performance of the traffic network by dynamic traffic routing. However, a traffic network may have thousands of links and nodes, resulting in a large-scale and computationally complex non-linear, non-convex optimization problem. To solve this problem, Ant Colony Optimization (ACO) is chosen as the optimization method in this paper because of its powerful optimization heuristic for combinatorial optimization problems. ACO is implemented online to determine the control signal – i.e., the splitting rates at each node. However, using standard ACO for traffic routing is characterized by four main disadvantages: 1. traffic flows for different origins and destinations cannot be distinguished; 2. all ants may converge to one route, causing congestion; 3. constraints cannot be taken into account; and 4. neither can dynamic link costs. These problems are addressed by adopting a novel ACO algorithm with stench pheromone and with colored ants, called Ant Colony Routing (ACR). Using the stench pheromone, the ACR algorithm can distribute the vehicles over the traffic network with less or no traffic congestion, as well as reduce the number of vehicles near some sensitive zones, such as hospitals and schools. With colored ants, the traffic flows for multiple origins and destinations can be represented. The proposed approach is also implemented in a simulation-based case study in the Walcheren area, the Netherlands, illustrating the effectiveness of the approach.     

Dynamic system‐optimal traffic assignment for a city using the continuum modeling approach

This paper presents a continuum dynamic traffic assignment model for a city in which the total cost of the traffic system is minimized: the travelers in the system are organized to choose the route to their destinations that minimizes the total cost of the system. Combined with the objective function, which defines the total cost and constraints such as certain physical and boundary conditions, a continuum model can be formulated as an optimization scheme with a feasible region in the function space. To obtain an admissible locally optimal solution to this problem, we first reformulate the optimization in discrete form and then introduce a heuristic method to solve it. This method converges rapidly with attractive computational cost. Numerical examples are used to demonstrate the effectiveness of the method. Copyright © 2013 John Wiley & Sons, Ltd.     

Revisiting Jiang’s dynamic continuum model for urban cities

Jiang et al. (Jiang, Y.Q., Wong, S.C., Ho, H.W., Zhang, P., Liu, R.X., Sumalee, A., 2011. A dynamic traffic assignment model for a continuum transportation system. Transportation Research Part B 45 (2), 343–363) proposed a predictive continuum dynamic user-optimaDUO-l to investigate the dynamic characteristics of traffic flow and the corresponding route-choice behavior of travelers. Their modeled region is a dense urban city that is arbitrary in shape and has a single central business district (CBD). However, we argue that the model is not well posed due to an inconsistency in the route-choice strategy under certain conditions. To overcome this inconsistency, we revisit the PDUO-C problem, and construct an improved path-choice strategy. The improved model consists of a conservation law to govern the density, in which the flow direction is determined by the improved path-choice strategy, and a Hamilton–Jacobi equation to compute the total travel cost. The simultaneous satisfaction of both equations can be treated as a fixed-point problem. A self-adaptive method of successive averages (MSA) is proposed to solve this fixed-point problem. This method can automatically determine the optimal MSA step size using the least squares approach. Numerical examples are used to demonstrate the effectiveness of the model and the solution algorithm.     

Traffic assignment in a two-dimensional continuous representation of a traffic network with flow-dependent speeds

The work deals with the assignment of traffic to a two-dimensional continuous representation of a traffic network. An important aspect of the treatment is that the reciprocal of the speed on each road in the network is at all times a linear function of the flow on that road. This speed-flow relationship is generalized to two-dimensional space using travel intensities and taking account of road densities, so that there is direct dependence of speeds upon flows at all points regardless of their location. There is also dependence of flows upon speeds at all points because Wardrop's first assignment principle is adopted. That is, for a given O-D pair, journey times on all routes actually used are identical, and less than journey times on all other possible routes. This results in the identification for each O-D pair of an “assignment zone”, an area within which all trips between that O-D pair are made, and beyond which no such trips are made. For a single O-D pair the assignment zone is identified by ?_m, the maximum angular divergence of a path from the straight line between O and D. Paths are then assumed to be bilinear so that for a single O-D pair the assignment zone is a parallelogram. Journey times, speeds, lateral displacement and other related quantities are obtained as functions of the flow Q between O and D. The work is extended to three O-D pairs located at the extremities of an equilateral triangle and four O-D pairs located at the corners of a square. At low flows these two configurations are trivial extensions of the single O-D pair problem because assignment zones do not overlap. At higher flows account is taken of this tendency to overlapping, so that although they do not overlap they do touch, becoming kite-shaped. Origins and destinations are assumed to be at the periphery of small circles of arbitrary radius. The work is inelegant to the extent that it involves a numerical integration but it is possible that this might eventually be circumvented.     

Merging bus routes in Hong Kong’s central business district: Analysis and models

A significant portion of the 200,000 people working in Hong Kong’s central business district (CBD) relies on buses as their primary means of transport. During peak hours, nearly a thousand double-decker buses pour into a tiny area of 150 ha. This causes traffic congestion and air pollution. Moreover, given that the flow is uni-directional (into the CBD in the morning and out of the CBD in the afternoon), the occupancy of buses in the CBD is actually low.In this paper, we propose to reduce traffic congestion and to increase bus occupancy by merging bus routes. We describe the peculiar situation of the CBD in Hong Kong and explain the necessary conditions for the possible success of merging routes. Our analysis shows that merging will lead to an overall benefit for all parties, including government, bus operators, and passengers. The actual merging decisions, which routes to merge and at what frequencies buses should run, are determined by a mathematical model. The model also shows quantitatively the benefits of merging routes and the impacts of other factors. The procedure that we follow and the model that we adopt can be applied to other CBD.     

Making do: The effects of a mass transit strike on travel behavior

A brief transit strike in early December 1976 disrupted bus services to the city of Pittsburgh and surrounding Allegheny County. That strike provided an opportunity for testing a variety of approaches to increase ride-sharing and to reduce traffic congestion, and for examining the effect of the strike on traffic congestion and on individual travel behavior. Even though over 60% of the commuters to the CBD use transit, the effects of the strike were relatively mild. There was some increase in traffic flow into the CBD and some spreading of the peak period. The largest proportion of the transit commuters who made trips to the CBD during the strike were dropped off by a non-commuter, increasing highway traffic. The most severe impact was felt by those transit commuters who had no cars in the household; 25% of these commuters (only 3% of the total CBD commuters) stayed home from work on the first day of the strike. Most attempts to mitigate the impact of the strike had little effect, largely because most commuters were able to manage adequately during the short strike. The anticipated parking problem, on which much of the contingency planning was focused, did not emerge, largely because of the use of carpooling and drop-off mode by many of the transit users.     

Evaluating the assumption of independent turning probabilities

Several urban traffic models make the convenient assumption that turning probabilities are independent, meaning that the probability of turning right (or left or going straight through) at the downstream intersection is the same for all travelers on that roadway, regardless of their origin or destination. In reality most travelers make turns according to planned routes from origins to destinations. The research reported here identifies and quantifies the deviations that result from this assumption of independent turning probabilities.An analysis of this type requires a set of reasonably realistic “original” route flows, which were obtained by a static user-equilibrium traffic assignment and an entropy maximization condition for most likely route flows. These flows are compared with those route flows resulting from the Assumption of Independent Turning Probabilities (ITP). A small subnetwork of 3 km by 5 km in Tucson, Arizona, was chosen as a case study. An overall “typical ratio” of 2.2 between original route flows and ITP route flows was obtained. Aggregating route flows to origin–destination flows led to an overall “typical ratio” of 1.7. Such deviations are particularly high for routes that go back-and-forth, reaching a ratio of more than 3 in certain time periods. Substantial deviations for origins and destinations that are on the same border of the subnetwork are also observed in the analyses. In addition, under the ITP assumption, morning rush hour traffic peaking is the same in all directions, while in the original flows some directions do not exhibit a peak in the morning rush hour period. Overall, the conclusion of the paper is that the assumption of independent turning probabilities leads to substantial deviations both at the route level and at the origin–destination level, even for such a small network of the case study. These deviations are particularly detrimental when a network is being modeled and studied for route-based measures of effectiveness such as the number and types of routes passing a point – for monitoring specified vehicles and/or managing detouring strategies.     

A real-time traffic signal control system: architecture, algorithms, and analysis

The paper discusses a real-time traffic-adaptive signal control system referred to as RHODES. The system takes as input detector data for real-time measurement of traffic flow, and “optimally” controls the flow through the network. The system utilizes a control architecture that (1) decomposes the traffic control problem into several subproblems that are interconnected in an hierarchical fashion, (2) predicts traffic flows at appropriate resolution levels (individual vehicles and platoons) to enable pro-active control, (3) allows various optimization modules for solving the hierarchical subproblems, and (4) utilizes a data structure and computer/communication approaches that allow for fast solution of the subproblems, so that each decision can be downloaded in the field appropriately within the given rolling time horizon of the corresponding subproblem. The RHODES architecture, algorithms, and its analysis are presented. Laboratory test results, based on implementation of RHODES on simulation models of actual scenarios, illustrate the effectiveness of the system.     

A predictive dynamic traffic assignment model in congested capacity-constrained road networks

In this paper, a predictive dynamic traffic assignment model in congested capacity-constrained road networks is formulated. A traffic simulator is developed to incrementally load the traffic demand onto the network, and updates the traffic conditions dynamically. A time-dependent shortest path algorithm is also given to determine the paths with minimum actual travel time from an origin to all the destinations. The traffic simulator and time-dependent shortest path algorithm are employed in a method of successive averages to solve the dynamic equilibrium solution of the problem. A numerical example is given to illustrate the effectiveness of the proposed method.     

A maximum entropy-least squares estimator for elastic origin-destination trip matrix estimation

In transportation subnetwork-supernetwork analysis, it is well known that the origin-destination (O-D) flow table of a subnetwork is not only determined by trip generation and distribution, but also a result from traffic routing and diversion, due to the existence of internal-external, external-internal and external-external flows. This result indicates the variable nature of subnetwork O-D flows. This paper discusses an elastic O-D flow table estimation problem for subnetwork analysis. The underlying assumption is that each cell of the subnetwork O-D flow table contains an elastic demand function rather than a fixed demand rate and the demand function can capture all traffic diversion effect under various network changes. We propose a combined maximum entropy-least squares estimator, by which O-D flows are distributed over the subnetwork in terms of the maximum entropy principle, while demand function parameters are estimated for achieving the least sum of squared estimation errors. While the estimator is powered by the classic convex combination algorithm, computational difficulties emerge within the algorithm implementation until we incorporate partial optimality conditions and a column generation procedure into the algorithmic framework. Numerical results from applying the combined estimator to a couple of subnetwork examples show that an elastic O-D flow table, when used as input for subnetwork flow evaluations, reflects network flow changes significantly better than its fixed counterpart.     

High-resolution numerical relaxation approximations to second-order macroscopic traffic flow models

A novel numerical approach for the approximation of several, widely applied, macroscopic traffic flow models is presented. A relaxation-type approximation of second-order non-equilibrium models, written in conservation or balance law form, is considered. Using the relaxation approximation, the nonlinear equations are transformed to a semi-linear diagonilizable problem with linear characteristic variables and stiff source terms. To discretize the resulting relaxation system, low- and high-resolution reconstructions in space and implicit–explicit Runge–Kutta time integration schemes are considered. The family of spatial discretizations includes a second-order MUSCL scheme and a fifth-order WENO scheme, and a detailed formulation of the scheme is presented. Emphasis is given on the WENO scheme and its performance for solving the different traffic models. To demonstrate the effectiveness of the proposed approach, extensive numerical tests are performed for the different models. The computations reported here demonstrate the simplicity and versatility of relaxation schemes as solvers for macroscopic traffic flow models.     

Analysis of the optimal length of road expansion – A case study of the Taipei metropolitan area

This study explores the optimal investment in the length of an expanded section of road to mitigate the congestion on a transportation corridor. It is assumed that one end of the road is in the central business district (CBD) and that the households are uniformly distributed along the road. Each individual makes trips from his/her residence to the CBD. Trip demand is elastic and depends on the cost of the trip (including congestion costs). During the first stage, the government determines the length of the expanded section given the width of that section. In the second stage, road users determine their trip demands by taking into consideration the trip cost function. In the process of solving this problem, the equilibrium traffic volume is first solved using differential equations. The optimal length of the expanded section is then solved by maximizing the social welfare. The analysis is then applied to the case of the Tucheng city – Banciao city – Taipei CBD corridor in the Taipei metropolitan area. The scheme of road expansion without tolling performs closely to the first-best scheme for the case of a high potential demand. This study’s approach can serve as valuable reference for city planners engaged in road planning in a transportation corridor between the CBD and satellite cities in a metropolitan area.     

Modeling and optimization of multimodal urban networks with limited parking and dynamic pricing

Cruising-for-parking constraints mobility in urban networks. Car-users may have to cruise for on-street parking before reaching their destinations. The accessibility and the cost of parking significantly influence people's travel behavior (such as mode choice, or parking facility choice between on-street and garage). The cruising flow causes delays eventually to everyone, even users with destinations outside limited parking areas. It is therefore important to understand the impact of parking limitation on mobility, and to identify efficient parking policies for travel cost reduction. Most existing studies on parking fall short in reproducing the dynamic spatiotemporal features of traffic congestion in general, lack the treatment of dynamics of the cruising-for-parking phenomenon, or require detailed input data that are typically costly and difficult to collect. In this paper, we propose an aggregated and dynamic approach for modeling multimodal traffic with the treatment on parking, and utilize the approach to design dynamic parking pricing strategies. The proposed approach is based on the Macroscopic Fundamental Diagram (MFD), which can capture congestion dynamics at network-level for single-mode and bi-modal (car and bus) systems. A parsimonious parking model is integrated into the MFD-based multimodal modeling framework, where the dynamics of vehicular and passenger flows are considered with a change in the aggregated behavior (e.g. mode choice and parking facility choice) caused by cruising and congestion. Pricing strategies are developed with the objective of reducing congestion, as well as lowering the total travel cost of all users. A case study is carried out for a bi-modal city network with a congested downtown region. An elegant feedback dynamic parking pricing strategy can effectively reduce travel delay of cruising and the generic congestion. Remarkably, such strategy, which is applicable in real-time management with limited available data, is fairly as efficient as a dynamic pricing scheme obtained from system optimum conditions and a global optimization with full information about the future states of the system. Stackelberg equilibrium is also investigated in a competitive behavior between different parking facility operators. Policy indications on on-street storage capacity management and pricing are provided.     

Link choice proportions from trip distribution and assignment models: An overview and comparison

A number of estimation procedures have been suggested for the situation where a prior estimate of an origin-destination matrix is to be updated on the basis of recently-acquired traffic counts. These procedures assume that both the link flows and the proportionate usage of each link made by each origin-destination flow (referred to collectively as the link choice proportions) are known. This paper examines the possibility and methods for estimating the link choice proportions. Three methods are presented: (1) using ad hoc iteration between trip distribution and traffic assignment; (2) combining trip distribution and assignment in one step; (3) solving a new optimization problem in which the path flows are directly considered as variables and its optimal solution is governed by a logit type formula. The algorithms, covergencies and computational efficiencies of these methods are investigated. Results of testing the three methods on example networks are discussed.     

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.     

On the modeling and solution algorithm for the reverse logistics recycling flow equilibrium problem

This paper presents a study that characterizes, formulates, and solves the reverse logistic recycling flow equilibrium (RLRFE) problem. The RLRFE problem is concerned with the recycling channel in which recyclable collectors, processors, landfills, and demand markets form a multi-tiered network to process the recycled material flows from sources destined either for landfills or demand markets. Motivated by a government policy making or enterprise conglomerate recycling system design and operation needs, the RLRFE problem is elaborated from a system-optimal perspective using the variational inequality (VI) approach. For each origin–destination (OD) pair, the corresponding equilibrium conditions are established as a variation of the Wardrop second principle. In light of demand and cost function interactions, a nested diagonalization solution (ND) algorithm is proposed that gradually transforms the RLRFE problem into a traffic assignment model. To address multiple landfills in the recycling network and to understand how a variable-demand problem can be analyzed as a fixed-demand problem, we propose a supernetwork representation of the RLRFE problem. A numerical analysis on a test case illustrates the model formulation and the proposed algorithm.     

A novel traffic signal control formulation

A novel traffic signal control formulation is developed through a mixed integer programming technique. The formulation considers dynamic traffic, uses dynamic traffic demand as input, and takes advantage of a convergent numerical approximation to the hydrodynamic model of traffic flow. As inherent from the underlying hydrodynamic model, this formulation covers the whole range of the fundamental relationships between speed, flow, and density. Kinematic waves of the stop-and-go traffic associated with traffic signals are also captured. Because of this property, one does not need to tune or switch the model for the different traffic conditions. It “automatically” adjusts to the different traffic conditions. We applied the model to three demand scenarios in a simple network. The results seemed promising. This model produced timing plans that are consistent with models that work for unsaturated conditions. In gridlock conditions, it produced a timing plan that was better than conventional queue management practices.