
Accession Number : AD0846676
Title : Rapid NearOptimal Solution of Large Minimal Cyclic Routing Problems.
Descriptive Note : Technical rept. JanMay 67 and MaySep 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 CDC6600 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 nearoptimal 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