# Optimal Charging Scheduling and Management with Bus-Driver-Trip Assignment considering Mealtime Windows for an Electric Bus Line

Authors: Yang Jiang; Tong He
Journal: Complexity
 (2022)

---

## Abstract

Compared to a charging scheduling and management problem characterized by predetermined trip assignment, this study takes bus and driver scheduling into account, and mealtime windows must be guaranteed as one of the major labor regulations. A discretized mixed-integer linear programming (MIPL) model is developed based on a single electric bus route. We aim to obtain fast and high-quality global solutions for this problem, and the model can be easily executed by bus operators by directly invoking an available optimization solver such as IBM ILOG CPLEX. We test our model on a real round-trip bus route. Numerical experiments show that CPLEX takes approximately 6 sec to obtain an optimal solution. The model can not only reasonably arrange daily trips for each electric bus and driver but also effectively determine the optimal charging schedule and management for an electric bus line. Besides, we analyze the sensitivity of the key parameters in the model. With the increase in the drivers’ maximum workload, the drivers’ average idle time decreases by approximately 11.25%. The objective value decreases by approximately 38.71% and 40.04% with increases in the battery capacity and fleet size, respectively, and the objective value increases by approximately 30.06% with the decrease in the initial battery driving range. In addition, we compare the effectiveness of our time discretization modeling method in solving the same case study to that from other similar studies, and the validity of our method can be verified by the calculation time. We also compare the computational efficiency of CPLEX in solving the same case study problem with and without implementing valid inequalities, and the computational efficiency of the valid inequality method is greatly improved. Finally, through the testing of a multiline network, the potential application of the model to a large-scale traffic network is verified.


---

## Body

## 1. Introduction

Increasingly serious air pollution has led to the popularity of using clean energy, such as the use of electric vehicles (Kafaei et al. [1]). As an important part of the urban transport system, urban public transport plays an important role in easing congestion, saving energy, reducing emissions, and improving air quality. It has become the consensus of society as a whole to vigorously develop public transport (Kang and Meng [2]; Janacek et al. [3]; Zhang et al. [4]). Especially in some larger cities, new-energy vehicles are gradually replacing traditional diesel vehicles, and green travel has become a new concept advocated by the government (Chediak et al. [5]). For example, electric buses were used during the 2008 Olympic Games in Beijing, the 2010 World Expo in Shanghai, and the Asian Games in Guangzhou (Pelletier et al. [6]).There are many factors that influence the efficiency of bus services, such as government policies, operations management, vehicle technology and so on (Ibarra-Rojas et al. [7]). As one of the main processes of bus operation, the purpose of bus and driver scheduling is to determine the optimal bus and driver schedule in accordance with labor laws and regulations for a given group of bus lines (Kang et al. [8]). The NP-hard characteristic of the scheduling process makes it difficult for bus operators to follow and execute in real-world scenarios (Paleti et al. [9]). This is especially true for electric bus promotion and management, which is hindered by more existing limitations, such as limited driving range, insufficient chargers, and long recharging durations (Amirhosseini and Hosseini [10]; Langbroek et al. [11]). In other words, it is difficult to optimally solve the bus and driver scheduling problem in the real-scale case, especially with practical regulations and constraints. Among them, arranging necessary mealtimes and recharging duration are important for bus operators. For example, it is necessary to take into account the lunch and evening mealtimes of bus drivers and ensure that drivers have enough rest time. Similarly, the driving range for electric buses requiring optimal recharging should be considered in the vehicle scheduling process. The maximum driving range of most electric buses in the market is reduced by 65% compared with diesel buses, which means that it is challenging to realize continuous driving without charging during the operation of electric buses (Mohamed et al. [12]).


### 1.1. Related Literature

Based on the number of bus depots, the bus scheduling problem can be divided into a single-depot vehicle scheduling problem (SDVSP) or a multidepot vehicle scheduling problem (MDVSP) (Xu et al. [13]). In the modeling process, the bus scheduling problem is often formulated as integer linear programming (ILP), and the SDVSP is often described as an assignment problem and a network flow problem (Árgilán et al. [14]; Freling et al. [15]). The MDVSP can be mainly divided into a multicommodity flow model and a set segmentation model. This refers to the fact that buses are located at multiple bus depots and allowed to execute the task of different bus routes, which is an expansion of the SDVSP. Multicommodity flows with fixed departure, arrival time and place (Bertossi et al. [16]) and setting a segmentation model based on a feasible train order chain (Oukil et al. [17]) are the most common methods to deal with the MDVSP. The model-solving algorithms include the heuristic algorithm (Wang and Shen [18]; Ramli et al. [19]), column generation algorithm (Lin and Hsu [20]), search tree method (Ma et al. [21]), branch-and-price (Chu et al. [22]; Goel and Irnich [23]), etc., but most of them can only be used to solve small-scale problems, and the heuristic algorithm is still an important method to solve the problem of bus scheduling.Compared to the conventional bus scheduling problem, electric bus research has been extended to several fields, and fruitful results have been obtained, including an introduction to electric bus applications (Hua et al. [24]; Mahmoud et al. [25]; Sebastiani et al. [26]), random behavior of electric vehicles (Sedighizadeh et al. [27]), battery property analysis and charging methods (Arif et al. [28]; Li et al. [29]; Lajunen and Lipman [30]), and optimal energy management of electric vehicles (Sedighizadeh et al. [31]; Ke et al. [32]; Qin et al. [33]). To solve the integration problem of renewable distributed power sources, Arif et al. [34] proposed a cost-effective energy management system based on a bilateral auction mechanism. Arif proposed a mixed-integer linear programming model (MILP) and analyzed it by using IBM ILOG studio with the CPLEX solver. The electric bus scheduling problem is more complicated and not only needs to meet the constraints of conventional bus scheduling but also needs to consider the limits of driving distance and recharging time (Yao et al. [35]). Teng et al. [36] established a multiobjective optimization model of a single electric bus line including the driving range and recharging duration and adopted a multiobjective particle swarm optimization algorithm to solve the model. Some highlights of the electric bus recharging scheduling model building will be reviewed below. To solve the negative impact brought by the unlimited charging of plug-in electric buses (PEBs) in bus depots, Arif et al. [37] proposed an MILP model and analyzed it by using IBM ILOG studio with the CPLEX solver. A discretizing method and a linear reformulation are used by He et al. [38] in a fast-charging electric bus system including multiple bus lines to obtain the optimal recharging management. A slight simplification of this study has a predetermined matching relationship, that is, trips in which the buses performed in the timetable are given in advance. Wang et al. [39] proposed a scheduling method based on dynamic programming to minimize the battery replacement cost of electric bus fleets and proved the effectiveness of the method in large-scale public bus transportation systems. We deal with bus and trip matching as part of the decision-making process in our research, which makes our research more practical. Wang et al. [40] proposed a modeling framework to optimize electric bus recharging scheduling based on a time discretization approach and proved the effectiveness of the model by using a real-world transit network. Our research also borrows this approach.However, it is more reasonable to consider the driver scheduling process in the vehicle scheduling environment, and an interesting research topic of vehicle and crew scheduling problems has been proposed (Sargut et al. [41]). For example, a time-space network was employed by Steinzen et al. [42] to improve the computational time and solution quality for the integrated vehicle and crew scheduling problem with multiple depots. The requirement of mealtimes in labor regulations is an important practical characteristic of the bus and driver scheduling problem (Lin and Hsu [20]; Kang et al. [8]), which needs to be highlighted. However, drivers are allowed to eat anytime while on duty, which is different from reality. In view of this, different improvement methods are proposed to handle mealtime windows. For example, Chen et al. [43] proposed a forward and backward search method to generate a task sequence suitable for a mealtime window. Kang et al. [8] determined the mealtimes with an identification strategy based on the start and end times of a pair of consecutive trips associated with the mealtime window. As an extension of the bus and driver scheduling problem, the literature does not involve the bus and driver scheduling problem with mealtime windows, even for a traditional bus route. Moreover, further extensions of the electric bus scheduling problem, incorporating driver scheduling and mealtime windows, are hindered by the complexity caused by the charging process. Therefore, bus and driver scheduling problems with charging and mealtime windows for an electric bus line are worth studying, as they are both important and practical in reality. At the same time, many scholars solve similar problems by constructing an MILP model. The solution to an MILP model usually includes automatic search algorithms (Bagherzadeh et al. [44]; EISheikh et al. [45]), local search algorithms (Solano-Charris et al. [46]; Cacchiani et al. [47]), genetic algorithms (Cariou et al. [48]; Jankauskas et al. [49]; Fahmy [50]) and other heuristic algorithms (Song et al. [51]; Polli et al. [52]). In addition, many scholars use CPLEX to solve an MILP model (Meng et al. [53]; Renani et al. [54]). For example, Chen et al. [55] proposed a discrete-time mixed-integer linear programming model to optimize the detailed scheduling of a multiproduct pipeline and used CPLEX as a solver to prove the effectiveness of the model. Cheng et al. [56] proposed an improved MILP model minimizing the total electricity cost to solve the parallel machine scheduling problem under the time-of-use tariff by using CPLEX.Table1 lists the comparisons among the representative studies for mathematical modeling, algorithm design, charging scheduling and labor regulations.Table 1
Summary comparison of related studies considering different features.
StudyChargingLabor regulationsBus-driver-trip assignmentModelAlgorithmCharged during operation hoursCharged during nonoperation hoursLimited driving time for driversLimited number of trips for busesMandatory restsMealtime windowsTrip-bus assignmentTrip-driver assignmentPelletier and Jabali [6]√×××××√×ILPAggregated approachKang et al. [8]√×√√√√√√IPLCPLEX and Valid cutoffRamli and Ibrahim [19]××√×√××√IPGALin and Hsu [20]××√×××√√IPColumn generationMa and Ceder [21]××√×√×√√ILPVNSSebastiani et al. [26]√√××××××Discrete event simulationGAKe et al.[32]√√××××√×TSMGAYao et al.[35]√√××√×√√ILPGATeng et al. [36]√××√××√×MOMINLPPSOWang et al. [40]√×××××××MILPAMPL& CPLEXLaurent and Hao [57]×√√×××××SCGreedy adaptive searchChen and Liu [58]××√×××√×Nonlinear integer programmingABCLaporte et al. [59]××√×××√×IPMIP XpressUçar et al. [60]××√×××√×MIPILOG CPLEXXiong et al. [61]√×××××√×MIPGAMesquita and Paias [62]×√√×√×××SPBranch-and-boundLeone et al. [63]√×√√√×××SPmeta- heuristicBoyer et al. [64]×√√×√×××IPLVariable neighborhood searchThis study√√√√√√√√MILPCPLEX


### 1.2. Objective and Contributions

This study aims to develop a charging scheduling and management problem for a single electric bus route. Meanwhile, the interactive influence of bus and driver scheduling and charging management is discussed. Major vehicle characteristics and labor regulations are accommodated, such as mealtime windows, limited duty length, mandatory rests. Optimal charging scheduling incorporating bus-driver-trip assignment decisions is performed to assist bus operators.Our major contributions are stated in two aspects. First, we develop an explicit MILP model to optimize the bus and driver scheduling problem considering charging decisions and mealtime windows for an electric bus line. Vehicles entering the charging station at different times will have an impact on the charging duration and charging cost. Additionally, bus-driver-trip assignment decisions have an important effect on charging management. Therefore, bus and driver scheduling and charging decisions should be considered as a whole. To the best of our knowledge, bus and driver scheduling are rarely considered in the study of charging management for electric bus lines. Second, we conduct a numerical test based on a real-world bus line to demonstrate the proposed model and investigate the time discretization approach with representative research, which improves the computational efficiency of CPLEX. The framework of the study is shown in Figure1.Figure 1
Framework of the study.The rest of the paper is organized as follows. The problem description and notation definitions are presented in Section2. Section 3 provides an explicit MILP model. A case study is conducted in Section 4. Finally, we conclude this study in Section 5.


## 1.1. Related Literature

Based on the number of bus depots, the bus scheduling problem can be divided into a single-depot vehicle scheduling problem (SDVSP) or a multidepot vehicle scheduling problem (MDVSP) (Xu et al. [13]). In the modeling process, the bus scheduling problem is often formulated as integer linear programming (ILP), and the SDVSP is often described as an assignment problem and a network flow problem (Árgilán et al. [14]; Freling et al. [15]). The MDVSP can be mainly divided into a multicommodity flow model and a set segmentation model. This refers to the fact that buses are located at multiple bus depots and allowed to execute the task of different bus routes, which is an expansion of the SDVSP. Multicommodity flows with fixed departure, arrival time and place (Bertossi et al. [16]) and setting a segmentation model based on a feasible train order chain (Oukil et al. [17]) are the most common methods to deal with the MDVSP. The model-solving algorithms include the heuristic algorithm (Wang and Shen [18]; Ramli et al. [19]), column generation algorithm (Lin and Hsu [20]), search tree method (Ma et al. [21]), branch-and-price (Chu et al. [22]; Goel and Irnich [23]), etc., but most of them can only be used to solve small-scale problems, and the heuristic algorithm is still an important method to solve the problem of bus scheduling.Compared to the conventional bus scheduling problem, electric bus research has been extended to several fields, and fruitful results have been obtained, including an introduction to electric bus applications (Hua et al. [24]; Mahmoud et al. [25]; Sebastiani et al. [26]), random behavior of electric vehicles (Sedighizadeh et al. [27]), battery property analysis and charging methods (Arif et al. [28]; Li et al. [29]; Lajunen and Lipman [30]), and optimal energy management of electric vehicles (Sedighizadeh et al. [31]; Ke et al. [32]; Qin et al. [33]). To solve the integration problem of renewable distributed power sources, Arif et al. [34] proposed a cost-effective energy management system based on a bilateral auction mechanism. Arif proposed a mixed-integer linear programming model (MILP) and analyzed it by using IBM ILOG studio with the CPLEX solver. The electric bus scheduling problem is more complicated and not only needs to meet the constraints of conventional bus scheduling but also needs to consider the limits of driving distance and recharging time (Yao et al. [35]). Teng et al. [36] established a multiobjective optimization model of a single electric bus line including the driving range and recharging duration and adopted a multiobjective particle swarm optimization algorithm to solve the model. Some highlights of the electric bus recharging scheduling model building will be reviewed below. To solve the negative impact brought by the unlimited charging of plug-in electric buses (PEBs) in bus depots, Arif et al. [37] proposed an MILP model and analyzed it by using IBM ILOG studio with the CPLEX solver. A discretizing method and a linear reformulation are used by He et al. [38] in a fast-charging electric bus system including multiple bus lines to obtain the optimal recharging management. A slight simplification of this study has a predetermined matching relationship, that is, trips in which the buses performed in the timetable are given in advance. Wang et al. [39] proposed a scheduling method based on dynamic programming to minimize the battery replacement cost of electric bus fleets and proved the effectiveness of the method in large-scale public bus transportation systems. We deal with bus and trip matching as part of the decision-making process in our research, which makes our research more practical. Wang et al. [40] proposed a modeling framework to optimize electric bus recharging scheduling based on a time discretization approach and proved the effectiveness of the model by using a real-world transit network. Our research also borrows this approach.However, it is more reasonable to consider the driver scheduling process in the vehicle scheduling environment, and an interesting research topic of vehicle and crew scheduling problems has been proposed (Sargut et al. [41]). For example, a time-space network was employed by Steinzen et al. [42] to improve the computational time and solution quality for the integrated vehicle and crew scheduling problem with multiple depots. The requirement of mealtimes in labor regulations is an important practical characteristic of the bus and driver scheduling problem (Lin and Hsu [20]; Kang et al. [8]), which needs to be highlighted. However, drivers are allowed to eat anytime while on duty, which is different from reality. In view of this, different improvement methods are proposed to handle mealtime windows. For example, Chen et al. [43] proposed a forward and backward search method to generate a task sequence suitable for a mealtime window. Kang et al. [8] determined the mealtimes with an identification strategy based on the start and end times of a pair of consecutive trips associated with the mealtime window. As an extension of the bus and driver scheduling problem, the literature does not involve the bus and driver scheduling problem with mealtime windows, even for a traditional bus route. Moreover, further extensions of the electric bus scheduling problem, incorporating driver scheduling and mealtime windows, are hindered by the complexity caused by the charging process. Therefore, bus and driver scheduling problems with charging and mealtime windows for an electric bus line are worth studying, as they are both important and practical in reality. At the same time, many scholars solve similar problems by constructing an MILP model. The solution to an MILP model usually includes automatic search algorithms (Bagherzadeh et al. [44]; EISheikh et al. [45]), local search algorithms (Solano-Charris et al. [46]; Cacchiani et al. [47]), genetic algorithms (Cariou et al. [48]; Jankauskas et al. [49]; Fahmy [50]) and other heuristic algorithms (Song et al. [51]; Polli et al. [52]). In addition, many scholars use CPLEX to solve an MILP model (Meng et al. [53]; Renani et al. [54]). For example, Chen et al. [55] proposed a discrete-time mixed-integer linear programming model to optimize the detailed scheduling of a multiproduct pipeline and used CPLEX as a solver to prove the effectiveness of the model. Cheng et al. [56] proposed an improved MILP model minimizing the total electricity cost to solve the parallel machine scheduling problem under the time-of-use tariff by using CPLEX.Table1 lists the comparisons among the representative studies for mathematical modeling, algorithm design, charging scheduling and labor regulations.Table 1
Summary comparison of related studies considering different features.
StudyChargingLabor regulationsBus-driver-trip assignmentModelAlgorithmCharged during operation hoursCharged during nonoperation hoursLimited driving time for driversLimited number of trips for busesMandatory restsMealtime windowsTrip-bus assignmentTrip-driver assignmentPelletier and Jabali [6]√×××××√×ILPAggregated approachKang et al. [8]√×√√√√√√IPLCPLEX and Valid cutoffRamli and Ibrahim [19]××√×√××√IPGALin and Hsu [20]××√×××√√IPColumn generationMa and Ceder [21]××√×√×√√ILPVNSSebastiani et al. [26]√√××××××Discrete event simulationGAKe et al.[32]√√××××√×TSMGAYao et al.[35]√√××√×√√ILPGATeng et al. [36]√××√××√×MOMINLPPSOWang et al. [40]√×××××××MILPAMPL& CPLEXLaurent and Hao [57]×√√×××××SCGreedy adaptive searchChen and Liu [58]××√×××√×Nonlinear integer programmingABCLaporte et al. [59]××√×××√×IPMIP XpressUçar et al. [60]××√×××√×MIPILOG CPLEXXiong et al. [61]√×××××√×MIPGAMesquita and Paias [62]×√√×√×××SPBranch-and-boundLeone et al. [63]√×√√√×××SPmeta- heuristicBoyer et al. [64]×√√×√×××IPLVariable neighborhood searchThis study√√√√√√√√MILPCPLEX


## 1.2. Objective and Contributions

This study aims to develop a charging scheduling and management problem for a single electric bus route. Meanwhile, the interactive influence of bus and driver scheduling and charging management is discussed. Major vehicle characteristics and labor regulations are accommodated, such as mealtime windows, limited duty length, mandatory rests. Optimal charging scheduling incorporating bus-driver-trip assignment decisions is performed to assist bus operators.Our major contributions are stated in two aspects. First, we develop an explicit MILP model to optimize the bus and driver scheduling problem considering charging decisions and mealtime windows for an electric bus line. Vehicles entering the charging station at different times will have an impact on the charging duration and charging cost. Additionally, bus-driver-trip assignment decisions have an important effect on charging management. Therefore, bus and driver scheduling and charging decisions should be considered as a whole. To the best of our knowledge, bus and driver scheduling are rarely considered in the study of charging management for electric bus lines. Second, we conduct a numerical test based on a real-world bus line to demonstrate the proposed model and investigate the time discretization approach with representative research, which improves the computational efficiency of CPLEX. The framework of the study is shown in Figure1.Figure 1
Framework of the study.The rest of the paper is organized as follows. The problem description and notation definitions are presented in Section2. Section 3 provides an explicit MILP model. A case study is conducted in Section 4. Finally, we conclude this study in Section 5.


## 2. Problem Description

The problem is defined based on a given electric bus route timetable, and trips in the timetable must be completed by electric buses and drivers considering necessary charging, mealtime windows and other labor regulations. A trip is defined as a round-trip journey here, which means that the bus departs from one terminus and returns to the same terminus according to the timetable. Figure2 describes a charging scheduling problem with bus-driver-trip assignment considering mealtime windows, and the problem can be expressed in detail as follows. For the convenience of introduction, the symbols used in this study are given in the Appendix.Time Interval. We discretize the study period into several small time intervals. The time discretization approach has been widely used and has received good results. For example, the time interval selected by Shao et al. [65] is 1 hour in their reservation and allocation of shared parking problems. Wang et al. [40] used a set of time nodes to indicate the start time of the earliest trip and the end time of the latest trip in an urban electric bus charging scheduling problem. In our study, we define K as the total number of time intervals, and each time interval is defined by k∈1,K. We divide K into Kon and Koff, which represent operation hours and nonoperation hours, respectively.Trips. Trips in set T=i|i=1,2,…,n are all extracted from a predetermined bus timetable. The round-trip i is associated with a start time and an end time, namely, tis∈1,K and tie∈1,K. The duration of trip i can be calculated by tie−tis+1. A binary indicator rik is introduced, which is equal to 1 if bus trip i includes time interval k and 0 otherwise.Buses. The electric buses in our study are consistent and represented by set V=v|v=1,2,…,r. A binary indicator svk is introduced to denote the duty time of bus v. If electric bus v provides service in time interval k, svk=1; otherwise, svk=0.Drivers. Let D=d|d=1,2,…,m be the set of bus drivers. tds∈1,K and tde∈1,K indicate the start and end times of his or her duty, respectively. We introduce a binary indicator sdk, which is defined to be 1 if driver d is on duty in time interval k and 0 otherwise.Mealtime Windows. Drivers need a mealtime if their working hours cover lunch time. The start and end times of mealtime at noon are defined by tlunchs and tlunche, respectively. We deal with mealtime windows TL=u=|u=1,2,…,U implicitly as several exclusive lunch tasks at noon. They are sorted sequentially, and the start time of each task is incremented in units of one time interval. They have a consistent duration. The start and end times of u are defined as tus and tue. We introduce a binary indicator rmuk that is defined to be 1 if u includes time interval k and 0 otherwise.Battery Capacity. It is assumed that the minimum remaining power of a battery is 20% after an electric bus is fully charged. λ represents the maximum driving range for a fully charged electric bus, in km. λ0 represents the extended driving distance using the minimum energy for an electric bus, in km.Figure 2
Bus and driver scheduling with charging and mealtime windows.Assumptions:(i)
All electric buses are of the same type and have the same driving range under full charge. All charging facilities are the same type.(ii)
The driver and electric bus can combine freely.(iii)
The power consumption is directly proportional to the driving range; the charging rate is proportional to the charging duration.


## 3. Mathematical Model

A mixed-integer programming model is developed to solve the electric bus and driver scheduling problem with charging and mealtime windows. Several decisions are made. First, the optimal driver-trip assignment decisions are made, and we setyid=1 if trip i is assigned to driver d and yid=0 otherwise. zd=1 if driver d is on duty, and zd=0 otherwise. In addition, xiv=1 if trip i is completed by electric bus v. zv=1 if electric bus v is used, and zv=0 otherwise. Third, a binary variable fdu is introduced; fdu=1 if driver d begins his or her meal at time interval tus, and fdu=0 otherwise. Moreover, to facilitate the measurement of driver idle times, we introduce another decision variable αijd. Let αijd=1 if after driver d handle trip i just before trip j. Similarly, βijv=1 if after bus v completes trip i, it immediately prepares to execute trip j. Finally, chvk=1 if bus v is charged in time interval k, and Evk represents the extended driving distance of bus v using the remaining energy in time interval k.


### 3.1. Objective Function

The objective is to minimize the daily cost shown as (1), which consists of the following two components: charging cost and drivers’ idle time cost.(1)C=minC1+C2.The charging cost consists of two components: charging cost during operation hours and charging cost during nonoperation hours. The charging cost is given as follows:(2)C1=∑v∈V∑k∈Konπon⋅chvk+∑v∈V∑k∈Koffπoff⋅chvk.The drivers’ idle time cost can be calculated as:(3)C2=∑i∈T∑j∈T,j>i∑d∈Dtjs−tie−1⋅l−Δ⋅ω⋅αijd.


### 3.2. Constraints

Constraints mainly include three aspects, which limit drivers, electric buses and charging management. The related constraints are as follows:Constraints for drivers: first, we put forward relevant constraints on a driver’s workload, lunch schedule and trip arrangement. The constraints are presented as follows:(4)∑i∈Tyid⋅rik+∑u∈TLfdu⋅rmuk≤zd⋅sdk,∀k∈Kon,∀d∈D,(5)zd−1⋅M≤∑i∈Tyid−ε≤M⋅zd,∀d∈D,(6)zd⋅Ndmin≤∑i∈Tyid≤zd⋅Ndmax,∀d∈D,(7)∑d∈Dyid=1,∀i∈T,(8)∑u∈TLfdu=zd,∀d∈D,Constraint (4) ensures that each driver can only complete one trip in each time interval, and a driver cannot be assigned any trip during his or her mealtime window. Constraint (5) indicates the relationship between variables yid and zd. Constraint (6) sets limits on the number of trips for each driver every day. Constraint (7) requires that any trip be completed. Constraint (8) schedules every driver on duty a mealtime.Moreover, a set of flow-balance constraints for drivers is given to measure the idle time of drivers.(9)∑i=0nαijd=yjd,∀j∈T,∀d∈D,(10)∑i=0nαijd=yjd,∀j∈T,∀d∈D,(11)∑d=1m∑i=1n+1αjid=1,∀j∈T,(12)tjs−tie−Δ⋅αijd≥0,∀i,j∈T,∀d∈D,(13)∑d=1mαijd≤1,∀i,j∈T,(14)∑j=1n+1αijd−∑j=0nαjid=0,∀i∈T,∀d∈D,(15)∑j∈Tα0jd=zd,∀d∈D,(16)∑i∈Tαin+1d=zd,∀d∈D,(17)y0d=zd,∀d∈D,(18)yn+1d=zd,∀d∈D,(19)yid,zd,αijd∈0,1.Constraints (9)–(11) mean that any trip must be assigned to only one driver. Constraints (12)–(14) ensure that trips are completed by each driver in a reasonable order. Constraints (15)–(18) introduce the first virtual trip and the last virtual trip for each driver on duty. Constraint (19) defines variables.Constraints for electric buses: first, we put forward constraints on the trip-bus assignment and workload.(20)∑i∈Txiv⋅rik+chvk≤zv⋅svk,∀k∈Kon,∀v∈V,(21)zv⋅Nvmin≤∑i∈Txiv≤zv⋅Nvmax,∀v∈V,(22)zv−1⋅M≤∑i∈Txiv−ε≤M⋅zv,∀v∈V,(23)∑v∈Vxiv=1,∀i∈T.Constraint (20) ensures that the service time and charging time of each electric bus during the operation hours must be less than or equal to the available time of the electric bus. Constraint (21) sets limits on the number of trips per bus every day. Constraint (22) shows the relationship between xiv and zv. Constraint (23) means that any trip must be assigned to an electric bus.Similarly, a set of flow-balance constraints for the electric bus is given to defineβijv.(24)∑i=0nβijv=xjv,∀j∈T,∀v∈V,(25)∑v=1r∑i=0nβijv=1,∀j∈T,(26)∑v=1r∑i=1n+1βjiv=1,∀j∈T,(27)tjs−tie−ε⋅βijv≥0,∀i,j∈T,∀v∈V,(28)∑v=1rβijv≤1,∀i,j∈T,(29)∑j=1n+1βijv−∑j=0nβjiv=0,∀i∈T,∀v∈V,(30)∑j∈Tβ0jv=zv,∀v∈V,(31)∑i∈Tβin+1v=zv,∀v∈V,(32)x0v=zv,∀v∈V,(33)xn+1v=zv,∀v∈V,(34)xiv,zv,βijv∈0,1.Constraints (24)–(26) mean that any trip must be assigned to only one electric bus. Constraints (27)–(29) ensure that trips are completed by each electric bus in a reasonable order. Constraints (30)–(33) introduce the first virtual trip and the last virtual trip for each vehicle on duty. Constraint (34) defines variables. Similar constraints on drivers and buses can be found in the literature [8].Constraints for charging: constraints on the power consumption, minimum remaining power and initial power of the battery are given as follows:(35)Evk=Evk−1−∑i∈Txiv⋅μ⋅rik+θon⋅chvk,∀v∈V,∀k∈Kon,(36)Evk=Evk−1+θoff⋅chvk,∀v∈V,∀k∈Koff,(37)Evk≤λ⋅zv,∀v∈V,∀k∈K,(38)Evk≥λ0⋅zv,∀v∈V,∀k∈K,(39)Ev0=EvK,∀v∈V,(40)∑v∈Vchvk≤nmax,∀k∈K,(41)Evtis−1≤λ¯⋅β0iv+1−β0iv⋅λ¯,∀v∈V,∀i∈T,(42)Evtis−1≥λ¯⋅β0iv,∀v∈V,∀i∈T,(43)chvk∈0,1.Constraints (35)–(36) refer to energy conservation. Constraint (37) ensures that the electric power of an electric bus is not larger than the maximum power. Constraint (38) ensures that the remaining power of an electric bus is not less than the minimum power. Constraint (39) ensures that the state of charge can be conserved in a closed time loop. Constraint (40) specifies the maximum number of vehicles charging at the same time. The initial power is specified by Constraints (41) and (42). Constraint (43) defines the range of variable chvk. Similar constraints on electric bus charging management can be found in the literature [40].


