Maximum probability O-D matrix estimation in large-sized networks

Iranian Journal of Numerical Analysis and Optimization

مقاله 6، دوره 10، شماره 2 - شماره پیاپی 18، آذر 2020، صفحه 105-130   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v10i2.79882

نویسنده

M. Abareshi^*

Department of Applied Mathematics, Faculty of Mathematics and Computer Sciences, Hakim Sabzevari University, Sabzevar, Iran.

چکیده

We propose a maximum probability model to estimate the origin-destination trip matrix in the networks, where the observed traffic counts of links and the target origin-destination trip demands are independent discrete random variables with known probabilities. The problem is formulated by using the least squares approach in which the objective is to maximize the probability that the sum of squared errors between the estimated values and the observed (target) ones does not exceed a pre-specified threshold. An enumeration so lution approach is proposed to solve the problem in small-sized networks, while a normal approximation based on the central limit theorem is applied in large-sized networks to transform the problem into a deterministic nonlin ear fractional model. Some numerical examples are provided to illustrate the efficiency of the proposed method.

کلیدواژه‌ها

Transportation؛ Origin-destination trip matrix؛ Least squares approach؛ Probabilistic traffic counts؛ Fractional programming

مراجع

1. Abareshi, M. and Zaferanieh, M. A bi-level capacitated P-median facility location problem with the most likely allocation solution, Transport. Res. B-Meth. 123 (2019), 1–20.

2. Abareshi, M. and Zaferanieh, M. The network 1-median with discrete demand weights and travel times, Iranian journal of numerical analysis and optimization, 9(1) (2019), 69–92.

3. Abareshi, M., Zaferanieh, M. and Keramati, B. Path flow estimator in an entropy model using a nonlinear L-shaped algorithm, Netw. Spat. Econ. 17 (2017), 293–315.

4. Abareshi, M., Zaferanieh, M. and Safi M. R. Origin-destination matrix estimation problem in a Markov chain approach, Netw. Spat. Econ. 19 (2019), 1069–1096.

5. Abrahamsson, T. Estimation of origin-destination matrices using traffic counts - A literature survey, IIASA Interim Report. IIASA, Laxenburg, Austria: IR-98-021 (1998).

6. Berman, O. and Wang, J. Probabilistic location problems with discrete demand weights, Networks, 44 (2004), 47–57.

7. Berman, O. and Wang, J. The network p-median problem with discrete probabilistic demand weights, Comput. Oper. Res. 37 (2010), 1455–1463.

8. Billionnet, A., Elloumi, S. and Plateau, M. C. Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: the QCR method, Discrete. Appl. Math. 157 (2009), 1185–1197.

9. Carey, M., Hendrickson, C. and Siddharthan, K. A method for direct estimation of origin/destination trip matrices, Transport. Sci. 15 (1981), 32–49.

10. Carey M. and Revelli, R. Constrained estimation of direct demand functions and trip matrices, Transport. Sci. 20 (1986), 143–152.

11. Cascetta, E. Estimation of trip matrices from traffic counts and survey data: A generalized least squares estimator, Transport. Res. B-Meth. 18 (1984), 289–299.

12. Charnes, A. and Cooper, W.W. Deterministic equivalents for optimizing and satisficing under chance constraints, Oper. Res. 11 (1963), 18–39.

13. Ching, W., Scholtes, S. and Zhang S. Numerical algorithms for dynamic traffic demand estimation between zones in a network, Eng. Optimiz. 36 (2004), 379–400.

14. Eppstein D. Finding the K-shortest paths, SIAM J. Comput. 28 (1998), 652–673.

15. Galli, L. and Letchford, A. N. Reformulating mixed-integer quadratically constrained quadratic programs, Working Paper. The Department of Man agement Science, Lancaster University, 2011.

16. Hoang, N.H., Vu, H.L. and Lo, H.K. An informed user equilibrium dynamic traffic assignment problem in a multiple origin-destination stochastic network, Transport. Res. B-Meth. 115 (2018), 207–230.

