ON A ROUTING PROBLEM*

ON A ROUTING PROBLEM*

1958 | BY RICHARD BELLMAN (The RAND Corporation)
The paper by Richard Bellman addresses a routing problem involving a set of \( N \) cities, each connected by roads with varying travel times due to road conditions and traffic. The goal is to find the optimal path from one city to another that minimizes travel time. Bellman proposes a dynamic programming approach combined with approximation in policy space to solve this problem iteratively. The method involves defining a sequence of functions \( f_i \) that represent the minimum time to travel from city \( i \) to the destination city \( N \). The nonlinear system of equations for these functions is derived using the principle of optimality. Bellman proves the uniqueness of the solution and demonstrates that the iterative algorithm converges after at most \( (N-1) \) iterations. The method is efficient for practical problem sizes, making it suitable for both manual and machine computation. The paper also discusses the monotone increasing convergence of the iterative scheme and provides a computational analysis, showing that it is feasible for values of \( N \) up to 50 or 100.The paper by Richard Bellman addresses a routing problem involving a set of \( N \) cities, each connected by roads with varying travel times due to road conditions and traffic. The goal is to find the optimal path from one city to another that minimizes travel time. Bellman proposes a dynamic programming approach combined with approximation in policy space to solve this problem iteratively. The method involves defining a sequence of functions \( f_i \) that represent the minimum time to travel from city \( i \) to the destination city \( N \). The nonlinear system of equations for these functions is derived using the principle of optimality. Bellman proves the uniqueness of the solution and demonstrates that the iterative algorithm converges after at most \( (N-1) \) iterations. The method is efficient for practical problem sizes, making it suitable for both manual and machine computation. The paper also discusses the monotone increasing convergence of the iterative scheme and provides a computational analysis, showing that it is feasible for values of \( N \) up to 50 or 100.
Reach us at info@study.space
Understanding ON A ROUTING PROBLEM