Accession Number:

ADA256112

Title:

The Voronoi Diagram for the Euclidean Traveling Salesman Problem Is Piecemeal Quartic and Hyperbolic

Descriptive Note:

Corporate Author:

ARMY CECOM SIGNALS WARFARE DIRECTORATE VINT HILL FARMS STATION VA

Personal Author(s):

Report Date:

1990-06-01

Pagination or Media Count:

32.0

Abstract:

The Euclidean traveling salesman problem ETSP is a special case of the general traveling salesman problem TSP. Given a set of cities and the associated costs between pairs of cities, the goal of the TSP is to find the optimal tour which visits every city exactly once, except for the start city, which is revisited at tours end. Unlike the TSP which utilizes a general cost function to link cities, the ETSP employs the Euclidean distance between cities as the metric, and equates optimality with shortest tour length. The objective of this research is to attempt to rigorously characterize the underlying geometry of ETSP tour construction, and subsequently to pursue an algorithm for an exact solution the problem for city databases of modest size. Artificial Intelligence, Data Fusion, Topology.

Subject Categories:

  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE