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.