# Charging Scheduling Optimization of Battery Electric Bus with Controllable Task Completion

Feifeng Zheng, Zhixin Wang, Yinfeng Xu, Ming Liu

► To cite this version:

Feifeng Zheng, Zhixin Wang, Yinfeng Xu, Ming Liu. Charging Scheduling Optimization of Battery Electric Bus with Controllable Task Completion. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.282-289, 10.1007/978-3-030-85906-0_32. hal-04022165

HAL Id: hal-04022165

https://inria.hal.science/hal-04022165

Submitted on 9 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Charging Scheduling Optimization of Battery Electric Bus with Controllable Task Completion*

Feifeng Zheng<fnref n="1" />, Zhixin Wang<fnref n="1" />, Yinfeng Xu<fnref n="1" />, and Ming Liu<fnref n="2" />

**Abstract.** In order to reduce carbon emissions, various government organizations have taken measures to promote the development of the electric vehicle industry. Motivated by scheduling practices, this work proposes a battery electric bus (BEB) charging scheduling problem. Different from the existing research on scheduling, the completion level of each task in this problem is controllable, because the charging level of BEB can be controlled. Besides, for saving charging cost, bus companies usually charge their battery electric buses (BEBs) at night. Because of the concentration of charging time, the decision-maker must make charging scheduling decision under a departure schedule to ensure charging with no delay. For solving this problem, we first establish a mixed integer linear programming model with the aim of minimising the total electricity cost and battery loss cost. Numerical experiments demonstrate the electiveness of the proposed model.

**Keywords:** Scheduling · Optimization · Bus charging · State of charge · Battery loss cost.

## 1 Introduce

With the rapid development of the world economy and the excessive development of natural resources, the energy crisis and the deterioration of the ecological environment have become a focal topic (Ibarra-Rojas et al. 2015; Mahmoud et al. 2016). As the dominant position of petroleum energy consumption and greenhouse gas emissions, traditional fuel vehicles are facing revolutionary changes. In the long run, new energy vehicles will become the main direction of the future development of the automobile industry (Lajunen 2014; Nurhadi et al. 2014; Liu and Song 2017; Grande Yahyaoui and Gómez 2018). In recent years, many countries and regions have issued policies to promote the development of new energy vehicles. Especially battery electric buses (BEBs) are the main way to improve environmental quality and promote people's green travel (Wesseling 2016; Hao et al. 2014).

<footnote n="1">¹ Glorious Sun School of Business and Management, Donghua University, 200051, Shanghai, China</footnote>

<footnote n="2">² School of Economics & Management, Tongji University, 200092, Shanghai, China</footnote>

<footnote>* This work was supported by the National Natural Science Foundation of China (Grant No. 71771048, 71832001, 72021002, 71972146 and 72071144) and the Fundamental Research Funds for the Central Universities (Grant No. 2232018H-07)</footnote>
Due to many advantages of BEBs, their number has increased rapidly. However, the construction speed of charging piles is slow, and the problem of insufficient charging resources is prominent. Under the premise of the limited resources available, a reasonable BEB charging scheduling can effectively solve this problem (Rogge et al. 2018; He et al. 2020; Abdelwahed et al. 2020). In this work, we describe the process of BEB charging as a parallel machine problem that controllable task completion level. As an important means to optimize industrial resource allocation and promote industrial structure upgrading, parallel machine scheduling theory can improve the competitiveness of enterprises (Liu et al. 2012; Zheng et al. 2013; Karhi and Shabtay 2017; Aschauer et al. 2020). We combined the parallel machine scheduling theory to establish a BEB charging scheduling model with a controllable task completion level. In our mathematical model, the task completion level is regarded as a variable to be decided. The current research on BEBs mainly concentrates on the fields of charging site selection, charging resource optimization and allocation, and there are relatively few studies on bus charging scheduling (Kang et al., 2016; He et al., 2020). And our research is mainly devoted to the formulation of a charging scheduling plan, the purpose is to save the cost of charging and battery loss. In addition, the model incorporates the cost of battery loss into the minimization goal, and explores the charging scheduling plan for BEBs.

The remainder of this paper is organized as follows. In Section 2, we describe the problem. In Section 3, we establish a mixed integer linear programming model. In Section 4, we have verified the applicability of the model through a case study. In Section 5, gives the conclusion.

## 2 Problem description

In this part, we introduce the concept of BEB charging with a controllable task completion level. The controllable task completion level means the BEBs charging level can be controlled, and the BEB departure time and residual state of charge (SOC) will affect its charging level decision. When the BEB starts to charge, the residual SOC of the battery is known. There are $|M|$ ($M$ is charging pile set) can be used to serve $|J|$ ($J$ is BEB set) BEBs. For the convenience of calculation, we use a charging level set $B = \{1, 2, \dots, |B|\}$ to replace the charging power quantity set $Q = \{1\%, 2\%, \dots, |Q|\%\}$. In details, charging level 1 denotes 1% of the battery capacity is charged. Once a BEB arrives at the charging depot, its remaining SOC $a_j$ is known. We define $H_j$ as the actual SOC of BEB $j$ after charging activity. The controllable task completion degree in this work means that the charging level of each BEB is controllable. Fig. 1 describes the controllable task completion degree. Notice that the red bracket part in Fig.1 denotes the controllable charging interval, while the green part means the actual charging level.

In practice, a safe remaining SOC is usually set to ensure battery health of each BEB. If the remaining SOC of a BEB less than its safe remaining SOC, it is unavailable. In the actual operation process, such a safe remaining SOC usually
set as 20% of the battery capacity. Under the given the fixed bus schedules, we make a reasonable assumption that the departure time, arrival time and driving route of each BEB are fixed and known before charging activity. Hence, the lower SOC limits $l_j$ of BEB $j \in \mathcal{J}$ to meet a day's operation is known. Besides, for reducing the damage to the battery caused by overcharging and over-discharging, BEB $j \in \mathcal{J}$ is set with an optimal SOC, i.e., $\bar{H}_j$. If $H_j > \bar{H}_j$, there is an overcharging risk. While $H_j < \bar{H}_j$, it may cause the battery's discharge depth to be too deep the next day, thus, there is an over-discharge risk. Therefore, the closer the SOC after charging activity is to $\bar{H}_j$, the lower the loss of the battery.

In addition, this research is also based on the following assumptions:

1. Only one charging depot is available to satisfy the charging demand of BEBs.

2. Each BEB has a fixed departure time.

3. The type of charging pile are the same, that is to say, the charging powers are the same and known before charging activity.

4. All BEBs are homogeneous and have the same cruising range.

5. The charging rate of all charging piles is the same, and the charging process is continuous.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Charging process of BEB with controllable task completion</figcaption></figure>
## 3 Model formulation

In this work, we assume that only one charging depot is available to satisfy the charging demand of BEBs. Under the given the fixed bus schedules, we make a reasonable assumption that the departure time, arrival time and driving route of each BEB are fixed and known before charging.

Below we first present other basic parameters and decision variables, and then establish a mixed integer linear programming model.

<table><thead><tr><th colspan="2">Parameters</th></tr></thead><tbody><tr><td><i>M</i>:</td><td>set of charging piles indexed by <i>i</i>, i.e., <i>i</i> &isin; <i>M</i> = {1, 2, ..., ||<i>M</i>|}</td></tr><tr><td><i>J</i>:</td><td>set of BEBs index <i>j</i>, i.e., <i>j</i> &isin; <i>J</i> = {1, 2, ..., |<i>J</i>|}</td></tr><tr><td><i>B</i>:</td><td>set of charging level indexed <i>b</i>, <i>b</i> &isin; <i>B</i> = {1, 2, ..., |<i>B</i>|}</td></tr><tr><td><i>a</i><sub><i>j</i></sub>:</td><td>initial state of charge (SOC) of BEB <i>j</i> &isin; <i>J</i></td></tr><tr><td><i>l</i><sub><i>j</i></sub>:</td><td>the lower limit of the SOC of the BEB <i>j</i> &isin; <i>J</i> after charging</td></tr><tr><td><i>r</i><sub><i>j</i></sub>:</td><td>arrival time of BEB <i>j</i> &isin; <i>J</i></td></tr><tr><td><i>d</i><sub><i>j</i></sub>:</td><td>departure time of BEB <i>j</i> &isin; <i>J</i></td></tr><tr><td><i>c</i>:</td><td>unit electricity price</td></tr><tr><td><i>&bar;a</i><sub><i>j</i></sub>:</td><td>the lower limit of SOC before charging activity</td></tr><tr><td><i>H&#773;</i><sub><i>j</i></sub>:</td><td>the optimal SOC <i>j</i> &isin; <i>J</i></td></tr><tr><td>&lambda;:</td><td>the penalty coefficient for overcharging and over-discharging</td></tr><tr><td>&tau;<sub><i>b</i></sub>:</td><td>the charging time spent when charged to level <i>b</i></td></tr><tr><td><i>L</i>:</td><td>a sufficiently large positive real number</td></tr></tbody><thead><tr><th colspan="2">Variables</th></tr></thead><tbody><tr><td><i>S</i><sub><i>j</i></sub>:</td><td>charging start time of BEB <i>j</i> &isin; <i>J</i></td></tr><tr><td><i>C</i><sub><i>j</i></sub>:</td><td>charging end time of BEB <i>j</i> &isin; <i>J</i></td></tr><tr><td><i>p</i><sub><i>j</i></sub>:</td><td>the charging time of BEB <i>j</i> &isin; <i>J</i></td></tr><tr><td><i>H</i><sub><i>j</i></sub>:</td><td>the actual SOC at the end of charging activity</td></tr><tr><td><i>z</i><sub><i>jb</i></sub>:</td><td>a binary variable equal to 1 if the BEB <i>j</i> &isin; <i>J</i> is charged to level <i>b</i> &isin; <i>B</i>, 0 otherwise</td></tr><tr><td><i>x</i><sub><i>ij</i></sub>:</td><td>a binary variable equal to 1 if BEB <i>j</i> &isin; <i>J</i> is assigned to charging pile <i>i</i> &isin; <i>M</i>, 0 otherwise</td></tr><tr><td><i>y</i><sup><i>i</i></sup><sub><i>jj'</i></sub>:</td><td>a binary variable equal to 1 if both BEBs <i>j</i> &isin; <i>J</i> and <i>j'</i> &isin; <i>J</i>{<i>j</i>}</td></tr></tbody></table>

The complete model is provided in (1)–(15):

$$ \min \sum_{j \in \mathcal{J}} \sum_{b \in \mathcal{B}} c \cdot \tau_b \cdot z_{jb} + \sum_{j \in \mathcal{J}} \lambda \cdot |H_j - \bar{H}_j| \quad (1) $$
Subject to:

$$ \sum_{i \in \mathcal{M}} x_{i,j} \leq 1 \quad \forall j \in \mathcal{J} \qquad (2) $$

$$ H_j \geq l_j \quad \forall j \in \mathcal{J} \qquad (3) $$

$$ H_j = a_j + \sum_{b \in \mathcal{B}} b \cdot z_{jb} \quad \forall j \in \mathcal{J} \qquad (4) $$

$$ x_{ij} + x_{ij'} \geq 2 - L(1 - y_{jj'}^i) \quad \forall i \in \mathcal{M}, \quad \forall j, j' \in \mathcal{J}, \quad j \neq j' \qquad (5) $$

$$ \sum_{i \in \mathcal{M}} (y_{jj'}^i + y_{j'j}^i) \leq 1 \quad \forall j, j' \in \mathcal{J}, \quad j \neq j' \qquad (6) $$

$$ S_j \geq C_{j'} - L(1 - \sum_{i \in \mathcal{M}} y_{jj'}^i) \quad \forall j, j' \in \mathcal{J}, \quad j \neq j' \qquad (7) $$

$$ C_j = p_j + S_j \quad \forall j \in \mathcal{J} \qquad (8) $$

$$ p_j = \sum_{b \in \mathcal{B}} \tau_b \cdot z_{jb} \quad \forall j \in \mathcal{J} \qquad (9) $$

$$ \sum_{b \in \mathcal{B}} z_{jb} = \sum_{i \in \mathcal{M}} x_{i,j} \quad \forall j \in \mathcal{J} \qquad (10) $$

$$ \sum_{b \in \mathcal{B}} z_{jb} \leq 1 \quad \forall j \in \mathcal{J} \qquad (11) $$

$$ C_j \leq d_j \quad \forall j \in \mathcal{J} \qquad (12) $$

$$ S_j > r_j \quad \forall j \in \mathcal{J} \qquad (13) $$

$$ z_{jb}, x_{ij}, y_{jj'}^i \in \{0, 1\} \quad \forall i \in \mathcal{M}, \quad \forall j, j' \in \mathcal{J}, \quad \forall b \in \mathcal{B}, \quad j \neq j' \qquad (14) $$

$$ s_j, c_j, p_j \in \mathbb{Z}^+ \quad \forall j \in \mathcal{J} \qquad (15) $$

Formula (1) is to minimize the total charging cost. Constraint (2) denotes that each BEB can only be assigned to a certain charging pile. Constraint (3) ensures that the SOC of BEB $j \in \mathcal{J}$ after charging activity is not less than the power required for BEB $j \in \mathcal{J}$ to complete a day's operation. Constraint (4) calculates the SOC of the battery after charging activity. Constraints (5)-(6) define $y_{jj'}^i$, which means that if both buses $j \in \mathcal{J}$ and $j' \in \mathcal{J}$ are charged on the same charging pile $i \in \mathcal{M}$, bus $j$ is charged before $j'$. Constraints (7)-(9) calculate the charging start time $S_j$, charging completion time $C_j$, as well as charging time $p_j$ of each BEB $j \in \mathcal{J}$. Constraints (10)-(11) guarantee that each BEB can only be charged to a certain level. Constraint (12)-(13) express the constraints of charging start time and completion time. Constraints (14)-(15) give the value range of decision variables.
# 4 Case study

For demonstrating the effectiveness of the proposed mixed integer linear programming, we apply it to solve a case study, i.e., the transit sub-network in the city of Shanghai, China.

## 4.1 Sub-network description and data preparation

We select a certain bus sub-network in the Shanghai area for analysis. This bus sub-network includes one charging depot and 6 bus lines. For ease of expression, bus lines are defined Line1 to Line6, and all bus lines are loop lines. The bus departs from a terminal station and returns to the starting point after a round detour. The bus sub-network is equipped with BYD K9 BEBs. This type of BEB has a cruising range of up to 350 kilometers, and the battery can be reused more than 4000 times.

In this bus sub-network, the bus company arranges the number of buses according to the length of each line. In the same bus route, the time interval between adjacent flights is 5 minutes. The travel time between two bus stops is 5 minutes. In the same bus, the interval between the arrival time of the previous flight and the start time of the next flight is 20 minutes. The real data is shown in Table 2:

<table><caption>**Table 2.** Basic information of each bus line</caption><thead><tr><th>Bus line</th><th>Bus stops</th><th>Terminal</th><th>Mileage</th><th>Number of BEBs</th><th>Number of tasks per BEB</th></tr></thead><tbody><tr><td>Line 1</td><td>11</td><td>2</td><td>16.9 km</td><td>17</td><td>11</td></tr><tr><td>Line 2</td><td>14</td><td>3</td><td>22.1 km</td><td>21</td><td>9</td></tr><tr><td>Line 3</td><td>12</td><td>2</td><td>18.2 km</td><td>18</td><td>10</td></tr><tr><td>Line 4</td><td>11</td><td>1</td><td>15.6 km</td><td>16</td><td>12</td></tr><tr><td>Line 5</td><td>9</td><td>2</td><td>14.3 km</td><td>15</td><td>13</td></tr><tr><td>Line 6</td><td>9</td><td>2</td><td>14.3 km</td><td>15</td><td>13</td></tr></tbody></table>

Table 2 shows the basic operation information of buses on different lines. For example, on bus line 1, there are 11 bus stops and two terminal stations, the total length is 16.9km. There are 17 buses operating together on this bus Line, each bus needs to perform 11 flights of transportation tasks, and the daily mileage is 185.9km.

## 4.2 Parameter setting and numerical experiment

Assigning values to the involved parameters according to the actual operating conditions of the BEB. In order to protect the battery of the BEB, the bus will set a minimum SOC requirement when it leaves the factory, the general setting value is 20%, so we set $\bar{a}_j = 20$; We set the minimum SOC based on the average
daily mileage of the BEB. Through calculation, after the charging activity, the minimum SOC of the BEBs of line 1 to line 6 are set to 75%, 78%, 77%, 78%, 78%, and 76%, respectively. According to the physical properties of the battery, when the SOC reaches 90%, the battery loss is minimal, so it is the optimal SOC. The rated power of all charging piles in this charging depot is 60kw, and the battery capacity of the BEB is 600Ah.

The charging depot serves 102 BEBs, and there are 30 charging piles in common. BEB earliest start time is 5:30, the latest end time is 22:35. For ease of description, we let 5:30 as the starting point discretize one day into 288 time intervals, with every five minutes as an interval. The proposed model was programmed in Matlab R2018a and solved by using the commercial solver CPLEX 12.4. All numerical experiments were run on a Surface book with 8 GB of RAM and 4.0 GHz of CPU under a Windows 10 environment.

<table><caption>**Table 3.** Numerical experiment results</caption><thead><tr><th>Line</th><th>a<sub>j</sub>(%)</th><th>p<sub>j</sub>(h)</th><th>H<sub>j</sub>(%)</th><th>τ<sub>b</sub> · z<sub>jb</sub></th><th>λ · |H<sub>j</sub> - H&#x0303;<sub>j</sub>|</th><th>obj</th></tr></thead><tbody><tr><td>Line 1</td><td>25%</td><td>2.190</td><td>86%</td><td>131.40</td><td>136</td><td>2369.80</td></tr><tr><td>Line 2</td><td>27%</td><td>2.088</td><td>85%</td><td>125.28</td><td>210</td><td>2840.88</td></tr><tr><td>Line 3</td><td>30%</td><td>2.052</td><td>87%</td><td>123.12</td><td>108</td><td>2324.16</td></tr><tr><td>Line 4</td><td>25%</td><td>2.124</td><td>84%</td><td>127.44</td><td>192</td><td>2231.04</td></tr><tr><td>Line 5</td><td>36%</td><td>2.160</td><td>86%</td><td>129.60</td><td>120</td><td>2064.00</td></tr><tr><td>Line 6</td><td>27%</td><td>2,160</td><td>87%</td><td>129.60</td><td>90</td><td>2034.00</td></tr><tr><td>Total</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>13863.88</td></tr></tbody></table>

The problem is solved in 13 minutes. The results are shown in Table 3. Since the BEBs on the same route have the same transportation tasks and mileage, the charging quantity and charging time after the decision is the same. The total cost of charging for the bus sub-network is 13,863.88 RMB, which is 4.35% lower than the average daily charging cost before the decision. At present, bus companies do not take into account the battery loss cost when calculating the charging cost. Therefore, the true ratio is higher than 4.35%.

# 5 Conclusion

