# Joint Optimization of Regular Charging Electric Bus Transit Network Schedule and Stationary Charger Deployment considering Partial Charging Policy and Time-of-Use Electricity Prices

Authors: Xinghua Li; Tianzuo Wang; Lingjie Li; Feiyu Feng; Wei Wang; Cheng Cheng
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

Electric buses (EBs) have been implemented worldwide and exhibited great potential for air pollution reduction and traffic noise control. In regular charging scenarios, the deployment of charging facilities and the operational scheduling of the transit system is crucial to bus transit system management. In this paper, we proposed a joint optimization model of regular charging electric bus transit network schedule and stationary charger deployment considering partial charging policy and time-of-use electricity prices. The objective of the model is to minimize the total investment cost of the transit system including the capital and maintenance cost of EBs and chargers, the power consumption cost, and time-related in-service cost. A solving procedure based on the improved adaptive genetic algorithm (AGA) is further designed and a transit network at inner Anting Town, Shanghai, with 8 individual bus routes and 867 daily service trips is adopted for the model validation. The validation results illustrated that the methodology considering the partial charging policy can arrange the charging schedule adaptive to the time-of-use electricity prices. Compared with the benchmark of single line separate scheduling, the proposed model can yield 3 million RMB investment saving by highly utilizing EBs and battery chargers.


---

## Body

## 1. Introduction

With the development of electric powertrain technologies, electric vehicles have been adopted worldwide. This new type of vehicle is environmentally friendly due to its low-level air pollution and noise generation and has been regarded as a potential alternative to conventional diesel automotive [1–6].According to recent research, transit bus system is a major area for electric vehicle adoption. A significant number of public transit routes have been configured with electric buses (EBs) throughout the world. According to Wang et al. [7], over 16000 conventional diesel buses have been replaced by EB in Shenzhen, China, and the usage percentage of EB in its bus transit system has reached 100% at the end of 2017. Similarly, the US Environmental Protection Agency (EPA) has announced that the proportion of EBs in America’s transit bus market has increased rapidly from 2% in 2007 to nearly 20% in 2015. It is also predicted that full application of EB will potentially lead to a 50% decrease in fuel consumption in the foreseeable future [8].Currently, there are mainly four means of EB charging strategies: regular charging, fast charging, battery exchange, and charging lanes [9–12]. Among these charging strategies, regular charging technology is relatively mature and safe and has been widely adopted in the bus transit system [13]. For regular charging scenarios, the deployment of charging facilities is crucial to bus transit system management. On one hand, the construction and operation cost of charging facilities is relatively large, and thus the investment plan has to be strictly considered. On the other hand, the deployment of chargers would influence the bus transit system’s service quality due to the bus recharging process during daily operation [14]. To maintain the bus system’s service quality and minimize the investment cost for charging facilities and EBs, this study would jointly optimize the EB fleet operation schedule and charging facility deployment to reduce the overall investment and achieve high utilization of regular charging chargers and EBs.


## 2. Literature Review

There have been some exploratory studies on the EB vehicle scheduling problem and EB charging infrastructure planning separately.


### 2.1. Literature Review on EB Vehicle Scheduling Problem

EB operation and charging scheduling belongs to the transit vehicle scheduling problem, which refers to the problem of investigating an optimal assignment of trips in a given transit timetable to the bus fleet. Transit management must design feasible and accurate plans for routes running and EBs charging when the EB penetration level is high. To operate the mixed bus fleet, Paul and Yamada [15] proposed a k-greedy algorithm-based approach to maximize the travel distance of the EBs in the bus fleet. Wei et al. [16] introduced a spatial-temporal optimization model to schedule the mixed bus fleet and identify the optimal infrastructure deployment strategies of the bus system.The existing research on the operation scheduling of the 100% EB fleet can be categorized according to the battery charging strategies outlined in the background. Jang et al. [17, 18] optimized the locations of charging lanes and the battery size to minimize the total social cost for a single bus line. Several studies addressed the operation of EB under battery exchange mode under the predetermined charging time and full-charging assumption [19–21]. Wang et al. [8] developed a framework to optimize the location and capacity of the charging stations while at the same time generating EB recharging schedules under fast-charging rules. Liu and Ceder [12] proposed two different mathematical programming models and solution methods to solve the scheduling problem of fast-charging EBs with the adoption of a partial charging policy.Compared with charging lanes, battery exchange, and fast charging, regular charging mode is the most adopted charging strategy but requires longer charging time and is more complicated in terms of scheduling operation and charging plans. The bus scheduling problem for regular charging mode was generally investigated by Li [22] in consideration of charging stations with limited capacity. Ke et al. [23] proposed an EB operation and battery charging simulation framework to minimize EB transportation system construction cost in Penghu, Taiwan. Considering charging and dispatching policies, Jiang et al. [24] developed a neighborhood search based heuristic to schedule an EB fleet on a trunk transport route with long travel distance and high service frequency. In the context of a single EB route level, Rogge et al. [14] provided a thorough and comprehensive framework for the cost-optimized planning of a mixed EB fleet of different EB types. As for the level of multidepot EB transit network, Wen et al. managed to develop an optimization model with the goal of minimizing the total EB fleet purchase and operation cost and proposed an adaptive large neighborhood search heuristic to solve the randomly generated numerical cases [25].


### 2.2. Literature Review on EB Charging Infrastructure Planning

EB charging infrastructure planning varies with EB’s charging strategies similarly. Charging lane EB system mainly pursues an optimal location and length of charging lanes [26, 27], whereas EB system with station-based charging modes generally requires optimization of charging station sitting and charging facility scheduling. Among the station-based charging modes, the fast-charging mode is usually linked to the distributed deployment format of the fast-charging station, which was investigated at the transit network level by Wei et al. [16]. Yan et al. [28] proposed a charging sequence generating strategy for a single fast-charging station. Centralized charging station deployment format is generally used for battery swapping and regular charging modes [11, 29]. Assuming the battery swapping duration is constant, several optimization methods for swapping station deployment and switching battery schedule were proposed in recent studies [30–32]. Meanwhile, the methods of these works can not be implemented directly to the infrastructure planning of regular charging EB system due to the regular charging EBs’ flexible charging policy with relatively long and variable charging duration.Most existing studies related to regular charging EB charging infrastructure planning concentrate mainly on the charging schedule optimization for charging stations, with known EB fleet size and operation schedule. Leou and Hung [33] presented a charging scheduling model for a centralized depot for a small centralized depot considering the variable daytime electricity prices. Houbbadi et al. [34] developed a multiobjective depot charging strategy optimization model aiming at reducing charging cost as well as extending battery lifetime and tested their solving procedure with a case study of one specific EB operating on a single line scenario. Wang et al. [7] presented a real-time charging scheduling method based on the Markov decision process for large-scale EB fleet to reduce the charging and operation cost. The real-world streaming data of 16359 EBs in Shenzhen was used to validate their method. Also grounding the practical case on EB transit network in Shenzhen, Lin et al. [35] focused on the deployment of the centralized charging station for EB transit system, introducing the connection of power grid to the problem of charging infrastructure planning.


### 2.3. Research Gaps, Contributions, and Organization of the Study

It has been addressed that the operation of electric vehicle fleets and the planning of charging systems are highly coupled together [36]. According to the literature review, however, the method for optimizing regular charging EB schedule and charging infrastructure deployment jointly is underexplored. Seldom researchers have tried to investigate such methods. Rogge et al. [14] adopted joint optimization at the level of bus line and optimized the bus fleet schedule based on the preconfigured blocks of service trips. But the quality of blocks had a considerable impact on that of the solution. Liu and Ceder [12] optimized the total number of buses and battery chargers for the fast-charging EB system with multiple lines. Meanwhile, their optimization objectives did not contain the operational cost. In this paper, we propose a joint optimization methodology of regular charging EB transit network schedule and stationary charger deployment. The methodology takes into account the range limitation of travel distance and state of charge (SOC) as constraints. Moreover, partial charging policy and time-of-use electricity prices are considered in the optimization method to enhance the model’s practical applicability [12, 37].The rest of this work is structured as follows. Section3 details a formal description of the regular charging EB stationary charger deployment and multidepot vehicle scheduling problem (SCD-MDVSP) with a small illustrative example, followed by the mathematical formulation in consistence with the problem statement in Section 4. Section 5 provides the solution approach of the improved adaptive genetic algorithm. Subsequentially, a case study involving 8 individual bus routes in Anting Town, Shanghai, China, is conducted for model validation and result analysis is in Section 6. Section 7 finally summarizes our current work and discusses the possible directions for future research.


## 2.1. Literature Review on EB Vehicle Scheduling Problem

