A Two-Layer Heterogeneous Ant Colony System With Applications in Part-Picking Planning

Abstract

The tape carrier packaging machine with multiple sucking discs is designed for modern, high-speed packaging production line, which is an important part of the electronic manufacturing process. The efficiency of the part-picking can directly affect the efficiency of the packaging production line. The problem involves at least three coupled sub-problems: the number of picking rounds, the matching relationship between the parts and sucking discs, and the picking order. Because the actual industrial production requires real-time or soft real-time scheduling, the challenge is how to efficiently solve this multi-dimensional combinatorial optimization problem within a fairly limited time. The existing advanced algorithms such as the genetic algorithm and the simulated annealing algorithm usually require complex and time-consuming encoding and decoding while solving this problem. In contrast, the ant colony algorithm has advantages in the convergence rate and parallel computing, especially for searching high dimensional paths in dynamic environments. In order to further improve the comprehensive performance of the ant colony algorithm in solving multi-dimensional coupled optimization problems in extremely limited time, we propose a novel two-layer heterogeneous ant colony system based on three strategies: (1) a bottom-up two-layer solution framework to decouple the original tightly coupled problem into a loosely coupled problem composed of two sub-problems; (2) a candidate cluster augmentation strategy based on the Delaunay triangulation to improve the diversity and quality of the clusters; (3) a co-evolution between a pair of heterogeneous colonies by mixing the high-quality pheromone properly as well as a co-evolution based on the prior knowledge. Finally, through a large set of comparisons, the average picking efficiency of Two-layer Heterogeneous Ant Colony System improved by the three proposed strategies is 13–16% higher than that of other popular heuristic algorithms.