# Optimizing Electric Vehicle Routing Efficiency Using K-Means Clustering and Genetic Algorithms
## 2 Proposed Approach  
The study attempts to optimize EV routes in order to reduce travel distances and waiting times at charging stations while maintaining the EV's battery capacity at all times. The complexity of the problem arises from the need to dynamically navigate a network of dispersed charging stations with fluctuating queueing times. The purpose of this approach is to introduce a realistic dimension to the routing process by assuming that accurate queueing information is only available for nearby stations, thereby reflecting real-world conditions and enhancing the applicability of the model.  
To simulate real-time conditions, this study employs the K-means clustering algorithm to group charging stations based on their geographic proximity, simulating a realistic scenario in which accurate queueing times are available only for stations in close proximity. The clustering step adds a layer of practical complexity to the problem by limiting the availability of queueing information to a limited number of stations. In order to identify the optimal charging station at each decision point, a GA is used. GAs operate iteratively, generating and refining solutions that minimize travel distance and waiting times through the use of genetic operators such as parent selection, crossover, and mutation.  
The proposed GA dynamically recalculates the optimal route based on the vehicle's current position, battery capacity, and real-time queue length updates. It continuously reassesses charging station selections, adjusting the route to reflect updated queueing times and current location. By incorporating real-time data within the current cluster, the GA effectively adapts to changing conditions at each segment. Through this method, the route can be continuously adapted in real-time to changing conditions and evolving vehicle states. By integrating these methodologies, the proposed approach provides a robust and practical solution to the dynamic optimization challenges inherent in the planning of electric vehicle routes. Algorithm 1 provides an overview of the proposed approach.  
```
1 Input: Routes, charging stations, and dynamic queueing times. Output: optimized feasible route
2 Generate route and random charging stations with queueing times. (Simulate a route for the EV, including potential charging stations and queuing times) Assign each charging station with a specific route point that serves as its exit point
3 Associate each charging station with a specific route point that serves as an exit point to the associated charging station)
4 Apply K-means clustering to the charging stations Cluster charging stations by proximity to allow dynamic route adjustments based on queuing times
5 whiledo
6 Perform K-means clustering on charging stations
7 Assign each route point to the nearest centroid
8 Dynamic optimization process using a GA Reassess the route and find the best charging stations for the current EV position based on updated queueing times at charging stations, optimizing both travel distance and waiting time
9 for each starting pointdo
10 Update the route according to the EV position.
11 Update relevant data based on the new starting point
12 for each pointdo
13 Adjust EV capacity based on the current position
14 Retrieve updated connections between route and charging stations
15 Remove irrelevant stations
16 Run the GA to determine the best charging stations for the current route
17 ifcharging station from the current solution is located at the start pointthen
18 Recharge the EV
19
20 end
```  
**Algorithm 1**Proposed solution.