Information Flow Propagation Wave Model Based on an Information Relay Control Strategy Under Congested V2V Communications
Jian Wang, Purdue University Yong Hoon Kim, University of Windsor Xiaozheng He, Rensselaer Polytechnic Institute (RPI) Srinivas Peeta, Purdue University
Show Abstract
Vehicular traffic congestion in a vehicletovehicle
(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 firstin, firstout queue discipline, from
being relayed if the information flow regime is congested. A macroscopic
twolayer model is proposed to characterize the IFPW. The upper layer is
formulated as integrodifferential equations to characterize the information
dissemination in space and time under this control strategy. The lower layer
adopts the LighthillWhithamRichards 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.

1800695

Applying Internet Protocol Random Early Detection Strategies to RealTime Traffic Management in Transportation Networks
Hanna Grzybowska, University of New South Wales
Show Abstract
There is no doubt that the provision of realtime 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 realtime 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 realtime 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 realtime
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.

1802143

A Greedy PathBased Algorithm for Traffic Assignment
Jun Xie, Southwest Jiaotong University Yu Nie, Northwestern University Xiaobo Liu, Southwest Jiaotong University
Show Abstract
This paper presents a new pathbased algorithm for the
static user equilibrium traffic assignment problem. It is generally believed
that pathbased algorithms are less efficient than bushbased 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 pathbased algorithm can outperform TAPAS or iTAPAS by a wide
margin. The proposed algorithm, sharing the same GaussSeidel decomposition
scheme with existing pathbased 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 origindestination
(OD) 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 bushbased algorithms.

1803128

Global Optimal Solution of the Continuous Network Design Problem Under Stochastic User Equilibrium
Ka Fai Ng, Hong Kong University of Science and Technology Hong Lo, University of Hong Kong
Show Abstract
Ng and Lo [1] formulated the housing supply
allocation problem with a bilevel program, in which the upper level maximizes
the housing profit by determining the optimal housing supply, while the lower
level constitutes a combined bidrent 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 bidrent process which
describes the competition among residents bidding for housing. Similar to the
classical NDP, this bilevel 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 mixedinteger 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
[2], 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, Mixedinteger linear programming, Bidrent process, nested choices,
range reduction scheme

1803897

Optimal Information Provision at Bottleneck Equilibrium with RiskAverse Travelers
Peng Liu, National University of Singapore Yang Liu, National University of Singapore
Show Abstract
The effects of traffic information provision for
riskaverse travelers have recently attracted everincreasing attention. This
paper examines a stochastic bottleneck model with riskaverse commuters, in
which the freeflow travel time is assumed uncertain and follows a uniform
distribution. We adopt the meanvariance approach to measure the travel cost
under risk. We prove that the individual travel cost at bottleneck equilibrium
monotonically increases with the riskaversion level. With higher riskaversion
level, the morning peak hour starts earlier, but the duration of peak hour
remains constant regardless of the riskaversion level. When information
provision can reduce the travel time variability, the riskaverse 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 riskaverse travelers and provide a guidance for the traffic
information provision.

1804280

RouteCost Assignment with Joint User and Operator Behavior as a ManytoOne Stable Matching Assignment Game
Saeid Rasulkhani, New York University Joseph Chow, New York University
Show Abstract
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
linkroute 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 taxisharing decreases
travel miles by 31% compared to just 3% increasing in travel time. The model
provides policymakers with a tool to evaluate cost sharing mechanisms for
different transport systems, including many shared mobility
services.

1804367

A Subgradient Approach to Solve for PathBased System Optimal Dynamic Traffic Assignment
Pinchao Zhang, Carnegie Mellon University Zhen Qian, Carnegie Mellon University
Show Abstract
The systemoptimal dynamic traffic assignment (SODTA)
problem aims at finding the timedependent traffic flow of a network that yields
the minimal total system cost provided with OriginDestination (OD) demand. The
key to solving the pathbased formulation of the SODTA 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 SODTA problem. We examine under what flow patterns the
TC is nondifferentiable, and how to compute and approximate subderivatives of
PMC in those cases. In addition, we propose heuristic solution algorithms that
can deal with nondifferentiable 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.

1804412

PathConstrained Traffic Assignment: Continuously Distributed Bounds on Travel Weights
Chi Xie, Shanghai Jiao Tong University Xing Wu, Lamar University Stephen Boyles, University of Texas, Austin
Show Abstract
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 flowindependent
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
networkwide batteryrecharging opportunities, which cause the socalled “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 willingtopay toll charges, by
considering their own income levels, trip purposes and other socioeconomic
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, weightordered path set and
weightpartitioned 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 weightconstrained 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.

1804790

Improving Scalability of Generic Online Calibration for RealTime Dynamic Traffic Assignment Systems
Arun Akkinepally, Massachusetts Institute of Technology (MIT) Ravi Seshadri, SingaporeMIT Alliance for Research and Technology Constantinos Antoniou, Technical University of Munich Francisco Pereira, Technical University of Denmark Moshe BenAkiva, Massachusetts Institute of Technology (MIT)
Show Abstract
Flexible calibration of Dynamic Traffic Assignment (DTA)
systems in realtime 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 statespace 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 realworld 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 widespread application of realtime DTA systems in
practice.

1804982

Multimodal Transportation Network Modeling Based on the GSOM Approach
JeanPatrick Lebacque, IFSTTAR Megan Khoshyaran, ETC Economics Traffic Clinic
Show Abstract
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 coexist: 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.

1805152

An Algorithm for Robust Shortest Path Problem with Travel Time Correlations
Yufeng Zhang, University of Minnesota, Twin Cities Alireza Khani, University of Minnesota, Twin Cities
Show Abstract
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 meanstandard 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 nonlinearity and nonadditivity of the Mixed Integer
NonLinear 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 largescale networks show the
efficacy of the algorithm in terms of relative duality gap and computation time.
The algorithm outperforms the existing onetoone RSP algorithms in the
literature.

1805972

Network Partitioning Algorithms for Solving the Traffic Assignment Problem Using a Decomposition Approach
Cesar Yahia, University of Texas, Austin Venktesh Pandey, University of Texas, Austin Stephen Boyles, University of Texas, Austin
Show Abstract
Recent methods in the literature to parallelize the traffic assignment problem consider partitioning a network into subnetworks to reduce the computation time for largescale networks. In this article, we seek a partitioning method that generates subnetworks minimizing the number of boundary nodes, the interflow 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 interflow are also lower for the generated subnetworks indicating the usefulness of this algorithm in generating partitions for decentralizing the static traffic assignment.

1806570

ReliabilityBased User Equilibrium Formulation in Dynamic Stochastic Networks with Correlated Travel Times and Heterogeneous User Preferences
Ali Zockaie, Michigan State University Hani Mahmassani, Northwestern University Yu Nie, Northwestern University Fatemeh Fakhrmoosavi, Michigan State University
Show Abstract
This study provides a framework for the
reliabilitybased user equilibrium traffic assignment problem in general
stochastic timevarying networks. In this problem, link travel times are
congestiondependent 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 reliabilitybased user equilibrium problem is first formulated
as a fixedpoint 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 nonlinear optimization
problem. An iterative solution procedure is then presented for the
reliabilitybased user equilibrium problem, which minimizes the defined gap
function. The approach is implemented and tested on an actual largescale
network of Chicago, in addition to a mediumsize test network. A core element of
this procedure is a pathfinding algorithm that relies on a MonteCarlo sampling
approach. This algorithm needs to be implemented as part of the column
generation approach and finds the optimal path for multiclass 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 reliabilitybased user
equilibrium problem. Two different reliability rules are applied in this study
for the pathfinding 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 reliabilitybased 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.

1806741
