Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper presents a recursive clustering algorithm for solving large Traveling Salesman Problems (TSPs) by segmenting cities into clusters of up to five, each with a centroid, and employing constrained TSP and simulated annealing for intra-cluster routing. The FPGA-based implementation demonstrates significant scalability and efficiency, allowing for the routing of a larger number of cities while maintaining low resource utilization through the use of squared Euclidean distance calculations. Key results indicate that this method not only enhances routing accuracy but also significantly improves operational frequency compared to traditional approaches.
Clustering cities into manageable groups allows for routing solutions that scale effectively, handling more cities with greater efficiency than ever before.
The Traveling Salesman Problem (TSP) continues to attract significant research interest due to its critical role in various applications. This paper introduces a recursive clustering approach that divides cities into a limited number of clusters, each containing up to five cities and its own centroid. Constrained TSP and simulated annealing techniques are employed to route cities within each cluster, using the centroids of neighboring clusters as entry and exit points for the routing process. This method offers the benefit of producing accurate and cost-effective routing solutions, due to the reduced number of cities in each cluster. The connections between cluster centroids are established using simulated annealing. The FPGA-based proposed hardware implementation demonstrates the feasibility of routing a large number of cities, as the approach leverages memory to store cluster information. Consequently, the method is independent of the FPGA's logic hardware, and its scalability depends on the FPGA's memory capacity. Furthermore, distance calculations using approximate methods for the FPGA execution are compared and the squared Euclidean is chosen due to its low resources'utilization. Compared to previous methods, the proposed approach can handle more cities for routing, offering better scalability and a higher operating frequency.