2018 · 44 citations · 21 references
EngineeringAutomotive EngineeringElectrical EngineeringElectric Vehicle EngineeringElectric Vehicle TechnologyOptimizationCharging InfrastructureCharging SystemsDemand-side ManagementElectricity Load ManagementCharging Load ManagementCharging OptimizationCharging Strategy OptimizationElectric Vehicle Charging Infrastructure PlanningElectric Vehicle Charging StationsElectric Vehicle SchedulingGranularityPrivate Charging Infrastructure
Cars of the future have been predicted as shared and electric. There has been a rapid growth in electric vehicle (EV) sharing services worldwide in recent years. For EV-sharing platforms to excel, it is essential for them to offer private charging infrastructure for exclusive use that meets the charging demand of their clients. Particularly, they need to plan not only the places to build charging stations, but also the amounts of chargers per station, to maximally satisfy the requirements on global charging coverage and local charging demand. Existing research efforts are either inapplicable for their different problem formulations or are at a coarse granularity. In this paper, we formulate the \underlineE lectric \underlineV ehicle \underlineC harger \underlineP lanning (EVCP) problem especially for EV-sharing. We prove that the \shortpro problem is NP-hard, and design an approximation algorithm to solve the problem with a theoretical bound of $1-\frac1 e $. We also devise some optimization techniques to speed up the solution. Extensive experiments on real-world datasets validate the effectiveness and the efficiency of our proposed solutions.
21
Approximation Algorithms for NP-Hard Problems
Dorit S. Hochba · ACM SIGACT News · 1997 · 3.1K citations · Full text