Locating Battery Swapping Stations for a Smart e-Bus System

Abstract

With the growing interest and popularity of electric vehicles (EVs), the electrification of buses has been progressing recently. To achieve the seamless operation of electric buses (e-Buses) for public transportation, some bus stations should play the role of battery swapping station due to the limited travel range of e-Buses. In this study, we consider the problem of locating battery swapping stations for e-Buses on a passenger bus traffic network. For this purpose, we propose three integer programming models (set-covering-based model, flow-based model and path-based model) to model the problem of minimizing the number of stations needed. The models are applied and tested on the current bus routes in the Seoul metropolitan area of South Korea.

1. Introduction

As the concern over global warming and energy issues grows, electric vehicles are increasingly considered as an alternative to traditional vehicles and have hence gained much attention from the general public. With the increasing interest and popularity of electric vehicles (EVs), many countries have developed electric buses and introduced them on a trial basis. In South Korea, the Seoul metropolitan government has operated electric buses around significant tourist destinations and has been gradually expanding the network [1]. Jeju island, the largest island in Korea, is preparing for pilot electric bus operation [2]. In addition to these attempts, academic research into the usefulness and operation policies of electric vehicles is actively underway [3]. Outside Korea, China has grown its market size of electric buses significantly [4], and we can infer that the demand for e-Buses is increasing continuously. Other major countries, such as the U.S, European countries, and India, have trends of increasing demand and application of electric buses, and these trends are expected to continue in the future [5].

There are several types of electric buses, as well as operation methods. The most typical ones are the plug-in type, the wireless rechargeable type, the trolley bus and the battery exchange type. Since each method has its special characteristics, it cannot be easily concluded which is the best. However, depending on the type of electric bus, the factors and problems requiring consideration vary widely. For example, the trolley bus needs wires for electric supply. Thus the constraint of wires becomes an important consideration, and there are many studies treating issues related to wire networks. Teoh et al. [6] cover routing network design and fleet planning for Malaysia’s transportation situation. On the other hand, for the battery charging system, efficient route configuration within a given battery capacity is important since charging takes time and is usually only possible in depots. Thus, regarding charging system problems, locating a depot or optimizing time scheduling given a network configuration are major concerns. In fact, some studies have focused on electric bus operations and the problem of locating charging stations. Relatively recently, Rogge et al. [7] aimed to optimize the charging schedule of electric buses to minimize overall costs, including vehicle investment, charger investment, operational costs, and energy expenses. Liu and Wang [8] treated the problem of locating several types of recharging facilities, especially wireless recharging facilities. There is also ongoing research into operating electric buses based on battery swapping. In battery swapping cases, each vehicle travels with a battery and can swap the battery at the designated places for exchange, so-called battery swapping stations. The advantage of the battery swapping system is that it does not require huge infrastructure as a trolleybus system does, and unlike the battery charging system, it is possible to replace the battery quickly along the route. In the battery swapping system, locating battery swapping stations is a crucial problem. Ko and Shim [9] deal with the issue of selecting the location of battery exchange stations for the seamless operation of electric taxis, which operate with no fixed routes. Furthermore, several studies deal with the issues related to the scheduling of battery swapping when operating electric vehicles or buses. For example, Chao and Xiaohong [10] and Kang et al. [11] dealt with the time scheduling problem of battery swapping systems. Sarker et al. [12] proposed a numerical model for selecting the location of battery swapping stations in terms of the supply of and demand for electricity, and the scheduling of electrical supply. Our paper differs from those studies in that we aim to determine both the location of swapping stations and the scheduling of battery swapping. We approach battery swapping systems as being underlying problem situations. In doing so, we deal with the problem of operating an electric bus in a public transit network with a battery swapping system. To achieve this, we assume the installation of a so-called Quick Charger Machine (QCM) over the public bus transit network (see Figure 1). We refer those who are interested in the QCM, to the web page of reference [13].

As Figure 1 shows, QCM is a machine installed in a proper bus station and it transforms an eligible bus station into a battery swapping station. Since the automated machine replaces the battery, it is possible to replace the battery within a short time (say, within one minute) while passengers are transferring. Inevitably, for the seamless operation of electric buses (e-Buses) in public transportation, some existing bus stations should play the role of battery swapping stations due to the limited travel range of e-Buses. Considering that the number of QCMs is related to the operational cost of the system, it is important to minimize the total number of QCMs installed. In this problem, we do not explicitly consider the installation costs of these QCMs, which may differ by location.

This problem can be partly viewed as a location routing problem (LRP) variant.The LRP considers vehicle routing and related resources (e.g., facilities, customers and so on) to find proper facility locations, determine the optimal number of facilities or vehicles, and optimize the routing plan [14]. The LRP itself has many variants depending on the particular purpose or problem situation [15,16]. In this paper, the problem is to find the number of facilities and their optimal locations. In the general LRP, some nodes have demands, and vehicles route them to satisfy those demands. In this problem, we can see the similarity with the LRP in the sense that the facilities considered are bus stations with a QCM and the vehicles travel over the bus transit network while preventing battery shortage by visiting some of the QCMs. There are many papers in literature (e.g., [17,18,19]) introducing the basic concept of the LRP, its variants and solution approaches. Amaya et al. [20] study the operation of vehicles and the location of depots with capacitated vehicles, a problem defined as the capacitated arc routing problem (CARP). The specific problem of that paper is that the service vehicle (SV) travels service arcs in a graph, and since the SV has a finite capacity, to enable its continuous service, it is replenished by a refilling vehicle (RV). There is a depot to refill the RV, and the paper tries to find the optimal location of the depot and optimal min-cost path. If we assume the refilling vehicles are fixed and uncapacitated, this problem situation becomes similar to our assumed problem situation. Nevertheless, our paper is completely different in that it considers the cost incurred in routing. Xing et al. [21] consider several depots in the CARP model. Bektaş and Elmastaş [22] deal with a similar problem to ours, and find the optimal locations for the depots, but consider just one main depot in the bus route for fulfilling buses without any other refill point. Yang and Sun [23] assume the problem of delivering goods to customers from a depot using electric vehicles. The depot serves as both a supply of goods and a battery swapping station. Within this setting, they select depot locations that minimize overall shipping costs. Rogge et al. [7] propose optimal charging priority and charging location in the battery swapping problem, and examine a similar situation to ours. However, this paper is different to ours in that it deals with a centralized charging system, which means that battery charging occurs only at the depot. Boccia et al. [24] deal with an interesting problem similar to ours in some respects. They determine the location of the facility on the flow network that maximizes the flow through the facilities. To summarize the above, our study significantly differs from previous studies. In our problem, each node (i.e., a bus station with QCM) can serve as a refill point while most of the previous works set a separate depot as the central refill point.