### 3.3. Valid Inequality

There may be some implicit constraints that can strengthen the model and reduce the feasible solution space. We call these constraints valid inequalities. To obtain tighter formulations and break symmetry constraints, we add valid inequalities (44)–(48) to strengthen our model.(44)∑j∈Tβ0jv≤∑j∈Tβ0jv−1,∀v∈V\1,(45)xiv≤∑j∈T,j<ixjv−1,∀v∈V1,∀i∈T,(46)∑j∈Tα0jd≤∑j∈Tα0jd−1,∀d∈D1,(47)yid≤∑j∈T,j<iyjd−1,∀d∈D1,∀i∈T,(48)∑v∈Vchdk≤∑v∈Vchdk−1,∀k∈Koff.


## 3.1. Objective Function

The objective is to minimize the daily cost shown as (1), which consists of the following two components: charging cost and drivers’ idle time cost.(1)C=minC1+C2.The charging cost consists of two components: charging cost during operation hours and charging cost during nonoperation hours. The charging cost is given as follows:(2)C1=∑v∈V∑k∈Konπon⋅chvk+∑v∈V∑k∈Koffπoff⋅chvk.The drivers’ idle time cost can be calculated as:(3)C2=∑i∈T∑j∈T,j>i∑d∈Dtjs−tie−1⋅l−Δ⋅ω⋅αijd.


## 3.2. Constraints

Constraints mainly include three aspects, which limit drivers, electric buses and charging management. The related constraints are as follows:Constraints for drivers: first, we put forward relevant constraints on a driver’s workload, lunch schedule and trip arrangement. The constraints are presented as follows:(4)∑i∈Tyid⋅rik+∑u∈TLfdu⋅rmuk≤zd⋅sdk,∀k∈Kon,∀d∈D,(5)zd−1⋅M≤∑i∈Tyid−ε≤M⋅zd,∀d∈D,(6)zd⋅Ndmin≤∑i∈Tyid≤zd⋅Ndmax,∀d∈D,(7)∑d∈Dyid=1,∀i∈T,(8)∑u∈TLfdu=zd,∀d∈D,Constraint (4) ensures that each driver can only complete one trip in each time interval, and a driver cannot be assigned any trip during his or her mealtime window. Constraint (5) indicates the relationship between variables yid and zd. Constraint (6) sets limits on the number of trips for each driver every day. Constraint (7) requires that any trip be completed. Constraint (8) schedules every driver on duty a mealtime.Moreover, a set of flow-balance constraints for drivers is given to measure the idle time of drivers.(9)∑i=0nαijd=yjd,∀j∈T,∀d∈D,(10)∑i=0nαijd=yjd,∀j∈T,∀d∈D,(11)∑d=1m∑i=1n+1αjid=1,∀j∈T,(12)tjs−tie−Δ⋅αijd≥0,∀i,j∈T,∀d∈D,(13)∑d=1mαijd≤1,∀i,j∈T,(14)∑j=1n+1αijd−∑j=0nαjid=0,∀i∈T,∀d∈D,(15)∑j∈Tα0jd=zd,∀d∈D,(16)∑i∈Tαin+1d=zd,∀d∈D,(17)y0d=zd,∀d∈D,(18)yn+1d=zd,∀d∈D,(19)yid,zd,αijd∈0,1.Constraints (9)–(11) mean that any trip must be assigned to only one driver. Constraints (12)–(14) ensure that trips are completed by each driver in a reasonable order. Constraints (15)–(18) introduce the first virtual trip and the last virtual trip for each driver on duty. Constraint (19) defines variables.Constraints for electric buses: first, we put forward constraints on the trip-bus assignment and workload.(20)∑i∈Txiv⋅rik+chvk≤zv⋅svk,∀k∈Kon,∀v∈V,(21)zv⋅Nvmin≤∑i∈Txiv≤zv⋅Nvmax,∀v∈V,(22)zv−1⋅M≤∑i∈Txiv−ε≤M⋅zv,∀v∈V,(23)∑v∈Vxiv=1,∀i∈T.Constraint (20) ensures that the service time and charging time of each electric bus during the operation hours must be less than or equal to the available time of the electric bus. Constraint (21) sets limits on the number of trips per bus every day. Constraint (22) shows the relationship between xiv and zv. Constraint (23) means that any trip must be assigned to an electric bus.Similarly, a set of flow-balance constraints for the electric bus is given to defineβijv.(24)∑i=0nβijv=xjv,∀j∈T,∀v∈V,(25)∑v=1r∑i=0nβijv=1,∀j∈T,(26)∑v=1r∑i=1n+1βjiv=1,∀j∈T,(27)tjs−tie−ε⋅βijv≥0,∀i,j∈T,∀v∈V,(28)∑v=1rβijv≤1,∀i,j∈T,(29)∑j=1n+1βijv−∑j=0nβjiv=0,∀i∈T,∀v∈V,(30)∑j∈Tβ0jv=zv,∀v∈V,(31)∑i∈Tβin+1v=zv,∀v∈V,(32)x0v=zv,∀v∈V,(33)xn+1v=zv,∀v∈V,(34)xiv,zv,βijv∈0,1.Constraints (24)–(26) mean that any trip must be assigned to only one electric bus. Constraints (27)–(29) ensure that trips are completed by each electric bus in a reasonable order. Constraints (30)–(33) introduce the first virtual trip and the last virtual trip for each vehicle on duty. Constraint (34) defines variables. Similar constraints on drivers and buses can be found in the literature [8].Constraints for charging: constraints on the power consumption, minimum remaining power and initial power of the battery are given as follows:(35)Evk=Evk−1−∑i∈Txiv⋅μ⋅rik+θon⋅chvk,∀v∈V,∀k∈Kon,(36)Evk=Evk−1+θoff⋅chvk,∀v∈V,∀k∈Koff,(37)Evk≤λ⋅zv,∀v∈V,∀k∈K,(38)Evk≥λ0⋅zv,∀v∈V,∀k∈K,(39)Ev0=EvK,∀v∈V,(40)∑v∈Vchvk≤nmax,∀k∈K,(41)Evtis−1≤λ¯⋅β0iv+1−β0iv⋅λ¯,∀v∈V,∀i∈T,(42)Evtis−1≥λ¯⋅β0iv,∀v∈V,∀i∈T,(43)chvk∈0,1.Constraints (35)–(36) refer to energy conservation. Constraint (37) ensures that the electric power of an electric bus is not larger than the maximum power. Constraint (38) ensures that the remaining power of an electric bus is not less than the minimum power. Constraint (39) ensures that the state of charge can be conserved in a closed time loop. Constraint (40) specifies the maximum number of vehicles charging at the same time. The initial power is specified by Constraints (41) and (42). Constraint (43) defines the range of variable chvk. Similar constraints on electric bus charging management can be found in the literature [40].


## 3.3. Valid Inequality

