A K-th shortest path set algorithm for urban traffic network

• In urban traffic network, it is important to optimize traffic flow of the K-th shortest path that meets the travel demand and then allocate the OD traffic flow onto the paths. This paper investigates the algorithm of searching K-th shortest path that meets the travel demand. The method overcomes the weakness of the traditional algorithm that can only get single K-th shortest path. According to the second principle of Wardrop and the road impedance function theory, the paper analyzes the necessity of the path set searching method for optimizing traffic flow, and proposes the definition and criterions of the K-th shortest path set in urban traffic network. Then, it presents an algorithm with the polynomial time complexity for searching K-th shortest path set in urban traffic network. The simulation results show that all of the K-th shortest path which meet the travel demand can be obtained effectively, and the feasibility of traffic allocation on above path set is proved with comparison of traditional algorithms.

Subject headings

TEKNIK OCH TEKNOLOGIER  -- Samhällsbyggnadsteknik -- Transportteknik och logistik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Civil Engineering -- Transport Systems and Logistics (hsv//eng)

Publication and Content Type

ref (subject category)

art (subject category)