Shortest Path Problems with Time Windows on Nodes and Arcs

A dynamic programming formulation of a shortest path problem is presented when there are time windows on the nodes and arcs of a graph. A time window at a node i is given by [ai, bi] and a time window at arc(i, j) is given by [αij, βij]. The shortest path from source node 1 to sink N is formulated and satisfies all time window constraints, i.e., arriving at node i when time window is open and traveling along arc(i, j) when time window along are is open.