METHOD FOR SOLVING COMBINATORAL OPTIMIZATION PROBLEMS

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.