This book presents advanced research in a relatively new field of scholarly inquiry that is usually referred to as dynamic network user equilibrium, now almost universally abbreviated as DUE. It provides the first synthesis of results obtained over the last decade from applying the differential variational inequality (DVI) formalism to study the DUE problem. In particular, it explores the intimately related problem of dynamic network loading, which determines the arc flows and effective travel delays (or generalized travel costs) arising from the expression of departure rates at the origins of commuter trips between the workplace and home. In particular, the authors show that dynamic network loading with spillback of queues into upstream arcs may be formulated as a differential algebraic equation system. They demonstrate how the dynamic network loading problem and the dynamic traffic user equilibrium problem may be solved simultaneously rather than sequentially, as well as how the first-in-first-out queue discipline may be maintained for each when Lighthill-Whitham-Richardson traffic flow theory is used. A number of recent and new extensions of the DVI-based theory of DUE and corresponding examples are presented and discussed. Relevant mathematical background material is provided to make the book as accessible as possible.

lgli/1632.eee.pdf

lgrsnf/1632.eee.pdf

TERRY L.. HAN, KE FRIESZ

Springer Nature Switzerland AG

Complex networks and dynamic systems, S.l, 2023

Switzerland, Switzerland

{"isbns":["3031255623","9783031255625"],"source":"libgen_rs"}

Preface
Contents
1 Introduction
1.1 Introduction
1.2 Some DTA and DUE Literature
1.3 Vocabulary of DUE Modeling
1.4 Alternative Formulations of DUE
1.5 The Structure of DUE Models
1.6 Dynamic Network Loading Models
1.6.1 Vickrey's Model of a Traffic Bottleneck and Its Extension
1.6.2 Network Loading Based on Link Dynamics
1.6.3 Network Loading as a LWR-Based PDAE System
1.6.3.1 The Perakis-Kachani DNL Models
1.6.3.2 The Han-Friesz Within-Link Dynamicsfor DNL
1.6.4 Network Loading Based on the CTM
1.6.5 Network Loading Based on the Variational Approach
1.6.6 LWR Network Loading Based on Closed-Form Operators
1.6.7 Dynamic User Equilibrium in Continuous Time
1.6.8 Dynamic User Equilibrium in Discrete Time
1.7 Other Considerations in Classifying DUE Models
1.8 Unresolved/Partially Resolved Fundamental Challenges
References and Suggested Reading
2 Mathematical Preliminaries
2.1 Selected Topics in Functional Analysis
2.1.1 Hilbert Spaces
2.1.2 Topological Vector Spaces
2.1.3 Compactness
2.1.4 The Contraction Mapping Theorem
2.2 Nonlinear Programming
2.2.1 Nonlinear Program Defined
2.2.2 The Fritz John Conditions
2.2.3 The Kuhn-Tucker Conditions
2.2.4 Kuhn-Tucker Conditions Sufficient
2.2.5 Kuhn-Tucker Conditions for Variational Inequalities
2.3 Calculus of Variations
2.3.1 The Space C1[t0,tf]
2.3.2 The Concept of a Variation
2.4 Optimal Control
2.4.1 The State Operator
2.4.2 Necessary Conditions for Continuous-TimeOptimal Control
2.4.3 Sufficiency in Optimal Control
2.4.3.1 The Mangasarian Theorem
2.4.3.2 The Arrow Theorem
2.5 Differential Variational Inequalities
2.5.1 Problem Definition
2.5.2 Regularity Conditions for DIV
2.5.3 Necessary Conditions
2.6 Nash Games and Differential Nash Games
2.6.1 Nash Equilibria and Normal Form Games
2.6.2 Differential Nash Games and Differential Nash Equilibria
2.6.3 Generalized Differential Nash Equilibria
2.7 The Scalar Conservation Law
2.7.1 Definition and Examples of the Scalar Conservation Law
2.7.2 Characteristics, Shock Waves, and Weak Solutions
2.7.3 Non-uniqueness of Integral Solutions, EntropyConditions
2.8 The Hamilton-Jacobi Equations and the Variational Principle
2.8.1 The Hamilton-Jacobi Equation
2.8.2 The Variational Theory
2.8.2.1 The Classical Lax-Hopf Formula
2.8.2.2 The Generalized Lax-Hopf Formula
References and Suggested Reading
3 The Variational Inequality Formulation of Dynamic User Equilibria
3.1 Notation and Essential Background
3.2 The VI Formulation of DUE with Fixed Demand
3.2.1 Definition of DUE with Fixed Demand
3.2.2 Variational Inequality Problem Equivalent to DUE with Fixed Demand
3.3 The VI Formulation of DUE with Elastic Demand
3.3.1 Definition of DUE with Elastic Demand
3.3.2 Variational Inequality Problem Equivalent to DUE with Elastic Demand
3.4 The VI Formulation of Boundedly Rational DUE
3.4.1 Definition of DUE with Bounded Rationality
3.4.2 Variational Inequality Equivalent to BR-DUE with Exogenous or Endogenous Tolerances
3.5 Kuhn-Tucker Conditions for DUE Problems
3.5.1 Application to DUE with Fixed Demand
3.5.1.1 Kuhn-Tucker Conditions for Discrete-time DUE Problems with Fixed Demand
3.5.1.2 An Equivalent Linear System
3.5.2 Application to DUE with Elastic Demand
3.5.2.1 Kuhn-Tucker Conditions for Discrete-time DUE Problems with Elastic Demand
3.5.2.2 An Equivalent Linear System
References and Suggested Reading
4 The Differential Variational Inequality Formulation of Dynamic User Equilibria
4.1 DVI Formulation of DUE with Fixed Demand
4.2 Fixed-Point Problem Formulation of DUE with Fixed Demand
4.3 DVI Formulation of DUE with Elastic Demand
4.4 Fixed-Point Problem Formulation of DUE with Elastic Demand
4.5 DVI Formulation of DUE with Bounded Rationality
4.5.1 With Exogenous Tolerances (BR-DUE)
4.5.2 With Endogenous Tolerances (VT-BR-DUE)
4.6 Fixed-Point Problem Formulation of DUE with Bounded Rationality
4.6.1 With Exogenous Tolerances (BR-DUE)
4.6.2 With Endogenous Tolerances (VT-BR-DUE)
References and Suggested Reading
5 Existence of Dynamic User Equilibria
5.1 Existence of Dynamic User Equilibrium with Fixed Demand
5.1.1 Mathematical Preparation
5.1.2 Alternative Expression of the Effective Path Delay
5.1.3 The Existence Proof
5.2 Existence of Dynamic User Equilibrium with Elastic Demand
5.2.1 The Variational Inequality Formulation in an Extended Hilbert Space
5.2.2 The Existence Proof
5.3 An Example of Non-existence of DUE
5.4 Existence of Dynamic User Equilibrium with Bounded Rationality
5.4.1 Analytical Properties of the New Operator
5.4.2 The Existence Proof
5.5 Characterization of Solutions for Dynamic User Equilibrium with Bounded Rationality
5.5.1 Discrete-Time VT-BR-DUE Problem
5.5.2 Characterization of the Solution Set of VT-BR-DUE
5.5.3 Constructing Connected Subset of the Solution Set
References and Suggested Reading
6 Algorithms for Computing Dynamic User Equilibria
6.1 Fixed-Point Algorithm
6.1.1 Fixed-Point Algorithm for DUE with Fixed Demand
6.1.2 Fixed-Point Algorithm for DUE with Elastic Demand
6.1.3 Fixed-Point Algorithm for DUE with BoundedRationality
6.2 Self-adaptive Projection Algorithm
6.2.1 Self-adaptive Projection Algorithm for DUE with Fixed Demand
6.2.2 Self-adaptive Projection Algorithm for DUE with Elastic Demand
6.2.3 Self-adaptive Projection Algorithm for DUE with Bounded Rationality
6.3 Proximal Point Method
6.3.1 Proximal Point Method for DUE with Fixed Demand
6.3.2 Proximal Point Method for DUE with Elastic Demand
6.3.3 Proximal Point Method for DUE with BoundedRationality
6.4 Convergence of Algorithms
6.4.1 Convergence Result for the Fixed-Point Algorithm
6.4.1.1 A Generic Proof Based on Strong Monotonicity
6.4.1.2 An Adapted Proof for E-DUE Based on Weak Monotonicity
6.4.2 Convergence Result for the Self-adaptive Projection Algorithm
6.4.3 Convergence Result for the Proximal Point Method
References and Suggested Reading
7 Dynamic Network Loading: Non-physical Queue Models
7.1 The Link Delay Model
7.1.1 Link Dynamics
7.1.2 Network Extension
7.1.3 Formulation of the Dynamic Network Loading Problem
7.1.4 Continuity of the Effective Path Delay Operator
7.2 The Vickrey Model
7.2.1 Ordinary Differential Equation Formulation
7.2.1.1 The Linear Complementarity SystemFormulation
7.2.1.2 The α-Model
7.2.1.3 The -Model
7.2.2 Partial Differential Equation Formulation
7.2.3 Closed-Form Solutions of the Vickrey Model
7.2.4 The Generalized Vickrey Model
7.2.4.1 Initial-Boundary Value Problem
7.2.5 DAE System Formulation of Dynamic Network Loading
7.2.6 Continuity of the Effective Path Delay Operator
7.3 Some Other Non-physical Queue Models
7.3.1 Models Based on Link Exit Flow Functions
7.3.2 Models with Controlled Entrance and Exit Flows
References and Suggested Reading
8 Dynamic Network Loading: Physical Queue Models
8.1 The Lighthill-Whitham-Richards Model
8.1.1 The LWR Model at Road Junctions
8.1.1.1 Demand and Supply
8.1.1.2 Riemann Solver for the Diverge Junction
8.1.1.3 Riemann Solver for the Merge Junction
8.1.2 The LWR Model on Road Networks
8.1.3 Partial Differential Algebraic Equation System Formulation of Dynamic Network Loading
8.1.3.1 Within-Link Dynamics
8.1.3.2 Determination of Boundary Conditions at an Ordinary Node
8.1.3.3 Determination of Flow Distribution at Origin/Destination Nodes
8.1.3.4 Calculation of Path Travel Times
8.1.3.5 The PDAE System
8.2 Variational Formulation of the LWR Model
8.2.1 Notation and Brief Recap of Variational Theory
8.2.2 Dynamics at the Origin Nodes
8.2.3 Differential Algebraic Equation System Formulation with General Fundamental Diagram
8.2.3.1 Determination of Link Demand and Supply
8.2.3.2 Determination of Boundary Conditions Using Demand and Supply
8.2.3.3 The DAE System
8.2.4 Differential Algebraic Equation System Formulation with Triangular Fundamental Diagram
8.2.4.1 Determination of Link Demand and Supply
8.2.4.2 The DAE System
8.3 The Cell Transmission Model
8.3.1 Link Dynamic of the CTM
8.3.2 Network Extension of the CTM
8.3.2.1 Ordinary Links
8.3.2.2 Merge Junction
8.3.2.3 Diverge Junction
8.4 The Link Transmission Model
8.4.1 Link Dynamics of the LTM
8.4.2 Network Extension of the LTM
8.4.3 Relationship with the Continuous-Time Variational Formulation
8.5 Continuity of the Effective Delay Operator for LWR-Based Dynamic Network Loading
8.5.1 Well-Posedness of Junction Models
8.5.1.1 An Example of Ill-posedness
8.5.1.2 Generalized Tangent Vectors
8.5.1.3 A Sufficient Condition for the Well-Posedness of the Diverge Model
8.5.2 An Estimation of Minimum Network Supply
8.5.3 The Continuity Result
8.5.3.1 Estimates Regarding the Path Disaggregation Variable
8.5.3.2 Well-Posedness of the Queuing Model at the Origin with Respect to Departure Rates
8.5.3.3 The Continuity of the Path Delay Operator
References and Suggested Reading
9 Numerical Results
9.1 Closed-Form Solutions of Dynamic User Equilibria
9.1.1 Simultaneous Route-and-Departure-Time DUE with Fixed Demand
9.1.2 Kuhn-Tucker Conditions for the Fixed Demand DUE
9.1.3 Simultaneous Route-and-Departure-Time DUE with Elastic Demand
9.1.4 Kuhn-Tucker Conditions for the Elastic Demand DUE
9.2 Basic Setup of Numerical Examples of Dynamic User Equilibria
9.3 Numerical Solutions of DUE with Fixed Demand
9.3.1 Performance of the Fixed-Point Algorithm
9.3.2 DUE Solutions
9.4 Numerical Examples of DUE with Elastic Demand
9.4.1 The Seven-Link Network
9.4.2 The Sioux Falls Network
9.4.3 Algorithm Performance
9.5 Numerical Examples of DUE with Bounded Rationality
9.5.1 VT-BR-DUE on a Seven-Link Network
9.5.2 BR-DUE on the Nguyen Network
9.5.3 BR-DUE on the Sioux Falls Network
References and Suggested Reading
Index

Complex Networks and Dynamic Systems
Erscheinungsdatum: 08.08.2023

2024-04-02