A data model for trip planning in multimodal transportation systems

ABSTRACT

This paper introduces the problem of modeling urban transportation systems in a database where certain aspects of the data are probabilistic in nature. The transportation network is composed of multiple modes (e.g., automobile, bus, train, pedestrian) that the user can alternate between. A trip -- a path between an origin and destination subject to some constraints -- is the central concept. How these trips and the network can be represented as both a graph and relational model, as well as the requirements for querying are the main contributions of this paper. A set of operators are defined to work over these transportation concepts and they are integrated within a SQL-like syntax to express queries over the uncertain transportation network. Additionally, the paper shows how this model can be integrated within other moving objects and spatio-temporal data models, and how these graph-based queries can be processed.

REFERENCES

• 1: Michele Angelaccio , Tiziana Catarci , Giuseppe Santucci, QBD*: A Graphical Query Language with Recursion, IEEE Transactions on Software Engineering, v.16 n.10, p.1150-1163, October 1990 [doi>10.1109/32.60295]
• 2: Bay Area Rapit Transit Planner. http://www.bart.gov/.
• 3: M. Bielli, A. Boulmakoul, and H. Mouncif. Object modeling and path computation for multimodal travel systems. In European Journal of Operational Research, volume 175, pages 1705--1730, December 2006.
• 4: Mariano P. Consens , Isabel F. Cruz , Alberto O. Mendelzon, Visualizing queries and querying visualizations, ACM SIGMOD Record, v.21 n.1, p.39-46, March 1992 [doi>10.1145/130868.130874]
• 5: Isabel F. Cruz , Alberto O. Mendelzon , Peter T. Wood, A graphical query language supporting recursion, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.323-330, May 27-29, 1987, San Francisco, California, United States
• 6: Isabel F. Cruz , Theodore S. Norvell, Aggregative Closure: An Extension of Transitive Closure, Proceedings of the Fifth International Conference on Data Engineering, p.384-391, February 06-10, 1989
• 7: S. Dar , R. Agrawal, Extending SQL with Generalized Transitive Closure, IEEE Transactions on Knowledge and Data Engineering, v.5 n.5, p.799-812, October 1993 [doi>10.1109/69.243510]
• 8: Shaul Dar , Rakesh Agrawal , H. V. Jagadish, Optimization of Generalized Transitive Closure Queries, Proceedings of the Seventh International Conference on Data Engineering, p.345-354, April 08-12, 1991
• 9: Martin Erwig , Markus Schneider, Spatio-Temporal Predicates, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.881-901, July 2002 [doi>10.1109/TKDE.2002.1019220]
• 10: M. Erwig and M. Schneider. STQL: A spatio-temporal query language. Mining Spatio-Temporal Information Systems, 2002.
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: Google Maps. http://maps.google.com/.
• 13: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 14: Hartmut Güting , Teixeira de Almeida , Zhiming Ding, Modeling and querying moving objects in networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.165-190, June 2006 [doi>10.1007/s00778-005-0152-x]
• 15: A. Lozano and G. Storchi. Shortest viable path algorithm in multimodal networks. In Transportation Research Part A: Policy and Practice, volume 35, pages 225--241, March 2001.
• 16: Mapquest. http://www.mapquest.com/.
• 17: Nikos Pelekis , Babis Theodoulidis , Ioannis Kopanakis , Yannis Theodoridis, Literature review of spatio-temporal database models, The Knowledge Engineering Review, v.19 n.3, p.235-274, September 2004 [doi>10.1017/S026988890400013X]
• 18: Regional Transit Authority Trip Planner. http://tripsweb.rtachicago.com/.
• 19: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 20: A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. Querying the uncertain position of moving objects. In Temporal Databases: Research and Practice, volume 1399 of Lecture Notes in Computer Science, pages 310--320. Springer, 1998.
• 21: Washington Metropolitan Area Transit Authority Trip Planner. http://www.wmata.com/tripplanner_d/tripplanner.cfm.