This paper introduces a new rich vehicle routing problem faced by companies that consider alternative-fuel vehicle (AFV) adoption into a service fleet consisting of gasoline or diesel vehicles. The service operation addressed here differs from delivery operations in that a vehicle has to stop for extended periods of time while its driver serves customers. We discuss measuring the impact of AFV adoption on fleet operations from multiple perspectives and formulate four objective functions to represent the defined performance metrics in a generalized mixed-integer linear programming model. The model can accommodate various AFV types with respect to driving range, refueling time, and availability of refueling stations. We develop a variable neighborhood search heuristic to solve large-scale problems efficiently. Results from the research show that the classical vehicle routing objective of minimizing total vehicle miles traveled does not work well in this emerging problem; instead, an objective such as minimizing carbon emissions or fuel costs provides more desirable solutions. The results also show that in service fleets, refueling time has lesser impact on fleet performance compared to service station availability or vehicle range. From a managerial standpoint, this indicates that investment in range extension or establishing service stations is more important than investment in faster refueling capability.