There is much reason to believe that fleets of service vehicles of many organizations will transform their vehicles that utilize alternative fuels which are more sustainable. The electric vehicle is a good candidate for this transformation, especially which “refuels” by exchanging its spent batteries with charged ones. This paper discusses the issues that must be addressed if a transit service were to use electric vehicles, principally the issues related to the limited driving range of each electric vehicle’s set of charged batteries and the possible detouring for battery exchanges. In particular, the paper addresses the optimization and analysis of infrastructure design alternatives dealing with (1) the number of battery-exchange stations, (2) their locations, (3) the recharging capacity and inventory management of batteries at each facility, and (4) routing and scheduling of the fleet. Several optimization models are developed and some preliminary results are given in the paper.