Abstract: A model of distribution vehicle scheduling problem is established,on the basis of analyzing such shortcomings of traditional heuristic algorithms as low searching efficiency and immature convergence.A DNA evolutionary algorithm is established for solving the distribution vehicle scheduling problem.The algorithm is improved in mutation,and is applied to Vehicle Scheduling Problem(VSP) successfully.VSP is a combinatorial optimization problem.In order to verify the effectiveness of the DNA evolutionary algorithm,a standard VSP problem is used.The simulation results show that the algorithm is very easy and feasible,and compared with other optimization algorithms,it has rapid convergence ability and searching ability.