On Convexity and Optimization Approaches for Electric Vehicle Charging Scheduling Under Time-of-Use Pricing

Abstract This paper addresses the optimization of electric vehicle charging schedules to minimize total charging costs while ensuring battery life is preserved through charging power limits based on the state-of-charge (SoC). The paper provides theoretical foundations for this charging problem, an area that lacks sufficient theoretical grounding in the literature. The charging power limit is modeled as a decreasing concave function of SoC, and the problem is formulated as a constrained optimal control problem, which, upon discretization, becomes a nonlinear programming (NLP) problem with a linear objective function and a convex feasible region. The paper proves the convexity of the feasible region and the strong duality of the problem, leading to an exact solution approach using a cutting-plane method to solve the Lagrangian dual problem and recover the primal solution. Two greedy heuristics are also proposed, where charging occurs at its limits during low-cost periods; however, theoretical and numerical results show that such greedy strategies may not always be optimal under SoC-dependent constraints, and counterexamples are provided. We further extend the recommended greedy heuristic to the multi-EV setting through a sequential fleet coordination algorithm, suitable for practical charging station management. Through numerical simulations, this work not only compares the efficacy of the proposed methods to existing approaches but also establishes a theoretical and computational foundation for multi-EV charging optimization, laying the groundwork for more complex, large-scale charging strategies.