We provide an improved algorithm called “a neighborhood expansion tabu search algorithm based on genetic factors” (NETS) to solve traveling salesman problem. The algorithm keeps the traditional tabu algorithm’s neighborhood, ensure the algorithm’s strong climbing ability and go to the local optimization. At the same time, introduce the genetic algorithm’s genetic factor (crossover factor and variation factor) to develop new search space for bounded domain. It can avoid the defects of the alternate search. The results show that this optimization algorithm has improved a lot in the target of “target value”, “convergence” and compared with traditional tabu algorithm and genetic algorithm.