Considering employing the electric vehicles to deliver parts to stations for automotive assembly lines based on in-plant milk-run delivery strategy, an electric vehicle delivery routing and battery swap station location problem was presented, and a mathematical programming model with an objective function of minimizing total cost of the system was set up. To tackle this complicated problem, the property was analyzed, and a two-phase dynamic programming method was adopted to obtain the global optimum for small scale problems. For medium and large scale problems, both the population decomposition strategy and the depth neighborhood search operator based on Lévy flight were applied to develop an improved discrete cuckoo search algorithm. Finally, through the comparison of the two-phase dynamic programming method, real genetic algorithm and modified artificial bee colony algorithm, the simulation experiments were carried out to illustrate the effectiveness and great advantages in stability, deep searching ability and convergence of the algorithm.