Optimal air-move path generation based on MMAS algorithm

Abstract

Air-move paths are executed by machine tools to cut 2D patterns that must retract (or turn off) when travelling from one pattern to the next. These retractions are nonproductive and hence their travelling distances should be minimised. For instance, reducing air-move time can increase the efficiency of cloth cutting in the garment industry. In this paper, a novel algorithm is proposed to solve this problem. In several past works, this problem is formulated as an instance of the generalised travelling salesman problem. We divide this problem into two independent sub-optimal problems (pattern cutting order and entry/exit cutting point) and iteratively solve them using a max–min ant system. This strategy can greatly narrow down the search space. We also perturb the pattern cutting order to avoid dowelling at a local minimum. Experiments show that the proposed algorithm is able to obtain near-optimal solutions, with the results beating the three state-of-the-art algorithms that were used as the benchmarks.

Keywords:

• air-move path
• cutting machine
• tool path
• max–min ant system

Acknowledgements

Thanks to Prof. Ajay Joneja for his proof reading work and the reviewers whose comments helped us improve the work.

Funding

This work is supported by the Natural Science Foundation of China [grant number 61100088]; the Natural Science Foundation of Guangdong Province [grant number S2013010013133]; and the Fundamental Research Projects of Shenzhen [grant number JC201105160526A, GJHS20120627113219599].