Accession Number : AD0846676

Title :   Rapid Near-Optimal Solution of Large Minimal Cyclic Routing Problems.

Descriptive Note : Technical rept. Jan-May 67 and May-Sep 68,

Corporate Author : AEROSPACE CORP SAN BERNARDINO CA SAN BERNARDINO OPERATIONS

Personal Author(s) : DeWitte, Leendert

Report Date : 20 JAN 1969

Pagination or Media Count : 25

Abstract : The solution to the problem of finding the minimal cyclic route through N points is approached by starting with a minimal route through a small number n of the points. A theorem is introduced which strongly limits the choices when trying to derive the minimal cyclic route when an additional point is added to an existing minimal route. Using this theorem, a basic algorithm has been constructed in which the number of operations are proportional to N cubed. The basic algorithm gives the correct optimal solution for the Fulkerson 48 city problem in a few seconds of CDC-6600 time, but, in general, solutions are not necessarily optimal. For very large problems (i.e., hundreds of points), refinements are introduced in the form of the best composite of a number of near-optimal approximate solutions. (Author)

Descriptors :   (*OPERATIONS RESEARCH, SCHEDULING), (*TRANSPORTATION, FLOW CHARTING), OPTIMIZATION, ALGORITHMS, APPROXIMATION(MATHEMATICS), RANGE(DISTANCE), TARGETS, GRAPHICS.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE