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.     

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.     

Surrogate‐based optimization of cordon toll levels in congested traffic networks

The benefit, in terms of social surplus, from introducing congestion charging schemes in urban networks is depending on the design of the charging scheme. The literature on optimal design of congestion pricing schemes is to a large extent based on static traffic assignment, which is known for its deficiency in correctly predict travel times in networks with severe congestion. Dynamic traffic assignment can better predict travel times in a road network, but are more computational expensive. Thus, previously developed methods for the static case cannot be applied straightforward. Surrogate‐based optimization is commonly used for optimization problems with expensive‐to‐evaluate objective functions. In this paper, we evaluate the performance of a surrogate‐based optimization method, when the number of pricing schemes, which we can afford to evaluate (because of the computational time), are limited to between 20 and 40. A static traffic assignment model of Stockholm is used for evaluating a large number of different configurations of the surrogate‐based optimization method. Final evaluation is performed with the dynamic traffic assignment tool VisumDUE, coupled with the demand model Regent, for a Stockholm network including 1240 demand zones and 17 000 links. Our results show that the surrogate‐based optimization method can indeed be used for designing a congestion charging scheme, which return a high social surplus. Copyright © 2016 John Wiley & Sons, Ltd.     

A dynamic stochastic assignment model for the analysis of general networks

The paper adopts the framework employed by the existing dynamic assignment models, which analyse specific network forms, and develops a methodology for analysing general networks. Traffic conditions within a link are assumed to be homogeneous, and the time varying O-D travel times and traffic flow patterns are calculated using elementary relationships from traffic flow theory and link volume conservation equations. Each individual is assumed to select a departure time and a route by trading off the travel time and schedule delay associated with each alternative. A route is considered as reasonable if it includes only links which do not take the traveller back to the origin. The set of reasonable routes is not consistant but depends on the time that an individual decides to depart from his origin. Equilibrium distributions are derived from a Markovian model which describes the evolution of travel patterns from day to day. Numerical simulation experiments are conducted to analyse the impact of different work start time flexibilities on the time dependent travel patterns. The similarity between link flows and travel times obtained from static and dynamic stochastic assignment is investigated. It is shown that in congested networks the application of static assignment results in travel times which are lower than the ones predicted by dynamic assignment.     

Multimodal,multiclass stochastic dynamic traffic assignment for evaluating information provision strategies

A multimodal, multiclass stochastic dynamic traffic assignment model was developed to evaluate pre‐trip and enroute travel information provision strategies. Three different information strategies were examined: user optimum [UO], system optimum [SO] and mixed optimum [MO]. These information provision strategies were analyzed based on the levels of traffic congestion and market penetration rate for the information equipment. Only two modes, bus and car, were used for evaluating and calculating the modal split ratio. Several scenarios were analyzed using day‐to‐day and within day dynamic models. From the results analyzed, it was found that when a traffic manager provides information for drivers using the UO strategy and drivers follow the provided information absolutely, the total travel time may increases over the case with no information. Such worsening occurs when drivers switch their routes and face traffic congestion on the alternative route. This phenomenon is the 'Braess Paradox'.     

Traffic assignment considering air quality

This paper presents a methodology of assigning traffic in a network with the consideration of air quality. Traffic assignment is formulated as an optimization problem considering travel cost and on-road emissions. It introduces a cell-based approach to model emission concentrations so that either the average or maximum emissions in a network can be considered in the optimization process. The emissions in a cell are modeled taking into consideration the influence of the emission sources from all cells in the network. A case study demonstrates that minimizing travel cost and reducing air pollutants may not be always achieved simultaneously. The traffic assignment procedure can effectively reduce emission concentrations at those locations with the worst air quality conditions, with only a marginal increase in travel time and average emission concentration in the network.     

Evaluating commuter opinion of congestion pricing in metropolitan Seattle

Continued growth and development in the Puget Sound region combined with existing geographic limitations have resulted in a transportation network that is at or near capacity for many hours during every weekday. Single‐occupancy vehicles (SOVs) remain the predominant mode of travel, despite a network of high‐occupancy vehicle lanes and regional transit. Given this situation, considering alternative methods to regulate traffic flow is necessary, and the implementation of a regional congestion pricing system is one such option. Although widespread throughout the world, congestion pricing has only recently been implemented in the United States.     

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.     

