This paper proposes a modified bi-level optimization algorithm to estimate the time-dependent origin–destination trip matrices for large-scale networks with multiple vehicle classes. Methodologies are presented to overcome the challenges caused by the scale of the problem. The upper-level problem, a bound-constrained quadratic problem, had many variables and parameters for a network with around 68,000 links, 28,000 nodes, and 3,700 zones. Techniques to reduce the number of variables and parameters are described in this study, along with an approach to reduce the time and memory requirement of the lower-level problem. Furthermore, the basic approach, which had been applied only to a single vehicle class, was extended and adapted in this study to estimate matrices for single-occupancy and high-occupancy vehicles jointly. Two solution packages, MINOS and KNITRO, were tested for the upper-level problem. The solution package KNITRO was run with an option to use an interior point–conjugate gradient algorithm, which was well suited to large-scale nonlinear problems. The modified bi-level algorithm was applied to estimate the time-dependent demand patterns for the New York City regional network.
Get full access to this article
View all access options for this article.
References
1.
CremerM., and KellerH.Dynamic Identification of Flows from Traffic Counts at Complex Intersections. Proc. 8th International Symposium on Transportation and Traffic Theory, Toronto, Ontario, Canada, 1981.
2.
CascettaE., InaudiD., and MarquisG.Dynamic Estimators of Origin–Destination Matrices Using Traffic Counts. Transportation Science, Vol. 27, No. 4, 1993, pp. 363–373.
3.
MahmassaniH. S., and TavanaH.Estimation of Dynamic Origin–Destination Flows from Sensor Data Using Bilevel Optimization Method. Presented at 80th Annual Meeting of the Transportation Research Board of the National Academies, Washington, D.C., 2001.
4.
TavanaH.Internally Consistent Estimation of Dynamic Network Origin–Destination Flows from Intelligent Transportation Systems Data Using Bi-Level Optimization. PhD dissertation. University of Texas at Austin, 2001.
5.
ZhouX.Dynamic Origin–Destination Demand Estimation and Prediction for Off-Line and On-Line Dynamic Traffic Assignment Operation. PhD dissertation. University of Maryland, College Park, 2004.
6.
AlibabaiH., and MahmassaniH. S.Dynamic Origin–Destination Demand Estimation Using Turning Movement Counts. In Transportation Research Record: Journal of the Transportation Research Board, No. 2085, Transportation Research Board of the National Academies, Washington, D.C., 2008, pp. 39–48.
7.
ZhouX., QinX., and MahmassaniH. S.Dynamic Origin–Destination Demand Estimation Using Multiday Link Traffic Counts for Planning Applications. In Transportation Research Record: Journal of the Transportation Research Board, No. 1831, Transportation Research Board of the National Academies, Washington, D.C., 2003, pp. 30–38.
8.
KangY.Estimation and Prediction of Dynamic Origin–Destination (O-D) Demand and System Consistency Control for Real-Time Dynamic Traffic Assignment Operation. PhD dissertation. University of Texas at Austin, 1999.
9.
AshokK., and Ben-AkivaM.Alternative Approaches for Real-Time Estimation and Prediction of Time-Dependent Origin–Destination Flows. Transportation Science, Vol. 34, No. 1, 2000, pp. 21–36.
10.
CremerM., and KellerH.A New Class of Dynamic Methods for the Identification of Origin–Destination Flows. Transportation Research Part B: Methodological, Vol. 21, No. 2, 1987, pp. 117–132.
11.
BellM. G. H.The Estimation of Origin–Destination Matrices by Constrained Generalized Least Squares. Transportation Research Part B: Methodological, Vol. 25, No. 1, 1991, pp. 13–22.
12.
NihanN. L., and DavisG. A.Application of Prediction Error Minimization and Maximum Likelihood to Estimate Intersection O-D Matrices from Traffic Counts. Transportation Science, Vol. 23, No. 2, 1989, pp. 77–90.
13.
OkutaniI., and StephanedesY.Dynamic Prediction of Traffic Volumes Through Kalman Filtering Theory. Transportation Research Part B: Methodological, Vol. 18, No. 1, 1984, pp. 1–11.
14.
KattanL., and AbdulhaiB.Noniterative Approach to Dynamic Traffic Origin–Destination Estimation with Parallel Evolutionary Algorithms. In Transportation Research Record: Journal of the Transportation Research Board, No. 1964, Transportation Research Board of the National Academies, Washington, D.C., 2006, pp. 201–210.
15.
NieY., and ZhangH. M.A One-Level O-D Estimation Approach Based on Relaxation. Presented at 87th Annual Meeting of the Transportation Research Board of the National Academies, Washington, D.C., 2007.
16.
BalakrishnaR., Ben-AkivaM. E., and KoutsopoulosH. N.Offline Calibration of Dynamic Traffic Assignment: Simultaneous Demand-and-Supply Estimation. In Transportation Research Record: Journal of the Transportation Research Board, No. 2003, Transportation Research Board of the National Academies, Washington, D.C., 2007, pp. 50–58.
17.
BalakrishnaR., and KoutsopoulosH. N.Incorporating Within-Day Transitions in Simultaneous Offline Estimation of Dynamic Origin–Destination Flows Without Assignment Matrices. In Transportation Research Record: Journal of the Transportation Research Board, No. 2085, Transportation Research Board of the National Academies, Washington, D.C., 2008, pp. 31–38.
18.
TsekerisT., DimitriouL., and StathopoulosA.Simultaneous Origin–Destination Matrix Estimation in Dynamic Traffic Networks with Evolutionary Computing. In Applications of Evolutionary Computing, vol. 4448 of Lecture Notes in Computer Science (GiacobiniM., eds.), Springer, Berlin, Germany, 2007, pp. 668–675.
19.
MadanatS. M., HuS.-R., and KrogmeierJ. V.Dynamic Estimation and Prediction of Freeway O-D Matrices with Route Switching Considerations and Time-Dependent Model Parameters. In Transportation Research Record 1537, TRB, National Research Council, Washington, D.C., 1996, pp. 98–105.
20.
Van der ZijjpN. J., and LindveldC. D. R.Estimation of Origin–Destination Demand for Dynamic Assignment with Simultaneous Route and Departure Time Choice. In Transportation Research Record: Journal of the Transportation Research Board, No. 1771, TRB, National Research Council, Washington, D.C., 2001, pp. 75–82.
21.
PazA., and PeetaS.Information-Based Network Control Strategies Consistent with Estimated Driver Behavior. Transportation Research Part B: Methodological, Vol. 43, No. 1, 2009, pp. 73–96.
22.
PazA., and PeetaS.On-Line Calibration of Behavior Parameters for Behavior-Consistent Route Guidance. Transportation Research Part B: Methodological, Vol. 43, No. 4, 2009, pp. 403–421.
23.
JayakrishnanR., MahmassaniH. S., and HuT.Y.An Evaluation Tool for Advanced Traffic Information and Management Systems in Urban Networks. Transportation Research Part C: Emerging Technologies, Vol. 2, No. 3, 1994, pp. 129–147.
24.
MurtaghB. A., and SaundersM. A.MINOS 5.5's User's Guide. Technical report SOL 83-20R. Stanford University, Calif., 1983 (revised 1998).
25.
ByrdR. H., HribarM. E., and NocedalJ.An Interior Point Algorithm for Large Scale Nonlinear Programming. Society for Industrial and Applied Mathematics Journal on Optimization, Vol. 9, No. 4, 1999, pp. 877–900.
26.
ByrdR. H., NocedalJ., and WaltzR. A.KNITRO: An Integrated Package for Nonlinear Optimization. In Large-Scale Nonlinear Optimization, vol. 83 of Nonconvex Optimization and Its Applications (di PilloG., and RomaM., eds.), Springer, 2006, pp. 35–59.
27.
NocedalJ., and WrightS. J.Numerical Optimization.Springer, 2006.
28.
WaltzR. A., and PlantengaT. D.KNITRO 6.0 User's Manual.Ziena Optimization Inc., Evanston, Ill., 2009.