There may be some implicit constraints that can strengthen the model and reduce the feasible solution space. We call these constraints valid inequalities. To obtain tighter formulations and break symmetry constraints, we add valid inequalities (44)–(48) to strengthen our model.(44)∑j∈Tβ0jv≤∑j∈Tβ0jv−1,∀v∈V\1,(45)xiv≤∑j∈T,j<ixjv−1,∀v∈V1,∀i∈T,(46)∑j∈Tα0jd≤∑j∈Tα0jd−1,∀d∈D1,(47)yid≤∑j∈T,j<iyjd−1,∀d∈D1,∀i∈T,(48)∑v∈Vchdk≤∑v∈Vchdk−1,∀k∈Koff.


## 4. Case Study

The model was applied to a round-trip suburban route served by electric buses in the city of Shenyang, China, as shown in Figure3. Thirty-four timetabled trips were completed by 8 electric buses and 10 drivers. According to the real data, the earliest start time of the bus line is 6:00 am, and the service end time is 7:00 pm. The time headway during peak hours is 15 minutes, and 30 minutes during nonpeak hours. One round-trip service is completed by each bus in one hour, and the length of one trip is 40 km. The maximum driving range and initial driving range of each electric bus are set to 150 km, and the lowest remaining driving range λ0 is set to 20% of the maximum driving range. We divide the 24 hours of a day into 96 time intervals, and one time interval represents 15 minutes. The operation hours cover 1 to 52 time intervals. Table 2 lists all the trips. πon is set to 3.25 CNY/min, and πoff is 1.3 CNY/min according to the literature [40]. The cost of idle time for driver ω is set to 0.65 CNY/min. μ is 10 km per time interval, θon is 20 km per time interval, and θoff is 10 km per time interval.Figure 3
A bidirectional public bus route in Shenyang (map from Baidu).Table 2
Timetable of the electric bus line.
Triptistie000114225336447558669771088119912101013111114121215131316141518151720161922172124182326192528202730212932223134233336243538253740263942274144284346294447304548314649324750334851344952355252The model in this paper can be directly solved using the CPLEX 12.4 optimization solver. The numerical experiments are carried out on a computer with 32 GB memory and a 2.40 GHz central processing unit (CPU) in a Windows 7 environment. There are 28,489 constraints and 24,303 variables (including 23,526 binary variables), and it takes approximately 6 sec of CPU time to solve the model.


### 4.1. Results and Discussion

#### 4.1.1. Optimal Bus-Driver-Trip Assignment

The schedule of the buses and drivers is shown together in Figure4. The horizontal axis represents the operation hours. The red dotted line indicates the driver’s mealtime window, which is from 11:30 to 13:30. As can be observed, 10 drivers can have the necessary mealtime. Rectangles in different colors represent trips. The number in rectangles, B1, …, B8, represents optimal matching between buses and trips. Rectangles in the same color indicate that these trips are completed by the same electric bus. The blank between two consecutive trips indicates necessary rest time and idle time. We do not set limits on the changeover times for drivers during their duty, so drivers and electric buses can combine freely. In addition, the driving time of each driver and the number of trips they undertake are analyzed in Figure 5. Drivers complete 1–6 trips per day with an average of 3.4 trips per driver.Figure 4
The optimal bus-driver-trip assignment.Figure 5
Driving time and the number of trips assigned to each driver.


#### 4.1.2. Analysis of the Electric Bus Battery Power

We describe the state of the charge over a 24-hour period in Figure6. This shows that the minimum remaining power of each bus is guaranteed. Optimal charging scheduling can ensure the operation of the electric bus line. However, the charging time and duration vary. This means that different buses may adopt different charging strategies. The general rule is that electric buses may be charged as long as the battery is about to be less than its minimum remaining power or not enough to complete the next trip. As shown in Figure 6(a), two different charging strategies are presented. Some electric buses are charged frequently during operation hours using their idle time to maintain a moderate battery level, such as electric buses B2, B3, B5, B6 and B7. Nevertheless, the other buses prefer to consume their power to the lower bound without charging, and they mainly rely on nonoperation hours to charge their batteries, as shown in Figure 6(b). Our optimal charging scheduling allows a combination of different charging strategies.Figure 6
State of the battery for electric buses in each time interval.
(a)(b)Furthermore, we analyze the relationship between charging time in operation hours and the total driving distance. The total driving distance of each electric bus is calculated by multiplying the corresponding route length by the number of trips, as shown in Figure7. This shows that the charging time is positively correlated with the total driving distance. The longer an electric bus travels, the more charging time it needs to be charged. This is because we assume that the power consumed is positively correlated with the distance. However, electric buses B1, B4, and B8 are not charged during operation hours because their driving distance (120 km) is less than the maximum driving range for a fully charged electric bus (150 km).Figure 7
Relationship between the total driving distance and charging time for each electric bus.


### 4.2. Sensitivity Analysis

In this section, a sensitivity analysis is carried out to analyze the impact of the maximum workload of the driver group and battery capacity, battery deterioration rate and the influence of fleet size on the objective value.


#### 4.2.1. The Maximum Workload of Drivers

To analyze the influence of the drivers’ maximum workload restriction, we relax Constraint (6) and test the driving time in the range of 4–9 hours (too small or too large driving time is impractical). The result is shown in Figure8. It is easy to understand that with the increase in drivers’ workload, the number of drivers gradually decreases and ultimately remains stable. However, the minimum number of drivers needed to complete the trips is almost certain. The average drivers’ idle time is also affected by workloads. As shown in Figure 8, when the maximum workload reaches a certain value, the average idle time of drivers is certain.Figure 8
Minimum number of drivers and average idle time under different workloads.


#### 4.2.2. Battery Capacity

The capacity of an electric bus battery determines the bus’s maximum driving range, which also affects the optimal charging scheduling. We set the driving range of the battery capacity to 100 km–500 km with a step size of 50 km and analyze the influence of the driving range of the battery capacity on the objective value. Figure9 shows the cost structures for different battery capacities. First, when the battery capacity increases from 100 km to 250 km, the objective value gradually decreases (i.e., from 51,382.5 CNY to 31,492.5 CNY). Second, when the battery capacity is between 250 km and 500 km, the objective value is stable at 31,492.5 CNY, and the cost of charging batteries is stable at 27,690 CNY. Third, when the battery capacity is 100 km–500 km, the cost of the idle time for drivers remains the same.Figure 9
Effect of different battery capacities on the objective value.When the battery capacity is low, electric buses need to charge their batteries frequently to maintain the lowest battery level. With the increase in battery capacity, electric buses can have a more flexible charging schedule. Specifically, if the battery capacity of electric buses is sufficient to complete subsequent trips, the electric buses will be charged less or even not at all during operation hours. When the battery capacity is high, better charging scheduling and management can be obtained. However, when the battery capacity is high enough, the flexibility of the charging time of the electric buses cannot be further improved.Furthermore, to illustrate the relationship between battery capacity and charging cost, the charging cost is divided into the charging cost during operation and nonoperation hours. Figure10 shows that when the battery capacity is low, the total charging cost decreases with increasing battery capacity. When the battery capacity is increased to 250 km and above, the total charging cost remains unchanged. Considering a time-of-use price scheme, the charging cost during nonoperation hours is much lower than that during operation hours. The charging cost during the operation hours gradually decreases, while the charging cost during the nonoperation hours gradually increases. Both remain unchanged when the battery capacity is set to 250 km.Figure 10
Effect of different battery capacities on charging cost.


#### 4.2.3. Initial Driving Range of Electric Buses

In the above analysis, it is assumed that the initial driving range of electric buses is the same as the maximum driving range (i.e.,λ=λ¯). Actually, there are different deterioration rates (i.e., 10%, 20%, ..., 50%). As the maximum driving range of vehicles is 150 km, considering battery deterioration, the corresponding initial driving ranges are 135 km, 120 km, 105 km, 90 km, and 75 km. The battery deterioration rate is set to 10–50%, and the results are shown in Figure 11. The charging cost and objective value gradually increase with increasing deterioration rate, while the cost of idle time for drivers remains unchanged. The charging cost is very sensitive to the battery deterioration rate. With the increase in battery deterioration rate, to complete the same number of trips, electric buses need to be charged more frequently during operation hours, and the charging time gradually increases, as shown in Figure 11.Figure 11
Effect of the initial driving range on the objective value and charging time during operation hours.


#### 4.2.4. Bus Fleet Size

We vary the electric bus fleet size to analyze the effects on the objective value, and the results are shown in Figure12. In the case of a small fleet size, the objective value is larger. With increasing fleet size, the objective value gradually decreases because the number of trips completed by each electric bus decreases. The total energy of electric buses is sufficient to complete the assigned trips. Therefore, during the operation hours, the number of electric buses that need to be charged decreases. Fewer buses need to be charged when the fleet size is large. Almost all electric buses require additional charging activities during operation hours when the bus fleet size is 5, which is the reason for the higher charging cost.Figure 12
Effect of the fleet size on the objective value and number of buses charged during operation hours.We divide the total charging cost into the charging cost during operation and nonoperation hours to present the details of the charging cost, as shown in Figure13. With increasing fleet size, the charging cost during operation hours gradually decreases because the initial power of the electric bus is sufficient for the electric bus to complete the assigned trips. Conversely, the charging cost during nonoperation hours gradually increases. Time-of-use pricing drives buses to charge batteries for a more favorable duration.Figure 13
Effect of the bus fleet size on the charging cost.


