Accession Number:

ADD020394

Title:

A Method for Solving Combinatoral Optimization Problems

Descriptive Note:

Patent application, Filed 29 Sep 2008

Corporate Author:

DEPARTMENT OF THE NAVY WASHINGTON DC

Personal Author(s):

Report Date:

2008-09-29

Pagination or Media Count:

33.0

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 Hamiltonian paths for subsequent zones has the effect of filtering out non-optimal Hamiltonian paths from earlier zones.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE