Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1
Guanzhou Li
 -- 1618 2023-10-19 13:40:58 |
2 Reference format revised.
Lindsay Dong
 + 2 word(s) 1620 2023-10-23 03:08:55 |

Video Upload Options

Do you have a full video?
Send video materials Upload full video

Confirm

Are you sure to Delete?
Yes No
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
Li, G.; Wu, J.; He, Y.; Li, D. Origin-Destination Estimation. Encyclopedia. Available online: https://encyclopedia.pub/entry/50553 (accessed on 11 May 2024).
Li G, Wu J, He Y, Li D. Origin-Destination Estimation. Encyclopedia. Available at: https://encyclopedia.pub/entry/50553. Accessed May 11, 2024.
Li, Guanzhou, Jianping Wu, Yujing He, Duowei Li. "Origin-Destination Estimation" Encyclopedia, https://encyclopedia.pub/entry/50553 (accessed May 11, 2024).
Li, G., Wu, J., He, Y., & Li, D. (2023, October 19). Origin-Destination Estimation. In Encyclopedia. https://encyclopedia.pub/entry/50553
Li, Guanzhou, et al. "Origin-Destination Estimation." Encyclopedia. Web. 19 October, 2023.
Origin-Destination Estimation
Edit
This entry is adapted from the peer-reviewed paper 10.3390/app132011257

The origin–destination matrix (OD matrix) reflects the expected movement intensity of road users, where each element is the number of trips between the two traffic analysis zones (TAZs). It can represent the traffic demand over different time scales, from hours to years, corresponding to the dynamic and static OD inference problem, respectively. In the short term, it can be applied both as the initial input to the simulator and to boost the precision of short-term traffic flow forecasts. In the long term, the OD matrix provides the details on the average daily mobility needs of city’s inhabitants and can help assess the urban layout’s rationality and plan future infrastructure development.

origin–destination estimation OD estimation

1. Introduction

The primary challenge in obtaining origin–destination(OD) matrices lies in the inherent difficulties of directly observing traffic demand, and the inverse engineering of traffic assignment is a viable option, since OD estimation and traffic assignment are a pair of endogenous and inseparable processes [1]. The OD estimation issue has been receiving continuous attention due to its significance. In the era of Intelligent Transportation Systems (ITS), the greater variety of data sources and advanced algorithms provides new opportunities for resolving this age-old problem more accurately and efficiently. The data for OD estimation can be derived from traffic counts [2], automatic vehicle identification [3][4][5], cellphone signaling [6][7], and floating vehicle tracks [8][9][10]. With these data, numerous novel and practical methods have been devised such as Probabilistic Tensor Factorization [11], Hierarchical Flow Network [12], Res3D [5], Path/Subpath-based Model [13][14], etc.
However, these multi-source data are not readily available in any scenario, and traffic count data remain among the most accessible data in the transportation domain. They refer to the number of vehicles that pass each road during a specific period, which can come from manual counting, loop detection, and video recognition. With these data, there were generally three branches of methods developed: Constrained Optimization, Iterative State Estimation (Kalman Filter), and Gradient-based Estimation (Simultaneous Perturbation Stochastic Approximation, Neural Networks).
Despite relentless progress, estimating the OD matrix from traffic count remains an interesting but challenging task. The uncertainty of traffic demand patterns, path selection, and traffic dynamics makes the OD estimation an under-determined problem, where unknown variables outnumber the recognized ones. To address this, the quasi-dynamic assumption has been proposed, which implies that the OD matrix remains stable for a short period, and the relatively changing demand structure can be estimated by more frequent observations of traffic counts [15][16][17]. Attempts have also been made to determine the basic demand structures by introducing prior matrices or additional assumptions. However, since the traffic demand patterns/structures in reality are diverse [18], the prior distribution from a handful of prior matrices or prior assumptions is inevitably different from the real one, called distribution shift. The distribution shift makes the well-calibrated model not necessarily generalize well to inferring OD matrices with different demand structures. Machine learning provides an excellent way to establish probabilistic mapping from traffic count to OD matrices with various traffic demand structures [12][19][20].

2. Origin-Destination Estimation

2.1. Data Sources for OD Estimation

