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
t0, 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
t0; and minimizes the total arrival time at a destination node
d. This formulation generalizes the classical shortest path problem in which
ce 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].