Although a lot of important results are achieved in the research of traditional ant colony optimization, and there are many shortcomings in solving large-scale combination optimization problems, such as premature convergence and time consuming. Therefore, a parallelization of ant colony algorithm based on the combination of neighborhood search algorithm and ant colony optimization is proposed and realized. The results of experiment show that the parallel algorithm has much higher quality and stability than that of traditional serial ant colony optimization for solving large-scale TSP problems.