# Regional Electric Bus Driving Plan Optimization Algorithm considering Charging Time Window

Authors: Yuhuan Liu; Enjian Yao; Muyang Lu; Ling Yuan
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

Currently, although pure electric buses have the advantage of environmental-friendly, its endurance mileage is insufficient and the charging pile is still far away from the actual demand, resulting in a more complicated scheduling. Given this, we studied the driving plan of a pure electric bus, aiming to support the promotion and application of the electric bus. Considering service quality, we built a regional pure electric bus driving plan model and designed an optimal solution based on packing idea and genetic algorithm, aiming at minimizing fleet size, charging facility, and empty driving mileage. We took the electric bus routes operated in a region of Beijing as an empirical example. Compared with the results from the greedy algorithm, we found that the total cost of 544 bus trips with tasks was reduced by 19.6%. Although the average empty driving mileage increased by approximately 20%, the number of pure electric bus vehicles and the required amount of charging infrastructure decreased by 19.7% and 33.3%, respectively. The cost of increasing empty driving mileage was lower than that of the reducing number of buses and charging facilities, indicating that the above three variables reached a balance, and the optimization algorithm is proved to be significantly effective.


---

## Body

## 1. Introduction

Transportation industry has long been regarded as one of the major sources of carbon emission and environmental pollution due to the following two main reasons: (1) high emission and pollution of fuel vehicles and (2) high energy consumption resulting from an unreasonable scheduling plan. Instead, the environmental-friendly electric bus becomes popular and, its proportion in public transports has increased gradually. Yet, due to an insufficient endurance mileage and a shortage of charging infrastructure currently, two main problems remain hindering the process of fuel bus replacement by pure electric buses: (1) The technical performance of pure electric bus vehicles does not match the operational requirements. The endurance mileage of pure electric buses is significantly lower than that of the fuel buses. Comparing with the operating organization of fuel bus vehicles, pure electric bus not only has the mileage range constraints in conducting mission trips, but also has the charging trips additionally. Therefore, the driving plan for pure electric buses is more complicated. (2) The speed of constructing charging piles could not keep pace with the speed of putting pure electric buses in use, resulting in the complexity of pure electric buses driving plan.There are several problems left to be solved currently, including solving the short mileage range of pure electric buses to adapt to the trend of developing electric public transport system and insufficient charging facilities, minimizing the number of electric buses, and seeking the optimization algorithm solution under the fact of the extreme large scale of the driving plan problem. Therefore, taking the above problems as the point, the paper carried out the research on the optimization of regional pure electric bus driving plan considering the charging pile quantity and the number of pure electric vehicles in a region and designed the optimization algorithm to realize the reasonable development of urban pure electric bus system.


## 2. Literature Review

In terms of bus scheduling model building, Wei et al. established a linear programming model for scheduling problems with time window constraints [1] and studied the relationship between regional bus scheduling and vehicle purchase plans. Situ studied the influence of timetable on the operational performance of the bus company and the passenger service quality [2]. Li et al. combined maximizing company’s benefits with minimizing the passenger’s waiting time as double objectives to optimize the timetable and conducted a hybrid intelligent algorithm to solve the problem [3]. Situ and Li et al. both balanced between the bus service quality and the bus company’s operational efficiency. Meng established a set partition model with a variable of vehicle-chain based on the space-time network [4]. Liebchen and Stiller considered the bus timetable affected by running late to achieve the optimization of departure interval and fleet size [5]. Sun et al. designed the Logit model to determine the transportation mode preferred by passengers [6]. Dai et al. established the departure frequency optimization model under the collaboration mode of multitype BRT vehicles [7]. Kliewer et al. applied the concept of time-space network to the problem of scheduling multistation bus driving plan for the first time [8]. Liu and Shen established a bilevel programming model between the timetable generation and vehicle scheduling in the bus scheduling system according to the regional bus scheduling mode [9].In terms of solving algorithm, the greedy algorithm has attracted much attention in recent years. Shi discussed the correspondence between vehicle scheduling and packing problem under the constraints of mileage range and proposed a method of applying the greedy algorithm to solve this problem [10]. Song took the two-dimensional bin-packing as the constraint and introduced the application of bin-packing thought, greedy algorithm, and genetic algorithm in the bin-packing problem [11]. Wang et al. discussed the optimized heuristic bin-packing algorithm and summarized the application of the greedy algorithm in bin-packing [12]. Ceder used a heuristic method to calculate the departure interval that satisfies the passenger flow demand [13]. Bookbinder and Désilets took the reduction of the transfer cost as a consideration to form a digital model using a heuristic algorithm [14]. Guihaire and Hao used the tabu search algorithm and found a way to improve the model in order to enhance the achievement ratio of the plan [15]. Laurent and Hao solved the multistation driving plan problem based on the iterative local search algorithm [16]. Li et al. purposed a single route to a single charging station pure electric bus scheduling algorithm with the target of minimizing the vehicle amount while considering the factors of charging interval and departure strategies [17]. However, the study only regarded the number of vehicles as the objective function and oversimplified the real operational situation. Yang et al. [18] converted the electric bus scheduling problem into a directed network and applied a new column generation algorithm, which efficiently solved the problem of electric bus scheduling and guided the promotion and application of electric buses.In terms of the studies on pure electric buses, Gao adopted a real number encoding method to encode bus trips, considering scheduling vehicles and charging batteries in the vehicle charging mode, and optimized the start time of vehicle charging [19]. Han et al. presented the approach of planning and designing the charging stations’ operations based on the parameters of the pure electric buses and the battery rapid replacement mode [20], but the application of replacing batteries to maintain the mileage range is different from the actual operations. Chen et al. divided the electric buses’ mileage range problem into the prediction of residual energy and the prediction of energy consumption in the future trips of the electric buses [21]. Xu analyzed the advantages and disadvantages of the different types of charging mode and studied on the mileage range of electric buses [22]. Zhao et al. did some research on estimating the battery state of pure electric buses based on the neural network [23]. Wang et al. developed a residual energy time-space estimation model for pure electric bus on the basis of traffic performance index [24].In summary, there are few studies on regional electric bus driving plan. The existing research model simplified the real operating environment, which makes it difficult to adapt to the complex real work. In addition, there is no regional scheduling considering the constraints of driving mileage and charging time. Some papers considered the travel time constraints instead of the situation that vehicles can continue to perform tasks after returning to the parking and supplementing energy. At the same time, in solving algorithm, the problem of planning is also solved by the idea of packing based on the greedy algorithm, but the number of bus tasks cannot be arranged in descending order according to the volume of goods, but it can be optimized. Therefore, this paper considers the constraints such as pure electric vehicles’ charging window, having no fixed affiliation relationship between the vehicle and the parking lot, and vehicles continuing to perform tasks after charging. Meanwhile, it also improves the solving algorithm to support the application of pure electric bus in real operation.


