@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",
}