It is expected that electric vehicles (EVs) will be important part of smart gird, not only in form of load but also as distributed energy source in Vehicle to Grid (V2G) system. As increase of EVs integration, V2G contributes to improve flexibility, reliability and stability of grid by providing ancillary services. These services, however, could accelerate degradation of battery whose price is almost half of EV. Thus, battery degradation cost must be considered while scheduling of EV charging. In this paper, a battery degradation cost model of EV lithium-ion batteries was incorporated in the optimal charging schedule of 400 EVs. EVs are located to 33 bus system in order to consider network losses in calculations. Heuristic algorithms such as Genetic Algorithm (GA), Differential Evolution (DE), Particle Swarm Optimization (PSO) and Artificial Bee Colony (ABC) are used for solving the associated optimization problem. The objective function aims to maximize user profit under dynamic pricing. Also, distribution system and EVs constraints are considered during optimization. The numerical results illustrate that each of the used heuristic algorithms able to mitigate peak loads and improve voltage levels. GA presents the most profitable charging scheduling in terms of EV owners.