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.     

Effects of queue spillover in networks considering simultaneous departure time and route choices

This paper explores the effects of queue spillover in transportation networks, in the context of dynamic traffic assignment. A model of spatial queue is defined to characterize dynamic traffic flow and queuing formation in network links. Network users simultaneously choose departure time and travel route to minimize the travel cost including journey time and unpunctuality penalty. Using some necessary conditions of the dynamic user equilibrium, dynamic network flows are obtained exactly on some networks with typical structure. Various effects of queue spillover are discussed based on the results of these networks, and some new paradoxes of link capacity expansion have been found as a result of such effects. Analytical and exact results in these typical networks show that ignoring queuing length may generate biased solutions, and the link storage capacity is a very important factor concerning the performance of networks.     

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.     

Routing aspects of electric vehicle drivers and their effects on network performance

This study investigates the routing aspects of battery electric vehicle (BEV) drivers and their effects on the overall traffic network performance. BEVs have unique characteristics such as range limitation, long battery recharging time, and recuperation of energy lost during the deceleration phase if equipped with regenerative braking system (RBS). In addition, the energy consumption rate per unit distance traveled is lower at moderate speed than at higher speed. This raises two interesting questions: (i) whether these characteristics of BEVs will lead to different route selection compared to conventional internal combustion engine vehicles (ICEVs), and (ii) whether such route selection implications of BEVs will affect the network performance. With the increasing market penetration of BEVs, these questions are becoming more important. This study formulates a multi-class dynamic user equilibrium (MCDUE) model to determine the equilibrium flows for mixed traffic consisting of BEVs and ICEVs. A simulation-based solution procedure is proposed for the MCDUE model. In the MCDUE model, BEVs select routes to minimize the generalized cost which includes route travel time, energy related costs and range anxiety cost, and ICEVs to minimize route travel time. Results from numerical experiments illustrate that BEV drivers select routes with lower speed to conserve and recuperate battery energy while ICEV drivers select shortest travel time routes. They also illustrate that the differences in route choice behavior of BEV and ICEV drivers can synergistically lead to reduction in total travel time and the network performance towards system optimum under certain conditions.     

Morning commute in a single-entry traffic corridor with no late arrivals

This paper analyzes a model of early morning traffic congestion, that is a special case of the model considered in Newell (1988). A fixed number of identical vehicles travel along a single-lane road of constant width from a common origin to a common destination, with LWR flow congestion and Greenshields’ Relation. Vehicles have a common work start time, late arrivals are not permitted, and trip cost is linear in travel time and time early. The paper explores traffic dynamics for the social optimum, in which total trip cost is minimized, and for the user optimum, in which no vehicle’s trip cost can be reduced by altering its departure time. Closed-form solutions for the social optimum and quasi-analytic solutions for the user optimum are presented, along with numerical examples, and it is shown that this model includes the bottleneck model (with no late arrivals) as a limit case where the length of the road shrinks to zero.     

An equilibrium analysis of commuter parking in the era of autonomous vehicles

This study is the first in the literature to model the joint equilibrium of departure time and parking location choices when commuters travel with autonomous vehicles (AVs). With AVs, walking from parking spaces to the work location is not needed. Instead, AVs will drop off the commuters at the workplace and then drive themselves to the parking spaces. In this context, the equilibrium departure/arrival profile is different from the literature with non-autonomous vehicles (non-AVs). Besides modeling the commuting equilibrium, this study further develops the first-best time-dependent congestion tolling scheme to achieve the system optimum. Also, a location-dependent parking pricing scheme is developed to replace the tolling scheme. Furthermore, this study discusses the optimal parking supply to minimize the total system cost (including both the travel cost and the social cost of parking supply) under either user equilibrium or system optimum traffic flow pattern. It is found that the optimal planning of parking can be different from the non-AV situation, since the vehicles can drive themselves to parking spaces that are further away from the city center and walking of commuters is avoided. This paper sheds light on future parking supply planning and traffic management.     

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.     

First-best marginal cost toll for a traffic network with stochastic demand

First-best marginal cost pricing (MCP) in traffic networks has been extensively studied with the assumption of deterministic travel demand. However, this assumption may not be realistic as a transportation network is exposed to various uncertainties. This paper investigates MCP in a traffic network under stochastic travel demand. Cases of both fixed and elastic demand are considered. In the fixed demand case, travel demand is represented as a random variable, whereas in the elastic demand case, a pre-specified random variable is introduced into the demand function. The paper also considers a set of assumptions of traveler behavior. In the first case, it is assumed that the traveler considers only the mean travel time in the route choice decision (risk-neutral behavior), and in the second, both the mean and the variance of travel time are introduced into the route choice model (risk-averse behavior). A closed-form formulation of the true marginal cost toll for the stochastic network (SN-MCP) is derived from the variational inequality conditions of the system optimum and user equilibrium assignments. The key finding is that the calculation of the SN-MCP model cannot be made by simply substituting related terms in the original MCP model by their expected values. The paper provides a general function of SN-MCP and derives the closed-form SN-MCP formulation for specific cases with lognormal and normal stochastic travel demand. Four numerical examples are explored to compare network performance under the SN-MCP and other toll regimes.     

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.     

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.     

Interactive travel choices and traffic forecast in a doubly dynamical system with user inertia and information provision

This study models the joint evolution (over calendar time) of travelers’ departure time and mode choices, and the resulting traffic dynamics in a bi-modal transportation system. Specifically, we consider that, when adjusting their departure time and mode choices, travelers can learn from their past travel experiences as well as the traffic forecasts offered by the smart transport information provider/agency. At the same time, the transport agency can learn from historical data in updating traffic forecast from day to day. In other words, this study explicitly models and analyzes the dynamic interactions between transport users and traffic information provider. Besides, the impact of user inertia is taken into account in modeling the traffic dynamics. When exploring the convergence of the proposed model to the dynamic bi-modal commuting equilibrium, we find that appropriate traffic forecast can help the system converge to the user equilibrium. It is also found that user inertia might slow down the convergence speed of the day-to-day evolution model. Extensive sensitivity analysis is conducted to account for the impacts of inaccurate parameters adopted by the transport agency.     

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.     

Simultaneous determination of the equilibrium market penetration and compliance rate of advanced traveler information systems

We consider a specific advanced traveler information systems (ATIS) whose objective is to reduce drivers’ travel time uncertainty with recurrent network congestion through provision of traffic information. Since the provided information is still partial or imperfect, drivers equipped with an ATIS cannot always find the shortest travel time route and thus may not always comply with the advice provided by ATIS. Thus, there are three classes of drivers on a specific day: drivers without ATIS, drivers with ATIS but without compliance with ATIS advice, drivers with ATIS and in compliance with ATIS advice. All three classes of drivers make route choice in a stochastic manner, but with different degree of uncertainty of travel time on the network. In this paper we investigate the interactions among the three classes of drivers in an ATIS environment using a multiple behavior stochastic user equilibrium model. By assuming that the market penetration of ATIS is an increasing function of the actual private gain (time saving minus the cost associated with system use) derived from ATIS service, and the ATIS compliance rate of equipped drivers is given as the probability of the actual travel time of complied drivers being less than that of non-complied drivers, we determine the equilibrium market penetration and compliance rate of ATIS and the resulting equilibrium network flow pattern using an iterative solution procedure.     

A discrete dynamical system of formulating traffic assignment: Revisiting Smith’s model

Through relaxing the behavior assumption adopted in Smith’s model (Smith, 1984), we propose a discrete dynamical system to formulate the day-to-day evolution process of traffic flows from a non-equilibrium state to an equilibrium state. Depending on certain preconditions, the equilibrium state can be equivalent to a Wardrop user equilibrium (UE), Logit-based stochastic user equilibrium (SUE), or boundedly rational user equilibrium (BRUE). These equivalence properties indicate that, to make day-to-day flows evolve to equilibrium flows, it is not necessary for travelers to choose their routes based on actual travel costs of the previous day. Day-to-day flows can still evolve to equilibrium flows provided that travelers choose their routes based on estimated travel costs which satisfy these preconditions. We also show that, under a more general assumption than the monotonicity of route cost function, the trajectory of the dynamical system converges to a set of equilibrium flows by reasonably setting these parameters in the dynamical system. Finally, numerical examples are presented to demonstrate the application and properties of the dynamical system. The study is helpful for understanding various processes of forming traffic jam and designing an algorithm for calculating equilibrium flows.     

