Abstract
The Irish transportation sector currently accounts for more than 30% of the energy related CO2 emissions of the country. Therefore, in order to reach the sustainable goals, the Irish government is working on multiple incentives to promote Electric Vehicles (EV) and infrastructure to decarbonize the sector, e.g., free domestic charging points, tool reductions, and the implementation of electric Buses (eBuses) in the medium to long term. In particular, eBuses operate with rechargeable batteries with a capacity to store approximately 300 kWh (and up to 600 kWh), equivalent to around 29.9 L of diesel, while reaching approx. 200 km. In order to ensure a proper transition from regular diesel buses to eBuses, charging times must be coordinated to ensure each bus has adequate energy to complete their operational route. In this work, we present a framework for an efficient management of renewable energies to charge a fleet of eBuses without perturbing the quality of service. Our framework starts by building a deep learning model for wind power forecasting to predict clean energy time windows, i.e., periods of time when the production of clean energy exceeds the demand of the country. Then, the optimization phase schedules charging events to reduce the use of non-clean energy to recharge eBuses while passengers are embarking or disembarking. The proposed framework is capable of overcoming the unstable and chaotic nature of wind power generation to operate the fleet without perturbing the quality of service. As expected, the size of the batteries does have a positive impact on the percentage of clean energy required to operate large fleets of eBuses. Methods developed in this paper help to mitigate potentially inaccuracies derived the prediction models. Our extensive empirical validation with real instances from Ireland suggests that our solutions can significantly reduce non-clean energy consumed on large datasets.
You have full access to this open access chapter, Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
The Vehicle Routing Problem (VRP) is a well-known combinatorial optimization problem with applications ranging from logistics to planning and scheduling. This problem involves the creation of optimal routes (e.g., minimizing the traveled distance or the required time to complete certain tasks). These routes might represent supply chains where vehicles deliver goods from a set of depots to customers (Laporte & Nobert, 1987). Research into the usage of EVs has spawned a variation of the VRP called the Electric Vehicle Routing Problem (EVRP). EVRP differs from traditional VRPs as the range of EVs is considerably shorter compared to traditional combustion vehicles. As pointed out above, the range of EVs varies depending on multiple factors, e.g., battery size, average speed, and ambient temperature. Furthermore, some form of charging must occur to complete the daily operations of the vehicles (in particular, for variations of the problem with pick-ups and deliveries (Olgun et al., 2021)). The EVRP focus mainly on minimizing the total cost of routing strategies (Lin et al., 2016) and the placement of charging stations to minimize or even negate detours needed to charge (Funke et al., 2015, 2016).
The Vehicle Routing Problem with Time Windows (VRPTW) is a popular variation of the traditional VRP, where vehicles must visit a set of customers within certain predefined time periods (e.g., outlined by the customers or local governments). This adds additional complexity to VRPs as a vehicle arriving early to a destination might be required to wait, and a vehicle arriving late may invalidate the solution (Desrochers et al., 1992). This has also spawned additional variations such as Time Window Assignment Vehicle Routing Problem (TWAVRP) focusing on assigning time windows to deliveries before the demand is known (Spliet & Gabor, 2015).
Variations of the VRPTW for EVs have also received significant attention recently. The Electric Vehicle Routing Problem with Time Windows (EVRPTW) aims at creating optimal routes as the traditional VRPTW, however the additional constraints of battery capacity and location on recharging stations are also taken into consideration (Schneider et al., 2014). Another line of work considers the charging location problem of EVs. One notable work in this area focuses on the transition to eBuses and the authors proposed a Mixed Integer Programming (MIP) model to identify suitable locations of fast charging units to maintain the current level of service, i.e., same routes and similar timetables (Arbelaez & Climent, 2020).
With the increase in research around EV there has also been a rising interest in using renewable energy to charge EVs. (Zhang et al., 2013) proposed the use of locally generated renewable energy to supplement the requirements of acquiring energy from the national grid. However, when creating a bus operation schedule information such as available renewable energy is needed ahead of time. Predict and Optimize (Elmachtoub & Grigas, 2021) is a relatively new paradigm which focuses on combining predictions and combinatorial optimization. The paradigm involves two stages: the first one involves training a model (e.g., a supervised learning or a time series model) to predict critical variables of the optimization problem. The second stage then uses these predicted values to solve an optimization problem e.g., weights in the weighted knapsack problem (Mandi et al., 2020) or scheduling of combinatorial problems with uncertain duration times (Duque et al., 2018). In this paper, we also use this two-stage paradigm. We start with a time series model to estimate surpluses of wind power in the national grid and then optimize the scheduling of charging events based on the predictions. A time series is a collection of consecutive measurements of powers in kWh recorded in equal intervals (15 min in this paper). The accuracy of the time series methods varies considerably with different forecasting horizons (number of future observations). In this paper we focus on medium-term horizons, i.e., the forecasting period ranges from 6 h to 1 day ahead. A 6, 12, 18, and 24 h ahead forecasting horizon will predict respectively a total of 24 (4 per hour × 6), 48, 72, and 96 observations. (Shobana Devi et al., 2021) outlines alternative models for other forecasting horizons, i.e., very short-range (a few seconds to 30 min ahead), short-range (30 min–6 h ahead), and long-term range forecasting (1 day to a week ahead).
Long Short-Term Memory (LSTM) is a popular deep learning architecture proven to be effective at energy forecasting (Lim & Zohren, 2021). Such models can be trained to make multi-step ahead predictions, where a variable n controls the number of future time-step predictions (Sangiorgio & Dercole, 2020).
2 Predict then Optimize Framework
The predict and optimize framework aims at guiding the optimization solver to tackle complex problems. In particular, we use a LSTM model to predict how much excess wind energy is available at any time period. This information is then passed to a MIP solver to identify suitable schedules to operate the fleet of eBuses while satisfying certain properties of the transportation system (Arbelaez & Climent, 2020).
2.1 Prediction Models
As pointed out above, we create four LSTM models for predicting excess wind energy 6, 12, 18, and 24 h in advance. Furthermore, we populate our models with historical data from the Irish nation grid in 15 min intervals and populate the training dataset with data from August 2013 to October 2021, and test dataset with data from November 2021 to January 2022 (demand and wind generated power dataset is available at http://smartgriddashboard.eirgrid.com/). The months of November 2021 to January 2022 where selected due to the increased about of wind power generated in winter months, therefore the ability of the LSTM model to predict excess in clean energy can be more accurately determined. Furthermore, we reserve 33% of the training dataset as a validation dataset. The demand and wind generated power datasets are aggregated into one dataset which represents the excess of clean energy at any time. However, at the moment Ireland’s national grid does not supply enough wind power to cover the demand. Therefore, we scaled the amount of wind power by a 1.4 factor to simulate a transition to eBuses with enough power to satisfy the current demand. This is in line with the estimations for Ireland’s growth in wind generated power by 2026/2027 (Department of Communications, Climate Action & Environment, 2019, p. 40). Therefore, we use a univariate dataset consisting of values between −5064.2 (representing a clean energy deficit of 5064.2) and 1005.8 (representing a clean energy surplus of 1005.8). The LSTM models are then trained on this data with a loss function of Root Mean Squared Error (RMSE) and using Adam optimizer (Kingma & Ba, 2014). We make the data stationary by applying a difference operation on each subsequent value and normalized to a range between −1 and 1 with minMax normalization.
Table 1 shows the Mean Absolute Percentage Error (MAPE) and RMSE of the LSTM models based on the results of the test dataset. We remark that these results are consistent with the literature, i.e., shorter prediction horizons produce more accurate results (Shobana Devi et al., 2021). This increase in error as the horizons become larger can be explained by the fact wind power is harder to predict due to the unstable and chaotic nature of wind power derived from multiple factors, e.g., wind speed, air density, wind turbines, etc.
2.2 Optimization Model
We extended the work of (Arbelaez & Climent, 2020) with additional constraints to determine whether the charge times of eBuses overlaps with times where there is an excess of clean energy. Furthermore, our solver aims at reducing CO2 emissions, and therefore, we minimize the total amount of non-clean energy used to operate the system. In our simulations, we assume that the eBuses travel at a constant speed of 35 km/h and a charge rate of 10 kWh per minute.
We also assume that the discharge rate of the batteries is 1 kWh per km.
We test multiple battery capacities for the bus fleets, these include 120, 180, and 240 kWh. We assert that the battery capacity must not fall below 12 kWh and only allow buses to charge up to 80% of their maximum capacity in a single charge. We also simulate a degree of overnight charging before the buses operational day begins. To represent this, we assume the buses start with a capacity of 30 kWh regardless of the selected battery capacity. It is assumed the placement of charging stations is a separate problem to the one covered in this paper (Loaiza Quintana et al., 2022), to this end the location of charging stations is passed as an argument to the optimization code. For this paper, we assume that charging stations are placed every × km on each bus route. Alternative placement methods involving cost functions will be explored in future works.
We evaluate our framework on three Irish cities, i.e., Cork, Limerick, and Galway. The bus system in Cork includes 11 bus routes operated with 81 buses and 578 stations; the network in Galway includes 6 bus routes operated with 24 buses and 288 stations; and the network in Limerick includes 6 bus routes operated with 23 buses and 253 routes (GPS location of bus stations and timetables are available at https://www.buseireann.ie). Furthermore, we assume two charging infrastructures. The first one, Inf-A, assumes that there is a charging unit every 12 km which results in 53 charging stations for Cork, 13 for Limerick, and 19 for Galway. The second one, Inf-B assumes that there is charging unit every 15 km which results in 43 charging stations for Cork, 12 for Limerick, and 11 for Galway.
We also assert a maximum deviation time for the newly created schedule, meaning the arrival times in the new schedules can be at most Δ different from the original schedule where Δ is an amount of time in minutes. For this paper we explore two values for Δ, 5 and 10 min.
3 Experiments and Results
Prediction models are used to predict wind energy excess for the two-week period of 14th to the 27th of February 2022. The month of February is chosen as it features a high amount of wind generated power, as a result there will be enough excess power to evaluate the performance of our framework. For the optimization model we assume three different scenarios regarding clean energy information. The first |Γ|=0 assumes the optimization model has no knowledge of clean energy information. The second uses the information generated by the prediction models previously outlined. Finally, we examine the ideal scenario, where we have perfect predictions (i.e., the actual historical values for excess wind energy).
Figure 1 shows the amount of modified wind energy vs the demand of the electrical grid. Of note there are a number of days where the amount of modified wind energy does not exceed system demand at any point (i.e., the 17th, 18th, 21st, and 24th). As a result, experiments which use wind data from these days will produce poor results as there is no clean energy available. On the contrary, the 26th features a very high amount of wind energy throughout the day, as a result any charges which take place on this day would use clean energy. For the empirical analysis of our experiments, we removed the results from the previously mentioned 5 days as they would represent outliers in the amount of wind energy available. Such outliers would not provide any insights into the performance of our framework, as the framework aims to reduce the total amount of non-clean energy used and therefore requires clean energy to operate.
Table 2 shows the results for the experiments using Inf-A and a deviation time of five minutes. As expected, when using predictions from our prediction models there is a notable decrease in the amount of non-clean energy used when compared to a naïve scenario with no knowledge of clean energy information. Therefore, while our LSTM models are not fully accurate there is a notable benefit in the integration of the learning component in our schedules. Also of note is that increasing battery capacity in the ideal scenario may not reduce the amount of non-clean energy consumed. This is because all of the available clean energy is already being consumed when capacity is set to 120. This is the case on the smaller datasets of Limerick and Galway; however, we see for the Cork dataset that increasing the capacity does reduce the non-clean energy consumed. Sometimes when using predictions from our LSTM models larger battery capacities consume more non-clean energy compared to smaller capacities, we attribute this to mispredictions in our LSTM models. Larger battery capacities can consume more energy in a single charge. As a result, any false positives in our prediction model (i.e., we predict there is a clean energy excess when there is actual a deficit) could result in the scheduling of a charge using non-clean energy.
Figure 2 shows a comparison between the average across all capacities for each scenario and each city. Here we see that the average difference between the three scenarios heavily demands on the dataset used. For example, smaller datasets like Limerick show minor differences between the three scenarios. However, the larger Cork dataset shows more significant difference. We attribute this to the higher energy requirements of the Cork dataset in addition to the longer operational times of the bus system. The Cork bus system begins operation earlier then both the Galway and Limerick datasets, and finishes operational routes later, as a result the Cork data-set is able to make use of any excess clean energy in the early morning and late night.
Experiments conducted using Δ = 10 min found that the solutions in the ideal scenario only improve by 0.685% on average. It should also be noted that experiments using Δ = 10 min took 27.39% longer to complete compared to Δ = 5 min. Results for experiments using Inf-B showed an increase in the amount of non-clean energy used on average. However, it should be noted, for the Cork dataset and capacity 240 solutions where only 0.93% worse compared to experiments using Inf-A. As the reader recalls Inf-A for the Cork dataset features 53 charging stations, while Inf-B has 43. This suggests the relationship between number of charging stations present and solution quality are not directly proportional.
4 Conclusions and Further Research
In this work, we use a deep learning model for wind power forecasting to estimate the availability of clean energy in a day, we then integrate the output into an optimization model to schedule charging events. Experimentation results with actual data from the Irish national grid and a major bus operator in Ireland suggest our models can make a notable reduction in the non-clean energy consumed compared to a naïve optimizer. While our predictions do not generate solutions as high quality as the ideal scenario, a significant reduction in non-clean energy consumed can be observed on larger datasets. Therefore, the results of the evaluation confirm the high-quality performance of the proposed approach. In the future, we plan to extend our framework with Bus-to-grid technology to help the national grid by returning energy when needed (i.e., during peak hours). We also plan to investigate the performance of our proposed framework with the charging infrastructure placement problem.
References
Arbelaez, A., & Climent, L. (2020). Transition to ebuses with minimal timetable disruptions. In Thirteenth Annual Symposium on Combinatorial Search, Vienna, Austria, May 26–28.
Department of Communications, Climate Action & Environment. (2019). National Climate & Energy Plan 2021–2030. Retrieved July 19, 2022, from https://assets.gov.ie/94442/f3e50986-9fde-4d34-aa35-319af3bfac0c.pdf
Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 342–354.
Duque, R., Arbelaez, A., & Díaz, J. F. (2018). Online over time processing of combinatorial problems. Constraints an International Journal, 23(3), 310–334.
Elmachtoub, A. N., & Grigas, P. (2021). Smart “predict, then optimize.” Management Science, 68(1), 9–26.
Funke, S., Nusser, A., & Storandt, S. (2016). Placement of loading stations for electric vehicles: Allowing small detours. In Twenty-Sixth International Conference on Automated Planning and Scheduling, London, UK, June 12–17 (Vol. 26, No. 1, pp. 131–139).
Funke, S., Nusser, A., & Storandt, S. (2015). Placement of loading stations for electric vehicles: No detours necessary! Journal of Artificial Intelligence Research, 53, 633–658.
Kingma, D. P., Ba, J. (2014) Adam: A method for stochastic optimization. arXiv preprint arXiv:14126980
Laporte, G., & Nobert, Y. (1987). Exact algorithms for the vehicle routing problem. In: S. Martello, G. Laporte, M. Minoux & C. Ribeiro (Eds.), North-Holland Mathematics Studies (Vol. 132, pp. 147–184).
Lim, B., & Zohren, S. (2021). Time-series forecasting with deep learning: A survey. Philosophical Transactions of the Royal Society A, 379(2194).
Lin, J., Zhou, W., & Wolfson, O. (2016). Electric vehicle routing problem. Transportation Research Procedia, 12, 508–521.
Loaiza Quintana, C., Climent, L., & Arbelaez, A. (2022). Iterated local search for the ebuses charging location problem. In Seventeenth International Conference on Parallel Problem Solving from Nature, Dortmund, Germany, September 10–14 (To Appear).
Mandi, J., Stuckey, P. J., & Guns, T. (2020). Smart predict-and-optimize for hard combinatorial optimization problems. In Thirty-Fourth AAAI Conference on Artificial Intelligence, New York, USA, February 7–12 (Vol. 34, No. 2, pp. 1603–1610).
Olgun, B., Koç, Ç., & Altiparmak, F. (2021). A hyper heuristic for the green vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 153.
Sangiorgio, M., & Dercole, F. (2020). Robustness of lstm neural networks for multi-step forecasting of chaotic time series. Chaos, Solitons & Fractals, 139.
Schneider, M., Stenger, A., Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(4), 500–520.
Shobana Devi, A., Maragatham, G., Boopathi, K., & Lavanya, S. R. (2021). Long-term wind speed forecasting—A review. Artificial Intelligence Techniques for Advanced Computing Applications, 130, 79–99.
Spliet, R., & Gabor, A. F. (2015). The time window assignment vehicle routing problem. Transportation Science, 49(4), 721–731.
Zhang, T., Chen, W., Han, Z., et al. (2013). Charging scheduling of electric vehicles with local renewable energy under uncertain electric vehicle arrival and grid power price. IEEE Transactions on Vehicular Technology, 63(6), 2600–2612.
Acknowledgements
This work received funding from the Sustainable Energy Authority of Ireland (SEAI) Research, Development & Demonstration (RDD) 2019 programme under the grant number 19/RDD/519. The authors would like to thank the anonymous reviewers for their comments and suggestions which helped to improve the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2023 The Author(s)
About this paper
Cite this paper
Jarvis, P., Climent, L., Arbelaez, A. (2023). Smart and Sustainable Scheduling of Charging Events for Electric Buses. In: Henriques, C., Viseu, C. (eds) EU Cohesion Policy Implementation - Evaluation Challenges and Opportunities. EvEUCoP 2022. Springer Proceedings in Political Science and International Relations. Springer, Cham. https://doi.org/10.1007/978-3-031-18161-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-18161-0_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-18160-3
Online ISBN: 978-3-031-18161-0
eBook Packages: Political Science and International StudiesPolitical Science and International Studies (R0)