In this work, we study a BEB charging scheduling model with a controllable task completion degree. This model combines the physical properties of the power battery, taking into account the impact of overcharge and over-discharge on battery loss, and incorporates the cost of battery loss into the model's minimization goal. In addition, the applicability of the model is verified by numerical experiments. However, the current solution method consumes a long calculation time, and it is even more unsolvable for large-scale multi-network problems. Therefore, our next step is to develop efficient algorithms for this problem to solve large-scale problems.
References

1. Ibarra-Rojas, O. J., Delgado, F., Giesen, R., and Muñoz, J. C.: Planning, operation, and control of bus transport systems: A literature review. Transportation Research Part B **77**, 38–75 (2015)

2. Mahmoud, M., Garnett, R., Ferguson, M., and Kanaroglou, P.: Electric buses: A review of alternative powertrains. Renewable and Sustainable Energy Reviews **62**, 673–684 (2016)

3. Lajunen, A.: Energy consumption and cost-benefit analysis of hybrid and electric city buses. Transportation Research Part C: Emerging Technologies **38**, 1–15 (2014)

4. Nurhadi, L., Borén, S., and Ny, H.: A Sensitivity Analysis of Total Cost of Ownership for Electric Public Bus Transport Systems in Swedish Medium Sized Cities. Transportation Research Procedia **3**, 818–827 (2014)

5. Liu, Z., and Song, Z.: Robust planning of dynamic wireless charging infrastructure for BEBs. Transportation Research Part C: Emerging Technologies **83**, 77–103 (2017)

6. Grande, L. S. A., Yahyaoui, I., and Gómez, S. A.: Energetic, economic and environmental viability of off-grid PV-BESS for charging electric vehicles: Case study of Spain. Sustainable Cities and Society **37**, 519–529 (2018)

7. Wesseling, J. H.: Explaining variance in national electric vehicle policies. Environmental Innovation and Societal Transitions **21**, 28–38 (2016)

8. Hao, H., Ou, X., Du, J., Wang, H., and Ouyang, M.: China's electric vehicle subsidy scheme: Rationale and impacts. Energy Policy **73**, 722–732 (2014)

9. Rogge, M., van der Hurk, E., Larsen, A., and Sauer, D. U.: Electric bus fleet size and mix problem with optimization of charging infrastructure. Applied Energy **211**, 282–295 (2018)

10. Abdelwahed, A., van den Berg, P. L., Brandt, T., Collins, J., and Ketter, W.: Evaluating and Optimizing Opportunity Fast-Charging Schedules in Transit Battery Electric Bus Networks. Transportation Science(2020). https://doi.org/10.1287/trsc.2020.0982

11. Liu, M., Zheng, F., Chu, C., and Xu, Y.: Single-machine scheduling with past-sequence-dependent delivery times and release times. Information Processing Letters **112**(21), 835–838 (2012)

12. Zheng, F., Cheng, Y., Liu, M., and Xu, Y.: Online interval scheduling on a single machine with finite lookahead. Computers & Operations Research **40**(1), 180–191 (2013)

13. Karhi, S., and Shabtay, D.: Single machine scheduling to minimise resource consumption cost with a bound on scheduling plus due date assignment penalties. International Journal of Production Research **56**(9), 3080–3096 (2017)

14. Aschauer, A., Roetzer, F., Steinboeck, A., and Kugi, A.: Efficient scheduling of a stochastic no-wait job shop with controllable processing times. Expert Systems with Applications (2020). https://doi.org/10.1016/j.eswa.2020.113879

15. Kang, Q., Wang, J., Zhou, M., and Ammari, A. C.: Centralized Charging Strategy and Scheduling Algorithm for Electric Vehicles Under a Battery Swapping Scenario. IEEE Transactions on Intelligent Transportation Systems **17**(3), 659–669 (2016)

16. He, Y., Liu, Z., and Song, Z.: Optimal charging scheduling and management for a fast-charging BEB system. Transportation Research Part E: Logistics and Transportation Review (2020). https://doi.org/10.1016/j.tre.2020.102056