A bi-objective user equilibrium model of travel time reliability in a road network

Travel time, travel time reliability and monetary cost have been empirically identified as the most important criteria influencing route choice behaviour. We concentrate on travel time and travel time reliability and review two prominent user equilibrium models incorporating these two factors. We discuss some shortcomings of these models and propose alternative bi-objective user equilibrium models that overcome the shortcomings. Finally, based on the observation that both models use standard deviation of travel time within their measure of travel time reliability, we propose a general travel time reliability bi-objective user equilibrium model. We prove that this model encompasses those discussed previously and hence forms a general framework for the study of reliability related user equilibrium. We demonstrate and validate our concepts on a small three-link example.     

Comparison of results of two models of transportation demand in Hong Kong: CDAM and a version of microTRIPS

CDAM is a new computer program for solving the combined trip distribution and assignment model for multiple user classes, which enables transport planners to estimate consistent Origin-Destination (O-D) matrices and equilibrium traffic flows simultaneously if the trip production and attraction of each user class at zone centroids are available. This paper reports an application of CDAM to the central Kowloon study area in Hong Kong. The coefficients of the model related to the components of generalized costs are calibrated on 1986 travel data. A comparison of results of CDAM and a version of MicroTRIPS models of transportation demand in Hong Kong are presented. Finally, some conclusions are drawn and the advantage of the CDAM are discussed.     

New technology and the modeling of risk-taking behavior in congested road networks

Intelligent transport systems provide various means to improve traffic congestion in road networks. Evaluation of the benefits of these improvements requires consideration of commuters’ response to reliability and/or uncertainty of travel time under various circumstances. Various disruptions cause recurrent or non-recurrent congestion on road networks, which make road travel times intrinsically fluctuating and unpredictable. Confronted with such uncertain traffic conditions, commuters are known to develop some simple decision-making process to adjust their travel choices. This paper represents the decision-making process involved in departure-time and route choices as risk-taking behavior under uncertainty. An expected travel disutility function associated with commuters’ departure-time and route choices is formulated with taking into account the travel delay (due the recurrent congestion), the uncertainty of travel times (due to incident-induced congestion) and the consequent early or late arrival penalty. Commuters are assumed to make decision on the departure-time and route choices on the basis of the minimal expected travel disutility. Thus the network will achieve a simultaneous route and departure-time user equilibrium, in which no commuter can decrease his or her expected disutility by unilaterally changing the route or departure-time. The equilibrium is further formulated as an equivalent nonlinear complementarity problem and is then converted into an unconstrained minimization problem with the use of a gap function suggested recently. Two algorithms based on the Nelder–Mead multidimensional simplex method and the heuristic route/time-swapping approach, are adapted to solve the problem. Finally, numerical example is given to illustrate the application of the proposed model and algorithms.     

Minimizing CO2e emissions by setting a road toll

The main purpose of this paper is to develop a bi-level pricing model to minimize the CO₂e emissions and the total travel time in a small road network. In the lower level of the model, it is assumed that users of the road network find a dynamic user equilibrium which minimizes the total costs of those in the system. For the higher level of the model, different road toll strategies are applied in order to minimize the CO₂e emissions. The model has been applied to an illustrative example. It shows the effects on traffic flows, revenues, total time and CO₂e emissions for different numbers of servers collecting tolls and different pricing strategies over a morning peak traffic period. The results show that the CO₂e emissions produced can be significantly affected by the number of servers and the type of toll strategy employed. The model is also used to find the best toll strategy when there is a constraint on the revenue that is required to be raised from the toll and how this affects the emissions produced. Further runs compare strategies to minimize the CO₂e emissions with those that minimize total travel time in the road system. In the illustrative example, the results for minimizing CO₂e emissions are shown to be similar to the results obtained from minimizing the total travel time.     

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.     

Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times

This paper presents a dynamic vehicle routing and scheduling model that incorporates real time information using variable travel times. Dynamic traffic simulation was used to update travel times. The model was applied to a test road network. Results indicated that the total cost decreased by implementing the dynamic vehicle routing and scheduling model with the real time information based on variable travel times compared with that of the forecast model. As well, in many cases total running times of vehicles were also decreased. Therefore, the dynamic vehicle routing and scheduling model will be beneficial for both carriers in reducing total costs and society at large by alleviating traffic congestion.