# Optimizing Electric Vehicle Routing Efficiency Using K-Means Clustering and Genetic Algorithms
## 3 Methodology and Problem Definition
### Genetic Algorithm
#### 3.3.2 Fitness Function  
An essential element of genetic algorithms is the fitness function, which measures how well a solution meets the problem's objectives. Assigning fitness scores to each chromosome guides the selection process and influences the evolution of subsequent generations. Considering multiple factors, the fitness function evaluates the efficiency of a proposed route for the EV routing problem. The route is measured based on the efficiency with which it minimizes total travel distance and waiting times at charging stations and ensures that the battery capacity constraints of the electric vehicle are met. As a result of balancing these objectives, the fitness function provides the genetic algorithm with the ability to prioritize solutions that offer optimal or near-optimal routing paths for EVs, allowing it to achieve effective and practical results. The following is a detailed explanation of the fitness function and how it contributes to the optimization of EV routing:  
* Validity and exceeded distance: The evaluation begins by verifying the validity of a route, ensuring that the distance between consecutive charging stations does not exceed the EV's range. This examination evaluates the feasibility of each segment connecting two consecutive charging stations. If a route is invalid, the function calculates the excess distance beyond the EV's capacity and applies a significant penalty to the chromosome. As part of the study, we introduced a penalty factor into this calculation. Initial tests revealed that without multiplying the exceeded distance by a penalty factor, the impact on the results was negligible, and invalid chromosomes were still being selected. A penalty factor was implemented as a means of addressing this issue, ensuring that invalid routes are heavily penalized and, as a result, are less likely to be selected in future generations. The majority of invalid chromosomes were not disqualified outright. Instead, those solutions with a higher fitness among the invalid solutions are retained. In this study, a fixed penalty has been applied to the chromosome. A static penalty discourages infeasible routes while still allowing the GA to explore near-feasible alternatives. * The fitness function incorporates a calculation of the total distance of a route by summing the distances between consecutive stops along the route. It serves as a key optimization criterion, with the objective of minimizing the total distance. * Waiting time penalty: The fitness function applies a penalty for waiting times at charging stations, calculated by multiplying the waiting time at each stop by a queuing time penalty factor. This factor increases the weight of waiting time in the overall fitness score, ensuring that the genetic algorithm prioritizes routes with shorter wait times. For charging stations within the current cluster (i.e., close to the EV's current location), the penalty is based on actual waiting times, which are simulated using random values. For stations outside the current cluster, an average waiting time is applied. A fixed penalty for waiting times at charging stations is calculated by multiplying the waiting time at each stop by a static queuing time penalty factor. * Fitness calculation: The fitness score is computed as the inverse of the sum of the total distance, waiting time penalties, and exceeded distance penalties. The formulation of the fitness function is \(F=1/f\) and is detailed in Equation (1). \[f=w_{1}\sum_{k=1}^{N}d_{i}+w_{2}\sum_{k=1}^{N}q_{i}+w_{3}P,\] (1) where\(d_{i}=\) distance traveled between consecutive stops on the route;  
\(q_{i}=\) waiting time in charging station \(i\);  
\[q_{i}= \begin{cases}\textit{actual queue time}&\text{if station is in the cluster}\\ \textit{average queue time}&\text{otherwise}\end{cases} ;\]  
\(P=\) exceeded distance penalty;  
\(w_{1},w_{2},w_{3}=\) weight factors. Using empirical testing, the following weighting coefficients were determined to balance travel distance, waiting times, and route feasibility.