A generalization of dynamic programming for Pareto optimization in dynamic networks

Teodros Getachew; Michael Kostreva; Laura Lancaster

RAIRO - Operations Research - Recherche Opérationnelle (2000)

  • Volume: 34, Issue: 1, page 27-47
  • ISSN: 0399-0559

How to cite

top

Getachew, Teodros, Kostreva, Michael, and Lancaster, Laura. "A generalization of dynamic programming for Pareto optimization in dynamic networks." RAIRO - Operations Research - Recherche Opérationnelle 34.1 (2000): 27-47. <http://eudml.org/doc/105207>.

@article{Getachew2000,
author = {Getachew, Teodros, Kostreva, Michael, Lancaster, Laura},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {Pareto optimization; dynamic network; shortest path; dynamic programming; time-dependent cost function},
language = {eng},
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/105207},
volume = {34},
year = {2000},
}

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 - Recherche Opérationnelle
PY - 2000
PB - EDP-Sciences
VL - 34
IS - 1
SP - 27
EP - 47
LA - eng
KW - Pareto optimization; dynamic network; shortest path; dynamic programming; time-dependent cost function
UR - http://eudml.org/doc/105207
ER -

References

top
  1. 1. R. E. BELLMAN, Ona Routing Problem, Quarterly Appl. Math., 1958, 16, p. 87-90. Zbl0081.14403MR102435
  2. 2. T. A. BROWN and R. E. STRAUCH, Dynamic Programming in Multiplicative Lattices, J. Mafh. Anal. Appl., 1965, 12, p. 364-370. Zbl0132.40303MR184776
  3. 3. J. BRUMBAUGH-SMITH and D. SHIER, An empirical investigation of some bicriterion shortest path algorithms, European J. Op. Res., 1989, 43, p. 216-224. Zbl0681.90081MR1033649
  4. 4. R. L. CARRAWAY and T. L. MORIN, Generalized Dynamic Programming for Multicriteria Optimization, European J. Op. Res., 1990, 44, p. 95-104. Zbl0693.90090MR1035589
  5. 5. K. L. COOKE and E. HALSEY, The Shortest Route Through a Network with Time-Dependent Internodal Transit Times, J. Math. Anal. AppL., 1966, 14, p. 493-498. Zbl0173.47601MR192921
  6. 6. H. W. CORLEY and I. D. MOON, Shortest Paths in Networks with Vector Weights, J. Opt. Theory Appl., 1985, 46, p. 79-86. Zbl0542.90099MR792595
  7. 7. H. G. DAELLENBACH and C. A. DEKLUYVER, Note on Multiple Objective Dynamic Programming, J. Op. Res. Soc., 1980, 31, p. 591-594. Zbl0434.90086
  8. 8. E. W. DIJKSTRA, A Note on Two Problems in Connection with Graphs, Num. Math., 1959, 1, p. 269-271. Zbl0092.16002MR107609
  9. 9. S. E. DREYFUS, An Appraisal of Some Shortest Path Algorithms, Ops.Res., 1969, 17, p. 395-412. Zbl0172.44202
  10. 10. T. GETACHEW, An Algorithm for Multiple-Objective Network Optimization with Time variant Link-Costs, Ph.D. dissertation, Clemson Univ., Clemson, South Carolina, USA, 1992. 
  11. 11. T. GETACHEW, Optimization over Stratified Posets, in preparation. 
  12. 12. J. HALPERN, Shortest Route with Time-dependent Length of Edges and Limited Delay Possibilities in Nodes, J. Ops. Res., 1977, 21, p. 117-124. Zbl0366.90116MR484343
  13. 13. M. I. HENIG, The Principle of Optimality in Dynamic Programming with Returns in Partially Ordered Sets, Math. Ops. Res., 1985, 10, p. 462-470. Zbl0582.90104MR798391
  14. 14. D. E. KAUFMANN and R. L. SMITH, Minimum Travel Time Paths in Dynamic Networks with Application to Intelligent Vehicle-highway Systems, University of Michigan, Transportation Research Institute, Ann Arbor, Michigan, USA, IVHS Tech. Rpt. 90-11, 1990. 
  15. 15. M. M. KOSTREVA and M. M. WIECEK, Time Dependency in Multiple Objective Dynamic Programming, J. Math. Anal. Appl., 1993, 173, p. 289-308. Zbl0805.90113MR1205924
  16. 16. A. ORDA and R. ROM, Shortest-path and Minimum-delay Algorithms in Networks with Time-dependent Edge-length, J. Assoc. Comp. Mach., 1990, 37, p. 607-625. Zbl0699.68074MR1072271
  17. 17. A. B. PHILPOTT, Continuous-time Shortest Path Problems and Linear Programming, SIAM J. Cont. Opt., 1994, 32, p. 538-552. Zbl0801.90121MR1261153
  18. 18. S. VERDU and H. V. POOR, Abstract Dynamic Programming Models under Commutativity Conditions, SIAM J. Cont. Opt., 1987, 25, p. 990-1006. Zbl0631.90082MR893994

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.