Determining the optimal location and capacity of energy storage systems (ESS) is a crucial planning problem for the virtual power plant (VPP). However, the trading characteristics of VPP have not been considered in the existing ESS optimal planning research due to its complicated mathematical relationships. In this paper, considering the VPP trading environment, a bi-level optimization model is established to determine ESS's optimal location and capacity. The proposed model is a mixed-integer, nonlinear, multi-period, and large-scale optimal problem, which is difficult to solve directly by traditional methods. Usually, linearizing or decomposing methods are used to simplify the original problem for solving. However, the available simplification methods greatly change the original problem, resulting in a large deviation between the simplified and the original problems. This paper proposes a novel interactive solution framework for the bi-level model based on the decomposition-coordination algorithm for improving the solution accuracy. The simulation results show the effectiveness of the ESS planning scheme in VPP under different objectives, EVs types, and electricity prices. Further analyses based on the IEEE 17-bus VPP system demonstrate that the proposed method can save nearly 29.01%, 28.08%, 26.62% of the ESS cost on average compared with the loss sensitivity factor, MILP-Based, and Benders decomposition methods, respectively. (C) 2020 Elsevier Ltd. All rights reserved.