This well-written paper explains the difficulties encountered in reducing the table motion (i.e., path) in positioning circuit boards for drilling the more than 3,000 (sometimes 17,000) holes in a circuit board. The total motion path is, of course, an example of a traveling salesman problem with a large number of points. No feasible algorithm is known for finding the true minimum path. Various approximation techniques have been developed to produce acceptable, if not truly minimal, paths. The author points out some difficulties common to the large class of “band sort” techniques already in common use before suggesting a method which more closely mimics the much used “human operator estimate technique” favored by many manufacturers. This technique starts with a scan of the entire field, “clumping” nearby points together as a unit, taking advantage of both the large scale structure and the small scale structures perceived to be present.

The author’s technique has been used successfully at Photocircuits for two years on more than 1,000 jobs, some with as many as 17,000 points. It has provided an average reduction in path length of 44 percent on their work mix over human operator choice. By adjusting the maximum cluster size, the computational load is adjusted to balance the benefits gained against computational cost. The algorithm is carefully described using a readily understood pseudocode. Performance criteria and results are also delineated. The author has found that on Photocircuits’ own problems (drill movement paths between holes in circuit boards), this algorithm out-performs any other they have used by more than 10:1, on a statistical basis.

This paper should certainly be read by any student studying traveling salesman type problems. It should also be read by users of various algorithms for achieving approximate minimal paths in applied problems.