This article studies optimal plug-in electric vehicle (PEV) charging station planning, with consideration for the 'overstay' problem. Today, public PEV charging station utilization is typically around 15%. When un-utilized, the chargers are either idle or occupied by a fully charged PEV that has not departed. We call this 'overstay.' This motivates a strategy for increasing utilization by interchanging fully charged PEVs with those waiting for service-an issue which is not well addressed in the existing literature. Thus, this article studies the PEV charging station planning problem taking strategic interchange into account. To our best understanding, this has not been studied in the literature. With interchange, the objective is to enhance the charger utilization rate and, thus, reduce the number of chargers. This potentially reduces the capital investment and operational cost. A novel power/energy aggregation model is proposed, and a chance-constrained stochastic programming planning model with interchange is developed for a public charging station to incorporate customer demand uncertainties. Numerical experiments are conducted to illustrate the performance of the proposed method. Simulation results show that incorporating strategic interchange operation can significantly decrease the number of chargers, enhance utilization and economic efficiency.