Microsimulation models incorporating both demand and supply dynamics

There has been rapid growth in interest in real-time transport strategies over the last decade, ranging from automated highway systems and responsive traffic signal control to incident management and driver information systems. The complexity of these strategies, in terms of the spatial and temporal interactions within the transport system, has led to a parallel growth in the application of traffic microsimulation models for the evaluation and design of such measures, as a remedy to the limitations faced by conventional static, macroscopic approaches. However, while this naturally addresses the immediate impacts of the measure, a difficulty that remains is the question of how the secondary impacts, specifically the effect on route and departure time choice of subsequent trips, may be handled in a consistent manner within a microsimulation framework.The paper describes a modelling approach to road network traffic, in which the emphasis is on the integrated microsimulation of individual trip-makers’ decisions and individual vehicle movements across the network. To achieve this it represents directly individual drivers’ choices and experiences as they evolve from day-to-day, combined with a detailed within-day traffic simulation model of the space–time trajectories of individual vehicles according to car-following and lane-changing rules and intersection regulations. It therefore models both day-to-day and within-day variability in both demand and supply conditions, and so, we believe, is particularly suited for the realistic modelling of real-time strategies such as those listed above. The full model specification is given, along with details of its algorithmic implementation. A number of representative numerical applications are presented, including: sensitivity studies of the impact of day-to-day variability; an application to the evaluation of alternative signal control policies; and the evaluation of the introduction of bus-only lanes in a sub-network of Leeds. Our experience demonstrates that this modelling framework is computationally feasible as a method for providing a fully internally consistent, microscopic, dynamic assignment, incorporating both within- and between-day demand and supply dynamics.     

Route swapping in dynamic traffic networks

A dynamic traffic assignment (DTA) model typically consists of a traffic performance model and a route choice model. The traffic performance model describes how traffic propagates (over time) along routes connecting origin-destination (OD) pairs, examples being the cell transmission model, the vertical queueing model and the travel time model. This is implemented in a dynamic network loading (DNL) algorithm, which uses the given route inflows to compute the link inflows (and hence link costs), which are then used to compute the route travel times (and hence route costs). A route swap process specifies the route inflows for tomorrow (at the next iteration) based on the route inflows today (at the current iteration). A dynamic user equilibrium (DUE), where each traveller on the network cannot reduce his or her cost of travel by switching to another route, can be sought by iterating between the DNL algorithm and the route swap process. The route swap process itself takes up very little computational time (although route set generation can be very computationally intensive for large networks). However, the choice of route swap process dramatically affects convergence and the speed of convergence. The paper details several route swap processes and considers whether they lead to a convergent system, assuming that the route cost vector is a monotone function of the route inflow vector.     

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.     

The optimization of lane assignment and signal timing at the tandem intersection with pre‐signal

This paper presents an integrated model for optimizing lane assignment and signal timing at tandem intersection, which is introduced recently. The pre‐signal is utilized in the tandem intersection to reorganize the traffic flow; hence, the vehicles, regardless of whether left‐turns or through vehicles, can be discharged in all the lanes. However, the previous work does not consider the extra traffic disruption and the associated delay caused by the additional pre‐signal. In the paper, the extra delay aroused by the coordination is incorporated in a lane assignment and signal timing optimization model, and the problem is converted into a mixed‐integer non‐linear programming. A feasible directions method is hence introduced to solve the mixed‐integer non‐linear programming. The result of the optimization shows that the performance of the tandem intersection is improved and the average delay is minimized. The comparison between the tandem and the conventional configuration is presented, and the results verify that the former shows better performance than the latter. In addition, the optimal sequence corresponding to the turning proportion and the optimal lane assignment at the upstream approach of the pre‐signal are presented. Furthermore, if the number of lanes is equal in all arms, the paper proves that the average delay will be reduced if lane assignment is proportional to the turning proportion and the vehicles with low proportion are discharged in advance. Copyright © 2013 John Wiley & Sons, Ltd.     

A model for assessing the effects of dynamic travel time information via variable message signs

