Skip to main content
main-content

Über dieses Buch

Intelligent Vehicle-Highway Systems are providing a welcome stimulus to research on dynamic urban transportation network models. This book presents a new generation of models for solving dynamic travel choice problems including traveler's destination choice, mode choice, departure/arrival time choice and route choice. These models are expected to function as off-line travel forecasting and evaluation tools, and eventually as on-line prediction and control models in advanced traveler information and traffic management systems. In addition to a rich set of new formulations and solution algorithms, the book provides a summary of the necessary mathematical background and concludes with a discussion of the requirements for model implementation.

Inhaltsverzeichnis

Frontmatter

Dynamic Transportation Network Analysis

Chapter 1. Introduction

Abstract
Intelligent Vehicle Highway Systems (IVHS) seek to apply advanced computer, telecommunication, and information technologies to vehicles, transportation networks and operational plans, in order to relieve traffic congestion, reduce travelers’ journey times, improve safety, reduce atmospheric emissions and energy consumption, and increase the productivity of transportation investment. Using IVHS technologies, vehicles and the infrastructure will exchange vast amounts of data back and forth, making possible the warning and avoidance of congestion or hazardous conditions, the automatic collection of tolls, the efficient dispatching of trucks and buses, dramatic improvements in safety and other benefits.
Bin Ran, David E. Boyce

Mathematical Background

Chapter 2. Continuous Optimal Control Problems

Abstract
Optimal control theory has been extensively used in solving many engineering problems, such as in mechanical engineering and aeronautics engineering. Its application in transportation engineering has been limited to traffic signal control on surface streets and ramp metering control on freeways. Recently, with the rapid advance of supercomputing facilities and techniques, solution of optimal control theory formulations of large-scale problems has become feasible. Therefore, the application of this approach to dynamic transportation network modeling is attractive. The objective of conventional optimal control theory is to determine optimal control strategies that will cause a process to satisfy the physical constraints and at the same time minimize or maximize some performance criterion. In this book, we will use optimal control theory to formulate and analyze time-dependent transportation network problems. Those optimal control models have many similarities with the optimization models for solving static counterparts of these problems which are formulated and solved using nonlinear programming theory.
Bin Ran, David E. Boyce

Chapter 3. Discrete Optimal Control, Mathematical Programming and Variational Inequality Problems

Abstract
In this chapter, we present more mathematical background which is necessary for modeling and solution of dynamic transportation network problems. This chapter will cover discrete optimal control, mathematical programming and variational inequality problems. First, we introduce the discrete optimal control problem (OCP). To simplify our presentation, we consider discrete optimal control problems with fixed end times as examples in Section 3.1. The discussion is focused on the analysis of optimality conditions. Then, some mathematical programming (MP) problems are presented in Section 3.2. Specifically, nonlinear programming (NLP) problems with equality and nonnegativity constraints are presented for comparison. Similarities between discrete optimal control problems and mathematical programming are emphasized.
Bin Ran, David E. Boyce

Deterministic Dynamic Route Choice

Chapter 4. Network Flow Constraints and Definitions of Travel Times

Abstract
In this chapter, the constraints for dynamic traffic necessary for a urban transportation network are presented. These constraints include flow conservation for links and nodes, flow propagation, first-in-first-out (FIFO) and oversaturation. Associated with these constraints and different needs for dynamic travel time information, two definitions of travel time are considered.
Bin Ran, David E. Boyce

Chapter 5. Instantaneous Dynamic User-Optimal Route Choice Models

Abstract
In this chapter, we discuss optimal control models for instantaneous dynamic user-optimal route choice problems. Using a network with two parallel routes, we first present an example to illustrate the instantaneous dynamic user-optimal concept in Section 5.1. The general definition of instantaneous dynamic useroptimal state is given in Section 5.2. Then, we present three instantaneous dynamic user-optimal route choice models. Model 1 is described in Section 5.3. In Section 5.4, the equivalence of Model 1 with DUO route choice is demonstrated by proving the equivalence of the first order necessary conditions of the model with the instantaneous DUO route choice conditions. In Section 5.5, the second DUO model employing a different link travel time function assumption is formulated, and the equivalence of Model 2 with the instantaneous DUO route choice conditions is also demonstrated. In Section 5.6, the third instantaneous DUO model employing a simpler link travel time function assumption is formulated, and its equivalence with the instantaneous DUO conditions is also demonstrated. Finally, we present a discrete-time numerical example indicating that this class of models yields realistic results.
Bin Ran, David E. Boyce

Chapter 6. A Computational Algorithm for Instantaneous Dynamic User-Optimal Route Choice Models

Abstract
In this chapter, solution algorithms are considered for solving the instantaneous DUO route choice models presented in Chapter 5. A capability to solve the DUO route choice problem is needed for several reasons. First, it appears that properties of alternative models can only be fully understood by computing solutions to hypothetical and real test problems. Unlike their static counterparts, dynamic models are sufficiently opaque that they are difficult to understand analytically. Second, computational solutions for standard test problems based on actual networks are needed to evaluate how well alternative models describe reality. Third, solutions for large networks are required to evaluate the potential effectiveness of proposed in-vehicle navigation and route guidance systems. Ultimately, such models might be used to guide the operation of such systems; however, the requirements of such systems are so undefined at this time that any discussion of algorithmic requirements is highly speculative.
Bin Ran, David E. Boyce

Chapter 7. An Ideal Dynamic User-Optimal Route Choice Model

Abstract
In this chapter, we present an ideal dynamic user-optimal route choice model for a network with multiple origin-destination pairs. The model extends our previous instantaneous DUO route choice model in an important respect: route equilibrium is based on actual travel times rather than instantaneous travel times at the time of the choice. In Section 7.1, additional network flow constraints and the definition of ideal DUO state are presented. The equivalent equality constraints of the ideal DUO route choice conditions are developed in Section 7.2. Then, an optimal control formulation of the travel-time-based ideal DUO route choice problem is presented in Section 7.3. In Section 7.4, this model is reformulated as a discrete time NLP. Subsequently, penalty and diagonalization/Frank-Wolfe methods are suggested to solve this NLP.
Bin Ran, David E. Boyce

Stochastic Dynamic Route Choice

Chapter 8. Stochastic Dynamic User-Optimal Route Choice Models

Abstract
Dynamic route guidance systems are being developed in order to inform and guide drivers regarding their best departure times and routes so as to avoid congestion delay. However, drivers may or may not rely on the information provided by the route guidance system to adjust their departure times and routes. Furthermore, drivers without navigation systems do not have perfect information on the network traffic and must use their own experience and perception of current traffic conditions to make travel decisions. Thus, there is a need to develop dynamic route choice models under imperfect information as well as perfect information.
Bin Ran, David E. Boyce

Chapter 9. Solution Algorithms for Stochastic Dynamic User-Optimal Route Choice Models

Abstract
Chapter 8 described two logit-type SDUO route choice models which are stochastic generalizations of deterministic dynamic user-optimal route choice models previously presented in Chapters 5 and 7. To solve these models for large networks, we need to develop solution algorithms avoiding route enumeration. Thus, the stochastic dynamic network algorithms in this chapter are link-based procedures that avoid route enumeration and perform dynamic assignments using only link and node variables. Some new notation is presented in Section 9.1. In Sections 9.2 and 9.3, two multiple-route dynamic route choice algorithms (DYNASTOCH) similar to Dial’s efficient-route algorithm (STOCH) are suggested to solve two discrete-time flow-independent instantaneous and ideal SDUO route choice models. Then, the discrete formulation of the flowdependent instantaneous SDUO route choice model is presented in Section 9.4 and a solution algorithm is presented to solve this model. In Section 9.5, the discrete formulation of ideal SDUO route choice model is presented and a solution algorithm is also proposed. In both solution algorithms for the flow-dependent SDUO route choice models, the DYNASTOCH algorithms are used to solve their subproblems so that explicit route enumeration can be avoided. The method of successive averages (MSA) and other methods are suggested to solve the one-dimensional search problems. Numerical examples are presented in Section 9.6 to illustrate the solution of the proposed algorithms.
Bin Ran, David E. Boyce

General Dynamic Travel Choices

Chapter 10. Combined Departure Time/Route Choice Models

Abstract
A dynamic route guidance system seeks to improve the utilization of transportation network capacity and reduce travel times, congestion and the effect of incidents. Provided with early detection of incidents and congestion, users of the system will be able to choose alternative routes, if there is excess capacity in the network, or shift their departure times to avoid congestion when no road capacity is available.
Bin Ran, David E. Boyce

Chapter 11. Combined Departure Time/Mode/Route Choice Models

