# Optimizing Electric Vehicle Routing Efficiency Using K-Means Clustering and Genetic Algorithms
## 1 Introduction
Genetic algorithms (GAs) have been used to solve this routing problem for two decades, including works by [21; 22; 23]. [PERSON] et al. [24] proposed a hybrid approach combining genetic algorithms and graph convolutional networks for multi-center capacitated vehicle routing, achieving a 100% success rate across various instances. Additionally, ref. [25] addressed the EVRP by developing an interaction-enhanced co-evolutionary algorithm incorporating an improved ant colony optimization method with a novel pheromone update approach. In real-world scenarios, additional challenges compound the complexities of path planning optimization, which this study addresses. First, the limited availability of chargers at many stations presents a significant obstacle to optimization, often leading to queuing delays before recharging can commence. The waiting time at charging stations is highly variable, influenced by factors such as station capacity, vehicle arrival rates, and usage patterns. Furthermore, charging speeds vary across stations due to differences in infrastructure, with some facilities offering high-speed charging while others rely on slower, conventional systems. These variations critically impact the total recharging duration and consequently affect route planning decisions [26]. Another notable challenge is the uneven geographic distribution of charging infrastructure. Urban centers typically benefit from a dense network of charging stations, whereas rural and remote areas frequently suffer from insufficient infrastructure. This disparity complicates route planning by requiring vehicles to navigate areas with limited or non-existent charging options. External factors further exacerbate these challenges. For instance, peak usage periods, such as during holidays or rush hours, can result in overcrowding at charging stations, significantly increasing wait times. Additionally, unexpected disruptions, such as maintenance events or station outages, may necessitate rerouting, thereby introducing further delays and inefficiencies [27]. In this work, we focus on a key objective: integrating real-world charging constraints into EV routing. Some studies assume that EVs are able to recharge immediately upon arrival at charging stations, but practical scenarios can be quite challenging. Depending on the infrastructure, charging speeds can vary, resulting in longer wait times. Limited charger availability frequently leads to queuing delays before vehicles are able to recharge. The contribution of this work consists of three key aspects. Firstly, the integration of K-means clustering with GA optimization represents a highly innovative approach. Second, the consideration of charging station queue lengths introduces a significant level of realism to the proposed solution, enhancing its practical applicability and effectiveness. Third, routes are optimized dynamically rather than being predetermined from start to finish, allowing greater adaptability to changing conditions. The remainder of this paper is organized as follows. Section 2 presents the proposed approach. Section 3 contains the problem definition and methods used with detailed algorithms. The optimization process of the GA parameters is presented in Section 4. The computational experiments and evaluations of the obtained results are presented in Section 5.