Browse Prior Art Database

Fast Heuristic for the Traveling Salesman Problem

IP.com Disclosure Number: IPCOM000114712D
Original Publication Date: 1995-Jan-01
Included in the Prior Art Database: 2005-Mar-29
Document File: 2 page(s) / 60K

Publishing Venue

IBM

Related People

Iwano, K: AUTHOR [+2]

Abstract

Disclosed is an approximation algorithm for the Traveling Salesman Problem (TSP) which has a vast variety of applications. The disclosed algorithm is a tour construction heuristics that builds a tour from scratch. It uses k-d tree, a data structure that enables fast near-neighbor queries in geometric space. Also it utilizes the van der Corput sequence, one of low-discrepancy sequences that attains the lower bound of discrepancy.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 93% of the total text.

Fast Heuristic for the Traveling Salesman Problem

      Disclosed is an approximation algorithm for the Traveling
Salesman Problem (TSP) which has a vast variety of applications.  The
disclosed algorithm is a tour construction heuristics that builds a
tour from scratch.  It uses k-d tree, a data structure that enables
fast near-neighbor queries in geometric space.  Also it utilizes the
van der Corput sequence, one of low-discrepancy sequences that
attains the lower bound of discrepancy.

      The heuristic proceeds as follows.  First, it picks up a set of
representative points out of all data points so that they well
reflect the overall distribution of data points.  These
representative points are chosen from internal nodes of a k-d tree,
which is constructed for later use in near-neighbor queries, in order
to distribute them uniformly in the input data region.  The heuristic
uses the addition method, and constructs a subtour from these
representative points.  When the addition method is applied,
representative points are picked up in the order of van der Corput
sequence so that chosen points distribute as uniformly as possible at
any stage of subtour construction.  The heuristic then grows the
subtour thus obtained by applying the addition method for the rest of
points.  More concrete description of the heuristic is depicted in
Fig. 1.

      Fig. 2 roughly shows how the heuristic works for an instance
of size 1127 (a).  Figure 2b is a set of represe...