Integrating efficient routes with station monitoring for electric vehicles in urban environments: simulation and analysis

Integrating Efficient Routes with Station Monitoring for Electric Vehicles in Urban Environments: Simulation and Analysis David Ragel-D´ıaz-Jara1(B),Jos´e-Luis Guisado-Lizar1,2 , Fernando Diaz-del-Rio1,2,Mar´ıa-Jos´eMor´on-Fern´andez1,2, Daniel Cagigas-Mu˜niz1,2, Daniel Cascado-Caballero1,2 , Gabriel Jim´enez-Moreno1,2, and Elena Cerezuela-Escudero1,2 1Department of Computer Architecture and Technology, Universidad de Sevilla, Avenida Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] 2Research Institute of Computer Engineering (I3US), Universidad de Sevilla, Avenida Reina Mercedes s/n, 41012 Sevilla, Spain Abstract. The electrification of road transportation requires the development of an extensive infrastructure of public charging stations (CSs). In order to avoid them contributing to increased traffic congestion and air pollution in a city, it is very important to optimize their deployment. To tackle this challenge, we present microscopic traffic simulations with a hybrid cellular automata and agent-based model to study different strategies to route electric vehicles (EVs) to CSs, when their battery level is low. EVs and CSs are modeled as agents with capability to demonstrate complex behaviors. Our models take into account the complex nature of traffic and decisions about routes and their predicted behavior. We show that a synthetic city is very useful for investigating the routing behavior and traffic patterns. We have found that a smart routing strategy can contribute to balancing the distribution of EVs among the different CSs in a distributed network, which is the CS layout that produces less traffic congestion. Contrary to our initial expectations, ensuring a balanced distribution throughout the city did not necessarily result in an increase in overall productivity. This observation led to a deeper exploration of the nuances of urban transport dynamics. Furthermore, our study emphasizes the superiority of time-based routing over its distance-based counterpart and highlights the inherent limitations of transportation within acity. Keywords: Electric Vehicle ·Charging ·Infrastructure Deployment · Modeling ·Simulation This work is part of the project SANEVEC TED2021-130825B-I00, funded by the Ministerio de Ciencia e Innovaci´on (MCIN), Agencia Estatal de Investigaci´on (AEI) of Spain, MCIN/AEI/10.13039/501100011033, and by the European Union NextGenerationEU/PRTR. Integrating Efficient Routes with Station Monitoring for EVs 167 1 Introduction The transportation sector is responsible for a substantial share of the total carbon dioxide CO2equivalents released into the atmosphere. Such greenhouse gas emissions are the cause behind the current global climate crisis, posing a formidable challenge to humanity. Within transportation, road vehicles, which play a major role in our daily mobility, are a significant contributors to this phenomenon. In response to this pressing issue, a shift toward electric vehicles (EVs) is being carried out at a global level. This electrification of road transportation needs the development of an extensive public charging infrastructure. Forecasts for the year 2030 indicate a significant surge in the demand for public charging stations (CSs), far surpassing the current figures. For example, a study conducted by the International Energy Agency indicates that electric vehicles are expected to constitute approximately 55% of all transportation modalities in Europe by 2030 in the existing policies scenario, taking into account different types of vehicles [10]. It is important to optimize the deployment of CSs in a city to avoid them from contributing to increased traffic congestion. In this context, the SANEVEC research project (“A simulation approach to determine the deployment of an urban network of electric vehicle charging stations for environmental and social benefits”), https://grupo.us.es/sanevec/en, funded by the Ministry of Science and Innovation of Spain and by the European Union under the NextGenerationEU program, aims to use simulations and artificial intelligence techniques in order to research, design and implement a computer simulation model to predict the effects of the layout of an urban network of EV CSs on the following aspects of a real city: traffic congestion, air-quality, carbon footprint, and electric grid usage. Some of the starting hypotheses of the SANEVEC project were established and studied in [6]. In that work, a hybrid microscopic simulation model, based on cellular automata and agent-based modeling, was introduced, which can simulate the behavior of individual vehicles, including EVs and internal combustion engine vehicles (ICEVs), and also the operation of CSs. In that model, each EV is modeled as an agent incorporating a complex behavior involving decisions about factors such as the specific destination of each vehicle, the route to follow, how to navigate there taking into account the local traffic state, when to drive to a CS to recharge the battery, and what station to drive to. A simulator called SIMTRAVEL [7] was also presented and used to study the effects on traffic of different dispositions of CSs in a synthetic city. It was found that the distribution of small or medium-size CSs distributed throughout the city is better than a large central station (or a few of them) in terms of their effect on traffic congestion. However, a drawback was also found: in the distributed CS scenario, there is an uneven distribution of EVs across various stations, leading to saturation at some stations while others retain available chargers. Accordingly, as vehicle density scales, the average queuing time for EVs at a CS, awaiting an available charger, exceeds that observed at a singular, larger station. 168 D. Ragel-D´ıaz-Jara et al. In this work, we study different routing strategies to route EVs to CSs when they need to recharge their batteries, using a simulator called PYSIMTRAVEL3 [15], which is based on the previous SIMTRAVEL simulator. Possible strategies could range from deploying informational signs indicating the occupancy of each CS to instituting an intelligent traffic management system that communicates directly with EVs or their users. The objective is to find strategies that can balance the distribution of EVs across different small or medium-size CSs scattered across the city, so that the benefit of distributed CSs (minimizing traffic congestion in the city) can be obtained without the drawback found in the previous study (uneven distribution of EVs across CSs). The remainder of the paper is organized as follows. Section 2presents related work. Section 3describes the methodology. The results are presented in Sect. 4. Finally, Sect. 5presents the conclusions and future research directions. 2 Related Works In recent years, many research works have been devoted to this topic due to its importance. For instance, in [5], an optimal allocation problem for charging stations in freight transport is formulated as an NP-hard optimization problem (specifically a Location Set Covering Problem), and tackled using an open-source optimization Python library (spopt). They used a dataset of GPS tracking data collected from a fleet of 61 freight vehicles operating during six months. In the work [9], a multi-period bi-objective optimization model is presented to provide optimal solutions for the placement of charging stations. In [3], the optimal placement and sizing of fast and slow CSs is studied as an optimization problem, in which the cost is determined by CS placement parameters (installation, operation and travel time cost) and penalties for violating power grid constraints. They employed a hybrid evolutionary algorithm combining a chicken swarm optimization and a teaching-learning-based optimization algorithm. In the work [13], GPS-enabled trajectory data were used for the location of CSs, with the objective of minimizing the CO2 emissions, employing a genetic algorithm. Nonetheless a significant portion of these studies overlook the impact of charging station locations on road congestion. Many also base their analyses on aggregated trajectories of conventional fuel vehicles, neglecting changes that electric vehicles might introduce in driving behaviors. Our approach is to tackle this challenge by directly simulating traffic using microscopic models. These models individually represent each vehicle and forecast its behavior in response to surrounding vehicular dynamics. Two main types of microscopic models have been used for traffic: cellular automata (CA) and agent-based models (ABM). CA are mathematical constructs characterized by their discrete spatial and temporal nature, local interactions, and synchronous parallel dynamic evolution [11]. Their application in modeling vehicle traffic can be traced back to the efforts of K. Nagel and M. Schreckenberg [14], followed by B. Chopard et al. [4], X.G. Li [12], and Y. Zheng [21], among others. In terms of electric vehicle considerations, Integrating Efficient Routes with Station Monitoring for EVs 169 Fig. 1. The simulation model is based on a cellular automaton that represents city roads. EVs are agents that occupy one cell, and in the next time step can move to another nearby cell. CSs are also agents located in a road cell. Xiang et al. [19] utilized a CA model to evaluate electric demand at a charging station for different traffic flows. However, the scope of their model was somewhat restrictive, including only one road, one intersection, and one charging station. Consequently, they did not examine the impact of the charging station network on traffic patterns. On the other hand, ABMs simulate the behaviors and interplays of individual components termed agents. Notable examples of the application of ABM in traffic studies include the work of Chen [1] and Waraich [17]. The study by Viswanathan et al. [16] employed an ABM model to explore the optimal placement of charging stations. However, in this work, vehicles followed fixed routes (based on daily traffic data) from a starting point to a destination, compromising its realism. The study by Zhai et al. [20] might be the closest in methodology to our work. They used a hybrid CA-ABM model, but it was not a microscopic model. Each cell was defined as a stretch of a 1 km road that holds multiple cars. Such a coarsegrained model cannot capture intricate traffic dynamics observed in actual urban settings and emergent properties of traffic as a complex system, such as traffic jams, and how they affect traffic density and charging demand. 3 Methodology Our study employs a cellular automata and agent-based microscopic hybrid model, which was previously introduced in [6]. An implementation of the model has been carried out on the PYSIMTRAVEL3 simulator [15], which is an evolutionized version of the previous SIMTRAVEL simulator [7]. The structure of the simulation model is depicted graphically in Fig. 1. Modelling of the city is based on a cellular automaton. The city is a square, synthetic, and regular 2D grid of interconnected cells representing streets and vehicles moving through them, useful for investigating 170 D. Ragel-D´ıaz-Jara et al. routing behavior and traffic patterns that occur in a real city. Therefore, the city roads are divided into square cells with a width of 5 m. The cell state can be either occupied by a vehicle or non-occupied. In this case, periodic boundary conditions are used, so the final structure adopts a 2D toroidal shape, but for future developments, the actual map of a city can be mapped by raster processing onto the 2D mesh proposed above or onto a 1D vector with components capable of storing spatial connection information to emulate the topology of the real city. A representation of the synthetic city is shown in Fig. 2. Fig. 2. Road map of the synthetic city showing the location of the 9 CSs. The city includes single lane streets, avenues with two lanes on each direction, and roundabouts with two lanes. Properties of city cells are inspired by the works of Chopard et al. [2,4]. The city model is built by joining together different tiles (groups of cells), forming different structures. There are different elements in a tile: – Streets: roads formed by linear configurations of cells in a particular direction, establishing one lane. They can be oriented toward the north, south, east, or west. – Avenues: bidirectional roads with two lanes of cells for each direction. Vehicle speed in avenues is higher than in streets. – Intersections: The junctions formed at the convergence of two streets. – Roundabouts: Established at the nexus of two avenues, they incorporate a central rotational segment of varying radius, with multiple input and output points. We assume that the energy usage of an EV is directly proportional to speed, following the study by Wu et al. [18], which identified an approximately linear correlation between an EV’s power consumption and speed for velocities below 50 km/h. With this premise, on typical streets, EVs move forward by 1 cell when Integrating Efficient Routes with Station Monitoring for EVs 171 the next cell is unoccupied, depleting 1 unit of their battery energy. On avenues, they advance by 2 cells per time step, consuming 2 energy units. A snapshot of a typical simulation is shown in Fig. 3. The color codes are shown in Table 1. Fig. 3. Snapshot of a simulation of the city with a density of 10% of EVs Vehicles are modeled as agents with the capability to demonstrate various complex behaviors, including making decisions about routes, recognizing when to visit a CS based on battery levels, and choosing a specific CS. At each step of the simulation, each EV (and thus each agent associated with an EV) evaluates its environment by obtaining information from the 2D matrix representing the current state of the city (own state and location, location of other EVs, remaining energy, route to the assigned target) and produces its next state and next location, which are stored in the 2D matrix representing the next state of the city. Each vehicle occupies a cell and navigates the city governed by a finite state machine. In this work, all vehicles are considered electric vehicles (EVs). A second type of agents are CSs. The objective of this work centers on tackling challenges associated with the positioning of stations, the dynamics of EV movements, and the charging durations. Therefore, we consider underground CSs, and avoid modeling a queue of vehicles building up on the road outside a station. In this way, CSs are conceptualized as distinct roadway cells that neither consume tangible physical space nor allow vehicles within them to be seen Table 1. Meaning of color codes for the simulation snapshot shown in Fig. 3 Green A one-way street Blue A street with a bifurcation Yellow Charging Station (CS) White Acar Red Safety distance 172 D. Ragel-D´ıaz-Jara et al. by external traffic. This design assumes endless capacity for vehicles awaiting or undergoing charging. The time it takes vehicles to recharge within a station depends on the power of the chargers. When every charger at a station is in use, vehicles wait in a queue inside a subterranean facility located under the CS. At the start of the simulation, each vehicle is assigned a sequence of random cells as targets. In order to ensure repeatability, a single seed for random numbers is taken for the whole program. More details of the cellular automata and agent-based microscopic hybrid model can be found in [6]. In that work, it was found that a distributed layout of CSs is better than a single large central station in terms of its effect on traffic patterns, because traffic is more fluid. However, a drawback was also found: the distribution of EVs among the different CSs in a distributed layout was not well balanced, so that some stations become saturated, while other ones still have free chargers. As a consequence, it was also found that the time spent by EVs queuing in the CS while waiting for a free charger is higher than for a single station. Therefore, it is important to use smarter routing strategies to balance the distribution of EVs among the different CSs in the distributed network. In the work cited, each EV simply randomly chose the CS to which it would drive when the battery is low. In the present work, we tackle this problem by studying the effect of different EV routing strategies to CSs. We compare the occupancy of CSs to assess if their usage is well-balanced, i.e., whether the occupancy levels of different distributed CSs (total number of vehicles in the queue) are similar. We also evaluate the effectiveness of the strategies using additional metrics, including productivity. In this context, productivity is defined as the average number of electric vehicles that reach their destination per step in a simulation. This is calculated by dividing the total number of EVs that arrive at their destination by the total number of simulated steps. We consider the following routing strategies: 1. “Distance”: Distance to the CS throughout the shorter path. 2. “Time”: Time needed to arrive at the station and obtain a charger. We do not consider the strategy used in [6] of randomly choosing the CS to which to drive, since it is obviously worse than the strategies considered in this work. The foundation of routing strategies is an A* algorithm [8] that uses heuristics to decide between the various branches it explores. In the Time-based algorithm, the average occupancy of the cells along the route is utilized as a primary determinant. Instead of relying on maximum road speeds, which do not account for dynamic traffic conditions, the average cell occupancy is used. A higher occupancy implies a slower speed, and conversely, a lower occupancy suggests a faster speed. After trying various heuristics, we opted to use the following one. To ensure that this average occupancy remains dynamic, an exponential moving average (EMA) has been adopted. The EMA has a weight wthat modulates the consideration of past data; thus, it is called here “Past Cell Occupancy Weight” (PCOW) Integrating Efficient Routes with Station Monitoring for EVs 173 or Exponential Weight. In our simulations, two forgetting PCOW factors have been evaluated: 0.5 (which emphasizes the recent information) and 0.95 (which gives more significance to the historical data). The aggregate occupancy of a route leads to good productivity. The heuristic occupancy can be represented by the equation: On=w×On−1+(1−w)×Cn(1) where: On: Heuristic Occupancy at time n On−1: Heuristic Occupancy at time n−1 Cn: Current Occupancy at time n w: weight Here, the current occupancy is defined as 0 if there is no vehicle, 1 if there is a vehicle, and 1/speed if a vehicle has passed at time n. We also consider adding the time it would take to be served at the CS. Therefore, it was assumed that a percentage of vehicles use a real-time information system and take that information into account to choose, among the closest CSs, the one that offers the shortest combined travel and waiting time. The term “CS queue query” has been employed here for this percentage. This suggests that they have the ability to utilize an Internet of Things (IoT) application, mobile app, or web service, thus enabling monitoring of the occupancy of nearby CSs. The possible states of a vehicle in each time step are described in Table 2. Initially, a sufficient number of vehicles are introduced into the CSs to ensure that the system is in energy balance. That is, the energy received by cars at the chargers should be the same as that of cars still in circulation. In this way, transient states are minimized. Obviously, if a vehicle initially does not have enough energy to reach the nearest CS, it is introduced forcibly. We perform comprehensive studies, varying parameter configurations, aiming to compare the occupancy of charging stations to assess if their usage is well balanced, and to evaluate the productivity of the simulations. Therefore, for each simulation, we generate two types of partial results: Table 2. Description of vehicle states. State Description Driving The vehicle drives without any issues towards its destination Waiting The vehicle had to stop due to non-fluid traffic Destination The vehicle reaches its destination and remains there for a unit of time ToCharging The vehicle is heading to the CS Queuing The vehicle enters the CS and queues, waiting for an available plug Charging The vehicle is at the CS, charging 174 D. Ragel-D´ıaz-Jara et al. – Standard deviation of the queues at the CSs, used to determine if the system is well-balanced (Fig. 5). – Productivity, which serves as an indicator of the overall performance of the city. 4 Results We performed tests using a city with six avenues, and with a distributed CS layout composed of 9 evenly distributed stations. Five parameters have been considered in the simulation, and their values can be seen in Table 3. We carried out experiments with two routing strategies: Distance and Time. Traffic density is the percentage of occupied road cells (that is, containing a vehicle). The “CS Queue Query” and PCOW were previously discussed in the methodology section. The last two parameters only make sense if the strategy is based on Time. The “Number of chargers per charging station” leads to scenarios where available energy ranges from scarce to abundant. For each parameter configuration, five simulations were conducted with different random seeds. In total, there are 690 simulations (5 ×3×2×11 ×2+ 5×3×2). For each experiment, we generated two types of results: standard deviation of the queues and productivity, of which we introduce some examples below. We begin by first showcasing a few example graphs from the simulations, followed by aggregate data charts and parameter cross-reference graphs. The first set of graphs depicts the state of the vehicles throughout the simulation execution. Some basic principles that have been followed along the simulations are the following: 1) Ideally, all EVs should be in the “driving” state, but there should be a constant percentage of EVs in “charging”. 2) There are two elements that disrupt this ideal scenario: On the one hand, if there is an energy deficit, we will see the “queuing” segment increase; on the other hand, if traffic becomes congested, the “waiting” segment will grow. 3) When a car reaches its destination, blue dots (labeled “Destination”) appear at the bottom. These are hard to spot because of their low frequency, but they are crucial for measuring the simulation’s productivity. The evolution of the number of vehicles in each possible state throughout a simulation under three different scenarios (a stable situation, an energy deficit, Table 3. Simulation Parameters Parameter Values Strategy Distance, Time Number of chargers per charging station 1, 5, 10 Traffic density (percentage of occupied road cells) 5%, 10% CS Queue Query 0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1 PCOW 0.5, 0.95 Integrating Efficient Routes with Station Monitoring for EVs 181 13. Liu, Q., Liu, J., Le, W., Guo, Z., He, Z.: Data-driven intelligent location of public charging stations for electric vehicles. J. Cleaner Prod. 232, 531–541 (2019). https://doi.org/10.1016/j.jclepro.2019.05.388 14. Nagel, K., Schreckenberg, M.: A cellular automaton model for freeway traffic. J. Phys. I France 2, 2221–2229 (1992). https://doi.org/10.1051/jp1:1992277 15. Ragel-D´ıaz-Jara, D., et al.: Pysimtravel3: urban traffic simulator for charging stations, electric and combustion vehicles, based on a hybrid cellular automata and agent-based model (2023). https://github.com/sanevec/pysimtravel3 16. Viswanathan, V., Zehe, D., Ivanchev, J., Pelzer, D., Knoll, A., Aydt, H.: Simulation-assisted exploration of charging infrastructure requirements for electric vehicles in urban environments. J. Comput. Sci. 12, 1–10 (2016). https://doi. org/10.1016/j.jocs.2015.10.012 17. Waraich, R.A., Galus, M.D., Dobler, C., Balmer, M., Andersson, G., Axhausen, K.W.: Plug-in hybrid electric vehicles and smart grids: investigations based on a microsimulation. Transp. Res. Part C: Emerg. Technol. 28, 74–86 (2013). https:// doi.org/10.1016/j.trc.2012.10.011 18. Wu, X., Freese, D., Cabrera, A., Kitch, W.A.: Electric vehicles’ energy consumption measurement and estimation. Transp. Res. Part D: Transp. Environ. 34, 52–67 (2015). https://doi.org/10.1016/j.trd.2014.10.007 19. Xiang, Y., Liu, Z., Liu, J., Liu, Y., Gu, C.: Integrated traffic-power simulation framework for electric vehicle charging stations based on cellular automaton. J. Mod. Power Syst. Clean Energy 6, 816–820 (2018). https://doi.org/10.1007/ s40565-018-0379-3 20. Zhai, Z., Su, S., Liu, R., Yang, C., Liu, C.: Agent-cellular automata model for the dynamic fluctuation of EV traffic and charging demands based on machine learning algorithm. Neural Comput. Appl. 31, 4639–4652 (2019). https://doi.org/10.1007/ s00521-018-3841-2 21. Zheng, Y.L., Zhai, R.P., Ma, S.Q.: Survey of cellular automata model of traffic flow. J. Highway Transp. Res. Dev. 23, 110–115 (2006)