A bi-level optimization framework for charging station design problem considering heterogeneous charging modes

Abstract

Purpose

The purpose of this paper is to optimize the design of charging station deployed at the terminal station for electric transit, with explicit consideration of heterogenous charging modes.

Design/methodology/approach

The authors proposed a bi-level model to optimize the decision-making at both tactical and operational levels simultaneously. Specifically, at the operational level (i.e. lower level), the service schedule and recharging plan of electric buses are optimized under specific design of charging station. The objective of lower-level model is to minimize total daily operational cost. This model is solved by a tailored column generation-based heuristic algorithm. At the tactical level (i.e. upper level), the design of charging station is optimized based upon the results obtained at the lower level. A tabu search algorithm is proposed subsequently to solve the upper-level model.

Findings

This study conducted numerical cases to validate the applicability of the proposed model. Some managerial insights stemmed from numerical case studies are revealed and discussed, which can help transit agencies design charging station scientifically.

Originality/value

The joint consideration of heterogeneous charging modes in charging station would further lower the operational cost of electric transit and speed up the market penetration of battery electric buses.

Citation

Zhang, L., Zeng, Z. and Gao, K. (2022), "A bi-level optimization framework for charging station design problem considering heterogeneous charging modes", Journal of Intelligent and Connected Vehicles, Vol. 5 No. 1, pp. 8-16. https://doi.org/10.1108/JICV-07-2021-0009

1. Introduction

Electric transit is considered as the key to the world’s clean transport future due to its high energy efficiency, zero emissions (Lajunen, 2014; Jin et al., 2015; Xu et al., 2021; Qu et al., 2020; Zhang et al., 2020; Zhang et al., 2021) and shareability (Gao et al., 2021; Bie et al., 2020; Meng and Qu, 2013; Wang et al., 2018). Compared with diesel buses, battery electric buses (BEBs) are able to improve energy efficiency by 50% and reduce greenhouse gas emissions by 98.36% (Mahmoud et al., 2016). During the past decade, the public transit is electrified step by step. For example, in the USA, the share of BEBs in the bus market increased rapidly from 2% in 2007 to nearly 20% in 2015 (Neff and Dickens, 2016); in Europe, the percentage of BEBs on the sales volumes of city buses is up to 10% by 2019, and this number rises up to around 20% in 2020. Undoubtedly, transit electrification is becoming an unstoppable trend.

Compared with diesel buses, the driving characteristics and refueling manner of BEBs are distinct. Specifically, BEBs generally have a much shorter operational range than buses powered by other energy sources, resulting in users’ “range anxiety” (Lebeau et al., 2016; Masmoudi et al., 2018; Qin et al., 2016; Li et al., 2019). To ensure normal operations, the consumed electricity must be replenished by either battery swapping or battery recharging (Li, 2013; Huang and Zhou, 2015; Wang et al., 2017; Tang et al., 2019; Liu and Ceder, 2020; Rinaldi et al., 2020). Unfortunately, instead of mitigating this disadvantage, lack of sufficient charging facilities further aggravates it (An, 2020). However, if sufficient charging facilities are deployed, it may cause severe budget burden for transit system. Meanwhile, charging modes also affect the charging efficiency as well as the infrastructure installation cost. Specifically, compared with normal charging, the fleet size can be reduced significantly through improved charging efficiency by adaptation of fast charging mode, but it also causes higher infrastructure installation cost. Therefore, how to design the charging station, trading off charging availability, charging efficiency and limited budget become an important issue in transit electrification. To this end, we aim at studying the optimal design of charging station deployed at the terminal station for electric transit in this paper. To be specific, we propose a bi-level model, where the lower-level model optimizes the scheduling of BEBs given the design of charging station, including the number of charging facilities of different charging modes (i.e. fast charging and normal charging); the upper-level model optimizes the design of charging station with explicit consideration of multiple charging modes. In the bi-level approach, the lower-level problem, i.e. optimal scheduling of BEBs, is the key and difficult part of the work. Therefore, we next present the relevant studies in the realm of vehicle scheduling.

