Accession Number:

ADA149337

Title:

Spacefilling Curves and the Planer Travelling Salesman Problem. Revision.

Descriptive Note:

Corporate Author:

GEORGIA INST OF TECH ATLANTA SCHOOL OF INDUSTRIAL AND SYSTEMS ENGINEERING

Report Date:

1984-10-01

Pagination or Media Count:

21.0

Abstract:

This paper analyzes the performance of a novel heuristic to obtain the minimal-length tour of N given points in the plane they are sequenced as they appear along a spacefilling curve. The algorithm consists essentially of sorting, so it is easily coded and requires only ON memory and ON log N operations. Its performance is shown to be competitive with that of other available methods. Key words Planar travelling salesman problem, heuristic algorithm, spacefilling curve.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE