ON A ROUTING PROBLEM

Abstract

Given a set of N cities, with every two linked by a road, and the times required to traverse these roads, we wish to determine the path from one given city to another given city which minimizes the travel time. The times are not directly proportional to the distances due to varying quality of roads, and v varying quantities of traffic. The functional equation technique of dynamic programming, combined with approximation in policy space, yield an iterative algorithm which converges after at most (N-1) iterations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 20, 1956
Accession Number
AD0606258

Entities

People

  • Richard E. Bellman

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computers
  • Convergence
  • Dynamic Programming
  • Equations
  • Hard Copy
  • Inequalities
  • Iterations
  • Nonlinear Systems
  • Sequences
  • Travel Time

Fields of Study

  • Mathematics

Readers

  • Environmental Impact Assessment (EIA) of Proposed Air Force Base Actions.
  • Operations Research

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers