Location Planning of Charging Stations for Electric Buses: Comparison
View Latest Version
Please note this is a comparison between Version 2 by Nora Tang and Version 1 by Natalia Kliewer.

Many public transport companies have recently launched projects testing the operation of electric buses. Progressively, traditional combustion engine buses are being replaced by electric buses. In such cases, some stops on bus lines are equipped with charging technology. Combustion engine buses can operate for an entire day without having to refuel. By contrast, electric buses have considerably shorter ranges and need to recharge their batteries throughout a day. For cost-efficient use of electric buses, charging stations must be located within the road network so that required deadhead trips are as short as possible, but attention must also be paid to construction costs. In contrast to vehicle scheduling, which is a more short-term planning task of public transport companies, location planning of charging stations is a long-term planning problem and requires a simultaneous solving of both optimization problems. Specifically, location planning and vehicle scheduling have to be considered simultaneously in order to open up optimization potentials by comparison to sequential planning, since locations of charging stations directly influence the resulting vehicle rotations. 

  • location planning
  • vehicle scheduling
  • electric buses

1. Scheduling Electric Buses

As one of the first contributions dealing with alternative engine types within vehicle scheduling, Stasko and Gao [14][1] present a solution method for the VSP taking into account different engine options. The solution approach is based on integer programming. Engines powered by compressed natural gas (CNG) are considered besides combustion engines. The approach aims at reducing emission levels within vehicle scheduling.
Reuer et al. [15][2] consider a mixed fleet of vehicles consisting of electrically powered buses and buses without range limitations within the basic VSP. The authors apply a time-space network based exact solution method for the VSP introduced by Kliewer et al. [16][3] to solve the enhanced optimization problem. Solutions obtained to this problem contain optimal flow values through the network. Therefore, strategies for flow decomposition are necessary to obtain vehicle rotations. The authors analyze six strategies for flow decomposition that aim at maximizing the proportion of feasible vehicle rotations for BEBs. Battery charging is assumed to be performed within constant time periods. The authors show that a simple substitution of traditional buses with BEBs leads to widely infeasible vehicle schedules.
Haghani and Banihashemi [17][4] consider a fleet consisting entirely of range restricted vehicles. They consider vehicle scheduling with route and time constraints in order to limit the lengths and durations of vehicle rotations. However, battery charging is not considered. The authors propose one exact and two heuristic solution models together with techniques for reducing the problem sizes in order to solve even larger-scale problem instances. Chao and Xiaohong [18][5] consider battery swapping in addition to limited operating ranges of BEBs within the VSP. To solve the problem, a solution method based on a Non-dominated Sorting Genetic Algorithm (NSGA-II) is introduced. A case study based on real-world data taken from a project in Shanghai is performed to analyze the solution approach. Li [19][6] addresses vehicle scheduling of BEBs with either battery swapping or charging and presents a model for restricting the maximum route distance. Both fast charging and battery swapping are presumed to be performed within constant time windows, but the time for fast charging depends on the location. Adler and Mirchandani [20][7] deal with scheduling of BEBs incorporating charging procedures at given charging stations located within the road network. To solve the problem, they present a column-generation approach. A heuristic method is presented to obtain necessary initial solution. The algorithm is based on a greedy algorithm and computes vehicle rotations under consideration of range limitations and charging. In this work, again full chargings of vehicle batteries are assumed.
As one of the first authors, Wen et al. [21][8] address the E-VSP with partial chargings. They present an exact solution method based on mixed integer programming and an adaptive large neighborhood search heuristic approach. The results demonstrate that the exact solution methods is only applicable to small problem instances. However, the heurstic solution approach also solves larger instances in a reasonable amount of time.  van Kooten Niekerk et al [22][9] also consider partial charging procedures of BEBs. The authors introduce a solution approach based on column generation. Charging times depend linearly on a battery’s SoC. Furthermore, battery aging and time-dependent energy prices are considered. The authors show that in some cases, the consideration of partial charging procedures leads to cost savings.
Recently, Wang et al. [23][10] proposed an exact solution method for the E-VSP based on dynamic programming. Within this contribution, battery aging is particularly considered. The objective of the solution method is minimize the total costs especially incorporating costs for battery replacements during the life spans of the vehicles deployed. By a computational study, the authors analyze the influence of different working loads, battery management, and working temperatures of batteries on resulting vehicle schedules.

2. Location Planning of Charging Stations for Electric Buses

At the present time, only few publications deal with location planning of charging stations for BEBs in public transport. Kunith et al. [2][11] present a mixed integer linear optimization model for determining locations for charging stations for a bus route. The model is based on a set covering problem. The objective is to minimize the number of charging stations needed. The authors consider constraints imposed by the buses’ operation and the battery charging process. In addition, different energy consumption scenarios are considered to reflect external influencing factors on the buses’ energy consumption, such as traffic volume and weather conditions. Standard optimization libraries are used for solving the problem.
Berthold et al. [24][12] propose a mixed integer linear program in order to determine optimal locations of charging stations for the electrification of a single bus line in Mannheim. The problem is solved by using standard optimization libraries. Furthermore, partial charging procedures and battery aging effects over several time periods are considered. Since the problem is very complex, the solution approach is not suitable for larger instances. Xyliaa et al. [25][13] develop a dynamic optimization model to establish a charging infrastructure for BEBs in Stockholm, Sweden, considering restricted waiting times at intermediate stops on service trips given by the schedule and different currents of the charging systems imposed by local conditions. They provide statements about the application possibilities of BEBs in urban areas and effects on vehicle rotations. Within both works, no line changes of the buses used are considered.
Liu et al. [26][14] consider energy consumption uncertainties within location planning of charging stations for BEBs in public transport. Therefore, the authors propose a robust optimization model represented by a mixed integer linear program. Using real-world data, the authors show that the proposed solution model can provide optimal locations for charging stations that are robust against uncertain energy consumption of BEBs. Lin et al. [27][15] introduce a spatial-temporal model for a large-scale planning of charging-stations for BEBs in public transport. The authors consider characteristics of BEBs operation and plug-in fast charging technologies. The model is represented by a mixed-integer second-order cone programming formulation with high computational efficiency. A case study using data from Shenzhen, China is used to analyse the robustness of the solution model to timetable changes.
Stumpe et al. [13][16] present an exact mathematical model for integrated optimization of vehicle scheduling with BEBs and location planning for charging stations. The authors particularly perform a robustness analysis and study the impact of technological aspects such as battery capacity, charging power, and energy consumption as well as economic issues containing investment costs for charging stations and electric buses. A computational study points out that the exact solution model introduced is not capable of solving realistic problem instances to optimality.
Regarding related optimization problems in the scope of transportation, there are some contributions dealing with the charging infrastructure for electric vehicles. Regarding Vehicle Routing Problems (VRP) with electric vehicles, Worley et al. [28][17] propose a solution approach for the simultaneous determination of optimal locations for charging stations and vehicle routes. They show that this approach leads to lower total costs of the vehicle deployment by comparison to locations of charging stations known a priori. Schiffer and Walther [29][18] also deal with the simultaneous determination of locations for charging stations and routes for electric vehicles. The authors extend this optimization problem by considering uncertain characteristics of the customers to be served. Uncertain spatial customer distributions, demand, and service time windows are particularly addressed. The authors introduce a robust optimization approach based on adaptive large neighborhood search. Vehicle routing comprises different challenges and conditions than vehicle scheduling and therefore needs other solution approaches. Consequently, it is not possible to draw concrete statements with regard to the E-VSP.

References

  1. Stasko, T.; Gao, H. Reducing transit fleet emissions through vehicle retrofits, replacements, and usage changes over multiple time periods. Transp. Res. Part D Transp. Environ. 2010, 15, 254–262.
  2. Reuer, J.; Kliewer, N.; Wolbeck, L. The electric vehicle scheduling problem-a study on time-space network based and heuristic solution approaches. In Proceedings of the Conference on Advanced Systems in Public Transport (CASPT), Rotterdam, The Netherlands, 19–23 July 2015.
  3. Kliewer, N.; Mellouli, T.; Suhl, L. A time–space network based exact optimization model for multi-depot bus scheduling. Eur. J. Oper. Res. 2006, 175, 1616–1627.
  4. Haghani, A.; Banihashemi, M. Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints. Transp. Res. Part A 2002, 36, 309–333.
  5. Chao, Z.; Xiaohong, C. Optimizing Battery Electric Bus Transit Vehicle Scheduling with Battery Exchanging: Model and Case Study. Intell. Integr. Sustain. Multimodal Transp. Syst.-Procedia-Soc. Behav. Sci. 2013, 13, 2725–2736.
  6. Li, J.Q. Transit Bus Scheduling with Limited Energy. Transp. Sci. 2014, 48, 521–539.
  7. Adler, J.D.; Mirchandani, P.B. The Vehicle Scheduling Problem for Fleets with Alternative-Fuel Vehicles. Transp. Sci. 2017, 51, 441–456.
  8. Wen, M.; Linde, E.; Ropke, S.; Mirchandani, P.; Larsen, A. An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem. Comput. Oper. Res. 2016, 76, 73–83.
  9. van Kooten Niekerk, M.E.; van den Akker, J.M.; Hoogeveen, J.A. Scheduling Electric Vehicles. Public Transp. 2017, 9, 155–176.
  10. Wang, J.; Kang, L.; Liu, Y. Optimal scheduling for electric bus fleets based on dynamic programming approach by considering battery capacity fade. Renew. Sustain. Energy Rev. 2020, 130, 109978.
  11. Kunith, A.; Goehlich, D.; Mendelevitch, R. Planning and Optimization of a Fast Charging Infrastructure for Electric Urban Bus Systems. In Proceedings of the 3rd International Conference on Traffic and Transport Engineering, Lisbon, Portugal, 17–18 April 2014; pp. 43–51.
  12. Berthold, K.; Förster, P.; Rohrbeck, B. Location Planning of Charging Stations for Electric City Buses. In Operations Research Proceedings; Springer: Cham, Switzerland, 2015; pp. 237–242.
  13. Xyliaa, M.; Leducc, S.; Patrizioc, P.; Silveiraa, S.; Kraxnerc, F. Developing a dynamic optimization model for electric bus charging infrastructure. Transp. Res. Procedia 2017, 27, 776–783.
  14. Liu, Z.; Song, Z.; He, Y. Planning of Fast-Charging Stations for a Battery Electric Bus System under Energy Consumption Uncertainty. Transp. Res. Rec. 2018, 2672, 96–107.
  15. Lin, Y.; Zhang, K.; Shen, Z.J.M.; Ye, B.; Miao, L. Multistage large-scale charging station planning for electric buses considering transportation network and power grid. Transp. Res. Part C Emerg. Technol. 2019, 107, 423–443.
  16. Stumpe, M.; Rössler, D.; Schryen, G.; Kliewer, N. Study on Sensitivity of Electric Bus Systems under Simultaneous Optimization of Charging Infrastructure and Vehicle Schedules. Euro J. Transp. Logist. 2021, 10, 100049.
  17. Worley, O.; Klabjan, D.; Sweda, T.M. Simultaneous vehicle routing and charging station siting for commercial electric vehicles. In Proceedings of the IEEE International Electric Vehicle Conference (IEVC), Greenville, SC, USA, 4–8 March 2012.
  18. Schiffer, M.; Walther, G. Strategic planning of electric logistics fleet networks: A robust location-routing approach. Omega 2018, 80, 31–42.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/)
Video Production Service
Feedback