Traffic counts are the earliest and most fundamental data in OD estimation [21][22]. Nevertheless, much of the information about trips, including route choice, departure, and arrival time, is not directly reflected in traffic count data. With the development of big data in the era of ITS, much additional data are being used to improve the accuracy of OD estimation, including data from automatic vehicle identification (AVI) [3][23][24], Bluetooth MAC scanner [13], mobile device and GPS [25][26], floating cars [10][27], and smart card records [28].
AVI and Bluetooth-scanning data gather the vehicle identification information and corresponding timestamps. By re-identifying the same vehicle at another location after the initial identification, complete or partial travel path information of the vehicle can be obtained. Recent work has pointed to the existence of a minimum sampling rate that guarantees estimation accuracy using AVI data [24]. The sampling rate is restricted by deployment of roadside AVI devices, the penetration rate of vehicle-side devices, and the accuracy of identification, making it challenging to achieve the desired accuracy in many cities.
Mobile device data includes cellular signaling token [26] and mobile positioning data [29]. It is frequently employed in crowd mobility modeling thanks to the high coverage of cellphones [30]. However, when applying mobile device data to the OD estimation, there are challenges of matching cellphone users with specified roads and traffic modes, and trade-offs between coarse spatial–temporal resolution and privacy protection.
Floating Car Data (FCD) contains detailed spatio-temporal trajectories of a subset of vehicles in the road network, typically from taxis equipped with positioning systems. As a sample of the complete traffic flows, the OD matrix from FCD can be scaled up in a statistical sense into the OD matrix for the full traffic volume. Additionally, FCD can be availed to obtain traffic status, including road travel times and turning rates at intersections. Nevertheless, FCD might be a biased sampling of the entire traffic flow in time and space, influenced by low penetration rates and operating characteristics [16] (e.g., tendency to gravitate to areas with higher demand; higher nighttime share relative to private cars).
Integrating multiple sources of data in OD estimation is undoubtedly a promising future direction. However, in different cities and application scenarios, the availability and usability of additional data sources are not identical, and integrating multi-source data at different levels of completeness is still challenging. Traffic-count-based OD estimation provides a basic usable solution for different scenarios.

2.2. Constrained Optimization

The solution of the OD matrix can be formalized as a constrained optimization problem. These methods include: Entropy Maximization (EM), Maximum Likelihood Estimation (MLE), and Generalized Least Squares (GLS). In thermodynamics, states with higher entropy are considered to have a higher probability of occurring. Zuylen and Willumsen first introduced the concept of entropy into the OD estimation problem, and expressed the convergence to the most likely demand distribution as entropy maximization [31]. EM establishes clear and intuitive formulas with strong interpretability and can be applied in the absence of a prior matrix. It reaches high accuracy in static OD estimation, but is hard to extend to dynamic OD estimation, and the insufficient modeling of dynamics makes the accuracy decrease when the demand structure changes drastically. Different from EM, which considers all states to be equally likely to occur, MLE hypothesizes the prior distribution of OD flows through experience and calculates the most probable states through a Bayesian model [32][33]. The performance of MLE would benefit from an accurate prior probability, but would also be affected by human-induced errors in the prior experience. GLS directly correlates the observations (i.e., traffic counts) and target variables (i.e., OD flows) through the statistical covariance matrix, and minimizes the errors of observations and target variables simultaneously [34][35]. The original model of GLS lacks consideration of the evolution of traffic demand and traffic flow over time and is susceptible to localized noise. To improve the accuracy and stability, dynamic time windows are introduced into GLS with quasi-dynamic assumptions [15]. Since the principles of the groups of optimization methods are similar, they might also be applied in combination. For instance, Xie et al. presented a combined form of EM and least squares, namely EM-LS [36]. A common limitation of this category of models is the homogeneity of traffic demand structure and traffic assignment pattern, both of which tend to be diverse in reality.

2.3. Iterative State Estimations

The iterative state estimation realizes continuous dynamic OD matrix estimation through auto-regressive error control, mainly using Kalman Filter (KF). This branch of methods has been widely explored since Ashok first introduced the concepts [37]. Since the assumption of linear correlation between variables required by ordinary KF is not satisfied in the OD estimation problem, the Extended KF (EKF) and Unscented KF (UKF) apply local linearization to the nonlinear problem by using local derivatives and sample points, respectively. The linearization process causes a considerable computational burden even for medium-size road network [38], and the Local Ensemble Transformed KF (LETKF) reduces the computational complexity by factoring the state variables into several parallellizable sub-states [39]. Inspired by [15], Marzano et al. introduced the quasi-dynamic assumption and presented quasi-dynamic EKF (QD-EKF) to improve the accuracy and stability of dynamic OD estimation [17]. Generally, the Kalman Filter provides an effective tool for tracking dynamic OD matrices, but the large-scale matrix multiplication in it is sensitive to the initial error, and the incomplete accuracy of the parameters (common in OD estimation) tends to result in amplification of the errors and ultimately leads to significant deviations.

