On the Shortest Path Touring n Circles
Chang-Chien Chou · International Journal of Advancements in Computing Technology · 2012
This paper solves the problem of computing the shortest Euclidean path touring n disjoint circles in 2D which is a generalization of the Travelling Salesman Problem (TSP) in Euclidean 2D plane and is not purely combinatorial. Based on the author’s previous work and the philosophy of Branch-andBound (B&B), this work presents a new exact algorithm to solve the problem. The empirical results have shown the correctness and the performance of the proposed algorithm dealing with a small number of circles. The proposed algorithm can be conducted in layered manufacturing of rapid prototyping, displacement of wireless sensor networks, or other related computer-aided design and manufacturing applications.