Finding K shortest looping paths in a traffic-light network

Hsu Hao Yang; Yen Liang Chen

doi:10.1016/j.cor.2003.08.004

Finding K shortest looping paths in a traffic-light network

Hsu Hao Yang, Yen Liang Chen

Department of Information Management

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

Abstract

In this paper we consider a traffic-light network where every node in the network is associated with the constraint consisting of a repeated sequence of time windows. The constraint aims to simulate the operations of traffic-light control in an intersection of roads. With this kind of constraints in place, directions of routes when passing through the intersections can be formally modeled. The objective of this paper is to find the first K shortest looping paths in the traffic-light network. An algorithm of time complexity of O(rK ²|V₁|³) is developed, where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.

Original language	English
Pages (from-to)	571-581
Number of pages	11
Journal	Computers and Operations Research
Volume	32
Issue number	3
DOIs	https://doi.org/10.1016/j.cor.2003.08.004
State	Published - Mar 2005

Keywords

Looping path
Shortest path
Traffic-light

Access to Document

10.1016/j.cor.2003.08.004

Cite this

@article{1c58f99d35a045158764e3cb1463e026,

title = "Finding K shortest looping paths in a traffic-light network",

abstract = "In this paper we consider a traffic-light network where every node in the network is associated with the constraint consisting of a repeated sequence of time windows. The constraint aims to simulate the operations of traffic-light control in an intersection of roads. With this kind of constraints in place, directions of routes when passing through the intersections can be formally modeled. The objective of this paper is to find the first K shortest looping paths in the traffic-light network. An algorithm of time complexity of O(rK 2|V1|3) is developed, where r is the number of different windows of a node and |V1| is the number of nodes in the original network.",

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

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

note = "Funding Information: The authors are grateful to the anonymous referees for their helpful comments. The first author was supported in part by National Science Foundation grant no. 91-2416-H-167-004. ",

year = "2005",

month = mar,

doi = "10.1016/j.cor.2003.08.004",

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

volume = "32",

pages = "571--581",

journal = "Computers and Operations Research",

issn = "0305-0548",

number = "3",

}

TY - JOUR

T1 - Finding K shortest looping paths in a traffic-light network

AU - Yang, Hsu Hao

AU - Chen, Yen Liang

N1 - Funding Information: The authors are grateful to the anonymous referees for their helpful comments. The first author was supported in part by National Science Foundation grant no. 91-2416-H-167-004.

PY - 2005/3

Y1 - 2005/3

N2 - In this paper we consider a traffic-light network where every node in the network is associated with the constraint consisting of a repeated sequence of time windows. The constraint aims to simulate the operations of traffic-light control in an intersection of roads. With this kind of constraints in place, directions of routes when passing through the intersections can be formally modeled. The objective of this paper is to find the first K shortest looping paths in the traffic-light network. An algorithm of time complexity of O(rK 2|V1|3) is developed, where r is the number of different windows of a node and |V1| is the number of nodes in the original network.

AB - In this paper we consider a traffic-light network where every node in the network is associated with the constraint consisting of a repeated sequence of time windows. The constraint aims to simulate the operations of traffic-light control in an intersection of roads. With this kind of constraints in place, directions of routes when passing through the intersections can be formally modeled. The objective of this paper is to find the first K shortest looping paths in the traffic-light network. An algorithm of time complexity of O(rK 2|V1|3) is developed, where r is the number of different windows of a node and |V1| is the number of nodes in the original network.

KW - Looping path

KW - Shortest path

KW - Traffic-light

UR - http://www.scopus.com/inward/record.url?scp=4744365210&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2003.08.004

DO - 10.1016/j.cor.2003.08.004

M3 - 期刊論文

AN - SCOPUS:4744365210

SN - 0305-0548

VL - 32

SP - 571

EP - 581

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 3

ER -

Finding K shortest looping paths in a traffic-light network

Abstract

Keywords

Access to Document

Fingerprint

Cite this