Rapid Near-Optimal Solution of Large Minimal Cyclic Routing Problems.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 20, 1969
- Accession Number
- AD0846676
Entities
People
- Leendert Dewitte
Organizations
- The Aerospace Corporation