Optimum drilling path planning for a rectangular matrix of holes using ant colony optimisation

摘要

This paper investigates optimum path planning for CNC drilling machines for a special class of products that involve a large number of holes arranged in a rectangular matrix. Examples of such products include boiler plates, drum and trammel screens, connection flanges in steel structures, food-processing separators, as well as certain portions of printed circuit boards. While most commercial CAD software packages include modules that allow for automated generation of the CNC code, the tool path planning generated from the commercial CAD software is often not fully optimised in terms of the tool travel distance, and ultimately, the total machining time. This is mainly due to the fact that minimisation of the tool travel distance is a travelling salesman problem (TSP). The TSP is a hard problem in the discrete programming context with no known general solution that can be obtained in polynomial time. Several heuristic optimisation algorithms have been applied in the literature to the TSP, with varying levels of success. Among the most successful algorithms for TSP is the ant colony optimisation (ACO) algorithm, which mimics the behaviour of ants in nature. The research in this paper applies the ACO algorithm to the path planning of a CNC drilling tool between holes in a rectangular matrix. In order to take advantage of the rectangular layout of the holes, two modifications to the basic ACO algorithm are proposed. Simulation case studies show that the average discovered path via the modified ACO algorithms exhibit significant reduction in the total tool travel distance compared to the basic ACO algorithm or a typical genetic algorithm.