Transportation Research Part E 58 (2013) 76–87

Contents lists available at ScienceDirect

Transportation Research Part E

journal homepage: www.elsevier.com/locate/tre

Locating multiple types of recharging stations

for battery-powered electric vehicle transport
Ying-Wei Wang a,⇑, Chuah-Chih Lin b
a
Department of Marketing and Logistics Management, National Penghu University of Science and Technology, 300 Liu-Ho Rd., Magong, Penghu, Taiwan, ROC
b
Department of Transportation and Communication Management Science, National Cheng Kung University, 1 University Road, Tainan 701, Taiwan, ROC

a r t i c l e i n f o a b s t r a c t

Article history: This study used the concepts of set- and maximum-coverage to formulate capacitated mul-
Received 30 August 2012 tiple-recharging-station-location models, using a mixed integer programming method,
Received in revised form 3 May 2013 based on a vehicle-refueling logic. The results of the case study demonstrate that the use
Accepted 29 June 2013
of mixed stations can achieve the optimal deployment for the planning area, with results
that are better than those achieved with a single type of recharging stations. While in some
paths the use of slow-recharging stations means that tours are not feasible, the deployment
Keywords:
of mixed stations can provide an economical approach which ensures the completion of
Recharging stations
Electric vehicle
overall tours on each path.
Set coverage Ó 2013 Elsevier Ltd. All rights reserved.
Maximum coverage
Mixed integer programming
Location

1. Introduction

As a result of concerns over climate change, energy security, urban air pollution and the continued growth in demand for
transportation services, the adoption of alternative fuel vehicles is becoming ever more important (Melaina and Bremson,
2008; Kley et al., 2011). Electric vehicles (EV) powered by batteries can be charged by regular power outlets and offer lower
operating costs than combustion engine cars. They are also efficient, emit no pollution, and are almost noiseless (Eggers and
Eggers, 2011), and thus are expected to become more popular over the next decade (San Román et al., 2011), a trend that
seems to be confirmed by the fact that several manufacturers are currently, or soon will be, offering their own EVs for cus-
tomers, such as BMW, Mercedes, Honda and Toyota (Khan and Kockelman, 2012). However, the successful penetration of EVs
still depends on the support of government policies, such as tax exemptions, and an environment where consumers do not
need to worry over the range of such vehicles (Schroeder and Traber, 2012). Therefore, the establishment of a convenient
recharging system is one of the most important factors to encourage the widespread use of EVs. However, due to the high
capital cost involved in doing this, developing a recharging station location model to achieve this economically is a pressing
concern for both researchers and government bodies.
Advances in technology mean that battery recharging times have now been cut to within 20–30 min using Direct-Current
fast charging (Schroeder and Traber, 2012; Svoboda, 2009). However, in practice, due to considerations of battery life and the
limited power supply at each site, slow recharging stations are still the predominant ones, as seen with the Park & Charge
system used in Europe (Park and Charge, 2012). However, in the near future, we can expect that EV recharging systems will
operate with multiple types of recharging stations, including both slow- and fast-recharging ones, such as currently seen on
the West Coast Electric Highway in America (West Cost Electric Highway, 2012). In these systems, multiple types of recharg-

⇑ Corresponding author. Tel.: +886 6 9264115x1101; fax: +886 6 9260373.

E-mail address: ywwang@gms.npu.edu.tw (Y.-W. Wang).

1366-5545/$ - see front matter Ó 2013 Elsevier Ltd. All rights reserved.
http://dx.doi.org/10.1016/j.tre.2013.07.003
 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87 77

