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 [a(i), b(i)] and a time window at arc(i,j) is given by [alpha(ij), beta(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. (C) 1994 Academic Press, Inc.

[发布日期] 1994-09-15