@article{274c0760b6694e18948f97b50f832eac,

title = "The first K shortest unique-arc walks in a traffic-light network",

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.",

keywords = "Shortest path, Traffic-light, Walk",

author = "Yang, {Hsu Hao} and Chen, {Yen Liang}",

note = "Funding Information: A classical shortest path problem is concerned with finding the path with the minimum time, distance, or cost from a source node to a destination through a connected network. It is an important problem because of its numerous applications and generalizations in transportation \[1\], communications \[2\],a nd many other areas. Readers are referred to several reviews on the shortest path problem \[3-5\]. To meet practical needs, a time-constrained shortest path problem generalizes the shortest path problem by incorporating temporal factors. The time window has been a common form of time constraint that assumes that a node can be visited only in a specified time *This author was supported in part by National Science Foundation Grant No. 90-2416-H-167-003. Author to whom all correspondence should be addressed. The authors are grateful to the anonymous referees for their helpful comments.",

year = "2004",

month = dec,

doi = "10.1016/j.mcm.2005.01.004",

language = "???core.languages.en_GB???",

volume = "40",

pages = "1453--1464",

journal = "Mathematical and Computer Modelling",

issn = "0895-7177",

number = "13",

}