- Author
- Kostreva, M. M. | Wiecek, M. M.
- Title
- Time Dependency in Multiple Objective Dynamic Programming.
- Coporate
- Clemson Univ., SC
- Journal
- Journal of Mathematical Analysis and Applications, Vol. 173, No. 1, 289-307, February 1993
- Sponsor
- National Institute of Standards and Technology, Gaithersburg, MD
- Contract
- NIST-GRANT-60NANB0D1023
- Keywords
- time | planning | algorithms | telecommunications | dynamic programming
- Identifiers
- network structure; path planning in networks
- 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.