A generalization of dynamic programming for Pareto optimization in dynamicnetworks

The Algorithm in this paper is designed to find the shortest path in a netw ork given time-dependent cost functions. It has the following features: it is recursive, it rakes place bath in a backward dynamic programming phase a nd in a forward evaluation phase; it does not need a time-grid such as in C ook and Halsey and Kostreva and Wiecek's "Algorithm One" ; it requires only boundedness (above and below) of the cost functions, it reduces to backwar d multi-objective dynamic programming if there are constant costs. This alg orithm has been successfully applied to multi-stage decision problems where the costs are a function of the time when the decision is made. There are examples of further applications to tactical delay in production scheduling and to production control.