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

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 tour's 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1990
Accession Number
ADA256112

Entities

People

  • T. M. Cronin

Tags

Communities of Interest

  • Air Platforms
  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computer Programming
  • Computer Science
  • Computers
  • Coordinate Systems
  • Data Fusion
  • Databases
  • Fungi
  • Geometry
  • Information Processing
  • Mathematical Programming
  • New York
  • Operations Research
  • Optimization
  • Theoretical Computer Science
  • Topology

Fields of Study

  • Computer science

Readers

  • Government Contracting/Procurement.
  • Graph Algorithms and Convex Optimization.
  • Military Mobilization and Reserve Forces Studies.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms