skip to main content


Title: Computing Dynamic User Equilibrium on Large-Scale Networks: Algorithms and Software Implementation
Dynamic user equilibrium (DUE) is the most widely studied form of dynamic traffic assignment (DTA), in which road travelers engage in a non-cooperative Nash-like game with departure time and route choices. DUE models describe and predict the time-varying traffic flows on a network consistent with traffic flow theory and travel behavior. This paper documents theoretical and numerical advances in synthesizing traffic flow theory and DUE modeling, by presenting a holistic computational theory of DUE, which is numerically implemented in a MATLAB package. In particular, the dynamic network loading (DNL) sub-problem is formulated as a system of differential algebraic equations based on the Lighthill-Whitham-Richards fluid dynamic model, which captures the formation, propagation and dissipation of physical queues as well as vehicle spillback on networks. Then, the fixed-point algorithm is employed to solve the DUE problems with simultaneous route and departure time choices on several large-scale networks. We make openly available the MATLAB package, which can be used to solve DUE problems on user-defined networks, aiming to not only facilitate benchmarking a wide range of DUE algorithms and solutions, but also offer researchers a platform to further develop their own models and applications. The MATLAB package and computational examples are available online.  more » « less
Award ID(s):
1662968
NSF-PAR ID:
10122265
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Networks and spatial economics
Volume:
19
Issue:
3
ISSN:
1566-113X
Page Range / eLocation ID:
869-902
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    In recent decades, the effects of vehicle emissions on urban environments have raised increasing concerns, and it has been recognized that vehicle emissions affect peoples’ choice of housing location. Additionally, housing allocation patterns determine people's travel behavior and thus affect vehicle emissions. This study considers the housing allocation problem by incorporating vehicle emissions in a city with a single central business district (CBD) into a bilevel optimization model. In the lower level subprogram, under a fixed housing allocation, a predictive dynamic continuum user‐optimal (PDUO‐C) model with a combined departure time and route choice is used to study the city's traffic flow. In the upper level subprogram, the health cost is defined and minimized to identify the optimal allocation of additional housing units to update the housing allocation. A simulated annealing algorithm is used to solve the housing allocation problem. The results show that the distribution of additional housing locations is dependent on the distance and direction from the CBD. Sensitivity analyses demonstrate the influences of various factors (e.g., budget and cost of housing supply) on the optimized health cost and travel demand pattern.

     
    more » « less
  2. Service function chaining (SFC), consisting of a sequence of virtual network functions (VNFs) (i.e., firewalls and load balancers), is an effective service provision technique in modern data center networks. By requiring cloud user traffic to traverse the VNFs in order, SFC im- proves the security and performance of the cloud user applications. In this paper, we study how to place an SFC inside a data center to mini- mize the network traffic of the virtual machine (VM) communication. We take a cooperative multi-agent reinforcement learning approach, wherein multiple agents collaboratively figure out the traffic-efficient route for the VM communication. Underlying the SFC placement is a fundamental graph-theoretical prob- lem called the k-stroll problem. Given a weighted graph G(V, E), two nodes s, t ∈ V , and an integer k, the k-stroll problem is to find the shortest path from s to t that visits at least k other nodes in the graph. Our work is the first to take a multi-agent learning approach to solve k- stroll problem. We compare our learning algorithm with an optimal and exhaustive algorithm and an existing dynamic programming(DP)-based heuristic algorithm. We show that our learning algorithm, although lack- ing the complete knowledge of the network assumed by existing research, delivers comparable or even better VM communication time while taking two orders of magnitude of less execution time. 
    more » « less
  3. Dynamic traffic assignment models rely on a network performance module known as dynamic network loading (DNL), which expresses flow propagation, flow conservation, and travel delay at a network level. The DNL defines the so-called network delay operator , which maps a set of path departure rates to a set of path travel times (or costs). It is widely known that the delay operator is not available in closed form, and has undesirable properties that severely complicate DTA analysis and computation, such as discontinuity, nondifferentiability, nonmonotonicity, and computational inefficiency. This paper proposes a fresh take on this important and difficult issue, by providing a class of surrogate DNL models based on a statistical learning method known as Kriging . We present a metamodeling framework that systematically approximates DNL models and is flexible in the sense of allowing the modeler to make trade-offs among model granularity, complexity, and accuracy. It is shown that such surrogate DNL models yield highly accurate approximations (with errors below 8%) and superior computational efficiency (9 to 455 times faster than conventional DNL procedures such as those based on the link transmission model). Moreover, these approximate DNL models admit closed-form and analytical delay operators, which are Lipschitz continuous and infinitely differentiable, with closed-form Jacobians. We provide in-depth discussions on the implications of these properties to DTA research and model applications. 
    more » « less
  4. null (Ed.)
    A reliable, accurate, and yet simple dynamic model is important to analyzing, designing, and controlling hybrid rigid–continuum robots. Such models should be fast, as simple as possible, and user-friendly to be widely accepted by the ever-growing robotics research community. In this study, we introduce two new modeling methods for continuum manipulators: a general reduced-order model (ROM) and a discretized model with absolute states and Euler–Bernoulli beam segments (EBA). In addition, a new formulation is presented for a recently introduced discretized model based on Euler–Bernoulli beam segments and relative states (EBR). We implement these models in a Matlab software package, named TMTDyn, to develop a modeling tool for hybrid rigid–continuum systems. The package features a new high-level language (HLL) text-based interface, a CAD-file import module, automatic formation of the system equation of motion (EOM) for different modeling and control tasks, implementing Matlab C-mex functionality for improved performance, and modules for static and linear modal analysis of a hybrid system. The underlying theory and software package are validated for modeling experimental results for (i) dynamics of a continuum appendage, and (ii) general deformation of a fabric sleeve worn by a rigid link pendulum. A comparison shows higher simulation accuracy (8–14% normalized error) and numerical robustness of the ROM model for a system with a small number of states, and computational efficiency of the EBA model with near real-time performances that makes it suitable for large systems. The challenges and necessary modules to further automate the design and analysis of hybrid systems with a large number of states are briefly discussed. 
    more » « less
  5. In this paper we propose a novel approach to deliver better delay-jitter performance in dynamic networks. Dynamic networks experience rapid and unpredictable fluctuations and hence, a certain amount of uncertainty about the delay-performance of various network elements is unavoidable. This uncertainty makes it difficult for network operators to guarantee a certain quality of service (in terms of delay and jitter) to users. The uncertainty about the state of the network is often overlooked to simplify problem formulation, but we capture it by modeling the delay on various links as general and potentially correlated random processes. Within this framework, a user will request a certain delay-jitter performance guarantee from the network. After verifying the feasibility of the request, the network will respond to the user by specifying a set of routes as well as the proportion of traffic which should be sent through each one to achieve the desired QoS. We propose to use mean-variance analysis as the basis for traffic distribution and route selection, and show that this technique can significantly reduce the end-to-end jitter because it accounts for the correlated nature of delay across different paths. The resulting traffic distribution is often non-uniform and the fractional flow on each path is the solution to a simple convex optimization problem. We conclude the paper by commenting on the potential application of this method to general transportation networks. 
    more » « less