GEOMETRIC APPROACHES TO SOLVE THE CHEBYSHEV TRAVELING SALESMAN PROBLEM

Several heuristic procedures based on geometric concepts have been developed for the Chebyshev (or too) Traveling Salesman Problem (CTSP),which has numerous applications in materials handling and information storage-retrieval. The following study is concerned with evaluating the performance of geometric approaches as a function of the shape of the service region and the number of points to be sequenced. A new approach, the band insertion heuristic, is also introduced and compared with existing procedures. Trade-offs in tour quality and solution effort are the primary focus of the study, which is empirical in nature; however, the results generally apply to a wide range of configurations. © 1990 Taylor & Francis Group, LLC.