Abstract： Aimed at the combinatorial optimization of tool trajectory upon the complex freeform curved surface piece, Hamiltonian path was adopted to transform it to an open traveling salesman problem (OTSP). Meanwhile the strategy of integrating the problemunrelated optimization algorithm and the problemrelated local search was adopted. First, the membership cloud models were introduced to adapt and adjust the randomness controlled by the ant colony algorithm. Then, the Kopt partial search strategy was introduced to find the solution to OTSP in respect of the combinatorial optimization of the tool trajectory based on the improved membership cloud models ant colony algorithm (MCMACA). The simulation result shows that MCMACA features better global search ability and local convergence. Meanwhile, it has obvious advantages in terms of optimization of the spray painting robot tool trajectory on complex curved surface.