A hybrid heuristic method for multi-color spraying path planning

Path planning is the primary task for multi-color spraying. This paper formulates multi-color spraying path planning as a generalization of the Traveling Salesman Problem (TSP). The spraying patterns with single/dual-nozzle spray gun are given separately. First, multi-color spray path planning of single nozzle spray gun is described as a Clustered Traveling Salesman Problem (CTSP). Greedy randomized adaptive search procedure (GRASP) and variable neighborhood search (VNS) are applied to solution of the problem. Then, multi-color spray path planning of dual-nozzle spray gun is defined as set-Clustered Traveling Salesman Problem (set-CTSP), which is NP-hard similar to CTSP. We propose a new hybrid heuristic algorithm to obtain the minimum path of the spray gun movement. The initial solution of the path is obtained from the color combination probability and GRASP. The neighborhood structure of the solution is continuously changed by four variable neighborhood search operators, and the color combination probability is updated according to the distance cost of the corresponding solution. Finally, extensive experiments with different sizes and patterns have be done verifying the feasibility of multi-color spray path planning based on single nozzle gun and dual-nozzle spray gun, while the dual-nozzle spray gun can reduce the gun travel distance compared to the single-nozzle spray gun.