Abstract: A multi-objective model is presented according to the comprehensive analysis of the electric power line overhaul in Liaoning province, taking account of various constraints. The coloring problem of graph theory is combined with an improved ant colony algorithm to plan optimally the overhaul. The core of the improved algorithm is to make dynamically the pheromones on routes adaptive so as to enable the increment of pheromones to become great from small to strengthen the ability for local search, and then become small from great to strengthen the ability for global search. Such a cyclical change is thus highly beneficial to an algorithm to get rid of locally optimal solution. The merit of the improved ant colony algorithm is that not only the satisfactory solution is obtained, but also the searching speed is improved. Simulation results showed that the improved ant colony algorithm is superior to the conventional one in quality.