A Heuristic Algorithm for Deploying Electric Taxi Charging Stations to Enhance Service Quality

With the growing maturity of electric vehicles technology and the increase in environmental awareness, electric vehicles have emerged as a feasible way to reduce carbon emissions due to transportation. In response, numerous cities have adopted electric vehicles into taxi and bus fleets to increase their use. As the use of electric taxis increases, the strategic deployment of charging stations becomes crucial to ensuring taxi operations. This study aims to optimize the deployment of electric taxi charging stations, with a focus on improving service quality. A heuristic algorithm, Improved K-means iterated with Queuing Theory (IKQT), is proposed. To validate the algorithm, over 11,000 GPS tracking trajectory data from Shanghai Qiangsheng taxis in April 2018 were analyzed. The results of the study demonstrate that the IKQT algorithm can significantly increase the utilization rate of charging stations, enabling them to serve more electric taxis during peak hours and thereby improving overall service quality. Specifically, the total waiting time for all charging services was reduced by approximately 6%, while the total number of unserved taxis across all charging stations decreased by roughly 19%. These improvements underscore the novelty and practical value of the IKQT in the deployment of electric taxi charging stations.