This paper is organized as follows. Section 2 presents the three different proposed mathematical programming models for the concomitant model. In Section 3, the proposed models are applied and tested on the current bus transit network in the Seoul metropolitan area of South Korea and the experimental results are discussed, including comparisons of the models. Finally, we provide a conclusion in Section 4.

2. Model

In this section, we present the mathematical programming models for swapping station deployments for an e-Bus transit network. The deployment of a network of swapping stations is essential given e-Buses’ limited travel range. This paper considers the problem of locating battery swapping stations for electric buses on a bus transit network while appropriately addressing the battery capacity of each bus in operation. Given the situation, the objective of our problem is to optimize network performance. Specifically, we maximize the flow covered by a predetermined number of stations or minimize the number of stations needed to cover traffic flows. For this, three different mixed-integer programming models are proposed to address the concomitant problem. These are the set-covering-based model (Section 2.3.1), the flow-based model (Section 2.3.2), and the path-based model (Section 2.3.3).

2.1. Assumption

Before presenting the mathematical models, we first present the assumptions while maintaining the essence of the problem. We note that all these assumptions are applied to the three models. First, battery swapping can be achieved within the time period the passengers are transferring so that the problem of interest is free from battery swapping time constraints. Second, if a bus route from a depot to the end does not require battery swapping during a journey, we exclude this route from consideration. Third, we also assume that a battery in the swapping station is always a fully charged battery; in other words, there are no replacements with an incompletely charged battery. Lastly, considering QCM assumptions, we ignore the possibility that there exist some stations where battery swapping facilities cannot be installed due to geographical and spatial problems or administrative problems.

2.2. Notation

The sets, parameters, and decision variables used in the models are listed in

Table 1. Mathematical notations used in this paper.

Sets and Parameters
$\mathcal{N}$	$=\left\{1,2,\dots ,N\right\}$. Set of bus stops
$\mathcal{A}$	$=\left\{(i,j)|i,j\in \mathcal{N},j(\ne i\left)\mathrm{is}\mathrm{directly}\mathrm{accessible}\mathrm{from}i\right(i.e.,i\to j)\right\}$. Set of arcs
${\mathcal{N}}_s\subseteq \mathcal{N}$	Set of potential bus stops equipped with battery swapping facility (Quick Change Machine (QCM))
$\mathcal{R}$	$=\left\{1,2,\dots ,R\right\}$. Set of bus routes
${\mathcal{D}}_o\subset {\mathcal{N}}_s$	Set of origins (depots) for all bus routes
${\mathcal{D}}_d\subset {\mathcal{N}}_s$	Set of destinations (depots) for all bus routes
${}_r$	Total number of bus stops on route $r\in \mathcal{R}$
$D_{max}$	Maximum travel distance per charge
${\overrightarrow{T}}^r$	$\equiv (n_1^r,n_2^r,\dots ,n_{{}_r}^r)$. Ordered sequence of bus stops on route $r\in \mathcal{R}$ where $n_i^r\in \mathcal{N}$ for all $i=1,2,\dots ,{}_r$. Note that (i) $(n_i^r,n_{i+1}^r)\in \mathcal{A}$ for $i=1,\dots ,{}_r-1$ and (ii) $n_i^r{\prec }_r{n}_j^r$ holds for any i and j such that $i<j$ where the precedence relationship in the ordered sequence is denoted by ${\prec }_r$.
${\mathcal{T}}^r$	$=\left\{n_1^r,n_2^r,\dots ,n_{{}_r}^r\right\}$. Ordered set of bus stops on route $r\in \mathcal{R}$
$D^r(\alpha ,\beta )$	Travel distance from bus stop $\alpha \in \mathcal{N}$ to bus stop $\beta \in \mathcal{N}$ on route $r\in \mathcal{R}$
${\mathcal{N}}_s^r$	$=\left({\mathcal{T}}^r\cap {\mathcal{N}}_s\right)$. Set of potential QCMs in ${\mathcal{T}}^r$
${\mathcal{T}}_{\alpha }^r$	$=\left\{\alpha \equiv n_i^r,n_{i+1}^r,\dots ,n_j^r\right\}\subset {\mathcal{T}}^r$. Maximal ordered subset (MOS) of ${\mathcal{T}}^r$, starting from a potential QCM $\alpha \in {\mathcal{N}}_s^r$ such that $D^r(n_i^r,n_j^r)\le D_{max}$ and $D^r(n_i^r,n_{j+1}^r)>D_{max}$ For given ${\mathcal{T}}_{\alpha }^r=\left\{\alpha \equiv n_i^r,n_{i+1}^r,\dots ,n_j^r\equiv \beta \right\}$, $D^r(\alpha ,\beta )$ is the maximal distance that e-Bus can drive without any battery swapping, assuming that a battery swap is performed at $\alpha \in {\mathcal{N}}_s$.
Decision variables
$y_i$	1 if a QCM is located at bus stop $i\in {\mathcal{N}}_s$, and 0 otherwise

:

We remark that the eligibility of each bus stop for a QCM (${\mathcal{N}}_s$) can be confirmed during the preprocessing process by considering factors such as electrical grid infrastructure and the availability of the construction space required for a QCM.

2.3. Mathematical Programming Formulations

In this section, we present the mathematical programming formulations for the problem of interest—i.e., set-covering formulation, flow-based formulation and path-based formulation—and then discuss the pros and cons of each formulation.In fact, we propose three types of formulations for the same strategic decision making problem of locating QCMs in a bus transit network. We will see that the set-covering formulation is efficient in terms of computational performance but that it lacks flexibility when incorporating additional issues such as Quality of Service. To address this drawback, flow-based and path-based formulations are also proposed since their models can incorporate these additional issues, as we will discuss in the subsequent sections.

2.3.1. Set-Covering Formulation

First, with the maximal ordered subset (MOS) defined in Table 1, this problem can be basically viewed as a set-covering problem. Figure 2 illustrates the definition of MOS and the basic idea of the set-covering formulation. If at least one QCM is included in all the MOSs for each bus route, we can confirm that no full battery discharge occurs during the bus’s traversal of that route, since MOS is defined as the maximal distance that an e-Bus can drive without needing a battery swap. By incorporating the definition of MOSs, the following formulation can be proposed to minimize the overall number of QCMs.

Model (Set-covering model)

$$\begin{array}{cc}\hfill \mathrm{minimize}& \sum _{\alpha \in {\mathcal{N}}_s}{y}_{\alpha }\hfill \end{array}$$

(1a)

$$\begin{array}{cc}\hfill \mathrm{subject}\mathrm{to}& \sum _{\beta \in {\mathcal{T}}_{\alpha }^r\cap {\mathcal{N}}_s}{y}_{\beta }\ge 1,\forall r\in \mathcal{R},\forall \alpha \in {\mathcal{N}}_s^r\hfill \end{array}$$

(1b)

$$\begin{array}{cc}\hfill & y_{\alpha }=1,\forall \alpha \in {\mathcal{D}}_o\hfill \end{array}$$

(1c)

$$\begin{array}{cc}\hfill & y_{\alpha }\in \{0,1\},\forall \alpha \in {\mathcal{N}}_s\hfill \end{array}$$

(1d)

The objective function in Equation (1a) is to minimize the total number of QCM installations over the e-Bus transit network. We note that, as for conventional facility location models, this objective function can be easily modified to minimize QCM installations and annual maintenance costs. However, in this paper we limit our attention to minimizing the total number of QCM installations. Constraint () indicates that each MOS must contain at least one QCM, as discussed above. Constraint () guarantees that all the depots have QCM functionality.

We assume that $|{\mathcal{N}}_s|$ is large enough to warrant that ${\mathcal{T}}_{\alpha }^r\cap {\mathcal{N}}_s\ne \varphi$ for all $r\in \mathcal{R}$, $\alpha \in {\mathcal{N}}_s^r$; otherwise, the problem becomes infeasible. This formulation has a compact form, compared with the other formulations below. However, the set-covering model only suggests the locations of QCMs among potential bus station candidates for QCM installation with y variables. We will see that the other proposed formulations simultaneously determine not only the QCM locations but also the battery swapping schedule of each bus en route. Thus, with this formulation, it is difficult to take Quality of Service (QoS) into account because of the difficulty of analyzing the operational efficiency of each bus and route due to limited information on where and how many times battery swapping occurs. We discuss this aspect further in Section 3.5. The formulations introduced below complement these perspectives and should be more informative.

2.3.2. Flow-Based Formulation

As noted earlier, the set-covering formulation in Section 2.3.1 does not explicitly provide detailed locations of where to swap batteries for each bus (i.e., battery swapping scheduling for each bus en route). Thus, we here suggest an alternative model which overcomes the limitation of the first model. This model is based on the idea of minimizing the number of QCM installations while satisfying all the in- and out-flows and the connectivity of all stations. For this, we first introduce the additional notations in

Table 2. Additional notations for flow-based formulation.

Sets and Parameters
$L^r\left(n_i^r\right)$	Last bus stop where a QCM is installed in ${\mathcal{T}}_{n_i^r}^r$ (i.e., $L^r\left(n_i^r\right)=n_j^r$ if the ordered set of ${\mathcal{T}}_{n_i^r}^r\cap {\mathcal{N}}_s$ with respect to ${\prec }_r$ is equal to $\left\{n_i^r,\dots ,n_j^r\right\}$).
${\mathcal{I}}^r\left(\alpha \right)$	$\equiv \left({\mathcal{T}}_{\kappa }^r\setminus \left\{\alpha \right\}\right)\cap {\mathcal{N}}_s^r$ where $L^r\left(\kappa \right)=\alpha$. Note that ${\mathcal{I}}^r\left(\alpha \right)=\varphi$ if $\alpha \in {\mathcal{D}}_o$.
${\mathcal{O}}^r\left(\alpha \right)$	$\equiv \left({\mathcal{T}}_{\alpha }^r\setminus \left\{\alpha \right\}\right)\cap {\mathcal{N}}_s^r$. Note that ${\mathcal{O}}^r\left(\alpha \right)=\varphi$ if $\alpha \in {\mathcal{D}}_d$.
Decision variables
$x_{\alpha \kappa }^r$	1 if a bus on the route r performs a battery swapping at QCM $\alpha$ and the next immediate battery swapping is performed at QCM $\kappa$ where $\alpha ,\kappa \in {\mathcal{N}}_s^r$ and $\alpha {\prec }_r\kappa$, and 0 otherwise.

and then introduce the flow-based model.

Model (Flow-based model)

$$\begin{array}{cc}\hfill \mathrm{minimize}& \sum _{\alpha \in {\mathcal{N}}_s}{y}_{\alpha }\hfill \end{array}$$

(2a)

$$\begin{array}{cc}\hfill \mathrm{subject}\mathrm{to}& x_{\alpha \kappa }^r\le y_{\alpha },\forall \alpha ,\kappa \in {\mathcal{N}}_s\mathrm{with}\alpha {\prec }_r\kappa ,\forall r\in \mathcal{R}\hfill \end{array}$$

(2b)

$$\begin{array}{cc}\hfill & x_{\alpha \kappa }^r\le y_{\kappa },\forall \alpha ,\kappa \in {\mathcal{N}}_s\mathrm{with}\alpha {\prec }_r\kappa ,\forall r\in \mathcal{R}\hfill \end{array}$$

(2c)

