Accession Number:

AD0606258

Title:

ON A ROUTING PROBLEM

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1956-12-20

Pagination or Media Count:

8.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE