《1. Introduction》

1. Introduction

The growing share of transportation in the world’s energy consumption heavily affects climate, energy security, and the environment, contributing 29% of total greenhouse gas (GHG) emissions, as approximately 95% of transport energy is still provided by oilderived fuels [1–3]. According to the US Federal Transit Administration report, the city bus is one of the most energy-efficient modes of urban transit, even if it is powered by diesel [4]. Moreover, if the bus fleet can be powered by electricity from renewable sources, the emission reduction would be further reduced by 80% [5,6]. Only in this way can we move toward a carbon-neutral transportation system [7].

Global efforts are being made to support infrastructure construction and stimulate electric vehicle purchases [8,9]. The Ministry of Transport of the People’s Republic of China promises to have at least a 20% market share of pure electric vehicles by 2030 [10]. Furthermore, with the continued implementation of the policy, the number of charging piles in China has boomed over the past five years, reaching 1.681 million in 2020. The vehicle-topile ratio is now 3.13:1 and is expected to continue to increase to 2:1 by 2025 [11]. Similarly, the 2 trillion USD infrastructure and jobs plan by the White House in the United States will invest 174 billion USD in building an electrified transportation network with 500 000 chargers by 2035, while spurring the procurement of electric cars, buses, and trucks [12]. In European countries, there has been a substantial growth of 480% in the deployment of charging infrastructure since 2014. The goal of charging point construction is 2.8 million by 2035—14 times the current amount. Moreover, 20 European countries offer bonus payments or premiums to electric vehicle buyers, causing electric bus (EB) registration to triple in 2019 [13].

EB stock has increased in key markets, according to the International Energy Agency [14]. China continues to dominate the EB industry, accounting for 99.0% of the worldwide fleet, with more than 30 Chinese cities planning to have fully electrified public transportation by the beginning of 2021 [15]. The global EB market is projected to double in size, reaching 1.2 million units by 2025, and approximately 40% of new city buses registered in Europe will be battery electric. Fig. 1 summarizes the market segmentation of European countries and the progress of global EBs. Doubling the stock of EBs is the main goal for developing the global bus fleet by 2025. Germany is in a leading position in Europe and has planned for longer-term purchases of around 4800 electrically powered buses before 2030, which is seven times the figure for 2020 [16]. Under these ambitious development plans, policymakers and transportation planners are starting to realize that systematic models should be available at such an urgent but preliminary stage to answer the following questions: ① how can the procurement be efficiently planned; and ② how can existing schedules be arranged and adjusted while considering the characteristics of the EB fleet [17,18]?

《Fig. 1》

Fig. 1. Global EB market size. (a) Market size development of EBs from 2018 to 2025; (b) 2020 European countries’ market size breakdown.

The motivation of this study is to promote the realization of the near-future bus electrification target. The rest of this paper is organized as follows. Section 2 reviews the state of the art of life-cycle analysis, charging station deployment, and bus fleet management. Section 3 provides a life-cycle cost (LCC) analysis framework and introduces a mathematical optimization model in which a tailored column generation algorithm is introduced for bus schedules. Subsequently, two case studies based on real-world electrification networks are presented in Section 4. Section 5 summarizes the work and provides a conclusion.

《2. The state of the art》

2. The state of the art

《2.1. Life-cycle cost》

2.1. Life-cycle cost

The LCC of an infrastructure or system is one of the most critical factors during the planning and operating stages. The LCC is defined as the sum of the costs throughout the entire life cycle. It covers the expenses from production to elimination, consisting of infrastructure ownership, operation and maintenance, renewal and reform, and scrap and recycling. It asks decision-makers to consider the whole process and plan accordingly, with consideration of both the lowest cost and the long-term benefits.

As a decision support tool, LCC analysis is extensively applied to urban transit systems. It can be used to inform operators of the optimal procurement plan and bus schedules. Mitropoulos et al. [19] proposed an LCC method to support bus procurement by comparing various vehicle fuels and technologies, including internal combustion, hybrid, and electric vehicles. The LCC integrated external emission costs, time losses, and ownership costs. They reported that electric vehicles had the lowest LCC with the lowest external costs. Ke et al. [20] proposed an optimization method to calculate the system cost of converting the transportation system into a fully electric fleet in the early stage.

Regarding environmental aspects, LCC analysis serves as an important tool to evaluate the vehicle utilization impact on GHG emissions [21]. The total amount of GHG emissions is calculated based on four aspects, including: ① well-to-tank (WTT) emissions, which represents the electricity delivery from the source to the bus energy storage system; ② tank-to-wheel (TTW) emissions, which comprises energy conversion and distribution inside the bus, where the TTW stage is emission-free for a battery EB recharged from the grid; ③ glider emissions, which includes bus production, maintenance, and recycling processes; and④powertrain emissions, which consists of motor, battery, and electronics production. Ribau et al. [22] focused on optimizing LCC in powertrain design considering investment cost, efficiency, and life-cycle impact. They reported that EBs exhibit 67% fewer CO2 equivalent (CO2eq) emissions and 58% less fuel consumption compared with conventional buses. Chan et al. [23] conducted an LCC analysis on fuel alternatives to evaluate their impact on GHG emissions. They concluded that operational emissions account for the most significant portion of life-cycle emissions, however, the results were highly dependent on the modeling and operational approach.

Under the demand for transportation electrification, LCC analyses of charging infrastructures attract attention. A study compared the LCC for the same conductive and inductive bus charging systems to support charging station selection [24]. The researchers reported that an overall lower cost is provided by inductive charging based on the current price of the battery unit, but that considerable uncertainty would remain when it came to maintenance [25].

《2.2. Charging station deployment》

2.2. Charging station deployment

Electric transit systems require comprehensive infrastructure planning, since bus routes have to be equipped with sufficient charging points to support daily operation [26]. Based on the characteristics of charging EBs, two technologies are considered and emphasized: en-route charging and depot charging [27]. Depot charging, often known as overnight charging, is one of the most prevalent charging options for EBs. A lengthy and continuous charging period during nighttime is required under this technique. In this strategy, the capacity of the battery determines the travel range of the bus. Due to the technical limitations of lithium batteries, it is currently impossible for EBs to reach the driving range of diesel vehicles, which increases the necessary size of the EB fleet. The depot charging problem is designed to optimize bus charging schedules and minimize charging loads [28]. Compared with depot charging, en-route fast chargers offer convenience and improve charging accessibility during bus operation. The en-route fastcharging system in common use in Europe is achieved through automatic roof connections, with typical charging times of 4– 6 min for a full charge and 15 s for a partial charge. The system can be easily integrated into existing bus routes by installing chargers at intermediate or terminal stations. Timely energy replenishment makes EBs less dependent on battery capacity [29]. A smaller battery package results in lighter bus weight, higher passenger capacity, and lower investment costs for battery ownership, albeit with massive infrastructure ownership costs and high electric power demand charges [30]. Recent studies have focused on the comparative and economic analysis of these two charging strategies. Mohamed et al. [31] simulated the charging methods in a bus network and concluded that en-route charging is more feasible for full transit EB operation compared with depot charging. However, it might suffer from high and intermittent power demands. Liu et al. [32] compared the financial performance of depot charging versus en-route charging. Their findings showed that, given current pricing for en-route fast-charging stations and batteries, installing en-route fast-charging stations for EBs is always advantageous. He et al. [33] analyzed the onboard battery size and systematic cost of these two charging strategies. They claimed that overnight depot-charging EB systems require much larger onboard batteries than on-the-road fast-charging EB systems. Their simulation results further show that the total cost of an en-route fast-charging system is 50.7% less than that of an overnight depot charging system.

En-route charging can be realized through conductive (plug-in) and inductive (wireless) energy transfer. Inductive charging provides a lighter onboard battery that gets charged from magnetic fields, which requires an underground coil system and an onboard one [34]. The charging power can reach 200 kW. However, the efficiency is relatively low due to the air gap between the coil system [35]. The maturity of the conductive charging technology enables a maximum of 600 kW charging power through either overhead or ground/underground infrastructures, which can be easily installed with little impact on the existing road networks. Supported by Asea Brown Boveri (ABB) [36], a power technology group, the bus can be recharged at en-route charging stations with a 15 s energy boost while passengers are boarding and alighting. Based on the fast-charging concept, the applications assume that en-route charging has no significant impact on existing timetables [37]. In this transitional phase, conductive fast-changing technology is widely used in European countries such as France, Germany, Italy, the United Kingdom, and Sweden, while only a few projects with inductive charging are presently being implemented in Scandinavian countries [38,39].

Due to the relatively high cost of en-route chargers, arranging the location and quantity of charging piles has become a challenge in the procurement and planning process. Optimal planning policies must take availability, effectiveness, and efficiency into consideration as much as possible. Availability of charging station deployment could be achieved by setting the constraint that energy consumption should not exceed battery capacity [40]. The consumption between two stations is usually estimated based on a worst-case scenario, using a larger unit consumption or a specific value based on historical data [41]. Some studies further examine the particular components of energy consumption in depth and create estimates [42]. The optimal deployment of en-route charging stations fundamentally results from the efficient replenishment of real-time energy consumption. Thus, to ensure effectiveness, especially to extend the battery lifespan, the battery state of charge (SOC) must be kept within an optimal range [43] and be balanced with the charging station deployment plan [44]. When the SOC approaches the minimum level, a charging activity is required [45]. Objectives are set to minimize the number of charging stations, maximize the charging demand coverage, and reduce delays stemming from bus charging [46].

Although several studies have investigated charging station deployment for EBs, the majority of studies have adopted fixed bus routes and schedules as inputs [47]. Thus, homogeneous fleets are usually considered [48], and the fleet size is either empirical [49] or assumed [50]. This creates a large gap between optimization results at the planning level and optimal practical operation goals.

《2.3. Bus fleet management》

2.3. Bus fleet management

Two sub-problems are associated with bus fleet management: battery sizing and bus scheduling, defined at the operational level [51].

2.3.1. Battery sizing

The battery sizing problem assigns a bus with a specific battery capacity to an electrified line, fundamentally based on bus energy consumption [52]. In a battery EB transit system, the charging stations and onboard battery have the highest bearing on the ownership cost. The cost of the onboard battery accounts for at least 20% of the total expenses, depending on the size of the battery [53]. If a homogeneous bus fleet with the same battery capacity is considered to serve the transit network, it would inevitably lead to an unnecessarily large investment cost. Thus, it is recommended that the battery capacity of the bus be determined individually for each bus line according to the energy storage requirements, thereby reducing unnecessary purchases and LCC in the long run.

To determine the battery capacity, an adequate description of energy consumption is crucial. The state of the art has been focused on estimating and modeling the energy consumption of buses under real-world traffic conditions or based on different scenario settings [54–56]. Studies have reported that factors such as bus weight, the topography of the transit network, and energy efficiency can influence line-specific energy consumption and result in different charging demands. The charging demands that can be satisfied at charging stations depend on the dwelling time, the availability of charging infrastructures, and the battery SOC [57].

2.3.2. Bus scheduling

The bus scheduling problem extends from the traditional vehicle routing problem (VRP) to the handling of deadheading trip connections, in which a trip refers to bus service in a timetable and is characterized by the arrival and departure time at the origin, the destination, and some intermediate stops [58]. Unlike in the VRP, the station sequence of each trip is fixed, while additional energy-compatible constraints are incorporated to guarantee the service (readers interested in VRP issues can refer to Refs. [59,60]).

The problem-solving methodologies differ according to different charging strategies, as the required charging time varies. In the field of en-route charging, van Kooten Niekerk et al. [61] proposed a mathematical optimization model to tackle single-depot homogeneous fleet-scheduling problems while considering both linear and nonlinear charging times. A column generation algorithm was proposed to solve the problem. The simulation method is also widely used for bus scheduling, based on operational data to acquire an adequate number of EBs and ensure that the bus is punctual [62]. For depot charging, the deadhead trip between terminals and depots and the relatively high charging time should be carefully considered. Rogge et al. [63] proposed a mixed-integer linear-programming method with heuristic and metaheuristic solving algorithms. They reported that a lightweight bus offers a more energy-efficient mode of transportation, although the deadheading mileage increases due to the frequency of charging. A heterogeneous fleet can offer 5% extra energy savings. Thus, we can conclude that the connection between battery sizing and bus scheduling becomes significant when mixed fleets and energy consumption are considered during scheduling.

《2.4. Joint optimization of charging station deployment and bus fleet management》

2.4. Joint optimization of charging station deployment and bus fleet management

Due to the inconsistency of planning and operation, the charging station layout and EB fleet provided during the planning stage perform sub-optimally in real-time operation, resulting in insufficient infrastructures or excess resources [64]. Efforts have been made to jointly optimize charging station deployment and bus fleet management to some extent. A summary of different research focuses is listed in Table 1 [32,47,49–52,63,65,66]. We divided these studies by charging method into depot charging and en-route charging. Since the operation of EBs under the depot charging strategy relies on the battery size, the issue of how to make the bus schedule as reasonable as possible based on the battery capacity has become the mainstream of research in this field. Three studies have listed optimized bus scheduling together with depot charging scheduling [63,65,66]. Rogge et al. [63] were the first to consider mixed-fleet scheduling in depot charging optimization. They generated scheduling plans based on the given bus type, with different charging frequencies. Li et al. [65] further investigated this topic by considering charging scheduling and passenger demand uncertainty. An [66] focused on charging station coverage to support daily operation with a minimized bus fleet. Although Rogge et al. [63] attempted to consider a heterogeneous fleet, while the other two studies focused on a homogeneous fleet, the composition of the fleet was given in advance. Thus, only rational use of available resources could be achieved, although the better choice is to fully consider the future operation plan at the time of acquisition to realize a perfect fit and avoid wasting resources. The en-route charging method provides a convenient way to replenish the battery in time for daily operation. Most studies have combined this method with battery sizing to balance the cost of building a charging station with battery ownership [32,47,51,52]. These studies considered battery management compared with depot charging, with a focus on the battery discharge cycle and delaying battery aging. However, they overlooked the scheduling of EBs. For transit networks, battery sizing leads to fleet heterogeneity. Thus, the succession between trips could be significantly affected due to the various energy storage requirements, which was not considered in these studies. The possible conflict between demand and supply would create additional challenges for scheduling heterogeneous fleets.

《Table 1》

Table 1 Research focuses based on different charging strategies.

In summary, current research has evaluated the operational performance of EBs in different aspects. However, the majority of these studies are limited to one aspect, such as ownership costs or charging charges, and fail to provide a more comprehensive framework. Further consideration of life-cycle emissions would be of great benefit, both in terms of evaluating the potential of e-mobility systems for carbon neutrality and in finding insights to specify the path for further improvement. Moreover, previous studies on en-route charging have mainly focused on the strategic level when locating bus chargers instead of incorporating the operational level by considering bus scheduling. This focus poses difficulties when operating EBs within large-scale networks, in areas such as the connection between trips with different requirements for energy storage. We believe that these gaps offer underexplored opportunities for a systematic evaluation framework and a complex consolidated model. The joint optimization of battery sizing, charging station deployment, and bus scheduling, each bearing different functions and requirements, could indeed considerably improve operational efficiency and fill the research gap. In this context, a consolidated optimization model is proposed in this work to study en-route charging station deployment, battery sizing, and bus scheduling.

In this work, we make the following contributions to this field of research:

(1) An LCC analysis framework is proposed to evaluate the performance of the infrastructure and bus fleet in terms of both economic and environmental aspects.

(2) An optimization model is introduced to consolidate charger deployment, battery sizing, and bus scheduling, thereby breaking down the planning and operational boundaries, especially for enroute charging.

(3) A tailored branch-and-price approach is adopted to generate the optimal solution with low time and computational burdens.

(4) Two application scenarios are designed, including optimizing an existing single-line bus operation and planning for future multiple lines.

These contributions are made here for the first time, to the best of our knowledge. The literature contains no studies that develop a mathematical model for integrating these three sub-problems. Moreover, few studies propose a systematic evaluation criterion to assess an electrified public transit system from production to retirement.

《3. Framework and mathematical model》

3. Framework and mathematical model

《3.1. LCC analysis framework》

3.1. LCC analysis framework

The suggested LCC analysis framework aims to assess the performance of the EB transit system from both economic and environmental aspects. Fig. 2 provides the evaluation framework that outputs the bus fleet composition, the deployment of charging stations, and the bus schedule. The objective function is set as the annual equivalent LCC (with interest rate); it includes the infrastructure ownership fee, external cost of emissions, operational cost of charging, maintenance cost of battery changes, and other repairing work. The inputs consist of the bus lines (red lines) and related service trips based on the predefined timetable (grey and blue blocks in Step 3), the dwell time at each stop, and a set of available battery capacities (e.g., 50, 100, and 150 kW·h). Under this evaluation criteria, the Step 1 is to size the battery for each line to ensure that the battery of a bus is sufficient to serve the line. As shown in Fig. 2, in this step, line 16 is assigned the appropriate battery type from a set of available buses based on its energy storage requirement under the current charger deployment plan. The Step 2 is to set up charging stations by setting constraints. These constraints are for managing the battery SOC range, in order to ensure that, when the battery is approaching the minimum allowed SOC, a charger is installed at the next stop. For the bus scheduling part, the available route choices after finishing each service trip are provided, based on the time constraints and bus type compatibility constraints that determine the availability of connections between two trips. Thus, when the bus arrives at the destination, the current trip of line 16 (8:00–8:40) is completed, and the block is marked in grey. The bus scheduling process then starts, where alternatives are chosen based on a certain criterion such as the deadhead distance.

《Fig. 2》

Fig. 2. Overview of the life-cycle optimization model. SOCmin, SOCmax: minimum and maximum battery SOC allowed, respectively.

To better formulate and evaluate the integrated model of charger deployment, battery sizing, and bus scheduling, the following assumptions are made:

(1) The buses in this study are assumed to be battery EBs, with different bus types defined by different battery capacities, which is in line with the operational reality of most bus operating companies.

(2) The charging activity is assumed to start when the bus arrives at the station, once a charger is provided. The charging time is equal to the bus dwell time at each stop minus the charger connecting and disconnecting times. Since the charging station deployment is an issue in terms of the planning level, individual driving behavior is not taken into consideration.

(3) We assume that, at most, one fast charger is provided for a station due to the limited space of the bus bay. When a charging station is shared by multiple lines, the bus arrival time at the station may overlap. We assume that the later buses are able to wait for the first bus to finish recharging before they can be recharged. Since most en-route charging times are around 1 min [67], the delay caused by waiting will not be long and can be compensated for during the traveling time [68].

(4) The battery cycle life will be used to determine whether a battery should be replaced. When a battery reaches a specified number of cycles, the capacity is assumed to have degraded to 70% of the initial value. Typically, this battery will be considered as no longer applicable for an EB. However, the considerable remaining capacity can be applied to stationary applications, such as apartment energy supply and renewable energy storage. Therefore, we assume that the residual value of the battery pack will be 400 SEK·(kW·h)–1 [53], where 1 SEK ≈ 0.09 USD. 

《3.2. Consolidated optimization model》

3.2. Consolidated optimization model

The features of the model, including its objective functions and constraints, will be detailed in the following two sub-sections. A schematic diagram representing the relationship among battery sizing, charging station deployment, and bus scheduling sub-problems is illustrated in Fig. 3. Each sub-problem determines one of the key components of the objective function. For example, the battery sizing sub-problem deals with the optimal battery size, while the number of chargers and the size of the bus fleet are decided by the charging station deployment and bus scheduling sub-problems, respectively. Unlike sequential optimization problems, the integrated model positions the variables that restrict each other between the sub-problems. For example, the battery sizing problem determines how the vehicle’s SOC affects the choice of charging points. It also limits whether two trips can be connected when solving the bus scheduling sub-problem. Conversely, the location and the number of en-route charging piles also affect the size of the battery needed to serve the bus line. The solution approach for bus scheduling sub-problems will be illustrated in Section 3.3. Table 2 [1,30,51,53,69–71] provides a summarized description of the sets, parameters, and variables discussed in this section.

《Fig. 3》

Fig. 3. Schematic diagram of the consolidated optimization model. RMP: restricted master problem; [P1]–[P4] mean four problems.

《Table 2》

Table 2 Sets, variables, and parameters definition of the model.

3.2.1. Objective function

In this section, we describe the formulation of the objective function, which calculates the annual equivalent LCC of an electric transit system from production to elimination.

The objective function defined in Eq. (1) aims at minimizing the sum of the infrastructure ownership cost COWN, the external cost of emissions CEM, and the annual bus operational and maintenance cost COM.

Eq. (2) calculates the annual equivalent infrastructure ownership cost. It consists of two parts: the capital cost for buses and that for charging stations. The first part of Eq. (2) is equal to the cost of battery and bus purchases minus the residual value of the batteries. The decision variable indicates whether bus is in use, which is the key object for optimizing bus schedules, as shown in Eq. (15). The second part sums the cost of installing chargers at bus stops. Eq. (3) calculates the annual equivalent life-cycle emissions from WTT, glider, and powertrain based on the yearly travel distance , which is calculated in Eq. (20). After that, a monetary scalar is designed to convert the emissions into the external cost, based on the work in Ref. [1]. The annual operation and maintenance costs in Eq. (4) include four components: bus maintenance expenses, fleet charging costs, battery replacement costs, and station maintenance costs. The frequency of battery change for bus within the entire life cycle is calculated in Eq. (5), where the theoretical cycle life before battery replacement is defined as  , based on the fatigue model introduced in Ref. [48]. Assuming that the bus schedule remains the same every year, the entire energy consumption can be estimated as . Knowing the boundary conditions of the recharge SOCmax and discharge SOCmin, the frequency of battery replacement can then be estimated. It is notable that, for each vehicle, the energy consumption rate (for each , we have ) and the battery capacity ðfor each ; we have are known, whereas the only variable in Eq. (5) is  similar to that in Eq. (3). It should also be noted that, when the bus is not in use, = = 0.

3.2.2. Constraints

In this section, we illustrate the formulation for battery sizing (e.g., Eqs. (6)–(8) and (14)), charger deployment (e.g., Eqs. (9)– (13)), and bus scheduling (e.g., Eqs. (15)–(20)). The solution approach for the bus scheduling sub-problems is formulated as Eqs. (21)–(27). Following the convention of daily operations, we assume that the bus will be fully charged before it departs from the depot and will set SOC to SOCmax at the beginning of the day. We will also set different charging stations for different directions. 

Eq. (6) calculates the estimated energy storage requirement for a bus to serve station i + 1 with the maximum energy consumption rate θ. The parameter θ refers to the maximum energy consumption per unit among all available bus types. We aim to figure out the highest energy demand based on a specific charging station layout. It is notable that the station with the largest energy demand may not be the terminal but be an intermediate station instead, since the en-route charging station is available. When a charger is provided, this requirement decreases by . When two buses arrive at the same stop at almost the same time, we assume that the later bus will wait for the earlier bus to leave and charge. Thus, in the case study, we add a buffer time to the dwell time in order to cope with the charging waiting situation. After a certain type has been assigned to the route, the bus type related energy consumption rate will be updated by  The introduction of en-route charging should not interrupt the predefined schedule. Thus, the charging time at each charging station is assumed to be equal to the passenger boarding time based on real-world operational data [36]. Eq. (7) determines the battery sizing from an inventory P. The battery applicability level β indicates the percentage of battery capacity after degradation, such as 70%. Before being replaced, the degraded battery capacity β·Qp should be applicable for the bus route. Thus, we ensure that the lowest battery capacity β·Qp is sufficient for running the route with the highest energy demand . Eq. (8) further ensures that one bus type should be assigned to each line. Eq. (9) calculates the energy left when a bus arrives at station i + 1, with an updated energy consumption rate Bp and charging station layout xi. To keep the battery’s SOC in the optimal range, we set Eq. (10) to constrain the remaining energy such that, when a bus leaves station i, the remaining energy is larger than the summation of the traveling consumption between two adjacent stops and the lowest allowed energy level. Eq. (11) defines the upper bound of the battery energy, which should not exceed the maximum allowed SOC times the battery capacity. Eq. (12) calculates the battery SOC when the bus arrives at station i of line r. It should be noted that this nonlinear expression of will only be used as evaluation criteria in the case studies and will not be included in the optimization. Two decision variables for the charging station layout and battery sizing for the route are defined in Eqs. (13) and (14), respectively. Eq. (13) introduces the binary decision variable xi, which represents whether station i is a charging station. Eq. (14) defines the binary decision variable , which indicates the battery sizing for line r

We know that a battery with larger capacity costs more than a battery with smaller capacity. However, a larger capacity can support a longer trip and be more flexible during scheduling, with less distance anxiety. To further manage the heterogeneous bus fleet, we formulate an integer network flow sub-model [P1] based on a node-arc framework, which decides the bus fleet size  and further decides the values of COWN and COM in Eqs. (2) and (4), respectively. 

In this sub-model, the set of nodes G consists of ① the bus trip node, represented by index g and h; and ② the bus depot node, represented by the index 0. It should be noted that we compress a bus trip with a specific departure and arrival time and space into one node. Arc set A represents the possible serving sequences of the buses. It includes arcs from the depot to each trip g, arcs from trip g to another available trip h, and arcs from trip h back to the depot. When two nodes are connected, the arc is generated. Nevertheless, a time-compatible constraint is set for connection availability, which means that there should be enough time for buses to finish the first trip and then drive to the next trip’s origin. Based on the time constraint, we further define a set  containing the available inbound nodes that can be served by bus type before starting trip g. If the battery capacity of bus type p satisfies the condition Qp ≥ Qg and QpQh, then trip h is added to the set In(g, p). Similarly, we define the set  as the available outbound node set of trip g, which can be served by bus type after completing trip g. In the bus inventory Vp, the vehicles of type p are recorded. Given the network description, we consider a sequence of trips that begins at the depot and ends at the depot to correspond to a bus schedule. Therefore, minimizing the total number of buses is the same as reducing the total flow out of the depot, node 0. To facilitate the use of algorithms to solve this problem, we describe the following sub-model as [P1]. 

Bus scheduling sub-model [P1]:

The objective function described in Eq. (15) does not exist independently but is the specific description of  in Eq. (2) representing that minimizing the bus fleet is equivalent to minimizing the number of buses departing from the depot.

Eq. (16) depicts the relation between variables  and . It ensures that, when bus type p is assigned to line r, there should be one bus of this bus type to serve the trips running on line r. Eq. (17) ensures the conservation of bus flow. For depot 0, it means that a bus departing from the depot should be back at the end of the day. For trip node g, it means that connections between nodes should be generated based on the inbound and outbound node sets. According to Eq. (18), there must be exactly-one bus serving every trip node. Eq. (19) defines a binary decision variable . When the variable is equal to 1, the bus serves trips g and h sequentially; otherwise, the variable is set to 0. It is notable that  records the daily service route of bus . If we assume that this service route remains the same during the year, based on the distance of each trip and the deadhead trips, can be determined as shown in Eq. (20).

where disg denotes the travel distance of trip g, and deadheadgh represents the deadhead distance between sequential trips g and h. We assume that the route for buses will not change within the whole year. The parameter days is introduced to record the days in one year.

《3.3. Solution approach》

3.3. Solution approach

As a branch of the VRPs, two types of solution methods can be identified: heuristic methods for a quick search and exact methods for a global optimal solution [72]. The column generation technique is part of these exact methods [73]. When this problem is an integer program, the branch-and-price algorithm is introduced, which combines column generation and branch-and-bound procedures and is devised to generate provably high-quality solutions for large-scale problems [74]. This algorithm was recently introduced to solve the scheduling problem for EBs [74–76]. In the branch-and-price algorithm, the master problem [P1] is first transformed into a partitioning problem with binary variables [P2] and then further reduced to a linear limited master problem considering a subset of columns [P3]. The task of the pricing sub-problem [P4] is to find additional potential columns (i.e., bus schedules) that satisfy a set of requirements. In this work, the pricing problem innovatively includes customized bus type constraints. Finally, branch-and-bound methods are proposed to ensure that the relaxed solution is an integer. The algorithm helps decrease the size of the decision variables and facilitates the solution process. In this section, a tailored branch-and-price algorithm is introduced for the EB scheduling sub-problem.

3.3.1. Set partition model

We first convert [P1] into a set partition model [P2], where trips are covered by feasible schedules.

Set partition model [P2]:

We denote by L the set of feasible schedules for buses within one day. For buses of the same type, the schedule is the same. The objective function is shown in Eq. (21), which ensures that minimizing the bus fleet size is equivalentto minimizing the number of schedules covered by each bus. Eq. (22) ensures that each trip g is covered in the optimal schedule plan. It should be noted that  is a predefined parameter that represents whether trip g is a part of schedule and can be served by bus : This parameter significantly reduces the solution space. For each schedule , a binary variable  is defined in Eq. (23) to denote whether bus serves schedule .

3.3.2. Restricted master problem (RMP)

 The RMP with the subset of potential schedules is formulated in the model [P3]. Initially, we derive by the label correcting method presented in Section 3.3.3.

RMP [P3]:

subject to

The dual variables of model [P3] are defined as follows:

: the dual variables for constraint Eq. (25),

At each iteration of column generation, the dual variable of model [P3], , comprises the input parameters of pricing sub-problem [P4] to generate a new column with the lowest reduced cost (i.e., the objective of model [P4]).

3.3.3. Pricing problem

The column generation method manages to find the optimal solution to the master problem [P2] by repeatedly solving the RMP [P3] with a subset of potential schedules, , and a relaxed decision variable, ≥ 0. In order to find this schedule  efficiently, a pricing problem is proposed. The target is to find a trip chain, which should also be negative for the minimization problem, with arc costs equal to – . 

The pricing problem is shown to generate a feasible schedule associated with a negative reduced cost.

Pricing model [P4]:

subject to

Eqs. (16)–(19).

The pricing problem is an extension of the shortest path problem. This problem can be solved efficiently with a dynamic programming approach. The inbound and outbound sets defined in Section 2.2.2 further accelerate the solving time by processing the time and space constraints in advance, where the trips in the two sets are sorted by the departure time. To solve the pricing problem, we adopt the label correcting algorithm proposed by Feillet et al. [77]. The label indicates the partial trip chain from the depot to a current trip node g G: The label is defined as label (g, c, S) , where g is the last trip node visited in the partial trip chain represented by label; c is the reduced cost of the partial trip chain represented by label; and S represents the set of trips covered along the chain.

The unreachable trips are also collected in set S; that is, trips are not covered in the chain represented by label without violating time or capacity constraints. 

The pseudocode of the label correcting algorithm is summarized as Algorithm 1.

When the optimal objective of [P4] is negative, the bus schedule with the minimum reduced cost will be added to [P3] as a new entering column, and the route determined by will enter subset . The column generation procedure terminates when the minimal reduced cost is non-negative, indicating that no feasible trip chains can be added to in model [P3] to improve the current solution. 

3.3.4. Branch scheme

