2007/10/02 by Anthony A. Ruffa, Ruffa, Anthony A.
Computer Science · Engineering · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.0710.0539
arxiv created 2007/10/02 · openalex publication_date 2007/10/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A solution to the benchmark ATT48 Traveling Salesman Problem (from the TSPLIB95 library) results from isolating the set of vertices into ten open-ended zones with nine lengthwise boundaries. In each zone, a minimum-length Hamiltonian Path (HP) is found for each combination of boundary vertices, leading to an approximation for the minimum-length Hamiltonian Cycle (HC). Determination of the optimal HPs for subsequent zones has the effect of automatically filtering out non-optimal HPs from earlier zones. Although the optimal HC for ATT48 involves only two crossing edges between all zones (with one exception), adding inter-zone edges can accommodate more complex problems.