2.4. Gradient-Based Estimations

Gradient-based methods include explicit gradient descent (Simultaneous Perturbation Stochastic Approximation, SPSA [40][41][42][43][44][45]) and implicit gradient propagation (Neural Networks, NNs [3][12][19][46][47][48]). As the name suggests, SPSA simultaneously optimizes both the target variable (OD flows) and the observations (traffic count) by gradient descent. Thanks to its simple expression, SPSA can be conveniently deployed in different road networks. However, it is sensitive to OD flows with significant fluctuations, and thus convergence is not guaranteed under large-scale road networks where traffic demand varies significantly. To address this, Tymakianaki et al. clustered OD flows according to their magnitude and assigned a set of hyper-parameters to each cluster [43], which was named c-SPSA. They further presented Robust SPSA to enhance the stability during the gradient process by employing a hybrid gradient strategy [44]. One of the earliest works using neural networks for OD estimation was the Hopfield Neural Networks used in Ref. [46]. Lorenz et al. applied Multi-Layer Perceptron (MLP) to estimate OD matrix [19]. Wu et al. proposed a multi-layered Hierarchical Flow Network to integrate multiple data sources and estimate travel demand [12]. Afandizadeh et al. compared five machine learning methods on OD estimation problems: K-Nearest Neighbor, Random Forest, LightGBM, MLP, CNN [48]. However, as aforementioned, the distribution shift between data of the training set and test set makes the application of neural networks in the field of OD estimation still limited.