### 4.3. Computational Efficiency of CPLEX and Investigation of the Valid Inequality Approach

To verify the effectiveness of the time discretization approach by CPLEX, we compared our approach with reference [8]. To ensure the comparison is made under equal conditions, we carry out the same case according to reference [8]. Detailed information on the case study is shown in Table 3.Table 3
Detailed information of the corresponding case.
Bus timetable:6:15–18:30Mealtime window11:30–13:00Break time:5 minLunchtime length30 minBus fleet size:25 busesDriver group size30 driversBus task bounds:3–10 tripsDriver task bounds2–6 tripsNumber of trips:78 tripsA round-trip service time:100 min for peak hours; 80 min for nonpeak hoursPeak hours:6:00–8:30; 11:30–13:30; 16:30–18:00Headway time:4–8 min for peak hours; 8–10 min for nonpeak hoursWe divide our model into three types according to reference [8]. The public transport bus driver scheduling problem can be formulated as PTBDS, and the model binds the driver and the bus together. In addition, the public transport bus and driver scheduling problem can be formulated as PTB&DS. Buses and drivers are combined freely. The model imposes some practical constraints on the driver and bus, such as the driver’s workload, driver’s necessary rest time after each trip and bus’s workload. Finally, the bus and driver scheduling problem with mealtime windows can be formulated as PTB&DS-MTW. Based on the PTB&DS model, the model is subject to some additional practical constraints; for example, a driver cannot be assigned trips during mealtime, and a driver can have one meal at most.We run CPLEX 12.4 on a 2.40 GHz CPU with 32 GB desktop memory to solve the PTBDS, PTB&DS and PTB&DS-MTW models. The comparison results are shown in Table4. Our approach takes 3.16 sec of CPU time to solve the PTBDS model. CPLEX uses approximately 0.01 MB of RAM in this instance with a final gap of 0.0%. In addition, it takes 841.20 sec of CPU time to solve the PTB&DS model and 1,031.81 sec of CPU time to solve the PTB&DS-MTW model. According to reference [8], it takes 45,241 sec of CPU time and uses 30,825 MB of RAM to solve the PTBDS model. It takes 62,154 sec of CPU time to solve the PTB&DS model and 129,351 sec of CPU time to solve the PTB&DS-MTW model. The time discretization approach is more efficient in solving the PTBDS, PTB&DS and PTB&DS-MTW models.Table 4
Comparison of computational efficiency in solving the same case study.
RecordOur methodReference [8]Best integerBest boundGapCPU timeRAMBest integerBest boundGapCPU timeRAMPTBDS optimization results13060100%1.28 sec0.0 M62200100%6.54 sec0.01 M23063060.0%3.16 sec0.01 M3512264224.77%22.10 sec421.4 M3—————328429589.93%75.51 sec820.4 M4—————328432481.10%15,624 sec25,243 M5—————328432740.30%45,241 sec30,825 MPTB&DS optimization results19660100%2.61 sec0.01 M45830100%8.13 sec0.01 M28387826.68%29.17 sec3.43 M3864284426.40%30.30 sec314.1 M38367836.34%83.64 sec67.61 M346032805.20%210.32 sec1005.4 M48367885.74%124.16 sec276.92 M346033862.14%26,242 sec23,451 M58367905.50%841.20 sec1134.64 M346034520.23%62,154 sec31,501 MPTB&DS-MTW optimization results111440100%2.73 sec0.01 M38180100%8.21 sec0.01 M2106094410.94%45.08 sec34.73 M3626296818.15%18.54 sec26.8 M310249507.18%169.25 sec186.92 M3600323810.06%246.11 sec1621.4 M410149565.72%230.91 sec489.70 M360035022.72%23,102 sec12,415 M510109585.15%1031.81 sec1068.76 M360035880.33%129,351 sec31,008 MLet us further examine the performance of the time discretization approach by CPLEX in solving the PTBDS, PTB&DS and PTB&DS-MTW models. CPLEX performed with high efficiency in solving the PTBDS model. It only took 3.16 sec and exhausted 0.01 MB of RAM to solve the PTBDS model. However, CPLEX performed with high efficiency during the first 29 sec in solving the PTB&DS model, reducing the gap from 100% to 6.68%. After that, the calculation efficiency decreased significantly, and it took more than 812 sec to reduce the gap from 6.68% to 5.50%. For the PTB&DS-MTW model, the computational efficiency also exhibits a phenomenon of high-to-low. First, CPLEX reduced the gap from 100% to 10.94% in 46 sec in solving the PTB&DS-MTW model. However, it took nearly 986 sec to reduce the gap from 10.94% to 5.15%. In view of this, a valid inequality approach is developed, and subsequent investigations need to be conducted.We compared the computational efficiency with and without the valid inequality approach in solving the same case study in reference [8], and the results are shown in Table 5. After adding valid inequalities, it took 1.12 sec of CPU time to solve the PTBDS model. In addition, it took 37.08 sec of CPU time to solve the PTB&DS model and 45.92 sec of CPU time to solve the PTB&DS-MTW model in our study. Compared with using only CPLEX to solve the above three models, the computational efficiency of the effective inequality method is improved by 64.56%, 95.59% and 95.55%, respectively, as shown in Figure 14.Table 5
Investigation of the valid inequality approach.
ModelValid inequalityGap (%)CPU time (sec)PTBDS×0.03.16√0.01.12PTB&DS×5.50841.20√0.037.08PTB&DS-MTW×5.151031.81√0.045.92Figure 14
Computational efficiency improvement.


### 4.4. Multiline Bus Route Network

To further test the proposed model on a large-scale bus network, we consider a multiline bus system, including 3 bus lines, 104 trips, 30 electric buses and 40 drivers. Other parameter data are the same as those in Section4.1.For a multiline bus network, the model has 780,466 constraints and 755,941 variables. It is solved using CPLEX 12.4, and the numerical experiments are carried out on a laptop with 32 GB memory and a 2.4 GHz CPU in a Windows 7 environment. The model can be solved successfully in a reasonable time, and the objective value is 169,260 CNY. In a multiline network, all trips are reasonably allocated to drivers and electric buses, and all electric buses are arranged to charge at the appropriate time. The proposed model can not only ensure the normal operation of an electric bus but also arrange the trip planning reasonably. The results show the potential application of the proposed model in large-scale public transport networks.


## 4.1. Results and Discussion

### 4.1.1. Optimal Bus-Driver-Trip Assignment

The schedule of the buses and drivers is shown together in Figure4. The horizontal axis represents the operation hours. The red dotted line indicates the driver’s mealtime window, which is from 11:30 to 13:30. As can be observed, 10 drivers can have the necessary mealtime. Rectangles in different colors represent trips. The number in rectangles, B1, …, B8, represents optimal matching between buses and trips. Rectangles in the same color indicate that these trips are completed by the same electric bus. The blank between two consecutive trips indicates necessary rest time and idle time. We do not set limits on the changeover times for drivers during their duty, so drivers and electric buses can combine freely. In addition, the driving time of each driver and the number of trips they undertake are analyzed in Figure 5. Drivers complete 1–6 trips per day with an average of 3.4 trips per driver.Figure 4
The optimal bus-driver-trip assignment.Figure 5
Driving time and the number of trips assigned to each driver.


### 4.1.2. Analysis of the Electric Bus Battery Power

We describe the state of the charge over a 24-hour period in Figure6. This shows that the minimum remaining power of each bus is guaranteed. Optimal charging scheduling can ensure the operation of the electric bus line. However, the charging time and duration vary. This means that different buses may adopt different charging strategies. The general rule is that electric buses may be charged as long as the battery is about to be less than its minimum remaining power or not enough to complete the next trip. As shown in Figure 6(a), two different charging strategies are presented. Some electric buses are charged frequently during operation hours using their idle time to maintain a moderate battery level, such as electric buses B2, B3, B5, B6 and B7. Nevertheless, the other buses prefer to consume their power to the lower bound without charging, and they mainly rely on nonoperation hours to charge their batteries, as shown in Figure 6(b). Our optimal charging scheduling allows a combination of different charging strategies.Figure 6
State of the battery for electric buses in each time interval.
(a)(b)Furthermore, we analyze the relationship between charging time in operation hours and the total driving distance. The total driving distance of each electric bus is calculated by multiplying the corresponding route length by the number of trips, as shown in Figure7. This shows that the charging time is positively correlated with the total driving distance. The longer an electric bus travels, the more charging time it needs to be charged. This is because we assume that the power consumed is positively correlated with the distance. However, electric buses B1, B4, and B8 are not charged during operation hours because their driving distance (120 km) is less than the maximum driving range for a fully charged electric bus (150 km).Figure 7
Relationship between the total driving distance and charging time for each electric bus.


## 4.1.1. Optimal Bus-Driver-Trip Assignment

The schedule of the buses and drivers is shown together in Figure4. The horizontal axis represents the operation hours. The red dotted line indicates the driver’s mealtime window, which is from 11:30 to 13:30. As can be observed, 10 drivers can have the necessary mealtime. Rectangles in different colors represent trips. The number in rectangles, B1, …, B8, represents optimal matching between buses and trips. Rectangles in the same color indicate that these trips are completed by the same electric bus. The blank between two consecutive trips indicates necessary rest time and idle time. We do not set limits on the changeover times for drivers during their duty, so drivers and electric buses can combine freely. In addition, the driving time of each driver and the number of trips they undertake are analyzed in Figure 5. Drivers complete 1–6 trips per day with an average of 3.4 trips per driver.Figure 4
The optimal bus-driver-trip assignment.Figure 5
Driving time and the number of trips assigned to each driver.