ing stations will be used to meet the varied demands or preferences of EV road users, while staying within the limits of the
power supply in each area. Therefore, there is an urgent need to develop a location model for mixed recharging station
deployment.
In previous research, various location models were proposed to optimally site refueling facilities. The proposed models
can be classified as node-based, arc-based, and flow-based, based on their assumptions of refueling demand type (Upchurch
and Kuby, 2010).
In this study, we mainly review the literature related to flow-based models of refueling facility location, since the refu-
eling demand for vehicles is generally in the form of traffic flows that pass by the refueling facilities (Hodgson, 1990).
To consider many types of service demand that can be thought of as traffic flows, such as that seen for convenience stores,
automated teller machines (ATM), and gasoline stations, Hodgson (1990) proposed a flow-capturing location model (FCLM)
based on the concept of maximum coverage, which locates p facilities to maximize the capture of the passing flows. This is
different from conventional facility location theory (Daskin, 1995), which is based on the assumption of fixed-node demand,
such as from homes to service stations. Two years after Hodgson, Berman et al. (1992) proposed a flow interception facility
location model, which is based on the same flow-demand that is used in the FCLM.
Hodgson (1990) provided a basic theoretical framework for dealing with the problem of locating alternative fuel refueling
stations. However, this approach depends on the assumption that if one facility is sited on a node of a path, then all the re-
lated traffic flows will be captured, and this cannot be applied to alternative fuel vehicles, since these have a limited range
and need a multi-stop refueling system to extend their driving distance and carry out long-distance journeys.
In order to achieve the multi-stop refueling needed for long-distance travel, Kuby and Lim (2005) proposed a flow refu-
eling location model (FRLM) on the basis of FCLM. Similar to the FCLM, the objective of FRLM is also to maximize the capture
of the traffic flows on each path if a combination of stations sited on the paths can be successfully used to refuel vehicles so
that they can complete their trips. This model needs to be solved in two stages. The first stage is to find feasible combinations
of candidate locations or stations to refuel the flows on each path, and the second stage is when these combinations are used
as inputs to the model to determine the station locations (Kuby and Lim, 2005). Due to the time-consuming process of gen-
erating combinations in first stage, Lim and Kuby (2010) provided some heuristic algorithms to solve larger scale problems,
including greedy substitution and genetic algorithms.
Later, Capar and Kuby (2012) developed a new approach to solve the flow refueling location problem in one stage. Three
locating logics were used to check whether a path could be refueled by the sited refueling stations. The first one is if there is
no station built at the origin then there should be at least one station built within half the vehicle range to the origin node, so
that it can be reachable by half a tank of fuel or half a battery charge. The second one is if there is a station built at a location,
then the next built facility should be within the vehicle range, otherwise the vehicle cannot reach to the next station. The
third one is if the vehicle range is greater than or equal to two times the path length, then a single station at any point
can refuel the entire path. However, these logics are available only when the vehicle has regained its full fuel or charge level
(for maximum range) after each period of refueling/recharging at the stations, for example via fuel-tank or battery exchange,
which makes the newer approach difficult to apply with regard to multiple types of stations with different refueling or
recharging efficiencies. In addition, this approach cannot solve the capacitated location problem. Basically, such models
do not consider the factors of refueling or recharging efficiency and time, and are limited to the location of a single type
of station for performing the battery or fuel-tank exchange (or very fast refueling) to refill the vehicles.
Different from the maximum-coverage type models, Wang and Lin (2009) proposed a flow-based set covering model for
economically siting fast-refueling stations, such as battery exchange or hydrogen refilling stations. The model was formu-
lated based on vehicle refueling logics which can ensure the alternative fuel vehicle has sufficient fuel to move between
the nodes, and a feasible path can then be achieved. The model can also be solved in one stage, i.e. it does not need to pre-
determine the feasible combination of stations, like the original FRLM does. In addition, this approach does not need the fuel
or charge level after each refueling or recharging to be full, and thus has more flexibility with regard to different situations.
Wang and Wang (2010) extended Wang and Lin’s model and proposed a bi-objective one by combining the flow-based set
covering model and classic set covering model to simultaneously consider intercity (path flow demands) and intra-city travel
(the nodal demands). Later, the flow-based set covering model was extended to consider battery recharging efficiency and
time to locate sufficient slow-recharging stations for electric scooters traveling in a destination area (Wang, 2011). However,
these models still adopt a set coverage approach for locating a single type of refueling stations.
This study extends the slow-recharging station location model (Wang, 2011) based on the flow-based set covering model
(Wang and Lin, 2009) by considering facility budget constraints, multiple types of recharging stations, and vehicle routing
behavior, and then proposes more generalized models with the characteristics of maximum-coverage and set-coverage
to locate multiple types of refueling stations for the (maximal) coverage of battery (or non-battery) powered EV journeys
on each path. At each site along paths, multiple types of charging stations, for example, including slow-recharging,
fast-recharging, and battery exchange stations, would be candidates to locate based on consideration of the station locating
cost, recharging efficiency and time (i.e. the specific extended range), and vehicle routing behavior. In addition, the available
refueling time (also the length of stay) at each site can be divided into three categories, including the sight-seeing or
recreational time at attractions, the battery switching time at convenience stores, and the normal refueling time at common
sites (similar to the refueling time at gasoline stations). An EV can be refueled by using the refueling time and refueling rate
at a specific type of station to increase its range for the movement between sites, and different vehicle ranges are also
considered in the models.
78 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87

Each path will consist of a sequence of visiting points to emphasize that the vehicles depart from the origin point and visit
specific points, such as tourist attractions, and then return to designated points, but not necessarily the original one. In this
way, the set of routes can include the shortest paths of the single origin–destination round trips, but need not be limited to
them, and can also include tours of various kinds.
This study next introduces the formulation of the facility location problem for the placement of multiple types of recharg-
ing-stations at various nodes. Section 3 of this paper then applies this model to a case study of Penghu Island in Taiwan, and
the solutions produced by the new model are compared with that produced for siting a single type of recharging station. The
final section provides a discussion of the results and the conclusions of this work.

2. Model formulation

Wang (2011) proposed the slow-recharging station location model based on the flow-based set covering model proposed
by Wang and Lin (2009) to determine the station locations for serving tourism transport using battery-powered electric
scooters (ES). The model already considers the parameters of battery recharging efficiency and time. The specific recharging
efficiency (from the single type of recharging station) and time were used to determine the replenished energy and the num-
ber of station locations. To clarify the relationship between the fuel consumption or refueling and riding distance, an ES field-
test was undertaken (Yu and Lu, 2013). The experimental data showed that the relationship between residual charge and
riding range is almost linear, and thus the charge consumed per unit riding distance is nearly constant. The experimental
results also showed that after riding 5 km the original state of charge can be recovered by 10 min recharging in the situations
of 40%, 50%, and 60% residual charge. Similarly, after riding 15 km it can be recovered by 30 min recharging. Therefore, the
extended riding distance per minute charged is almost constant, at around 0.5 km, and so a linear recharging rate over time
is assumed. To locate multiple types of recharging stations, multiple recharging rates should also be considered in the model.
In addition, some planning situations exist where it is impossible to satisfy the entire refueling demand, due to resource
or budget constraints, and thereby the maximum coverage models will probably be a more appropriate choice for station
location plans (Wang, 2011). Wang’s set-coverage model is based on the assumption that there is sufficient budget to cover
the overall flow demand on paths, and it is necessary to further consider budget constraints when developing a new max-
imum-coverage one. Moreover, almost all the proposed models assume that the traveling path is a round trip on a single
path (Berman et al., 1992; Capar and Kuby, 2012; Hodgson, 1990; Kuby and Lim, 2005; Lim and Kuby, 2010; Wang and
Lin, 2009; Wang and Wang, 2010). That is, a node or point will be revisited again in the return trip. However, in practice
a node or point may not necessarily be revisited again in a journey, such as those that occur in tourism and delivery travel,
and this behavior should be considered in the model. To solve these problems, new location models are thus proposed based
on the relaxation of certain assumptions, including multiple recharging stations (i.e. multiple recharging rates), budget con-
straints, and the consideration of practical vehicle routing behavior. The key notations used in the model are as follows.

