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

Y. L. Chen, D. Rinks, K. Tang

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

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 form 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.

Original languageEnglish
Pages (from-to)102-108
Number of pages7
JournalJournal of the Operational Research Society
Volume52
Issue number1
DOIs
StatePublished - Jan 2001

Keywords

  • Networks and graphs
  • Road transport
  • Shortest path

Fingerprint

Dive into the research topics of 'The first K minimum cost paths in a time-schedule network'. Together they form a unique fingerprint.

Cite this