# Solving Optimal Electric Vehicle Charger Deployment Problem
## 5 Case Study 1: Region with Average EV Density
### Results and Discussion  
We expand the perspective of the proposed problem to taking _route minimization_ into consideration. We propose to characterize route minimization as a traveling salesperson problem (TSP). Figures 2 and 3 demonstrate the EV chargers' locations on the map of the State of Georgia. The agent (i.e., salesperson) has to visit \(n=50\) points created on a map of the State of Georgia. The map is with shorter connections as iterations progress through the course of SA. Through the two figures, our SA algorithm (which has been shown as Algorithm 1) optimizes the route covering all the chargers and coming back to the starting point. The initial state in our algorithm is a connection to a completely random neighbor.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Solver** & \(x_{1}\) & \(x_{2}\) & \(\cdots\) & \(x_{10}\) & **Objective Value** & **Number of Iterations** \\ \hline Integer Linear Programming & \(4.4409\times 10^{-16}\) & \(4.4409\times 10^{-16}\) & \(\cdots\) & \(4.4409\times 10^{-16}\) & 0 & 0 \\ \hline Pattern Search & 0 & 0 & \(\cdots\) & 0 & 0 & 204 \\ \hline Genetic Algorithm & \(-0.062657\) & \(0.042974\) & \(\cdots\) & \(-0.041941\) & 1.4801 & 3907 \\ \hline Particle Swarm & \(-7.2517\times 10^{-7}\) & \(2.5503\times 10^{-8}\) & \(\cdots\) & \(1.7757\times 10^{-6}\) & \(7.3\times 10^{-10}\) & 4320 \\ \hline Simulated Annealing & \(6.4039\times 10^{-5}\) & \(-1.99\) & \(\cdots\) & \(0.00018799\) & 3.9798 & 3008 \\ \hline Surrogate Optimization & \(0.99678\) & \(1.9937\) & \(\cdots\) & \(1.9832\) & 8.9671 & 200 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison among several representative optimization solvers.  
Figure 1: Example mapping of 20 EV chargers and 40 demand areas on the map of the State of Georgia.  
However, as the temperature is updated in each iteration, each node becomes able to connect to a closer neighbor. We notice here that our algorithm defines the temperature as the _distance_ between two stops on the map.  
Figure 3: Solving a TSP by using SA (After 300 iterations).  
Figure 2: Solving a TSP by using SA (After 1 iteration).  
```
1:\(s=s_{0}\)
2:for\(k\leq k_{\max}\)do
3:\(\mathsf{T}\longleftarrow\text{temperature}((1-(k+1)/k_{\max}))\)
4:\(s_{\text{new}}\longleftarrow\text{neighbor}(s)\)
5:if\(\mathsf{P}(\mathsf{E}(s),\mathsf{E}(s_{\text{new}}),\mathsf{T})\geq\mathcal{U}(0,1)\)then
6:\(s\longleftarrow s_{\text{new}}\)
7:endif
8:endfor
```  
**Algorithm 1** SA implemented in this work  
Algorithm 1 presents the pseudocode for the SA implementation in this simulation. The following parameters are used: \(T\) for the temperature, \(k\) for the index in the loop, \(P(\cdot)\) for the acceptance probability, \(E(\cdot)\) for the energy of a state, and \(U\) for the uniform random variable. The name of the algorithm \"annealing\" comes from the metallurgy process, through which a metal cools and freezes into a crystalline structure with minimum energy [59]. SA starts with an initial solution at a higher temperature \(T\), where the changes are accepted with a higher probability \(P\). Hence, the exploration capability of the algorithm is high, and the search space can be explored widely. As the algorithm continues to run, \(T\) decreases gradually, like the annealing process, and the acceptance probability of a non-successful move \(P\) decreases.  
Figure 4 displays how the traveling distance converges as the iteration progresses via Algorithm 1.