Indexes
p Paths
i, j Nodes or locations
k Type of recharging stations

Sets
P Set of all paths
N Set of all nodes (potential locations)
K Set of all types of recharging stations

Parameters
cki Cost of locating a type k recharging station at node i
dij Distance (km) between node i and node j
bk Recharging rate of type k station; the increased driving distance per min recharge (km/min)
c Battery’s maximal state of charge, which is equivalent to the EV range (km) using the full charge (energy)
uki The locating capacity at node i (the maximum number of type k stations that can be located at this node)
wp EV flows on path p
tpi Length of stay (also possible recharge time (min)) at node i on path p
‘ Budget for siting recharging stations
sk Vehicle sharing of a type k recharging station

Decision variables
Fp If the path p is covered (EV flows on a path can be served by the sited stations), Fp = 1, otherwise Fp = 0
X ki If there are type k stations located at node i, X ki P 0, otherwise X ki ¼ 0
Y pik If an EV is recharged using a type k station at node i on path p, Y pik ¼ 1, otherwise, Y pik ¼ 0
Bpi The available range (km) using the remaining charge (energy) in the battery at node i on path p
Rpi The increased range (km) using the energy being recharged in the battery at node i on path p
 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87 79

With these notations, the problem of siting multiple types of recharging stations can be formulated as follows:
X p
Maximize F wp ð1Þ
p2P

Subject to
Bpj ¼ ðBpi þ Rpi Þ  F p dij 8i; j 2 N; 8p 2 P; ð2Þ
Rpi 6c  Bp 8 i2 N; 8p 2 P; ð3Þ
X ip p k
Rpi 6 ðY ik t i b Þ 8i 2 N; 8p 2 P; ð4Þ
k2K

Rpi 6 F c 8i 2 N; 8p 2 P;
p
ð5Þ
X
Y pik 6 1 8i 2 N; 8p 2 P; ð6Þ
k2K
X p
sk X ki 6 ðY ik wp Þ 8k 2 K; 8i 2 N; ð7Þ
p2P

X ki 6 uki 8k 2 K; 8i 2 N; ð8Þ
XX
cki X ki 6 ‘ ð9Þ
k2K i2N

F p ; Y pik 2 f0; 1g 8k 2 K; 8i 2 N; 8p 2 P; ð10Þ

X ki ; Bpi ; Rpi P 0 8k 2 K; 8i 2 N; 8p 2 P; ð11Þ
The objective function (1) is to maximize the coverage of EV flows on paths by the siting of multiple types of stations.
Constraint (2), derived from the vehicle refueling logic (b) (Wang and Lin, 2009), states that when an EV travels from node
i to node j on a path (if Fp = 1), the available range using the remaining energy at node j is equal to the available range using
the remaining energy at node i, plus the increased range using the energy via the recharge (if any) at node i, minus the trav-
eling distance (the energy consumed) between them. In contrast, if Fp = 0, EV did not move from node i to node j on a path.
That is, the path will not be covered. Fp is the critical variable to determine whether or not a path is covered, and the formula
is derived from the previous one, Bpj ¼ ðBpi þ Rpi Þ  dij (Wang and Lin, 2009). Constraint (3), derived from the vehicle refueling
logic (c) (Wang and Lin, 2009), represents the increased range using the energy replenished at a node, which must be less
than or equal to the consumed energy (i.e. the range with full battery energy, minus the available range using the remaining
energy at a node). Constraint (4) means that the increased range using the actual energy recharged at a node on a path is less
than or equal to the increased range using the whole replenished energy at a specific recharging rate during the length of the
visit. For example, if an EV (with a range of 40 km) with enough remaining energy to travel 10 km is recharged for 30 min at a
recharging rate of 2 (km/min) at a station, its increased range is only 30 km before leaving. In this case, constraint (3) will
force the replenished energy (Rpi ) to be less than or equal to 30 km (40–10 km). Therefore, the practical refueling time and
energy replenished are 15 min and 30 km instead of 30 min and 60 km, respectively. Constraint (5) states that if a path can-
not be covered (if Fp = 0), the increased range at each node on the path must be zero. Since Fp = 0, the right hand side of con-
straint (5) will be zero, and thus force Rpi to be zero. If Fp = 1, the increased range is less than or equal to the EV range (c).
Constraint (6) indicates that an EV on a path can only use one type of station to refuel at a node. Constraint (7) states that
the number of each type of station sited at node i is equal to the number of EV being recharged using that type station at the
node. The sharing of a type k station can be considered via the sk parameter. Constraint (8) means that the number of each
type of recharging station located at a site must less than or equal to the locating capacity (i.e. maximum number of type k
stations being sited) for each type of station. The limitations of local power and land use can be considered via the parameter
of uki . Constraint (9) is the resources or budget constraints used to limit the number of all types of recharging stations being
sited. Constraint (10) indicates that Fp and Y pik are 0 or 1 integers. Constraint (11) requires that the variables of X ki , Bpi , and Rpi
are not less than zero.
In the present model, constraints (2) to (4) ensure that if Fp = 1, an EV can move between nodes with sufficient energy
from the original point to the destination. The model can thus be applied to any type of traveling path, not only to the short-
est path of specific original-destination round trips assumed in previous models, such as FRLM. In addition, since the model
considers the battery recharging rate and time, it can simulate the battery’s state of charge (energy) at each site to further
determine the locations of multiple types of stations. Moreover, when the recharging rate is high enough, such as 10 km/min,
the battery recharging time is significantly shortened, and can be neglected (t ? 0). In this situation, the battery recharging
P
behavior is quite similar to the battery-exchange or DC fast recharging one. Constraint (4) can be reduced to Rpi 6 ðY pik bk Þ
k
(where b is the range of EV instead of the rate of recharging), as used in Wang and Lin’s model (2009). In fact, no matter
whether battery recharging (slow and fast) or exchange is used, the refilling time is still a critical factor in the practical
use of EVs. Including the recharging time in the model formulation is also a simple way to represent the characteristics
of battery replenishment for different types of recharging station, such as battery recharging and exchange ones. Therefore,
the model can be used to locate multiple types of recharging stations. In addition, the battery’s state of charge (energy) at the
original point can be set to any positive integer (via Bp0 ) which is less than or equal to the range of the EV. This means that the
planner can determine the parameters based on the actual situations of EV energy at each starting point.
80 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87

