Plug-in electric vehicles (PEVs) appear to offer a promising option for mitigating greenhouse emission. However, uncoordinated PEV charging can weaken the reliability of power systems. The proper accommodation of PEVs in a power grid imposes many challenges on system planning and operations. This work aims to investigate optimal PEV coordination strategies with cost-benefit analysis. In Part I, we first present a new method to calculate the charging load of PEVs with a modified Latin hypercube sampling (LHS) method for handling the stochastic property of PEVs. We then propose a new two-stage optimization model to discover the optimal charging states of PEVs in a given day. Using this model, the peak load with charging load of PEVs is minimized in the first stage and the load fluctuation is minimized in the second-stage with peak load being fixed as the value obtained in the first stage. An algorithm based on linear mixed-integer programming is provided as a suitable solution method with fast computation. Finally, we present a new method to calculate the benefit and cost for a PEV charging and discharging coordination strategy from a social welfare approach. These methods are useful for developing PEV coordination strategies in power system planning and supporting PEV-related policy making.