Time Dependency in Multiple Objective Dynamic Programming.
Time Dependency in Multiple Objective Dynamic
Programming.
(1030 K)
Kostreva, M. M.; Wiecek, M. M.
Journal of Mathematical Analysis and Applications, Vol.
173, No. 1, 289-307, February 1993.
Sponsor:
National Institute of Standards and Technology,
Gaithersburg, MD
Keywords:
time; planning; algorithms; telecommunications; dynamic
programming
Abstract:
The problem of planning paths is a network structure is
important for many applications. Interest in path
planning is strong in transportation,
telecommunications, computer design, and fire hazard
analysis. Such a problem is sometimes called a routing
problem, or a shortest path problem. One of the
earliest solutions to the problem was given by Bellman.
Under the assumptions of constant travel times on each
link, dynamic programming was applied to compute the
path of minimum travel time through the network, from
any node to a given destination node. Bellman applied
the functional equations approach to devise an iterative
algorithm which converges to the solution in at most N -
1 steps for a network with N nodes.
