## Abstract

This paper studies three types of algorithms for computing all-to-one time-dependent shortest paths for all departure times on a discrete time dynamic network: the CLASSIC algorithms (direct extensions of static shortest path algorithms), the decreasing order of time (DOT) algorithm and the STEN algorithm based on an explicit network expansion. All algorithms are analyzed under the same type of compact space-time expansion networks, and implemented in a flexible and extendable framework using object-oriented programming (OOP) concepts. Two types of randomly generated networks similar to those found in real transportation systems are used for evaluating the relative performance of the studied algorithms. Our numerical results show a discrepancy between DOT's theoretical and practical computational efficiency, and STEN's computational tractability in applications involving large-size networks and demanding strict acyclicity.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Eighth International Conference on Applications of Advanced Technologies in Transportation Engineering |

Editors | K.C. Sinha, T.F. Fwa, R.L. Cheu, D.-H. Lee |

Pages | 66-71 |

Number of pages | 6 |

State | Published - Dec 1 2004 |

Event | Proceedings of the Eighth International Conference on Applications of Advanced Technologies in Transportaion Engineering - Beijing, China Duration: May 26 2004 → May 28 2004 |

### Other

Other | Proceedings of the Eighth International Conference on Applications of Advanced Technologies in Transportaion Engineering |
---|---|

Country | China |

City | Beijing |

Period | 5/26/04 → 5/28/04 |

## ASJC Scopus subject areas

- Engineering(all)