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