Social-Aware Optimal Electric Vehicle Charger Deployment on Road Network

With the increasing awareness towards protecting environment, people are paying more attention to 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. To provide a better EVC station deployment plan to benefit the whole society, we propose a problem called Social-Aware Optimal Electric Vehicle Charger Deployment (SOCD) on road network. The SOCD problem is hard and different from existing work in three aspects, 1) we assume that the charging demand should be satisfied not only in urban areas but also in relatively rural areas; 2) our work is the first one that considers an EVC station should have multiple types of charging plugs, which is more reasonable in real world; 3) different from the regional deployment solutions in previous literature, our SOCD directly works on a real road network and EVC stations are placed at appropriate POIs laying on the road network. We show that the SOCD problem is NP-hard. To deal with the hardness, we design two heuristic algorithms whose efficiency and effectiveness can be experimentally demonstrated. 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 real road network of Shanghai to demonstrate both effectiveness and efficiency of our algorithms.