## 3. Bin-Packing Idea, Genetic Algorithm, and Driving Plan Schedule

### 3.1. The Comparison between Driving Plan Scheduling Problem and Bin-Packing Problem

Essentially, the driving plan scheduling problem is an optimal combination decision-making problem. The optimal solution needs to be searched among plenty of different combinations. There are many similarities between the driving plan scheduling and the bin-packing. Applying the greedy algorithm in solving the bin-packing problem is also equivalent to solving the optimal combination decision-making problem. The corresponding relationship is shown in Table1.Table 1
Corresponding relationships between driving plan scheduling and bin-packing problem.
Driving plan scheduling
Bin-packing problem
Shifts
Items
Shift scheduling
Item allocation
Interval difference between shifts
Shape volume difference between items
Optimize the vehicle scheduling
Minimize the number of boxes
Constraints: endurance mileage
Constraint: total volume is less than the box capacityFor traditional fuel buses, once the timetable is determined, the task set for the day is confirmed. However, for pure electric buses, due to the constraint of endurance mileage, every electric bus will have different charging time throughout the day under different scheduling. Therefore, pure electric buses’ driving plan scheduling problem is different from the classic bin-packing problem. The items for bin-packing are identified initially, but the daily task sets for pure electric buses (including task trips and charging trips) are not sure at the start. To deal with the problem, a solution is proposed that converts the pure electric bus driving plan scheduling problem with charging trips into the same scheduling problem with time window constraints. In other words, if the constraint conditions of the electric bus endurance mileage are not satisfied, a charging time window is added after the last task of the bus. Otherwise, the extra time-window is not required.


### 3.2. The Solving Method Based on Bin-Packing Idea and Genetic Algorithm

The scale of solving bus regional planning problem is very large. Genetic algorithm searches for global optimization solution by simulating the evolution process of biological survival of the fittest. It can be effectively used to solve the NP problem. Therefore, the paper uses the genetic algorithm to solve the pure electric bus regional planning model and introduces the idea of the greedy algorithm to reduce the scale of the solution and improve the efficiency of the algorithm. When the genetic algorithm is used to optimize, the coding scheme of the solution is designed according to the characteristics of the model. The coding scheme is decoded based on the idea of packing, the fitness function is designed, and the crossover and mutation operations are designed.The regional bus driving planning can be regarded as a special kind of “packing problem.” The classical packing problem is that a certain number of items are packed in boxes with the same capacity. The boxes and items need to meet the capacity constraints and the number of boxes used is the least. Traditional bus driving plan can be understood that a combination of certain tasks (when the timetable is determined, it cannot be changed) is required to be carried out by buses with the same attributes, so that each bus can meet the relevant constraints (such as time constraints) in the execution of tasks, and the number of vehicles used is minimum. The all-day task set of pure electric buses (including task and charging times) is uncertain at the beginning. Therefore, the paper transforms the planning of pure electric bus with charging times into the planning of pure electric bus with time window constraints. That is to say, if it is judged that the constraints of endurance mileage of pure electric bus are not satisfied, a charging time window will be added after the last mission of the vehicle. If it is satisfied, it will not be necessary.The greedy algorithm is often used to solve the bin-packing problem. The basic idea is to sort all the items by volume in descending order. Take out the items in order, compare the opening time of all the boxes with enough volume capacity, and put the items into the first opened box until all the items are packed up. By constraining the electric bus charging tasks with time windows, the regional driving plan scheduling problem for pure electric buses can also be solved by the bin-packing idea based on the greedy algorithm. However, it is different from sorting the items that the bus tasks cannot be sorted by volume in descending order. Thus, the following approach was applied when using the bin-packing idea to solve the regional pure electric bus driving plan scheduling problem. Generate the task set according to the task shifts of the bus timetable, randomly sort the set, and take out the task shift according to the order. If the task shift meets the current time constraint and space constraint (presenting in the form of time window constraint, which means determining that after empty driving, whether the task vehicle can reach the task start station before the start time), then assign the task to the current vehicle. Otherwise, put the task shift back to the task set. After the current vehicle is “loaded” with tasks, check whether each shift meets the endurance mileage constraint. If not, add a charging time window after the last task shift. If there is a time conflict, delete the shift coincided with the charging trip, which is usually the next shift after the charging trip, and the deleted shift returns to the task set. Then, start assigning task shifts to the next vehicle until all the task shifts are assigned. The approach allows that all the task shifts in the task set could be executed with the least number of vehicles in this sort order.Since the solutions under different task orders vary a lot when applying the bin-packing idea to solve the problem, in order to find the optimal or the approximately optimal solution, the paper adopted the genetic algorithm to search the global optimum, find the optimal order, and develop the optimal solution based on bin-packing idea under the optimal order.The solution scale of the regional bus driving plan scheduling problem is very large, and the mileage range constraint of the pure electric buses makes the problem even more complicated. The method based on bin-packing idea and genetic algorithm can reduce the solution scale and improve the efficiency of the algorithm.When applying the genetic algorithm in the study, the task shift order was regarded as the gene of the genetic algorithm. The objective function value obtained by the greedy algorithm reflected the fitness of the gene. According to the principle of survival of the fittest, the optimal solution or approximate optimal solution could be achieved by the conservation of good genes and cross-variation of bad genes. Individuals in the initial population were uniformly generated by the computer in random, and the population size was chosen to be 100.The flow chart of the solution algorithm for the pure electric bus vehicle regional driving plan scheduling is shown in Figure1.Figure 1
Flow chart of the optimization algorithm.


## 3.1. The Comparison between Driving Plan Scheduling Problem and Bin-Packing Problem

Essentially, the driving plan scheduling problem is an optimal combination decision-making problem. The optimal solution needs to be searched among plenty of different combinations. There are many similarities between the driving plan scheduling and the bin-packing. Applying the greedy algorithm in solving the bin-packing problem is also equivalent to solving the optimal combination decision-making problem. The corresponding relationship is shown in Table1.Table 1
Corresponding relationships between driving plan scheduling and bin-packing problem.
Driving plan scheduling
Bin-packing problem
Shifts
Items
Shift scheduling
Item allocation
Interval difference between shifts
Shape volume difference between items
Optimize the vehicle scheduling
Minimize the number of boxes
Constraints: endurance mileage
Constraint: total volume is less than the box capacityFor traditional fuel buses, once the timetable is determined, the task set for the day is confirmed. However, for pure electric buses, due to the constraint of endurance mileage, every electric bus will have different charging time throughout the day under different scheduling. Therefore, pure electric buses’ driving plan scheduling problem is different from the classic bin-packing problem. The items for bin-packing are identified initially, but the daily task sets for pure electric buses (including task trips and charging trips) are not sure at the start. To deal with the problem, a solution is proposed that converts the pure electric bus driving plan scheduling problem with charging trips into the same scheduling problem with time window constraints. In other words, if the constraint conditions of the electric bus endurance mileage are not satisfied, a charging time window is added after the last task of the bus. Otherwise, the extra time-window is not required.


## 3.2. The Solving Method Based on Bin-Packing Idea and Genetic Algorithm

The scale of solving bus regional planning problem is very large. Genetic algorithm searches for global optimization solution by simulating the evolution process of biological survival of the fittest. It can be effectively used to solve the NP problem. Therefore, the paper uses the genetic algorithm to solve the pure electric bus regional planning model and introduces the idea of the greedy algorithm to reduce the scale of the solution and improve the efficiency of the algorithm. When the genetic algorithm is used to optimize, the coding scheme of the solution is designed according to the characteristics of the model. The coding scheme is decoded based on the idea of packing, the fitness function is designed, and the crossover and mutation operations are designed.The regional bus driving planning can be regarded as a special kind of “packing problem.” The classical packing problem is that a certain number of items are packed in boxes with the same capacity. The boxes and items need to meet the capacity constraints and the number of boxes used is the least. Traditional bus driving plan can be understood that a combination of certain tasks (when the timetable is determined, it cannot be changed) is required to be carried out by buses with the same attributes, so that each bus can meet the relevant constraints (such as time constraints) in the execution of tasks, and the number of vehicles used is minimum. The all-day task set of pure electric buses (including task and charging times) is uncertain at the beginning. Therefore, the paper transforms the planning of pure electric bus with charging times into the planning of pure electric bus with time window constraints. That is to say, if it is judged that the constraints of endurance mileage of pure electric bus are not satisfied, a charging time window will be added after the last mission of the vehicle. If it is satisfied, it will not be necessary.The greedy algorithm is often used to solve the bin-packing problem. The basic idea is to sort all the items by volume in descending order. Take out the items in order, compare the opening time of all the boxes with enough volume capacity, and put the items into the first opened box until all the items are packed up. By constraining the electric bus charging tasks with time windows, the regional driving plan scheduling problem for pure electric buses can also be solved by the bin-packing idea based on the greedy algorithm. However, it is different from sorting the items that the bus tasks cannot be sorted by volume in descending order. Thus, the following approach was applied when using the bin-packing idea to solve the regional pure electric bus driving plan scheduling problem. Generate the task set according to the task shifts of the bus timetable, randomly sort the set, and take out the task shift according to the order. If the task shift meets the current time constraint and space constraint (presenting in the form of time window constraint, which means determining that after empty driving, whether the task vehicle can reach the task start station before the start time), then assign the task to the current vehicle. Otherwise, put the task shift back to the task set. After the current vehicle is “loaded” with tasks, check whether each shift meets the endurance mileage constraint. If not, add a charging time window after the last task shift. If there is a time conflict, delete the shift coincided with the charging trip, which is usually the next shift after the charging trip, and the deleted shift returns to the task set. Then, start assigning task shifts to the next vehicle until all the task shifts are assigned. The approach allows that all the task shifts in the task set could be executed with the least number of vehicles in this sort order.Since the solutions under different task orders vary a lot when applying the bin-packing idea to solve the problem, in order to find the optimal or the approximately optimal solution, the paper adopted the genetic algorithm to search the global optimum, find the optimal order, and develop the optimal solution based on bin-packing idea under the optimal order.The solution scale of the regional bus driving plan scheduling problem is very large, and the mileage range constraint of the pure electric buses makes the problem even more complicated. The method based on bin-packing idea and genetic algorithm can reduce the solution scale and improve the efficiency of the algorithm.When applying the genetic algorithm in the study, the task shift order was regarded as the gene of the genetic algorithm. The objective function value obtained by the greedy algorithm reflected the fitness of the gene. According to the principle of survival of the fittest, the optimal solution or approximate optimal solution could be achieved by the conservation of good genes and cross-variation of bad genes. Individuals in the initial population were uniformly generated by the computer in random, and the population size was chosen to be 100.The flow chart of the solution algorithm for the pure electric bus vehicle regional driving plan scheduling is shown in Figure1.Figure 1
Flow chart of the optimization algorithm.


## 4. Pure Electric Bus Regional Driving Plan Optimization Model

### 4.1. Problem Description

To guarantee the service quality and meet transportation demand, the most important thing for pure electric bus operating companies is cost control. Besides, it is necessary to consider charging infrastructure capacities required in operation. Thus, the output of the optimization model included the amount of the charging infrastructure. In addition, compared with fuel buses, pure electric vehicles are more expensive. In addition, more electric vehicles are needed to complete the same transport task. Therefore, the cost of purchasing electric vehicles is also an important factor. Finally, due to the implementation of regional driving plan, there will be significant difference in the empty driving cost of the buses which should be considered. Other influencing factors can be neglected as they differ little. Therefore, the objective functions are composed of the purchase cost of pure electric buses, the purchase and installation cost of charging infrastructure, and the daily empty driving cost of the buses. In terms of major constraints, since the technical performance of the pure electric buses does not match the operational requirements, the charging time needs to be arranged in the operation tasks in a day. Therefore, the paper added the mileage range constraint and the charging tasks in the optimization model.


### 4.2. Data Collection

The data in the paper is sourced from four bus routes (including Beijing Xing 11 Route) and two bus terminals (Huangcun Railway Station Bus Terminal Station and Fuyuan Terminal Station). The data includes the timetable of each route, the amount of bus terminals and their respective capacities, the mileage matrix between each bus station and bus terminal, the average speed of the vehicles, the length of each route, the mileage between the first and last station of each route, and the charging time of the pure electric bus.


### 4.3. Model Development

#### 4.3.1. Model Assumption

Based on the current scenarios in real operation of pure electric bus, an optimization model of pure electric bus operation plan is established based on the following assumptions:(1)
Make vehicle operation plan on a daily basis, with minutes as the minimum unit of time(2)
All bus trips can be executed accurately without delay(3)
There is no fixed allocation relationship between vehicles and depots, but when the full-time mission is over, buses need to return to the original station


#### 4.3.2. Objective Function

The vehicle task is to complete all the task shifts in the regional timetable. The optimization objectives include minimizing the size of the pure electric bus fleet which can be calculated by equation (1), the amount of charging infrastructure which can be calculated by equation (2), and the empty driving mileage in a day which can be calculated by equation (3). In order to reduce the complexity and the difficulty of the model, the multiple objectives are transformed into a single objective function with the lowest total system cost which can be calculated by equation (4). Within the objective function, the fixed cost determined by the size of the pure electric bus fleet can be calculated as the number of vehicles multiplied by the unit price of one pure electric bus. The fixed cost of the charging infrastructure can be achieved by multiplying the number of charging infrastructure and the unit purchase and installation cost of charging infrastructure. The empty driving cost caused by scheduling the buses is determined by the daily empty driving mileage, the electricity consumption per 100 kilometer of the electric bus, and the local standard electricity price.(1)minZ1=min∑k∈C∑i∈Ω∑j∈Ωxijk,where Ω is the set of all shifts, C is the set of all bus vehicles and xijk is a variable which is either 0 or 1. If vehicle k conducts shift i and will conduct shift j for the next, the variable is 1; otherwise, it is 0.(2)minZ2=min∑p∈Pθp,where θp is a variable which is either 0 or 1; if the charging pile p has conducted the charging task, the variable is 1; otherwise, it is 0; and P is the set for all charging piles.(3)minZ3=min∑k∈C∑i∈Ω∑j∈Ωxijk.lij,where lij is the empty mileage required for the vehicle to complete shift j after completing the shift i.(4)minZ=minc1Z1+c2Z2+c3Z3,where c1,c2,c3 represent the unit cost of the vehicle, the unit fixed cost of the charging infrastructure, and the unit empty driving cost of the vehicle.The total objective function indicates that the sum of fixed cost and empty driving cost of the pure electric bus company reached the minimum.


#### 4.3.3. Constraints of the Model

The major constraints of the regional bus driving plan include(5)∑k∈C∑i∈Ωxijk=1,i≠j,i∈1,2,…,n.(1)
The Time Connection Constraint between Each Shift. The time interval between the finish time of shift i and the departure time of shift j should be longer than the time spent on the road between shift i and shift j. It can be specified by the following equation:(6)tijxijk≤tsj−tei,wheretsj is the departure time of shift j, tei is the finish time of shift i, and tij is the time required for driving to shift j after the completion of shift i.(2)
The Vehicle Mileage Constraint. Before conducting shift j, the constraint has to be met that the mileage of shift j is smaller than the difference between full mileage and the sum of all conducted shift mileage and the mileage returning to the bus terminal after completing shift j. It can be specified by the following equation:(7)li∗j∗≤L−∑i∈Ω∑j∈Ωxijklij−lc,SOC is the state of charge of the battery;L is longest mileage that the pure electric bus can run under the condition of SOCmax.(3)
It is stipulated that all the vehicles should return to the original bus terminals eventually. In order to be consistent with the actual operation requirements, the pure electric bus departs from a certain bus terminal, and after it completes certain shifts, it has to return to its original departure terminal station. It can be specified by the following equation:(8)SkQ=EkQ,whereSkQ is a variable which is either 0 or 1, representing whether the vehicle k departs from terminal station Q and EkQ is a variable which is either 0 or 1, representing whether the vehicle k returns to terminal station Q.(4)
The number of vehicles in each bus terminal stationQ cannot excess its capacity. It can be specified by the following equation:(9)∑kSkQ=∑kEkQ≤capacityQ,Q is the terminal station set, and the capacity of the terminal station is represented by capacityQ.


## 4.1. Problem Description

To guarantee the service quality and meet transportation demand, the most important thing for pure electric bus operating companies is cost control. Besides, it is necessary to consider charging infrastructure capacities required in operation. Thus, the output of the optimization model included the amount of the charging infrastructure. In addition, compared with fuel buses, pure electric vehicles are more expensive. In addition, more electric vehicles are needed to complete the same transport task. Therefore, the cost of purchasing electric vehicles is also an important factor. Finally, due to the implementation of regional driving plan, there will be significant difference in the empty driving cost of the buses which should be considered. Other influencing factors can be neglected as they differ little. Therefore, the objective functions are composed of the purchase cost of pure electric buses, the purchase and installation cost of charging infrastructure, and the daily empty driving cost of the buses. In terms of major constraints, since the technical performance of the pure electric buses does not match the operational requirements, the charging time needs to be arranged in the operation tasks in a day. Therefore, the paper added the mileage range constraint and the charging tasks in the optimization model.


## 4.2. Data Collection

The data in the paper is sourced from four bus routes (including Beijing Xing 11 Route) and two bus terminals (Huangcun Railway Station Bus Terminal Station and Fuyuan Terminal Station). The data includes the timetable of each route, the amount of bus terminals and their respective capacities, the mileage matrix between each bus station and bus terminal, the average speed of the vehicles, the length of each route, the mileage between the first and last station of each route, and the charging time of the pure electric bus.


## 4.3. Model Development

### 4.3.1. Model Assumption

Based on the current scenarios in real operation of pure electric bus, an optimization model of pure electric bus operation plan is established based on the following assumptions:(1)
Make vehicle operation plan on a daily basis, with minutes as the minimum unit of time(2)
All bus trips can be executed accurately without delay(3)
There is no fixed allocation relationship between vehicles and depots, but when the full-time mission is over, buses need to return to the original station


### 4.3.2. Objective Function

The vehicle task is to complete all the task shifts in the regional timetable. The optimization objectives include minimizing the size of the pure electric bus fleet which can be calculated by equation (1), the amount of charging infrastructure which can be calculated by equation (2), and the empty driving mileage in a day which can be calculated by equation (3). In order to reduce the complexity and the difficulty of the model, the multiple objectives are transformed into a single objective function with the lowest total system cost which can be calculated by equation (4). Within the objective function, the fixed cost determined by the size of the pure electric bus fleet can be calculated as the number of vehicles multiplied by the unit price of one pure electric bus. The fixed cost of the charging infrastructure can be achieved by multiplying the number of charging infrastructure and the unit purchase and installation cost of charging infrastructure. The empty driving cost caused by scheduling the buses is determined by the daily empty driving mileage, the electricity consumption per 100 kilometer of the electric bus, and the local standard electricity price.(1)minZ1=min∑k∈C∑i∈Ω∑j∈Ωxijk,where Ω is the set of all shifts, C is the set of all bus vehicles and xijk is a variable which is either 0 or 1. If vehicle k conducts shift i and will conduct shift j for the next, the variable is 1; otherwise, it is 0.(2)minZ2=min∑p∈Pθp,where θp is a variable which is either 0 or 1; if the charging pile p has conducted the charging task, the variable is 1; otherwise, it is 0; and P is the set for all charging piles.(3)minZ3=min∑k∈C∑i∈Ω∑j∈Ωxijk.lij,where lij is the empty mileage required for the vehicle to complete shift j after completing the shift i.(4)minZ=minc1Z1+c2Z2+c3Z3,where c1,c2,c3 represent the unit cost of the vehicle, the unit fixed cost of the charging infrastructure, and the unit empty driving cost of the vehicle.The total objective function indicates that the sum of fixed cost and empty driving cost of the pure electric bus company reached the minimum.


### 4.3.3. Constraints of the Model

The major constraints of the regional bus driving plan include(5)∑k∈C∑i∈Ωxijk=1,i≠j,i∈1,2,…,n.(1)
The Time Connection Constraint between Each Shift. The time interval between the finish time of shift i and the departure time of shift j should be longer than the time spent on the road between shift i and shift j. It can be specified by the following equation:(6)tijxijk≤tsj−tei,wheretsj is the departure time of shift j, tei is the finish time of shift i, and tij is the time required for driving to shift j after the completion of shift i.(2)
The Vehicle Mileage Constraint. Before conducting shift j, the constraint has to be met that the mileage of shift j is smaller than the difference between full mileage and the sum of all conducted shift mileage and the mileage returning to the bus terminal after completing shift j. It can be specified by the following equation:(7)li∗j∗≤L−∑i∈Ω∑j∈Ωxijklij−lc,SOC is the state of charge of the battery;L is longest mileage that the pure electric bus can run under the condition of SOCmax.(3)
It is stipulated that all the vehicles should return to the original bus terminals eventually. In order to be consistent with the actual operation requirements, the pure electric bus departs from a certain bus terminal, and after it completes certain shifts, it has to return to its original departure terminal station. It can be specified by the following equation:(8)SkQ=EkQ,whereSkQ is a variable which is either 0 or 1, representing whether the vehicle k departs from terminal station Q and EkQ is a variable which is either 0 or 1, representing whether the vehicle k returns to terminal station Q.(4)
The number of vehicles in each bus terminal stationQ cannot excess its capacity. It can be specified by the following equation:(9)∑kSkQ=∑kEkQ≤capacityQ,Q is the terminal station set, and the capacity of the terminal station is represented by capacityQ.


## 4.3.1. Model Assumption

Based on the current scenarios in real operation of pure electric bus, an optimization model of pure electric bus operation plan is established based on the following assumptions:(1)
Make vehicle operation plan on a daily basis, with minutes as the minimum unit of time(2)
All bus trips can be executed accurately without delay(3)
There is no fixed allocation relationship between vehicles and depots, but when the full-time mission is over, buses need to return to the original station


## 4.3.2. Objective Function

The vehicle task is to complete all the task shifts in the regional timetable. The optimization objectives include minimizing the size of the pure electric bus fleet which can be calculated by equation (1), the amount of charging infrastructure which can be calculated by equation (2), and the empty driving mileage in a day which can be calculated by equation (3). In order to reduce the complexity and the difficulty of the model, the multiple objectives are transformed into a single objective function with the lowest total system cost which can be calculated by equation (4). Within the objective function, the fixed cost determined by the size of the pure electric bus fleet can be calculated as the number of vehicles multiplied by the unit price of one pure electric bus. The fixed cost of the charging infrastructure can be achieved by multiplying the number of charging infrastructure and the unit purchase and installation cost of charging infrastructure. The empty driving cost caused by scheduling the buses is determined by the daily empty driving mileage, the electricity consumption per 100 kilometer of the electric bus, and the local standard electricity price.(1)minZ1=min∑k∈C∑i∈Ω∑j∈Ωxijk,where Ω is the set of all shifts, C is the set of all bus vehicles and xijk is a variable which is either 0 or 1. If vehicle k conducts shift i and will conduct shift j for the next, the variable is 1; otherwise, it is 0.(2)minZ2=min∑p∈Pθp,where θp is a variable which is either 0 or 1; if the charging pile p has conducted the charging task, the variable is 1; otherwise, it is 0; and P is the set for all charging piles.(3)minZ3=min∑k∈C∑i∈Ω∑j∈Ωxijk.lij,where lij is the empty mileage required for the vehicle to complete shift j after completing the shift i.(4)minZ=minc1Z1+c2Z2+c3Z3,where c1,c2,c3 represent the unit cost of the vehicle, the unit fixed cost of the charging infrastructure, and the unit empty driving cost of the vehicle.The total objective function indicates that the sum of fixed cost and empty driving cost of the pure electric bus company reached the minimum.


## 4.3.3. Constraints of the Model