In view of the serious traffic congestion during peak hours in most metropolitan areas around the world and recent improvement of information technology, there is a growing aspiration to alleviate road congestion by applications of electronic information and communication technology. Providing drivers with dynamic travel time information such as estimated journey times on major routes should help drivers to select better routes and guide them to utilise existing expressway network. This can be regarded as one possible strategy for effective traffic management. This paper aims to investigate the effects and benefits of providing dynamic travel time information to drivers via variable message signs at the expressway network. In order to assess the effects of the dynamic driver information system with making use of the variable message signs, a time-dependent traffic assignment model is proposed. A numerical example is used to illustrate the effects of the dynamic travel time information via variable message signs. This revised version was published online in June 2006 with corrections to the Cover Date.     

Path-constrained traffic assignment: A trip chain analysis under range anxiety

This paper proposes and analyzes a distance-constrained traffic assignment problem with trip chains embedded in equilibrium network flows. The purpose of studying this problem is to develop an appropriate modeling tool for characterizing traffic flow patterns in emerging transportation networks that serve a massive adoption of plug-in electric vehicles. This need arises from the facts that electric vehicles suffer from the “range anxiety” issue caused by the unavailability or insufficiency of public electricity-charging infrastructures and the far-below-expectation battery capacity. It is suggested that if range anxiety makes any impact on travel behaviors, it more likely occurs on the trip chain level rather than the trip level, where a trip chain here is defined as a series of trips between two possible charging opportunities (Tamor et al., 2013). The focus of this paper is thus given to the development of the modeling and solution methods for the proposed traffic assignment problem. In this modeling paradigm, given that trip chains are the basic modeling unit for individual decision making, any traveler’s combined travel route and activity location choices under the distance limit results in a distance-constrained, node-sequenced shortest path problem. A cascading labeling algorithm is developed for this shortest path problem and embedded into a linear approximation framework for equilibrium network solutions. The numerical result derived from an illustrative example clearly shows the mechanism and magnitude of the distance limit and trip chain settings in reshaping network flows from the simple case characterized merely by user equilibrium.     

Network-wide adaptive tolling for connected and automated vehicles

This article proposes Δ-tolling, a simple adaptive pricing scheme which only requires travel time observations and two tuning parameters. These tolls are applied throughout a road network, and can be updated as frequently as travel time observations are made. Notably, Δ-tolling does not require any details of the traffic flow or travel demand models other than travel time observations, rendering it easy to apply in real-time. The flexibility of this tolling scheme is demonstrated in three specific traffic modeling contexts with varying traffic flow and user behavior assumptions: a day-to-day pricing model using static network equilibrium with link delay functions; a within-day adaptive pricing model using the cell transmission model and dynamic routing of vehicles; and a microsimulation of reservation-based intersection control for connected and autonomous vehicles with myopic routing. In all cases, Δ-tolling produces significant benefits over the no-toll case, measured in terms of average travel time and social welfare, while only requiring two parameters to be tuned. Some optimality results are also given for the special case of the static network equilibrium model with BPR-style delay functions.     

The treatment of uncertainty in the dynamic origin–destination estimation problem using a fuzzy approach

Regardless of existing types of transportation and traffic model and their applications, the essential input to these models is travel demand, which is usually described using origin–destination (OD) matrices. Due to the high cost and time required for the direct development of such matrices, they are sometimes estimated indirectly from traffic measurements recorded from the transportation network. Based on an assumed demand profile, OD estimation problems can be categorized into static or dynamic groups. Dynamic OD demand provides valuable information on the within-day fluctuation of traffic, which can be employed to analyse congestion dissipation. In addition, OD estimates are essential inputs to dynamic traffic assignment (DTA) models. This study presents a fuzzy approach to dynamic OD estimation problems. The problems are approached using a two-level model in which demand is estimated in the upper level and the lower level performs DTA via traffic simulation. Using fuzzy rules and the fuzzy C-Mean clustering approach, the proposed method treats uncertainty in historical OD demand and observed link counts. The approach employs expert knowledge to model fitted link counts and to set boundaries for the optimization problem by defining functions in the fuzzification process. The same operation is performed on the simulation outputs, and the entire process enables different types of optimization algorithm to be employed. The Box-complex method is utilized as an optimization algorithm in the implementation of the approach. Empirical case studies are performed on two networks to evaluate the validity and accuracy of the approach. The study results for a synthetic network and a real network demonstrate the robust performance of the proposed method even when using low-quality historical demand data.     

A dynamic evacuation model for pedestrian–vehicle mixed-flow networks

