Contents Introduction
With the inevitable increase of electric buses in the fleets of bus operators worldwide, the problem of route and charging scheduling becomes more important. Compared to the diesel fleets, the electric buses pose new challenges such as a shorter range due to the limited battery capacity, significantly longer refueling (charging) time and energy consumption which is highly dependent on parameters such as for example the ambient temperature [1]–[4]. These new requirements have a direct impact both on the daily operation of such fleets as well as on their composition and cost. Including these properties into the existing route-scheduling systems, such as making sure that the buses have enough energy to cover their trips and enough time to recharge, is crucial for uninterruptable daily operation of electric bus fleets [5], [6]. The composition and cost of one fleet is on the other hand also highly dependent on the route scheduling, since it can lead to a smaller number of necessary buses. Besides the route scheduling a further important aspect of the electric bus fleets is the charging scheduling. The scheduling of the charging events has a significant effect on the operational costs, design of charging infrastructure, the expected load peak and the grid connection point [7]–[11]. Therefore, a combined strategy of both route- and charging scheduling is necessary, especially for depots with limited capacity available from the power grid.
The term “route scheduling” used in this paper is defined as a case of the so-called Vehicle Scheduling Problem (VSP) and has a goal to assign buses to an already predefined timetable with trips. The VSP is a very well researched topic. Additional constraints relevant to the electric bus fleets, such as for example the battery charging and discharging, lead to a special case of the VSP called Electric Vehicle Scheduling Problem (E-VSP). Several authors proposed scheduling algorithms for a variety of different specific problems, focusing on different charging concepts and different fleet compositions (homogenous or heterogeneous). While distinguishing the charging concepts, the proposed solutions focus on the battery swapping principle [12], [13], fast charging on chosen stations and terminals (opportunity charging) [14]–[16] or centralized charging (single or multiple depots or terminals). In case of centralized charging, the bus depots are often big and equipped with the charging stations with lower power compared to fast opportunity charging. Further important difference between the analyzed problems is the fleet composition, such as a mixed fleet of electric and other buses [17]–[21] or a pure electric fleet, which is shown in a more detailed overview in Section II.
This paper focuses on a single centralized bus depot and pure electric bus fleet consisting of different bus types. After the introduction, there is an overview of relevant publications in the same research field in Section II. The contribution of this paper compared to other work is also given in this section. The analyzed depots are presented in Section III. Section IV provides an insight into the problem definition and the methodology that was used. Results are shown in Section V followed by a conclusion in Section VI.
Literature Overview
Studies concentrating on the route scheduling, as the problem defined in this paper, are summarized in Table 1. The comparison is based on several characteristics such as the method (exact or heuristic), consideration of a heterogeneous fleet (different types of electric buses), charging on additional terminals besides one central depot, consideration of the grid capacity and the ability to charge the buses only partially. Janovec and Koháni propose a linear programming (LP) mathematical model to minimize the number of used buses for a pure homogenous electric bus fleet [22]. Besides charging on the depot, they also allow charging on further chosen terminals. Additionally they allow partial charging. Jefferies and Göhlich propose among other things a greedy scheduling algorithm for opportunity charging as well as for centralized depot charging, with the goal to minimize the total cost of ownership (TCO) [14]. Olsen and Kliewer propose a heuristic algorithm for scheduling trips of a pure electric fleet with the goal to minimize the overall costs [23]. In addition to the charging on one centralized bus depot, buses can also charge on several further stops during the trip. Messaoudi and Oulamara tackle the problem of bus scheduling, allocations to the parking space at the depot and charging schedule [24]. They propose a mixed integer linear programming (MILP) model for very small instances and a decomposition model (DM) for larger problems. In case of exceeding the allowed grid capacity, the available charging power for the buses is reduced. van Kooten Niekerk et al. propose a linear programming method as well as column generation (CG) algorithm to minimize the total cost of a pure electric bus fleet [25]. They also include electricity cost and battery degradation into their models. Wen et al. propose a method to minimize the number of vehicles and the total traveling distances (total deadheading) using MILP and adaptive large neighborhood (ALN) search [26]. They use a randomly created set of trips for the analysis. Rogge et al. consider route scheduling while planning the number of necessary buses for different scenarios and the number of necessary chargers at the depot [27]. They use grouping genetic algorithm (GGA) and MILP formulation to minimize the total cost of ownership. By additionally scheduling the charging events, they avoid charging overlapping and reduce the number of necessary chargers. Yao et al. propose a heuristic solution method based on a genetic algorithm (GA) with the goal to minimize the total scheduling cost [28]. They consider multiple buy types with different ranges. Tao and Avishai propose a heuristic solution to minimize the number of buses necessary for operation as well as the number of chargers [29]. They use the deficit function theory and adjusted maximum flow approach.
This paper proposes an exact route-scheduling optimization model that can be applied for different objectives such as the minimization of the number of buses or the minimization of the fleet cost. The model focuses on a scheduling problem with the following characteristics: usage for both homogenous and heterogeneous fleets, charging only on centralized depots and including partial charging. Especially when considering heterogeneous fleets with electric buses of different types and different battery capacities there is only a few research published so far. This is, however, a very important aspect of future electric bus fleets. Further contribution of this paper is an extension of the model to include charging scheduling. The goal of the combined route- and charging schedule is to minimize the number of buses charging simultaneously and in that way minimize the expected maximum load peak at the depot. Rather than decreasing the charging power, the optimization provides an optimum schedule of charging events, shifting the charging to the time periods with less load. By adding the charging scheduling into the proposed model, it is possible to take the capacity of the grid at the grid connection point into account. Further on, this paper provides an analysis of the proposed optimization model using real timetables of five bus depots in the city of Hamburg in Germany. Providing a concrete study of the existing timetables while considering the infrastructure, charging and operation concept of future electric bus depot in this city, can assist other fleet operators in the process of the electrification of their fleets.
Analyzed Depots
Five different bus depots (BD1 to BD5) with corresponding timelines were chosen for the analysis in this paper. The chosen examples are based on the bus depots with diesel buses from the city of Hamburg. This city has decided to completely electrify its bus fleet by the year 2030 [8]. Based on this plan and for the purposes of this paper, it was assumed that the five analyzed depots are completely electrified and that the conventional buses can be replaced with electric ones. All bus trips at these depots are circular, meaning that buses start and finish their trips at the same depot. Fig. 1 shows the cumulative distribution of the different trip lengths and Fig. 2 the duration of those trips for the five analyzed depots for a typical working day. As it can be seen, there are only a few trips with the length under 50 km with some trips going even up to 300 km. The majority of the trips lasts between 5 and 15 hours. The vast majority of the trips occurs during the day, with only a small number during the night. All buses at the depots have their parking spaces with the proper charging infrastructure. Just like at the already existing electric depots in the city, the nominal charging power in this paper is set to 150 kW. It is assumed that the buses charge with constant power. Bus types 
\begin{equation*} C_{\mathrm {b}}=L_{\mathrm {b}}\cdot \mathrm {1.3/0.9}\tag{1}\end{equation*}
MILP Definition and Methodology
A small example of the route-scheduling problem is shown in Fig. 3. There are two types of nodes. The first type of nodes (starting with number 1) represents the initial positions of the buses at the depot. The second type of nodes (starting with number 1001) represent the bus trips. All trips are circular as they start and finish at the same depot with a possibility to charge before the next trip. Trip nodes have a departure and arrival time, length (kilometers) and a required bus type. Connection between two nodes is feasible if they have matching bus types and if the arrival of the first node is before the departure of the second one. Additionally, the departure must occur within 15 hours (900 minutes) since this is the maximum allowed dwelling time for the buses at the depot. Two sets are calculated in the initialization phase, set of all feasible arrival nodes
A_{1003}=\{\mathrm {3,4,1002}\} D_{1003}=\{\mathrm {1004,1005}\}
Graphical representation of the route-scheduling problem for a pool of buses with different battery capacities at the depot.
Using only feasible connections decreases the number of variables which can contribute significantly to the computation time.
Table 3 shows all the relevant variables for the problem definition.
A. Basic Constraints
Important part of the route-scheduling problem is the node connections, defined with constraints (2)–(5). Each node must have one incoming connection, meaning that each trip must have one bus assigned to it, as defined in constraint (2). On the other hand, the nodes do not need the have an outgoing connection, as defined in constraint (3). For example, the nodes at the end (last planned trip) do not have a further connection.\begin{align*}&\sum _{j\in A_{i}}{R_{j,i}=1;~\forall ~i\in N_{1001}} \tag{2}\\&\sum _{i\in D_{j}}{R_{j,i}\le \mathrm {1};~\forall ~j\in N_{1}\cup N_{1001}}\tag{3}\end{align*}
The capacity of the first initial nodes (≤1000) is a fixed parameter as it simply represents the capacity of the buses \begin{equation*} {if~R}_{j,i}=1~{then~C}_{j}=C_{i};~\forall i\in N_{1001},~\forall j\in A_{i}\tag{4}\end{equation*}
Another relevant aspect of the route-scheduling problem is the charging and discharging of the electric buses, defined in constraints (5)–(11). The discharging depends on the battery charge of the incoming node and the energy consumption of the bus, as shown in constraint (5). For the route scheduling purposes in this paper, the energy consumption of buses during one particular day is calculated as a simple linear function of the minimum daily temperature. However, more complex methods for forecasting the bus consumption on a specific route can be applied without any negative effect on the optimization efficiency, since the consumption is only an input variable. Initial nodes (≤1000) are assumed to be fully charged. When discharging, the buses are not allowed to go under 10% of the total battery capacity, as specified in constraint (6).\begin{align*}&{if~R}_{j,i}=1~then~{aC}_{i}={dC}_{j}-{Cons}_{i}; \\&\qquad \forall ~i\in N_{1001},~\forall j\in A_{i} \tag{5}\\&{aC}_{i}\ge 0.1\cdot C_{i};~\forall i\in N_{1001}\tag{6}\end{align*}
The charging depends on the total available time on the node (in minutes), charging power and charging efficiency which is set to 95%, as shown in constraint (7).\begin{equation*} {dC}_{i}={aC}_{i}+{chT}_{i}\cdot \frac {P}{60}\cdot 0.95;~\forall i\in N_{1001}\tag{7}\end{equation*}
The charging time must be chosen carefully. On one hand, it cannot be longer than the total available time at the node (time between the arrival and the next planned departure). On the other hand the time cannot be bigger than the time necessary to fully charge the battery. This is defined in constraints (8) and (9). Making sure that the charging time always equals to the smaller one of these two values (time until fully charged or time until departure) is guaranteed with constraints (10) and (11), the so-called “big M” constraints. The big M in constraint (10) is set to 180 (minutes), since this is the theoretical maximum time one bus would need to fully charge. The big M in constraint (11) is set to 900 since this represents the maximum time distance between two nodes (15 h or 900 minutes). The binary variable \begin{align*}&chT_{i} \le \frac {\left ({C_{i}-{aC}_{i}}\right )\cdot 60}{P\cdot 0.95};~\forall i\in N_{1001} \tag{8}\\&if~R_{i,j}=1~then~{chT}_{i} \le {dT}_{j}-{aT}_{i}-1; \\&\qquad \forall i\in N_{1001},~\forall j\in D_{i} \tag{9}\\&{chT}_{i} \ge \frac {\left ({C_{i}-{aC}_{i}}\right )\cdot 60}{P\cdot 0.95}- 180\cdot x_{i}; \forall i\in N_{1001} \tag{10}\\&{if~R}_{i,j}=1 \\&then~chT_{i} \ge \left ({dT_{j}-{aT}_{i}-1}\right ) \\&\qquad - 900\cdot \left ({1-x_{i}}\right );~\forall i\in N_{1001},~\forall j\in D_{i}.\tag{11}\end{align*}
B. Grid Capacity Constraints
For the case where there is a limited grid capacity for the depot, it is necessary to schedule the charging events of the buses with respect to this limit. In this paper, the grid limit is defined as the maximum allowed load peak or the maximum number of buses allowed to charge simultaneously. This is possible since all of the buses charge with the same charging power (150 kW) and the charging process is considered to be linear, meaning the charging is implemented with constant power. If neglecting the electrical loses within the depot itself, the number of buses charging simultaneously is therefore considered to be directly proportional to the load peak in this paper. Taking the grid capacity limit into consideration is implemented within constraints (12)–(18). Charging end of some node depends on its charging start and the charging time, as shown in constraint (12). Charging start and charging end are also limited with the arrival and departure time, respectively, as defined in constraints (13)–(15). Charging end must be before the next planned departure as shown in constraint (13). For the final nodes, that do not have any further connections, the charging end must be within 15 hours upon arrival, as shown in constraint (14). Charging start must be after the arrival time, as defined in constraint (15).\begin{align*} {End}_{i}=&{Start}_{i}+{chT}_{i};~\forall i\in N_{1001} \tag{12}\\ if~R_{i,j}=&1~then~{End}_{i}\le {dT}_{j};~\forall i\in N_{1001},~\forall j\in D_{i} \qquad \tag{13}\\ {End}_{i}\le&{aT}_{i}+900;~\forall i\in N_{1001} \tag{14}\\ {Start}_{i}\ge&{aT}_{i};~\forall i\in N_{1001}\tag{15}\end{align*}
After the charging start and charging end have been defined, it is necessary to see how many buses are charging at each single minute. This can be achieved with the binary decision variables \begin{align*}&(t+1)\cdot \left ({1-y_{i,t}}\right )\le {Start}_{i};~\forall i\in N_{1001},~\forall t\in T \tag{16}\\&{End}_{i}-t+1\le z_{i,t}\cdot 900;~\forall i\in N_{1001},\forall t\in T \tag{17}\\&\sum _{i\in N_{1001}}{y_{i,t}+z_{i,t}-1\le cLimit};~\forall t\in T.\tag{18}\end{align*}
C. Objectives
Minimization of the number of buses can be achieved with objective (19). The number of buses can be minimized regardless of the composition of the fleet, homogenous or heterogeneous.\begin{equation*} min\sum _{n\in N_{1}}{\sum _{i\in D_{n}}{R_{n,i}}}\tag{19}\end{equation*}
Another interesting goal especially for the case of a heterogeneous fleet is the minimization of the total purchasing cost as shown in objective (20). Since the buses with a smaller battery capacity also cost less, looking for an optimum number of buses with different capacities can significantly reduce the total purchasing cost of the fleet.\begin{equation*} min\sum _{n\in N_{1}}{\sum _{i\in D_{n}}{R_{n,i}}}\cdot {Cost}_{n}\tag{20}\end{equation*}
\begin{equation*} min\sum _{n\in N_{1}}{\sum _{i\in D_{n}}{R_{n,i}}}\cdot {Cost}_{n}+cLimit\cdot w.\tag{21}\end{equation*}
Results
The MILP problem defined in this paper was implemented in Python 3.7 using Gurobi 9.0.1 solver on a machine with Intel Core i7 2.7–2.9 GHz, 16 GB RAM and 2 cores. Fig. 4 shows an example output for one bus depot. For every chosen bus, the schedule shows the corresponding trips (blue blocks) and charging events (green blocks). The effect of grid constraint and charging scheduling is obvious when observing the green charging blocks. In the case without grid constraint, the charging takes place immediately after arrival to the depot and the green blocks are connected to the blue ones, as shown in Fig. 4a. For the case with the grid constraint, the green blocks take the best possible position to avoid mutual overlapping as shown in Fig. 4b. Time window for charging scheduling can be limited to the evening hours as further explained in Section V-B.
Example of an output schedule for one depot showing the trips and the charging events for the chosen buses: (a) for the case without grid capacity limit and charging scheduling; (b) for the case with grid capacity limit and charging scheduling.
Two different cases are analyzed for five different depots in this paper, homogenous and heterogeneous fleet. The initial number of buses for the homogenous fleet (S1) is 80% of the number of trips in one day. For the heterogeneous fleet (S2) defined in (22), the initial number of buses \begin{equation*} B_{l}={Tr}_{l}+{MF}_{l}\cdot tTr;~\forall l\in \left \{{150,~200,~250,~300}\right \}\tag{22}\end{equation*}
Based on the experience from the analysis of several bus depots in this paper, the multiplication factor MF was set to 5% for the ranges 200, 250 and 300 km and to −30% for the range of 150 km. A summary of initial available buses for the optimization for each depot and for both fleet compositions is given in Table 4. In the case of a homogenous fleet, all buses have the range of 300 km. This is necessary since there are several trips with the length between 250 and 300 km. The total observed time for the scheduling is from the first trip, which is usually around 3 AM until 12 PM on the following day. This leads to an average total time window for scheduling of 33 hours. Scheduling beyond the 24 hour-frame is important to make sure that the buses charging overnight can indeed charge enough to cover the trips on the following day.
The optimization model proposed in this paper can be used for scenarios with or without grid capacity limitation. Accordingly, the results are split into two parts. In the first part, using the cost minimization an optimum number of buses is determined. In the second part, the grid capacity limit is taken into account.
A. Minimizing the Cost
The cost optimum number of buses based on the inputs defined in Table 4 is shown in Table 5. The Gurobi settings were adjusted to find the best objective in the shortest possible time. As it can be seen from the resulting gap (difference between the lower bound and the best objective) in Table 5, not every solution reached 0% gap in the shown computation time. This is due to the user defined termination criteria. Based on the experience from analyzing different scenarios and different depots, the criteria for terminating the optimization in this paper were set to 60 s without any change in the best objective, for the cases where the gap is already under 1%. These criteria were applied for bus depots BD2, and BD4, for the scenario S2. Besides this user defined termination criteria, the solver also stops when reaching 0% gap, which was the case with the bus depots BD1, BD3 and BD5. In fact all of the analyzed cases, even BD2 and BD4, eventually reached the 0% gap, as shown for the example of BD4 in Fig. 5. For this case, the Gurobi settings were adjusted to focus on proving optimality, instead of looking for the best objective in the shortest possible time. As it can be seen, the optimum solution (best objective) was found after 170 s. The lower bound continued to change until eventually after 632 s the gap reached 0%. This was the case for the bus depots BD2 as well. The user defined termination criteria was introduced to decrease the total computation time and did not affect the optimum solution for any of the analyzed cases.
Elapse of the computation time for the bus depot BD4 and scenario S2, showing the best objective and best bound until the gap reaches 0%.
As expected, the computation time grows with the problem size. For the homogenous fleet it took from 1.2 to 13.8 s to solve the optimization problem, depending on the complexity of the depot. For the heterogeneous fleet, the computation time was from 8.8 s to 167.1 s, depending on the depot. The computation time is the total time needed to reach the optimum schedule, including initialization, model building, solving and plotting the results.
It is interesting to observe that the heterogeneous fleet, consisting of buses with different battery capacities, lead to lower costs. The difference in cost between the homogenous and heterogeneous fleet grows with the depot size. While for the BD1 it was 2 Mio. €, for the BD5 the difference reached an amount of 7 Mio. €. This shows the advantage of operating a mixed fleet of buses with different capacities. Fig. 6 shows a comparison of the trips and optimum fleet composition for the five analyzed depots. The bar on the left side for each depot represents the number of trips with different ranges. The bar on the right side for each depot represents the optimum heterogeneous fleet with the number of buses for each analyzed range. As it can be seen, the number of buses with the ranges 200, 250 and 300 km was kept to the minimum and corresponds approximately to the number of trips with that same range. The number of buses with the range 150 km was significantly smaller compared to the number of trips with that range for all depots. This can be explained by the numerous trips with a relatively small distance on each depot, meaning that one bus with the range of 150 km usually covers several smaller trips during one day.
Number of trips with different ranges as well as the optimum number of buses in the heterogeneous fleet for the five analyzed depots.
B. Optimization Considering the Capacity Limit
The grid capacity limit in this analysis is defined as the maximum number of buses that are allowed to charge simultaneously. Two possible approaches to including this grid capacity into the route and charging scheduling were analyzed in this paper. One approach is to include the number of buses charging simultaneously into the objective and minimize it together with the cost of the fleet. This approach leads to a combined cost and load peak minimization on the depot. Other approach is to only minimize the cost while considering the grid capacity as a predefined constant. This approach is suitable for depots where the capacity limit at the grid connection point is a well-known and fixed parameter. The number of buses charging simultaneously without any consideration of the grid capacity limit is shown in Fig. 7 for one whole day.
Number of buses charging simultaneously for the five analyzed depots, without optimized charging schedule.
Several additional variables need to be added to the MILP formulation in order to include the capacity limit, as shown in Section IV. Since every single minute is simulated, for all available buses, these additional variables lead to a significant increase in the problem complexity and the computation time.
In order to deal with this problem, two simplifications were implemented. The first simplification is a limited time frame in which the grid capacity is considered (for either one of the two mentioned approaches). Depending on the size and properties of the depot, the majority of the load can occur during the night hours, from 6 PM until 4 AM on the following day. This is obvious for the example for depots 2, 4 and 5 in the Fig. 7. Therefore, the grid capacity limit can also be observed only during this time period. In this case for the buses that arrive during the observed time period (6 PM – 4 AM) the solver looks for an optimum start of the charging process. The buses that arrive outside of the observed time period, charge immediately upon their arrival to the depot. This is demonstrated with the time window for charging in the Fig. 4. Reducing the observed time period can lead to a significant decrease of the computation time. For the depots where there is a rather equal distribution of load during the day and night, for example depots 1 and 3 in Fig. 7, this simplification cannot be applied. The second simplification is the observed time step. This affects directly the constraints (16)–(18) and the set of analyzed time units T. Instead of using a set T with 1-minute time step, it is possible to increase the step an observe 10 minute blocks. This would mean, that instead of calculating the number of buses charging simultaneously in every single minute, the optimization focuses on this number in every block of 10 minutes. This action also leads to a significant decrease of computation time and on the other hand, did not show any negative effects on the resulting objective. Both fleet compositions are analyzed in this section, just like in the previous one, homogenous (S1) and heterogeneous (S2). Initial conditions at the depot are also the same as in the previous section, as summarized in Table 4.
Table 6 shows the results for two different variants:
Variant A - Minimizing both the cost and the number of buses charging simultaneously
Variant B - Minimizing the cost with a fixed allowed number of buses charging simultaneously. This number was calculated as 20% of the optimum fleet size for each depot
All of the analyzed cases resulted in the same number of optimum buses like in the previous section, shown in Table 5. However, the computation time increased. When minimizing both the cost and the number of buses charging simultaneously, for the homogenous fleet it took from 6.1 s to 267.8 s to solve the optimization problem, depending on the complexity of the depot. For the heterogeneous fleet, the computation time was from 81.3 s to 492.6 s, depending on the depot. Especially the case of the heterogeneous fleet for the depots BD3 and BD5 required significantly more computation time, compared to the results in the previous section without the grid capacity limitation. When minimizing only the cost, with a fixed predefined number of buses charging simultaneously, the computation time was smaller. For the homogenous fleet it took from 2.9 s to 33.12 s and for the heterogeneous fleet it took from 18.54 s to 155.37 s to reach the optimum solution.
The effect of the charging scheduling can be seen in Fig. 8, showing the number of buses charging simultaneously for on whole day on the BD5. The figure gives a comparison of three different charging scheduling approaches analyzed in this paper. While minimizing the cost only and not considering the grid capacity the peak number of buses charging simultaneously was 27. When considering the grid capacity, the peak number was 19 when using a fixed predefined limit (20% of the total number of buses at the depot) and 12 when minimizing both the cost and the number of buses charging at the same time.
Number of buses charging simultaneously for the BD5 for three different approaches to charging scheduling.
It is interesting to observe in the Fig. 8 how the charging without any intelligent charging scheduling and with a fixed allowed number of buses in the variant B ended around 4 AM. For the variant A, when minimizing the number of buses charging simultaneously, there are buses charging even until 7:20 AM. This is due to do the fact that in the variant A, the solver used the maximum of the potential for shifting the charging events. Several of the buses charged up to a few minutes before their departure. The potential for charging event shifting is for the analyzed BD5 indeed significant. A total of 33 trips have their departure time between 6 AM and 7:30 AM which means that the buses assigned to these trips can charge even long beyond the last charging event at 4 AM shown for the variant B.
In this paper, there was no time limit for the buses regarding the end of their charging. However, based on the experience of bus fleet operators, this time limit can be easily set. This would mean that for example buses need to finish charging at least 10 minutes before their departure to account for all of the procedures that need to be conducted, before the bus actually leaves the depot.
C. Comparison With Other Models and Algorithms
Comparing the efficiency of the optimization model proposed in this paper with other proposed models and algorithms in the literature is not straightforward. The best indicator of the efficiency is the computation time. However, this depends strongly on the size of the problem (number of trips and buses), observed time window, properties of the computer used for optimization and other parameters. Table 7 gives an overview of the results with the publications that can be considered most similar to this paper and that focus on exact solutions. Heuristic algorithms are not considered for the comparison. Janovec and Koháni propose an exact solution based on LP and demonstrate the results with 4 different scenarios [22]. Meassaudi and Oulamara propose a MILP and a decomposition model [24]. MILP did not manage to solve even the smallest instance and the results demonstrated in the paper were calculated using the decomposition model. van Kooten Niekerk et al. demonstrate the results of their proposed LP model using 4 different scenarios [25]. For all of these scenarios, they run the optimization once for the buses with a battery capacity of 122 kWh and once for 244 kWh. While the capacity of 122 kWh gave very good result, with a solution up to 4 s, the 244 kWh capacity needed up to 894 s. Wen et al. use among other methods a MILP model and demonstrate results on a randomly created sets of trips [26]. For the biggest case of 30 trips, the optimization managed to provide a result in a time range from 2.4 to 1107 s. Not all of the cases reached optimality. Those who did reach it resulted in an optimum fleet of 7 to 10 buses.
All of the proposed solutions in Table 7 are for homogenous fleets. Additionally, only Meassaudi and Oulamara consider a grid capacity limit. To the best knowledge of the authors, there is no similar work proposing an exact solution and in the same time also demonstrating the results for a heterogeneous electric fleet published so far. The most similar publication to the presented approach in this paper, focusing on the number of buses charging simultaneously, is Rogge et al. [27]. They however analyze a more complex problem and use a heuristic approach. They also do not state the necessary computation time in their publication which would allow a relevant comparative value.
Conclusion
This paper proposes a MILP based route scheduling model for centralized large-scale electric bus depots. The model can be used for the cost minimization as well as the minimization of the number of buses in a fleet. In a response to the mixed fleets of different electric buses, with different battery capacities, as seen on many depots in reality, the model in this paper considers both homogenous and heterogeneous fleets. Additionally, the grid capacity limit at the grid connection point can be included in the scheduling process. For this purpose, the model focuses not only on the route but also on the charging scheduling. By scheduling the charging events, the optimization model can minimize the number of buses charging simultaneously and in that way directly reduce the expected load peak which is critical in case of a limited grid capacity at the connection point. The efficiency of the proposed solution is demonstrated on five real depots from the city of Hamburg in Germany. Due to the usage of concrete timetables of existing depots, as well as operation concepts based on real electric bus depots already implemented in Hamburg, the analysis in this paper can provide valuable inputs to other transportation companies planning the electrification of their fleets.
While minimizing the cost of the fleet, without the grid capacity limit, the model managed to give optimal solution for all of the five depots, homogenous as well as heterogeneous scenario, within the computation time from 1.2 s to 167.1 s. For the biggest depot BD5, the heterogeneous fleet resulted in 7 Mio. € smaller purchasing cost, compared to the homogenous fleet. This shows the advantage of operating a mixed fleet of buses with different capacities.
Minimizing the cost while taking the grid capacity limit into account resulted in longer computation time. Two scenarios were observed in this case, minimizing both the cost and the number of buses charging simultaneously and minimizing the cost while considering a predefined fixed number of buses allowed to charge simultaneously. For the first case the computation time was from 6.1 s to 267.8 s for the homogenous and from 81.3 s to 492.6 s for the heterogeneous fleet. The second case on the other hand results in a computation time from 2.9 s to 33.12 s and from 18.54 s to 155.37 s for the homogenous and heterogeneous fleet respectively.
The short computation time allows the usage of the proposed scheduling model in the design phase upon purchasing of the fleet, but also in daily operation.
Charging process in this paper is assumed to be linear, with a constant charging power. This can lead to underestimation of the total charging time. Integration of realistic charging curves in the model is a part of the future work.
ACKNOWLEDGMENT
This work is a part of the project Accompanying Research for Charging Infrastructure on Bus Depots. The authors thank the project partners Hochbahn AG and Verkehrsbetriebe Hamburg-Holstein GmbH (VHH) for their cooperation and support.