The major constraints of the regional bus driving plan include(5)∑k∈C∑i∈Ωxijk=1,i≠j,i∈1,2,…,n.(1)
The Time Connection Constraint between Each Shift. The time interval between the finish time of shift i and the departure time of shift j should be longer than the time spent on the road between shift i and shift j. It can be specified by the following equation:(6)tijxijk≤tsj−tei,wheretsj is the departure time of shift j, tei is the finish time of shift i, and tij is the time required for driving to shift j after the completion of shift i.(2)
The Vehicle Mileage Constraint. Before conducting shift j, the constraint has to be met that the mileage of shift j is smaller than the difference between full mileage and the sum of all conducted shift mileage and the mileage returning to the bus terminal after completing shift j. It can be specified by the following equation:(7)li∗j∗≤L−∑i∈Ω∑j∈Ωxijklij−lc,SOC is the state of charge of the battery;L is longest mileage that the pure electric bus can run under the condition of SOCmax.(3)
It is stipulated that all the vehicles should return to the original bus terminals eventually. In order to be consistent with the actual operation requirements, the pure electric bus departs from a certain bus terminal, and after it completes certain shifts, it has to return to its original departure terminal station. It can be specified by the following equation:(8)SkQ=EkQ,whereSkQ is a variable which is either 0 or 1, representing whether the vehicle k departs from terminal station Q and EkQ is a variable which is either 0 or 1, representing whether the vehicle k returns to terminal station Q.(4)
The number of vehicles in each bus terminal stationQ cannot excess its capacity. It can be specified by the following equation:(9)∑kSkQ=∑kEkQ≤capacityQ,Q is the terminal station set, and the capacity of the terminal station is represented by capacityQ.


## 5. Results

### 5.1. Explanations of the Basic Information

We took Daxing District in Beijing as an example to develop the pure electric bus driving plan model and algorithm analysis. Two bus parking and charging stations (Huangcun Railway Station Bus Terminal Station and Fuyuan Bus Terminal Station) and four bus routes (Xing 11 Route, Xing 12 Route, Xing 36 Route, and Xing 47 Route) are selected to conduct the analysis.(1)
Introduction of the Route’s Basic Information. The original and terminal stations of the four routes and the mileage between stations are listed in Table 2.(2)
The Description of Pure Electric Bus Vehicles. We took Futian Ouhui BJ6851 series pure electric bus as an example to analyze the pure electric bus operation scheduling. The bus is 10.5 meters long, the maximum passenger capacity is 70, and the maximum endurance mileage can be 120 kilometers. The average running speed of the bus is 30 km/h.(3)
The Description of Genetic Algorithm Parameters. According to the custom, the initial population size is 100 individuals, the crossover probability is 0.6, the mutation probability is 0.01, and the excellent gene retention rate is 0.1 in the genetic algorithm of this paper. We used Python 3.0 programming to solve the algorithm.Table 2
The mileage table between stations.
Xing 11 Route (km)
Xing 12 Route (km)
Xing 36 Route (km)
Xing 47 Route (km)
Ba Yuan Zi station
Tai Zhong garden station
Jin Hua Yuan community
Xihongmen town government
Huangcun railway station
Shou Bao Zhuang
Yi Zhuang Qiao railway station
Xing Kang Jiayuan
Xing 11 Route (km)
Ba Yuan Zi station
0
22.9
12.6
22.3
13.4
23.4
34.2
20
Tai Zhong garden station
22.9
0
7.1
4.9
6.7
4.8
27.6
4.5
Xing 12 Route (km)
Jin Hua Yuan community
12.6
7.1
0
10.5
3
11.8
30.9
9.3
Xihongmen town government
22.3
4.9
10.5
0
9.5
5.2
12.9
7.3
Xing 36 Route (km)
Huangcun railway station
13.4
6.7
3
9.5
0
10.1
29.9
5.4
Shou Bao Zhuang
23.4
4.8
11.8
5.2
10.1
0
13.1
8.8
Xing 47 Route (km)
Yi Zhuang Qiao railway station
34.2
27.6
30.9
12.9
29.9
13.1
0
28.5
Xing Kang Jiayuan
20
4.5
9.3
7.3
5.4
8.8
28.5
0


### 5.2. The Operational Organization in Pure Electric Bus Region considering the Service Level

Take the upline timetable of Xing 11 Route as an example and calculate the departure frequency of each route of a day. Adjust the departure frequency and generate a pure electric bus route timetable with the consideration of the service level, which is shown in Table3.Table 3
Departure timetable of the upline of Xing 11 Route.
06:00
06:05
06:10
06:15
06:20
06:25
06:30
06:35
06:40
06:45
06:50
06:55
07:00
07:05
07:10
07:15
07:20
07:25
07:30
07:35
07:40
07:45
07:50
07:55
08:00
08:05
08:10
08:15
08:20
08:25
08:30
08:35
08:40
08:45
08:50
08:55
09:00
09:10
09:20
09:30
09:40
09:50
10:00
10:15
10:30
10:45
11:00
11:15
11:30
11:45
12:00
12:15
12:30
12:45
13:00
13:20
13:40
14:00
14:15
14:40
15:00
15:15
15:30
15:45
16:00
16:10
16:20
16:30
16:40
16:50
17:00
17:05
17:10
17:15
17:20
17:25
17:30
17:35
17:40
17:45
17:50
17:55
18:00
18:10
18:20
18:30
18:40
18:50
19:00
19:15
19:30
19:45
20:00
20:20
20:40
21:00Based on the above table, we adopt the pure electric bus regional driving plan optimization model and algorithm which can be calculated by equation (10) to do the driving plan scheduling for 2 studied terminal stations and 4 routes including both upline and downline, which contains 544 task shifts in total. The values of the parameters in the model are as follows: σ1 is the vehicle cost conversion factor. As the Futian Ouhui BJ6851 series pure electric urban bus is selected in the study, the price on the official website is used, which is 1,500,000 yuan. σ2 is the cost conversion factor for pure electric bus charging infrastructure. According to its purchase and installation cost, σ2 is 100,000 yuan. σ3 is the empty driving mileage cost conversion factor. According to the studies, it can be assumed that the electricity consumption per hundred kilometers of pure electric buses is 40 kWh, the daytime electricity fee in Beijing is 0.5 yuan/kWh, and the service life for pure electric buses and charging infrastructure is 6 years. So, the daily empty driving mileage is multiplied by 2190 days and takes σ3 as 438.(10)minZ=minσ1Z1+σ2Z2+σ3Z3=min1500000∑k∈C∑i∈Ω∑j∈Ωxijk+100000∑p∈Pθp+438∑k∈C∑i∈Ω∑j∈Ωxijk.lij.


