Charging scheduling problem of an M-to-N electric vehicle charger

This study investigates a real case of charging scheduling of an electric vehicle charger with multiple ports called M-to-N charger. The charger is designed for a multi-unit dwelling facility and can charge N electric vehicles simultaneously despite the supplied charging capacity being limited to only M electric vehicles. The electric vehicles arrive at the charger randomly and stay for their desired length of time, during which they must be charged as much as possible with minimum electric cost. The scheduling problem considers four objectives: maximizing the total charging amount, minimizing the total charging cost, minimizing the charging completion time, and maximizing the charging balance among the electric vehicles. A mixed-integer linear programming model and a relaxation-based heuristic algorithm are developed. Computational experiment results show that the proposed heuristic algorithm can generate schedules within 8 s for this case study by using an open-source linear programming solver. Compared with the mixed-integer programming algorithm, the proposed heuristic algorithm can provide solutions with less than 7% charging amount gap and 4% price gap. The proposed heuristic algorithm is successfully implemented in a real M-to-N charger.