A Shortest Path Algorithm With Turn Penalty in Urban Road Networks

Urban road networks generally consist of a large number of intersections. Drivers perform a turn maneuver at each intersection they approach as occasions demand. Delays which drivers experience at intersections also may vary with traffic volume. Therefore, a shortest path algorithm for urban road networks should provide drivers with travel time information considering turn penalty varying with traffic volume. The purpose of this paper is to develop a shortest path algorithm which considers turn penalty in time-dependent networks. Kaufman‟s algorithm, which is one of the well-known shortest path algorithms, is modified in this paper to consider turn penalty. Gangnam-gu which is one of the most crowded areas in Seoul is selected as our study site. Link travel times per minute are calculated by PARAMICS, the microscopic traffic simulation software. A comparison is performed between the minimum travel costs calculated by Dijkstra‟s algorithm, the original Kaufman‟s algorithm and the modified Kaufman‟s algorithm. The result shows that total travel time searched by the algorithm in this study is different from them by the other existing algorithms and thus the shortest path information considering turn penalty should be provided. This research and the result will not only maximize drivers‟ benefit by offering reality-based travel information, but also by offering an alternative route.

• Corporate Authors:

  ITS Japan

  Tokyo,   Japan 

  ITS America

  1100 17th Street, NW, 12th Floor
  Washington, DC  United States  20036

  ERTICO

  326 Avenue Louis
  Brussels,   Belgium  B-1050
• Authors:
  • Min, Keun-Hong
  • Yang, Ji-Soo
  • Kim, Dong-Kyu
  • Kho, Seung-Young
• Conference:
  • 17th ITS World Congress
  • Location: Busan , Korea, South
  • Date: 2010-10-25 to 2010-10-29
• Publication Date: 2010

Language

• English

Media Info

• Media Type: DVD
• Features: Figures; References; Tables;
• Pagination: 9p
• Monograph Title: 17th ITS World Congress, Busan, 2010: Proceedings

Subject/Index Terms

• TRT Terms: Advanced driver information systems; Shortest path algorithms; Traffic simulation; Travel time
• Identifier Terms: Paramics (Computer program)
• Geographic Terms: Seoul (Korea)
• Subject Areas: Highways; Operations and Traffic Management; I70: Traffic and Transport;

Filing Info

• Accession Number: 01345270
• Record Type: Publication
• Files: TRIS
• Created Date: Jul 21 2011 10:07AM