# A Heuristic Approach for a Real-World Electric Vehicle Routing Problem
## 4 Solution Approach
### Labeling Algorithm
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Parameter** & **Meaning** & **Value** \\ \hline \(T_{\text{ALNS}}\) & Defines the runtime (seconds) of the ALNS stage & 600 \\ (\(\alpha_{0}\), \(\beta_{0}\), \(\gamma_{0}\)) & Defines the initial penalty weights of time window, & (100.0, 100.0, 100.0) \\  & capacity, and battery capacity violations & (0.001, 0.1, 0.001) \\ (\(\alpha_{\text{min}}\), \(\beta_{\text{min}}\), \(\gamma_{\text{min}}\)) & Defines the maximal penalty weights of time window, & (0.001, 0.1, 0.001) \\ (\(\alpha_{\text{max}}\), \(\beta_{\text{max}}\), \(\gamma_{\text{max}}\)) & Defines the maximal penalty weights of time window, & (10,000.0, 1,000.0, 1000.0) \\  & capacity, and battery capacity violations & (10,000.0, 1,000.0, 0, 1000.0) \\ \(\omega\) & Adjusts the penalty weights of violations & 1.25 \\  & Defines the score if a pair of removal and insertion & 33 \\  & heuristics finds a new global best solution & 33 \\  & Defines the score if a pair of removal and insertion & 9 \\  & before and is better than the current one & 9 \\  & Defines the score if a pair of removal and insertion & \\  & heuristics finds a new non-improving solution that has not & 13 \\  & been accepted before but is accepted in current iteration & 125 \\  & Controls how quickly the weight adjustment reacts to & 0.1 \\  & changes in the effectiveness of the heuristics & [0.1 \\  & Defines the number of customers removed at each iteration & [0.1 \(|\,N\,|\,0.4\,|\,N\,|\)] \\ \(p_{\text{Shaw}}\) & Determines the degree of randomization in Shaw removal & 3 \\ \(p_{\text{worst}}\) & Determines the degree of randomization in worst removal & 3 \\  & Determines the degree of randomization in historical & 5 \\  & \multicolumn{1}{c}{} & \\ \(c\) & Defines the cooling rate in the simulated annealing & 0.99975 \\ \(w\) & Defines the initial temperature control parameter & 0.0005 \\ \(T_{\text{IP}}\) & Defines the runtime (seconds) of the IP stage & 180 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Values for the parameters of the proposed algorithm after the tuning phase. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{\(q\)} & \begin{tabular}{c} \([0.05\,|\,N\,|\,\), \\ \(0.25\,|\,N\,|\,\), \\ \(0.25\,|\,N\,|\,\), \\ \end{tabular} & \begin{tabular}{c} \([0.05\,|\,N\,|\,\), \\ \(0.31\,|\,N\,|\,\), \\ \(0.31\,|\,N\,|\,\), \\ \end{tabular} & \begin{tabular}{c} \([0.05\,|\,N\,|\,\), \\ \(0.35\,|\,N\,|\,\), \\ \(0.35\,|\,N\,|\,\), \\ \end{tabular} & \begin{tabular}{c} \([0.05\,|\,N\,|\,\), \\ \(0.4\,|\,N\,|\,\), \\ \(0.35\,|\,N\,|\,\), \\ \end{tabular} & \begin{tabular}{c} \([0.1\,|\,N\,|\,\), \\ \(0.35\,|\,N\,|\,\), \\ \(0.45\,|\,N\,|\,\), \\ \end{tabular} & \
\begin{tabular}{c} \([0.15\,|\,N\,|\,\), \\ \(0.45\,|\,N\,|\,\), \\ \(0.45\,|\,N\,|\,\), \\ \end{tabular} &
\begin{tabular}{c} \([0.15\,|\,N\,|\,\), \\ \(0.45\,|\,N\,|\,\) \\ \(0.45\,|\,N\,|\,\), \\ \end{tabular} \\ \hline Avg. Obj. & 12,690.22 & 12,632.71 & 12,528.81 & 12,378.87 & 12,430.25 & 12,462.68 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Parameter settings for \(q\). that can be used in the instance; and the columns \"Min\", \"Avg\", and \"Std\" are the minimal, average, and standard deviation, respectively, of objective function values in ten runs. The column \"Original ALNS\" lists the results of instances obtained by the original ALNS; sub-columns \"ALNS\" and \"IP\" in the column \"Proposed Algorithm\" report the results of instances obtained by the ALNS and improved by the IP, respectively; and the column \"Gap\" is the relative gap of the minimal objective function value obtained by the corresponding algorithm and proposed algorithm. From the results listed in Table 4, for all instances, the minimal and average of the objective function values (i.e., total operational cost) obtained by the original ALNS was greater than that found by our proposed algorithm; their average relative gap reached 0.82%.