Author(s)

Nasser A. El-Sherbeny^1,2

¹Mathematics Department, Faculty of Science, Al-Azhar University, Cairo, Egypt.
²Mathematics Department, Faculty of Applied Medical Science, Taif University, Turabah, KSA.

In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where V is a set of nodes, E is a set of edges with a non-negative transit-time function . For each node , a time window  within which the node may be visited and  , is non-negative of the service and leaving time of the node. A source node s, a destination node d and a departure time t₀, the time-dependent shortest path problem with time windows asks to find an s, d-path that leaves a source node s at a departure time t₀; and minimizes the total arrival time at a destination node d. This formulation generalizes the classical shortest path problem in which c_e are constants. Our algorithm of the time windows gave the generalization of the ALT algorithm and A* algorithm for the classical problem according to Goldberg and Harrelson [1], Dreyfus [2] and Hart et al. [3].

Shortest Path, Time-Dependent Shortest Path, ALT Algorithm, A* Algorithm, Time Windows

El-Sherbeny, N. (2014) The Algorithm of the Time-Dependent Shortest Path Problem with Time Windows. Applied Mathematics, 5, 2764-2770. doi: 10.4236/am.2014.517264.