  We formulate an optimal scheduling problem for battery swapping that assigns
to each electric vehicle (EV) a best station to swap its depleted battery based
on its current location and state of charge. The schedule aims to minimize
total travel distance and generation cost over both station assignments and
power flow variables, subject to EV range constraints, grid operational
constraints and AC power flow equations. To deal with the nonconvexity of power
flow equations and the binary nature of station assignments, we propose a
solution based on second-order cone programming (SOCP) relaxation of optimal
power flow (OPF) and generalized Benders decomposition. When the SOCP
relaxation is exact, this approach computes a globally optimal solution. We
evaluate the performance of the proposed algorithm through simulations. The
algorithm requires global information and is suitable for cases where the
distribution network, stations, and EVs are managed centrally by the same
operator. In Part II of the paper, we develop distributed solutions for cases
where they are operated by different organizations that do not share private
information.