In facility location planning, there may be sufficient budget to meet the entire demand on all paths. Therefore, how to
economically determine the number and location of multiple refueling stations to serve the flow demands on each path
is the problem addressed in this work. The formulas used to achieve this are as follows.
XX
Minimize cki X ki ð12Þ
i2N k2K

Bpj ¼ ðBpi þ Rpi Þ  dij 8i; j 2 N; 8p 2 P; ð13Þ

Constraints (3–4), (6–7), (10) and (11).

The objective function (12) is to minimize the total cost of locating multiple recharging stations. Since the total path de-
mand will be covered, the Fp will be equal to one. Formula (2) can be reduced to formula (13). The other constraints are as
described above.

3. Case study

Since the new model is extended from the slow-recharging station location model (Wang, 2011), the case of Penghu Is-
land’s recharging station planning is used again to test it and contrast the solutions thus derived with those from the pre-
vious work.

3.1. Data acquisition

Penghu Island, located off the coast of Taiwan, has abundant natural resources, such as a good windfield, and was selected
as an example of a low-carbon island by the Taiwanese government in its low-carbon island plan, which began in 2010. Due
to the significant emissions from the transportation sector, green transport is a critical part of this plan. At present, there are
about 1600 ES on the island, some of which are used for vehicle rental, and thus the rental firms need to deploy sufficient
battery exchange or recharging stations on the popular routes to enable the ES to complete their journeys. In addition, the
rental firms have undertaken strategic alliances with local convenience stores (7-Elevens) to site the battery recharging and
exchange stations.
Fig. 1 shows a network representation of the popular scenic touring routes on Penghu Island. This network extends the
original one described in Wang (2007, 2008) to include the eastern and southern central traveling routes. In the network,
there are three types of possible locations or nodes, including the attractions (nodes D1, D2 . . . D12) marked with triangles,
intersections (nodes A, B, C, D and E) marked with circles, and convenience stores (nodes S1, S2 . . . S8) marked with rectan-
gles. Basically, at the attractions only slow-recharging stations (SRS) can be sited, while the intersections are for the fast
recharging ones (FRS). The convenience stores can have battery exchange stations (BES), SRS, and FRS. The distribution of
recreational trips along the popular routes is shown in Table 1, with 12 popular paths. The lengths of the paths are all over
the range of the ES (approximately 40 km when fully charged), and thus the vehicles need to be recharged to complete these
journeys. The maximal flows per hour for each path are between two to four electric scooters, according to one survey in
Wang et al. (2002). Also from the same survey, tourists’ average stays (and also possible recharging times) at Citou (D1),

Fig. 1. Candidate sites. (a) Locations on the map, and (b) a network representation.
 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87 81

Table 1
Trip distributions along popular routes.

No. Type of routes Distance Maximum

(km) flow
(scooters/h)
1 Magong ? Citou ? A ? Tongling ? B ? Chuwan ? C ? Siaomen ? D ? Erkan ? E ? Wai- 78.8 3
An ? S8 ? S7 ? S6 ? Magong
2 Magong ? Citou ? A ? Tongling ? B ? Chuwan ? C ? Siaomen ? D ? E ? Erkan ? S8 ? S7 ? S6 ? Magong 66.8 3
3 Magong ? Citou ? A ? Tongling ? B ? C ? Chuwan ? S8 ? S7 ? S6 ? Magong 59.6 3
4 Magong ? A ? Tongling ? B ? C ? Siaomen ? D ? E ? Erkan ? S8 ? S7 ? S6 ? Magong 66.4 3
5 Magong ? A ? B ? Chuwan ? C ? Siaomen ? D ? E ? Wai-An ? S8 ? S7 ? S6 ? Magong 78.2 3
6 Magong ? A ? B ? C ? Siaomen ? D ? E ? Wai-An ? S8 ? S7 ? S6 ? Magong 78 4
7 Magong ? Citou ? A ? B ? C ? D ? Siaomen ? S8 ? S7 ? S6 ? Magong 63.2 2
8 Magong ? A ? Tongling ? B ? C ? Chuwan ? S8 ? S7 ? S6 ? Magong 59.4 2
9 Magong ? A ? Citou ? B ? C ? D ? E ? Wai-An ? S8 ? S7 ? S6 ? Magong 76.2 2
10 Magong ? Citou ? A ? Tongling ? B ? C ? D ? E ? Wai-An ? S8 ? S7 ? S6 ? Magong 76.4 2
11 Magong ? S6 ? S5 ? Beiliao ? Guoye ? Linto ? S4 ? Fongguei ? S3 ? S2 ? S1 ? Magong 54.9 2
12 Magong ? Shanshuei ? Shihli ? Fongguei ? S3 ? S2 ? S1 ? S4 ? Lintou ? Guoye ? Beiliao ? S5 ? S6 ? Magong 56.9 2

Tongliang (D2), Chuwan (D3), Siaomen (D4), Erkan (D5), Wai-an (D6), Shanshuei (D7), Shihli (D8), Fongguei (D9), Lintou
(D10), Guoye (D11), and Beiliao (D12) are 56, 19, 22, 28, 33, 30, 30, 25, 20, 32, 28, and 28 min, respectively. The average times
spent at the nodes of the intersection points and convenience stores are around 20 and 10 min, respectively.
In addition, the cost of each station location mainly depends on the cost of land use, charging equipment, and battery
backup and delivery (for exchange stations). In general, the cost of a slow-recharging station is far less than that of a
fast-recharging one, while the cost of battery exchange station is linearly related to the number of the batteries needed
to meet demand. However, the actual cost of each type of recharging station still needs more exact calculations. In this study,
suppose that the locating cost of slow-recharging, fast-recharging, and battery exchange stations are NT$4000, 50,000, and
20,000, respectively. In addition, the estimation of the recharging rate for each type of station is based on the recharging time
of the battery, from empty to full charge. The rates (km/min) for slow-recharging, fast-recharging, and battery exchange sta-
tions are thus 0.133, 2, and 4, respectively. These data are used as the inputs for the model.
Given that the location model was established using a mixed integer program, LINGO’s BRANCH and BOUND method
(Thornburg and Hummel, 2003) is used to obtain the solutions, running on a computer with Windows XP 32-Bit OS, Intel
(R) Core (TM) 2 CPU at 3.4 GHz with 3 GB of RAM.

3.2. Solutions for the set-coverage based model

On the assumption that the budget was sufficient to meet the entire demand on the paths, the solutions listed in Table 2
were obtained using the following parameters: the range of the ES (40 km), the battery’s state of charge at the original point
(fully charged: 40 km), recharging rates for the slow-recharging, fast-recharging, and battery exchange stations (0.133, 2, 4),
vehicle sharing of a type k station is set at 1, the capacity of locating each type of station at each site (5, 6, 7, 8, 9, and 10), the
locating cost for slow-recharging, fast-recharging, and battery exchange stations (as mentioned above), and the length of
stay at the sites (as mentioned above)). The locations of multiple types of stations, in the cases of the ranges of 40 and
50 km together with capacities of 5 and 10, are shown in Fig. 2.
In Table 2, the optimal station location plans have the multiple recharging stations sited to cover the overall path refu-
eling demand with the minimum cost, and the stations sited at the locations of convenience stores currently exist, for exam-
ple, in the case of a capacity of 5, with 15 stations sited at location S8, including 5 slow-recharging stations, 5 fast-recharging
ones, and 5 battery exchange ones.
In addition, when the capacity of each site increases from 5 to 10, the number of stations being sited increases from 49 to
57 for SRS, decreases from 17 to 7 for FRS, and increases from 10 to 20 for BES. Because of the higher locating cost for fast-
recharging stations, the present set-coverage based model with the objective of minimizing the locating cost will tend to
select the location of slow-recharging and battery-exchange stations. With regard to the changes (from 76 to 84) in the total
number of stations, the locating cost falls from NT$1,246,000 to NT$978,000. A higher station capacity will lead to greater
reductions in the locating cost.
As seen in Fig. 3, when the recharging rate falls from 2 to 0.6 (km/min), the total number of multiple stations increases
from 84 (57, 7, and 20) to 116 (85, 11, and 20), although the increase in the number of slow-recharging stations, from 57 to
85, is more significant. Due to the decrease in the recharging rate when using fast-recharging stations at intersections, more
slow-recharging stations need to be located at the attractions to recharge the ES.
In Fig. 4, when the unit cost of a battery exchange station increases from NT$10,000 to NT$60,000, the number of multiple
stations increases from 72 (41, 7, and 24) to 110 (89, 21, and 0), and the reduction in the number of battery-exchange sta-
tions and increase in the number of slow-recharging stations are more significant. With regard to the station cost of NT$
82 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87

Table 2
The number and locations of recharging stations for different capacities with a vehicle range of 40 km.

Location Location (number of SRS) Location Location Total number of Total location
capacity (number of (number of stations (SRS, FRS, BES) cost (NT$)
FRS) BES)
5 D1(5), D2(4), D3(3), D5(3), D6(4), D7(2), D10(4), D11(4), S8(5), C(3), S7(5), S8(5) 76(49, 17, 10) 1,246,000
D12(4), S4(2), S6(5), S7(4), S8(5) D(4), E(5)
6 D1(5), D2(5), D3(5), D4(6), D5(6), D6(6), D7(2), D10(4), S8(4), D(6) S6(3), S7(5), 94(67, 13, 14) 1,198,000
D11(4), D12(4), S4(2), S6(6), S7(6), S8(6) E(3) S8(6)
7 D1(6), D2(5), D3(2), D6(6), D7(2), D10(4), D11(4), D(7), E(6) S7(7)S7(7), 78(51, 13, 14) 1,134,000
D12(4), S1(2), S6(3), S7(6), S8(7) S8(8), S8(7)
8 D1(8), D2(5), D3(3), D4(5), D5(6), D6(8), D7(2), D10(4), D(2), E(7) S7(7), S8(8) 98(74, 9, 15) 1,046,000
D11(4), D12(4), S1(2), S6(7), S7(8), S8(8)
9 D1(7), D2(5), D3(3), D4(9), D5(9), D6(9), D7(2), D10(4), E(7) S7(8), S8(9) 103(79, 7, 17) 1,006,000
D11(4), D12(4), S4(2), S6(6), S7(6), S8(9)
10 D1(9), D2(2), D3(3), D4(3), D5(6), D6(6), D7(2), D10(4), D(4), E(3) S7(10), S8(10) 84(57, 7, 20) 978,000
D11(4), D12(4), S2(2), S6(4), S7(3), S8(5)

Fig. 2. The maps of station locations in the cases of ranges of 40 and 50 km, with capacities of 5 and 10.

50,000, 10 more fast-recharging stations need to be deployed to replace the 10 less battery exchange stations to recharge the
ES. When the station cost is up to NT$60,000, no battery-exchanging stations are used, as they are all replaced by the fast-
recharging ones.
Fig. 5 shows that as the vehicle range increases, the locating cost decreases for different deployment methods. For exam-
ple, with respect to the locations of multiple stations (convenience store mixed, i.e. mixed stations located only at conve-
nience stores), the locating cost decreases from NT$978,000 to 296,000 when the range increases from 40 to 60 km. Since
the number of recharging stations required to service all routes mainly depends on the vehicle range, the greater this range,
the fewer recharging stations that are needed to accomplish all journeys. The vehicle range is thus crucial for determining
the optimal number and locations of stations, regardless of whether single or multiple types of stations are used.
Slow-recharging stations have the lowest unit cost, while fast-recharging ones have the highest. Ideally, the locations of
slow-recharging stations will have lowest locating cost. However, since the completion of a journey is mostly affected by
the practical recharging rate, recharging time and vehicle range, siting slow-recharging stations probably cannot meet the
 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87 83