The branching procedure splits the solution space to restrict the search and tighten the bound [78]. This ensures that the added constraints are compatible with the master problem. The rule for vehicle scheduling depends on the property that a node should be visited at most once [79].

The branching rules introduced by Ryan and Foster [80] have been proven to be one of the most efficient schemes and are thus adopted in this paper. When is a partial solution to the RMP, the flow along the route can be defined as  and follows  ≥ 0 and  ≤ 1. For each solution ; there exist at least two nodes g and h, such that 0 <  < 1 . In the master problem, is required to be either 0 or 1. Thus, for any arc (g, h) ; two branches can be generated: 

• In the first branch, the upper limit on flow on arc (g, h) is fixed to 0; that is, = 0.

• In the second branch, the lower limit on flow on arc (g, h) is fixed to 1; that is, = 1.

This Ryan–Foster branching scheme can be easily managed in the column generation procedure with the following constraints: .

《4. Case study》

4. Case study

The proposed model and algorithm provide a straightforward method for assigning buses to lines, deploying bus chargers, and minimizing the bus fleet size with optimal schedules for realworld problems. To compare it with the current operational performance, one scenario is designed, while another scenario generates the optimal plan for a future multi-line bus service consisting of one existing line and one planned line.

All instances in this section are implemented in the General Algebraic Modeling System (GAMS) 25.1.3 and were solved with CPLEX 12.0 on a Dell laptop with a 1.9 GHz Intel Core i7 CPU and 8 GB running on Windows 10.

《4.1. Existing electrified bus line optimization》

4.1. Existing electrified bus line optimization

This scenario is designed for optimizing the existing electrified bus line in Gothenburg, which is the first venture of Volvo Buses for the purpose of developing, demonstrating, and evaluating nextgeneration sustainable public transport [81]. The current operational strategy is shown in Fig. 4(a). It depicts an existing electrified line 55 in its entirety, with a distance of about 7.6 km. This line is equipped with two terminal charging stations. Although the two directions have differently located terminal stops, deadheading can be carried out after the battery is fully recharged. The bus schedules provided by the bus operator contain 73 outgoing and 73 returning trips, which are currently served by ten pure EBs with 200 kW·h battery capacity. The operational data is provided by Vasttrafik. The proposed optimal solution is illustrated in Fig. 4(b). In contrast to the current plan, the charger deployment is considered separately for each direction in this scenario, with two chargers being provided for outgoing trips (blue circle) and two for returning trips (purple circle). The increase in the number of chargers is caused by the compensation of downsizing in battery capacity. Among the selected charging stations, two are located in terminals to provide adequate energy for trip connections, whereas the others are used for maintaining the battery SOC within an optimal range. The bus fleet size in the proposed plan is decreased from 10 to 7, and the battery capacity is decreased from 200 to 30 kW·h. In keeping with current operating conditions (Volvo 7900), we use lithium-ion batteries as traction batteries with a maximum charge power of 450 kW. Since it is unnecessary to consider the compatibility of bus types in singleline bus scheduling, the only limitation on trip connections is the time constraint. Therefore, trips with earlier departure times and less deadheading mileage are preferred in order to dispatch buses more efficiently, which is reflected in the definition of inbound and outbound trip sets.

《Fig. 4》

Fig. 4. Operational strategies of the existing setting and optimized plan. (a) Current plan; (b) optimized plan.

A comparison between the current plan and the proposed plan is made using the LCC evaluation framework. Fig. 5(a) describes the breakdown of annual equivalent LCC, which reveals the improvement delivered by the proposed plan. In the battery sizing module, a suitable battery capacity (30 kW·h) is allocated for the short line (7.6 km). The detailed calculation is illustrated in Eq. (7), where we divided the energy storage requirement calculated by Eq. (6) by a specific depth of discharge (e.g., 0.6) and compared it with the degraded battery capacity. We find that the 30 kW·h of battery capacity is sufficient to support single trip operation under the optimal charging station configuration. Moreover, the bus fleet optimization module enables a reduction of the fleet size, which reduces the bus investment expenses. More specifically, the annual equivalent LCC decreases by 1.96 million SEK, achieving a 30.4% reduction in comparison with the current plan. The individual measures—namely, the ownership cost, emission, and operational maintenance—are reduced by 1.80, 0.13, and 0.03 million SEK, respectively, with the external cost of emissions falling to around half that in the current plan. It can be seen that the ownership cost dominates the cost reduction, although the number of charging stations has doubled. Thus, effective bus scheduling is the most crucial factor in reducing LCC.

《Fig. 5》

Fig. 5. Performance of the current and proposed plans. (a) Breakdown of the annually equivalent LCC; (b) breakdown of the annual emissions; (c) SOC curves for outgoing trips; (d) SOC curves for returning trips.

Fig. 5(b) compares the optimized breakdown of the annual equivalent life-cycle emissions with the real-world operating plan. The results indicate that the annual emissions reduction in the glider, powertrain, and WTT stages is 16.28, 28.51, and 9.04 tCO2eq, respectively, with the highest mitigation level occurring in the powertrain, which achieves an 86% reduction through the use of a lower capacity battery. It is notable that Sweden’s carbon-intensive electricity mix is the lowest in the world due to its inclusion of renewable and nuclear energy, with an intensity of 20 gCO2eq·(kW·h)–1 . Thus, WTT delivers much lower emissions than in the average country. For example, in the United Kingdom, WTT emissions account for over 50% of the total lifecycle emissions, with an intensity of 300 gCO2eq·(kW·h)–1 [69]. If UK energy intensity is used as an input, WTT will surpass the powertrain and become the second-largest component of emissions. Compared with the impact of the fleet size, the battery capacity has a more significant mitigation effect on emissions. The SOC curve in both plans and the two directions is illustrated in Figs. 5(c) and (d), respectively. The green line shows the SOC curve under the current plan, while the blue and pink lines represent the swing of the SOC in the proposed plan for different directions. If the SOC drops first and then rises on the same abscissa, it means that a charging station is set at this point. In the proposed plan, for the outgoing trips, when a bus travels around 5 km, it reaches a charging station, and the battery SOC increases to 0.87. In order to serve the next trip with enough energy storage, another charger is located in the terminal station, and the battery SOC increases to 0.95 after the bus arrives at the destination. For returning trips, a bus travels 4.6 km before arriving at the first charging station. Accordingly, the battery SOC increases to 0.89 when the bus leaves this stop. Similarly, the second charger is provided at the destination. In contrast, in the current plan, due to the large battery capacity, the entire trip consumes around 10% of the energy storage. Therefore, due to the small battery capacity used, the number of charging stations is doubled even in the proposed plan, and the SOC fluctuation is higher than in the existing plan. It should be noted that the fluctuation of the SOC depends on the distance traveled and the energy consumption rate [82]. However, in order to clearly indicate battery SOC at each stop and to evaluate the charging plan intuitively, we assume that a change in SOC only occurs when the bus arrives at the charging station. The SOC between two stops is represented by a horizontal line, which is consistent with the result of Eq. (12).

In the current plan, utilizing a bus with a large battery capacity also has some advantages, such as extending the battery cycle life. To compare the cycle life of different plans, the SOC curves on the outgoing and return trips are summarized in Figs. 5(c) and (d). For both directions, the SOC in the current plan remains in the interval from 0.95 to 0.85, whereas the SOC in the proposed plan fluctuates from 0.95 to 0.61 in the outgoing trips and from 0.95 to 0.65 in the returning trips. We take the lowest values of the SOC as SOCmin for each plan, which are 0.85 and 0.61, respectively. When SOCmin is 0.85, as in the current plan, the battery cycle life can reach 49 000 times. When the value decreases to 0.61, the cycle life decreases to around 6720 times. As a result, the battery change frequency increases in the proposed plan, and the yearly operational fee will increase accordingly. In general, combining the above points, lightweight batteries and a smaller bus fleet perform better both economically and environmentally. At the same time, battery replacement and maintenance can compensate the cycle life reduction caused by the giant SOC swing. 

The case study was solved with CPLEX 12.0. It took 43 s to generate the optimal solution.

《4.2. Future multi-line planning》

4.2. Future multi-line planning

This scenario focuses on near-future electrified bus line planning, with one existing line (the same as in Section 4.1) and one planned line currently being run by diesel buses but being tested for electrification [83]. It should be noted that the proposed model does not limit the problem scale. The two bus lines were chosen because they are entirely in line with Gothenburg’s current electrification plan and the inter-lining situation can be represented in this scenario. Table 3 summarizes the major characteristics of the two lines, including the length, travel time, serving time, number of trips, and number of stops, where the number of stops is doubled, since we separate outgoing and returning directions. For more information regarding the value of other modeling parameters, please refer to the Appendix A.

《Table 3》

Table 3 Electrified lines’ major characteristics.

The possible trip connections and their corresponding deadheading mileages are shown in Fig. 6. Buses usually run back and forth on the same line, as shown in the first column of the first row and the second row. However, in daily operation, buses are allowed to serve different lines sequentially in order to conduct a flexible schedule and reduce the size of the fleet, as shown in the third row. Similarly, due to the uncoordinated planning of the timetable in two directions, the frequency of departures in one direction is often higher than that in the other direction. As a result, buses are allowed to serve the same direction sequentially with a long deadheading trip, which is illustrated in the second column. When a bus is assigned to serve two lines, we eliminate the single-direction service choice since the deadheading mileage is too large, which is not conducive to generating an efficient schedule.

《Fig. 6》

Fig. 6. Possible trip connections.

Fig. 7 shows the optimal charger deployment for this network, with the existing line in solid black and the planned line in dashed brown. The battery sizing module assigns buses with a 30 kW·h battery capacity to both lines. In contrast, the charger deployment module selects eight stops as charging stations from the available station set, which contains 64 bus stops (32 in the outgoing direction and 32 in the returning direction). Half of the selected charging stations are shared by two lines (solid circles in Fig. 7), while the others are close to the destination (hollow circles in Fig. 7) to ensure that enough energy is stored to serve the next trip. When comparing Fig. 4(b) and Fig. 7, it can be seen that, even for the same electrified line, the selection of charging stations is different under the conditions of the single-line and network-scale optimization. More specifically, only one of the four charging stations coexists in the two plans. It is worth noting that the other three charging stations that differ from those in the single-line optimization plan are located on the stations shared by the two lines. The advantage is that, since the two lines’ arrival times do not overlap, these charging stations can be more efficient and fully utilized.

《Fig. 7》

Fig. 7. Optimal charger deployment for a multi-line bus service.

The optimal bus scheduling is shown in Fig. 8, with a fleet of 26 buses. The number of trips served, operational time, and deadheading mileage for each bus are shown in each subfigure, respectively. In the optimization, the same bus type is allocated to two lines, which enables a reduction of the bus fleet since buses are allowed to serve trips from both lines. To avoid long deadheading mileage, it is preferable to run a bus back and forth on the same line. In this first subfigure, the number of trips served by each vehicle is collected in ascending order, and the order remains when displaying the performance in terms of operational time and deadhead mileage. Analyzing the data in the first and third subfigures, it can be seen that the strategy of sharing lines is advantageous because of the increased trip coverage of a bus when a tolerable bus deadhead mileage is allowed. The highest coverage for one bus is 25 trips. When extracting the first column (bus 1) of these two subfigures, it can be seen that the bus with the smallest number of trips has the longest deadheading distance. Due to the uncoordinated timetable, the trips served by each bus will fluctuate. The figure shows that the fluctuation is between 10 and 25, and the average is 13 trips per bus. The bus operational time shown in the second subfigure refers to the time duration between a bus departing from the depot and returning to the depot; this is not the exact bus running time, as the waiting time for trip connection is also included. The average operational time is around 15 hour per bus, while the longest is 24 h for the planned line. The last few columns in subfigures 1 and 2 indicate that the broadest trip coverage requires the longest bus running time. In the third subfigure, there are 14 buses with zero deadhead mileage, which means that they are dedicatedly assigned to serve the planned line back and forth. However, the origins and destinations are located differently in the two directions of the existing line. Thus, all buses serving the existing lines by going back and forth still have deadheading mileages of around 1 km. As a result, the majority of buses have a certain deadhead mileage. The average deadhead length is around 12 km, while the longest is 50 km when a bus travels between two lines or serves a single direction for one line. It should be noted that, as we are scheduling the plan for the new line based on the existing timetable, the timetable and bus schedules could not cooperate effectively when multi-line service is not allowed. Thus, the two directions’ uncoordinated departure times require the bus to run an entire deadhead trip to continuously serve two trips in the same direction in order to reduce the fleet size. This notable drawback offers an opportunity for the joint optimization of timetables and bus schedules.

