Time-dependent shortest path problems arise in a variety of applications; e.g., dynamic traffic assignment (DTA), network control, automobile driver guidance, ship routing and airplane dispatching. In the majority of cases one seeks the cheapest (least generalized cost) or quickest route between an origin and a destination for a given time of departure. This is the "forward" shortest path problem. In some applications, however, e.g., when dispatching airplanes from airports and in DTA versions of the "morning commute problem", one seeks the cheapest or quickest routes for a given arrival...