The Location and Capacity Optimization of Public Charging Station based on Adaptive Large Neighborhood Search Algorithm

Electric taxis (ETs) are the primary users of public charging stations (PCSs). For ET drivers, the convenience of charging services is a critical factor influencing their utilization of PCSs. The location and capacity planning of PCSs directly impact the convenience of these services. An optimal deployment of PCSs should minimize costs incurred by ETs, such as seeking and waiting times. However, the fluctuating demand for charging services complicates the estimation of these costs, thereby challenging the decision-making process for location and sizing. To tackle this issue, this paper proposes an integer programming model for optimizing the location and sizing of PCSs based on the temporal-spatial charging demand patterns of ETs. Additionally, an enhanced adaptive large neighborhood search (ALNS) framework is introduced to solve this model. This framework redesigns three types of destroy operators and four categories of repair operators tailored to the problem's characteristics, incorporates a dynamic destruction range parameter, and integrates greedy algorithms with event-driven simulation methods. Numerical experiments demonstrate the effectiveness of the proposed ALNS algorithm, showing its ability to consistently generate high-quality solutions within a reasonable time frame. These results suggest that the proposed method can be effectively applied to address real-world location and sizing challenges for PCSs.