Multiple Path-Finding Models Using Kalman Filtering and Space Syntax Techniques

Abstract

A study was done to develop a shortest path algorithm in which the realism of way finding had been improved by incorporating the concept of road cognition. The existing shortest path algorithms consider travel time and travel distance only. However, cognition of road configurations also can be considered for providing a realistically satisfied path. Surveys have shown that people prefer a high-cognition path rather than a low-cognition path. Therefore, the study developed a shortest path algorithm to provide a realistically plausible route that is preferred by many people and that considered the travel time, travel distance, and road cognition. The profiles of travel times, which are required to estimate arrival times up to destination, are predicted by using a Kalman filtering technique to reflect time-varying travel conditions. The travel distance is calculated by using the geographic information system (GIS) attributes, and road cognition is established by applying a space syntax technique to identify road configurations. Also, space data of the space syntax model are based on GIS data. By considering both the shortest path in terms of travel time and distance and the best cognition in terms of road configurations, multiple paths are determined.

Get full access to this article

View all access options for this article.

References

Hall

Route Choice and Advanced Traveler Information Systems on a Capacitated and Dynamic Network. Transportation Research C, No. 4, No. 5, 1996, pp. 289.

Ben-Akiva

, and Lerman

Discrete Choice Analysis: Theory and Application to Travel Demand. MIT Press, Cambridge, Mass., 1985.

Shofer

J. L.

, Koppelman

F. S.

, and Charlton

W. A.

Perspectives on Driver Preferences for Dynamic Route Guidance Systems. In Transportation Research Record 1588, TRB, National Research Council, Washington, D.C., 1997, pp. 26–31.

Delvert

Heterogeneous Agents Facing Route Choice: Experienced Versus Inexperienced Tripmakers. Presented at IATBR '97, Austin, Texas, 1997.

Gopinath

Modeling Heterogeneity in Discrete Choice Processes: Application to Travel Demand. PhD dissertation. MIT, Cambridge, Mass., 1995.

Ramming

Network Knowledge and Route Choice. PhD dissertation. MIT, Cambridge, Mass., 2001.

Nicholson

Finding the Shortest Route Between Two Points in a Network. The Computer Journal, Vol. 9, 1966, pp. 275–280.

Bertsekas

An Auction/Sequential Shortest Path Algorithm for the Minimum Cost Network Flow Problem. MIT, Cambridge, Mass., 1995.

Ahuja

, Magnanti

, and Orlin

Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, N.J., 1993.

10.

Thomas

Traffic Assignment Techniques. Avebury Technical, Aldershot, England, 1991.

11.

Zhang

F. B.

Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures. Journal of Geographic Information and Decision Analysis, Vol. 1, No. 1, 1997.

12.

Daganzo

C. F.

Reversity of the Time-Dependent Shortest Path Problem. Research Report UCB-ITS-RR-98-14. Department of Civil Engineering, University of California, Berkeley, 1998.

13.

de la Barra

, Perez

, and Anez

Multidimensional Path Search and Assignment. Proc., 21st PTRC Summer Meeting, University of Manchester, UK, PTRC Education and Research Services, Ltd., London, 1993, pp. 307–319.

14.

Lee

, and Lee

Development of Dynamic Route Guidance Algorithm Using Multi-Step Ahead Link Travel Time Prediction. Behavior in Networks Workshop (BiNs), University of Seoul, Korea 2004.

15.

Huang

, and Peng

Z.-R.

Object-Oriented Geographic Information System Data Model for Transit Trip Planning Systems. In Transportation Research Record: Journal of the Transportation Research Board, No. 1804, Transportation Research Board of the National Academies, Washington, D.C., 2002, pp. 205–211.

16.

Heuristic Shortest Path Algorithms for Transportation Applications: State of the Art. Computers and Operations Research, Vol. 33, No. 11, 2005, pp. 3324–3343.

17.

Bonsall

, and Joint

Driver Compliance with Route Guidance: The Evidence and Its Implications. Society of Automotive Engineers, Warrendale, Pa., 1991.

18.

Hillier

Space Is the Machine. Cambridge University Press, Cambridge, England, 1996.

19.

Batty

, and Rana

The Automatic Definition and Generation of Axial Lines and Axial Maps. Environment and Planning B: Planning and Design, Vol. 31, 2004, pp. 615–640.

20.

Dalton

Storing Directionality in Axial Lines Using Complex Node Depths. Presented at Fourth International Space Syntax Symposium, London, 2003.

21.

Jiang

, and Claramunt

Integration of Space Syntax into GIS: New Perspectives for Urban Morphology. Transaction in GIS, Vol. 6, No. 3, 2002, pp. 295.

22.

Lee

, and Jun

Assessing Public Transportation Accessibility Based on Topological Structure. Presented at CUPUM 05, London, 2005.

23.

Hiller

, and Hansom

The Social Logic of Space. Cambridge University Press, Cambridge, England, 1984.