$$\begin{array}{cc}\hfill & \sum _{\kappa \in {\mathcal{O}}^r\left(\alpha \right)}{x}_{\alpha \kappa }^r-\sum _{\kappa \in {\mathcal{I}}^r\left(\alpha \right)}{x}_{\kappa \alpha }^r=b_{\alpha },\forall \alpha ,\kappa \in {\mathcal{N}}_s\mathrm{with}\alpha {\prec }_r\kappa ,\forall r\in \mathcal{R}\hfill \\ \hfill & \mathrm{where}{b}_{\alpha }=1\mathrm{if}\alpha \in {\mathcal{D}}_o,b_{\alpha }=-1\mathrm{if}\alpha \in {\mathcal{D}}_d,\mathrm{and}0\mathrm{otherwise}\hfill \end{array}$$

(2d)

$$\begin{array}{cc}\hfill & y_{\alpha }=1,\forall \alpha \in {\mathcal{D}}_o\hfill \end{array}$$

(2e)

$$\begin{array}{cc}\hfill & y_{\alpha }\in \{0,1\},\forall \alpha \in {\mathcal{N}}_s\hfill \end{array}$$

(2f)

$$\begin{array}{cc}\hfill & x_{\alpha \kappa }^r\in \{0,1\},\forall \alpha ,\kappa \in {\mathcal{N}}_s\mathrm{with}\alpha {\prec }_r\kappa ,\forall r\in \mathcal{R}\hfill \end{array}$$

(2g)

Constraints (2b) and (2c) indicate that a QCM can only be installed when the variable x is selected, which means that a bus in route r will use $\alpha$ and $\kappa$ stations for swapping batteries. Constraint (2d) is the connectivity constraint with the conditional parameter $b_{\alpha }$. Constraint (2e) indicates that all the depots should also play the role of QCM, and Constraints (2f) and (2g) say that $y_{\alpha }$ and $x_{\alpha \kappa }^r$ are binary variables. The advantage of this model is that we can determine not only the QCM locations but also the detailed battery swapping schedules for each bus. Moreover, this model gives a potential chance for insight into aspects of Quality of Service (QoS) since x variables suggest the detailed routing schedule information for each bus so we can analyze the efficiency of each bus route. On the other hand, a drawback of this model is that if a bus route has more QCMs than its minimally required number, a bus on the route does not necessarily follow the suggested battery swapping schedules (i.e., alternative plans exist, and this model cannot capture that aspect). Moreover, compared with the set-covering formulation, the complexity of this formulation is significantly increased in terms of the number of decision variables and constraints because, with n stations, the total number of x variables is as much as $(n^2-n)/2$, in the worst case. In addition, as we can see in the structure of the formulation, the number of constraints also increases in proportion to the number of variables. This implies that, depending on the number of entire stations of our problem or stations over the certain bus transit network, the computational complexity of the model dramatically increases. Thus, it may be necessary to come up with more efficient modeling or solution approaches. In this regard, we propose another formulation utilizing a column generation algorithm suitable for solving a large-scale problem, as presented in the next section.

2.3.3. Path-Based Formulation

We now present a path-based formulation for this problem. The main difference between the flow-based model and the path-based model is that the decision variable x in the flow-based model indicates the previous and next stations for the battery swap. On the other hand, the path-based model groups these x variables based on each route and defines the set of paths throughout a bus itinerary, where each path corresponds to a feasible battery swapping schedules. In summary, a path is nothing but one of a subset of QCM stations for battery swapping on each route.

Table 3. Additional notations for path-based formulation.

Sets and Parameters
$\mathcal{P}\left(r\right)$	Set of paths for the route $r\in \mathcal{R}$ where a path is a set of consecutive sub-routes where connecting points correspond to QCMs
${\mathcal{N}}_r\left(l\right)$	Set of stations which the path l for the route r visits.
Decision variables
$x_l^r$	1 if the path $l\in \mathcal{P}\left(r\right)$ is selected, and 0 otherwise.

shows additional notations for the path-based formulation.

The path-based model can be formulated as follows:

Model (Path-based model)

$$\begin{array}{cc}\hfill \mathrm{minimize}& \sum _{\alpha \in {\mathcal{N}}_s}{y}_{\alpha }\hfill \end{array}$$

(3a)

$$\begin{array}{cc}\hfill \mathrm{subject}\mathrm{to}& \begin{array}{cc}\hfill \sum _{l\in \mathcal{P}\left(r\right)}{x}_l^r=1,& \forall r\in \mathcal{R}\hfill \end{array}\hfill \end{array}$$

(3b)

$$\begin{array}{cc}\hfill & \begin{array}{cc}\hfill \sum _{l\in \mathcal{P}\left(r\right)\parallel \alpha \in {\mathcal{N}}_r\left(l\right)}{x}_l^r\le y_{\alpha },& \forall \alpha \in {\mathcal{N}}_s,r\in \mathcal{R}\hfill \end{array}\hfill \end{array}$$

(3c)

$$\begin{array}{cc}\hfill & \begin{array}{cc}\hfill x_l^r\in \{0,1\},y_{\alpha }\in \{0,1\},& \forall l\in \mathcal{P}\left(r\right),\alpha \in {\mathcal{N}}_s,r\in \mathcal{R}\hfill \end{array}\hfill \end{array}$$

(3d)

The x variables of the flow-based model are translated into a path, which becomes much simpler than before. Constraint (3b) means only one path should be chosen from among the possible paths for each route, and Constraint (3c) indicates that if a path is selected, then the nodes included in that path must be QCM stations. Finally, all the decision variables are binary variables, as indicated by Constraint (3d). The problem is that, although this formulation looks simple, creating a path set for each route and considering all these paths are not straightforward at all. With n nodes in a bus route, the total number of possible paths can reach up to $n^2$. Thus, we approach this problem based on column generation techniques. Note that a column generation algorithm is useful when dealing with problems featuring large numbers of variables because it avoids the enumeration of all possible variables and instead only evaluates them as needed. We note that column generation algorithms cannot be applied to all cases, but that they are applicable to this problem in two respects. First, LP-relaxation is essential for application of the column generation algorithm, and because this problem treats a kind of network-flow problem, we can use LP-relaxation [25]. Moreover, as described above, this problem has a large number of variables compared to the number of constraints. According to the column generation algorithm, we divide this model into a master problem $\mathcal{MP}$ and sub-problems $\mathcal{SP}\left(r\right)$ for each route $r\in \mathcal{R}$. We then iteratively solve the problem by repeatedly adding the feasible paths from each sub-problem to the master problem using the column generation algorithm.

