A use of information and communication technologies in the framework of advanced management of transportation systems: dynamic OD matrix estimation

A use of Information and Communication Technologies in the framework of Advanced Management of Transportation systems: Dynamic OD Matrix Estimation Lídia Montero, Jaume Barceló and M.Bullejos, Statistics and Operations Research Dept. Technical University of Catalonia-UPC Barcelona, Spain (lidia.montero, jaume.barcelo, manuel.bullejos)@upc.edu Abstract—Origin-Destination (OD) trip matrices are the primary data input used in principal traffic and transit models, which describe the patterns of trips/passengers across the area of study. In this way, OD matrices become a critical requirement in Advanced Transport Management and/or Information Systems that are supported by Dynamic Assignment models. In the future, once combined dynamic traffic and transit assignment tools will be available to practitioners, the problem of estimating the time-dependent number of trips/passengers between transportation zones would be a critical aspect for real applications. However, because OD matrices are not directly observable, the current practice consists of adjusting an initial or seed matrix from link/segment counts which are provided by an existing layout of traffic counting stations or data gathering in the field (detection layout) for non-dynamic models. The typical approaches to time-dependent OD estimation have been based either on Kalman-Filtering or on bi-level mathematical programming approaches that can be considered in most cases as ad hoc heuristics. The advent of the new Information and Communication Technologies (ICT) makes available new types of real-time traffic and passenger data with higher quality and accuracy, allowing new modeling hypotheses which lead to more computationally efficient algorithms. This paper presents a Kalman Filtering approach that explicitly exploits data available from Bluetooth sensors to simplify an underlying space-state model, and describes the validation of the proposal through a set of simulation experiments, either on networks or corridors. Those involve car data provided by the detection of the electronic signature of on-board devices. Finally, an extension of the framework to the estimation of passenger matrices is addressed when data from passenger’s electronic signature devices are available. KeywordsInformation Systems, Advanced Traffic Management, Dynamic OD matrix, linear Kalman-filtering, spacestate models I. INTRODUCTION Over the next 25 years, demand for liquid fuels will be increasing more rapidly in the transportation sector than in any other end-use sector [1]. A primary factor in the projected increase of energy demand for transportation is the steadily rising demand for personal travel but at a time when the environmental implications of modern life are scrutinized, reducing the energy spent on transport is a key objective for achieving sustainability for our way of life. Future trends in transportation demand will be influenced by government policies directed at reducing emissions and congestion while promoting alternative fuels, new vehicle technologies, and mass transit. Conceptually, the basic architectures of Advanced Traffic Information Systems (ATIS) and Advanced Traffic Management Systems (ATMS) mainly share the same model components; Fig.1 depicts schematically that of an integrated generic ATMS/ATIS: • A road network equipped with detection stations, which provides the data supporting the applications in a timely fashion. • A Data Collection system collecting raw real-time traffic data that must be filtered and checked before being used by the models supporting the management system. • An ad hoc Historic Traffic Database storing the traffic data used by traffic models in combination with the real-time data. • Dynamic Traffic and Transit models aimed at estimating and short term forecasting the traffic state, fed with realtime and historic data. • Time Dependent Origin-Destination (OD) matrices are inputs to models for Advanced Traffic Management. The estimation algorithms combine real-time and historic data along with other inputs which are not directly observable. • Estimated and predicted states of the network are compared with the expected states. If the comparison is OK, then no action is taken; otherwise, a decision is made (traffic policy) to achieve the desired objectives. 978-1-61284-875-4/12/$31.00 ©2012 IEEE Figure 1. Conceptual approach to ATIS/ATMS architecture We draw attention in this paper to the main requirement of ATIS/ATMS: the estimation of time-dependent Origin to Destination (OD) matrices from measurements of traffic or transit variables. We assume that the usual traffic data collected by inductive loop detectors (i.e. volumes, occupancies and speeds) are complemented by accurate measurements of travel times and speeds between two consecutive sensors based on new technologies able to capture the electronic signature of specific devices, either on-board devices for cars or mobile phones for passengers in public transportation lines. The sensor captures the public parts of the Bluetooth or WiFi signals within its coverage radius, the most relevant being the MAC address, whose uniqueness makes it possible to use a matching algorithm to log the device when it becomes visible to the sensor. A vehicle/passenger equipped with a Bluetooth device traveling along the network is logged and time-stamped at time t1 by the sensor at location 1. After traveling a certain distance it is logged and time-stamped again at time t2 by the sensor at location 2 downstream. The difference in time stamps IJ = t2 – t1 measures the travel time of the trip with that mobile device. The speed is also measured, assuming that the distance between both locations is known. Data captured by each sensor is sent to a central server by wireless telecommunications for processing. The basic principles on how these sensors operate are depicted in Fig. 2. Figure 2. Vehicle monitoring with bluetooth based sensors Traffic detectors are usually the means for measuring fundamental traffic variables (i.e. flows, speeds and occupancies), whose values determine the state of the traffic system. Origin-to-Destination trip matrices describe the number of trips between any origin-destination pair in a traffic network. A pilot project was conducted north of Barcelona (Spain) on a 40 km long section of the AP-7 Motorway, between Barcelona and the French border and it has been reported in [2]. The project was addressed to validate the use of Bluetooth (BT) data for traffic estate estimation. All formulations of static traffic or transit assignment models [3], as well as dynamic [4, 5, 6, 7], assume that a reliable estimate of an OD is available. However, OD matrices are not yet directly observable, even less so in the case of the time-dependent OD matrices that are necessary for Dynamic Models; consequently, it has been natural to resort to indirect estimation methods. These indirect estimation methods are the so-called matrix adjustment methods, whose main modeling hypothesis can be stated as follows: if the number of trips in the links/segments defined in a network are the consequence of the assignment of an OD matrix onto a network, then, if we are capable of measuring vehicles per link (passengers by segment of transit line), the problem of estimating the OD matrix that generates such loading can be considered as the inverse of the assignment problem. Since the earlier formulation of the problem by Van Zuylen and Willumsen [8], the matrix adjustment problem has been a relevant research and practical problem. Bi-level methods based on traffic assignment or transit assignment problem in the inner-level models are widely propose in literature and use in practical transportation planning studies The adequacy of the detection layout strongly determines the quality of the adjusted OD matrices. The usual approaches to the Detection Layout problem assume that detectors are located at network links, although some proposals to locate detectors on intersection have been developed and seem more suitable to real-time data collected by emerging Information and Communication Technologies [9]. Route choice models describe how trips select the available paths between origins and destinations and, as a consequence, the number of trips using a given path in private transportation modes. In other words, they describe the path flows or the path flow proportions, depending on whether we refer to the number of trips using a path or to the fraction of trips using a path, with respect to the total number of trips between the corresponding origin and destination. This first prototype for dynamic OD matrix estimation was programmed in MatLab and the formulation did not allow multiple paths between origindestination zones [2]. We extended the original formulation suitable for freeways to general network structures in [10]. Currently, we are working with counts and travel times provided by BT on-board devices in a pilot study in the medium-size urban network of Eixample district in Barcelona. The site is being equipped with BT sensors, according to [2], but data are not available yet. To test the approach to dynamic OD matrix estimation, we have conducted three large sets of simulation experiments with AIMSUN simulator [11] to emulate BT equipped vehicles. Firstly, we tested an urban freeway in Barcelona --a 11.551-km-long section of the Ronda de Dalt-- between the Trinitat and the Diagonal Exchange Nodes. The site has 11 entry ramps and 12 exit ramps on the section being studied, fully equipped on ramps, which flows in the direction of Llobregat (to the south of the city), in fact, it is a particular case of a network structure, i.e. a linear freeway. Secondly, a small urban network modeling Amara district in Donosti (north of Spain) was considered, with 232 links, 142 nodes and 85 OD pairs, with a rich structure of alternative paths between OD pairs, totaling 358 paths according to Dynamic User Equilibrium OD paths for the selected demand matrix computed with Dynameq [12], the detection layout was considered to be of 48 ICT detectors. Eixample district in Barcelona is being used for the final validation of the linear Kalman-filter formulation [13] developed by the authors. The selected time-horizon is 1h and 15 min, with subintervals of 1.5 to 5 min. The scenario contains 877 OD pairs and a set of almost 2000 OD paths define the state variables in the formulation, these paths correspond to the set of “most likely OD paths” according to the Dynamic User Equilibrium behavioral hypothesis (those accounting for more than 5% of the total OD flows in the whole horizon of simulation). Equipped and non equipped vehicle data are emulated with AIMSUN [11] and the dynamic OD estimation process is coded in MatLab. Firstly, we outline the the Kalman filter formulation. Secondly, we describe the design of the experimental tests by simulation and present some results. Thirdly, we consider some conclusions and lines for further research. II. FORMULATION The space-state formulations based on Kalman Filtering have always been an appealing approach to the estimation of time dependent OD matrices. In this paper we propose a recursive linear Kalman-Filter for state variable estimation that combines and modifies the earlier works in [4,5,6,7], adapting their models to take advantage of travel times and traffic counts collected by both tracking Bluetooth equipped vehicles and conventional detection technologies. A basic hypothesis is that equipped and non-equipped vehicles follow common OD patterns. We assume that this holds true in what follows and that it requires a statistical contrast for practical applications. Expansion factors for everything from equipped vehicles to total vehicles, in a given interval, can be estimated by using the inverse of the proportion of ICT counts to total counts at centroids; expansion factors are assumed to be shared by all OD paths and pairs with a common origin centroid and initial interval. We model the time-varying dependencies between measurements (sensor counts of equipped vehicles) and state variables (deviates of equipped OD path flows), adapting an idea of Lin and Chang [7], for estimating discrete approximations to travel time distributions. The estimation of these distributions is made on the basis of flow models which induce nonlinear relationships that require extra state variables, leading to a non linear KF approach. Since our approach exploits the travel ICT time measurements from equipped vehicles, we can replace the nonlinear approximations by estimates from a sample of vehicles. This has advantages that constitute a major contribution of this paper because no extra state variables for modeling travel times and traffic dynamics are needed, since sampled travel times are used to estimate discrete travel time distribution (H bins are used for adaptive approximations). Additionally, travel times collected from ICT sensors are incorporated into the proposed model and it is not necessary that vehicles reach their destination, since at any intermediate sensor that they pass by the travel time measured from the entry point (centroid) to that sensor updates the discrete travel time approximation. No information about trajectories of equipped vehicles is used in this version. The approach assumes an extended state variable for M+1 sequential time intervals of equal length Δt, M is the maximum number of time intervals required for vehicles to traverse the entire network in a congested scenario. The solution provides estimations of the OD matrices for each time interval up to the k-th interval. State variables () kgijc Δ are deviations of OD path flows () kgijc relative to historic OD path flows () kgijc ~ for equipped vehicles. III. DESIGN OF COMPUTATIONAL EXPERIMENTS The simulation experiments for testing the proposed approach have been conducted using an historic dynamic OD matrix sliced into 15-minute slices to emulate demand variability, corresponding to a rise in congested conditions. This OD, considered the true historical OD matrix, has been determined through simulation by building the Macro Fundamental Diagram (MFD) for the network (Daganzo and Geroliminis [14]). Therefore, congestion is not a design factor in these experiments. Microscopic simulation with AIMSUN induces variability in the historical inputs in a realistic way and produces target OD flows per interval (related to the true historical OD matrix) and provide the inputs to the KFX model in terms of counts for ordinary and BT equipped vehicles and travel times from entry i to BT sensor q. Fig. 3 depicts the methodological framework for the simulation experiments. The assumed OD matrix is the result of applying some perturbation to the true historical matrix, related to the design, from most to less important factors according to provisional results encountered so far: firstly, BT (ICT technology, in general) penetration rates; secondly, the quality of the historic OD matrix, in patterns and flow magnitudes, and last, but not least, the structure of a priori variance-covariance matrices involved in the Kalman filter. Figure 3. Methodological Design Of The Experimenst By Simulation Target OD flows per interval are compared with estimated OD flows (filtered OD flows) per interval at OD pair level by means of U Theil’s coefficient and the normalized root mean square error (RMSEN). Weighted indicators for subsets of OD pairs (usually subset of OD pairs whose hourly flow is in 25% of higher flows) and a weighted global indicator for the whole set of OD pairs are also computed (GU, GRMSEN). IV. CONCLUSIONS The computational experiments show that the proposed linear Kalman-Filtering approach to dynamic OD matrix estimation provides good estimates of target values in the simulation tests in network and freeway sites. BT data simplifies the dynamic estimation of OD matrices by a KF approach because it is a linear filter and reduces the computational burden when compared to well-known formulations in the literature that use Extended Kalman Filter. The strategy of collecting the DUE most likely used paths according to Dynamic Equilibrium models --and, thus, defining KFX state variables-- seems promising, since time-dependent path proportion shares and assignment matrices are not employed in the formulation. The horizon of study has to be divided in time intervals of length Δt, usually 1.5 to 5 minutes, depending on the network size (and travel times involved), OD flows and BT penetration rates. OD pairs with large volumes are not seriously affected neither by the quality of the assumed historical matrix nor by BT penetration rates under 50% (around 20% in real sites) and thus the proposed KF approach for dynamic OD matrix estimation exhibits good convergence properties that are needed for practical applications in urban networks, corridors and freeways. Further lines of research consider the case of a public transportation network as being the subject of study, thus, Origin-to-Destination matrices describe the number of passengers between OD pairs or origin-to-destination stations. We are adapting previous proposals [15, 16] to the dynamic case. Optimal strategy models in transit assignment describe stations and transfers where transit lines are combined to satisfy trip needs. Strategies in transit assignment models are generalization of the path concept for traffic models, we are now in the process of adapting the Kalman filter equations. ACKNOWLEDGMENT This research is funded by projects MITRA (TRA200914270) and TRA2011-27791-C03-02 of the Spanish R+D National Programs and has benefited from participation in EU COST Action TU0903 MULTITUDE – Methods and tools for supporting the Use caLibration and validaTIon of Traffic simUlation models. REFERENCES [1] International Energy Outlook 2011, United States Department of Energy - Washington, DC. http://www.eia.doe.gov/oiaf/ieo/index.html. Retrieved on Setember 2011. [2] J. Barceló, L. Montero, L. Marqués and C. Carmona, “Travel time forecasting and dynamic of estimation in freeways based on Bluetooth traffic monitoring”, Transportation Research Records: Journal of the Transportation Research Board, 2010, Vol. 2175, pp. 19-27. [3] M. Florian and D. Hearn, “Network Equilibrium Models and Algorithms”, Chapter 6 in: M.O. Ball et al., Eds., Handbooks in OR and MS, Vol.8, 1995, Elsevier Science B.V. [4] C. Antoniou, M. Ben-Akiva and H.N.Koutsopoulos, “Nonlinear Kalman Filtering Algorithms for On-Line Calibration of Dynamic Traffic Assignment Models” IEEE Transactions on Intelligent Transportation Systems, 2007, Vol. 8 No.4. [5] K. Ashok and M. Ben-Akiva, “Alternative Approaches for Real-Time Estimation and Prediction of Time-Dependent Origin-Destination Flows”, Transportation Science 34(1), 2000, pp. 21-36. [6] S. Hu, S.M. Madanat, J. Krogmeier and S. Peeta “Estimation of Dynamic Assignment Matrices and OD Demands using Adaptative Kalman filtering”, Intelligent Transportation Systems Journal vol. 6, 2001, pp 281-300. [7] P. Lin, G. Chang, “A generalized model and solution algorithm for estimation of the dynamic freeway origin-destination matrix”. Transportation Research B 41, 2007, pp. 554-572. [8] J.H. Van Zuylen and L.G. Willumsen, “The most likely trip matrix estimated from traffic counts” Transportation Research 14B, 1980, pp. 281-293. [9] J. Barceló, F. Gilliéron, M.P. Linares, O. Serch and L. Montero, “The Detection Layout Problem” Paper #12-2056, Presented at the 91st Annual TRB Meeting, 2012, accepted for publication in Transp.Res.Record. [10] J. Barceló, L. Montero, M. Bullejos, O. Serch and C. Carmona “A Kalman Filter Approach for the Estimation of Time Dependent OD Matrices Exploiting Bluetooth Traffic Data Collection”, 2011, submitted to the Journal of Intelligent Transport Systems, unpublished, in revision process. [11] AIMSUN 7.0 Traffic Simulator, distributed by Transport Simulation Systems, 2011. [12] Dynameq, (2010), Version 1.4.6, INRO www.inro.ca. [13] R.E. Kalman “A new approach to linear filtering and prediction problem”. Journal of Basic Engineering 82 (1), 1960, pp. 35–45. [14] Daganzo, C. F. and N. Geroliminis An analytical approximation for the macroscopic fundamental diagram of urban traffic. Trans. Res. B 42, 2008. [15] V.Kostakos, T. Camacho and C. Mantero, “Wireless detection of end-toend passenger trips on public transport buses”. In proceedings of the IEEE Conference on Intelligent Transportation Systems, Funchal, Portugal, (2010). pp. 1795-1800. [16] W. Wang, J.P. Attanucci and N.H.M.Wilson, “Bus Passenger OriginDestination Estimation and Related Analyses Using Automated Data Collection Systems”. J. Public Transportation, Vol. 14, No. 4, 2011, pp 131-150. HISTORIC OD MATRIX MICROSCOPIC SIMULATOR KFX DYNAMIC OD ESTIMATOR EMULATED TRAFFIC DATA PERTURBATION OD MATRIX TARGET OD MATRIX ASSUMED HISTORIC OD MATRIX ESTIMATED OD MATRIX COMPARISON TARGET VS FIT