Accession Number : ADA115357

Title :   An O(NlogN) Planar Travelling Salesman Heuristic Based on Spacefilling Curves,

Corporate Author : GEORGIA INST OF TECH ATLANTA PRODUCTION AND DISTRIBUTION RESEARCH CENTER

Personal Author(s) : Platzman,L K ; Bartholdi,J J , III

PDF Url : ADA115357

Report Date : Apr 1982

Pagination or Media Count : 15

Abstract : N points in a square of area A may be sorted according to their images under a spacefilling mapping to give a tour of length at most 2 square root of (NA). If the points are statistically independent under a smooth distribution, with N large, then the tour will be roughly 25% longer than optimum (and a simple enhancement reduces this to 15%). The algorithm is easily coded: a complete BASIC program is included in the appendix. Since the algorithm consists essentially of sorting, points are easily added or removed. Our method may also be used with simple dynamic programming to solve TSP path problems.

Descriptors :   *Points(Mathematics), *Routing, *Sorting, Sequences(Mathematics), Length, Heuristic methods, Algorithms, Mapping, Filling, Space(Room), Paths, Dynamic programming

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE