Finding the first k shortest paths in a time-window network

Finding the first k shortest paths in a time-window network

0.00 Avg rating0 Votes
Article ID: iaor20043287
Country: United Kingdom
Volume: 31
Issue: 4
Start Page Number: 499
End Page Number: 513
Publication Date: Apr 2004
Journal: Computers and Operations Research
Authors: ,
Abstract:

The time-constrained shortest path problem is an important generalization of the classical shortest path problem and has attracted much research interest in recent years. We consider a time-window network, where every node in the network has a list of pre-specified windows and departure from a node may take place only in these window periods. The objective of this paper is to find the first K shortest paths in a time-window network. An algorithm of time complexity of O(Kr|V|3) is developed to find the first K shortest paths, where |V| is the numbers of nodes in the network and r represents the maximum number of windows associated with a node.

Reviews

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