Abstract
Given a spatio-temporal network, a source, a destination, and a start-time interval, the All-start-time Lagrangian Shortest Paths (ALSP) problem determines a path set which includes the shortest path for every start time in the given interval. ALSP is important for critical societal applications related to air travel, road travel, and other spatio-temporal networks. However, ALSP is computationally challenging due to the non-stationary ranking of the candidate paths, meaning that a candidate path which is optimal for one start time may not be optimal for others. Determining a shortest path for each start-time leads to redundant computations across consecutive start times sharing a common solution. The proposed approach reduces this redundancy by determining the critical time points at which an optimal path may change. Theoretical analysis and experimental results show that this approach performs better than naive approaches particularly when there are few critical time points.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Delta airlines, http://www.delta.com/
Google maps, http://www.maps.google.com/
Navteq, http://www.navteq.com/
Batchelor, G.K.: An introduction to fluid dynamics. Cambridge Univ. Press, Cambridge (1973)
Chabini, I., Lan, S.: Adaptations of the a* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks. IEEE Transactions on Intelligent Transportation Systems 3(1), 60–74 (2002)
Demiryurek, U., Banaei-Kashani, F., Shahabi, C.: A case for time-dependent shortest path computation in spatial networks. In: Proc. of the SIGSPATIAL Intl. Conf. on Advances in GIS, GIS 2010, pp. 474–477 (2010)
Deutsch, C.: Ups embraces high-tech delivery methods. NY Times (July 12, 2007), http://www.nytimes.com/2007/07/12/business/12ups.html
Ding, B., Yu, J.X., Qin, L.: Finding time-dependent shortest paths over large graphs. In: Proc. of the Intl. Conf. on Extending Database Technology (EDBT), pp. 205–216 (2008)
Evans, M.R., Yang, K., Kang, J.M., Shekhar, S.: A lagrangian approach for storage of spatio-temporal network datasets: a summary of results. In: Proc. of the SIGSPATIAL Intl. Conf. on Advances in GIS, GIS 2010, pp. 212–221 (2010)
Foschini, L., Hershberger, J., Suri, S.: On the complexity of time-dependent shortest paths. In: SODA. pp. 327–341 (2011)
George, B., Shekhar, S.: Time-aggregated graphs for modelling spatio-temporal networks. J. Semantics of Data XI, 191 (2007)
George, B., Shekhar, S., Kim, S.: Spatio-temporal network databases and routing algorithms. Tech. Rep. 08-039, Univ. of Minnesota - Comp. Sci. and Engg. (2008)
George, B., Kim, S., Shekhar, S.: Spatio-temporal network databases and routing algorithms: A summary of results. In: Papadias, D., Zhang, D., Kollios, G. (eds.) SSTD 2007. LNCS, vol. 4605, pp. 460–477. Springer, Heidelberg (2007)
Gunturi, V., Shekhar, S., Bhattacharya, A.: Minimum spanning tree on spatio-temporal networks. In: Bringas, P.G., Hameurlain, A., Quirchmayr, G. (eds.) DEXA 2010. LNCS, vol. 6262, pp. 149–158. Springer, Heidelberg (2010)
Kanoulas, E., Du, Y., Xia, T., Zhang, D.: Finding fastest paths on a road network with speed patterns. In: Proceedings of the 22nd International Conference on Data Engineering (ICDE), p. 10 (2006)
Kaufman, D.E., Smith, R.L.: Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. I V H S Journal 1(1), 1–11 (1993)
Köhler, E., Langkau, K., Skutella, M.: Time-expanded graphs for flow-dependent transit times. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 599–611. Springer, Heidelberg (2002)
Kleinberg, J., Tardos, E.: Algorithm Design. Pearson Education, London (2009)
Lovell, J.: Left-hand-turn elimination. NY Times (December 9, 2007), http://www.nytimes.com/2007/12/09/magazine/09left-handturn.html
Orda, A., Rom, R.: Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM 37(3), 607–625 (1990)
Yuan, J., Zheng, Y., Zhang, C., Xie, W., Xie, X., Sun, G., Huang, Y.: T-drive: driving directions based on taxi trajectories. In: Proc. of the SIGSPATIAL Intl. Conf. on Advances in GIS, GIS 2010, pp. 99–108 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gunturi, V.M.V., Nunes, E., Yang, K., Shekhar, S. (2011). A Critical-Time-Point Approach to All-Start-Time Lagrangian Shortest Paths: A Summary of Results. In: Pfoser, D., et al. Advances in Spatial and Temporal Databases. SSTD 2011. Lecture Notes in Computer Science, vol 6849. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22922-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-22922-0_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22921-3
Online ISBN: 978-3-642-22922-0
eBook Packages: Computer ScienceComputer Science (R0)