## 4.1.2. Analysis of the Electric Bus Battery Power

We describe the state of the charge over a 24-hour period in Figure6. This shows that the minimum remaining power of each bus is guaranteed. Optimal charging scheduling can ensure the operation of the electric bus line. However, the charging time and duration vary. This means that different buses may adopt different charging strategies. The general rule is that electric buses may be charged as long as the battery is about to be less than its minimum remaining power or not enough to complete the next trip. As shown in Figure 6(a), two different charging strategies are presented. Some electric buses are charged frequently during operation hours using their idle time to maintain a moderate battery level, such as electric buses B2, B3, B5, B6 and B7. Nevertheless, the other buses prefer to consume their power to the lower bound without charging, and they mainly rely on nonoperation hours to charge their batteries, as shown in Figure 6(b). Our optimal charging scheduling allows a combination of different charging strategies.Figure 6
State of the battery for electric buses in each time interval.
(a)(b)Furthermore, we analyze the relationship between charging time in operation hours and the total driving distance. The total driving distance of each electric bus is calculated by multiplying the corresponding route length by the number of trips, as shown in Figure7. This shows that the charging time is positively correlated with the total driving distance. The longer an electric bus travels, the more charging time it needs to be charged. This is because we assume that the power consumed is positively correlated with the distance. However, electric buses B1, B4, and B8 are not charged during operation hours because their driving distance (120 km) is less than the maximum driving range for a fully charged electric bus (150 km).Figure 7
Relationship between the total driving distance and charging time for each electric bus.


## 4.2. Sensitivity Analysis

In this section, a sensitivity analysis is carried out to analyze the impact of the maximum workload of the driver group and battery capacity, battery deterioration rate and the influence of fleet size on the objective value.


### 4.2.1. The Maximum Workload of Drivers

To analyze the influence of the drivers’ maximum workload restriction, we relax Constraint (6) and test the driving time in the range of 4–9 hours (too small or too large driving time is impractical). The result is shown in Figure8. It is easy to understand that with the increase in drivers’ workload, the number of drivers gradually decreases and ultimately remains stable. However, the minimum number of drivers needed to complete the trips is almost certain. The average drivers’ idle time is also affected by workloads. As shown in Figure 8, when the maximum workload reaches a certain value, the average idle time of drivers is certain.Figure 8
Minimum number of drivers and average idle time under different workloads.


### 4.2.2. Battery Capacity

The capacity of an electric bus battery determines the bus’s maximum driving range, which also affects the optimal charging scheduling. We set the driving range of the battery capacity to 100 km–500 km with a step size of 50 km and analyze the influence of the driving range of the battery capacity on the objective value. Figure9 shows the cost structures for different battery capacities. First, when the battery capacity increases from 100 km to 250 km, the objective value gradually decreases (i.e., from 51,382.5 CNY to 31,492.5 CNY). Second, when the battery capacity is between 250 km and 500 km, the objective value is stable at 31,492.5 CNY, and the cost of charging batteries is stable at 27,690 CNY. Third, when the battery capacity is 100 km–500 km, the cost of the idle time for drivers remains the same.Figure 9
Effect of different battery capacities on the objective value.When the battery capacity is low, electric buses need to charge their batteries frequently to maintain the lowest battery level. With the increase in battery capacity, electric buses can have a more flexible charging schedule. Specifically, if the battery capacity of electric buses is sufficient to complete subsequent trips, the electric buses will be charged less or even not at all during operation hours. When the battery capacity is high, better charging scheduling and management can be obtained. However, when the battery capacity is high enough, the flexibility of the charging time of the electric buses cannot be further improved.Furthermore, to illustrate the relationship between battery capacity and charging cost, the charging cost is divided into the charging cost during operation and nonoperation hours. Figure10 shows that when the battery capacity is low, the total charging cost decreases with increasing battery capacity. When the battery capacity is increased to 250 km and above, the total charging cost remains unchanged. Considering a time-of-use price scheme, the charging cost during nonoperation hours is much lower than that during operation hours. The charging cost during the operation hours gradually decreases, while the charging cost during the nonoperation hours gradually increases. Both remain unchanged when the battery capacity is set to 250 km.Figure 10
Effect of different battery capacities on charging cost.


### 4.2.3. Initial Driving Range of Electric Buses

In the above analysis, it is assumed that the initial driving range of electric buses is the same as the maximum driving range (i.e.,λ=λ¯). Actually, there are different deterioration rates (i.e., 10%, 20%, ..., 50%). As the maximum driving range of vehicles is 150 km, considering battery deterioration, the corresponding initial driving ranges are 135 km, 120 km, 105 km, 90 km, and 75 km. The battery deterioration rate is set to 10–50%, and the results are shown in Figure 11. The charging cost and objective value gradually increase with increasing deterioration rate, while the cost of idle time for drivers remains unchanged. The charging cost is very sensitive to the battery deterioration rate. With the increase in battery deterioration rate, to complete the same number of trips, electric buses need to be charged more frequently during operation hours, and the charging time gradually increases, as shown in Figure 11.Figure 11
Effect of the initial driving range on the objective value and charging time during operation hours.


### 4.2.4. Bus Fleet Size

We vary the electric bus fleet size to analyze the effects on the objective value, and the results are shown in Figure12. In the case of a small fleet size, the objective value is larger. With increasing fleet size, the objective value gradually decreases because the number of trips completed by each electric bus decreases. The total energy of electric buses is sufficient to complete the assigned trips. Therefore, during the operation hours, the number of electric buses that need to be charged decreases. Fewer buses need to be charged when the fleet size is large. Almost all electric buses require additional charging activities during operation hours when the bus fleet size is 5, which is the reason for the higher charging cost.Figure 12
Effect of the fleet size on the objective value and number of buses charged during operation hours.We divide the total charging cost into the charging cost during operation and nonoperation hours to present the details of the charging cost, as shown in Figure13. With increasing fleet size, the charging cost during operation hours gradually decreases because the initial power of the electric bus is sufficient for the electric bus to complete the assigned trips. Conversely, the charging cost during nonoperation hours gradually increases. Time-of-use pricing drives buses to charge batteries for a more favorable duration.Figure 13
Effect of the bus fleet size on the charging cost.


## 4.2.1. The Maximum Workload of Drivers

To analyze the influence of the drivers’ maximum workload restriction, we relax Constraint (6) and test the driving time in the range of 4–9 hours (too small or too large driving time is impractical). The result is shown in Figure8. It is easy to understand that with the increase in drivers’ workload, the number of drivers gradually decreases and ultimately remains stable. However, the minimum number of drivers needed to complete the trips is almost certain. The average drivers’ idle time is also affected by workloads. As shown in Figure 8, when the maximum workload reaches a certain value, the average idle time of drivers is certain.Figure 8
Minimum number of drivers and average idle time under different workloads.


## 4.2.2. Battery Capacity

The capacity of an electric bus battery determines the bus’s maximum driving range, which also affects the optimal charging scheduling. We set the driving range of the battery capacity to 100 km–500 km with a step size of 50 km and analyze the influence of the driving range of the battery capacity on the objective value. Figure9 shows the cost structures for different battery capacities. First, when the battery capacity increases from 100 km to 250 km, the objective value gradually decreases (i.e., from 51,382.5 CNY to 31,492.5 CNY). Second, when the battery capacity is between 250 km and 500 km, the objective value is stable at 31,492.5 CNY, and the cost of charging batteries is stable at 27,690 CNY. Third, when the battery capacity is 100 km–500 km, the cost of the idle time for drivers remains the same.Figure 9
Effect of different battery capacities on the objective value.When the battery capacity is low, electric buses need to charge their batteries frequently to maintain the lowest battery level. With the increase in battery capacity, electric buses can have a more flexible charging schedule. Specifically, if the battery capacity of electric buses is sufficient to complete subsequent trips, the electric buses will be charged less or even not at all during operation hours. When the battery capacity is high, better charging scheduling and management can be obtained. However, when the battery capacity is high enough, the flexibility of the charging time of the electric buses cannot be further improved.Furthermore, to illustrate the relationship between battery capacity and charging cost, the charging cost is divided into the charging cost during operation and nonoperation hours. Figure10 shows that when the battery capacity is low, the total charging cost decreases with increasing battery capacity. When the battery capacity is increased to 250 km and above, the total charging cost remains unchanged. Considering a time-of-use price scheme, the charging cost during nonoperation hours is much lower than that during operation hours. The charging cost during the operation hours gradually decreases, while the charging cost during the nonoperation hours gradually increases. Both remain unchanged when the battery capacity is set to 250 km.Figure 10
Effect of different battery capacities on charging cost.


## 4.2.3. Initial Driving Range of Electric Buses