EB operation and charging scheduling belongs to the transit vehicle scheduling problem, which refers to the problem of investigating an optimal assignment of trips in a given transit timetable to the bus fleet. Transit management must design feasible and accurate plans for routes running and EBs charging when the EB penetration level is high. To operate the mixed bus fleet, Paul and Yamada [15] proposed a k-greedy algorithm-based approach to maximize the travel distance of the EBs in the bus fleet. Wei et al. [16] introduced a spatial-temporal optimization model to schedule the mixed bus fleet and identify the optimal infrastructure deployment strategies of the bus system.The existing research on the operation scheduling of the 100% EB fleet can be categorized according to the battery charging strategies outlined in the background. Jang et al. [17, 18] optimized the locations of charging lanes and the battery size to minimize the total social cost for a single bus line. Several studies addressed the operation of EB under battery exchange mode under the predetermined charging time and full-charging assumption [19–21]. Wang et al. [8] developed a framework to optimize the location and capacity of the charging stations while at the same time generating EB recharging schedules under fast-charging rules. Liu and Ceder [12] proposed two different mathematical programming models and solution methods to solve the scheduling problem of fast-charging EBs with the adoption of a partial charging policy.Compared with charging lanes, battery exchange, and fast charging, regular charging mode is the most adopted charging strategy but requires longer charging time and is more complicated in terms of scheduling operation and charging plans. The bus scheduling problem for regular charging mode was generally investigated by Li [22] in consideration of charging stations with limited capacity. Ke et al. [23] proposed an EB operation and battery charging simulation framework to minimize EB transportation system construction cost in Penghu, Taiwan. Considering charging and dispatching policies, Jiang et al. [24] developed a neighborhood search based heuristic to schedule an EB fleet on a trunk transport route with long travel distance and high service frequency. In the context of a single EB route level, Rogge et al. [14] provided a thorough and comprehensive framework for the cost-optimized planning of a mixed EB fleet of different EB types. As for the level of multidepot EB transit network, Wen et al. managed to develop an optimization model with the goal of minimizing the total EB fleet purchase and operation cost and proposed an adaptive large neighborhood search heuristic to solve the randomly generated numerical cases [25].


## 2.2. Literature Review on EB Charging Infrastructure Planning

EB charging infrastructure planning varies with EB’s charging strategies similarly. Charging lane EB system mainly pursues an optimal location and length of charging lanes [26, 27], whereas EB system with station-based charging modes generally requires optimization of charging station sitting and charging facility scheduling. Among the station-based charging modes, the fast-charging mode is usually linked to the distributed deployment format of the fast-charging station, which was investigated at the transit network level by Wei et al. [16]. Yan et al. [28] proposed a charging sequence generating strategy for a single fast-charging station. Centralized charging station deployment format is generally used for battery swapping and regular charging modes [11, 29]. Assuming the battery swapping duration is constant, several optimization methods for swapping station deployment and switching battery schedule were proposed in recent studies [30–32]. Meanwhile, the methods of these works can not be implemented directly to the infrastructure planning of regular charging EB system due to the regular charging EBs’ flexible charging policy with relatively long and variable charging duration.Most existing studies related to regular charging EB charging infrastructure planning concentrate mainly on the charging schedule optimization for charging stations, with known EB fleet size and operation schedule. Leou and Hung [33] presented a charging scheduling model for a centralized depot for a small centralized depot considering the variable daytime electricity prices. Houbbadi et al. [34] developed a multiobjective depot charging strategy optimization model aiming at reducing charging cost as well as extending battery lifetime and tested their solving procedure with a case study of one specific EB operating on a single line scenario. Wang et al. [7] presented a real-time charging scheduling method based on the Markov decision process for large-scale EB fleet to reduce the charging and operation cost. The real-world streaming data of 16359 EBs in Shenzhen was used to validate their method. Also grounding the practical case on EB transit network in Shenzhen, Lin et al. [35] focused on the deployment of the centralized charging station for EB transit system, introducing the connection of power grid to the problem of charging infrastructure planning.


## 2.3. Research Gaps, Contributions, and Organization of the Study

It has been addressed that the operation of electric vehicle fleets and the planning of charging systems are highly coupled together [36]. According to the literature review, however, the method for optimizing regular charging EB schedule and charging infrastructure deployment jointly is underexplored. Seldom researchers have tried to investigate such methods. Rogge et al. [14] adopted joint optimization at the level of bus line and optimized the bus fleet schedule based on the preconfigured blocks of service trips. But the quality of blocks had a considerable impact on that of the solution. Liu and Ceder [12] optimized the total number of buses and battery chargers for the fast-charging EB system with multiple lines. Meanwhile, their optimization objectives did not contain the operational cost. In this paper, we propose a joint optimization methodology of regular charging EB transit network schedule and stationary charger deployment. The methodology takes into account the range limitation of travel distance and state of charge (SOC) as constraints. Moreover, partial charging policy and time-of-use electricity prices are considered in the optimization method to enhance the model’s practical applicability [12, 37].The rest of this work is structured as follows. Section3 details a formal description of the regular charging EB stationary charger deployment and multidepot vehicle scheduling problem (SCD-MDVSP) with a small illustrative example, followed by the mathematical formulation in consistence with the problem statement in Section 4. Section 5 provides the solution approach of the improved adaptive genetic algorithm. Subsequentially, a case study involving 8 individual bus routes in Anting Town, Shanghai, China, is conducted for model validation and result analysis is in Section 6. Section 7 finally summarizes our current work and discusses the possible directions for future research.


## 3. Description of the SCD-MDVSP

The goal of this section is to facilitate the understanding of the SCD-MDVSP, including input conditions, the modeling scenario, and a feasible solution. A simple numerical example, which is based on a transit network with 3 lines, is used to illustrate the SCD-MDVSP.In this numerical example, there are 5 terminal stations related to the 3 transit lines. Considering space and power management constraints, 2 terminal stations are selected as charging stations, while other terminal stations are ordinary terminal stations. It is assumed that the battery chargers can only be installed in the candidate charging stations. Figure1 shows the transit network topology and the operating duration between any two stations.Figure 1
Topology of the transit network.The SOC-related parameters of EB set in the numerical example are listed in Table1, which indicates the charging and discharging characteristics of EB. In the modeling scenario, after completing their service missions, EBs would return to their original departing charging stations and get fully charged at night and depart with the permitted maximum SOC the next day.Table 1
SOC-related parameters of EB.
ParametersSettingsTotal battery capacity200 kWhPermitted maximum SOC180 kWhPermitted minimum SOC30 kWhCharging power of a battery charger40 kWPower consumption rate during EB running20 kWThe timetables for the 15 service trips on the 3 lines are presented in Table2. Each service trip in the timetables should be covered exactly once per day, and multiline trips can be assigned to one EB only if the sequence of trips and charging arrangements is feasible in respect of time and SOC range constraints.Table 2
Timetables of the transit lines.
Line IDDirectionDeparture timeArrival timeService trip ID1Line 1D1 ⟶ D25:007:00113:0015:00814:3016:309D2 ⟶ D19:0011:00615:3017:301020:0022:0014Line 2D1 ⟶ T15:008:00211:3014:307T1 ⟶ D17:3010:3048:3011:30519:0022:0013Line 3T2 ⟶ T315:3016:301120:3021:3015T3 ⟶ T25:306:30317:0018:00121Service trip ID numbers are in the order of the service trips’ departure time.Given the input data above, the objective of SCD-MDVSP is to minimize the overall construction and operation cost of the EB transit system, including EB fleet purchase cost, battery charger deployment cost, power consumption cost, and time-related operation cost. To achieve this goal, there are 4 key points in the joint optimization framework of EB scheduling and charger deploying, including the EB fleet size, the assignment of service trips to EBs, the start time and duration of EBs’ charging tasks, and the allocation of the number of stationary chargers in the charging stations. Figure2 illustrates a feasible solution to the SCD-MDVSP.Figure 2
A feasible solution to the SCD-MDVSP. (a) EB fleet schedule and (b) battery charger arrangement.
(a)(b)As shown in Figure2(a), the EB fleet schedule in SCD-MDVSP can be established as a flowchart pattern, comprising of charging stations, trips, and charging tasks as nodes [13, 38], while black arrows indicate the sequence of EB missions as arcs. There are 2 EBs (bus 1 and bus 2) belonging to charging station 1; meanwhile, 1 EB (bus 3) and 1 charger (charger 3) belong to charging station 2. The operation and charging schedules of bus 1, bus 2, and bus 3 are D1⟶s1⟶c1⟶s6⟶s7⟶s11⟶c4⟶s14⟶D1, D1⟶s2⟶s5⟶c3⟶s9⟶s12⟶s13⟶D1, and D2⟶s3⟶s4⟶c2⟶s8⟶s10⟶c5⟶s15⟶D2, respectively. Similarly, each charger’s battery charger arrangement can also be isolated as a flowchart pattern (see Figure 2(b)), which is a circle starting from the charging station where the charger is installed, serializing the charging tasks executed by the same charger chronologically and ending up with the same charging station. There are 2 chargers (charger 1 and charger 2) installed in charging station 1 and 1 charger (charger 3) installed in charging station 2. The charging task arrangement of charger 1, charger 2, and charger 3 is D1⟶c3⟶c5⟶D1, D1⟶c2⟶D1, and D2⟶c1⟶c4⟶D2, respectively. The flowchart patterns of EB fleet schedule and battery charger arrangement are the basis for the SCD-MDVSP modeling in Section 4.


## 4. Mathematical Formulation

### 4.1. Mathematical Notations

To better illustrate the proposed model, the notations of parameters and variables relevant to the SCD-MDVSP are presented in Table3.Table 3
Notations of the SCD-MDVSP model.
Sets/indicesSSet of service tripsCSet of charging tasksDSet of charging stationsNSet of pricing intervals of time-of-use electricity pricesi,jIndices of service trips,i,j∈Sp,qIndices of charging tasks,p,q∈CdIndices of charging stations,d∈DnIndices of pricing interval of time-of-use electricity prices,n∈NParametersaiStarting time of service tripi∈StiDuration of service tripi∈SeiPower consumption of service tripi∈StijDuration of the deadhead to implement the shift from service tripi∈S to service trip j∈S without charging midwayeijPower consumption for the deadhead to implement the shift from service tripi∈S to service trip j∈S without charging midwaytdi′Duration of the deadhead to implement the service tripi∈S after the EB pulling out of the charging station d∈D without charging midwayedi′Power consumption for the deadhead to implement the service tripi∈S after the EB pulling out of the charging station d∈D without charging midwaytid″Duration of the deadhead to pull in the charging stationd∈D after finishing the service trip i∈S without charging midwayeid″Power consumption for the deadhead to pull in the charging stationd∈D after finishing the service trip i∈S without charging midwayt⌣ipDuration of the deadhead to execute charging taskp∈C after service trip i∈Se⌣ipPower consumption for the deadhead to execute charging taskp∈P after service trip i∈S without charging midwayt⌢piDuration of the deadhead to execute service tripi∈S after charging task p∈Ce⌢piPower consumption for the deadhead to execute service tripi∈S after charging task p∈Ct¯dpDuration of the deadhead to execute charging taskp∈C after the EB pulling out of the charging station d∈De¯dpPower consumption for the deadhead to execute charging taskp∈C after the EB pulling out of the charging station d∈Dt˜pdDuration of the deadhead to pull in the charging stationd∈D after the charging task p∈Ce˜pdPower consumption for the deadhead to pull in the charging stationd∈D after the charging task p∈Ce^pPower recharged during charging taskp∈CmnStarting time of pricing intervaln∈NtnDuration of pricing intervaln∈NfnElectricity price in pricing intervaln∈NcbCapital and maintenance cost of a busctTime-related operational cost for a busccPurchasing and maintenance cost per chargerIntermediate variablesliEB’s current SOC at the completion of the service tripi∈S, which can be calculated as (21)tpnCharging duration of the charging taskp∈C in the pricing interval n∈NDecision variablesxijEquals 1 if the EB’s next service trip isj∈S after finishing the service trip i∈S (regardless of whether or not the EB goes for charging between the two service trips), 0 otherwiseypqEquals 1 if charging taskp∈C takes place after charging task q∈C and the two charging tasks are completed by the same charger, 0 otherwisezipEquals 1 if the EB travels to execute the charging taskp∈C after finishing the service trip i∈S, 0 otherwisez^piEquals 1 if the EB travels to execute the service tripi∈S after finishing the charging task p∈C, 0 otherwiseudiEquals 1 if the EB pulls out of the charging stationd∈D to execute the service trip i∈S (regardless of whether or not the EB goes for charging midway), 0 otherwiseu^idEquals 1 if the EB pulls in the charging stationd∈D after finishing the service trip i∈S (regardless of whether or not the EB goes for charging midway), 0 otherwisevdpEquals 1 if the EB pulls out of the charging stationd∈D to execute the charging task p∈C, 0 otherwisev^pdEquals 1 if the EB pulls in the charging stationd∈D after finishing the charging task p∈C, 0 otherwisewdpEquals 1 if the charging taskp∈C is executed by the charger installed in the charging station d∈D and is the earliest of all the charging tasks executed by the same charger throughout the dayw^pdEquals 1 if the charging taskp∈C is executed by the charger installed in the charging station d∈D and is the latest of all the charging tasks executed by the same charger throughout the daya^pStarting time of charging taskp∈Ct^pDuration of the charging taskp∈CCharging and discharging functionsFl0,t^pCharging function withl0 (SOC at the start of charging) and t^p as independent variables and e^p as a dependent variableGl0,trDischarging function withl0 (SOC at the start of charging) and tr (representing ti,tij,tdi′,tid″,t⌣ip,t⌢pi,t¯dp,t˜pd) as independent variables and er (representing ei,eij,edi′,eid″,e⌣ip,e⌢pi,e¯dp,e˜pd) as a dependent variable


### 4.2. Mathematical Model

Given a set of timetabled bus trips and a set of charging stations, the SCD-MDVSP model is to minimize the total cost by exploring for an assignment of bus trips to EBs and an allocation of battery chargers to the charging stations. The objective function is defined in 4.2.1 and module constraints are formulated based on the flowchart patterns of EB fleet schedule and battery charger arrangement presented inSection 3. Specifically, the EB fleet schedule flowchart can be divided into two subparts: trip-related vehicle schedule and charging-related vehicle schedule. And the constraints of the two subparts are discussed in 4.2.2 and 4.2.4, respectively. Besides, the constraints of the battery charger arrangement flowchart are shown in 4.2.3. Moreover, the energy level constraints and supplement parts (intermediate variable calculation and charging and discharging functions) are detailed in 4.2.5, 4.2.6, and 4.2.7.


#### 4.2.1. Objective Function

(1)minZ=cb∑d∑iudi+cc∑d∑pwdp+∑n∑pfntpn+ct∑d∑iudi∑pz^pit¯dp+t^p+t⌢pi+1−∑pz^pitdi′+∑i∑j,i≠jxijti+∑pzipt⌣ip+t^p+t⌢pj+1−∑pziptij+∑d∑iu^id∑pzipt⌣ip+t^p+t˜pd+1−∑pziptid″.Objective (1) is to minimize the total cost of constructing and operating the EB system, which consists of the purchase and maintenance cost of EBs and chargers, the energy consumption cost, and time-related in-service cost, such as wages of bus drivers. The time-related in-service cost is proportional to the sum of the pull-out time, the duration of operating and shifting the service trips, and the pull-in time of all the EBs. Specifically, ∑pzipt⌣ip+t^p+t⌢pj+1−∑pziptij represents that if the bus implements any charging task during the shift from service trip i to service trip j (∑pzip=1), the shift duration is t⌣ip+t^p+t⌢pj; otherwise, (1−∑pzip=1), the shift duration is tij.


#### 4.2.2. Vehicle Scheduling Constraints

(2)∑iudi−∑iu^id=0,∀d,(3)∑jxij+∑du^id=1,∀i,i≠j,(4)∑jxji+∑dudi−∑jxij+∑du^id=0,∀i,i≠j,(5)ai+ti+∑pzipt⌣ip+t^p+t⌢pj+1−∑pziptij≤aj+M1−xij,∀i,j,i≠j,(6)udi∈0,1,∀d,i,(7)u^id∈0,1,∀d,i,(8)xij∈0,1,∀i,j,i≠j.Constraint (2) shows that the number of pull-out EBs is equal to that of pull-in EBs in order to maintain the same daily operational plan. Constraint (3) ensures that each service trip is executed by exactly one bus. Equation (4) illustrates that after finishing a service trip, the bus should perform another operational task (representing service trip, pull-out from the charging station, or pull-in the charging station). Constraint (5) indicates that the service trips carried out by the same bus do not overlap in timeline. Constraints (6)–(8) define the binary decision variables udi, u^id. and xij.


#### 4.2.3. Charger Scheduling Constraints

(9)∑pwdp−∑pw^pd=0,∀d,(10)∑qypq+∑qw^pd=1,∀p,p≠q,(11)∑qyqp+∑qwdp−∑qypq+∑qw^pd=0,∀p,p≠q,(12)ap+tp≤aq+M1−ypq,∀p,q,p≠q,(13)wdp∈0,1,∀d,p,(14)w^pd∈0,1,∀d,p,(15)ypq∈0,1,∀p,q,p≠q,(16)ap>0,∀p,(17)tp>0,∀p.Constraint (9) indicates that a complete charging schedule for a battery charger should be a close loop that starts and ends at the same charging station as presented in the battery charger arrangement flowchart. Equation (10) ensures that each charging task is performed exactly once per day. Equation (11) shows the flow constraint of each charging task in the flowchart of the battery charger arrangement. Constraint (12) ensures that the charging tasks performed by the same charger do not overlap in timeline. Constraints (13)–(17) define the range of decision variables wdp, w^pd, ypq, a^p, and t^p.


#### 4.2.4. Vehicle Scheduling and Charger Scheduling Cross Constraints

(18)∑izip+∑dvdp=1,∀p,(19)∑izip+∑dvdp−∑iz^pi+∑dv^pd=0,∀p,(20)ap+tp+t⌢pi≤ai+M1−z^pi,∀i,p,(21)zip∈0,1,∀i,p,(22)z^pi∈0,1,∀i,p,(23)vdp∈0,1,∀d,p,(24)v^pd∈0,1,∀d,p.Constraint (18) ensures that only one EB can be served per charging task. Equation (19) enforces that each charging task is performed between two consecutive operational tasks. Constraint (20) represents that the bus should not be late for the next service trip after being charged. Constraints (21)–(24) define the binary decision variables zip, z^pi, vdp, and v^pd.


#### 4.2.5. Energy Level Constraints

(25)li−∑pzipe⌣ip≥SOCmin,∀i,(26)li+ei+∑pz^pie⌢pi≤SOCmax,∀i,(27)SOCmax−vdpe¯dp≥SOCmin,∀d,p,(28)li+u^id∑pzipe^p−e⌣ip≤SOCmax,∀i,d,(29)li−u^id∑pzipe⌣ip+e˜pd−e^p+1−∑pzipeid″≥SOCmin,∀i,d.The start and end of a charging task are the moments when the EB’sSOC reaches the minimum and maximum values, respectively, during the daily operation. Constraints (25)–(28) limit the residual power of buses between SOCmin and SOCmax at the start and end of any charging task. Constraint (29) ensures that the SOC of buses is more than SOCmin when the buses pull in the charging stations.


#### 4.2.6. Intermediate Variable Calculation

(30)li=SOCmax−∑dudi1−vdpz^piedi′+vdpz^pie¯dp+e⌢pi−ep,∀i,while∃udi=1,∀d,∑jxjilj+∑pzjpe^p−e⌣jp−e⌢pi−1−∑pzjpeij−ei,∀i,i≠j,otherwise,(31)dpn=0,ap≥mn+tnorap+tp≤m,tn,ap≤mnandap+tp≥mn+tn,tp,ap+tp>mnandap+tp<mn+tnandap≥mn,∀p,n.ap+tp−mn,ap+tp>mnandap+tp<mn+tnandap<mn,mn+tn−ap,ap>mnandap<mn+tnandap+tp>mn+tn,Equation (30) defines the calculation of the intermediate variables li. If the service trip i is the first service trip for a particular bus, li can be calculated as the top branch of equation (30). Otherwise, li can be calculated as the bottom branch. Equation (31) defines the calculation method for dividing the whole charging task into several charging segments according to the electricity tariff periods.


#### 4.2.7. Charging and Discharging Functions

(32)e^p=Ft^p=f⋅t^p,∀p,(33)er=Gtr=g⋅tr,∀r.In this paper, it is assumed that the charging functionFl0,t^p and the discharging functions Gl0,tr are proportional functions, which means they are independent from l0 and can be rewritten as Ft^p and Gtr. Since only EB’s average discharging power under daily operational conditions is available, the discharging power under any driving condition is set to the same value. Let f and g be the charging and discharging power individually. Therefore, the charging and discharging functions are illustrated as (32) and (33).


## 4.1. Mathematical Notations

To better illustrate the proposed model, the notations of parameters and variables relevant to the SCD-MDVSP are presented in Table3.Table 3
Notations of the SCD-MDVSP model.
Sets/indicesSSet of service tripsCSet of charging tasksDSet of charging stationsNSet of pricing intervals of time-of-use electricity pricesi,jIndices of service trips,i,j∈Sp,qIndices of charging tasks,p,q∈CdIndices of charging stations,d∈DnIndices of pricing interval of time-of-use electricity prices,n∈NParametersaiStarting time of service tripi∈StiDuration of service tripi∈SeiPower consumption of service tripi∈StijDuration of the deadhead to implement the shift from service tripi∈S to service trip j∈S without charging midwayeijPower consumption for the deadhead to implement the shift from service tripi∈S to service trip j∈S without charging midwaytdi′Duration of the deadhead to implement the service tripi∈S after the EB pulling out of the charging station d∈D without charging midwayedi′Power consumption for the deadhead to implement the service tripi∈S after the EB pulling out of the charging station d∈D without charging midwaytid″Duration of the deadhead to pull in the charging stationd∈D after finishing the service trip i∈S without charging midwayeid″Power consumption for the deadhead to pull in the charging stationd∈D after finishing the service trip i∈S without charging midwayt⌣ipDuration of the deadhead to execute charging taskp∈C after service trip i∈Se⌣ipPower consumption for the deadhead to execute charging taskp∈P after service trip i∈S without charging midwayt⌢piDuration of the deadhead to execute service tripi∈S after charging task p∈Ce⌢piPower consumption for the deadhead to execute service tripi∈S after charging task p∈Ct¯dpDuration of the deadhead to execute charging taskp∈C after the EB pulling out of the charging station d∈De¯dpPower consumption for the deadhead to execute charging taskp∈C after the EB pulling out of the charging station d∈Dt˜pdDuration of the deadhead to pull in the charging stationd∈D after the charging task p∈Ce˜pdPower consumption for the deadhead to pull in the charging stationd∈D after the charging task p∈Ce^pPower recharged during charging taskp∈CmnStarting time of pricing intervaln∈NtnDuration of pricing intervaln∈NfnElectricity price in pricing intervaln∈NcbCapital and maintenance cost of a busctTime-related operational cost for a busccPurchasing and maintenance cost per chargerIntermediate variablesliEB’s current SOC at the completion of the service tripi∈S, which can be calculated as (21)tpnCharging duration of the charging taskp∈C in the pricing interval n∈NDecision variablesxijEquals 1 if the EB’s next service trip isj∈S after finishing the service trip i∈S (regardless of whether or not the EB goes for charging between the two service trips), 0 otherwiseypqEquals 1 if charging taskp∈C takes place after charging task q∈C and the two charging tasks are completed by the same charger, 0 otherwisezipEquals 1 if the EB travels to execute the charging taskp∈C after finishing the service trip i∈S, 0 otherwisez^piEquals 1 if the EB travels to execute the service tripi∈S after finishing the charging task p∈C, 0 otherwiseudiEquals 1 if the EB pulls out of the charging stationd∈D to execute the service trip i∈S (regardless of whether or not the EB goes for charging midway), 0 otherwiseu^idEquals 1 if the EB pulls in the charging stationd∈D after finishing the service trip i∈S (regardless of whether or not the EB goes for charging midway), 0 otherwisevdpEquals 1 if the EB pulls out of the charging stationd∈D to execute the charging task p∈C, 0 otherwisev^pdEquals 1 if the EB pulls in the charging stationd∈D after finishing the charging task p∈C, 0 otherwisewdpEquals 1 if the charging taskp∈C is executed by the charger installed in the charging station d∈D and is the earliest of all the charging tasks executed by the same charger throughout the dayw^pdEquals 1 if the charging taskp∈C is executed by the charger installed in the charging station d∈D and is the latest of all the charging tasks executed by the same charger throughout the daya^pStarting time of charging taskp∈Ct^pDuration of the charging taskp∈CCharging and discharging functionsFl0,t^pCharging function withl0 (SOC at the start of charging) and t^p as independent variables and e^p as a dependent variableGl0,trDischarging function withl0 (SOC at the start of charging) and tr (representing ti,tij,tdi′,tid″,t⌣ip,t⌢pi,t¯dp,t˜pd) as independent variables and er (representing ei,eij,edi′,eid″,e⌣ip,e⌢pi,e¯dp,e˜pd) as a dependent variable


## 4.2. Mathematical Model

Given a set of timetabled bus trips and a set of charging stations, the SCD-MDVSP model is to minimize the total cost by exploring for an assignment of bus trips to EBs and an allocation of battery chargers to the charging stations. The objective function is defined in 4.2.1 and module constraints are formulated based on the flowchart patterns of EB fleet schedule and battery charger arrangement presented inSection 3. Specifically, the EB fleet schedule flowchart can be divided into two subparts: trip-related vehicle schedule and charging-related vehicle schedule. And the constraints of the two subparts are discussed in 4.2.2 and 4.2.4, respectively. Besides, the constraints of the battery charger arrangement flowchart are shown in 4.2.3. Moreover, the energy level constraints and supplement parts (intermediate variable calculation and charging and discharging functions) are detailed in 4.2.5, 4.2.6, and 4.2.7.


### 4.2.1. Objective Function

(1)minZ=cb∑d∑iudi+cc∑d∑pwdp+∑n∑pfntpn+ct∑d∑iudi∑pz^pit¯dp+t^p+t⌢pi+1−∑pz^pitdi′+∑i∑j,i≠jxijti+∑pzipt⌣ip+t^p+t⌢pj+1−∑pziptij+∑d∑iu^id∑pzipt⌣ip+t^p+t˜pd+1−∑pziptid″.Objective (1) is to minimize the total cost of constructing and operating the EB system, which consists of the purchase and maintenance cost of EBs and chargers, the energy consumption cost, and time-related in-service cost, such as wages of bus drivers. The time-related in-service cost is proportional to the sum of the pull-out time, the duration of operating and shifting the service trips, and the pull-in time of all the EBs. Specifically, ∑pzipt⌣ip+t^p+t⌢pj+1−∑pziptij represents that if the bus implements any charging task during the shift from service trip i to service trip j (∑pzip=1), the shift duration is t⌣ip+t^p+t⌢pj; otherwise, (1−∑pzip=1), the shift duration is tij.


### 4.2.2. Vehicle Scheduling Constraints

(2)∑iudi−∑iu^id=0,∀d,(3)∑jxij+∑du^id=1,∀i,i≠j,(4)∑jxji+∑dudi−∑jxij+∑du^id=0,∀i,i≠j,(5)ai+ti+∑pzipt⌣ip+t^p+t⌢pj+1−∑pziptij≤aj+M1−xij,∀i,j,i≠j,(6)udi∈0,1,∀d,i,(7)u^id∈0,1,∀d,i,(8)xij∈0,1,∀i,j,i≠j.Constraint (2) shows that the number of pull-out EBs is equal to that of pull-in EBs in order to maintain the same daily operational plan. Constraint (3) ensures that each service trip is executed by exactly one bus. Equation (4) illustrates that after finishing a service trip, the bus should perform another operational task (representing service trip, pull-out from the charging station, or pull-in the charging station). Constraint (5) indicates that the service trips carried out by the same bus do not overlap in timeline. Constraints (6)–(8) define the binary decision variables udi, u^id. and xij.


### 4.2.3. Charger Scheduling Constraints

(9)∑pwdp−∑pw^pd=0,∀d,(10)∑qypq+∑qw^pd=1,∀p,p≠q,(11)∑qyqp+∑qwdp−∑qypq+∑qw^pd=0,∀p,p≠q,(12)ap+tp≤aq+M1−ypq,∀p,q,p≠q,(13)wdp∈0,1,∀d,p,(14)w^pd∈0,1,∀d,p,(15)ypq∈0,1,∀p,q,p≠q,(16)ap>0,∀p,(17)tp>0,∀p.Constraint (9) indicates that a complete charging schedule for a battery charger should be a close loop that starts and ends at the same charging station as presented in the battery charger arrangement flowchart. Equation (10) ensures that each charging task is performed exactly once per day. Equation (11) shows the flow constraint of each charging task in the flowchart of the battery charger arrangement. Constraint (12) ensures that the charging tasks performed by the same charger do not overlap in timeline. Constraints (13)–(17) define the range of decision variables wdp, w^pd, ypq, a^p, and t^p.


### 4.2.4. Vehicle Scheduling and Charger Scheduling Cross Constraints

(18)∑izip+∑dvdp=1,∀p,(19)∑izip+∑dvdp−∑iz^pi+∑dv^pd=0,∀p,(20)ap+tp+t⌢pi≤ai+M1−z^pi,∀i,p,(21)zip∈0,1,∀i,p,(22)z^pi∈0,1,∀i,p,(23)vdp∈0,1,∀d,p,(24)v^pd∈0,1,∀d,p.Constraint (18) ensures that only one EB can be served per charging task. Equation (19) enforces that each charging task is performed between two consecutive operational tasks. Constraint (20) represents that the bus should not be late for the next service trip after being charged. Constraints (21)–(24) define the binary decision variables zip, z^pi, vdp, and v^pd.


### 4.2.5. Energy Level Constraints

(25)li−∑pzipe⌣ip≥SOCmin,∀i,(26)li+ei+∑pz^pie⌢pi≤SOCmax,∀i,(27)SOCmax−vdpe¯dp≥SOCmin,∀d,p,(28)li+u^id∑pzipe^p−e⌣ip≤SOCmax,∀i,d,(29)li−u^id∑pzipe⌣ip+e˜pd−e^p+1−∑pzipeid″≥SOCmin,∀i,d.The start and end of a charging task are the moments when the EB’sSOC reaches the minimum and maximum values, respectively, during the daily operation. Constraints (25)–(28) limit the residual power of buses between SOCmin and SOCmax at the start and end of any charging task. Constraint (29) ensures that the SOC of buses is more than SOCmin when the buses pull in the charging stations.


### 4.2.6. Intermediate Variable Calculation

(30)li=SOCmax−∑dudi1−vdpz^piedi′+vdpz^pie¯dp+e⌢pi−ep,∀i,while∃udi=1,∀d,∑jxjilj+∑pzjpe^p−e⌣jp−e⌢pi−1−∑pzjpeij−ei,∀i,i≠j,otherwise,(31)dpn=0,ap≥mn+tnorap+tp≤m,tn,ap≤mnandap+tp≥mn+tn,tp,ap+tp>mnandap+tp<mn+tnandap≥mn,∀p,n.ap+tp−mn,ap+tp>mnandap+tp<mn+tnandap<mn,mn+tn−ap,ap>mnandap<mn+tnandap+tp>mn+tn,Equation (30) defines the calculation of the intermediate variables li. If the service trip i is the first service trip for a particular bus, li can be calculated as the top branch of equation (30). Otherwise, li can be calculated as the bottom branch. Equation (31) defines the calculation method for dividing the whole charging task into several charging segments according to the electricity tariff periods.


### 4.2.7. Charging and Discharging Functions

(32)e^p=Ft^p=f⋅t^p,∀p,(33)er=Gtr=g⋅tr,∀r.In this paper, it is assumed that the charging functionFl0,t^p and the discharging functions Gl0,tr are proportional functions, which means they are independent from l0 and can be rewritten as Ft^p and Gtr. Since only EB’s average discharging power under daily operational conditions is available, the discharging power under any driving condition is set to the same value. Let f and g be the charging and discharging power individually. Therefore, the charging and discharging functions are illustrated as (32) and (33).


## 4.2.1. Objective Function

(1)minZ=cb∑d∑iudi+cc∑d∑pwdp+∑n∑pfntpn+ct∑d∑iudi∑pz^pit¯dp+t^p+t⌢pi+1−∑pz^pitdi′+∑i∑j,i≠jxijti+∑pzipt⌣ip+t^p+t⌢pj+1−∑pziptij+∑d∑iu^id∑pzipt⌣ip+t^p+t˜pd+1−∑pziptid″.Objective (1) is to minimize the total cost of constructing and operating the EB system, which consists of the purchase and maintenance cost of EBs and chargers, the energy consumption cost, and time-related in-service cost, such as wages of bus drivers. The time-related in-service cost is proportional to the sum of the pull-out time, the duration of operating and shifting the service trips, and the pull-in time of all the EBs. Specifically, ∑pzipt⌣ip+t^p+t⌢pj+1−∑pziptij represents that if the bus implements any charging task during the shift from service trip i to service trip j (∑pzip=1), the shift duration is t⌣ip+t^p+t⌢pj; otherwise, (1−∑pzip=1), the shift duration is tij.


## 4.2.2. Vehicle Scheduling Constraints

(2)∑iudi−∑iu^id=0,∀d,(3)∑jxij+∑du^id=1,∀i,i≠j,(4)∑jxji+∑dudi−∑jxij+∑du^id=0,∀i,i≠j,(5)ai+ti+∑pzipt⌣ip+t^p+t⌢pj+1−∑pziptij≤aj+M1−xij,∀i,j,i≠j,(6)udi∈0,1,∀d,i,(7)u^id∈0,1,∀d,i,(8)xij∈0,1,∀i,j,i≠j.Constraint (2) shows that the number of pull-out EBs is equal to that of pull-in EBs in order to maintain the same daily operational plan. Constraint (3) ensures that each service trip is executed by exactly one bus. Equation (4) illustrates that after finishing a service trip, the bus should perform another operational task (representing service trip, pull-out from the charging station, or pull-in the charging station). Constraint (5) indicates that the service trips carried out by the same bus do not overlap in timeline. Constraints (6)–(8) define the binary decision variables udi, u^id. and xij.