References

  1. Ou, J.; Lu, J.; Xia, J.; An, C.; Lu, Z. Learn, assign, and search: Real-time estimation of dynamic origin-destination flows using machine learning algorithms. IEEE Access 2019, 7, 26967–26983.
  2. Sun, W.; Shao, H.; Shen, L.; Wu, T.; Lam, W.H.; Yao, B.; Yu, B. Bi-objective traffic count location model for mean and covariance of origin–destination estimation. Expert Syst. Appl. 2021, 170, 114554.
  3. Cao, Y.; Tang, K.; Sun, J.; Ji, Y. Day-to-day dynamic origin–destination flow estimation using connected vehicle trajectories and automatic vehicle identification data. Transp. Res. Part C Emerg. Technol. 2021, 129, 103241.
  4. Guo, J.; Liu, Y.; Li, X.; Huang, W.; Cao, J.; Wei, Y. Enhanced least square based dynamic OD matrix estimation using Radio Frequency Identification data. Math. Comput. Simul. 2019, 155, 27–40.
  5. Tang, K.; Cao, Y.; Chen, C.; Yao, J.; Tan, C.; Sun, J. Dynamic origin-destination flow estimation using automatic vehicle identification data: A 3D convolutional neural network approach. Comput.-Aided Civ. Infrastruct. Eng. 2021, 36, 30–46.
  6. Montero, L.; Ros-Roca, X.; Herranz, R.; Barceló, J. Fusing mobile phone data with other data sources to generate input OD matrices for transport models. Transp. Res. Procedia 2019, 37, 417–424.
  7. Wang, Z.; Wang, S.; Lian, H. A route-planning method for long-distance commuter express bus service based on OD estimation from mobile phone location data: The case of the Changping Corridor in Beijing. Public Transp. 2021, 13, 101–125.
  8. Yang, X.; Lu, Y.; Hao, W. Origin-destination estimation using probe vehicle trajectory and link counts. J. Adv. Transp. 2017, 2017, 4341532.
  9. Nigro, M.; Cipriani, E.; del Giudice, A. Exploiting floating car data for time-dependent Origin–Destination matrices estimation. J. Intell. Transp. Syst. 2018, 22, 159–174.
  10. Mitra, A.; Attanasi, A.; Meschini, L.; Gentile, G. Methodology for O-D matrix estimation using the revealed paths of floating car data on large-scale networks. IET Intell. Transp. Syst. 2020, 14, 1704–1711.
  11. Sun, L.; Axhausen, K.W. Understanding urban mobility patterns with a probabilistic tensor factorization framework. Transp. Res. Part B Methodol. 2016, 91, 511–524.
  12. Wu, X.; Guo, J.; Xian, K.; Zhou, X. Hierarchical travel demand estimation using multiple data sources: A forward and backward propagation algorithmic framework on a layered computational graph. Transp. Res. Part C Emerg. Technol. 2018, 96, 321–346.
  13. Behara, K.N.; Bhaskar, A.; Chung, E. A novel methodology to assimilate sub-path flows in bi-level OD matrix estimation process. IEEE Trans. Intell. Transp. Syst. 2020, 22, 6931–6941.
  14. Cipriani, E.; Gemma, A.; Mannini, L.; Carrese, S.; Crisalli, U. Traffic demand estimation using path information from Bluetooth data. Transp. Res. Part C Emerg. Technol. 2021, 133, 103443.
  15. Cascetta, E.; Papola, A.; Marzano, V.; Simonelli, F.; Vitiello, I. Quasi-dynamic estimation of o–d flows from traffic counts: Formulation, statistical validation and performance analysis on real data. Transp. Res. Part B Methodol. 2013, 55, 171–187.
  16. Bauer, D.; Richter, G.; Asamer, J.; Heilmann, B.; Lenz, G.; Kölbl, R. Quasi-dynamic estimation of OD flows from traffic counts without prior OD matrix. IEEE Trans. Intell. Transp. Syst. 2017, 19, 2025–2034.
  17. Marzano, V.; Papola, A.; Simonelli, F.; Papageorgiou, M. A Kalman filter for quasi-dynamic od flow estimation/updating. IEEE Trans. Intell. Transp. Syst. 2018, 19, 3604–3612.
  18. Ma, W.; Qian, Z.S. Estimating multi-year 24/7 origin-destination demand using high-granular multi-source traffic data. Transp. Res. Part C Emerg. Technol. 2018, 96, 96–121.
  19. Lorenzo, M.; Matteo, M. OD matrices network estimation from link counts by neural networks. J. Transp. Syst. Eng. Inf. Technol. 2013, 13, 84–92.
  20. Krishnakumari, P.; van Lint, H.; Djukic, T.; Cats, O. A data driven method for OD matrix estimation. Transp. Res. Procedia 2019, 38, 139–159.
  21. Van Zuylen, H. A method to estimate a trip matrix from traffic volume counts. In Proceedings of the PTRC Summer Annual Meeting, Coventry, UK, 11 July 1978.
  22. Willumsen, L. Estimating the most likely OD matrix from traffic counts. In Proceedings of the 11th Annual Conference of Universities Transport Studies Group, University of Southampton, Southampton, UK, January 1979.
  23. Zhou, X.; Mahmassani, H.S. Dynamic origin-destination demand estimation using automatic vehicle identification data. IEEE Trans. Intell. Transp. Syst. 2006, 7, 105–114.
  24. Rao, W.; Wu, Y.J.; Xia, J.; Ou, J.; Kluger, R. Origin-destination pattern estimation based on trajectory reconstruction using automatic license plate recognition data. Transp. Res. Part C Emerg. Technol. 2018, 95, 29–46.
  25. Ma, J.; Li, H.; Yuan, F.; Bauer, T. Deriving operational origin-destination matrices from large scale mobile phone data. Int. J. Transp. Sci. Technol. 2013, 2, 183–204.
  26. Iqbal, M.S.; Choudhury, C.F.; Wang, P.; González, M.C. Development of origin–destination matrices using mobile phone call data. Transp. Res. Part C Emerg. Technol. 2014, 40, 63–74.
  27. Cao, P.; Miwa, T.; Yamamoto, T.; Morikawa, T. Bilevel generalized least squares estimation of dynamic origin–destination matrix for urban network with probe vehicle data. Transp. Res. Rec. 2013, 2333, 66–73.
  28. Munizaga, M.A.; Palma, C. Estimation of a disaggregate multimodal public transport Origin–Destination matrix from passive smartcard data from Santiago, Chile. Transp. Res. Part C Emerg. Technol. 2012, 24, 9–18.
  29. Ge, Q.; Fukuda, D. Updating origin–destination matrices with aggregated data of GPS traces. Transp. Res. Part C Emerg. Technol. 2016, 69, 291–312.
  30. Phithakkitnukoon, S.; Horanont, T.; Lorenzo, G.D.; Shibasaki, R.; Ratti, C. Activity-aware map: Identifying human daily activity pattern using mobile phone data. In Proceedings of the International Workshop on Human Behavior Understanding, Istanbul, Turkey, 22 August 2010; Springer: Berlin/Heidelberg, Germany, 2010; pp. 14–25.
  31. Van Zuylen, H.J.; Willumsen, L.G. The most likely trip matrix estimated from traffic counts. Transp. Res. Part B Methodol. 1980, 14, 281–293.
  32. Ben-Akiva, M.; Macke, P.P.; Hsu, P.S. Alternative Methods to Estimate Route-Level Trip Tables and Expand on-Board Surveys; Number 1037; National Academies: Washington, DC, USA, 1985.
  33. Aerde, M.V.; Rakha, H.; Paramahamsan, H. Estimation of origin-destination matrices: Relationship between practical and theoretical considerations. Transp. Res. Rec. 2003, 1831, 122–130.
  34. Cascetta, E. Estimation of trip matrices from traffic counts and survey data: A generalized least squares estimator. Transp. Res. Part B Methodol. 1984, 18, 289–299.
  35. Bell, M.G. The estimation of origin-destination matrices by constrained generalised least squares. Transp. Res. Part B Methodol. 1991, 25, 13–22.
  36. Xie, C.; Kockelman, K.M.; Waller, S.T. A maximum entropy-least squares estimator for elastic origin-destination trip matrix estimation. Procedia-Soc. Behav. Sci. 2011, 17, 189–212.
  37. Ashok, K. Dynamic origin-destination matrix estimation and prediction for real-time traffic management system. In Proceedings of the 12th International Symposium on Transportation and Traffic Theory, Berkeley, CA, USA, 21–23 July 1993; pp. 465–484.
  38. Antoniou, C.; Ben-Akiva, M.; Koutsopoulos, H.N. Nonlinear Kalman filtering algorithms for on-line calibration of dynamic traffic assignment models. IEEE Trans. Intell. Transp. Syst. 2007, 8, 661–670.
  39. Carrese, S.; Cipriani, E.; Mannini, L.; Nigro, M. Dynamic demand estimation and prediction for traffic urban networks adopting new data sources. Transp. Res. Part C Emerg. Technol. 2017, 81, 83–98.
  40. Balakrishna, R.; Koutsopoulos, H.N. Incorporating within-day transitions in simultaneous offline estimation of dynamic origin-destination flows without assignment matrices. Transp. Res. Rec. 2008, 2085, 31–38.
  41. Cipriani, E.; Florian, M.; Mahut, M.; Nigro, M. A gradient approximation approach for adjusting temporal origin–destination matrices. Transp. Res. Part C Emerg. Technol. 2011, 19, 270–282.
  42. Balakrishna, R.; Ben-Akiva, M.; Koutsopoulos, H.N. Offline calibration of dynamic traffic assignment: Simultaneous demand-and-supply estimation. Transp. Res. Rec. 2007, 2003, 50–58.
  43. Tympakianaki, A.; Koutsopoulos, H.N.; Jenelius, E. c-SPSA: Cluster-wise simultaneous perturbation stochastic approximation algorithm and its application to dynamic origin–destination matrix estimation. Transp. Res. Part C Emerg. Technol. 2015, 55, 231–245.
  44. Tympakianaki, A.; Koutsopoulos, H.N.; Jenelius, E. Robust SPSA algorithms for dynamic OD matrix estimation. Procedia Comput. Sci. 2018, 130, 57–64.
  45. Ros-Roca, X.; Montero, L.; Barceló, J.; Nökel, K. Dynamic origin-destination matrix estimation with ICT traffic measurements using SPSA. In Proceedings of the 2021 7th International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), Heraklion, Greece, 16–17 June 2021; IEEE: New York, NY, USA, 2021; pp. 1–8.
  46. Gong, Z. Estimating the urban OD matrix: A neural network approach. Eur. J. Oper. Res. 1998, 106, 108–115.
  47. Krishnakumari, P.; Van Lint, H.; Djukic, T.; Cats, O. A data driven method for OD matrix estimation. Transp. Res. Part C Emerg. Technol. 2020, 113, 38–56.
  48. Afandizadeh Zargari, S.; Memarnejad, A.; Mirzahossein, H. Hourly Origin–Destination Matrix Estimation Using Intelligent Transportation Systems Data and Deep Learning. Sensors 2021, 21, 7080.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
Upload a video for this entry
Information
Subjects: Transportation; Transportation Science & Technology
Contributors MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
Guanzhou Li
,
Jianping Wu
,
Yujing He
,
Duowei Li
View Times: 169
Revisions: 2 times (View History)
Update Date: 23 Oct 2023
Table of Contents
    1000/1000
    Hot Most Recent
    Feedback