Bus scheduling problem consists of assigning buses to serve a series of timetabled trips with the objective of minimizing fleet size and/or operational costs. It is an extension of the well-known vehicle scheduling problem (VSP), which has been extensively studied in the literature (Marković et al., 2015; Schöbel, 2017). Generally speaking, VSP can be categorized into two groups: the single-depot VSP (SDVSP) (Paixão and Branco, 1987; Freling et al., 2001; Kang et al., 2019) and the multiple-depot VSP (MDVSP) (Dell'Amico et al., 1993; Kliewer et al., 2006). Over the years, many varieties and extensions of VSP have been proposed to incorporate the real-world constraints and conditions, including VSP with multiple vehicle types (Ceder, 2011), VSP with route constraints (VSP-RC) (Bunte and Kliewer, 2009), the alternative fuel VSP (AF-VSP) (Li, 2013; Adler, 2014) and electric VSP (E-VSP) (Wen et al., 2016). Among these varieties, VSP-RC, AF-VSP and E-VSP are strongly motivated by electric vehicles. To accounting for the specifics of electric vehicles, route duration or route distance is constrained in VSP-RC (Haghani and Banihashemi, 2002). If vehicles are allowed to be refueled at given recharging stations to prolong the total distance, that is AF-VSP. However, traditional AF-VSP only considers full charging and the charging time is set as fixed. Specifically, the vehicle’s fuel level is set to be full after visiting any recharging stations. For example, Li (2013) incorporated vehicle waiting time at charging stations into the model, and the charging time was simplified as fixed by considering battery swapping. Later, E-VSP was proposed, where partial charging was allowed and the charging time was usually assumed to be a linear function of the charged amount. Unfortunately, whereas much efforts have been made to deal with BEB scheduling, very little attention has been dedicated to explicitly modeling the design of charging station for electric transit, with full consideration of multiple charging modes. It will cause unforeseen operational cost when promoting transit electrification.

In light of the above literature, this paper would employ the latest study in electric vehicle scheduling to study the optimal design of charging station, and the bi-level solution approach is adopted to fix this problem. Numerical case studies were conducted to validate the applicability of the proposed model. It reveals that it is a cost-efficient choice to deploy sufficient charging facilities at the terminal station as the unit cost of charging facilities per day is much lower than that of BEBs.

Our key contributions from a theoretical and practical point of view can be summarized as follows:

• We are, to our best knowledge, the first to formulate and solve charging station design problem with explicit consideration of multiple charging modes and their corresponding effect on battery capacity fading.

• A number of managerial insights stemmed from the numerical case study are outlined, which can serve as a solid theoretical foundation for more cost-efficient charging station design.

The rest of this paper is organized as follows. Section 2 presents the problem formulation, i.e. a bi-level model. Section 3 elaborates the proposed solution approach for solving the problem. The numerical cases are conducted in Section 4. Conclusions are summarized in Section 5.

2. Mixed charging station design problem

2.1 Problem description

In this section, a single-terminal transit network is considered to define the optimization problem of charging station design, as depicted in Figure 1. BEBs depart from the terminal station to operate a sequence of scheduled round-trips, denoted as set V. For simplicity, we refer to the round-trip as trip for short from now. Charging facilities in mode q ∈ Q = {q₁, q₂} are deployed at terminal station with limited number C_q, where q₁ indicates normal charging mode and q₂ indicates fast charging mode. For each trip i(∈ V), the departure time s_i, travel time e_i and the consumption of battery level relative to battery capacity, m_i are predefined and deterministic. The objective of this problem is to minimize the total cost of transit agency, including bus acquisition cost, charging fee, maintenance cost of BEB fleet and the cost incurred by the deployment of charging facilities. Therefore, the operators shall make decisions at both tactical and operational levels. To be specific, at the tactical level, the number of charging facilities in each type deployed at the terminal station should be optimized and the vector of decision variables at this level is denoted by C ≜ {C_q|q ∈ Q}. At the operational level, the operators shall make decisions on: how to assign BEBs to serve a series of trips satisfying the minimal battery level constraint and how to optimize recharging schedule considering limited charging facilities (i.e. given specific charging station design). The corresponding decision variables at this level (i.e. service sequence and charging strategy) are denoted by vector X. Notations used in this paper are summarized in Appendix.

2.2 Lower-level problem: optimal scheduling of battery electric bus fleet

The objective of the lower-level model is to minimize total operational cost, including bus acquisition cost, charging fee and maintenance cost within one day, where the maintenance cost is mainly incurred by battery degradation. It is worth to note that the total charging fee is constant in our model, as it is related to the predefined trip service, which is fixed and independent of BEB schedule. Therefore, the objective function is simplified as the sum of bus acquisition cost and maintenance cost. The vector of decision variables at the operational level, X, can be defined as X = {δ_ij, μ_itq, ϕ_itq|i ∈ V, t ∈ T, q ∈ Q}, where:

δ_ij ∈ {0, 1}: set to one if BEB serves trips i and j consecutively, where trip i begins earlier than trip j; and to zero otherwise, i ∈ V ∪ O, j ∈ V ∪ D, i ≠ j. Here O denotes a virtual trip that every bus must serve before its first real trip, and D denotes another virtual trip that each BEB serves after completing the last real trip of a day and being fully charged. The two notations are defined for the convenience of modeling work. The virtual trips’ travel times and electricity consumption are all set to zero:

μ_itq ∈ {0, 1}: set to one if BEB begins to charge with charging mode q at time step t after finishing trip i and before serving the next trip, and to zero otherwise, i ∈ V, t ∈ T, q ∈ Q.

ϕ_itq ∈ {0, 1}: set to one if BEB is under charging with charging mode q at time step t after finishing trip i and before serving the next trip, and to zero otherwise, i ∈ V, t ∈ T, q ∈ Q.

In this model, we make the following assumptions:

• Assumption 1: The time is discretized with the unit time as 10 min. The time for full charge in mode q₁ (i.e. normal charging) and mode q₂ (i.e. fast charging) are 2 h (i.e. 12 time steps) and 10 min (i.e. 1 time step), respectively.

• Assumption 2: BEBs are fully charged when departing from the original depot, and are charged back to full when returning to destination depot.

• Assumption 3: After finishing one trip, BEB can either be charged for one time and charged to full or serve the next trip consecutively without any charging activity.

The lower-level model [P1] can be formulated as:

(1a) minXJ[P1](Cq|q∈Q)=v˜⋅∑i∈VδOi+∑i∈V∑t∈T∑q∈Qμitqdq(SOCi,1)

Subject to:

(1b) ∑i∈V∪Oδij=1,   ∀j∈V

(1c) ∑j∈V∪Dδij−∑j∈V∪Oδji=0,   ∀i∈V

(1d) ∑t∈T∑q∈Qμitq≤1,   ∀i∈V

(1e) (1−∑t∈T∑q∈Qμitq)M+∑t∈T∑q∈Qμitq⋅t≥si+ei,   ∀i∈V 

(1f) ∑i∈Vϕitq≤Cq,   ∀t∈T,q∈Q

(1g) −(1−μitq1)M+F(SOCi,q1)≤∑t′=tt+F(SOCi,q1)−1ϕit′q1≤(1−μitq1)M+F(SOCi,q1), ∀t∈T,i∈V

(1h) −(1−μitq2)M+F(SOCi,q2)≤ϕitq2≤(1−μitq2)M+F(SOCi,q2), ∀t∈T,i∈V

(1i) 1−mi−(1−δOi)M≤SOCi≤1−mi+(1−δOi)M,   ∀i∈V

(1j) SOCi≥lb,   ∀i∈V

(1k) SOCj≤SOCi−mj+(1−δij)M+M∑t∈T∑q∈Qμitq,   ∀i,j∈V

(1l) SOCj≥SOCi−mj−(1−δij)M−M∑t∈T∑q∈Qμitq,   ∀i,j∈V

(1m) SOCj≤1−mj+(1−δij)M+(1−∑t∈T∑q∈Qμitq)M,   ∀i,j∈V

(1n) SOCj≥1−mj−(1−δij)M−(1−∑t∈T∑q∈Qμitq)M,   ∀i,j∈V

(1o) dq(SOCi,1)=2×ξ(SOCi,1)×(1−SOCi)χWγ(q),   ∀i∈V,q∈Q

(1p) sj≥si+ei−(1−δij)M−M∑t∈T∑q∈Qμitq,   ∀i,j∈V

(1q) sj≥∑t∈Tμitq1⋅t+F(SOCi,q1)−(1−δij)M−(1−∑t∈Tμitq1)M,   ∀i,j∈V

(1r) sj≥∑t∈Tμitq2⋅t+F(SOCi,q2)−(1−δij)M−(1−∑t∈Tμitq2)M,   ∀i,j∈V

(1s) ∑t∈T∑q∈Qμitq≤1+M(1−δiD),   ∀i∈V

(1t) ∑t∈T∑q∈Qμitq≥1−M(1−δiD),   ∀i∈V

In the above model, the objective function (1a) is to minimize the total operational cost over the operation hours of one day, including bus acquisition cost and maintenance cost, where v˜ denotes the unit acquisition cost of BEB per day, and d_q indicates the cost incurred by battery degradation with the state of charge (SOC) from SOC_i (i.e. the SOC of BEB after just finishing trip i) to 100% under charging mode q. Constraints (1b) guarantee that each trip is served exactly once. Constraints (1c) represent covering and flow conservation. Constraints (1d) state that after trip i, BEB may start charging in a certain time step with a certain charging mode. Constraints (1e) ensure that the starting time of charging activity after trip i should be no earlier than the end time of trip i, where M is a sufficiently large number. Constraints (1f) guarantee the number of charging facilities used in each time step cannot exceed its capacity. Constraints (1g) ((1h)) state that F(SOC_i, q₁) (F(SOC_i, q₂)) time steps are occupied if normal (fast) charging operation is applied. Here F(SOC_i, q) indicates the number of time steps required to charge battery from SOC_i to full under charging mode q; F(SOC_i, q₂) is always equal to 1 for all SOC_i ∈ (0, 1) due to assumption 1. Constraints (1i) indicate that BEB is fully charged when it departs from the original depot O, where m_i means the consumption of battery level relative to battery capacity of trip i. Constraints (1j) guarantee that SOC should be no smaller than a predefined lower bound lb to reduce range anxiety. Constraints (1k-n) record the dynamic SOC of BEBs if δ_ij = 1. Constraints (1o) define the function d_q, where W indicates the battery acquisition cost; χ is the end-of-life related parameter. The term ξ(SOC_i, 1) denotes the corresponding battery capacity fading rate, borrowed from Lam and Bauer (2012); γ(q) refers to charging-mode related coefficient, where the coefficient of fast charging mode is larger than that of normal charging mode, i.e. γ(q₁) < γ(q₂). Constraints (1p-r) state the stating time of trip j should be no earlier than the ending time of trip i if δ_ij = 1 and ∑t∈T∑q∈Qμitq=0; and the stating time of trip j should be no earlier than the ending time of charging operation applied after trip i if δ_ij = 1 and ∑t∈T∑q∈Qμitq=1. Constraints (1s) and (1t) indicate that buses are charged back to full when returning to destination depot.

We next present the exact mathematical form of function ξ(SOC_i, 1):

(2a) ξ(SoCi,1)=γ1SoCi,dev⋅eγ2SoCi,avg+γ≤eγ4SoCi,dev

where

(2b) SoCi,avg=1+SoCi 2,

(2c) SoCi,dev=1−SoCi 2

Here the coefficients γ₁, γ₂, γ₃ and γ₄ are constant model parameters.

In this paper, we consider nonlinear charging profile, where SOC increases nonlinearly with respect to the charging time, as presented in Figure 2. Specifically, the battery would undergo two phases, namely, CC phase and CV phase. In the first phase (i.e. CC phase), the charging current is held constant and hence the SOC increases linearly with time until the battery’s terminal voltage reaches the threshold. After that, the terminal voltage keeps constant (i.e. CV phase), thus resulting in the current decreasing exponentially and the growth rate of SOC decreasing with respect to the charging time. The pattern of SOC with respect to the charging time under normal charging mode can be approximated by piecewise linear function:

(3) SOC(t,q1)={0.8t   t∈[0,1)0.8+0.2(t−1)   t∈[1,2]

where t is in the unit of hour. Therefore, the number of time steps required to charge battery from SOC_i to full under normal charging mode can be calculated as follows:

(4) F(SOCi,q1)={30(1−SOCi)   if SOCi>0.86+152(0.8−SOCi)   if SOCi≤0.8

Here function [a] returns the smallest integer that is no smaller than a.

2.3 Upper-level problem: optimal design of charging station

The upper-level model can be formulated as follows:

(5a) minCJ[P2] =∑q∈QAqCq+J[P1](X,C)

Subject to:

(5b) X=g(C)

where A_q indicates the unit installation cost of charging facility in mode q amortized to one day, measured in $/day; g(·) denotes the optimal lower-level solution for X under a given design of charging station C, which is found by solving model [P1]. J_[P1] (X, C) indicates the daily operational cost under tactical decision C and operational decision X, which is consistent with the objective function of model [P1].

3. Solution approach

3.1 Column generation-based heuristic algorithm for solving lower-level model

To solve model [P1], we next reformulate it as an equivalent set partitioning model, which can be solved by column generation (CG). To this end, we introduce trip chain firstly. A trip chain of BEB includes the service sequence, i.e. a series of trips sorted in an ascending order in terms of their departure time, and the charging strategy between any two consecutive trips. A trip chain is feasible, if i) all the covered trips can be served on time; and ii) battery level is sufficient to support all the covered trips given that BEB can be charged at terminal station if both time and charging facilities permit. Given the definition of trip chain, the equivalent set partitioning model is presented as follows:

(6a) minλrJ[P3]=∑r∈Rcrλr

Subject to:

(6b) ∑r∈RAirλr=1,   ∀i∈V

(6c) ∑r∈RUtqrλr≤Cq,   ∀t∈T, q∈Q

(6d) λr∈{0,1},   ∀r∈R

In the above formulation, we denote R as the set of all feasible trip chains within one day, and c_r denotes the cost of trip chain r ∈ R, including the unit bus acquisition cost and maintenance cost along the trip chain. For each feasible trip chain r ∈ R, we define a binary variable λ_r, which equals to one if and only if trip chain r is selected; and to zero otherwise. Objective function (6a) minimizes the total cost over the operation hours of one day. Constraints (6 b) ensure that each trip i ∈ V is served exactly once in the solution, where Air is set to one if trip i is covered in trip chain r and to zero otherwise. Constraints (6c) guarantee that the charging facilities used in each time step are within the limited capacity C_q; and Utqr is set to one if BEB is under charging with charging mode q at time step t in trip chain r and to zero otherwise. Constraints (6d) define the domain of decision variable λ_r, r ∈ R.

We next describe the CG procedure to solve the linear relaxation of set partitioning model, defined as model [P4], i.e. the binary constraint of λ_r is relaxed and replaced by constraints:

(7) λr≥0,    ∀r∈R

We now describe CG procedure to solve model [P4]. The description is kept for short in the interest of brevity because the algorithm is only a standard practice of the CG algorithm. For more details on the theory of CG, please refer to Merle et al. (1999). Briefly, model [P4] is solved by repeatedly solving (i) a restricted master problem with a subset of trip chains and (ii) a pricing subproblem to generate new trip chains with negative reduced costs. The restricted master problem is solved by commercial solvers directly (e.g. Cplex, Gurobi). The pricing problem is shortest path problem with resource constraint and solved by label-correcting algorithm with fully considering special problem aspects: minimal battery level and battery recharging. Each state is represented by a label, (k, b), where k is the last reached node and b represents the corresponding battery level. The cost of label (k, b) is c¯(k,b), representing the accumulative cost from original depot O. Now consider that both label (k, b) and label ( k,b¯), label (k, b) dominates ( k,b¯) if (1) c¯(k,b)≤c¯(k,b¯), and (2) b≥b¯, where at least one of above inequalities is strict. The label extension and dominance rule are placed into a framework of the general label-correcting algorithm to solve the pricing problem.

To generate feasible integer solution, we next propose a heuristic algorithm based upon the CG procedure to obtain near-optimal integer solutions. In the proposed heuristic algorithm, the inner procedure is the CG procedure; the outer procedure is the selection strategies used to obtain an integer solution.

Firstly, we modify constraint (6c) in model [P3] as:

(8) ∑r∈R′Utqrλr≤Ctq,   ∀t∈T, q∈Q

Initially, C_tq is constant and equal to C_q. Then the available number of charging facilities at each time step may decrease as the outer procedure proceeds in our heuristic algorithm. To be specific, every time the inner CG procedure stops, we select the trip chain (i.e. column) with the largest value of the decision variables λ_r. Then update C_tq and V for a new iteration of the above process:

• if BEB is charged in time step t under charging mode q according to the selected trip chain, update C_tq ← C_tq – 1;

• if trip i is served in the selected trip chain, update V ← V/i;

The algorithm terminates when all the trips are served.

3.2. A tabu-search method for solving upper-level model

The first step of the tabu search is to initialize a feasible initial solution to model [P2], denoted by X0≡{Cq10, Cq20}. Then define a move as a change from a feasible solution X to a new feasible solution, where the change can be one of the following: (i) Cq1→Cq1−1 or Cq1→Cq1+1; and (ii) Cq2→Cq2−1 or Cq2→Cq2+1. At each move, the CG-based heuristic algorithm presented in Section 3.1 is executed to find the BEB utilization schedule and recharging plan. The total cost J_[P2] is then calculated. Define the neighborhood of X, N(X), as the set of feasible solutions that can be obtained by making one move from X. Further define the tabu list, TL, as the list of inverse moves of those most recent moves performed. The maximum length of tabu list is denoted as tabu_size. In each iteration, a move is made according to one of the following two rules:

• If no move in N(X) can produce a lower total cost as compared to the best solution so far, set the current move to the one in N(X)\TL that produces the lowest total cost. Following this rule, a move is made even if it produces a higher cost than the best solution so far.

• If a move in N(X) ∩ TL produces a lower total cost than the best solution so far, set the current move to the lowest-cost move in N(X).

The tabu list TL is updated after each iteration. It is used to prevent the algorithm from returning to a solution attained in a previous iteration. The first rule finds the best neighboring solution that is generated not from any move in the tabu list. However, if a move in the tabu list can yield a better solution than the best one so far, that move is still selected according to the second rule. The algorithm ends when no better solution is found after max_num_tb consecutive iterations.

4. Numerical cases

To validate our model, in this section we focus on a case study with the terminal denoted as terminal station A. Departing from terminal station A, five yet-to-be-electrified lines are studied. The lengths of the five lines are 11 km, 11.5 km, 12.6 km, 19.3 km and 16.8 km respectively. Their travel durations (terminal to terminal) are 80 min, 90 min, 110 min, 150minand 130 min respectively. The timetables for these five lines are shown in Table 1. The technical parameters needed for this paper are obtained from Yutong ZK6850BEVG53, as specified in Table 2. Specifically, Yutong ZK6850BEVG53 is a kind of medium BEB, with vehicle length as 8.5 meters. Its price is 0.65 million RMB, and this cost covers the maintenance of vehicles over 8 years. The battery capacity is 162 kWh with unit price as 1130 RMB/kWh on average. Therefore, the price of battery packs is about:

(9) 1130×162×ς=28008.2 $

where ς denotes the exchange rate of RMB to US dollar ($/RMB) and equals 0.153 in this paper.[1] Hence, the price of battery packs, W, is approximated as 28000 $. The price of BEB without battery is:

(10) 650000×ξ−28000=71450 $

The service life of bus (without batteries) is set as 12 years (Lajunen, 2014). Then, the unit acquisition cost of bus (without battery) per day is:

(11) 71450÷12÷365=16.31 $

Similarly, the unit acquisition cost of bus (without battery) per day, v˜, is approximated as 16.5 $in this paper.

We firstly examine the scenario where only one kind of charging facilities is allowed to install at the terminal station. Without of loss of generality, we consider normal charging mode firstly and optimize the BEB service and charging schedule under a range of charging station capacity: Cq1∈[1,21], as presented in Figure 3. Figure 3 shows that the optimal operational cost (the solid curve with triangle markers) decreases as Cq1 increases, until it reaches a threshold of 17. This threshold represents the maximum number of normal charging facilities needed for BEBs at terminal station A; i.e. any additional charging facilities would be redundant, and the optimal total cost would stay the same.

The asterisk-marked solid curve represents the corresponding total cost at the upper level. We note that, the optimal total cost decreases as Cq1 increases, until it reaches to 17. After that, the optimal total cost increases as Cq1 increases. This is because any more charging facilities would be redundant and the optimal operational cost at the lower level would not reduce any more. Therefore, for the studied transit network, it is optimal to deploy 17 charging facilities at the terminal station A if the operators only consider normal charging mode. Further investigation reveals that, as the unit cost of charging facilities per day is relatively low as compared with that of BEBs, it is cost-efficient to deploy the charging facilities as more as needed so that the total cost of transit agency can be saved by reducing fleet size.

We also note that the SoC variation negatively affects battery aging rate: the larger the SoC variation is, the faster the battery degrades. Therefore, to prolong battery life, the operators are encouraged to charge BEBs as frequently as possible, instead of as late as possible. As a trade-off, when the charging facilities are relatively sufficient, the electric buses tend to be charged as frequently as possible, to achieve more cost saving by extending batteries’ lifespan.

We next examine the effect of the number of fast chargers on the optimal cost, as presented in Figure 4. Compared to normal charging, fast charging mode can reduce the fleet size largely due to its high charging efficiency, even though the installation cost of fast charging facilities is much higher than that of normal charging facilities. Therefore, the maximum number of fast chargers required is only 3 with the minimal operational cost at the lower-level as $1.05 × 10³, as shown in Figure 4. The figure also reveals that the minimal total cost at the upper level ($1.14 × 10³) occurs when the number of fast chargers is 3.

When mixed design of charging station is considered, the model reveals that the optimal charging station design is to install 2 fast chargers and 2 normal chargers, where the optimal total cost is $1.12 × 10³. Even though the daily saving brought by mixed design of charging station is minor, i.e. only $20. However, this benefit cannot be overlooked over 10 years or more.

5. Conclusions

In this paper, we present a new mathematical formulation aimed at optimizing the design of charging station deployed at the terminal station for electric transit. To this end, a bi-level model is built with full consideration of the decision-makings at both tactical and operational levels. Specifically, the lower-level model optimizes the scheduling of BEBs given the design of charging station, including the number of charging facilities under different charging mode (i.e. fast charging and normal charging), whereas the upper-level model optimizes the design of charging station given optimized BEB service sequence and charging plan at the lower level.

In the future work we plan to explore more realistic scenarios where the “full-charging” assumption is relaxed, i.e. partial charging among BEBs is allowed and the charging time depends on the amount of energy to be replenished following more realistic non-linear charging profile. Meanwhile, we would also plan to extend the transit network to the one with multiple terminals, explore more efficient solution approach with high quality, instead of using heuristic algorithm; consider agency budget for the installation of charging infrastructure and consider users’ psychological inertia (Gao et al., 2020).

Figures

Figure 1

Single-terminal transit network

Figure 2

Illustration of nonlinear charging profile

Figure 3

Effects of the number of normal chargers on the optimal cost

Figure 4

Effects of the number of fast chargers on the optimal cost

Table 1

Timetables for selected bus lines, departing from terminal station A

Line 1	Line 2	Line 3	Line 4	Line 5
07:00:00	06:10:00	07:00:00	06:20:00	06:40:00
07:20:00	Every 20 min	07:30:00	Every 30 min	07:10:00
07:40:00	09:10:00	08:00:00	18:50:00	07:40:00
Every 20 min	Every 30 min	Every 20 min		Every 10 min
10:40:00	15:10:00	14:20:00		18:20:00
Every 30 min	Every 20 min	14:50:00		18:50:00
16:40:00	19:10:00	15:10:00		19:20:00
Every 20 min		Every 20 min		19:50:00
19:20:00		20:10:00

Table 2

Parameter definitions and values

Parameter	Notation	Value	Unit
Lower bound of battery level	lb	20	%
Unit acquisition cost of an electric bus (without battery) per day	v˜	16.5	$/day
Battery acquisition cost	W	2.8e4	$
Unit cost of a normal charging facility per day	Aq1	5	$/day
Unit cost of a fast charging facility per day	Aq2	30	$/day
Coefficient of battery capacity fading under normal charging mode	γ(q1)	1	–
Coefficient of battery capacity fading under fast charging mode	γ(q2)	2	–
Coefficient for battery degradation model	γ1	−4.09e-4	–
Coefficient for battery degradation model	γ2	−2.167	–
Coefficient for battery degradation model	γ3	1.418e-5	–
Coefficient for battery degradation model	γ4	6.13	–
End-of-life related threshold	χ	0.2	–

Table A1

List of notations

Notation	Description
Sets and Indices
V	Set of trips
T	Set of time steps
R	Set of all feasible trip chains
R'	Subset of feasible trip chains
Q	Set of charging modes
i, j	Trip and node indices
O	Index of a virtual trip before each BEB’s first trip of the day
D	Index of a virtual trip after each BEB’s last charging activity of the day
T	Time step index
R	Trip chain index
Q	Charging mode index
Decision variables
δij ∈{0,1}	Equals one if a BEB serves trips i and j in turn and consecutively, and zero otherwise, i ∈ V ∪{O}, j ∈ V ∪ {D}, i ≠ j
μitq ∈ {0,1}	Equals one if a BEB’s charging activity following trip i ∈ V starts at time step t ∈ T with charging mode q, and zero otherwise
ϕitq ∈{0,1}	Equals one if a BEB is being charged at time step t ∈ T between trip i ∈ V and the next trip it serves with charging mode q, and zero otherwise
Cq	Number of charging facilities in mode q deployed at terminal station
λr ∈ {0, 1}	Equals one if trip chain r ∈ R is selected, and zero otherwise
C	Decision variables at the tactical level
X	Decision variables at the operational level
Parameters and other variables
si	Departure time of trip i
ei	Travel time of trip i
Lb	Minimum battery level to eliminate range anxiety
mi	Battery consumption of trip i
M	A sufficiently large number
v˜	Amortized acquisition and maintenance cost of a BEB per day
q1	Normal charging mode
q2	Fast charging mode
F(SOCi, q)	Number of time steps required from SOCi to full with charging mode q
W	Battery acquisition cost
Aq	Unit cost of a charging facility per day with charging mode q
cr	Cost of trip train r
γ(q)	Coefficient of battery capacity fading under charging mode q
r1,r2,r3,r4	Coefficient for battery degradation model
Χ	End-of-life related threshold
ξ(SOCi,1)	Battery capacity fading rate from SOCi to full
dq (SOCi,1)	Cost incurred by battery capacity fading from SOCi to full under charging mode q
c¯(k,b)	Cost of label (k, b)
Air	Equals one if trip i ∈ V is covered by trip chain r and zero otherwise
Utqr	Equals one if a BEB in trip chain r is on a charger with charging mode q at time step t and zero otherwise
N(X)	Neighborhood of X
TL	Tabu list
Σ	Exchange rate of RMB to US dollar

Note

1 The result may deviate within a small range due to the variation of exchange rate.