A Lagrangian Relaxation Method for an Online Decentralized Assignment of Electric Vehicles to Charging Stations

This article addresses the issue of assigning electric vehicles to charging stations, minimizing the maximum completion time. It envisions the interaction between electric vehicles and the charging infrastructure to match supply and demand in a decentralized and collaborative fashion. For this reason, the assignment issue is regarded as a linear integer programming problem and a Lagrangian relaxation heuristic is proposed to solve it. Thus, each electric vehicle selects the charging station and the most convenient path to minimize its own completion time. The completion time of each electric vehicle is composed of the travel time (TT), the waiting time (WT) at the station, and the charging time. The Lagrangian relaxation heuristic results are more effective compared to other local heuristic procedures performances and demonstrate a fair allocation of the electric vehicles to the charging stations. The analysis of the time components of the solution on a real urban network highlights that the TT is negligible with respect to the WT and charging time, that are comparable. Therefore, a reservation policy is also considered.