140

Number of multiple stations

120
100 Slow
80 Fast
60 Exchange

40 Total stations

20
0
0.6 0.8 1 1.2 1.4 1.6 1.8 2

Fig. 3. The number of multiple stations for fast-recharging stations with different recharging rates.
Number of recharging stations

120

100

80 Slow
Fast
60
Exchange
40 Total stations

20

0
10 20 30 40 50 60 70
Unit costs (NT$ 1,000)

Fig. 4. The number of multiple stations for different unit cost of battery exchange station, with unit costs of slow- and fast recharging stations set at
NT$4000 and NT$50,000.

overall recharging demand on the paths. For example, with the lower recharging rate of 0.133 at slow-recharging stations, in
some vehicle ranges, such as 40 to 55 km, the station locations cannot ensure the completion of entire ES journeys, as shown
in Fig. 6. That is, there are no solutions to the model when the range is below 60 km, as shown in Fig. 5. In contrast, the use of
multiple stations or fast-recharging or battery exchange ones can guarantee the completion of all journeys.
Fig. 5 shows that the use of multiple types of stations will lead to the lowest locating cost. The figure also shows that the
locating cost when using the partially mixed stations (i.e. convenience store mixed) is higher than the cost of using battery
exchange stations alone when the vehicle range is below 55 km. However, if the mixed stations are located at the overall
candidate sites, the locating cost will be the lowest. For example, with respect to the range of 40 km, the costs for a network
of mixed stations and battery exchange ones are NT$652,000 and 740,000, respectively. In addition, the locations of multiple
stations will enable ES users to choose which type of station to visit based on their recharging demand or preferences.

3.3. Solutions for the maximum-coverage based model

On the assumption that the budget is insufficient to meet the entire demand on all paths, the solutions listed in Table 3
were obtained using the following parameters: the range of the ES (40 km), the battery’s state of charge at the original point

2,000
M ultiple stations (all
1,800 mixed)

1,600 M ultiple stations

Locating cost ( NT$ 1,000)

1,400 (convenience store

mixed)
1,200 Slow-recharging
stations only
1,000
800 Fast-recharging stations
only
600
Battery exchange
400 stations only
200
0
35 40 45 50 55 60 65 70
Vehicle range (km)

Fig. 5. The relationship between the vehicle range and the locating cost for different deployment methods, with the capacity of 10 for each type of station.
84 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87

50

P8
40 P9

Fuel being Carried (KM)

P10

30

20

10

Horizontal line
0

-10
Mag. Cit. A Cit2 Ton. B C Chu. D E Wai. S8 S7 S6 Mag2
Location

Fig. 6. Some paths uncovered (below horizontal line) with a range of 40 km.

100% Multiple stations (convenience

store Mixed) ( range= 40km)

Multiple stations (convenience

store Mixed) (range= 50km)
80%
Percentage of flows covered (%)

Battery exchange stations

only (range= 40km)

Battery exchange stations only

(range= 50km)
60%
Slow-recharging stations only
(range= 40km)

Slow-recharging stations only

40% (range= 50km)

Fast-recharging stations only

(range= 40km)

Fast-recharging stations only

20% (range= 50km)

Multiple stations (all mixed)

(range= 50km)

0% Multiple stations (all

1 5 9 13 17 mixed)(range= 40km)
Budgetary constraint (NT$ 100,000)

Fig. 7. The tradeoff between the budget and percentage of flows covered for different vehicle ranges and deployment methods.

(fully charged: 40 km), recharging rates for the slow recharging, fast recharging, and battery exchange stations (0.133, 2, and
4), vehicle sharing of a type k station is set at 1, the capacity for locating each type of station at each site (10), locating cost for
slow-recharging, fast-recharging, and battery exchange stations (as mentioned above), and the length of stay at sites (as
mentioned above), and budgetary constraints (from NT$100,000 to 978,000). Table 3 shows that when the budget increases
from NT$100,000 to 978,000, the percentage of path flows being served increases from 5% to 100%. In addition, the mixed
location of different types of recharging stations is still carried out, no matter what budget constraint is used. For example,
with respect to the budget of NT$300,000, to cover 48.8% of the flows three SRS and eight BES need to be sited at the S8 con-
venience store. In theory, the budget needed to cover 100% of the flows when using the maximum-coverage based model is
same as the locating cost when using the set-coverage based one, and in this case this is NT$978,000. Although the cost is the
same, the number and location of stations using the set-coverage based model are different from those with the maximum-
coverage one. For example, some station locations, such as D3(3), D6(6), S2(2), S7(3), S8(5), D(4), and E(3), as shown in Ta-
ble 2, can be changed to D6(5), S4(2), S7(4), S8(8) and E(7), as shown in Table 3. That is, there are alternate optimal solutions
to this problem (Wang and Lin, 2009).
Fig. 7 shows the tradeoff between the budget and the percentage of path flows served for different vehicle ranges and
deployment methods. The higher the percentage of path flows that are covered, the higher the cost. In Fig. 7, if only a
single type of slow-recharging stations is deployed, the maximal percentage of flows covered just can reach 51.6% and
77.4% for the ranges of 40 and 50 km, respectively, due to the lack of coverage of some path flows, such as paths 5, 6,
Table 3
The number and location of recharging stations, and the percentage of path flows covered for different budgets, with a vehicle range of 40 km, and the station capacity of 10.

Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87

