Volume 34, Number 1, January March 2000
|Page(s)||27 - 47|
|Published online||15 August 2002|
A Generalization of Dynamic Programming for Pareto Optimization in Dynamic Networks
Clemon University, Department
of Mathematical Sciences, Clemson, South Carolina 29634-1907,
The Algorithm in this paper is designed to find the shortest path in a network given time-dependent cost functions. It has the following features: it is recursive; it takes place bath in a backward dynamic programming phase and in a forward evaluation phase; it does not need a time-grid such as in Cook and Halsey and Kostreva and Wiecek's "Algorithm One”; it requires only boundedness (above and below) of the cost functions; it reduces to backward multi-objective dynamic programming if there are constant costs. This algorithm 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.
Key words: Pareto optimization / dynamic network / shortest path / dynamic programming / time-dependent cost function.
© EDP Sciences, 2000
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.