## 4.2.3. Charger Scheduling Constraints

(9)∑pwdp−∑pw^pd=0,∀d,(10)∑qypq+∑qw^pd=1,∀p,p≠q,(11)∑qyqp+∑qwdp−∑qypq+∑qw^pd=0,∀p,p≠q,(12)ap+tp≤aq+M1−ypq,∀p,q,p≠q,(13)wdp∈0,1,∀d,p,(14)w^pd∈0,1,∀d,p,(15)ypq∈0,1,∀p,q,p≠q,(16)ap>0,∀p,(17)tp>0,∀p.Constraint (9) indicates that a complete charging schedule for a battery charger should be a close loop that starts and ends at the same charging station as presented in the battery charger arrangement flowchart. Equation (10) ensures that each charging task is performed exactly once per day. Equation (11) shows the flow constraint of each charging task in the flowchart of the battery charger arrangement. Constraint (12) ensures that the charging tasks performed by the same charger do not overlap in timeline. Constraints (13)–(17) define the range of decision variables wdp, w^pd, ypq, a^p, and t^p.


## 4.2.4. Vehicle Scheduling and Charger Scheduling Cross Constraints

(18)∑izip+∑dvdp=1,∀p,(19)∑izip+∑dvdp−∑iz^pi+∑dv^pd=0,∀p,(20)ap+tp+t⌢pi≤ai+M1−z^pi,∀i,p,(21)zip∈0,1,∀i,p,(22)z^pi∈0,1,∀i,p,(23)vdp∈0,1,∀d,p,(24)v^pd∈0,1,∀d,p.Constraint (18) ensures that only one EB can be served per charging task. Equation (19) enforces that each charging task is performed between two consecutive operational tasks. Constraint (20) represents that the bus should not be late for the next service trip after being charged. Constraints (21)–(24) define the binary decision variables zip, z^pi, vdp, and v^pd.


## 4.2.5. Energy Level Constraints

(25)li−∑pzipe⌣ip≥SOCmin,∀i,(26)li+ei+∑pz^pie⌢pi≤SOCmax,∀i,(27)SOCmax−vdpe¯dp≥SOCmin,∀d,p,(28)li+u^id∑pzipe^p−e⌣ip≤SOCmax,∀i,d,(29)li−u^id∑pzipe⌣ip+e˜pd−e^p+1−∑pzipeid″≥SOCmin,∀i,d.The start and end of a charging task are the moments when the EB’sSOC reaches the minimum and maximum values, respectively, during the daily operation. Constraints (25)–(28) limit the residual power of buses between SOCmin and SOCmax at the start and end of any charging task. Constraint (29) ensures that the SOC of buses is more than SOCmin when the buses pull in the charging stations.


## 4.2.6. Intermediate Variable Calculation

(30)li=SOCmax−∑dudi1−vdpz^piedi′+vdpz^pie¯dp+e⌢pi−ep,∀i,while∃udi=1,∀d,∑jxjilj+∑pzjpe^p−e⌣jp−e⌢pi−1−∑pzjpeij−ei,∀i,i≠j,otherwise,(31)dpn=0,ap≥mn+tnorap+tp≤m,tn,ap≤mnandap+tp≥mn+tn,tp,ap+tp>mnandap+tp<mn+tnandap≥mn,∀p,n.ap+tp−mn,ap+tp>mnandap+tp<mn+tnandap<mn,mn+tn−ap,ap>mnandap<mn+tnandap+tp>mn+tn,Equation (30) defines the calculation of the intermediate variables li. If the service trip i is the first service trip for a particular bus, li can be calculated as the top branch of equation (30). Otherwise, li can be calculated as the bottom branch. Equation (31) defines the calculation method for dividing the whole charging task into several charging segments according to the electricity tariff periods.


## 4.2.7. Charging and Discharging Functions

(32)e^p=Ft^p=f⋅t^p,∀p,(33)er=Gtr=g⋅tr,∀r.In this paper, it is assumed that the charging functionFl0,t^p and the discharging functions Gl0,tr are proportional functions, which means they are independent from l0 and can be rewritten as Ft^p and Gtr. Since only EB’s average discharging power under daily operational conditions is available, the discharging power under any driving condition is set to the same value. Let f and g be the charging and discharging power individually. Therefore, the charging and discharging functions are illustrated as (32) and (33).


## 5. Solving Procedure

According to the model formulation, the EB scheduling and charger deploying mutually influence each other. Besides, the consideration of the partial charging policy also increases the complexity of the optimization formulation [39]. In order to improve the solving efficiency and results reliability, the adaptive genetic algorithm (AGA) is implemented in the solving procedure. The AGA was proposed by Srinivas and Patnaik [40]. This method inherits the natural selection process core of the genetic algorithm and improves the population diversity and the capability to convergence compared with the ordinary genetic algorithm. In order to implement AGA into the proposed SCD-MDVSP, some special designs in AGA chromosome encoding and adaptive operator formulating process are proposed. The detailed steps of the solving procedure are presented in:Step 1: AGA initialization. Set up the number of service trips the EB fleet serves (S), population size (P), maximum generation (P), and the independent variables of the probability function for the crossover (Pc1, Pc2, and kc) and mutation process (Pm1, Pm2, and km).Step 2: initial solution. In the first generation (g=0), a feasible random initialization is implemented. Service trips in the order of starting time are assigned randomly to the buses with several previous trips and enough SOC rather than a new bus. A coding example of a chromosome based on the feasible solution of the illustrative example in Section 3 (see Figure 2) is illustrated in Figure 3. It is assumed that the EB departs from the charging station closest to the starting station of its first service trip. The operating and charging schedules of EBs during the transit system's operating hours are represented in the chromosome. Specifically, to improve the utilization rate of EBs, it is assumed that EBs are recharged as long as possible when they are arranged to be charged in the charging stations. Thus, the starting time of the charging task is the moment the EB arrives at the charging station, and the duration of the charging task is the longer of the full-charge duration and the idling duration between service trips. Subsequently, the minimum number of chargers required for each charging station can be calculated from the daytime charging tasks. After a day of operations, EBs return to their original departing charging stations for night-time charging during EB’s nonservice time, the arrangements of which for each charging station are generated by the heuristic random search algorithm. For the night-time charging demand of EBs in each charging station, the algorithm randomly assigns EBs to feasible chargers in order of EBs’ arrival time at the charging station from late to early. If no feasible charger is available, an additional charger will be added.Step 3: fitness function and selection. There are considerable differences in magnitude between the individual’s total cost and the range of them. If we take the total cost as the fitness of individual, the selection operation will be ineffective. Therefore, the fitness function is defined as (34) in this paper, where TCreci represents the reciprocal of total cost and r is a minimal positive number:(34)f=TCreci−TCreci_min+rTCreci_max−TCreci_min+r.Step 4: crossover and mutation. Both crossover and mutation are operated within the range of feasible solutions. To prevent premature convergence and enhance search efficiency, improved adaptive operators are presented as (35) and (36), which can ensure the crossover probability increases while mutation probability decreases with the evolution of the population. Let fmax and favg represent the maximum fitness and average fitness in the population. f and f′ are defined as the individual’s fitness before mutation and crossover, respectively. kc, Pc1, and Pc2 indicate the change rate and initial maximum and minimum probability of crossover, while km, Pm1, and Pm2 define the change rate and initial maximum and minimum probability of mutation. The maximum and minimum probabilities of crossover and mutation in generations 0 and G are shown in Table 4. Once the crossover and mutation operators have finished, g=g+1. If g<G, return to Step 3. Otherwise, terminate the AGA process:(35)Pc=Pc1−Pc1−Pc2⋅f′−f¯fmax−f¯+kcgG,f′≥favg,Pc1−Pc1−Pc2⋅kcgG,f′<favg,(36)Pm=Pm1−Pm1−Pm2⋅f′−f¯fmax−f¯−kmgG,f≥favg,Pm1−Pm1−Pm2⋅kmgG,f<favg,where 0<Pc1,Pc2,Pm1,Pm2≤1, kc,km>0.Figure 3
The chromosome structure of the individual.Table 4
Maximum and minimum probabilities of crossover and mutation in generations 0 andG.
PGeneration0GPcfmaxPc2−kc⋅Pc1+1+kc⋅Pc2PcfavgPc11−kc⋅Pc1+kc⋅Pc2PmfmaxPm2km⋅Pm1+1−km⋅Pm2PmfavgPm11+km⋅Pm1−km⋅Pm2


## 6. Case Study and Result Analysis

### 6.1. Case Descriptions