### 5.3. Results Output

By solving the model, the optimal solution is obtained that the objective value is 108 778 596 yuan, and the program iteration process is shown in Figure2.Figure 2
Program iteration process.The result shows that a total of 71 pure electric bus vehicles and 15 charging infrastructures are required. Among them, Huangcun Railway Station Bus Terminal Station has 47 pure electric buses and 7 charging infrastructures while Fuyuan Bus Terminal Station has 24 pure electric buses and 8 charging infrastructures. The total empty driving mileage is 4 991 km. Table4 shows the vehicle chain, where the number in the chain represents the task number that reflects the tasks conducted by the vehicle throughout the day. Charge1 and Charge2 represent the charging task executed in Huangcun Railway Station Bus Terminal Station and Fuyuan Bus Terminal Station, respectively.Table 4
Vehicle chain.
Vehicle number
Affiliated terminal station
Number of tasks
Vehicle chain
Time/min
Waiting time
Empty driving time
Travelling time
1
Huangcun
12
102-18-403-338-407-Charge2-291-419-62-305-377-257
91
55
684
2
Huangcun
15
321-267-117-33-282-Charge2-416-229-361-158-249-441-384-444-387
68
42
720
3
Fuyuan
10
388-323-113-209-406-Charge2-473-360-156-536
150
45
570
4
Fuyuan
10
320-325-202-459-Charge1-144-359-480-247-442
112
63
590
5
Huangcun
10
4-115-280-Charge2-143-528-307-440-256-543
155
45
575
6
Fuyuan
9
103-507-Charge2-58-154-68-376-381-385
185
40
540
7
Fuyuan
10
498-275-128-47-Charge1-147-238-244-176-94
138
47
580
8
Fuyuan
11
264-327-119-35-342-410-Charge1-418-61-160-80
140
50
590
…
…
…
…
…
70
Huangcun
2
350-170
60
25
160
71
Huangcun
3
517-470-532
75
40
230


## 5.1. Explanations of the Basic Information

We took Daxing District in Beijing as an example to develop the pure electric bus driving plan model and algorithm analysis. Two bus parking and charging stations (Huangcun Railway Station Bus Terminal Station and Fuyuan Bus Terminal Station) and four bus routes (Xing 11 Route, Xing 12 Route, Xing 36 Route, and Xing 47 Route) are selected to conduct the analysis.(1)
Introduction of the Route’s Basic Information. The original and terminal stations of the four routes and the mileage between stations are listed in Table 2.(2)
The Description of Pure Electric Bus Vehicles. We took Futian Ouhui BJ6851 series pure electric bus as an example to analyze the pure electric bus operation scheduling. The bus is 10.5 meters long, the maximum passenger capacity is 70, and the maximum endurance mileage can be 120 kilometers. The average running speed of the bus is 30 km/h.(3)
The Description of Genetic Algorithm Parameters. According to the custom, the initial population size is 100 individuals, the crossover probability is 0.6, the mutation probability is 0.01, and the excellent gene retention rate is 0.1 in the genetic algorithm of this paper. We used Python 3.0 programming to solve the algorithm.Table 2
The mileage table between stations.
Xing 11 Route (km)
Xing 12 Route (km)
Xing 36 Route (km)
Xing 47 Route (km)
Ba Yuan Zi station
Tai Zhong garden station
Jin Hua Yuan community
Xihongmen town government
Huangcun railway station
Shou Bao Zhuang
Yi Zhuang Qiao railway station
Xing Kang Jiayuan
Xing 11 Route (km)
Ba Yuan Zi station
0
22.9
12.6
22.3
13.4
23.4
34.2
20
Tai Zhong garden station
22.9
0
7.1
4.9
6.7
4.8
27.6
4.5
Xing 12 Route (km)
Jin Hua Yuan community
12.6
7.1
0
10.5
3
11.8
30.9
9.3
Xihongmen town government
22.3
4.9
10.5
0
9.5
5.2
12.9
7.3
Xing 36 Route (km)
Huangcun railway station
13.4
6.7
3
9.5
0
10.1
29.9
5.4
Shou Bao Zhuang
23.4
4.8
11.8
5.2
10.1
0
13.1
8.8
Xing 47 Route (km)
Yi Zhuang Qiao railway station
34.2
27.6
30.9
12.9
29.9
13.1
0
28.5
Xing Kang Jiayuan
20
4.5
9.3
7.3
5.4
8.8
28.5
0


## 5.2. The Operational Organization in Pure Electric Bus Region considering the Service Level

Take the upline timetable of Xing 11 Route as an example and calculate the departure frequency of each route of a day. Adjust the departure frequency and generate a pure electric bus route timetable with the consideration of the service level, which is shown in Table3.Table 3
Departure timetable of the upline of Xing 11 Route.
06:00
06:05
06:10
06:15
06:20
06:25
06:30
06:35
06:40
06:45
06:50
06:55
07:00
07:05
07:10
07:15
07:20
07:25
07:30
07:35
07:40
07:45
07:50
07:55
08:00
08:05
08:10
08:15
08:20
08:25
08:30
08:35
08:40
08:45
08:50
08:55
09:00
09:10
09:20
09:30
09:40
09:50
10:00
10:15
10:30
10:45
11:00
11:15
11:30
11:45
12:00
12:15
12:30
12:45
13:00
13:20
13:40
14:00
14:15
14:40
15:00
15:15
15:30
15:45
16:00
16:10
16:20
16:30
16:40
16:50
17:00
17:05
17:10
17:15
17:20
17:25
17:30
17:35
17:40
17:45
17:50
17:55
18:00
18:10
18:20
18:30
18:40
18:50
19:00
19:15
19:30
19:45
20:00
20:20
20:40
21:00Based on the above table, we adopt the pure electric bus regional driving plan optimization model and algorithm which can be calculated by equation (10) to do the driving plan scheduling for 2 studied terminal stations and 4 routes including both upline and downline, which contains 544 task shifts in total. The values of the parameters in the model are as follows: σ1 is the vehicle cost conversion factor. As the Futian Ouhui BJ6851 series pure electric urban bus is selected in the study, the price on the official website is used, which is 1,500,000 yuan. σ2 is the cost conversion factor for pure electric bus charging infrastructure. According to its purchase and installation cost, σ2 is 100,000 yuan. σ3 is the empty driving mileage cost conversion factor. According to the studies, it can be assumed that the electricity consumption per hundred kilometers of pure electric buses is 40 kWh, the daytime electricity fee in Beijing is 0.5 yuan/kWh, and the service life for pure electric buses and charging infrastructure is 6 years. So, the daily empty driving mileage is multiplied by 2190 days and takes σ3 as 438.(10)minZ=minσ1Z1+σ2Z2+σ3Z3=min1500000∑k∈C∑i∈Ω∑j∈Ωxijk+100000∑p∈Pθp+438∑k∈C∑i∈Ω∑j∈Ωxijk.lij.


