A Method for Solving Combinatoral Optimization Problems

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 29, 2008
Accession Number
ADD020394

Entities

People

  • Anthony A. Ruffa

Organizations

  • United States Department of the Navy

Tags

Communities of Interest

  • Air Platforms
  • Space

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Chemical Reactions
  • Computations
  • Computer Programming
  • Crossings
  • Filtration
  • Genetic Algorithms
  • Inventions
  • Job Shop Scheduling
  • Optimization
  • Patent Applications
  • Patents
  • Permutations
  • Scheduling (Production)
  • Three Dimensional
  • United States

Readers

  • Graph Algorithms and Convex Optimization.
  • Marine Ecological Systems Migration
  • Systems Analysis and Design