A Deep-Learning Approach for Network Traffic Assignment with Incomplete Data
Yue Su, University Paris, SaclayShow Abstract
Wenbo Fan (email@example.com), Southwest Jiaotong University
Jakob Puchinger, University Paris, Saclay
Minyu Shen, Hong Kong Polytechnic University
The Origin-Destination (OD) data collection often relies on the questionnaire surveys which is inevitably incomplete. With incomplete input data, the traditional traffic assignment models (e.g., mathematical programming) cannot generate reasonable results. Alternatively, we propose a deep-learning approach employing Feed-Forward Neural Network (FFNN) for the traffic assignment that respects incomplete data. Experiments are conducted in the Braess’s paradox network, Sioux Falls network, and Chicago sketch network. In the first two networks, training data for the FFNN is obtained by randomly generating 10000 OD scenarios and running mathematical assignment models for link flows. For Chicago sketch network, a mesoscopic tool is employed to generate the training data. The feasibility of using FFNN to learn traffic assignment mechanics is verified by using complete OD data and full link flow data with accuracy over 90% in three networks. In case of partially observed OD data, our idea is to learn the mapping between incomplete OD data and full link flow data. Experiments are conducted under different OD data incompleteness levels. The results demonstrate that the accuracy of FFNN model remains over 90% even losing 50% OD data and overwhelms that of the mathematical assignment model in three networks. Practically, the reported model can be trained for a certain network with easily-obtained partial OD data (e.g., observed cellular mobile data) and traffic flow data in the field (e.g., loop data and video data). Once well trained, when inputting voluminous incomplete OD data, the data-driven approach can provide accurate full link flows efficiently.
Adapting The Barzilai-Borwein Step Size for The Nonadditive Traffic Equilibrium Problem
Heqing Tan, Hohai UniversityShow Abstract
Muqing Du (firstname.lastname@example.org), Hohai University
Anthony Chen, Hong Kong Polytechnic University
The nonadditive traffic equilibrium problem (NaTEP) overcomes the additivity assumption of the traditional traffic equilibrium models in which the path cost is just a simple sum of costs of links on that path. The computational efficiency for solving the NaTEP heavily depends on the step size determination step. This paper aims to develop a faster algorithm for the NaTEP by adapting the Barzilai-Borwein (BB) step size scheme. The proposed algorithm utilizes the solution information of the previous iterations to determine a suitable step size and avoids extra evaluations to the value or the derivative of the mapping function. Thus, the required computational cost of the proposed algorithm is modest. Furthermore, we customize an accelerating strategy to speed up the algorithm on realistic networks. Numerical results demonstrate the efficiency and robustness of the proposed algorithm.
Dynamic Mixed Information Strategy for Heterogeneous Network Users and System Optimal Design
Larkin Folsom, North Carolina A&T State UniversityShow Abstract
Hyoshin Park, North Carolina A&T State University
Current Dynamic Traffic Assignment (DTA) research typically considers non-competing groups of drivers seeking either Dynamic User Equilibrium (DUE) or Dynamic System Optimal (DSO) equilibrium. Real-world solutions for minimizing congestion by routing heterogeneous road users under mixed information frameworks require more reliable and robust methods for heterogeneous users' decision-making. This research provides a methodology for reducing congestion using the competing strategies of DUE and DSO seeking drivers. A realistic simulation of the responses of drivers to sudden road network perturbations is presented by applying Dynamic Traffic Assignment (DTA) to two groups of drivers; informed and uninformed. A navigation app provides within-day route suggestions to informed drivers using information about the time-varying decision-making habits of uninformed drivers. These within-day route suggestions cause some informed users to detour from their initially proposed routes in order to minimize network congestion and delays, pushing the system toward DSO equilibrium, while uninformed drivers make day-to-day (DTD) decisions which push the system toward DUE. Simulations considering varying fractions of informed drivers show that congestion is reduced by approximately 59.2\% when 20\% of drivers are informed, and is nearly eliminated when 80\% of drivers are informed. The computational efficiency of this approach is also improved using shared memory multi-core parallelization.
Mean Field Games Framework to Departure Time Choice Equilibrium in Urban Traffic Networks
Mostafa Ameli (email@example.com), University Gustave EiffelShow Abstract
Mohamad Sadegh Shirani Faradonbeh, University of Waterloo
Jean-Patrick Lebacque, University Gustave Eiffel
Hossein Abouee-Mehrizi, University of Waterloo
Ludovic Leclercq, Universite Gustave Eiffel
Departure time choice models have a crucial role in transportation network planning in order to provide planners with predictions about the optimal traffic load. This paper introduces a new dynamic departure time choice framework based on the so-called Mean-field Games (MFGs) theory proposed by Lasry and Lions (1). MFGs models aim to analyze large population differential games. This feature gives us a unique opportunity to design a departure time choice equilibrium model in a scale-free transportation system. The proposed framework is the combination of two components: (i) the reaction of travelers to the traffic congestion by choosing their departure time to optimize the travel cost; (ii) the aggregation of the actions of the travelers, which determines the congestion level of the system. The first component corresponds to a classical game theory model, while the second one captures the interactions of the travelers at the macroscopic level. We use the generalized bathtub model recently proposed by Jin (2) to represent the traffic dynamics at the network level. First, we provide a continuous model to investigate the equilibria and then give a discrete approximation of the system from deterministic differential games models. Finally, we show on a real test case that the model can represent the departure time choice equilibrium for multiple preferred travel time with heterogeneous trip lengths while the framework is capable of considering a large number of players.
Parallel Network Flow Allocation in Repeated Routing Games via LQR Optimal Control
Yiling You, University of California, BerkeleyShow Abstract
Marsalis Gibson, University of California, Berkeley
Alexandre Bayen, University of California, Berkeley
In this article, we study the repeated routing game problem on a parallel network with affine latency functions on each edge. We cast the game setup in a LQR control theoretic framework, leveraging the Rosenthal potential formulation. We use control techniques to analyze the convergence of the game dynamics with specific cases that lend themselves to optimal control. We design proper dynamics parameters so that the conservation of flow is guaranteed. We provide an algorithmic solution for the general optimal control setup using a multiparametric quadratic programming approach (explicit MPC). Finally we illustrate with numerics the impact of varying system parameters on the solutions.
A Framework to Generate Realistic and Scalable Hypothetical Networks for Transportation Studies
Negin Shariat, University of California, IrvineShow Abstract
Daisik Nam (firstname.lastname@example.org), University of California, Irvine
R. Jayakrishnan, University of California, Irvine
Michael Hyland, University of California, Irvine
Traditional network generators are typically used for pure network studies within idealized optimization or modeling contexts in fields such as Operations Research and Computer Science. But for rare exceptions, such schemes for generating hypothetical networks have not been used in transportation studies and research. This is despite the recognition in many studies that the results were not generalizable or transferable due the studies being on limited networks that are often idealized forms of real networks. Newer mobility paradigms envisaged in the near future also make it important now to develop generators of data on hypothetical future network geometries and layouts, as well as the associated supply and demand. The reason for not using network generators in transportation studies is the myriad complexities that need to be addressed in the urban network context. This paper describes a network generation framework that focuses on several such complexities with respect to network form, node density, link connections, freeway link generation, ramp generation, etc. The proposed framework generates not only different sizes and topologies but also more detailed data usable in agent-based models like activity locations. This paper also highlights the demand-side information needed in these models and generates randomly distributed agent trips with defined activities so that they are also usable in activity-based models. Illustrative results are provided with a few candidate networks generated by the framework and the paper discusses several associated details of conceptual and practical significance.
Self-Regulating Demand and Supply Equilibrium in Joint Simulation of Travel Demand and a Ride-Pooling Service
Gabriel Wilkes, Karlsruhe Institute of Technology (KIT)Show Abstract
Roman Engelhardt, Technische Universitat Munchen
Lars Briem, Karlsruhe Institute of Technology (KIT)
Florian Dandl, Technische Universitat Munchen
Peter Vortisch, Karlsruhe Institute of Technology (KIT)
Klaus Bogenberger, Technische Universitat Munchen
Martin Kagerbauer, Karlsruhe Institute of Technology (KIT)
This paper presents the coupling of a state-of-the-art ride-pooling fleet simulation package with the mobiTopp travel demand modeling framework. The coupling of both models enables a detailed agent- and activity based demand model, in which travelers have the option to use ride-pooling based on real-time offers of an optimized ride-pooling operation. On the one hand, this approach allows the application of detailed mode-choice models based on agent-level attributes coming from mobiTopp functionalities. On the other hand, existing state-of-the-art ride-pooling optimization can be applied to utilize the full potential of ride-pooling. The introduced interface allows mode choice based on real-time fleet information and thereby does not require multiple iterations per simulated day to achieve a balance of ride-pooling demand and supply. The introduced methodology is applied to a case study of an example model where in total approximately 70,000 trips are performed. Simulations with a simplified mode-choice model with varying fleet size (0-150 vehicles), fares and further fleet operator's settings show that (i) ride-pooling can be a very attractive alternative to existing modes and (ii) the fare model can affect the mode shifts to ride-pooling. Depending on the scenario, the mode share of ride-pooling is between 7.6% and 16.8% and the average distance-weighed occupancy of the ride-pooling fleet varies between 0.75 and 1.17.
Adaptive Sampling Simulated Annealing for the synthesis of disaggregate mobility data from Origin-Destination matrices
Haris Ballis, University of CyprusShow Abstract
Loukas Dimitriou, University of Cyprus
Disaggregate models are gaining significant momentum for the tackling of transportation related problems. Nonetheless, such models often require difficult to obtain and highly detailed input at person-level. One of the most useful inputs describing mobility are the trip-chains people execute for the completion of their activity schedules. Although a plethora of methodologies have been suggested for the creation of such data, none has utilised the widely available aggregate Origin-Destination (OD) matrices as input. Identifying all the possible trip-chains in an input OD and subsequently identifying a combination which recreates the input is theoretically feasible, but the combinatorial nature of the problem can render its solution intractable. In the current paper an advanced optimisation algorithm is proposed, named Adaptive Sampling Simulated Annealing (ASSA) algorithm that proves as a suitable method to address combinatorial problems with excessively large search spaces and stochastic constraints through the exploitation of calibration information for the guidance of the optimisation process towards optimality. The proposed optimisation algorithm is tested on computational experiments completed over a set of large-scale OD matrices including 253 thousand trips showcased the potential of identifying combinations of individual home-based trip-chains (i.e. tours) which can accurately represent the inputted travel demand patterns. In particular, the methodology accurately reconstructed the input ODs to thousands of individual multi-leg tours which closely match the observed data with the accuracy exceeding 90%. The implications are significant since large-scale ODs can be now converted to disaggregate tours able to fuel sophisticated disaggregate transport models.
Effects of Origin-Destination Matrix Errors on User Equilibrium in Networks
Priyadarshan Patil (email@example.com), University of Texas, AustinShow Abstract
Carlin Liao, University of Texas, Austin
Stephen Boyles, University of Texas, Austin
For network traffic assignment, the origin-destination matrix is the most difficult input to estimate, particularly in future years. An obvious question is how accurate this matrix must be in order to ensure a certain level of accuracy in the modeling outputs. The answer depends critically on the source of these errors, so we examine the effect of three different models of demand matrix error in the static traffic assignment problem. The first assumes uniform error across all demand pairs (perfect correlation); the second assumes the error is independent across demand pairs (no correlation); and the third assumes that error occurs with spatial correlation. We perform tests by perturbing demand matrices on standard test networks in the literature according to these three models and measuring the effects on three metrics: total system travel time, flow-weighted volume-capacity ratio, and total vehicle miles traveled. Using standard test networks, we show that errors of the first type (uniform) have the greatest effect on network metrics, particularly in congested networks. To achieve accuracy in the model outputs within 5%, the necessary accuracy levels in the OD matrix are observed to be <5%, <10% and <5% for the full correlation, no correlation and spatial correlation cases. For small perturbations (<25%) in input matrix, percentage of spatially perturbed nodes did not appear to have significant impact on the output metrics. The uniform perturbation model requires higher input accuracy for congested networks.
Origin-Destination matrix estimation in the presence of faulty measurements using the cell transmission model
Yiolanda Englezou (firstname.lastname@example.org), University of CyprusShow Abstract
Stelios Timotheou, University of Cyprus
Christos Panayiotou, University of Cyprus
Estimation of origin-destination (O-D) matrices, i.e. counting the number of trips from a given origin to a given destination, is an important and challenging task that can effectively support transport studies and the development of smart cities. The main objective of the estimation procedure is to calculate an O-D matrix based on available sources (e.g. link traffic counts obtained from traffic sensors) to reproduce the field data as accurately as possible. A significant complication when using information obtained from traffic sensors, is that sensors deployed in the traffic network are subject to considerable disruptions that affect the quality and reliability of the information delivered. Despite the extensive study of efficient O-D matrix estimation in the literature, there is no research work that assumes faulty traffic sensors. A novel methodology for O-D matrix estimation in the presence of faulty measurements is presented. The path-based cell transmission model (CTM) is utilised to capture the dynamics of traffic networks in a pre-specified time window and associate link densities with per path densities and the path demand. The problem is formulated in an optimisation framework by (i) not taking into account faulty sensors and (ii) taking into account the presence of faulty sensors. The methodology is tested on a sample network and shows great potential in terms of O-D matrix estimation in the presence of faulty measurements. Simulation results underpin the advantage of the proposed approach in terms of performance in estimating quantities of interest as well as identifying the faulty sensors and their fault characteristics.
Estimating Link Flows from Limited Traffic Volume and Sparse Trajectory Data: Reinforcement Learning Approaches
Miner Zhong, University of QueenslandShow Abstract
Jiwon Kim (email@example.com), University of Queensland
Zuduo Zheng, University of Queensland
This paper addresses the problem of estimating link flows on a road network by combining traffic volume and trajectory data. While traffic volume data from loop detectors have been the most commonly used data for link flow estimation, the volume observations are often available only on a limited number of links and, thus, it is desirable to incorporate other data sources such as vehicle trajectory data collected from vehicle tracking sensors (e.g., GPS, Bluetooth, and WiFi). Trajectory data are, however, still sparse in that a trajectory sample only represents a small subset of the whole population, where the exact sampling rate (the percentage of vehicles captured by a given trajectory dataset) is unknown and may vary over space and time. In this paper, we develop methods to leverage these two limited data sources to enhance link flow estimation. A novel generative modelling framework is proposed, where we use reinforcement learning approaches to learn drivers’ route choice behaviours in observed trajectories and make generalisation from trajectory sample to vehicle population to reconstruct population trajectories that produce the observed traffic volumes. The generated trajectories are then used to estimate link flows across the whole network. The experiment results on grid networks show the proposed methods can accurately estimate unobserved link flows given limited link volume and sparse trajectory data.
Network Assignment-Based Estimation of Origin-Destination Matrices with a Full Travel Demand Model
William Alexander, University of Texas, AustinShow Abstract
Carlin Liao, University of Texas, Austin
Rishabh Thakkar, University of Texas, Austin
Karthik Velayutham, University of Texas, Austin
Stephen Boyles, University of Texas, Austin
In the network modeling community, traditional techniques for origin-destination matrix estimation (ODME) focus on adjusting the OD matrix directly, or on tuning the parameters of the distribution model. These approaches are prone to overfitting and reduce the behavioral interpretation of the OD matrix. Instead, we propose tuning parameters in trip generation, the earliest stage of the traditional four-step model. Our procedure calibrates an initial estimate of trip generation rates by using a local search to reduce the error between the network flows predicted by a demand model and field link flow observations as a proxy for finding the true (but unobservable) trip generation rates. In our experiments, we use synthetic data to investigate the effectiveness of this technique in matching unknown trip generation rates based only on ``observed'' link flows from the travel demand model. We show across scenarios in the Sioux Falls and Chicago Sketch networks that our method reduces link flow RMSE by an average of at least 47.1% and parameter RMSE by 26.2%, relative to initial estimates. Using our results, we identify how to set the local search termination criterion for consistent performance across scenarios, and how to adjust the demand model to prioritize reducing error for the trip generation rates of greatest consequence.
A Congested Schedule-based Dynamic Transit Passenger Flow Estimator Using Stop Count Data
Qi Liu, New York UniversityShow Abstract
Joseph Chow (firstname.lastname@example.org), New York University
A dynamic transit flow estimation model based on congested schedule-based transit equilibrium assignment is proposed using observations from stop count data. A solution algorithm is proposed for the mathematical program with schedule-based transit equilibrium constraints (MPEC) with computational complexity of O(N^2 L) where N and L represent the number of stops and transit lines respectively. The equilibrium constraints corresponding to the schedule-based hyperpath flow is adapted from the literature with some modifications to fit it into an estimation problem. Computational experiments are conducted first to verify the methodology with two synthetic data sets (one of which is Sioux Falls), followed by a validation of the method using bus data from Qingpu District in Shanghai, China from July 1, 2016, with 4 bus lines, 120 segments, 55 bus stops, and 120 one-minute intervals; this is one of the largest implementation of the schedule-based assignment model with congestion effects in the literature and the first for passenger flow estimation based on it. The estimation model converged to 0.005 tolerance of relative change in 10 iterations. The estimated average of segment flows are only 2.5% off from the average of the observed segment flows; relative errors among segments are 42.5%, which compares well with OD estimation methods applied to real data in the literature (e.g. Irvine network, Brescia motorway).
Efficient Computation of Optimal Traffic Assignment in Nationwide Highway Networks from Raw Loop Detector Data
Alexander Roocroft (email@example.com), University of SheffieldShow Abstract
Muhamad Azfar Ramli, Institute of High Performance Computing, A*STAR
Giuliano Punzo, University of Sheffield
The ability to effectively compute optimal traffic flow patterns for real-world large scale highway networks is important for planners to understand the deviation between the desired efficiency of the system versus the observed traffic flows due to selfish driving behaviour. In this article, we present a novel approach to compute the optimal traffic flows through an entire network. This is done by obtaining the congestion function through a density-based fitting of parameters on the well-known Bureau of Public Roads congestion function using raw loop detector data which has so far mainly been applied to a single road sensor. Our approach is compared to the other known method in literature using Inverse Optimisation which also mainly takes in raw loop counter data as input and does not require prior knowledge of the associated origin-destination matrix for the particular network. The methods were applied to three subnetworks of the England Strategic Road Network using loop detector data taken from the Motorway Incident Detection and Automatic Signalling (MIDAS) system in the Manchester and Birmingham area. Our results showed that the majority of the results obtained for system optimal flows were fairly similar while user-optimal flows obtained from the density-based fitting were more consistent with the observed flows with a significant outlier obtained for the Inverse Optimisation method. Moreover, our procedure proved to be significantly less computationally intensive especially when applied to larger networks. The final results were used to compute the deviation between system-optimal and user-optimal performance known as the Price of Anarchy.
A Stochastic Multi-Agent Optimization Framework for Interdependent Transportation and Power System Analyses
Zhaomiao Guo (firstname.lastname@example.org), University of Central FloridaShow Abstract
Fatima Afifah, University of Central Florida
Junjian Qi, University of Central Florida
We study the interdependence between transportation and power systems considering decentralized renewable generators and electric vehicles (EVs). We formulate the problem in a stochastic multi-agent optimization framework considering the complex interactions between EV/conventional vehicle drivers, solar/conventional generators, and independent system operators, with locational electricity and charging prices endogenously determined by markets. We show that the multi-agent optimization problems can be reformulated as a single convex optimization problem and prove the existence and uniqueness of the equilibrium. To cope with the curse of dimensionality, we propose ADMM-based decomposition algorithm to facilitate parallel computing. Numerical insights are generated using standard test systems in transportation and power system literature.
An improved PBCD method for the parallel computing of traffic assignment problem
Zewen Wang, Southeast UniversityShow Abstract
Kai Zhang, Southeast University
Xinyuan Chen, Hong Kong Polytechnic University
Meng Wang, Huawei Technologies Co. Ltd.
Zhiyuan Liu (email@example.com), Southeast University
This paper presents an improved Parallel Block-Coordinate Descent (iPBCD) algorithm for solving the user equilibrium traffic assignment problem. The iPBCD algorithm is developed based on the state-of-the-art parallel block coordinate descent algorithm (PBCD). A different type of flow update policy is studied and investigated to further enhance the robustness of the algorithm. Numerical experiments indicate that indices grouping rules have significant impact on the convergence, and the information-based grouping rule performs well in terms of convergence and efficiency. A greedy update order of block indexes is introduced to optimize the simple strategies adopted in the original PBCD algorithm. Besides, a sensitivity analysis of the parallel level is conducted to identify the optimal one. The numerical examples show the effect of the iPBCD algorithm.
Performance of Reservation-Based Carpooling Service under Detour and Waiting Time Restrictions
Yanfeng Ouyang (firstname.lastname@example.org), University of Illinois, Urbana-ChampaignShow Abstract
Haolin Yang, University of Illinois, Urbana-Champaign
Carlos Daganzo, University of California, Berkeley
This paper focuses on reservation-based carpooling services, e.g. those provided by Scoot and Waze Pool, where travelers are matched up well ahead of their trips so that the driving is done by one the travelers sharing part of its trip with another rider. The impacts of guaranteeing maximum rider waits and driver detours are explored. This paper provides a basis for analyzing the economic feasibility of such service guarantees by (i) developing formulas for the percent of rides that can be matched under a variety of scenarios and guarantee levels; (ii) quantifying the impacts of guarantee levels on the expected vehicle distance traveled. These formulas are verified by outputs from state-of-art matching algorithms using simulated data under a range of parameter values.
DISCLAIMER: All information shared in the TRB Annual Meeting Online Program is subject to change without notice. Changes, if necessary, will be updated in the Online Program and this page is the final authority on schedule information.