## 3 Problem Formalization  
The EV-STSP is a variant of the classical STSP in which the cost of traveling between locations is based on electric consumption rather than distance or travel time. The main difference between the TSP and STSP is that the TSP aims to find the shortest route that visits all nodes in a graph exactly once, while the STSP focuses on finding the shortest route that visits a subset of nodes in the graph [29]. Figure 4 provides a visual representation of  
Figure 3: Visual representation of a speed snapshot. Figure 2: Elevation map of nodes in the Madrid city graph. the problem, where a connected directed graph \(G=(V,E)\) models the road network of a city, \(V\) represents the intersections, and \(E\) represents roads or segments. The problem involves a list \(V_{0}\subset V\) of stops to visit, and the objective is to find a path that visits all the stops and returns to the starting point, minimizing the electric consumption. We also denote \(n_{0}=|V_{0}|\). \(d(i,j)\) as the electric consumption between stop \(v_{i},v_{j}\subset V_{0}\), and \(x(i,j)=\delta_{ij}\) (Kronecker's delta) to indicate whether we travel from \(v_{i}\) to \(v_{j}\). This can be stated by minimizing  
\[\sum_{i=1}^{n_{0}}\sum_{j=1}^{n_{0}}x(i,j)d(i,j) \tag{1}\]  
subject to:  
\[\sum_{j=1}^{n_{0}}x(i,j)=1,\text{ for all }i\ \in\ \{1,\ldots,n_{0}\}\text{ with }i\
eq j \tag{2}\]  
\[\sum_{i=1}^{n_{0}}x(i,j)=1,\text{ for all }j\ \in\ \{1,\ldots,n_{0}\}\text{ with }j\
eq i \tag{3}\]  
\[x(i,j)\in\ \{0,\ 1\},\text{ for all }i,j\ \in\ \{1,\ \ldots,\ n\} \tag{4}\]  
We estimate the traveling costs \(d(i,j)\), taking into account both distance and elevation as in [PERSON] et al. (2017). The forces acting against the vehicle are represented in (5), a combination of the traction force, the rolling resistance, and the aerodynamics resistance. We recall that in (5), \(a\) is the acceleration, \(m\) is the mass, \(g\) the gravity constant, \(\alpha\) the road grade angle, \(v\) the speed measured in meters per second, \(\rho\) is the air density, \(c_{rr}\) the rolling friction coefficient, \(A\) is the vehicle front surface area, and \(c_{w}\) indicates the air drag coefficient. In Equation (6) the terms \(\eta_{M}\) correspond to the energy efficiency of power conversion, \(\eta_{C}\) is the efficiency of energy regeneration, and \(P_{0}\) is the basic consumption of the vehicle. Once we compute these forces, we can compute electrical energy \(E_{el}\) drawn during the trip along a time window \([0,T]\) as \(d(i,j)=E_{el}=\int_{0}^{T}P_{el}\ dt\), where the power \(P_{el}\) can be obtained in terms of \(F_{T}\):  
\[F_{T}=a\cdot f\cdot m+m\cdot g\cdot sin(\alpha)+m\cdot g\cdot\cos(\alpha) \cdot c_{rr}+\frac{\rho\cdot A\cdot c_{w}}{2}\cdot v^{2} \tag{5}\]  
\[P_{el}= \begin{cases}\frac{F_{T}\cdot v}{\eta_{M}}+P_{0}&\text{ for }F_{T}\geq 0\\ F_{T}\cdot v\cdot\eta_{C}+P_{0}&\text{ for }F_{T}<0\end{cases}  \tag{6}\]  
In order to accurately represent the low efficiency of the vehicle under conditions such as traffic jams, we incorporate the representation of losses generated by the drive train (7). It is worth mentioning that for speeds lower than 80 km, this represents a higher loss than the specific energy consumption itself; see Figure 1 of [PERSON] et al. (2017). We also in  
Figure 4: STSP problem in a road network. corporate the energy consumption for the supply of auxiliary systems (8), as proposed also in [PERSON] et al. (2018) using a Weibull model, which is typically used to model inefficiencies in mechanical systems:  
\[E_{DT}=(3\cdot 10^{-10}v^{6}-2\cdot 10^{-7}v^{5}+5\cdot 10^{-5}v^{4}-0.0057v^{3} \ +0.358v^{2}-10.26v+\ 139.27)\cdot\mathrm{d}_{0} \tag{7}\]  
\[E_{AUX}=121.1v^{-0.794}\cdot\mathrm{d}_{0} \tag{8}\]  
where \(v\) is expressed in km/h and the total distance \(d_{0}\) in km. The final expression for calculating energy consumption in EVs is the result of adding \(E_{el},E_{DT}\), and \(E_{AUX}\) that is expressed in \(Wh\).