ON A ROUTING PROBLEM*

ON A ROUTING PROBLEM*

1958 | RICHARD BELLMAN
This paper presents a method for solving a routing problem using dynamic programming and approximation in policy space. The problem involves finding the shortest path between two cities in a network of N cities, where travel times between cities are not directly proportional to distances due to varying road conditions and traffic. The authors propose an iterative algorithm based on the functional equation technique of dynamic programming, which converges after at most (N - 1) iterations. The method is a method of exhaustion, meaning it guarantees convergence after a finite number of steps. The paper first formulates the problem as finding the minimum time path from city 1 to city N, given a matrix T of travel times. It then introduces a dynamic programming approach, defining f_i as the minimum time to travel from city i to city N using an optimal policy. The f_i satisfy a nonlinear system of equations, which is shown to have a unique solution. The authors then present an algorithm for solving this system using successive approximations. They start with an initial guess for the f_i and iteratively improve the estimates until convergence. The algorithm is shown to produce a monotone increasing sequence that converges to the true solution. The method is computationally feasible for large N, as it requires only the column of the matrix T for each city. The paper also discusses the computational aspects of the method, noting that it is suitable for both hand and machine computation for N up to 100. It concludes that the method provides a reliable and efficient way to solve the routing problem.This paper presents a method for solving a routing problem using dynamic programming and approximation in policy space. The problem involves finding the shortest path between two cities in a network of N cities, where travel times between cities are not directly proportional to distances due to varying road conditions and traffic. The authors propose an iterative algorithm based on the functional equation technique of dynamic programming, which converges after at most (N - 1) iterations. The method is a method of exhaustion, meaning it guarantees convergence after a finite number of steps. The paper first formulates the problem as finding the minimum time path from city 1 to city N, given a matrix T of travel times. It then introduces a dynamic programming approach, defining f_i as the minimum time to travel from city i to city N using an optimal policy. The f_i satisfy a nonlinear system of equations, which is shown to have a unique solution. The authors then present an algorithm for solving this system using successive approximations. They start with an initial guess for the f_i and iteratively improve the estimates until convergence. The algorithm is shown to produce a monotone increasing sequence that converges to the true solution. The method is computationally feasible for large N, as it requires only the column of the matrix T for each city. The paper also discusses the computational aspects of the method, noting that it is suitable for both hand and machine computation for N up to 100. It concludes that the method provides a reliable and efficient way to solve the routing problem.
Reach us at info@study.space