January 2001, Volume 52, Issue 1, Pages 102 - 108

Technical Note

The first K minimum cost paths in a time-schedule network Y-L Chen1, D Rinks2 & K Tang3 1National Central University, Taiwan     2Lousiana State University, USA     3Purdue University, USA     Correspondence to: Dr K Tang, Krannert School of Management, Purdue University, West Lafayette, IN 47907-1310, USA. E-mail: ktang@mgmt.purdue.edu

Keywords

shortest path;   road transport;   networks and graphs

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.

Received October 1998; Accepted January 2000

^© Macmillan Publishers Ltd 2001