Model $\mathcal{MP}$ (Master problem of path-based model)

$$\begin{array}{cc}\hfill \mathrm{minimize}& \sum _{\alpha \in {\mathcal{N}}_s}{y}_{\alpha }\hfill \end{array}$$

(4a)

$$\begin{array}{cc}\hfill \mathrm{subject}\mathrm{to}& \begin{array}{cc}\hfill \sum _{l\in \mathcal{P}\left(r\right)}{x}_l^r=1,& \forall r\in \mathcal{R}\hfill \end{array}\hfill \end{array}$$

(4b)

$$\begin{array}{cc}\hfill & \begin{array}{cc}\hfill \sum _{l\in \mathcal{P}\left(r\right)\parallel \alpha \in {\mathcal{N}}_r\left(l\right)}{x}_l^r\le y_{\alpha },& \forall \alpha \in {\mathcal{N}}_s,r\in \mathcal{R}\hfill \end{array}\hfill \end{array}$$

(4c)

$$\begin{array}{cc}\hfill & \begin{array}{cc}\hfill x_l^r\in \{0,1\},y_{\alpha }\in \{0,1\},& \forall l\in \mathcal{P}\left(r\right),\alpha \in {\mathcal{N}}_s,r\in \mathcal{R}\hfill \end{array}\hfill \end{array}$$

(4d)

The master problem $\mathcal{MP}$ is basically the same as the path-based formulation (Section 2.3.3), but starts with a partial set of paths as an initial basis. Let ${\pi }_r$ and ${\mu }_{\alpha ,r}$ be the dual variables for Equations () and (), respectively. To solve the problem with these dual variables, the linear programming relaxation of the master problem is solved. If the reduced cost for x variable, $\left(-{\sum }_{\alpha \in {\mathcal{N}}_r\left(l\right)}{\mu }_{\alpha ,r}-{\pi }_r\right)$, turns out to be negative, then the corresponding column $x_l^r$ can be added to the restricted master problem. To find a candidate x-variable to add, we need to solve the following pricing sub-problem $\mathcal{SP}\left(r\right)$ for a route r:

Model $\mathcal{SP}\left(r\right)$ (Subproblem of path-based model for route r)

$$\begin{array}{cc}\hfill \mathrm{minimize}& \sum _{\alpha \in {\mathcal{N}}_s\left(r\right)}\left(-{\mu }_{\alpha ,r}{y}_{\alpha }^r-{\pi }_r\right)\hfill \end{array}$$

(5a)

$$\begin{array}{cc}\hfill \mathrm{subject}\mathrm{to}& \begin{array}{cc}\hfill x_{\alpha \kappa }^r\le y_{\alpha }^r,& \forall (\alpha ,\kappa )\in \mathcal{E}\left(r\right)\hfill \end{array}\hfill \end{array}$$

(5b)

$$\begin{array}{cc}\hfill & \begin{array}{cc}\hfill x_{\alpha \kappa }^r\le y_{\kappa }^r,& \forall (\alpha ,\kappa )\in \mathcal{E}\left(r\right)\hfill \end{array}\hfill \end{array}$$

(5c)

$$\begin{array}{cc}\hfill & \begin{array}{cc}\hfill \sum _{(\alpha ,\kappa )\in \mathcal{E}\left(r\right)}{x}_{\alpha \kappa }^r-\sum _{(\kappa ,\alpha )\in \mathcal{E}\left(r\right)}{x}_{\kappa \alpha }^r=b_{\alpha },& \forall \alpha \in {\mathcal{N}}_s\left(r\right)\hfill \end{array}\hfill \end{array}$$

(5d)

$$\begin{array}{cc}\hfill & \begin{array}{cc}\hfill x_{\alpha \kappa }^r\in \{0,1\},y_{\alpha }^r\in \{0,1\},& \forall (\alpha ,\kappa )\in \mathcal{E}\left(r\right),\alpha \in {\mathcal{N}}_s\left(r\right)\hfill \end{array}\hfill \end{array}$$

(5e)

In the sub-problem $\mathcal{SP}\left(r\right)$, $b_{\alpha }=1$ if $\alpha \in {\mathcal{D}}_o$, $b_{\alpha }=-1$ if $\alpha \in {\mathcal{D}}_d$, and 0 otherwise. Note that the path generation sub-problem $\mathcal{SP}\left(r\right)$ is a variant of the shortest path problem. Unlike a typical shortest path problem, $\mathcal{SP}\left(r\right)$ minimizes node costs instead of edge costs. It is trying to minimize the sum of the costs incurred at the nodes visited. The problem $\mathcal{SP}\left(r\right)$ can be easily transformed to an edge-cost-minimizing shortest path problem. Since the arc weights in the transformed model are non-negative (the dual variables for Equation (4c), ${\mu }_{\alpha ,r}$, are negative), the sub-problem $\mathcal{SP}\left(r\right)$ can be solved efficiently by Dijkstra’s algorithm.

The objective Function (5a) indicates the reduced cost of the master problem, and thus if the objective function of $\mathcal{SP}\left(r\right)$ is non-negative, it means that we have found a candidate x-variable with a negative reduced cost. Constraints (5b) and (5c) show the activating condition of y, since the master problem $\mathcal{MP}$ is a minimization problem so that a variable with negative reduced costs could further decrease the objective function of $\mathcal{MP}$. When the sub-problem cannot find any solution with a negative objective function value, we can conclude that all the necessary variables have been added to the restricted master problem. The algorithm is then terminated after deriving the optimal solution of the master problem.

3. Case Study on a Smart e-Bus System

In this section, we run numerical experiments with the three proposed mathematical programming models in Section 2 and evaluate them with the actual bus transit network data of the Seoul metropolitan area, South Korea. All the bus transit network data used in this experiment are available at [26]. When it comes to the driving range of the e-Bus, the electric bus under consideration can drive up to 60 km with a fully charged battery, according to [13]. All the experiments were performed using an Intel(R) Core(TM) i7-4770 CPU at 3.40 GHZ with 32 GB memory.

