Key to the mass adoption of electric vehicles is the establishment of a sufficient battery service infrastructure network on the basis of customer behavior and psychology. Motivated by EV service infrastructure network design under the battery leasing/electric car sharing service business models, we present an electric vehicle battery service network design problem considering a customers satisfaction related to “range anxiety” and “loss anxiety”. The problem is formulated as a linear integer programming model under deterministic and fuzzy scenarios. A Tabu Search heuristic combined with GRASP is proposed to efficiently solve the problem. Finally, we conduct parametric analysis on real-world road networks.