《Fig. 8》

Fig. 8. Optimal schedule for each bus. (a) Trip serving amount; (b) serving time; (c) deadheading distance.

The SOC curves for each line in each direction are illustrated in Fig. 9. The maximum SOC fluctuation is around 0.35, which enables 6720 cycles during the battery lifetime. In both directions of the existing line, the bus recharges twice, while the bus recharges four times in the planned line. Moreover, this configuration ensures that, after the bus reaches the terminal, the remaining SOC is still above 92% for the existing line and equal to 100% for the planned line. Unlike the charging station layout in the previous section, the charging station in the existing line is not the terminal station but one stop before it. The reason is that the distance between the two stations is small, and both lines share the selected station. However, if the last two stations are far apart, the terminal station is usually set as a charging station to ensure the subsequent journey. Thus, the proposed plan not only ensures sufficient energy storage but is more affordable as well.

《Fig. 9》

Fig. 9. SOC curves for the existing and planned lines.

To further evaluate the performance, the breakdown of the annual equivalent LCC is summarized in Table 4. As in the conclusion in the previous section, the investment in the ownership of infrastructures accounts for the largest share, at 62.5%. This is followed by the cost of operation and maintenance—namely, the battery changes and energy consumption—which accounts for 36.9%. Green electricity production in Sweden makes the external cost of emissions much lower than the other costs, at only 0.56% of the total LCC. The emissions delivered by the glider, powertrain, and WTT elements are less than 200 tCO2eq·a–1 . It is notable that the emissions of the WTT, powertrain, and glider in the networkscale EB system have a consistent pattern compared with those in the previous section; more specifically, the glider accounts for the largest share, followed by the WTT and finally the powertrain. Each component of the LCC is around three times higher than that in the proposed plan for the single-line service due to the larger bus fleet and increased number of charging stations. However, we have not taken into account the future of green manufacturing or the widespread use of clean energy, both of which would be projected to reduce the glider and WTT emissions to a relatively low level if fully included. Supposing that deadheading between the two lines were not allowed, then the bus fleet would increase by a minimum of three. Moreover, the cost saved by charger sharing could also relieve the capital burden. 

《Table 4 》

Table 4 Annual equivalent LCC breakdown of the planned line.

To evaluate the performance of the proposed algorithm, we test two different methods for the same case using GAMS. If the algorithm does not include column generation, the model introduced in Section 2.2 will be solved directly by the mixed-integer program solver; otherwise, [P2]–[P4] will be solved sequentially under the proposed framework. Table 5 shows that the calculation time required is 20 times longer when solving the model with a mixed-integer program (MIP) solver. Thus, the result proves the efficiency of the proposed solving algorithm in practical applications.

《Table 5》

Table 5 Performance comparison of different algorithms.

《5. Conclusions》

5. Conclusions

In this work, a novel optimization approach is proposed to consolidate the charging station deployment, battery sizing, and bus scheduling problem. An LCC analysis framework is introduced to evaluate the performance of electrification infrastructure investment decisions. To make the problem tractable with a low computational burden, a tailored branch-and-price algorithm is suggested.

In the optimized results, two case studies are evaluated, including existing line optimization and further multi-line service planning. The results show that the integration of the planning and operational layers dramatically reduces the LCC by 30.4% and, in particular, the cost of infrastructure ownership by 33.87%. Reducing the bus fleet size is the most critical step in reducing the LCC and mitigating life-cycle emissions. By comparing actual operations and optimization results for a single line and multiple lines, it is discovered that the share of ownership in the optimized results decreased from 82.7% to 78.6% for one line, and then to 62.5% for multiple lines, implying that large-scale road networks will tend to rely more on efficient daily operation strategies. This is why bus scheduling is introduced as an essential sub-problem in the model. Although downsizing the battery capacity and reducing the number of charging stations are mutually exclusive goals, even if the number of chargers doubles, the adoption of smaller capacity batteries can significantly relieve the economic burden in the evaluation framework. The aim of battery downsizing is to provide reliable services for the line, which also reflects the benefits of combining battery sizing and charging station optimization. Furthermore, we find that, with an expansion of the road network, the powertrain, WTT, and glider emissions consistently grow about three times as much as those for a single line, making the introduction of green manufacturing and clean energy increasingly important. The results confirm that this model not only minimizes the LCC but also guarantees a reliable public transit service. We also summarize essential issues that need to be improved urgently from economic and environmental perspectives.

It should be noted that the proposed method offers a wide range of applications due to its joint consideration of the strategic and operational layers. It is suitable for existing plan evaluation and adjustment and for the feasibility analysis of future planning as well. For these applications, a reasonable balance of charging infrastructure deployment, bus fleet investment, and operational bus scheduling can be determined. The importance of influencing factors in different cases can also be observed. Therefore, whether it is for optimization or planning, a transportation company can directly utilize the generated plan or customize it as necessary. Moreover, this optimization method can be extended and adapted to bus networks with different infrastructures, such as wireless chargers and dynamic charging lanes, by customizing some of the parameters and input data to assist with the implementation of future charging technologies. The application and extension of the proposed method will enable a detailed assessment of public transport transformation from diesel to EBs. It is believed that proper planning could further accelerate the penetration of bus electrification.

Further research should include, first and foremost, an extension of the developed model to a large-scale network in order to better represent reality, including aspects such as multi-line shared charging stations. Irregular operational disturbances should also be addressed, such as fluctuations in passenger demand, in order to avoid unstable bus dwell times and delayed trip arrivals. Thus, the delay caused by such disturbances should be added as a penalty function. Finally, the influence of the electrochemical characteristics of the battery on its cycle life under different charging station configurations must be further considered. We envision our model as being employed in a more practical framework.

《Acknowledgments》

Acknowledgments

This research is financially supported by EU Project SMUrTS under JPI initiatives.

《Compliance with ethics guidelines》

Compliance with ethics guidelines

Ziliang Zeng, Shuaian Wang, and Xiaobo Qu declare that they have no conflict of interest or financial conflicts to disclose.

《Appendix A. Supplementary data》

Appendix A. Supplementary data

Supplementary data to this article can be found online at https://doi.org/10.1016/j.eng.2022.07.019.