Budgetary Location (number of SRS) Location Location Total number of Path covered Number of flows
constraint (NT$) (number of (number of stations (SRS, FRS, BES) covered (percent)
FRS) BES)
100,000 – – S8(5) 5(0, 0, 5) P3, P7 5 (16.1%)
200,000 D10(2), D11(2), D12(4), S3(2) – S8(8) 18(10, 0, 8) P2,P3,P7,P11 10 (32.3%)
300,000 D1(3), D2(3), D3(3), D7(2), D10(4), D11(4), D12(4), S3(2), – S8(8) 42(34, 0, 8) P2,P3,P4,P8,P11,P12 15 (48.4%)
S6(3)S7(3), S8(3)
400,000 D1(7), D6(2), D7(2), D10(4), D11(4), D12(4), S3(2) – S7(5), S8(10) 40(25, 0, 15) P2, P3, P4, P7, P8, P10, P11, 19 (61.3%)
P12
500,000 D1(6), D3(3), D5(3), D6(4), D7(2), D9(2), D10(4), D11(4), D12(4), – S7(8), S8(9) 55(38, 0, 17) P2, P3, P4, P7, P8, P9, P10, 21 (67.7%)
S8(6) P11, P12
600,000 D1(9), D2(5), D4(3), D5(6), D6(2), D7(2), D9(2), D10(4), D11(2), – S7(10), S8(10) 70(50, 0, 20) P1, P2, P3, P4, P7, P8, P9, 24 (77.4%)
D12(2), S1(2), S3(2), S5(2), S6(2), S7(3), S8(2) P10, P11, P12
700,000 D1(10), D4(3), D5(6), D6(7), D7(2), D10(4), D11(4), D12(4), S1(2), E(3) S7(8), S8(10) 68(47, 3, 18) P1, P2, P3, P4, P5, P8, P9, 25 (80.6%)
S8(5) P10, P11, P12
800,000 D1(9), D2(5), D3(6), D5(6), D6(8), D7(2), D10(4), D11(2), D12(4), E(3) S7(10), S8(10) 83(60, 3, 20) P1, P2, P3, P4, P5, P7, P8, P9, 27 (87.1%)
S3(2), S5(2), S6(2), S7(3), S8(5) P10, P11, P12
900,000 D1(7), D2(5), D3(3), D4(3), D5(3), D6(8), D7(2), D10(4), D11(2), E(7) S7(5),S8(9) 87(66, 7, 14) P2, P3, P4, P5, P6, P7, P8, P9, 28 (90.3%)
D12(4), S1(2), S3(2), S5(2), S6(6), S7(10), S8(3) P10, P11, P12
974,000 D1(5), D4(3), D5(6), D6(6), D10(2), D11(2), D12(2), S3(2), S7(10), D(4), E(3) S2(2), S4(2), 75(46, 7, 22) P1, P2, P3, P4, P5, P6, P7, P8, 29 (93.5%)
S8(8) S7(8), S8(10) P9, P11, P12
978,000 D1(9), D2(2), D4(3), D5(6), D6(5), D7(2), D10(4), D11(4), D12(4), E(7) S7(10), S8(10) 84(57, 7, 20) P1, P2, P3, P4, P5, P6, P7, P8, 31 (100%)
S4(2), S6(4), S7(4), S8(8) P9, P10, P11, P12

85
86 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87

7, 8, 9, and 10 for a range of 40 km, and paths 5 and 6 for a range of 50 km. Therefore, to cover the overall vehicle flows,
the location of multiple stations (partially or all mixed) or battery-exchange or fast-recharging stations are needed.
However, due to the higher station cost, reaching the same coverage ratio with fast-recharging stations is more expensive
than with multiple stations (for either partially or all mixed stations). In addition, with respect to a specific budget,
vehicles with a higher range will have a higher percentage of flows covered. For example, with the deployment of multiple
stations and a budget of NT$50,000, the percentage of flows covered is 94% for vehicles with the range of 50 km, which is
significantly more than the ratio of 67.5% for those with a range of 40 km. From the viewpoint of cost effectiveness (the
percentage of flow covered with respect to a budget), the location of multiple stations (i.e. mixed stations sited at all
candidate locations) is significantly better than the location of a single type of stations, no matter whether they are
slow-recharging, fast-charging or battery-exchange ones. For example, with respect to the range of 50 km and the budget
of NT$500,000, the percentage of flows covered is 100%, 93.54%, 80.64%, 70.96%, and 32.25% for the location of all mixed
stations, partially mixed stations, battery-exchange stations, slow-recharging stations, and fast-recharging stations,
respectively.

4. Conclusions

