A Generalization of Dynamic Programming for Pareto Optimization in Dynamic Networks

Getachew, Teodros, Kostreva, Michael, and Lancaster, Laura. "A Generalization of Dynamic Programming for Pareto Optimization in Dynamic Networks." RAIRO - Operations Research 34.1 (2010): 27-47. <http://eudml.org/doc/197846>.

@article{Getachew2010,
abstract = { 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. },
author = {Getachew, Teodros, Kostreva, Michael, Lancaster, Laura},
journal = {RAIRO - Operations Research},
keywords = { Pareto optimization; dynamic network; shortest path; dynamic programming; time-dependent cost function.; Pareto optimization; dynamic programming; time-dependent cost function},
language = {eng},
month = {3},
number = {1},
pages = {27-47},
publisher = {EDP Sciences},
title = {A Generalization of Dynamic Programming for Pareto Optimization in Dynamic Networks},
url = {http://eudml.org/doc/197846},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Getachew, Teodros
AU - Kostreva, Michael
AU - Lancaster, Laura
TI - A Generalization of Dynamic Programming for Pareto Optimization in Dynamic Networks
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 1
SP - 27
EP - 47
AB - 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.
LA - eng
KW - Pareto optimization; dynamic network; shortest path; dynamic programming; time-dependent cost function.; Pareto optimization; dynamic programming; time-dependent cost function
UR - http://eudml.org/doc/197846
ER -