To validate the effectiveness of the proposed methodology, a case study was designed based on the configuration of the inner Anting Town bus system, at Jiading District, Shanghai, China. The timetable and transit network details were obtained from Shanghai Jiading Public Transportation Co., Ltd. [41]. The bus system consists of 5 charging stations and 7 ordinary terminals, 8 lines, and 867 daily service trips (see Figure 4). The operation details are shown in Table 5. The deadheading time between any two terminals was attained from the Gaode API [42].Figure 4
The inner anting town bus system.Table 5
Operational details of the 8 transit lines.
DetailsLine 1Line 2Line 3Line 4Line 5Line 6Line 7Line 8Service time05:05–23:2005:00–19:0006:00–20:0005:30–19:0006:30–19:0005:35–22:3005:15–19:3505:20–20:00Length of route15 km18.7 km9.5 km18 km11.9 km7.9 km14.6 km15.5 kmServicing duration49 min52 min34 min54 min42 min30 min53 min50 minNumber of stops2628182715142016Number of service trips2061269766481686690Average interval11 min14 min17 min25 min33 min12 min27 min20 minTerminal station 1 (the nearest charging station)1 (1)1 (1)6 (1)2 (2)9 (5)2 (1)3 (3)4 (4)Terminal station 2 (1 nearest charging station)4 (4)8 (4)7 (1)10 (5)11 (5)12 (5)5 (5)5 (5)The EB vehicle model used in this case is BYD K9, which is one of the most popular EB vehicle models in Shenzhen [7]. The battery capacity, full-charging duration, and maximum travelling distance are set as 324 kWh, 3 h, and 250 km, respectively [43]. In line with the general battery lifetime, the calculation interval of the total cost is set for 3 years, and the discounted cost of purchasing and maintaining an EB and a charger are 1,500,000 and 450,000 RMB, respectively. The technical parameters of BYD K9 and its battery charger along with other case parameters are displayed in Table 6.Table 6
Parameter settings for the case study.
NotationsMeaningSettingsETotal battery capacity324 kWhRSOCmaxRatio of the permitted maximum SOC to total battery capacity0.95RSOCminRatio of the permitted minimum SOC to total battery capacity0.25fCharging power of the charger1.8 kWh/mingPower consumption rate during operation0.65 kWh/mincbPurchasing and maintenance conversion cost of an EB1,500,000 RMBccPurchasing and maintenance conversion cost per charger450,000 RMBctTime-related operational cost for an EB25 RMB/hThe time-varying electric price pattern of Shanghai is presented in Figure5, which was acquired from State Grid Shanghai Municipal Electric Power Company [44]. The price pattern can be divided into 3 levels. The highest tariff is applied during peak hours in the morning and evening, the lowest tariff occurs during the early morning hours, and the rest periods are linked to the intermediate tariff.Figure 5
Time-of-use electricity prices in Shanghai.


### 6.2. Result Analysis

To improve the solving efficiency, the line-based optimal solution is implemented as the initial solution in the solving process. This result is also considered as a benchmark to check the model’s reliability and effectiveness. The AGA parameter settings for the EB transit network optimization are presented in Table7.Table 7
AGA parameter settings for the single line separate optimizations.
NotationsMeaningSettingsPPopulation size1000GMaximum generation2000rMinimum positive number in fitness function0.01Pc1Initial maximum crossover probability0.95Pc2Initial minimum crossover probability0.85kcGeneration related variation rate of crossover probability1Pm1Initial maximum mutation probability0.1Pm2Initial minimum mutation probability0.05kmGeneration related variation rate of mutation probability0.2The SCD-MDVSP considering partial charging policy and time-of-use electricity prices can be well solved by the proposed methodology. According to the solving procedure, 67 EBs and 20 chargers are adopted to meet the operational and charging demands of the EB transit system. The total investment over 3 years is 140,579,264.92 RMB, which consists of bus fleet purchasing cost (100,500,000 RMB, 71.5%), stationary charger deploying cost (9,000,000 RMB, 6.4%), power consumption cost (12,400,390.92 RMB, 8.8%), and time-related operational cost (18,678,875 RMB, 13.3%). For the EBs’ operation results, each bus operates 12.94 service trips, serves 1.45 lines, and travels 219.32 km on average per day.As shown in Figure6(a), the charging scheduling scheme shows an obvious staggered charging pattern. Under the predetermined time-varying electric price, the charging demand mainly occurs during the off-peak (51.2%) and flat (41.2%) periods while the electricity consumed during the peak periods only accounts for 7.6%. Specifically, Figure 6(b) demonstrates the flexibility of the charging scheduling scheme. During low price hours, the number of EBs being charged is higher and the average charging duration is longer than those during high tariff hours. The EBs’ charging duration during the service time and nonservice time is 22.35 min and 111.51 min, respectively, which indicates that the proposed methodology can improve the utilization of EBs by scheduling long time charging tasks for nonservice time.Figure 6
Performance of the charging schedules. (a) Charging demand by hourly periods. (b) Overall view of the implementation of charging tasks.
(a)(b)


### 6.3. Comparison and Discussion

#### 6.3.1. Comparison of the Overall Performance

The line-based optimization results are set as the benchmark for optimization result comparisons. The differences between the benchmark and proposed network level optimization results are presented in Tables8 and 9. Compared with scheduling 8 lines separately, the EB transit network scheduling saves over 3 million RMB in total cost, including the investment of 1 EB and 5 battery chargers, while the power consumption and time-related cost rise slightly.Table 8
Comparison of EB fleet size and charger deployment results.
Optimization scenarioNumber of EBsNumber of chargersCharging station no.12345Benchmark682576165Proposed model672065153Table 9
Comparison of total cost and 4 components of the total cost1.
Optimization scenarioEB fleet investmentCharger investmentPower consumptionTime-related costTotal costBenchmark102,000,00011,250,00011,958,39918,387,331143,595,730Proposed model100,500,0009,000,00012,373,51718,643,288140,516,8051Unit: RMB.


#### 6.3.2. Comparison of the Utilization of EB and Chargers

Transit network scheduling can improve both the utilization of the EB fleet and battery chargers. After sorting EBs in descending order of the travel duration, we make the difference of travel duration for the first 67 EBs and plot the empirical cumulative distribution function as shown in Figure7. It is indicated that over 70% EBs’ travel duration in transit network optimization surpasses that in single line separate optimization. In terms of the utilization of battery chargers, the average daily charging duration of the battery chargers under transit network scheduling and single line scheduling is 737.79 and 582.13 minutes, respectively. Figure 8 illustrates that there is less variation in the average daily charging duration of the battery chargers across charging stations under transit network dispatch than that under single line dispatch. So, EB scheduling and charger deploying at the transit network level can also equalize the depletion of stationary chargers.Figure 7
Difference in EB daily travel duration between the results of transit network scheduling optimization and single line separate scheduling optimization.Figure 8
The average daily charging duration of the battery chargers in each charging station under transit network scheduling and single line separate scheduling.


## 6.1. Case Descriptions

To validate the effectiveness of the proposed methodology, a case study was designed based on the configuration of the inner Anting Town bus system, at Jiading District, Shanghai, China. The timetable and transit network details were obtained from Shanghai Jiading Public Transportation Co., Ltd. [41]. The bus system consists of 5 charging stations and 7 ordinary terminals, 8 lines, and 867 daily service trips (see Figure 4). The operation details are shown in Table 5. The deadheading time between any two terminals was attained from the Gaode API [42].Figure 4
The inner anting town bus system.Table 5
Operational details of the 8 transit lines.
DetailsLine 1Line 2Line 3Line 4Line 5Line 6Line 7Line 8Service time05:05–23:2005:00–19:0006:00–20:0005:30–19:0006:30–19:0005:35–22:3005:15–19:3505:20–20:00Length of route15 km18.7 km9.5 km18 km11.9 km7.9 km14.6 km15.5 kmServicing duration49 min52 min34 min54 min42 min30 min53 min50 minNumber of stops2628182715142016Number of service trips2061269766481686690Average interval11 min14 min17 min25 min33 min12 min27 min20 minTerminal station 1 (the nearest charging station)1 (1)1 (1)6 (1)2 (2)9 (5)2 (1)3 (3)4 (4)Terminal station 2 (1 nearest charging station)4 (4)8 (4)7 (1)10 (5)11 (5)12 (5)5 (5)5 (5)The EB vehicle model used in this case is BYD K9, which is one of the most popular EB vehicle models in Shenzhen [7]. The battery capacity, full-charging duration, and maximum travelling distance are set as 324 kWh, 3 h, and 250 km, respectively [43]. In line with the general battery lifetime, the calculation interval of the total cost is set for 3 years, and the discounted cost of purchasing and maintaining an EB and a charger are 1,500,000 and 450,000 RMB, respectively. The technical parameters of BYD K9 and its battery charger along with other case parameters are displayed in Table 6.Table 6
Parameter settings for the case study.
NotationsMeaningSettingsETotal battery capacity324 kWhRSOCmaxRatio of the permitted maximum SOC to total battery capacity0.95RSOCminRatio of the permitted minimum SOC to total battery capacity0.25fCharging power of the charger1.8 kWh/mingPower consumption rate during operation0.65 kWh/mincbPurchasing and maintenance conversion cost of an EB1,500,000 RMBccPurchasing and maintenance conversion cost per charger450,000 RMBctTime-related operational cost for an EB25 RMB/hThe time-varying electric price pattern of Shanghai is presented in Figure5, which was acquired from State Grid Shanghai Municipal Electric Power Company [44]. The price pattern can be divided into 3 levels. The highest tariff is applied during peak hours in the morning and evening, the lowest tariff occurs during the early morning hours, and the rest periods are linked to the intermediate tariff.Figure 5
Time-of-use electricity prices in Shanghai.


