Information Flow Propagation Wave Model Based on an Information Relay Control Strategy Under Congested V2V Communications
Jian Wang, Purdue UniversityShow Abstract
Yong Hoon Kim, University of Windsor
Xiaozheng He, Rensselaer Polytechnic Institute (RPI)
Srinivas Peeta, Purdue University
Vehicular traffic congestion in a vehicle-to-vehicle (V2V) communication environment can lead to congestion effects for information flow propagation. Such congestion effects can impact whether a specific information packet of interest can reach a desired location, and if so, in a timely manner to influence the traffic system performance. This paper aims to characterize the information flow propagation wave (IFPW) for an information packet in a congested V2V communication environment under an information relay control strategy. This strategy seeks to exclude information that is dated in the communication buffer under a first-in, first-out queue discipline, from being relayed if the information flow regime is congested. A macroscopic two-layer model is proposed to characterize the IFPW. The upper layer is formulated as integro-differential equations to characterize the information dissemination in space and time under this control strategy. The lower layer adopts the Lighthill-Whitham-Richards model to capture the traffic flow dynamics. A necessary condition for existence of IFPW is derived which quantifies the expected time that needs to be reserved for broadcasting the information packet of interest so as to ensure the formation of an IFPW. The asymptotic IFPW speed and the asymptotic density of informed vehicles (those that have received the information of interest) are analytically explored in this study, which help in evaluating the timeliness of information propagation and the influence of traffic dynamics on information propagation. The proposed model can aid in the design of traffic management strategies built upon the timely propagation of information through V2V communication.
Applying Internet Protocol Random Early Detection Strategies to Real-Time Traffic Management in Transportation Networks
Hanna Grzybowska, University of New South WalesShow Abstract
There is no doubt that the provision of real-time travel information to the individual drivers has a big potential for influencing their behaviour with respect to the route choice, trip making, times of travel and mode choice. As real-time data became available in large quantities, cheaply and fast, due to the most recent development in the Information and Communication Technologies and Intelligent Transport Systems area, there arose questions on effects of this information on the individual drivers' behaviour and the overall network performance. As a consequence a demand has been rising for new control strategies levering the provision of information on a real-time basis to individual vehicles in a traffic system in order to expand the spectrum of opportunities to influence traffic conditions in increasingly congested networks. This paper argues that the congestion problems observed in the Internet networks are analogous to the transportation networks'. That the methods targeting congestion which proved successful in the Transmission Control Protocol can be adapted to be used in transportation networks. Thus, the paper provides a proof of concept for the application of the Random Early Detection strategy in transportation networks taking the advantage of the real-time information with the goal of alleviating congestion. The test were conducted on a fitted Braess' network. The obtained results indicated that Random Early Detection algorithms are suited to tackle congestion in transportation network and that they hold a potential for improvement yet to be discovered.
A Greedy Path-Based Algorithm for Traffic Assignment
Jun Xie, Southwest Jiaotong UniversityShow Abstract
Yu Nie, Northwestern University
Xiaobo Liu, Southwest Jiaotong University
This paper presents a new path-based algorithm for the static user equilibrium traffic assignment problem. It is generally believed that path-based algorithms are less efficient than bush-based counterparts, such as Algorithm B, TAPAS and iTAPAS, because explicitly storing and manipulating all paths appears unwisely wasteful. However, our numerical experiments indicate that the proposed path-based algorithm can outperform TAPAS or iTAPAS by a wide margin. The proposed algorithm, sharing the same Gauss-Seidel decomposition scheme with existing path-based algorithms, delivers such a surprising performance most likely due to its two main features. First, it adopts a greedy method to solve the restricted subproblem defined on each origin-destination (O-D) pair. Second, instead of sequentially visiting each OD pair in each iteration, it introduces an intelligent scheme to determine which OD pairs need more or less work. The proposed algorithm is also more straightforward to implement than bush-based algorithms.
Global Optimal Solution of the Continuous Network Design Problem Under Stochastic User Equilibrium
Ka Fai Ng, Hong Kong University of Science and TechnologyShow Abstract
Hong Lo, University of Hong Kong
Ng and Lo  formulated the housing supply allocation problem with a bi-level program, in which the upper level maximizes the housing profit by determining the optimal housing supply, while the lower level constitutes a combined bid-rent and residence choices equilibrium model. The lower level involves not only the conventional user equilibrium conditions as in the network design problem (NDP), but also the bid-rent process which describes the competition among residents bidding for housing. Similar to the classical NDP, this bi-level problem belongs to the class of mathematical program with equilibrium constraints (MPEC), whose solution global optimality is not guaranteed. This paper proposes a global optimal solution algorithm to solve such problems, including the continuous NDP (CNDP) as a special case. Specifically, the original housing supply allocation problem is reformulated and relaxed into a mixed-integer linear program (MILP) through the process of piecewise linear relaxation of the original nonlinear functions. The MILP provides a global solution to the linearized original problem through the iterative solution algorithm developed in this paper. Extending the work of Polisetty , the proposed updating process of the linearized problem and the information from the original problem at each iteration step assure convergence of the global optimal solution. This paper provides a proof of the global optimality of the solution, and numerical studies to demonstrate its promising results, in solution accuracy and computational speed.
Keywords: Global optimal algorithm, Mixed-integer linear programming, Bid-rent process, nested choices, range reduction scheme
Optimal Information Provision at Bottleneck Equilibrium with Risk-Averse Travelers
Peng Liu, National University of SingaporeShow Abstract
Yang Liu, National University of Singapore
The effects of traffic information provision for risk-averse travelers have recently attracted ever-increasing attention. This paper examines a stochastic bottleneck model with risk-averse commuters, in which the free-flow travel time is assumed uncertain and follows a uniform distribution. We adopt the mean-variance approach to measure the travel cost under risk. We prove that the individual travel cost at bottleneck equilibrium monotonically increases with the risk-aversion level. With higher risk-aversion level, the morning peak hour starts earlier, but the duration of peak hour remains constant regardless of the risk-aversion level. When information provision can reduce the travel time variability, the risk-averse commuters will benefit from the higher quality of information. Nevertheless, if the cost of information provision is taken into account, we derive the optimal information quality, which minimizes the total system cost. The numerical examples with simulated scenarios demonstrate the information efficiency and provision strategy. The findings reveal the characteristics of stochastic bottleneck congestion with risk-averse travelers and provide a guidance for the traffic information provision.
Route-Cost Assignment with Joint User and Operator Behavior as a Many-to-One Stable Matching Assignment Game
Saeid Rasulkhani, New York UniversityShow Abstract
Joseph Chow, New York University
In this paper we proposed a generic model using assignment game criteria compatible with transportation application. Unlike conventional assignment game models, capacity of the proposed model is at the link-route level. Using this model enables us to find both the stable pricing and matching of travelers to routes—a more generalized transportation assignment methodology that can evaluate diverse mobility systems. We examined two different examples to test the model. As a case study, we used this model to evaluate taxi ridesharing in lower Manhattan in NYC. The results show that, by accounting for traveler and taxi behavior, 60% of a sample of over 300 users would share their cab. The model also determines that taxi-sharing decreases travel miles by 31% compared to just 3% increasing in travel time. The model provides policy-makers with a tool to evaluate cost sharing mechanisms for different transport systems, including many shared mobility services.
A Subgradient Approach to Solve for Path-Based System Optimal Dynamic Traffic Assignment
Pinchao Zhang, Carnegie Mellon UniversityShow Abstract
Zhen Qian, Carnegie Mellon University
The system-optimal dynamic traffic assignment (SO-DTA) problem aims at finding the time-dependent traffic flow of a network that yields the minimal total system cost provided with Origin-Destination (O-D) demand. The key to solving the path-based formulation of the SO-DTA problem is to accurately and efficiently compute path marginal cost (PMC). Existing studies implicitly assume that the total system cost (TC) is always differentiable with respect to path flow. However we show that the upper gradient of TC does not always equal to its lower gradient, especially when the optimality condition holds. Overlooking this fact leads to failure of path flow convergence while numerically solving the SO-DTA problem. We examine under what flow patterns the TC is non-differentiable, and how to compute and approximate sub-derivatives of PMC in those cases. In addition, we propose heuristic solution algorithms that can deal with non-differentiable TC. Numerical experiments show that both the TC and path flow converge towards the optimum using this subgradient approach, whereas algorithms that assume the differentiability of TC fail.
Path-Constrained Traffic Assignment: Continuously Distributed Bounds on Travel Weights
Chi Xie, Shanghai Jiao Tong UniversityShow Abstract
Xing Wu, Lamar University
Stephen Boyles, University of Texas, Austin
A new traffic assignment problem with continuously distributed bounds on travel weights is introduced in this paper, as an emerging modeling tool for evaluating traffic networks in which the route choice behavior of individual motorists is subject to heterogeneous upper limits of some flow-independent travel weights. This problem may arise from the following two traffic network instances. In a traffic network serving electric vehicles, the driving range of these vehicles is subject to onboard battery capacities and electricity consumption rates as well as network-wide battery-recharging opportunities, which cause the so-called “range anxiety” issue in the driving population. In a tolled traffic network, while drivers take into account both travel time and road toll in their route choice decisions, many of them imply a “budget constraint” on willing-to-pay toll charges, by considering their own income levels, trip purposes and other socio-economic factors. For characterizing and quantifying such traffic assignment instances, we proposed a convex programming model with a finite number of constraints, on the basis of newly introduced modeling components, namely, weight-ordered path set and weight-partitioned path flow rate. The mathematical properties of the model was then analyzed and a linear approximation algorithm was further implemented, where the algorithm encapsulates an efficient weight-constrained -minimum cost path search procedure to perform the network loading. Numerical results obtained from conducting quantitative analyses on example networks clearly illustrate the applicability of the modeling and solution methods for the defined problem and reveal the mechanism of continuously distributed weight limits reshaping the network equilibrium.
Improving Scalability of Generic Online Calibration for Real-Time Dynamic Traffic Assignment Systems
Arun Akkinepally, Massachusetts Institute of Technology (MIT)Show Abstract
Ravi Seshadri, Singapore-MIT Alliance for Research and Technology
Constantinos Antoniou, Technical University of Munich
Francisco Pereira, Technical University of Denmark
Moshe Ben-Akiva, Massachusetts Institute of Technology (MIT)
Flexible calibration of Dynamic Traffic Assignment (DTA) systems in real-time has important applications in effective traffic management. However, the existing approaches are either limited to small networks or to a specific class of parameters. In this light, this study presents a framework to systematically reduce the dimension of the generic online calibration problem making it more scalable. Specifically, we propose a state-space formulation of the problem in the reduced dimension space. Following which the problem is solved using the Constrained Extended Kalman Filter, which is made tractable because of the low dimensionality of the formulated problem. The effectiveness of the proposed approach is demonstrated using a real--world network leading to better state estimation by 13% and better state predictions by 11% ---with a 50 fold dimensionality reduction. Insights into choosing the right degree of dimensionality reduction are also discussed. This work has the potential for a more wide-spread application of real-time DTA systems in practice.
Multimodal Transportation Network Modeling Based on the GSOM Approach
Jean-Patrick Lebacque, IFSTTARShow Abstract
Megan Khoshyaran, ETC Economics Traffic Clinic
The GSOM (Generic second order modeling) approach to vehicular traffic flow combines the traditional kinematic description of traffic with dynamic equations for vehicle attributes. The GSOM model provides a unifying framework for many models of the literature. This framework includes tools such as local supply and demand, discretization, variational formulation and generic intersection models.The object of this paper is to extend this approach to multimodal modeling of transportation networks. In multimodal networks two connected but distinct flows co-exist: vehicular and passenger flow. The main idea of the paper is to express the passenger flow as the flow of a specific attribute: the passenger load of vehicles, the unit of which is expressed in passengers per vehicle. Supplementary attributes pertaining to passengers can be added: destinations, activity plans, information availability, passenger category… Intermodal poles, stations (bus, taxi, train) and intersections are modeled as nodes. It is shown that the stock variables associated to vehicules and passengers satisfy to a system of conservation equations (on links) coupled with a system of ordinary differential equations (in nodes). Boundary conditions and numerical methods are proposed for the resolution of the model. Some examples are given, notably a method for managing a major incident on an automatic train line. The method uses most elements of the model in order to define the control strategy: passenger and train dynamics, station models and local traffic supply and demand analysis.
An Algorithm for Robust Shortest Path Problem with Travel Time Correlations
Yufeng Zhang, University of Minnesota, Twin CitiesShow Abstract
Alireza Khani, University of Minnesota, Twin Cities
Robust shortest path (RSP) problem reflects the variability of travel time and is more realistic than standard shortest path problem which considers only the average travel time. This paper describes an algorithm for solving the mean-standard deviation RSP problem considering link travel time correlations. The proposed algorithm adopts the Lagrangian relaxation and covariance matrix decomposition technique to deal with the difficulty resulting from non-linearity and non-additivity of the Mixed Integer Non-Linear Program (MINLP). The problem is decomposed into a standard shortest path problem and a convex optimization problem which are both easy to solve. The complexity of the original problem is significantly reduced by the proposed algorithm such that it can be scaled to large networks. Applying the standard labeling methods and efficient convex optimization algorithms greatly reduces the computational costs. Numerical experiments on large-scale networks show the efficacy of the algorithm in terms of relative duality gap and computation time. The algorithm outperforms the existing one-to-one RSP algorithms in the literature.
Network Partitioning Algorithms for Solving the Traffic Assignment Problem Using a Decomposition Approach
Cesar Yahia, University of Texas, AustinShow Abstract
Venktesh Pandey, University of Texas, Austin
Stephen Boyles, University of Texas, Austin
Recent methods in the literature to parallelize the traffic assignment problem consider partitioning a network into subnetworks to reduce the computation time for large-scale networks. In this article, we seek a partitioning method that generates subnetworks minimizing the number of boundary nodes, the inter-flow between subnetworks, and the computation time when the traffic assignment is solved in parallel on the subnetworks. We test two different methods for partitioning. The first is an agglomerative clustering algorithm that decomposes a network with the objectives of minimizing subnetwork boundary nodes. The second is a flow weighted spectral clustering algorithm that uses the graph Laplacian to partition the network.
We test the performance of both algorithms on different test networks. The results indicate that the flow weighted spectral clustering is superior to the agglomerative clustering algorithm on the stated objectives. For the Austin network partitioned into four subnetworks, spectral clustering has 82.7\% lower computation time for the subnetworks solved to equilibrium in parallel. The number of boundary nodes and inter-flow are also lower for the generated subnetworks indicating the usefulness of this algorithm in generating partitions for decentralizing the static traffic assignment.
Reliability-Based User Equilibrium Formulation in Dynamic Stochastic Networks with Correlated Travel Times and Heterogeneous User Preferences
Ali Zockaie, Michigan State UniversityShow Abstract
Hani Mahmassani, Northwestern University
Yu Nie, Northwestern University
Fatemeh Fakhrmoosavi, Michigan State University
This study provides a framework for the reliability-based user equilibrium traffic assignment problem in general stochastic time-varying networks. In this problem, link travel times are congestion-dependent random variables that vary over time and exhibit general correlation patterns, reflecting spatial and temporal network flow processes. The resulting general problem has not been previously addressed in the literature. The reliability-based user equilibrium problem is first formulated as a fixed-point problem, followed by an equivalent variational inequalities formulation. A gap function is then defined for this variational inequalities formulation to substitute the main problem with a non-linear optimization problem. An iterative solution procedure is then presented for the reliability-based user equilibrium problem, which minimizes the defined gap function. The approach is implemented and tested on an actual large-scale network of Chicago, in addition to a medium-size test network. A core element of this procedure is a path-finding algorithm that relies on a Monte-Carlo sampling approach. This algorithm needs to be implemented as part of the column generation approach and finds the optimal path for multi-class users considering a given link travel time distributions and correlation structure. The optimal path and its associated utility compared with the current used paths and their experienced utilities are used to update the traffic assignment at each iteration of the iterative solution procedure for the reliability-based user equilibrium problem. Two different reliability rules are applied in this study for the path-finding algorithm and three different assignment approaches are compared for different scenarios. The main contribution of this study is to present a research framework for the reliability-based user equilibrium problem that considers link travel time correlations for heterogenous users in a dynamic stochastic network. The numerical result section shows satisfactory application of the algorithm and its sensitivity to different parameters such as the valuation of reliability by users or the correlation structure.