In this study, a framework is proposed for minimizing the societal cost of replacing gas-powered household passenger cars with battery electric ones (BEVs). The societal cost consists of operational costs of heterogeneous driving patterns' cars, the government investments for charging deployment, and monetized environmental externalities. The optimization framework determines the timeframe needed for conventional vehicles to be replaced with BEVs. It also determines the BEVs driving range during the planning timeframe, as well as the density of public chargers deployed on a linear transportation network over time. We leverage datasets that represent U.S. household driving patterns, as well as the automobile and the energy markets, to apply the model. Results indicate that it takes 8 years for 80% of our conventional vehicle sample to be replaced with electric vehicles, under the base case scenario. The socially optimal all-electric driving range is 204 miles, with chargers placed every 172 miles on a linear corridor. All of the public chargers should be deployed at the beginning of the planning horizon to achieve greater savings over the years. Sensitivity analysis reveals that the timeframe for the socially optimal conversion of 80% of the sample varies from 6 to 12 years. The optimal decision variables are sensitive to battery pack and vehicle body cost, gasoline cost, the discount rate, and conventional vehicles' fuel economy. In conclusion, faster conventional vehicle replacement is achieved when the gasoline cost increases, electricity cost decreases, and battery packs become cheaper over the years.