The First K Minimum Cost Paths in a Time-Schedule Network

Title	The First K Minimum Cost Paths in a Time-Schedule Network
Creator	唐揆 Chen, Y. L.;Rinks, D.;Tang, Kwei
Contributor	企管系
Key Words	shortest path; road transport; networks and graphs
Date	2001-01
Date Issued	25-Aug-2016 14:10:55 (UTC+8)
Summary	The time-constrained shortest path problem is an important generalisation of the classical shortest path problem and in recent years has attracted much research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure from a node may take place only at one of these departure times. The objective of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is developed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time.
Relation	Journal of Operational Research Society, 52(1), 102-108
Type	article
DOI	http://dx.doi.org/10.1057/palgrave.jors.2601028

dc.contributor	企管系
dc.creator (作者)	唐揆	zh_TW
dc.creator (作者)	Chen, Y. L.;Rinks, D.;Tang, Kwei
dc.date (日期)	2001-01
dc.date.accessioned	25-Aug-2016 14:10:55 (UTC+8)	-
dc.date.available	25-Aug-2016 14:10:55 (UTC+8)	-
dc.date.issued (上傳時間)	25-Aug-2016 14:10:55 (UTC+8)	-
dc.identifier.uri (URI)	http://nccur.lib.nccu.edu.tw/handle/140.119/100734	-
dc.description.abstract (摘要)	The time-constrained shortest path problem is an important generalisation of the classical shortest path problem and in recent years has attracted much research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure from a node may take place only at one of these departure times. The objective of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is developed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time.
dc.format.extent	188388 bytes	-
dc.format.mimetype	application/pdf	-
dc.relation (關聯)	Journal of Operational Research Society, 52(1), 102-108
dc.subject (關鍵詞)	shortest path; road transport; networks and graphs
dc.title (題名)	The First K Minimum Cost Paths in a Time-Schedule Network
dc.type (資料類型)	article
dc.identifier.doi (DOI)	10.1057/palgrave.jors.2601028
dc.doi.uri (DOI)	http://dx.doi.org/10.1057/palgrave.jors.2601028