Figure 3 shows the summary statistics and a plot of the entire dataset we use. We use this dataset from Seoul, South Korea, to evaluate the performance of the proposed mathematical programming models. In doing so, we vary the size of the experimental dataset to better understand the tested formulations in terms of computational time and quality of solution as dataset size increases. When it comes to experimental dataset generation, several factors are considered. Since the battery capacity is 60 km per charge, we prioritize including in each dataset the bus routes longer than 60 km, which we refer to as the primary routes. Indeed, the experimental datasets are generated with those primary routes, and the non-primary routes added as necessary. The same suite of generated datasets is then used to evaluate the numerical performance of each proposed mathematical programming approach. We note that the numerical experiment is conducted 10 times with same conditions for each dataset and each mathematical programming approach.

3.1. Experiments with Set-Covering Model

We first present the experimental results from the set-covering formulation and

Table 4. Experimental results of the set-covering model.

# of Routes (# of Stations)	Optimal # of QCM Stations	Avg. CPU Time (sec)	Max Gap between CPU Times (sec)	# of Variables	# of Constraints
5 (441)	12	0.086	0.012	441	595
10 (822)	20	0.301	0.076	822	1185
20 (1611)	37	0.708	0.071	1611	2422
30 (2286)	53	0.968	0.066	2286	3631
40 (2681)	65	1.326	0.411	2681	4710
50 (3058)	73	2.001	0.444	3058	5822
60 (3597)	82	2.493	0.558	3597	7074
70 (3929)	102	2.561	0.329	3929	7880
80 (4235)	121	2.848	0.186	4235	8537
90 (4435)	137	3.034	0.11	4435	9282
100 (4732)	152	3.378	0.121	4732	10,287
200 (7008)	256	5.614	0.233	7008	18,194
300 (8059)	315	7.725	1.17	8059	25,352
400 (8937)	382	9.246	0.377	8937	31,492
500 (10,934)	549	9.87	0.4	10,934	34,908
600 (12,650)	721	9.793	0.459	12,650	37,799
635 (13,191)	782	10.313	1.357	13,191	38,636

and Figure 4 show the summary of the results.

As the graphs in Figure 4 show, we observe that there exists a linear relationship between dataset size and the number of decision variables as well as the number of constraints. We remark that, in the set-covering model, the variable y is the only decision variable, and the number of constraints is almost equal to the size of the dataset. Moreover, for each route r, there are at most $|{\mathcal{N}}_s^r|-1$ number of MOSs. Thus, despite the complexity of the model structure, at least the number of variables and constraints does not increase exponentially, and we can learn that empirically the computational time of the model also increases linearly. This model seems quite easy to use experimentally to solve this problem, at least for our dataset. However, this also shows the limitation of the set-covering model of not giving intuition about where to swap a battery.

Figure 5 shows plots of the experiment results of four test instances. Most of the stations are centralized in the downtown, especially in Figure 5d. This is because the location is decided by the route, not the distance between the QCM stations. Considering this point, if there are too many centralized stations, a penalty could be imposed on the distance between neighborhood stations as an extra constraint. We left this as a further study.

3.2. Experiments with Flow-Based Model

We now discuss the experimental results from the flow-based model. In the flow-based model experiment, we cannot get a solution in case of more than 20 routes due to the computational memory becoming full, as presented in

Table 5. Experimental results of the flow-based model.

# of Routes (# of Stations)	Optimal # of QCM Stations	Avg. CPU Time (sec)	Max Gap between CPU Times (sec)	# of Variables	# of Constraints
5 (441)	12	16.835	0.202	972,846	240,434
10 (822)	21	35.891	1.223	2,205,658	681,564
15 (1230)	28	122.667	1.658	6,757,662	1,816,809
18 (1552)	32	687.125	5.805	10,757,662	4,816,809
20 (1611)	37	2356.156	15.425	34,541,551	12,426,973
30 (2286)	-	-	-	-	-
40 (2681)	-	-	-	-	-
50 (3058)	-	-	-	-	-

.

The computational time increases exponentially as the size of the data set increases (see Figure 6a), as does the number of decision variables and constraints (see Figure 6c,d). However, as stated earlier, the advantage of using this model is that we can obtain the battery swapping schedule for each route with x variables.

Figure 7 shows the same results as with the set-covering model in terms of the optimal QCM locations. However, due to the limitation of the test size, the plots of the result are also restricted to data sizes, 10 (Figure 7a) and 20 (Figure 7b) only. From the result, note that we can confirm the same QCM installations as the set-covering model.

3.3. Experiments with Path-Based Model

We finally present the experimental results from the path-based formulation and

Table 6. Experimental results of the path-based model.

# of Routes (# of Stations)	Optimal # of QCM Stations	Avg. CPU Time (sec)	Max Gap between CPU Times (sec)	# of Variables	# of Constraints	Avg. # of Iterations
5 (441)	12	15.781	0.042	515	202	86
10 (822)	21	60.418	0.084	956	422	215
15 (1230)	28	285.118	1.584	1355	569	348
20 (1611)	37	1296.621	3.584	1950	744	586
30 (2286)	53	2874.516	6.871	3125	968	863
40 (2681)	65	4225.889	10.668	4857	1268	1153
50 (3058)	73	5826.146	15.139	22,618	1605	1868
60 (3597)	82	7361.411	23.584	30,520	2841	2735
70 (3929)	102	8165.156	43.458	37,211	3869	3868
80 (4235)	121	10,041.453	167.165	43,584	5412	5066
90 (4435)	137	14,025.584	304.545	51,251	8169	6166
100 (4732)	152	23,218.975	518.107	58,518	9887	7259
200 (7008)	256	81,540.145	682.618	135,685	34,815	25,015
300 (8059)	315	345,154.587	822.123	209,871	65,036	68,121

and Figure 8 summarize the results.

The computational results on the data set indicate that the proposed approach works to find the optimal solution of every problem instance under consideration. As Figure 8a shows, the computational time tends to increase exponentially, but not as rapidly as the flow-based model, as also shown by comparing Figure 6a and Figure 8a. The path-based model overcomes the limitation of the result of the flow-based model. Note that the flow-based model cannot derive the solution when the dataset becomes too large. Thus, the path-based model more effectively manages the computer memory compared than flow-based one. This is due to the column generation algorithm’s characteristic of solving the problem iteratively, and not using all the columns.