## 5.3. Results Output

By solving the model, the optimal solution is obtained that the objective value is 108 778 596 yuan, and the program iteration process is shown in Figure2.Figure 2
Program iteration process.The result shows that a total of 71 pure electric bus vehicles and 15 charging infrastructures are required. Among them, Huangcun Railway Station Bus Terminal Station has 47 pure electric buses and 7 charging infrastructures while Fuyuan Bus Terminal Station has 24 pure electric buses and 8 charging infrastructures. The total empty driving mileage is 4 991 km. Table4 shows the vehicle chain, where the number in the chain represents the task number that reflects the tasks conducted by the vehicle throughout the day. Charge1 and Charge2 represent the charging task executed in Huangcun Railway Station Bus Terminal Station and Fuyuan Bus Terminal Station, respectively.Table 4
Vehicle chain.
Vehicle number
Affiliated terminal station
Number of tasks
Vehicle chain
Time/min
Waiting time
Empty driving time
Travelling time
1
Huangcun
12
102-18-403-338-407-Charge2-291-419-62-305-377-257
91
55
684
2
Huangcun
15
321-267-117-33-282-Charge2-416-229-361-158-249-441-384-444-387
68
42
720
3
Fuyuan
10
388-323-113-209-406-Charge2-473-360-156-536
150
45
570
4
Fuyuan
10
320-325-202-459-Charge1-144-359-480-247-442
112
63
590
5
Huangcun
10
4-115-280-Charge2-143-528-307-440-256-543
155
45
575
6
Fuyuan
9
103-507-Charge2-58-154-68-376-381-385
185
40
540
7
Fuyuan
10
498-275-128-47-Charge1-147-238-244-176-94
138
47
580
8
Fuyuan
11
264-327-119-35-342-410-Charge1-418-61-160-80
140
50
590
…
…
…
…
…
70
Huangcun
2
350-170
60
25
160
71
Huangcun
3
517-470-532
75
40
230


## 6. Discussion and Conclusions

The paper conducts a research on 544 task shifts including 2 bus terminal stations and 4 two-way trip bus routes. The conventional greedy algorithm is used as the comparison method to analyze the effectiveness of the algorithm. The comparison of the outcome indicators is shown in Table5.Table 5
Comparison of outcome indicators.
Algorithm
Total cost (yuan)
Number of pure electric buses
Number of charging infrastructures
Daily empty driving mileage
Algorithm in the paper
108 778 596
71
15
4 991
Conventional algorithm
130 122 128
85
20
3 988The results analyzed are as follows:(1)
The average daily empty driving mileage increased by 20% approximately by using the method based on bin-packing idea and the genetic algorithm in this paper rather than by comparison algorithm.(2)
The required number of pure electric buses and charging infrastructures reduced by 19.7% and 33.3%, respectively. And the total cost thereof is cut down by 19.6%.(3)
Since the number of charging piles is reduced, the length of the charging empty driving arc extends. Yet, the increasing cost of the longer empty driving mileage is lower than the reduced cost saved by charging infrastructures and the number of vehicles. Thus, the above three elements achieve the optimal balance and maintain the lowest total cost.(4)
Based on the bin-packing idea and the genetic algorithm purposed in the paper, the solving algorithm reduces the scale of the infrastructures and saves the operation cost, which effectively functions in real scheduling of the pure electric bus driving plan.Public transportation with large scale bus routes and high departure frequencies can result in an extensive scale of regional bus driving plan schedule. And time window of pure electric bus makes it even more complicated. Without an ideal algorithm, generation of a reasonable scheduling in the acceptable time can be affected. The method based on the bin-packing idea and genetic algorithm can efficiently reduce the scale of the problem, and the results are better than those obtained from the traditional greedy algorithm. In this paper, we consider multiple objectives including pure electric bus fleet size and the number of the charging infrastructures and build a regional pure electric bus scheduling model with multiroute to multicharging station. Based on the genetic algorithm and bin-packing idea, the pure electric bus regional scheduling model is solved and validated with examples. The research is of great significance for pure electric buses promotion and could better satisfy passengers’ travel needs.The paper establishes a pure electric bus planning model for regional multiline and multicharging stations. The research can effectively save system cost and solve the most urgent problem at present. The impact of pure electric bus on distribution network and the coordination with pure electric private car need to be considered in the future work. There are mainly the following aspects:(1)
After the large scale application of pure electric bus, especially when there are many buses charging at the same bus station, it will have a lot of impact on the distribution network. Voltage distortion is easily caused by disordered charging. Charging load will cause voltage deviation and load rate of distribution network to exceed safety level and produce harmonic pollution. Therefore, the research on orderly charging strategy of pure electric bus is an urgent issue.(2)
Electric private cars are also growing rapidly. Driver’s behavior will have a significant impact on the charging activities of electric private cars, so we should consider social and geographical factors, including the driver’s social class, distance from charging station to build the driver’s behavior model, and encourage the driver to charge at the recommended charging time and location. How to coordinate the charging of pure electric bus and electric private car to minimize the adverse impact on the power grid needs to be considered.(3)
Multibus charging in the same parking lot will also have a negative impact on the distribution network. Considering the number of charging piles and the real-time charging situation, the proposed tasks can be given when there are multiple tasks to choose from.(4)
Furthermore, with the rapid development of vehicle positioning, data collection, and wireless communication technology, a dynamic organizational operation of public transportation can be achieved by acquiring real-time vehicle information and passenger flow information, which can provide a better service to bus operating organizations.



---

*Source: 7863290-2019-10-16.xml*