Abstract
We consider the efficient operation of an integrated transportation system within an IVHS environment. A dynamic route guidance system would improve utilization of the overall capacity of the transportation system so as to reduce travel times, congestion and incidents. By providing early detection of incidents and congestion in the transportation network, the route guidance system would redistribute traffic among the available modes and routes when there is excess capacity in some parts of the road network or shift the departure times of travelers to avoid peak-hour congestion when no additional road capacity is available. Furthermore, the route guidance system would provide travelers with accurate, current information on both transit and road networks so that some motorists could make their own time-cost tradeoffs and shift to transit, if appropriate.
Bin Ran, David E. Boyce

Variational Inequality Models

Chapter 12. Variational Inequality Models of Instantaneous Dynamic User-Optimal Route Choice Problems

Abstract
In this chapter, we present several variational inequality (VI) models for instantaneous dynamic user-optimal route choice problems for a network with multiple origin-destination pairs. In Section 12.1, a route-time-based VI model is first proposed. The equivalence of the VI model with the route-time-based instantaneous DUO route choice conditions is demonstrated. In order to generalize this route-based model, travelers are stratified into several groups and a multi-group route-cost-based VI model is developed in Section 12.2.
Bin Ran, David E. Boyce

Chapter 13. Variational Inequality Models of Ideal Dynamic User-Optimal Route Choice Problems

Abstract
In this chapter, we present both route-based and link-based variational inequality models for the ideal dynamic user-optimal route choice problem. In Section 13.1, a route-time-based VI model for ideal DUO route choice is proposed. This model is the most straight-forward formulation of route-time-based, ideal DUO route choice conditions. In Section 13.2, a multi-group route-time-based VI model is developed. In this model, each group of travelers is associated with a disutility function. Thus, the route-based ideal DUO route choice conditions are defined for each group of travelers on the basis of travel disutilities instead of travel times only.
Bin Ran, David E. Boyce

Chapter 14. Variational Inequality Models of Dynamic Departure Time/Route Choice Problems

Abstract
In this chapter, we consider an ideal situation where all travelers are equipped with navigation devices and fully comply with the dynamic user-optimal criterion when choosing routes, departure times and modes. We first present a dynamic, user-optimal departure time/route choice model for a general network with multiple origin-destination pairs. We model this choice problem by specifying that a given number of travelers are ready for departure between each origin-destination pair at time 0. However, their departure times may be delayed to reduce their overall travel costs. A route-based variational inequality model for joint departure time/route choice is presented in Section 14.1. In a parallel fashion, a link-based variational inequality model is proposed in Section 14.2. The relationship between the variational inequality models and the optimization models is discussed in Section 14.3.
Bin Ran, David E. Boyce

Chapter 15. Dynamic System-Optimal Route Choice and Congestion Pricing

Abstract
In this chapter, we present several dynamic system-optimal (DSO) route choice models for a network with multiple origin-destination pairs. The constraint set for DSO route choice models can be much more comprehensive, including constraints such as the capacity and oversaturation spillback constraints. However, the more constraints we have, the more difficult will be the solution algorithm. Thus, for large-scale networks, we need to make a trade-off between the reality of formulations and the difficulty of the solution algorithm. The modeling complexity can be pursued as long as realistic traffic flows can be fully represented and reasonable computational times can be achieved.
Bin Ran, David E. Boyce

Implications for IVHS

Chapter 16. Link Travel Time Functions for Dynamic Network Models

Abstract
Extensive resèarch has occurred in recent years on dynamic transportation network models, and especially on dynamic route choice models; these models have important applications in future ATIS and ATMS systems. However, most of the existing models lack a basis in traffic engineering. A significant problem for dynamic route choice is that the traditional BPR (Bureau of Public Roads, the predecessor of the Federal Highway Administration, U.S. DOT) volume-delay function is not applicable to a time-dependent traffic network. Meanwhile, since no proper dynamic link travel time functions exist, current dynamic route choice models assume various functional forms which are either too abstract or cannot provide realistic travel time estimates, even for a small network. Thus, it is becoming increasingly urgent to develop a set of timedependent link travel time functions for dynamic route choice problems.
Bin Ran, David E. Boyce

Chapter 17. Implementation in IVHS

Abstract
The rapid evolution of IVHS technologies presents more and more specific requirements for dynamic network modeling. Conversely, implementation of dynamic models is becoming more and more important for the design and evaluation of IVHS. In Section 17.1, several applications of dynamic models to IVHS components are discussed. We mainly investigate the technical aspects of applying these models. Subsequently, we discuss various data requirements for implementing these dynamic models in Section 17.2.
Bin Ran, David E. Boyce

Backmatter

Weitere Informationen