Data processing: artificial intelligence – Knowledge processing system
Reexamination Certificate
2008-09-29
2011-12-06
Gaffin, Jeffrey A (Department: 2129)
Data processing: artificial intelligence
Knowledge processing system
Reexamination Certificate
active
08073797
ABSTRACT:
A method for solving a combinatorial optimization problem and applying the solutions to routing as employed in naval convoying and other transit point scheduling. The method involves isolating a plurality of vertices into open-ended zones with lengthwise boundaries. In each zone, a minimum length Hamiltonian path is found for each combination of boundary vertices, leading to an approximation for the minimum-length Hamiltonian Cycle. The method discloses that when the boundaries create zones with boundary vertices confined to the adjacent zones, the sets of candidate HPs are found by advancing one zone at a time, considering only the vertices in the zone in question (with embedded HPs from previous zones) and an adjacent zone in the direction of progression. Determination of the optimal Hamiltonin paths for subsequent zones has the effect of filtering out non-optimal Hamiltonian paths from earlier zones.
REFERENCES:
Aras,N. et al. “A Kohonen-like Decomposition Method for the Traveling Salesman Problem—Knies Decompose”. ECAI 2000. 14th European Conference on Artificial Intelligence. 2000. pp. 261-265.
Buss Benjamin
Gaffin Jeffrey A
Kasischke James M.
Nasser Jean-Paul A.
Stanley Michael P.
LandOfFree
Method for solving combinatoral optimization problems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for solving combinatoral optimization problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for solving combinatoral optimization problems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4270875