## 6.2. Result Analysis

To improve the solving efficiency, the line-based optimal solution is implemented as the initial solution in the solving process. This result is also considered as a benchmark to check the model’s reliability and effectiveness. The AGA parameter settings for the EB transit network optimization are presented in Table7.Table 7
AGA parameter settings for the single line separate optimizations.
NotationsMeaningSettingsPPopulation size1000GMaximum generation2000rMinimum positive number in fitness function0.01Pc1Initial maximum crossover probability0.95Pc2Initial minimum crossover probability0.85kcGeneration related variation rate of crossover probability1Pm1Initial maximum mutation probability0.1Pm2Initial minimum mutation probability0.05kmGeneration related variation rate of mutation probability0.2The SCD-MDVSP considering partial charging policy and time-of-use electricity prices can be well solved by the proposed methodology. According to the solving procedure, 67 EBs and 20 chargers are adopted to meet the operational and charging demands of the EB transit system. The total investment over 3 years is 140,579,264.92 RMB, which consists of bus fleet purchasing cost (100,500,000 RMB, 71.5%), stationary charger deploying cost (9,000,000 RMB, 6.4%), power consumption cost (12,400,390.92 RMB, 8.8%), and time-related operational cost (18,678,875 RMB, 13.3%). For the EBs’ operation results, each bus operates 12.94 service trips, serves 1.45 lines, and travels 219.32 km on average per day.As shown in Figure6(a), the charging scheduling scheme shows an obvious staggered charging pattern. Under the predetermined time-varying electric price, the charging demand mainly occurs during the off-peak (51.2%) and flat (41.2%) periods while the electricity consumed during the peak periods only accounts for 7.6%. Specifically, Figure 6(b) demonstrates the flexibility of the charging scheduling scheme. During low price hours, the number of EBs being charged is higher and the average charging duration is longer than those during high tariff hours. The EBs’ charging duration during the service time and nonservice time is 22.35 min and 111.51 min, respectively, which indicates that the proposed methodology can improve the utilization of EBs by scheduling long time charging tasks for nonservice time.Figure 6
Performance of the charging schedules. (a) Charging demand by hourly periods. (b) Overall view of the implementation of charging tasks.
(a)(b)


## 6.3. Comparison and Discussion

### 6.3.1. Comparison of the Overall Performance

The line-based optimization results are set as the benchmark for optimization result comparisons. The differences between the benchmark and proposed network level optimization results are presented in Tables8 and 9. Compared with scheduling 8 lines separately, the EB transit network scheduling saves over 3 million RMB in total cost, including the investment of 1 EB and 5 battery chargers, while the power consumption and time-related cost rise slightly.Table 8
Comparison of EB fleet size and charger deployment results.
Optimization scenarioNumber of EBsNumber of chargersCharging station no.12345Benchmark682576165Proposed model672065153Table 9
Comparison of total cost and 4 components of the total cost1.
Optimization scenarioEB fleet investmentCharger investmentPower consumptionTime-related costTotal costBenchmark102,000,00011,250,00011,958,39918,387,331143,595,730Proposed model100,500,0009,000,00012,373,51718,643,288140,516,8051Unit: RMB.


### 6.3.2. Comparison of the Utilization of EB and Chargers

Transit network scheduling can improve both the utilization of the EB fleet and battery chargers. After sorting EBs in descending order of the travel duration, we make the difference of travel duration for the first 67 EBs and plot the empirical cumulative distribution function as shown in Figure7. It is indicated that over 70% EBs’ travel duration in transit network optimization surpasses that in single line separate optimization. In terms of the utilization of battery chargers, the average daily charging duration of the battery chargers under transit network scheduling and single line scheduling is 737.79 and 582.13 minutes, respectively. Figure 8 illustrates that there is less variation in the average daily charging duration of the battery chargers across charging stations under transit network dispatch than that under single line dispatch. So, EB scheduling and charger deploying at the transit network level can also equalize the depletion of stationary chargers.Figure 7
Difference in EB daily travel duration between the results of transit network scheduling optimization and single line separate scheduling optimization.Figure 8
The average daily charging duration of the battery chargers in each charging station under transit network scheduling and single line separate scheduling.


## 6.3.1. Comparison of the Overall Performance

The line-based optimization results are set as the benchmark for optimization result comparisons. The differences between the benchmark and proposed network level optimization results are presented in Tables8 and 9. Compared with scheduling 8 lines separately, the EB transit network scheduling saves over 3 million RMB in total cost, including the investment of 1 EB and 5 battery chargers, while the power consumption and time-related cost rise slightly.Table 8
Comparison of EB fleet size and charger deployment results.
Optimization scenarioNumber of EBsNumber of chargersCharging station no.12345Benchmark682576165Proposed model672065153Table 9
Comparison of total cost and 4 components of the total cost1.
Optimization scenarioEB fleet investmentCharger investmentPower consumptionTime-related costTotal costBenchmark102,000,00011,250,00011,958,39918,387,331143,595,730Proposed model100,500,0009,000,00012,373,51718,643,288140,516,8051Unit: RMB.


## 6.3.2. Comparison of the Utilization of EB and Chargers

Transit network scheduling can improve both the utilization of the EB fleet and battery chargers. After sorting EBs in descending order of the travel duration, we make the difference of travel duration for the first 67 EBs and plot the empirical cumulative distribution function as shown in Figure7. It is indicated that over 70% EBs’ travel duration in transit network optimization surpasses that in single line separate optimization. In terms of the utilization of battery chargers, the average daily charging duration of the battery chargers under transit network scheduling and single line scheduling is 737.79 and 582.13 minutes, respectively. Figure 8 illustrates that there is less variation in the average daily charging duration of the battery chargers across charging stations under transit network dispatch than that under single line dispatch. So, EB scheduling and charger deploying at the transit network level can also equalize the depletion of stationary chargers.Figure 7
Difference in EB daily travel duration between the results of transit network scheduling optimization and single line separate scheduling optimization.Figure 8
The average daily charging duration of the battery chargers in each charging station under transit network scheduling and single line separate scheduling.


## 7. Conclusions and Future Research

EB transit system has been regarded as a promising means of transportation for reducing traffic congestion, air pollution, and traffic which cities suffered. To promote the electrification of the public transport system, progress has been made in EB scheduling problem and charging infrastructure planning. Unfortunately, most of the previous research has not considered the joint optimization of these two aspects especially at the transit network level. To fill this gap, we introduce a mathematical model for the SCD-MDVSP of the regular charging EB transit network. The objective of this model is to minimize the overall construction and operation cost of an EB transit system considering partial charging policy and time-varying electric prices. Accordingly, a solving procedure based on the improved AGA is proposed. The proposed model and solving procedure are applied to the inner Anting Town bus transit network with 8 individual bus routes and 867 daily service trips as a case study. The results validated the effectiveness of the approach and illustrated that the methodology considering the partial charging policy can arrange the charging schedule adaptive to the time-of-use electricity prices. Moreover, it can be drawn from the comparison between the model results and line-based optimization results that EB scheduling and charger deploying at the transit network level can improve the utilization of both EB and stationary chargers and make the charging tasks of chargers more evenly allocated. Since the modeling scenario is well suited to the reality, the proposed methodology can provide practical support for developing the EB transit system planning.Similar to other methodological studies, this study has its own limitations. First, the model does not consider the volatility of bus travel time. Second, the EB battery charging and discharging characteristics vary with weather and seasons, so the EB scheduling plan may need to be adjusted accordingly. Third, due to the integer property of most decision variables and several complicated constraints, the mathematical model is nonconvex, which makes it hard for the proposed solving procedure to reach the global optimal solution. Meanwhile, the convergence speed and searching efficiency of the AGA are not so satisfactory that the computational cost will increase rapidly with the growth of the bus network. Therefore, an innovative algorithm offering higher computational efficiency and large-scale network adaptability would be a direction for future studies.



---

*Source: 8863905-2020-12-21.xml*