Comparative Analysis of Evolutionary, Local Search, and Hybrid Approaches to O/D Traffic Estimation
Publication: Journal of Transportation Engineering
Volume 137, Issue 1
Abstract
This paper compares the performance of various advanced evolutionary algorithm (EA) techniques to solve the problem of dynamic origin/destination (O/D) estimation. The potential of EA in the dynamic O/D estimation problem lies in their powerful global search and optimization capabilities. This EA-based demand estimation framework is implemented into a model that we call dynamic O/D estimator (DynODE). DynODE is integrated with an existing dynamic traffic assignment (DTA) platform (i.e., Dynasmart-P). The EA-based methods in this research are further augmented with EA parallelization as well as hybridization schemes to further improve the quality and efficiency of the solution. In this paper, we evaluate the performance of the basic EA model, the hybrid EA model, the parallel EA (PEA) model, as well as the parallel hybrid EA model. Additionally, the performance of a local-search method is examined and compared with the EA-based approaches. The comparison is performed on a medium size network. The results from the study show that the PEA model outperforms the other algorithms in terms of speed as well as solution quality. However, all hybrid and PEA runs result in savings in computation resources as well as enhancement in the quality of solution as compared to the basic EA model. Still, the basic EA model outperforms the local-search model.
Get full access to this article
View all available purchase options and get full access to this article.
References
Ashok, K., and Ben-Akiva, M. E. (2002). “Estimation and prediction of time-dependent origin-destination flows a stochastic mapping to path flows and link flows.” Transp. Sci., 36(2), 184–198.
Belew, R. (1990). “Evolution, learning and culture: Computational metaphors for adaptive algorithms.” Complex Syst., 4(1), 11–49.
Cantú-Paz, E. (2000). Efficient and accurate parallel genetic algorithms, Kluwer, Dordrecht, The Netherlands.
Cascetta, E. (2001). Transportation systems engineering theory and methods, Kluwer, Dordrecht, The Netherlands.
Cascetta, E., and Nguyen, S. (1988). “A unified framework for estimating or updating origin/destination matrices from traffic counts.” Transp. Res., Part B: Methodol., 22(6), 437–455.
Cheu, R. -L., Jin, X., and Ng, K. C. (1998). “Calibration of FRESIM for Singapore Expressway using genetic algorithm.” J. Transp. Eng., 124(6), 526–535.
Davis, L. (1990). The handbook of genetic algorithms, Van Nostrand Reinhold, New York.
Foy, M., Benekohal, R. F., and Goldberg, D. E. (1992). “Signal timing determination using genetic algorithms.” Transportation Research Record 1365, TRB, National Research Council, Washington, D.C., 108–115.
Holland, J. H. (1975). Adaptation in natural and artificial system, University of Michigan Press, Ann Arbor, Mich.
Kattan, L. (2005). “Dynamic traffic origin/destination estimation using evolutionary based algorithms.” Ph.D. dissertation, Dept. of Civil Engineering, Univ. of Toronto, Toronto.
Kattan, L., and Abdulhai, B. (2006). “Non-iterative approach to dynamic traffic origin-destination estimation using parallel evolutionary algorithms.” Transp. Res. Rec., 1964, 201–210.
Kruchten, N., Abdulhai, B., Kattan, L., and de Koning, D. (2004). “Galapagos: A generic distributed parallel genetic algorithm development platform for computationally demanding its optimization problems.” 83rd Annual Meeting of the Transportation Research Board, January 2004, Washington, DC, (CD-ROM).
Mathias, K. E., Whitley, D., Stork, C., and Kusuma, T. (1994). “Staged hybrid genetic search for seismic data imaging.” Proc., IEEE Int. Conf. on Evolutionary Computation, J. D. Shaffer, Orlando, FL, 356–361.
Michalewicz, Z. (1994). Genetic program, Springer, New York.
Moscato, P. (1989). “On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms.” Technical Rep. No. 790, Caltech Concurrent Computation Program, California Institute of Technology, Calif.
Mühlenbein, H., Schomisch, M., and Born, J. (1991). “The parallel genetic algorithm as function optimizer.” Proc., 4th Int. Conf. on Genetic Algorithms, R. K. Belew and L. B. Booker, eds., Morgan Kaufmann, San Mateo, Calif., 271–278.
Peeta, S., and Mahmassani, H. S. (1995). “Multiple user classes real-time traffic assignment for online operations a rolling horizon solution framework.” Transp. Res., Part C: Emerg. Technol., 3(2), 83–98.
Renders, J. -M., and Flasse, S. P. (1996). “Hybrid methods using genetic algorithms for global optimization.” IEEE Trans. Syst., Man, Cybern., Part B: Cybern., 26(2), 243–258.
Roy, P., and Abdulhai, B. (2003). “GAID: Genetic adaptive incident detection for freeways.” Transportation Research Record 1856, TRB, National Research Council, Washington, D.C., 96–105.
Spall, J. (1998). “An overview of the simultaneous perturbation method for efficient optimization.” Johns Hopkins University APL Technical Digest, 19(4), 482–492.
Tavana, H. (2001). “Internally consistent estimation of dynamic origin-destination flows from intelligent transportation systems data using bi-level optimizations.” Ph.D. thesis, Univ. of Texas at Austin, Austin, Tex.
Van Zuylen, H. J. (1981). “Some improvements in the estimation of an OD matrix from traffic counts.” Proc., 8th Int. Symp. on Transportation and Traffic Theory, Tornoto, Ontario, Canada.
Wu, J. (1996). “Real-time origin-destination matrix updating algorithm for on-line applications.” Transp. Res., Part B: Methodol., 31(5), 381–396.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 137 • Issue 1 • January 2011
Pages: 46 - 56
Copyright
© 2011 ASCE.
History
Received: Apr 28, 2008
Accepted: Apr 28, 2010
Published online: May 5, 2010
Published in print: Jan 2011
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.