Figure 9 shows plots of results from the path-based model experiment. We note that the outcome is consistent with previous models.

3.4. Model Comparison

In this section, we compare the results discussed in Section 3.1, Section 3.2 and Section 3.3 and summarize pros and cons of each model.

Table 7. Comparison of the computational results of the three models.

	Set-Covering Model		Flow-Based Model		Path-Based Model
# of Routes (# of Stations)	CPU Time (sec)	Optimal # of QCM Stations	CPU Time (sec)	Optimal # of QCM Stations	CPU Time (sec)	Optimal # of QCM Stations
5 (441)	0.086	12	16.835	12	15.781	12
10 (822)	0.301	21	35.891	21	60.418	21
15 (1230)	0.514	28	122.667	28	285.118	28
20 (1611)	0.708	37	2356.156	37	1296.621	37
30 (2286)	0.968	53	-	-	2874.516	53
40 (2681)	1.326	65	-	-	4225.889	65
50 (3058)	2.001	73	-	-	5826.146	73
60 (3597)	2.493	82	-	-	7361.411	82
70 (3929)	2.561	102	-	-	8165.156	102
80 (4235)	2.848	121	-	-	10,041.453	121
90 (4435)	3.034	137	-	-	14,025.584	137
100 (4732)	3.378	152	-	-	23,218.975	152
200 (7008)	5.614	256	-	-	81,540.145	256
300 (8059)	7.725	315	-	-	345,154.587	315
400 (8937)	9.246	382	-	-	-	-
500 (10,934)	9.87	549	-	-	-	-
600 (12,650)	9.793	721	-	-	-	-
635 (13,191)	10.313	782	-	-	-	-

presents a comparison of the three proposed models. The column ‘dataset’ indicates the used subsets in the experiment. For each model, the first column indicates the computational time, and the next column indicates the optimal number of QCM installations for each problem instance. The result confirms that every model we propose yields the same optimal solution. The set-covering model clearly has a strong point and weak point. While it offers limited information, only the location of QCM installations, it suggests the result superiorly fast compared to other models. Both the flow-based model and path-based model are useful in that they can additionally offer information about where to swap batteries. In terms of computation time, they fall short of the set-covering model. However, the path-based model shows better performance than the flow-based one. Figure 10 incorporates and compares the previous experiments’ computational time results graphically.

3.5. Quality of Service Analysis for Electric Buses

In this section, we further discuss how QoS, which was briefly mentioned in Section 2.3.1, can be incorporated in the proposed models. There are several aspects needing consideration when making strategic decisions on QCM locations in public transit networks. One example might be how many e-Bus routes should be associated with each QCM station. While the proposed QCM only requires a short time for each battery swap, this service time can reduce the potential for serving multiple buses simultaneously at one station. Thus, properly dispersing these flocking vehicles across a battery swapping queue could help to provide a better and more seamless service over the operation of the entire bus transit system. Figure 11 shows the imbalance of the service rate measured by the number of bus routes scheduled for battery swapping per one QCM station when the experimental dataset with 100 routes is used.

Figure 11 presents QCM station distribution in terms of the number of bus routes they service for battery swapping. For example, while one QCM station serves 24 bus routes, 60 QCM stations serve only one. Considering this, limiting the maximum number of bus routes served by a QCM station, would allow QCM service rates to be appropriately balanced.

From the computational point of view, the set-covering model has outperformed the flow-based and path-based models. This section will determine how the battery swapping schedule of each bus route can be utilized in the QoS analysis and demonstrate how the flow-based and path-based models can consider such QoS aspects while the set-covering model cannot. Note that the results of the set-covering model show that while we can derive the number of bus routes including each QCM station, we cannot directly incorporate constraints to limit the number of bus routes that each QCM station serves. On the other hand, the flow-based and path-based models contain information about which QCM station each bus route should stop at for battery swapping within the x variables. This is because these models support constraints explicitly limiting the number of bus routes passing through each QCM station and can derive the exact number of routes each QCM station should serve for battery swapping. In this regard, we limit the number of bus routes stopping at each QCM station in order to disperse battery swapping servicing and hence reduce the chance of having to wait for battery swapping at any station. We remark that in the path-based model this constraint can be easily added through the x variables, and we name the new model the extended path-based model. We can also add similar constraints to the flow-based model. The additional notation (

Table 8. Additional notation for the extended path-based formulation.

Additional Parameter
$\gamma$	Maximally allowable number of bus routes stopping at a QCM station for battery swapping

) and the formulation of the extended path-based formulation are given below:

Model ${\mathcal{MP}}_e$ (Master problem of the extended path-based model)

$$\begin{array}{cc}\hfill \mathrm{minimize}& \left(4a\right)\hfill \\ \hfill \mathrm{subject}\mathrm{to}& \left(4b\right),\left(4c\right),\left(4d\right)\hfill \\ \hfill & \begin{array}{cc}\hfill \sum _{r\in \mathcal{R}}\sum _{l\in \mathcal{P}\left(r\right)\parallel \alpha \in {\mathcal{N}}_r\left(l\right)}{x}_l^r\le \gamma & \forall \alpha \in {\mathcal{N}}_s\hfill \end{array}\hfill \end{array}$$

(6a)

Constraint (6a) limits the number of bus routes stopping at each QCM station $\alpha \in {\mathcal{N}}_s$. By simply adding the constraint, we can indirectly control the battery swapping demand at each QCM station and disperse the traffic. However, we would like to note that the additional constraint (6a) cannot be directly incorporated at the initial stage of the column generation procedure of the path-based model. If the value of $\gamma$ in the constraint is not sufficiently large, the path-based model can become infeasible at the initial stage of the column generation procedure because of an insufficient number of columns available. Thus, in order to incorporate the constraint and implement the column generation procedure, we should either add constraint (6a) at a later stage after a number of iterations or reduce the value of $\gamma$ gradually over the iterations. In the numerical experiment, we add the additional constraints at the later stage of the column generation procedure. To evaluate the effects of adding the QoS constraints into the path-based model, we compare the results with the original path-based model.

