In this paper, a new approach is presented to determine the optimal number, location and capacity of each Electric Vehicle (EV) parking lot to maximize the profit of electrical distribution companies. In the proposed approach, while considering the term of "EV owners' welfare", the effect of this term on optimal location and capacity of the EV parking lots is also investigated. Moreover, the expected growth percentage of the EVs in the upcoming years is presented as a probabilistic parameter. The way of affecting the planning of the parking lots is analyzed. Also, an approach has been presented based on K-means clustering method to estimate the number of EVs approaching for a parking lot which can lead to a more accurate prediction of the costs and incomes of establishing a parking lot. The presented approach is performed on the 69 node radial distribution system and the results are analyzed. (C) 2016 Elsevier Ltd. All rights reserved.