Monte Carlo Tree Search Heuristic Algorithm for Placement Routing Problem in a Dual-Gantry Placement Machine

In printed circuit board assembly (PCBA), effectively and reliably addressing the placement routing problem (PRP) for dual-gantry placement machines continues to be a considerable issue. In contrast to single-gantry placement machines, the placement routing of dual-gantry placement machines needs to solve the problem of the variation of the placement route when the placement point is distributed in different gantries. This article proposes a Monte Carlo tree search heuristic algorithm (MCTSHA) for tackling PRP. The algorithm comprises a Monte Carlo tree search (MCTS) framework and a cycle route generation heuristic algorithm (CRGHA). In the proposed MCTSHA, the MCTS framework completes the construction and decision-making of the search tree of the mounting cycle, and CRGHA completes the generation of placement routes for each search tree node according to the characteristics of the PRP. The MCTSHA applies a root node parallelization structure to improve the solving efficiency. The proposed algorithm offers advantages in the aspects of scalability and flexible adjustment of search strategy. Finally, the experimental results demonstrate that the proposed MCTSHA improves at least 3.40% over mainstream algorithms placement routing results.