17. Jones, L.K., Gartner, N.H., Shubov, M., Stamatiadis, C. and Einstein, D. Modeling origin-destination uncertainty using network sensor and survey data and new approaches to robust control, Transport. Res. C-Emer. 94 (2018), 121–132.

18. Jornsten, K. and Nguyen, S. On the estimation of a trip matrix from net work data, Technical report. LiTH-MAT-R-79-36, Department of Mathematics, University of Linkoping, Sweden, 1979.

19. Lu, C., Fang, S.C., Jin, Q., Wang, Z. and Xing, W. KKT solution and conic relaxation for solving quadratically constrained quadratic program ming problems, SIAM J. Optim. 21 (2011), 1475–1490.

20. Ma, W. and Qian, Z. Statistical inference of probabilistic origin destination demand using day-to-day traffic data, Transport. Res. C-Emer. 88 (2018), 227–256.

21. Ma, W. and Qian, Z. Estimating multi-year 24/7 origin-destination demand using high-granular multi-source traffic data, Transport. Res. CEmer. 96 (2018), 96–121.

22. Maher, M.J. Inferences on trip matrices from observations on link volumes: A Bayesian statistical approach, Transport. Res. B-Meth. 17 (1983), 435–447.

23. Misener, R. and Floudas, C.A. Global optimization of mixed integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Math. Program. 136 (2012), 155–182.

24. Nie, Y., Zhang, H.M. and Recker, W.W. Inferring origin-destination trip matrices with a decoupled GLS path flow estimator, Transport. Res. B Meth. 39 (2005), 497–518.

25. Nocedal, J. and Wright, S. Numerical Optimization, 2nd ed, Springer Verlag New York, 2006.

26. Parry, K. and Hazelton, M.L. Bayesian inference for day-to-day dynamic traffic models, Transport. Res. B-Meth. 50 (2013), 104–115.

27. Pitombeira-Neto, A.R., Loureiro, C.F.G. and Carvalho, L.E. A dynamic hierarchical Bayesian model for the estimation of day-to-day origin destination flows in transportation networks, Netw. Spat. Econ. 20 (2020), 499–527.

28. Shao, H., Lam, W.H.K., Sumalee, A., Chen, A. and Hazelton, M. L. Estimation of mean and covariance of peak hour origin-destination demands from day-to-day traffic counts, Transport. Res. B-Meth. 68 (2014), 52–75

29. Spiess, H. A maximum likelihood model for estimating origin-destination matrices, Transport. Res. B-Meth. 21 (1987), 395–412.

30. Stancu-Minasian, I.M. Fractional programming, theory, methods and applications, 1st ed, Springer Netherlands, 1997.

31. Sun, C., Chang, T., Luan, X., Tu, Q. and Tang, W. Origin destination demand reconstruction using observed travel time under con gested network, Netw. Spat. Econ. https://doi.org/10.1007/s11067-020-09496-4 (2020).

32. Sun, C., Chang, Y., Shi, Y., Cheng, L. and Ma, J. Subnetwork origin destination matrix estimation under travel demand constraints, Netw. Spat. Econ. 19 (2019), 1123–1142.

33. Van Zuylen, H. and Willumsen, L.G. The most likely trip matrix estimated from traffic counts, Transport. Res. B-Meth. 14 (1980), 281–293.

34. Wardrop, J. Some theoretical aspects of road traffic research, Proceedings of the institution of civil engineers, (1952) 325–378.

35. Willumsen, L.G. Estimation of an O − D matrix from traffic counts- A review, Working paper, Institute of Transport Studies, University of Leeds, Leeds, UK 1978.

36. Willumsen, L.G. Simplified transport models based on traffic counts, Transportation, 10 (1981), 257–278.

37. Xie, C., Kockelman, K.M. and Waller, S.T. A maximum entropy-least squares estimator for elastic origin-destination trip matrix estimation, Transport. Res. B-Meth. 45 (2011), 1465–1482.