Table 9. Computational result with(out) Quality of Service (QoS) constraints in the path-based model.

	Original Path-Covering Model				Extended Path-Based Model
# of Routes (# of Stations)	# of QCM Stations	Maximum Flock ($\gamma$)	Variance of Flocking	CPU Time (sec)	# of QCM Stations	Maximum Flock ($\gamma$)	Variance of Flocking	CPU Time (sec)
5 (441)	12	4	1.401	15.781	14	2	0.863	16.115
10 (822)	21	7	1.987	60.418	22	4	1.478	69.054
15 (1230)	28	9	2.081	285.118	29	5	1.975	308.487
20 (1611)	37	9	1.993	1296.621	39	5	1.072	1583.142
30 (2286)	53	9	1.974	2874.516	55	5	1.882	3593.145
40 (2681)	65	9	2.013	4225.889	67	5	1.342	5451.396
50 (3058)	73	9	1.955	5826.146	76	5	1.277	9828.708
60 (3597)	82	11	2.154	7361.411	85	7	1.270	10,453.203
70 (3929)	102	15	3.377	8165.156	104	8	1.483	13,717.462
80 (4235)	121	21	3.670	10,041.453	125	10	2.495	12,903.267
90 (4435)	137	24	3.823	14,025.584	141	10	2.478	19,032.717
100 (4732)	152	25	4.284	23,218.975	158	12	2.876	34,317.645

shows the numerical test results.

Since dataset size limits the configurability of the $\gamma$ value, the $\gamma$ value is adaptively set according to it. After adding the QoS constraints, we can observe the intuitive result that the number of the QoS installations is more than with the original path-based model. The ‘maximum flock’ column indicates the maximum number of buses coming to a QCM station for battery swapping, and the ’variance of flocking’ column indicates the distribution of the number of buses scheduled to swap their batteries at each QCM station. Table 9 indicates that, as the number of QCM installations increases and the number of bus routes stopping at a QCM station for battery swapping is restricted, the overall flocking variance decreases.

Figure 12 compares the results shown in Figure 11 with the corresponding results from the extended model. As Figure 12 shows, no QCM station serves more than $\gamma$ bus routes. This restriction allows the flocking phenomenon to be resolved without significantly increasing the optimal number of QCM installations, implying that severe flocking would occur at only a few stations. We can conclude that the extended model helps to effectively redistribute the demand for battery swapping away from overused stations. We conduct further experiments with the extended path-based model to examine how sensitive the results are to $\gamma$.

Table 10. Computational result as the $\gamma$ value changes.

	Extended Path-Based Model Experimented with 60 Routes
$\gamma$	# of QCM Stations	Maximum Flock	Variance of Flocking	CPU Time (sec)
6	infeasible	-	-	-
7	85	7	1.270	10,453.204
8	84	8	1.621	9358.721
9	84	9	1.819	8715.780
10	82	10	2.084	7521.184
11 (no restict)	82	11	2.154	7361.411

shows the variation in the optimal number of QCM stations and the flocking variance according to $\gamma$.

Table 10 shows the trade-off between the optimal number of QCM stations and flocking variance as the value of $\gamma$ varies. Flocking can be mitigated by changing the $\gamma$ value without too much degradation in the optimal number of QCM installations. We also note that it is possible for the extended model to become infeasible if $\gamma$ becomes too small. In summary, we demonstrate that, unlike the set-covering model, the flow-based or path-based model can address various considerations, such as QoS, and that, by controlling the number of bus routes stopping at a station, the additional QoS constraints can help to reduce the chances of high demand for battery swapping at individual QCM stations.

4. Conclusions and Future Research

In this paper, we studied the effective operation of electric buses, assuming the battery swapping system, in which batteries can be swapped in bus stations by using special equipment called quick charger machines. The purpose of this study is to minimize the total number of QCM installations in existing bus stations over the urban bus transit network while providing the seamless operation of a public bus service in a metropolitan area. To address this problem, we suggest three different mathematical models based on mixed-integer programming. The first model, the set-covering-based formulation, has fast computational times since it is formulated as a low complexity model. The deficiency of this model is that it does not suggest a detailed schedule of where to swap batteries for each bus; it only provides the locations of the QCM stations. On the other hand, the flow-based formulation and path-based formulation do provide this important additional information, unlike the set-covering model. However, these models are highly computationally complex, as shown by the experiment results with actual data. The column generation algorithm used in the path-based model makes this model better balanced in terms of computational time and completeness of information than the set-covering model or flow-based model. In Section 3, we check the performance of each model and their validity for this problem with the actual bus transit network data from the Seoul metropolitan area. Above all, in Section 3.5, as a QoS analysis, we introduce additional constraints to the path-based model so that the demand for battery servicing at QCM stations is distributed more evenly over the entire bus transit network and demonstrate that the approach is effective. Most of all, we show the improved flexibility and scalability of the flow-based and path-based models compared to the set-covering model. This paper contributes significantly to the understanding of how to introduce an electric vehicle to an urban area. The varied models can solve this problem and give insight into further studies.

For future work, we can generalize the assumptions used in our problem. First, we assume that all buses depart from the depot at full battery capacity. However, if each bus rotates its route several times, then the initial or final condition of the battery can be different every time. By taking this into account, the improved model can reflect the initial battery level. Moreover, considering the cost of installing each QCM on an individual basis can be meaningful since here we assume the cost of installation is the same for all stations, and, therefore, only focus on minimizing the total number of QCMs. For another problem approach, we can first solve the set-covering model and then solve another scheduling model. The set-covering model only suggests the optimal location of QCM stations but not the specific scheduling, and the result of the flow-based model and path-based model are also restricted by their computational complexity. Thus, proposing additional scheduling problems that utilize the QCM location results of the set-covering model could be another methodological approach, although one that would not guarantee an optimal solution. It is apparent from numerical experiments with real-world data that a heuristic algorithm may be necessary to solve these problems efficiently. Finally, once the strategic decision to install QCMs has been made, operational decisions, such as those concerning battery pack charging/discharging based on usage and the availability of battery packs eligible for battery swapping, need to be addressed.