The first K minimum cost paths in a time-schedule network

The first K minimum cost paths in a time-schedule network

0.00 Avg rating0 Votes
Article ID: iaor20014152
Country: United Kingdom
Volume: 52
Issue: 1
Start Page Number: 102
End Page Number: 108
Publication Date: Jan 2001
Journal: Journal of the Operational Research Society
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.