In urban emergency evacuation, a potentially large number of evacuees may depend either on transit or other modes, or need to walk a long distance, to access their passenger cars. In the process of approaching the designated pick-up points or parking areas for evacuation, the massive number of pedestrians may cause tremendous burden to vehicles in the roadway network. Responsible agencies often need to contend with congestion incurred by massive vehicles emanating from parking garages, evacuation buses generated from bus stops, and the conflicts between evacuees and vehicles at intersections. Hence, an effective plan for such evacuation needs to concurrently address both the multi-modal traffic route assignment and the optimization of network signal controls for mixed traffic flows. This paper presents an integrated model to produce the optimal distribution of vehicle and pedestrian flows, and the responsive network signal plan for massive mixed pedestrian–vehicle flows within the evacuation zone. The proposed model features its effectiveness in accounting for multiple types of evacuation vehicles, the interdependent relations between pedestrian and vehicle flows via some conversion locations, and the inevitable conflicts between intersection turning vehicle and pedestrian flows. An illustrating example concerning an evacuation around the M&T stadium area has been presented, and the results indicate the promising properties of our proposed model, especially on reflecting the complex interactions between vehicle and pedestrian flows and the favorable use of high-occupancy vehicles for evacuation operations.     

The impacts of connected vehicle technology on network-wide traffic operation and fuel consumption under various incident scenarios

ABSTRACT

Incidents are a major source of traffic congestion and can lead to long and unpredictable delays, deteriorating traffic operations and adverse environmental impacts. The emergence of connected vehicles and communication technologies has enabled travelers to use real-time traffic information. The ability to exchange traffic information among vehicles has tremendous potential impacts on network performance especially in the case of non-recurrent congestion. To this end, this paper utilizes a microscopic simulation model of traffic in El Paso, Texas to investigate the impacts of incidents on traffic operation and fuel consumption at different market penetration rates (MPR) of connected vehicles. Several scenarios are implemented and tested to determine the impacts of incidents on network performance in an urban area. The scenarios are defined by changing the duration of incidents and the number of lanes closed. This study also shows how communication technology affects network performance in response to congestion. The results of the study demonstrate the potential effectiveness of connected vehicle technology in improving network performance. For an incident with a duration of 900?s and MPR of 80%, total fuel consumption and total travel time decreased by approximately 20%; 26% was observed in network-wide travel time and fuel consumption at 100% MPR.     

Dynamic traffic metering in urban street networks: Formulation and solution algorithm

Traffic metering offers great potential to reduce congestion and enhance network performance in oversaturated urban street networks. This paper presents an optimization program for dynamic traffic metering in urban street networks based on the Cell Transmission Model (CTM). We have formulated the problem as a Mixed-Integer Linear Program (MILP) capable of metering traffic at network gates with given signal timing parameters at signalized intersections. Due to the complexities of the MILP model, we have developed a novel and efficient solution approach that solves the problem by converting the MILP to a linear program and several CTM simulation runs. The solution algorithm is applied to two case studies under different conditions. The proposed solution technique finds solutions that have a maximum gap of 1% of the true optimal solution and guarantee the maximum throughput by keeping some vehicles at network gates and only allowing enough vehicles to enter the network to prevent gridlocks. This is confirmed by comparing the case studies with and without traffic metering. The results in an adapted real-world case study network show that traffic metering can increase network throughput by 4.9–38.9% and enhance network performance.     

Congestion-aware system optimal route choice for shared autonomous vehicles

We study the shared autonomous vehicle (SAV) routing problem while considering congestion. SAVs essentially provide a dial-a-ride service to travelers, but the large number of vehicles involved (tens of thousands of SAVs to replace personal vehicles) results in SAV routing causing significant congestion. We combine the dial-a-ride service constraints with the linear program for system optimal dynamic traffic assignment, resulting in a congestion-aware formulation of the SAV routing problem. Traffic flow is modeled through the link transmission model, an approximate solution to the kinematic wave theory of traffic flow. SAVs interact with travelers at origins and destinations. Due to the large number of vehicles involved, we use a continuous approximation of flow to formulate a linear program. Optimal solutions demonstrate that peak hour demand is likely to have greater waiting and in-vehicle travel times than off-peak demand due to congestion. SAV travel times were only slightly greater than system optimal personal vehicle route choice. In addition, solutions can determine the optimal fleet size to minimize congestion or maximize service.