In the above analysis, it is assumed that the initial driving range of electric buses is the same as the maximum driving range (i.e.,λ=λ¯). Actually, there are different deterioration rates (i.e., 10%, 20%, ..., 50%). As the maximum driving range of vehicles is 150 km, considering battery deterioration, the corresponding initial driving ranges are 135 km, 120 km, 105 km, 90 km, and 75 km. The battery deterioration rate is set to 10–50%, and the results are shown in Figure 11. The charging cost and objective value gradually increase with increasing deterioration rate, while the cost of idle time for drivers remains unchanged. The charging cost is very sensitive to the battery deterioration rate. With the increase in battery deterioration rate, to complete the same number of trips, electric buses need to be charged more frequently during operation hours, and the charging time gradually increases, as shown in Figure 11.Figure 11
Effect of the initial driving range on the objective value and charging time during operation hours.


## 4.2.4. Bus Fleet Size

We vary the electric bus fleet size to analyze the effects on the objective value, and the results are shown in Figure12. In the case of a small fleet size, the objective value is larger. With increasing fleet size, the objective value gradually decreases because the number of trips completed by each electric bus decreases. The total energy of electric buses is sufficient to complete the assigned trips. Therefore, during the operation hours, the number of electric buses that need to be charged decreases. Fewer buses need to be charged when the fleet size is large. Almost all electric buses require additional charging activities during operation hours when the bus fleet size is 5, which is the reason for the higher charging cost.Figure 12
Effect of the fleet size on the objective value and number of buses charged during operation hours.We divide the total charging cost into the charging cost during operation and nonoperation hours to present the details of the charging cost, as shown in Figure13. With increasing fleet size, the charging cost during operation hours gradually decreases because the initial power of the electric bus is sufficient for the electric bus to complete the assigned trips. Conversely, the charging cost during nonoperation hours gradually increases. Time-of-use pricing drives buses to charge batteries for a more favorable duration.Figure 13
Effect of the bus fleet size on the charging cost.


## 4.3. Computational Efficiency of CPLEX and Investigation of the Valid Inequality Approach

To verify the effectiveness of the time discretization approach by CPLEX, we compared our approach with reference [8]. To ensure the comparison is made under equal conditions, we carry out the same case according to reference [8]. Detailed information on the case study is shown in Table 3.Table 3
Detailed information of the corresponding case.
Bus timetable:6:15–18:30Mealtime window11:30–13:00Break time:5 minLunchtime length30 minBus fleet size:25 busesDriver group size30 driversBus task bounds:3–10 tripsDriver task bounds2–6 tripsNumber of trips:78 tripsA round-trip service time:100 min for peak hours; 80 min for nonpeak hoursPeak hours:6:00–8:30; 11:30–13:30; 16:30–18:00Headway time:4–8 min for peak hours; 8–10 min for nonpeak hoursWe divide our model into three types according to reference [8]. The public transport bus driver scheduling problem can be formulated as PTBDS, and the model binds the driver and the bus together. In addition, the public transport bus and driver scheduling problem can be formulated as PTB&DS. Buses and drivers are combined freely. The model imposes some practical constraints on the driver and bus, such as the driver’s workload, driver’s necessary rest time after each trip and bus’s workload. Finally, the bus and driver scheduling problem with mealtime windows can be formulated as PTB&DS-MTW. Based on the PTB&DS model, the model is subject to some additional practical constraints; for example, a driver cannot be assigned trips during mealtime, and a driver can have one meal at most.We run CPLEX 12.4 on a 2.40 GHz CPU with 32 GB desktop memory to solve the PTBDS, PTB&DS and PTB&DS-MTW models. The comparison results are shown in Table4. Our approach takes 3.16 sec of CPU time to solve the PTBDS model. CPLEX uses approximately 0.01 MB of RAM in this instance with a final gap of 0.0%. In addition, it takes 841.20 sec of CPU time to solve the PTB&DS model and 1,031.81 sec of CPU time to solve the PTB&DS-MTW model. According to reference [8], it takes 45,241 sec of CPU time and uses 30,825 MB of RAM to solve the PTBDS model. It takes 62,154 sec of CPU time to solve the PTB&DS model and 129,351 sec of CPU time to solve the PTB&DS-MTW model. The time discretization approach is more efficient in solving the PTBDS, PTB&DS and PTB&DS-MTW models.Table 4
Comparison of computational efficiency in solving the same case study.
RecordOur methodReference [8]Best integerBest boundGapCPU timeRAMBest integerBest boundGapCPU timeRAMPTBDS optimization results13060100%1.28 sec0.0 M62200100%6.54 sec0.01 M23063060.0%3.16 sec0.01 M3512264224.77%22.10 sec421.4 M3—————328429589.93%75.51 sec820.4 M4—————328432481.10%15,624 sec25,243 M5—————328432740.30%45,241 sec30,825 MPTB&DS optimization results19660100%2.61 sec0.01 M45830100%8.13 sec0.01 M28387826.68%29.17 sec3.43 M3864284426.40%30.30 sec314.1 M38367836.34%83.64 sec67.61 M346032805.20%210.32 sec1005.4 M48367885.74%124.16 sec276.92 M346033862.14%26,242 sec23,451 M58367905.50%841.20 sec1134.64 M346034520.23%62,154 sec31,501 MPTB&DS-MTW optimization results111440100%2.73 sec0.01 M38180100%8.21 sec0.01 M2106094410.94%45.08 sec34.73 M3626296818.15%18.54 sec26.8 M310249507.18%169.25 sec186.92 M3600323810.06%246.11 sec1621.4 M410149565.72%230.91 sec489.70 M360035022.72%23,102 sec12,415 M510109585.15%1031.81 sec1068.76 M360035880.33%129,351 sec31,008 MLet us further examine the performance of the time discretization approach by CPLEX in solving the PTBDS, PTB&DS and PTB&DS-MTW models. CPLEX performed with high efficiency in solving the PTBDS model. It only took 3.16 sec and exhausted 0.01 MB of RAM to solve the PTBDS model. However, CPLEX performed with high efficiency during the first 29 sec in solving the PTB&DS model, reducing the gap from 100% to 6.68%. After that, the calculation efficiency decreased significantly, and it took more than 812 sec to reduce the gap from 6.68% to 5.50%. For the PTB&DS-MTW model, the computational efficiency also exhibits a phenomenon of high-to-low. First, CPLEX reduced the gap from 100% to 10.94% in 46 sec in solving the PTB&DS-MTW model. However, it took nearly 986 sec to reduce the gap from 10.94% to 5.15%. In view of this, a valid inequality approach is developed, and subsequent investigations need to be conducted.We compared the computational efficiency with and without the valid inequality approach in solving the same case study in reference [8], and the results are shown in Table 5. After adding valid inequalities, it took 1.12 sec of CPU time to solve the PTBDS model. In addition, it took 37.08 sec of CPU time to solve the PTB&DS model and 45.92 sec of CPU time to solve the PTB&DS-MTW model in our study. Compared with using only CPLEX to solve the above three models, the computational efficiency of the effective inequality method is improved by 64.56%, 95.59% and 95.55%, respectively, as shown in Figure 14.Table 5
Investigation of the valid inequality approach.
ModelValid inequalityGap (%)CPU time (sec)PTBDS×0.03.16√0.01.12PTB&DS×5.50841.20√0.037.08PTB&DS-MTW×5.151031.81√0.045.92Figure 14
Computational efficiency improvement.


## 4.4. Multiline Bus Route Network

To further test the proposed model on a large-scale bus network, we consider a multiline bus system, including 3 bus lines, 104 trips, 30 electric buses and 40 drivers. Other parameter data are the same as those in Section4.1.For a multiline bus network, the model has 780,466 constraints and 755,941 variables. It is solved using CPLEX 12.4, and the numerical experiments are carried out on a laptop with 32 GB memory and a 2.4 GHz CPU in a Windows 7 environment. The model can be solved successfully in a reasonable time, and the objective value is 169,260 CNY. In a multiline network, all trips are reasonably allocated to drivers and electric buses, and all electric buses are arranged to charge at the appropriate time. The proposed model can not only ensure the normal operation of an electric bus but also arrange the trip planning reasonably. The results show the potential application of the proposed model in large-scale public transport networks.


## 5. Conclusions

In this paper, an optimal charging scheduling and management problem considering bus and driver scheduling is proposed for an electric bus line. Major vehicle characteristics and multiple labor regulations, including mealtime windows, are considered in our model. A time discretization approach is adopted. The effectiveness of our model is verified using a case study. CPLEX can quickly solve the model in a short time using a valid inequality approach.The optimal results show that the model can not only reasonably arrange daily trips for each electric bus and driver but also effectively determine the optimal charging schedule and management for electric buses. In addition, we performed sensitivity analysis on the key parameters in the model. More specifically, with the increase in the drivers’ maximum workload, the driver’s average idle time decreases by approximately 11.25%. The objective value decreases by approximately 38.71% and 40.04% with the increase in battery capacity and fleet size, respectively, and the objective value increases by approximately 30.06% with the decrease in the initial battery driving range. In addition, we compared the effectiveness of the time discretization approach in solving the same case study. The validity of our method can be verified by the calculation time. The study also compared the computational efficiency of CPLEX in solving the same case study with and without valid inequalities. The computational efficiency can be greatly improved. Finally, through the test on a multiline bus route network, the model can be solved by CPLEX in a reasonable time, and the potential application of the model to a large-scale bus route network is verified.



---

*Source: 3087279-2022-03-17.xml*