Heinz College — 99P Labs Capstone Project: Traffic Flow Estimation Using Vehicle Telematics Data
Introduction
Over the course of the Fall 2023 semester, our capstone group from Carnegie Mellon University’s Heinz College embarked on a project that aimed to transform how traffic flow is understood and managed. Our goal was to leverage vehicle telematics data for a more comprehensive view of traffic patterns in Columbus, Ohio.
Understanding traffic dynamics is critical to enabling efficient and sustainable mobility in the ever-changing world of transportation and urban development. Comprehensive traffic flow analysis not only helps to alleviate congestion but also creates the groundwork for informed decision-making in infrastructure development and resource allocation.
Impact of Our Work
Our project is not just about numbers and data; it’s about shaping the future of urban mobility. By delving into the intricacies of traffic dynamics, we aimed to provide local authorities with critical insights. These insights are essential for informed urban planning, enhancing road safety, and ultimately, moving towards a future with zero traffic collision fatalities.
The Highway Performance Monitoring System (HPMS) is a critical national archive for traffic data, useful for identifying patterns and trends for policy formulation and budget allocation. However, the current infrastructure, which consists of approximately 5000 counting stations distributed across the United States, falls short of providing the detail required for full traffic analysis.
This study details the approach, insights, and outcomes of implementing this project in Columbus, Ohio. The collaboration between our team of six students from Heinz College at Carnegie Mellon University and 99P Labs endeavors to illuminate nuanced traffic flow patterns within the city. By amalgamating vehicle telematics with existing databases, we aim to lay the groundwork for more informed and effective traffic management strategies in the Columbus metropolitan area, underpinned by enhanced analysis and visualization.
Project Synopsis
In this project the aim is to use vehicle telematics, points of interest, census, and road inventory data to estimate the traffic counts on a given road segment. The proposed methodology involved three parts: map — matching, implementing machine learning models, and lastly integrating the two workflows. Map matching involved taking the telematics data and placing each data point on a physical road segment that was contained in our existing Geographic Information System (GIS) network. All of the features would then be put through machine learning models to tune and optimize them, in order for them to provide predictions on traffic counts with future feature data. Lastly, both the features (specifically traces of vehicle trips from the telematics data) and the prediction of traffic counts would be displayed on a front end.
A 2-pronged approach: Map Matching and Machine Learning
To best utilize the individual talents of our team members and speed up our development, we divided ourselves into two subteams i.e., one which focused on the map-matching side of things and one which looked into the data and machine learning aspect of the project.
This allowed us to parallelize both workflows which significantly accelerated our timeline and also made sure that all members worked in the domains they were already familiar with.
Project Timeline
Phase 1: Literature Review
In this initial phase, we immersed ourselves in the world of traffic analysis. Our exploration spanned various traffic counting methods, map-matching algorithms, and machine learning techniques. This stage was crucial for setting the direction of our project.
Phase 2: Two-step development and Implementation
As mentioned above, we split into two focused groups — one on GIS and map-matching, another on data science and machine learning. This phase was all about application — turning theory into practice.
Phase 3: Culmination and Integration
The final phase was about synthesis. The two teams brought together their findings, and integrated them. We then used the combined result to develop a pipeline which fed into a machine learning model for estimating vehicle counts for unknown road segments.
Literature Review
Map Matching Algorithms
Map matching algorithms can be categorized into four main four types: geometric, topological, probabilistic, and other advanced techniques [1]. These algorithms can also be divided into incremental and global methods based on the number of sampling points [2].
Geometric map matching algorithms use geometric principle, such as distance, similarity, and other factors, to find the optimal path based on the relationship between point-line and line-line, including point-to-point matching [3], point-to-curve matching [4], curve-to-curve matching [5], and the road reduction filter (RRF) algorithm [6].
Topological map matching algorithms utilize the geometry of the links and the connectivity of the links. This type of algorithm constructs the road network and integrates the local search algorithm to find the optimal path. Common algorithms include weighted topological algorithm [7], simplified map matching algorithm using a topological analysis of the road network [8], cooperative localization algorithm based on topology matching [9], and the curvature integration constrained map-matching method [10].
The probability statistics algorithm is created to estimate the probability distribution of a vehicle’s location along a road network, taking into account the uncertainties in positioning data. Notable approaches to incorporate probabilistic models include a Path-Size Logit model for smartphone GPS data [11], map-searching tree for low-sampling-rate trajectories [12], and an enhanced probabilistic algorithm designed to reconcile imprecise location data with inaccuracies in digital road network information [13].
Advanced models incorporate recently developed techniques, such as fuzzy logic methods [14], support vector machines [15], neural networks [16], and reinforcement learning [17]. Based on this literature review, we explore potential open-source libraries for map matching.
Machine Learning
Traffic flow and speed predictions are more than just numbers on a screen — they’re vital components of Intelligent Transportation Systems, crucial for enhancing road safety, managing traffic, and reducing congestion. The advent of machine learning has opened new doors in this domain, offering more accurate and efficient solutions. Let’s explore how recent studies have leveraged these advancements.
The Art of Data Preprocessing: Laying the Groundwork for Accurate Predictions
Before we delve into complex models, it’s crucial to understand the significance of data preprocessing in traffic prediction. Proper data cleaning, selection, and transformation are the unsung heroes in the world of predictive modeling. They ensure the robustness and accuracy of the models we rely on. For instance, the use of Kalman filtering in real-time traffic flow prediction has shown the seamless integration of traditional statistical methods in modern systems. It’s like setting the stage before the main actors (our machine learning models) perform.
Innovative Approaches in Traffic Modeling: From XGBoost to LSTM
XGBoost in Action: Understanding Traffic Through Insurance Claims
A fascinating study by A.R Williams and team delves into telematics data within the context of insurance claims [18]. They employed an XGBoost model to sift through the data, extracting features that help categorize drivers for insurance purposes. This approach sheds light on the diverse applications of machine learning in traffic analysis and beyond.
Deciphering Driver Behavior: A Statistical Approach
Mario V. Wüthrich’s work takes a statistical dive into telematics data, unraveling patterns in driver behavior [19]. This kind of analysis is crucial in understanding the human elements that influence traffic dynamics, providing a more holistic view of transportation systems.
RNN and LSTM: The Cutting Edge of Traffic Prediction
The research by E. Sherafat et al. stands out in its use of Recurrent Neural Networks (RNNs), particularly the attention-based Long Short-Term Memory (LSTM) models [20]. Focusing on a critical segment between Tehran and Chalus in Iran, their study not only underscores the effectiveness of A-LSTM over traditional models in short intervals but also highlights the impact of input variable transformations. The comparison between one-hot and cyclic encodings revealed that cyclic variables offer better performance, marking a significant advancement in the field.
Data Sources
The data sources for this project can be split into those that contain the features for the machine learning and those that contain the target variable that the models are trying to predict.
The target variable data was the traffic counts data that was obtained from the ODOT.
The feature data was obtained from the following sources:
- Vehicle to Everything (V2X)
- Census
- Road Inventory
- Points of Interest (POI)
Each source will be described below.
Target Variable Data
Traffic Counts Data
Traffic counts data are the number of vehicles that have crossed a traffic counter on a particular road segment during a particular 15 minute interval. This data was obtained from the ODOT for one day in October 2019 and is split between cars and trucks. Spatially the counts are split by links or road segments that were provided as being already matched to the ODOT GIS network.
Feature Data
Vehicle to Everything (V2X) Data
The V2X data is the most important set of feature data in this project. This data set contains information regarding trips taken by vehicles in the Columbus area during October 2019. The features include vehicle information such as speed, braking status, steer angle, transmission state, and stability control to name a few. Each trip has a slightly varying sampling frequency but on average sample around 100 data points per second (Hz).
There were 1716 trips originally in this data set but there were 3 data cleaning filters that were used to preprocess the data:
- Removing all rows that contained only not a number (NaN) values
- Removing trips with any geographic discontinuities (Figure 2)
- Removing trips that were stationary for the entirety of the trip duration.
Census Data
Census data was also included on the feature side of the machine learning model to provide additional information about the area surrounding the road segments. Specific parameters of interest included but were not limited to population, demographics, type of usage, social and economic characteristics. The census data did not vary over the course of the time frame that was being considered for the project and therefore we considered it as being time independent. For our purposes, we used it as a method to allow for spatial variations in characteristics between road segments.
Road Inventory Data
Road inventory data was provided to our group as part of the data that had been matched to the ODOT GIS data. Similar to the census, we considered this data to be time independent, yet spatially varying. This data included information such as number of lanes, whether there is a median present, the size of the median, the size of the lanes, and similar attributes.
Points of Interest Data
Point of interest data was included as features to provide more information on the area surrounding the road segments. Points of interest that would potentially be relevant to traffic included arenas, schools, museums, and others in the same vein.
Methodology
Map Matching
The map matching library used by the previous year’s capstone group, Fast Map Matching (FMM) was found to be deprecated and could not be used for the purposes of our project. A very desirable attribute of the FMM library was that on top of taking in the data to be matched, it allowed the user to input the GIS data that it wanted the data to be matched to. This allowed the previous group to match vehicle data onto the ODOT GIS data on which the traffic counts data was already snapped.
After it was determined that the FMM library could not be used for our project, we surveyed available free to use map matching libraries and found two that had comprehensive documentation, clear examples, and projects that had been by third parties completed using these libraries. However, unlike FMM these libraries did allow for the input of GIS files. They instead mapped the data onto OpenStreetMap (OSM), a free to use geographic data set that is maintained by volunteers. Due to the inability to input custom GIS data into these libraries, a new process had to be devised and implemented for map matching.
Libraries
The two libraries that were evaluated were PyTrack and Leuven. These both matched input data onto the OSM.
Updated Map Matching Process
The output from map-matching is provided in OSM coordinates, which differs from the ODOT State Plane Coordinate System (SPCS) used in our systems. This discrepancy between the map-matching results and our required format necessitates a conversion of the map-matching output to align with the ODOT coordinate system.
Calculating direction
The links and counts data processed by our advisor are directional, meaning they vary based on the traffic flow direction of each lane. To ensure an accurate spatial join, it’s essential to consider the direction of traffic flow for each segment. We determine the direction of a segment by calculating the arctangent of the start and end points of the segment. This calculation is then converted into compass bearings, where 0 degrees corresponds to North and 90 degrees to East.
Merging with OSM
After establishing the traffic flow direction for each segment, we can transform the OSM coordinates into the ODOT SPCS format using Geopandas. This allows us to conduct a spatial join with our static dataset. In this process, we retain only those rows where the traffic flow directions match, effectively filtering out any erroneous or spurious joins.
Machine Learning
Data Pre-processing
The dichotomy between Static and Non-Static data forms the cornerstone of our analytical approach. Static data provides a constant backdrop, akin to a reference point in time, while Non-Static data introduces temporal dynamics essential for understanding traffic fluctuations. Our methodology in traffic prediction hinges on the sophisticated integration of these two data categories.
1. Distinct Yet Interconnected: Vehicle Categorization
Our analysis begins with a fundamental categorization of data based on vehicle types, specifically “Cars” and “Trucks”. This distinction is pivotal as it acknowledges the unique impact each vehicle type has on traffic patterns and congestion.
2. Time as a Dimension: Structuring Traffic Data
Envisioning time as a critical dimension, we transformed our data into a ‘Long’ format, incorporating ‘Time’ as a key feature. This structure enables us to capture detailed traffic patterns in 15-minute intervals, offering granular insights into daily traffic movements.
3. Integrating Diverse Data Sources
Our approach integrates three distinct data sources, each contributing unique perspectives to our traffic model:
Road Level Data: This dataset forms the geographical foundation of our model, encompassing Segment IDs and nodes for each road segment.
Census Data: Sourced from government databases, this data enriches our model with demographic and spatial information, represented as polygon geometries. Our technique involves a spatial join with the traffic count dataset, considering the intersection of road segments with census-designated regions.
Points of Interest Data (POI): This data, also in the form of shape files, incorporates geographic coordinates. We conducted a nearest neighbor spatial join to determine the proximity of POIs to road segments, adding another layer of contextual information to our model.
4. The Process of Data Fusion
The fusion of these datasets involved meticulous steps, akin to assembling a complex puzzle. Employing spatial joins and proximity analyses, we combined these diverse datasets into a comprehensive whole, thus enhancing the predictive capabilities of our traffic model.
5. Refining for Predictive Accuracy: Normalization and Encoding
To prepare our dataset for predictive modeling, we applied z-score normalization to numerical features, ensuring a standard scale for all variables. Categorical features were transformed through one-hot encoding, converting them into a format amenable for machine learning algorithms.
Modeling
Choosing the right machine learning model is akin to selecting the right lens to view a complex picture. Our project experimented with three distinct models: Ridge Regression, Random Forest, and XGBoost. Each offers unique advantages and faces specific limitations, shaping the way we understand and predict vehicle counts.
1. Ridge Regression: The Balancing Act
Ridge Regression is like the steady hand in the unpredictable world of traffic prediction. It’s known for its ability to prevent overfitting, thanks to a clever regularization parameter.
Advantages:
Regularization: This is Ridge Regression’s secret weapon, helping to control the complexity of the model.
Efficiency with Multiple Regressors: When dealing with numerous variables, Ridge Regression shines, simplifying what could otherwise be a complex scenario.
Limitations:
Linear Focus: Its Achilles’ heel is an inability to grasp non-linear relationships, which can be crucial in traffic data.
Implementation:
We took cues from the 2022 Capstone Team, applying their hyperparameters and conducting a 5-Fold Cross-Validation for reliability.
2. Random Forest: The Ensemble Performer
Imagine a team where each member brings a unique perspective. That’s Random Forest for you, a model that thrives on diversity and complexity.
Advantages:
Capturing Non-linear Relationships: It sees the twists and turns in data that linear models might miss.
Resilient to Overfitting: Like a well-rooted tree, Random Forest stands firm even when inundated with numerous features.
Implementation:
Since this was something the previous tema had not tried, we used GridSearchCV to fine-tune our model, ensuring we extracted the best it had to offer.
3. XGBoost: The Non-linear Navigator
XGBoost is the detective of machine learning models, uncovering hidden patterns and non-linear relationships with finesse.
Advantages:
Master of Non-linearities: It thrives in the intricate web of traffic data, revealing patterns that others might miss.
Avoids Overfitting: Built-in features in XGBoost prevent the model from getting lost in the forest of data.
Insightful on Feature Importance: It helps us understand which factors are the true influencers in traffic prediction.
Implementation:
Echoing our approach with Random Forest, we employed GridSearchCV for XGBoost, diving deeper into the model’s capabilities and fine-tuning it for optimal performance.
Results
Map Matching
The results from using the PyTrack and Leuven map matching libraries were inconclusive since there were no metrics for evaluating the map matching performance. There were trips (Figure 1) that appeared to be matched well, while others such as the one seen in Figure 2, had great difficulty in being matched.
Overall the updated map matching methodology was successful (Figure 3). However there still exists a need to connect the map matched nodes that are outputted from the libraries to specific data points from the V2X data, in order to get the rest of the V2X features in a specific time frame.
Machine Learning
Our exploration ventured through various models, including Linear Regression with Cross-Validation (CV), Ridge Regression, Random Forest, and XGBoost. Each model was scrutinized based on Mean Absolute Error (MAE), Root Mean Square Error (RMSE), and R² score, revealing their unique strengths and weaknesses in predicting traffic patterns. The below figure shows a summary of all our ablations on different models.
1. The Linear Models: Steady but Limited
Linear Regression with CV and Ridge Regression presented a reasonable performance, showing moderate accuracy. With R² scores over 0.6, they provided a decent fit to the data, yet there was room for improvement, especially in capturing complex traffic dynamics.
2. Random Forest: A Step Up in Complexity
Random Forest emerged as a more powerful contender, especially notable in its basic form with an R² of 0.920547 on the training data. However, a drop in test data performance hinted at overfitting. The introduction of CV and GridSearchCV in Random Forest models fine-tuned their performance, achieving a better balance between training and testing accuracy.
3. XGBoost: The Champion of Complexity
XGBoost models, both standard and enhanced with GridSearchCV, demonstrated exceptional performance. They struck an impressive balance in training and testing, showcasing their capability to handle complex, non-linear traffic data patterns effectively. The XGBoost model, particularly with GridSearchCV, emerged as the top performer, displaying the highest R² score of 0.812126 on the test set.
Understanding What Influences Traffic: Feature Importance
Our journey into feature importance revealed fascinating insights:
Facility Type (FACTYPE): The type of facility profoundly impacts vehicle counts. Commercial areas buzz with more traffic than quieter residential zones.
Public Category (CATEGORY_PUB): Different public facilities, like parks and government buildings, attract varying traffic levels.
Lanes (LANES): More lanes usually mean more vehicles, a straightforward yet critical correlation.
Distance (distance): Traffic thins as we move away from city centers and main roads.
Posted Speed (POSTSPD): Higher speed limits attract more vehicles, but only up to a point.
In the figure below, you can see how the most important features affect vehicle counts. We can observe that only a few of the top features are linearly related, which explains the superior performance of Random Forest and XGBoost compared to vanilla and Ridge Regression.
These insights, visualized in our feature dependence plots, underscore the non-linear and complex nature of traffic patterns, highlighting the effectiveness of XGBoost in modeling these dynamics.
Counts Predictions
The inference results from the dataset offer a comparison between actual vehicle counts and those predicted by the model at various hours and locations denoted by ‘HR’ and ’N’. The performance of the model can be evaluated by examining the percent difference between actual and predicted counts.
Actual Counts vs Predicted Counts (Random Data Selected)
Here, the model predictions vary widely from the actual counts, with differences ranging from underestimates (e.g., at 09:00, the actual count is 29.666667, while the predicted is 61.772640) to overestimates (e.g., at 06:45, the actual count is 12.000000, while the predicted is 81.353104). This indicates a degree of variance in the model’s accuracy across different times and conditions.
Actual Counts vs Predicted Counts (Random Data Selected with 10% margin error)
Looking at the random data filtered with a 10% variance threshold, the results show that the model’s predictions are quite close to the actual figures, with less than a 10% difference in counts. For instance, at 10:15, the actual count is 25.00000 compared to the predicted 24.906212, demonstrating the model’s precision in certain conditions.
Actual Counts vs Predicted Counts (Random Data Selected with 1% margin error)
Further refining the data to a 1% variance threshold, the model’s predictions align even more closely with the actual counts. Samples such as at 14:15, where the actual count is 39.000000 and the predicted count is 38.729008, highlight the model’s high accuracy for specific instances.
In summary, while there are instances of significant variance between actual and predicted counts, the model is capable of making highly accurate predictions within a 10% margin of error in many cases, and can even achieve remarkable precision within a 1% variance for certain data points. This suggests that the model, while not perfect, is generally effective at predicting vehicle counts, especially when the error margin is relaxed to 10%.
Recommendations and Conclusion
Paid map matching packages
One recommendation from the group is to evaluate the availability of paid map matching packages. This would improve the reliability and robustness of the map matching process.
Develop an inhouse map matching algorithm
Another approach would be to put resources into developing an inhouse map matching algorithm. However, this would require a significant amount of time and work.
Obtain counts data with latitude and longitude
Another recommendation would be to obtain counts data that has latitude and longitude information. This would allow for it to be map matched together with the feature data onto OSM.
Limitations and Challenges We Faced
The most significant challenge that was faced by the group was finding out that the map matching library that had been used by the previous years capstone group (FMM) had been deprecated. This caused a shift in our entire semester plan and resulted in the scope of what was achievable in the semester to change significantly.
Improvement Direction
Work remains to be done to connect the rest of the V2X points data apart from the latitude and longitude, in terms of which links does a given vehicle go through at what time in order to match feature data at a given time, with traffic counts data at that same time.
Once this link has been established, the two pipelines will be fully connected and the machine learning models can be properly assessed.
Acknowledgement
The project group would like to acknowledge Sean Qian for all of his support throughout the duration of the project. Sean provided comprehensive and timely feedback that was indispensable.
The group would also like to thank Ryan Lingo and Nithin Santhanam from the 99P labs team for their guidance, encouragement, and feedback during the project. Without their exceptional support, we would not have been able to complete this project.
References
[1] Mohammed Quddus, Washington Yotto Ochieng, and Robert B. Noland, “Current Map-Matching Algorithms for Transport Applications: State-of-the Art and Future Research Directions,” Transportation Research Part C: Emerging Technologies 15, no. 5 (October 1, 2007): 312–28, https://doi.org/10.1016/j.trc.2007.05.002.
[2] Zhengfeng Huang et al., “Survey on Vehicle Map Matching Techniques,” CAAI Transactions on Intelligence Technology 6, no. 1 (March 1, 2021): 55–71, https://doi.org/10.1049/cit2.12030.
[3] Bernstein, David. “An Introduction to Map Matching for Personal Navigation Assistants,” August 1, 1996. https://rosap.ntl.bts.gov/view/dot/38257.
[4] Christopher E. White, David Bernstein, and Alain L. Kornhauser, “Some Map Matching Algorithms for Personal Navigation Assistants,” Transportation Research Part C: Emerging Technologies 8, no. 1–6 (February 1, 2000): 91–108, https://doi.org/10.1016/s0968-090x(00)00026-7.
[5] Bishnu P. Phuyal, “Method and Use of Aggregated Dead Reckoning Sensor and GPS Data for Map Matching,” Institute of Navigation, September 27, 2002, https://www.ion.org/publications/abstract.cfm?articleID=2042.
[6] George Taylor et al., “Road Reduction Filtering for GPS-GIS Navigation,” Transactions in GIS 5, no. 3 (June 1, 2001): 193–207, https://doi.org/10.1111/1467-9671.00077.
[7] Greenfeld, Joshua S. “Matching GPS observations to locations on a digital map.” In Transportation Research Board 81st Annual Meeting, vol. 22, pp. 576–582. 2002.
[8] Yu, Meng. “Improved positioning of land vehicle in ITS using digital map and other accessory information.” (2006).
[9] Choi, Seung-Tak, Woo-Sol Hur, and Seung-Woo Seo. “Cooperative localization based on topology matching.” In 2014 IEEE 6th International Symposium on Wireless Vehicular Communications (WiVeC 2014), pp. 1–5. IEEE, 2014.
[10] Zhe, Z. E. N. G., L. I. Qingquan, Z. O. U. Haixiang, and W. A. N. Jianhua. “Curvature integration constrained map matching method for GPS floating car data.” Acta Geodaetica et Cartographica Sinica 44, no. 10 (2015): 1167.
[11] Bierlaire, Michel, Jingmin Chen, and Jeffrey Newman. “A probabilistic map matching method for smartphone GPS data.” Transportation Research Part C: Emerging Technologies 26 (2013): 78–98.
[12] Tuo, Yupeng, Xiaochun Yun, and Yongzheng Zhang. “MSTM: A novel map matching approach for low-sampling-rate trajectories.” In 2017 IEEE 28th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), pp. 1–7. IEEE, 2017.
[13] Ochieng, Washington Y., Mohammed A. Quddus, and Robert B. Noland. “Map-matching in complex urban road networks.” Brazilian Journal of Cartography (Revista Brasileira de Cartografia) 55, no. 2 (2003): 1–18.
[14] Quddus, Mohammed A., Robert B. Noland, and Washington Y. Ochieng. “A high accuracy fuzzy logic based map matching algorithm for road transport.” Journal of Intelligent Transportation Systems 10, no. 3 (2006): 103–115.
[15] Goh, Chong Yang, Justin Dauwels, Nikola Mitrovic, Muhammad Tayyab Asif, Ali Oran, and Patrick Jaillet. “Online map-matching based on hidden markov model for real-time traffic sensing applications.” In 2012 15th International IEEE Conference on Intelligent Transportation Systems, pp. 776–781. IEEE, 2012.
[16] Shen, Zhihao, Wan Du, Xi Zhao, and Jianhua Zou. “DMM: Fast map matching for cellular data.” In Proceedings of the 26th annual international conference on mobile computing and networking, pp. 1–14. 2020.
[17] Osogami, Takayuki, and Rudy Raymond. “Map matching with inverse reinforcement learning.” In Twenty-Third International Joint Conference on Artificial Intelligence. 2013.
[18] Williams, Allen R., Yoolim Jin, Anthony Duer, Tuka Alhani, and Mohammad Ghassemi. “Nightly Automobile Claims Prediction from Telematics-Derived Features: A Multilevel Approach.” Risks 10, no. 6 (2022): 118.
[19] Wuthrich, Mario V. 2016. “Covariate Selection from Telematics Car Driving Data.” SSRN. December 19. https://ssrn.com/abstract=2887357
[20] Sherafat, Elahe, Bilal Farooq, Amir Hossein Karbasi, and Seyedehsan Seyedabrishami. “Attention-LSTM for Multivariate Traffic State Prediction on Rural Roads.” arXiv preprint arXiv:2301.02731 (2023).
