## Abstract

A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time-window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK^{2} V_{1} ^{3}), where r is the number of different windows of a node and V_{1} is the number of nodes in the original network.

Original language | English |
---|---|

Pages (from-to) | 458-465 |

Number of pages | 8 |

Journal | Applied Mathematical Modelling |

Volume | 30 |

Issue number | 5 |

DOIs | |

State | Published - May 2006 |

## Keywords

- Shortest looping path
- Time-window