Social-Aware Optimal Electric Vehicle Charger Deployment on Road Network

EasyChair Preprint 1173

Abstract

With the increasing awareness towards protecting the environment, people are paying more and more attention to renewable energy vehicles, especially, the electric vehicles (EVs). Accompanying the rapid growing number of EVs, challenges raise at the same time, about how to place EV chargers (EVC), within a city, to satisfy multiple types of charging demand. Aiming at providing better EVC station deployment plan to benefit the whole society to the greatest extent, we propose a problem called Social-Aware Optimal Electric Vehicle Charger Deployment} (SOCD) on a real road network. The SOCD problem is different from the previous works mainly in three aspects, 1) we assume that the charging demand should be satisfied not only in urban areas but also in rural areas; 2) our work is the first one that assumes an EVC station can have multiple types of charging plugs, which is more reasonable in the real world; 3) different from the regional deployment from previous literature, our SOCD directly works on a real road network and EVC stations can be deployed at any POI laying on the road network. We show that the SOCD problem is NP-hard and thus there exists no efficient polynomial algorithm. Therefore, we design several efficient and effective heuristics to solve the SOCD problem. Furthermore, we investigate the incremental case, that is, given an existing EVC station deployment plan and extra more budget, we need to decide where and how many to place more chargers. Finally, we conduct extensive experiments on the real road network of Shanghai to demonstrate both the effectiveness and efficiency of our algorithms.

Keyphrases: EV Charger Deployment, combinatorial optimization, road network, urban planning

@booklet{EasyChair:1173,
  author    = {Qiyu Liu and Yuxiang Zeng and Lei Chen and Xiuwen Zheng},
  title     = {Social-Aware Optimal Electric Vehicle Charger Deployment on Road Network},
  howpublished = {EasyChair Preprint 1173},
  year      = {EasyChair, 2019}}