Due to the limited range of electric vehicles, the establishment of a refueling infrastructure is necessary to ensure that
travelers can achieve their journeys. In practice, to increase the convenience and choice of road users, the siting of sufficient,
multiple types of recharging stations is the main task of facility planning. This study extended the slow-recharge station
location model presented in Wang (2011), and used the concepts of set coverage and maximum coverage to formulate
capacitated multiple-recharging-station-location models using a mixed integer programming method, based on a vehicle-
refueling logic (Wang and Lin, 2009). The results of the case study demonstrate that the approach presented in this work
can achieve the optimal deployment for a specific area, regardless of whether the minimum locating cost or maximum traffic
flows are considered, and further that a mixed stations location plan is the optimal one, when compared to the location of a
single type of recharging station, from the viewpoint of system cost or cost effectiveness.
The contributions of the paper to the literature are that it relaxes the constraints of using a single type of recharging sta-
tion and sufficient budget in Wang’s model (2011) in order to offer greater convenience and choice to travelers, as well as
cost effective facility planning based on a limited budget. To the best of our knowledge, previous studies assume that a single
type of refueling station will be used (Hodgson, 1990; Berman et al., 1992; Kuby and Lim, 2005; Wang and Lin, 2009; Wang
and Wang, 2010; Wang, 2011), while this work presents a location model for multiple types of recharging stations. More-
over, the proposed models can be applied to any type of routing behavior, and can relax the assumption of the shortest path
of single origin–destination round trips used in most of previous studies, such as those that employed the FCLM and FRLM
models. The new maximum-coverage based model, which considers the battery’s recharging rate and time, as well as vehicle
range, can simulate the changes in an EV’s stored energy at each site to determine the combination of recharging stations and
their locations needed to cover the maximal flows of such vehicles, which is not easy to achieve with conventional models,
such as FCLM and FRLM.
The results of the sensitivity analysis show that the greater the vehicle’s range, the fewer the number of stations that
need to be sited, although the recharging efficiency and capacity are also factors that influence this number and the
sites’ locations. In addition, since the objective is the minimum locating cost or the maximal flows covered with a
specific budget, the station cost is a critical factor when it comes to selecting the type of recharging stations used.
Therefore, how to increase the range of an EV and decrease the station cost are critical to achieving an effective
reduction in the costs of the recharging infrastructure, and important for the future development of this technology
(Wang and Lin, 2009).
Although the proposed models with a single objective, such as minimum cost or maximum flow, can achieve cost effec-
tiveness from the viewpoint of the supplier, the vehicle users may be concerned as to whether the infrastructure is easy to
access and the recharging time is short enough. In future work, the single objective used in this study can be extended to
multiple ones, such as also minimizing the total recharging cost or time from the viewpoint of users to determine the opti-
mal composition of station locations. In addition, the pricing of charging services still needs to be explored in order to assess
the effects of charging cost or time on the location of stations. Furthermore, the impacts of the refueling system on the exist-
ing grid or electrical power systems also need to be identified. Finally, although the case of Penghu Island is a small-scale
problem and the solution time in most of cases is less than 2 min, in some cases the time can be up to 60 min for the set
coverage based model, due to the consideration of recharging rate and time, mixed stations, and also the refueling logics
(Wang and Lin, 2009). The performance of the proposed models when used with a large-scale network still needs to be
examined, and mostly likely also needs to be improved.

References

Berman, O., Larson, R.C., Fouska, N., 1992. Optimal location of discretionary service facilities. Transportation Science 26 (3), 201–211.
Capar, I., Kuby, M., 2012. An efficient formulation of the flow refueling location model for alternative-fuel stations. Institute of Industrial Engineers
Transactions 44 (8), 622–636.
Daskin, M.S., 1995. Network and Discrete Location. John Wiley & Sons, Inc..
 Y.-W. Wang, C.-C. Lin / Transportation Research Part E 58 (2013) 76–87 87

Eggers, F., Eggers, F., 2011. Where have all the flowers gone? Forecasting green trends in the automobile industry with a choice-based conjoint adoption
model. Technological Forecasting and Social Change 78, 51–62.
Hodgson, M.J., 1990. A flow capturing location-allocation model. Geographical Analysis 22 (3), 270–279.
Khan, M., Kockelman, K.M., 2012. Predicting the market potential of plug-in electric vehicles using multiday GPS data. Energy Policy 46 (C), 225–233.
Kley, F., Lerch, C., Dallinger, D., 2011. New business model for electric cars-A holistic approach. Energy Policy 39 (6), 3392–3403.
Kuby, M., Lim, S., 2005. The flow-refueling location problem for alternative-fuel vehicles. Socio-Economic Planning Sciences 39 (2), 125–145.
Lim, S., Kuby, M., 2010. Heuristic algorithms for siting alternative-fuel stations using the Flow-Refueling Location Model. European Journal of Operational
Research 204 (1), 51–61.
Melaina, M., Bremson, J., 2008. Refueling availability for alternative fuel vehicle markets: Sufficient urban station coverage. Energy Policy 36 (8), 3233–3241.
Park and Charge system, <http://www.Park-charge.ch/> (accessed 23.08.12).
San Román, T.G., Momber, I., Abbad, M.R., Miralles, A.S., 2011. Regulatory framework and business models for charging plug-in electric vehicles:
Infrastructure, agents, and commercial relationships. Energy Policy 39 (10), 6360–6375.
Schroeder, A., Traber, T., 2012. The economics of fast charging infrastructure for electric vehicles. Energy Policy 43, 136–144.
Svoboda, V., 2009. Fast Charging. Encyclopedia of Electrochemical Power Sources, 424–442.
Thornburg, K., Hummel, A., 2003. User’s Manual. LINDO system, Inc., Chicago.
Upchurch, C., Kuby, M., 2010. Comparing the p-median and flow-refueling models for locating alternative-fuel stations. Journal of Transport Geography 18
(6), 750–758.
Wang, Y.W., 2007. An optimal location choice model for recreation-oriented scooter recharge stations. Transportation Research Part D: Transport and
Environment 12 (3), 231–237.
Wang, Y.W., 2008. Locating battery exchange stations to serve tourism transport: a note. Transportation Research Part D: Transport and Environment 13 (3),
193–197.
Wang, Y.-W., 2011. Locating flow-recharging stations at tourist destinations to serve recreational travelers. International Journal of Sustainable
Transportation 5, 153–171.
Wang, Y.-W., Lin, C.-C., 2009. Locating road-vehicle refueling stations. Transportation Research Part E: Logistics and Transportation Review 45, 821–829.
Wang, Y.-W., Wang, C.-R., 2010. Locating passenger vehicle refueling stations. Transportation Research Part E: Logistics and Transportation Review 46, 791–
801.
Wang, Y.W., Kang, H.C., Yang, Y.R., 2002. Planning and design of infrastructure system for electric scooter at Penghu recreational area. Transportation
Planning Journal 31 (3), 553–582.
West Coast Electric Highway, <http://westcoastgreehighway.com/electrichighways.htm> (accessed 23.08.12).
Yu, J.-M., Lu, R.-Z., 2013. The empirical study of battery exchange station location model. Practical Projects, Advisor: Ying-Wei, Wang. National Penghu
University of Science and Technology.