Speeding up a programmable drilling machine by a travelling salesman algorithm

What is it about?

METELCO, a printed circuit boards (PCB) manufacturer in Greece, noticed that drilling the boards was a production bottleneck. The programmable drill spent a seemingly long time moving the drill head between drilling locations, and an employee was assigned the task of planning the drill head's path. Although the paths thus generated were efficient, the whole procedure took too much time, slowing down production. The problem was identified as a planar travelling salesman problem but in the L - infinity norm (the machine has a x and a y motor, thus the longest of x,y is important). Several heuristic algorithms were tried and proved successful, their outcome being slightly better than what the operator came up. The algorithms were then implemented in an ad hoc ad on to the drilling machine, thus semi automating the whole drilling procedure.

Featured Image

Why is it important?

Another example of the importance of the TSP algorithms, and perhaps the first use of the L - infinity norm in this context.

Perspectives