Advances in Discrete-Time Dynamic Data Representation with Applications to Intelligent Transportation Systems
Abstract
Efficient storage, processing, and communication of dynamic data are at the heart of intelligent transportation systems (ITS) applications. The speed of communication and processing as well as the storage space required by such data depend on the method used for its representation. ITS applications typically involve dynamic data that are discrete and require fast computation and communication speeds to support real-time operations. An efficient representation method is presented, which is called the bit-stream representation, for discrete-time dynamic data. Its positive impacts are presented by developing efficient representations for storage and communication of travel times in dynamic transportation networks. It is shown theoretically that this representation method typically leads to an L/2-fold gain in both storage space and communication speed compared with methods that represent discretetime dynamic data using L-bits to store an integer. The proposed representation holds the potential to develop new faster algorithms that would directly operate on dynamic data represented as bit streams.
Get full access to this article
View all access and purchase options for this article.
References
1. Ahn B. H., and Shin J. Y. Vehicle Routing with Time Windows and Time-Varying Congestion. Journal of the Operational Research Society, Vol. 42, pp. 393–400.
2. Cai X., Kloks T., and Wong C. K. Time-Varying Shortest Path Problems with Constraints. Networks, Vol. 29, 1997, pp. 141–149.
3. Chabini I. Fastest Routes in Temporal Networks Revisited. Presented at Optimization Days, Montreal, Quebec, Canada, May 1996.
4. Chabini I. A New Shortest Paths Algorithm for Discrete Dynamic Networks. Proc., 8th IFAC Symposium on Transport Systems, 1997, pp. 551–556.
5. Chabini I. Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run Time. In Transportation Research Record 1645, TRB, National Research Council, Washington, D.C., 1998, pp. 170–175.
6. Chabini I., and Dean B. Shortest Path Problems in Discrete-Time Dynamic Networks: Complexity, Algorithms, and Implementations. Internal Report. Massachusetts Institute of Technology, Cambridge, 1999.
7. Chabini I. Fastest Routes in Temporal Networks Revisited. Presented at Optimization Days, Montreal, Quebec, Canada, May 1996.
8. Cooke L., and Halsey E. The Shortest Route Through a Network with Time-Dependent Internodal Transit Times. Journal of Mathematical Analysis and Applications, Vol. 14, 1966, pp. 492–498.
9. Dreyfus S. An Appraisal of Some Shortest-Path Algorithms. Operations Research, Vol. 17, 1969, pp. 395–412.
10. Ganugapati S. Dynamic Shortest Paths Algorithms: Parallel Implementations and Application to the Solution of Dynamic Traffic Assignment Models. Master’s thesis. Massachusetts Institute of Technology, Cambridge, 1998.
11. Kaufman D. E., and Smith R. L. Fastest Paths in Time-Dependent Networks for Intelligent-Vehicle Highway Systems Application. Intelligent-Vehicle Highway Systems Journal, Vol. 1, 1993, pp. 1–11.
12. Orda A., and Rom R. Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge Length. Journal of the ACM, Vol. 37, No. 3, 1990, pp. 607–625.
13. Orda A., and Rom R. Minimum Weight Paths in Time-Dependent Networks. Networks, Vol. 21, No. 3, 1991, pp. 295–320.
14. Pallottino S., and Scutellà M. G. Shortest Path Algorithms in Transportation Models: Classical and Innovative Aspects. In Equilibrium and Advanced Transportation Modelling (Marcotte P. and Nguyen S., eds.), Kluwer, New York, 1998, pp. 245–281.
15. Ziliaskopoulos A. K., and Mahmassani H. S. Time-Dependent, Shortest-Path Algorithms for Real-Time Intelligent Vehicle Highway System Applications. In Transportation Research Record 1408, TRB, National Research Council, Washington, D.C., 1993, pp. 94–100.
Cite article
Cite article
Cite article
OR
Download to reference manager
If you have citation software installed, you can download article citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published: January 2001
Issue published: January 2001
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in Transportation Research Record: Journal of the Transportation Research Board.
VIEW ALL JOURNAL METRICSArticle usage*
Total views and downloads: 2
*Article usage tracking started in December 2016
Altmetric
See the impact this article is making through the number of times it’s been read, and the Altmetric Score.
Learn more about the Altmetric Scores
Articles citing this one
Receive email alerts when this article is cited
Web of Science: 0
Crossref: 2
- State space reduction in modeling traffic network dynamics for dynamic...
- Adaptations of the A* algorithm for the computation of fastest paths i...
Figures and tables
Figures & Media
Tables
View Options
Get access
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
