Institution: | Institute of Production System Engineering and Management National Chinyi Institute of Technology Taiping, 411, Taiwan, Republic of China Department of Information Management National Central University Chung-Li, Taiwan 320, Republic of China |
Abstract: | In this article, we present an algorithm to find the first K shortest unique-arc walks in a traffic-light network. Each node of the present network is associated with a repeated sequence of different windows to model operations of traffic signals and intersection movements. Unlike conventional simple or looping paths, we refer to the paths in this paper as unique-arc walks because they may include repeated nodes but will exclude repeated arcs. Using the heap structure, we develop an algorithm to find the first K shortest unique-arc walks in time O(Kr|V|3|A|), where |V| is the number of nodes, |A| is the number of arcs, and r represents the number of different windows associated with a node. |