A Lagrangian Relaxation Method for an Online Decentralized Assignment of Electric Vehicles to Charging Stations
Open Access
- 11 May 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics: Systems
- Vol. 53 (9) , 5568-5579
Abstract
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.Keywords
This publication has 32 references indexed in Scilit:
- Electric Vehicle Charging Station Placement: Formulation, Complexity, and SolutionsIEEE Transactions on Smart Grid, 2014
- Optimization of Charging Stops for Fleet of Electric Vehicles: A Genetic ApproachIEEE Intelligent Transportation Systems Magazine, 2014
- A joint routing and localization algorithm for emergency scenarioAd Hoc Networks, 2014
- Smart Management of Electric Vehicles Charging Operations: the Vehicle-to-Charging Station Assignment ProblemIFAC Proceedings Volumes, 2014
- Limiting Pollution in Ground Control Optimization2011
- Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization TechniqueEuropean Journal of Operational Research, 2010
- Comparing Lagrangian-based distributed algorithms for parallel machine scheduling problemsInternational Journal of Manufacturing Research, 2009
- Distributed Lagrangean relaxation protocol for the generalized mutual assignment problem2006
- Holonic manufacturing scheduling: architecture, cooperation mechanism, and implementationComputers in Industry, 1998
- Complexity of Machine Scheduling Problems1977