1 Introduction

The lack of sufficient public fueling stations for Alternative Fuel Vehicles (AFVs), particularly electric vehicles, compressed natural gas powered vehicles, and fuel-cell vehicles, has greatly hindered the adoption of AFVs as mass-market modes of personal transportation. Specifically, the limited vehicle travel ranges on AFVs and scarcity of fueling stations give rise to a very valid concern, from motorists’ perspectives, on successfully completing their trips. This so-called “range anxiety” in addition to their relatively high costs of ownership and maintenance even with substantial government tax subsidies, is perhaps the greatest hindrance preventing greater market penetration of AFVs. An effective system of public fueling stations on transportation networks is crucial to facilitate successful mass adoption of AFVs.

The fundamental question on where to locate the fueling stations is related to the well-studied facility location problems (Daskin 1995), that include the covering, center, and median problems, in which a central planner allocates supplies or services to satisfy demands on a spatial network. It is one of the research areas of spatial economics (Ducruet and Beauguitte 2013) and there are extensive applications in alternative fueling station (AFS) locations (Adler et al. 2014; Frade et al. 2011; Frick et al. 2007; He et al. 2013; Ip et al. 2010; Nicholas et al. 2004; Stephens-Romero et al. 2010; Wen et al. 2013). Demands in these studies were treated as being located at specified nodes on the network and drivers would have to make specific trips to the facilities to obtain services.

For facilities such as fueling stations, however, it may be more realistic to model the demands as flows on the network, which are served “on the way”. This consideration leads to the development of flow-based models. First developed by Berman et al. (1992) and Hodgson (1990), the Flow-Capturing Location Model (FCLM) is a maximum coverage model that entails facility locations to serve passing flows, which are considered as captured if a facility is located on the flow paths. Applications of the FCLM include locations of billboards for passing motorists (Hodgson and Berman 1997) and inspection stations for intercepting dangerous vehicles (Hodgson et al. 1996). The FCLM sets the foundation for a subsequent Flow-Refueling Location Model (FRLM), which is developed by Kuby and Lim (2005) to explicitly address the critical issue of limited vehicle range. The FRLM extends the FCLM to incorporate the effects of limited vehicle ranges and to allow for undertaking of long-distance trips via possible multi-stop refueling. The FRLM is a maximum coverage model, which maximizes the flows served on the network given a predefined total number of stations. The model has been used to site hydrogen refueling stations in the state of Florida (Kuby et al. 2009; Lim and Kuby 2010). Distinct from the maximum flow coverage models, there is another series of flow-based models that aim to satisfy all travel demands by using the least number of AFSs through strategic locations on networks (Wang 2007, 2008; Wang and Lin 2009), which are called flow-based set-covering models. These two distinct types of flow-based models have been reformulated as a flexible refueling station location problem (MirHassani and Ebrazi 2013). The recent efforts on the development of flow-based facility location problems have already been elucidated in a comprehensive review (Zeng et al., 2010).

The sparse distribution of AFSs on networks means that AFV users may be willing to take a slightly longer path (i.e., a deviation path) to ensure that they can refuel their vehicles en route, particularly on long-distance trips. This alternate routing consideration is particularly realistic as drivers can now use mobile map applications (e.g., Google Map®) to navigate. Berman et al. (1995) is among the first to relax the assumption that all flows are on the shortest path between O-D pairs. Kim and Kuby (2012) recently formulate a Deviation-Flow Refueling Location Model (DFRLM) to extend the FRLM, in which facilities are located so as to maximize the total flows refueled via at most one path (including deviation paths) for each O-D pair that contributes most to the objective.

In this study, we develop a novel, AFS location model, called the Multipath Refueling Location Model (MPRLM), in which AFV users can utilize multiple deviation paths between all O-D pairs on the network. An O-D pair is considered as covered if there is at least one path, either a shortest path or a path with a reasonable deviation, available between the O-D pair through which drivers can complete a trip with single/multiple refueling stops. The model minimizes the total cost of locating AFSs while satisfying travel demands between all O-D pairs, subject to limited vehicle travel ranges. The MPRLM provides integrated decisions on strategic refueling station locations and the feasible routes between O-D pairs under a single framework. Note that all AFSs in this study are assumed as uncapacitated and the effects of traffic flows and congestions are not explicitly addressed in this model. These assumptions are more defensible in the early AFV adoption phase. When AFVs are massively adopted, explicit AFS capacity design will be necessary.

By incorporating deviation paths into a flow-based set-covering model, our MPRLM considers multiple deviation paths available between an O-D pair. It is believed that this relaxed assumption offers a greater flexibility in siting stations on networks than the existing studies. We summarize the major differences between the proposed model and the existing flow-based models in Table 1.

Table 1 Summary of differences between the proposed MPRLM and existing flow-based models
Full size table

We implement the MPRLM on two test networks – the Sioux Falls road network (LeBlanc et al. 1975) and a 25-node network (Simchi-Levi and Berman 1988). These have been widely used as representations of real networks for numerical experiments in the transportation network design (the Sioux Falls network) and facility location problems (the 25-node network). We use these test networks to draw insights into the interplay between locations, deviations, and vehicle ranges. The model can be applied towards different problems by customizing it to meet the specific technological requirements, e.g., electric vehicle charging stations, battery swapping stations, compressed natural gas stations, hydrogen refueling stations. The most cost-effective vehicle travel range is also identified as an “elbow point”, at which the marginal reduction in the total cost of building AFSs drops. This work will enhance the efforts of private industry to increase its service coverage in a strategic manner and help government agencies plan subsidies to generate public interest in buying AFVs before the market matures.

The remainder of the paper is organized as follows. We will present the concept, assumptions, and formulation of the multipath station location model in section 2, with in-depth discussions on modeling and algorithms in generating multiple paths. In section 3, we will present the numerical results of the model on the two test networks and the results of sensitivity analyses. We will conclude the study and outline the possible future work in section 4.

2 Multipath Refueling Location Model (MPRLM)

In this MPRLM, AFSs may not be located exactly on a pre-planned path (e.g., a shortest distance or shortest travel time path), but they can still serve drivers if they are fairly close within a reasonable deviation limit. It is believed that drivers would accept a moderate deviation for refueling en route. The model integrates the considerations of multiple paths and the limited vehicle ranges into the decision making process for AFS locations, aiming to provide a least-cost solution while satisfying trips between all O-D pairs with reasonable deviations.

The critical model inputs are deviation paths between O-D pairs and vehicle travel ranges. Without available empirical data as to what extent travelers would deviate for refueling from their pre-planned paths (normally the paths with which the travelers are most familiar), we assume a set of deviation tolerances in terms of distance, mainly because the vehicle range is directly related to the distance traveled. Note that travelers’ deviation choices can also be dominated by other factors, such as travel time, travel cost, and network topology. However, there has been no well-defined relationship between deviation acceptance and different factors and most studies still rely on some explorative methods as pointed out by Kim and Kuby (2012). In this study, we assume that one of the shortest paths is treated as the pre-planned path between an O-D pair, and that deviation paths are either other shortest paths (if any) or paths that are slightly longer than the pre-planned path. Deviation paths are exogenously generated by algorithms described in section 2.3 and dependent on the selected deviation tolerances. These deviation paths will then be the model inputs. Note that the model is not designed to satisfy all deviation paths. Instead, as long as there is at least one path between an O-D pair that can be completed via single or multi-stop refueling, this pair is considered as covered. The AFV’s vehicle travel range is another important model input that restricts the maximum distance traveled by a vehicle before refueling.

2.1 A Sample Network

We use a 7-node network (Fig. 1) to demonstrate the concept of the multipath refueling location problem. Assume that nodes A and E are origins, nodes C and G are destinations, and nodes B, D, and F are intermediate nodes. There are four O-D pairs, i.e., A-C, A-G, E-C, and E-G. The numbers on the links are link lengths and vehicle range is assumed to be 15.

Fig. 1
figure 1

A 7-node sample network

Full size image

If only shortest paths are allowed between O-D pairs, three stations in total are needed at nodes B, D, and F, in which nodes B and F will respectively serve the O-D pairs A-C and E-G and node D will serve both the pairs A-G and E-C. If a 20 % deviation from a shortest path is acceptable, drivers going from node A to C can accept the path A → D → C. Similarly, the path E → D → G is now acceptable for trips from node E to G. Because of this relaxation, only node D is needed, which covers all O-D pairs. Paths between the O-D pairs of A-G and E-C remain unchanged. However, a drop in the deviation to 10 % eliminates the deviation path available for both pairs A-C and E-G, resulting in a solution that is identical to that of considering the shortest paths.

The above example illustrates how deviations can help reduce the total number of stations needed. The AFS locations are results of vehicle range and choices of deviation tolerances. A higher deviation from the increased flexibility in path choice would reduce the number of stations needed on the network while increasing the total distance traveled. This trade-off will be explicitly discussed in section 3.

2.2 Model Formulation

Let (N, A) be a transportation network where N and A are the sets of nodes and links in the network respectively, with Ñ the set of candidate locations for AFSs, Ñ ⊆ N. Denote a link by a ∈ A or the pair of its starting and ending nodes, i.e., a = (i, j) ∈ A. Let R ⊆ N, index r, be a set of origin nodes, and S ⊆ N, index s, be a set of destination nodes. With K deviation paths, where K is a predefined maximum number of deviation paths, we denote by P rs,k a sequence of nodes on the k th path from nodes r to s, where k =1, 2,…, K.

We make the following assumptions: (1) candidate locations for AFSs are predetermined; (2) vehicles are homogenous and fully fueled at origins; (3) AFSs are uncapacitated; (4) energy (e.g., fuel or electricity) consumed and refueled is unified in terms of travel distance; (5) all drivers are fully informed about AFS locations on the network; and (6) vehicle range (e.g., in miles) is predetermined and homogenous for all AFVs.

A mixed integer linear programming (MILP) model is formulated. The complete model (P) is provided in (1)–(10):

Minimize

$$ \mathrm{Z}={\displaystyle \sum_{i\in \tilde{N}}{w}_i{X}_i} $$
(1)

Subject to:

$$ {B}_i^{rs,k}+{l}_i^{rs,k}\le \overline{M}\left(1-{Y}^{rs,k}\right)+\beta \forall r\in R,s\in S;i\in {P}^{rs,k};k=1,2\dots, K $$
(2)
$$ {B}_i^{rs,k}+{l}_i^{rs,k}-{d}_{ij}-{B}_j^{rs,k}\le \overline{M}\left(1-{Y}^{rs,k}\right),\forall r\in R,s\in S;i,j\in {P}^{rs,k};\left(i,j\right)\in A;k=1,2\dots, K $$
(3)
$$ -\left({B}_i^{rs,k}+{l}_i^{rs,k}-{d}_{ij}-{B}_j^{rs,k}\right)\le \overline{M}\left(1-{Y}^{rs,k}\right),\forall r\in R,s\in S;i,j\in {P}^{rs,k};\left(i,j\right)\in A;k=1,2\dots, K $$
(4)
$$ {\displaystyle \sum_{r\in N}{\displaystyle \sum_{s\in S}{\displaystyle \sum_k{l}_i^{rs,k}}{\delta}_i^{rs,k}\le \overline{M}{X}_i}}\forall i\in \tilde{N} $$
(5)
$$ {\displaystyle \sum_k{Y}^{rs,k}\ge 1}\forall r\in R,s\in S $$
(6)
$$ {B}_i^{rs,k}=\beta \forall r\in R,s\in S;i\in R;k=1,2,\dots, K $$
(7)
$$ {X}_i=\left\{0,1\right\}\forall i\in \tilde{N} $$
(8)
$$ {Y}^{rs,k}=\left\{0,1\right\}\forall r\in R,s\in S;k=1,2,\dots, K $$
(9)
$$ {B}_i^{rs,k}\ge 0,{l}_i^{rs,k}\ge 0\forall r,s;i\in {P}^{rs,k} $$
(10)

where:

i: :

index of candidate AFS sites, i ∈ Ñ ⊆ N

r: :

an origin node in the network, r ∈ R ⊂ N

s: :

a destination node in the network, s ∈ S ⊂ N

k: :

index of the paths for an O-D pair, k = 1, 2, …, K

a: :

index of arc set A, a = (i, j) ∈ A.

w i: :

weight on each candidate site, such as the installing and operating cost of an AFS, i ∈ Ñ

β: :

onboard fuel capacity (unified in travel distance), i.e., vehicle range

\( \overline{M} \) :

a sufficiently large number

P rs,k: :

a sequence of nodes on the k th path between r-s; where k =1,2…K

d ij: :

distance between node i and j

δ rs,k: i :

=1 if node i is in the set of nodes P rs,k, 0 otherwise, this is an outcome of multipath algorithm (described in section 3.3).

X i: :

=1 if an AFS is located at node i 0 otherwise

Y rs,k: :

=1 if the k th path between r and s can be completed (taken), 0 otherwise

B rs,k: i :

remaining onboard energy at node i on the k th path of O-D pair r-s

l rs,k: i :

amount of energy refueled at node i on the k th path of O-D pair r-s.

The objective is to minimize the total cost of locating AFSs on the network. When w i  = 1, ∀ i ∈ Ñ, it minimizes the total number of stations, which is essentially a flow-based set-covering problem with path deviations. Constraint set (2) assures that the total onboard fuel will not exceed the AFV fuel capacity (B rs,k i  + l rs,k i  ≤ β) on those paths k that are taken by the vehicle (i.e., Y rs,k = 1); otherwise no restriction is applied (i.e., Y rs,k = 0), simply because no traveler will use that route. Constraints (3) and (4) work simultaneously to ensure that the energy consumption conservation B rs,k i  + l rs,k i  − d ij  − B rs,k j  = 0 holds for all links on the k th path if the path is taken (Y rs,k = 1) by any AFV. Otherwise, when Y rs,k = 0, the inequality becomes \( {B}_i^{rs,k}+{l}_i^{rs,k}-{d}_{ij}-{B}_j^{rs,k}\le \overline{M} \), i.e., no restraining effects. Constraint set (5) is a logic constraint, stating that refueling is only available at node i if AFSs are available. Constraint set (6) states that there is at least one path, either a shortest or deviation path, available between an O-D pair. Constraint set (7) follows the assumption that all AFVs are fully refueled at origins (i.e., i ∈ R). Constraints (8)–(10) are binary and nonnegativity constraints.

Note that the proposed MPRLM generalizes the assumption of the shortest paths between O-D pairs in the refueling location models, which is equivalent to the case of K = 1 in this model. It is also distinct from the DFRLM (Kim and Kuby 2012) in that multiple deviation paths are considered in constraint (6). Moreover, the model provides the routing choices indicated by Y rs,k.

  • Remark 1: The constraints (2)–(5) in the model (P) involving sufficiently large number \( \overline{M} \) may raise computational concerns. Mixed-integer programming solvers (such as CPLEX) proceed by optimizing continuous relaxations of the constraints, but for very big M values a relaxation will yield very tiny values of the binary variable (i.e., Y rs,k in this model) that do not provide useful information about the effects of the variables on the left-hand side of an inequality. Generally, the presence of one group of coefficients that are larger by many orders of magnitude than any of the others is known to have potentially bad numerical effects of the all aspects of the solution process.

    We now make a proposition to convert problem (P) to an equivalent optimization problem (P1) that will yield the same optimal value of the objective function by replacing the inequality (2) with a more restrictive set of constraints (11) and (12),

    $$ {B}_i^{rs,k}+{l}_i^{rs,k}\le \beta, \forall r\in R,s\in S;i\in {P}^{rs,k};k=1,2\dots, K $$
    (11)
    $$ {l}_i^{rs,k}\le \beta {Y}^{rs,k}\forall r\in R,s\in S;i\in {P}^{rs,k};k=1,2\dots, K $$
    (12)

    Constraint set (11) assures that the total onboard energy will not exceed the capacity on all possible paths between an O-D pair. Constraint set (12) is a logic constraint, stating that the energy fueled l rs,k i has to be within the capacity for those paths taken (i.e., Y rs,k = 1); otherwise it is zero (Y rs,k = 0). With substitution of constraint sets (11) and (12) with constraint set (2), we define a new model (P1) as: Minimize (1), subject to: (3)–(12).

    The model (P1) can significantly improve the solution efficiency, compared to the model (P) for two major reasons. First, it eliminates the big number \( \overline{M} \) in constraint set (2). As discussed in Remark 1, the big \( \overline{M} \) results in computational and numerical problems. Secondly, it improves the solution efficiency. In constraint set (12) if Y rs,k = 0, then l rs,k i  = 0 and B rs,k i  ≤ β, which reduces the number of variables and constraints from the model (P) and essentially eliminates the big \( \overline{M} \) in constraints (3) and (4) as well. We show the numerical comparisons between these two models in section 3.1. Constraint set (5) is a standard logic constraint and a similar transformation is not easy to derive. For numerical implementations, a least sufficiently large value is selected. For example, it is possible to set the value equal to the total number of paths × β for the uncapacitated location model or to the AFS capacity for a capacitated model.

    • Proposition 1: Problem (P1) yields the same optimal value of the objective function as in Problem (P).

    • Proof: Let Z* and Z1* respectively denote the optimal objective values of problems (P) and (P1). Since the constraint set in problem (P1) are more restrictive, then Z* ≤ Z1*. On the other hand, suppose X* and Y* are solutions of problem (P). It is then clear that for the k th path between O-D pair r and s such that Y*rs,k = 1, constraint 2 is equivalent to constraints (11) and (12). For the k th path between O-D pair r and s such that Y*rs,k = 0, because B rs,k i and l rs,k i are practically not bounded by constraints (2)–(4) due to a fairly large number \( \overline{M} \), we can always find B rs,k i and l rs,k i for any node i ∈ P rs,k such that both constraints (11) and (12) are satisfied, and the adoption of the new constraints does not change the feasibility of X* and Y*. Therefore, X* and Y* are still feasible so that \( {\mathrm{Z}}_1^{*}\le {\mathrm{Z}}^{*} \). Overall, Z* = Z1*, and X* and Y* is also an optimal solution for the problem (P1).

  • Remark 2: Problem P1 can be solved much more efficiently than the original problem (P). In the case where the weights w equal one for all locations, the model leads to the minimum number of AFS locations needed for the network. In another case when the weights w represent installing and operation costs of AFS and the values may be differentiated with different locations, the model results in the minimum total cost and the resulting total number of stations will be at least as many as the minimum number of stations of the problem when w = 1. However, in either case, the station locations may not be unique, nor are the paths traversed between O-D pairs. We discuss more numerical experiments in section 3.1.

2.3 Notes on the Algorithms Generating Multiple Paths

The multiple paths between an O-D pair reflect drivers’ tolerance in deviation from the shortest path and the deviation paths could be the 2nd, 3rd, …, k th shortest paths. There are two types of K-shortest path problems: one allows loops between node pairs in a network and the other does not allow any loops, which is also called the K shortest loopless paths. The first type is easier to implement with existing algorithms such as the N-path method (Hoffman and Pavley 1959). The second type is more challenging due to the additional loopless constraint that no repeated nodes are allowed on a path. First addressed by Yen’s algorithm (Yen 1971),Footnote 1 it has been further developed in other studies (Martins and Pascoal 2003; Qian and Zhang 2013). In this study, we adopt the loopless Yen’s algorithm for two reasons. First, because a transportation network is a network without links that are negative in travel time or distance, looped trips do not help reduce travel cost. Second, for flow-based facility location problems including the refueling station location problem in this paper, specific looped trips to stations are avoided because the goods or services are modeled to be obtained “on the way”.

However, because this algorithm only specifies the number of alternative paths between an O-D pair, the deviations from a shortest path can be too large to be realistic in some cases. We develop the K-shortest path with deviation cap algorithm by imposing a cap that restrains the alternative path within a predefined deviation limit, e.g., 10 %, 20 %, and 50 %. The algorithm can be described as follows:

For each O-D pair (r, s):

  1. Step 1

    Find the shortest path using any efficient shortest path algorithm, such as Dijkstra’s algorithm (Dijkstra 1959) for (r, s) (the length denoted as L rs,1); set k =1.

  2. Step 2

    Compare the length of the k th path (denoted as L rs,k) with (1 + p)L rs,1, where P is a predefined deviation cap. If L rs,k ≥ (1 + p)L rs,1, then stop; otherwise, set k = k + 1, and go to step 3;

  3. Step 3

    Find the k th shortest path using Yen’s algorithm; Go to step 2.

Note that if the parameter K in the algorithm is sufficiently large, the algorithm will find all deviation paths within the predefined deviation cap. Depending on the network structure, the number of deviation paths between an O-D pair may vary. In some cases (especially large-scale networks), we may need to use a finite K and deviation cap jointly to restrict the number of deviation paths between O-D pairs.

3 Numerical Implementation and Analysis of Results

To validate the model and demonstrate its applicability, we implement the model on the two well-known test networks: the Sioux-Falls roadway network and the 25-node network shown in Fig. 2. The numbers in the circles represent the node indices. The numbers on the links denote the test distances in miles or kilometers.

Fig. 2
figure 2

Two test networks

Full size image

These two networks have different topological structures. In particular, the Sioux-Falls network is a closed-loop network, in which every node is interconnected with at least two other nodes, while in the 25-node network node #25 is only connected to #24, which is a “tail” that makes the network less flexible in station deployment. In the numerical study, we assume that all nodes are candidate sites for AFSs, i.e., Ñ = N and we treat every candidate site equally costly, i.e., w i  = 1, ∀ i ∈ Ñ. Every node on the network is an origin and a destination, i.e., R = S = N.

Solving the model (P1) involves two major steps: (1) preparing the multipath sets for all O-D pairs as model inputs by using the K-shortest path algorithm and the K-shortest path with deviation cap algorithm, which are both implemented in MATLAB; and (2) programming the model in AMPL (Fourer et al. 2003) and solving it by using a commercial solver CPLEX 12.4. All numerical experiments described run on a DELL desktop with 8 GB RAM and Intel Core i5-2500@3.30GHz processor under Windows 7 environment. Depending on the deviation tolerance, the number of decision variables Y rs,k and number of constraints may be expanding exponentially. Thus, solving time may vary dramatically.

3.1 The Sioux Falls Network

The vehicle range is set to be 100 the length of the longest link on the network. We consider three different deviation scenarios – the shortest path (K = 1), 3-shortest paths (K = 3), and 20 % deviation cap to illustrate how different deviations affect the station siting strategies. Optimal AFS locations are represented by solid nodes in Fig. 3.

Fig. 3
figure 3

Locations of AFSs on the Sioux Falls network with vehicle range of 100 under three deviation scenarios

Full size image

Results indicate that deviations help reduce the number of stations required. In particular, the minimum numbers of stations needed following the solutions of shortest path (K = 1), K = 3 and 20 % deviation cap are respectively 12, 7, and 11. The paths traversed between O-D pairs can be identified by revealing the decision variables Y rs,k, which are determined simultaneously with the station location decisions. For example, in the K = 1 solution, path #1 → 2 → 6, highlighted in Fig. 3a, is traversed between nodes #1 and #6 and AFVs on that path have to stop at node #2 for refueling. When K = 3, two additional paths #1 → 3 → 4 → 5 → 6 and #1 → 3 → 12 → 11 → 4 → 5 → 6 become acceptable, which are the second and third shortest paths between that O-D pair. These two deviation paths shown in Fig. 3b help eliminate AFSs at node #2. In particular, the path #1 → 3 → 4 → 5 → 6 is completed via refueling at node #5 and the path #1 → 3 → 12 → 11 → 4 → 5 → 6 is completed via multi-stop refueling at nodes #12, 11, and 5. The solution of the 20 % deviation cap shows a similar location pattern as the solution of K = 1. This is because only very few paths other than the shortest are within a 20 % deviation cap. For example, there is no deviation path within 20 % cap between the O-D pair #1 to #6 and thus only the shortest path is taken. The results in Fig. 3 also imply that new station siting plans with deviations are not simple processes of removing stations from the K = 1 solution, which instead require re-optimizations of the entire network.

We provide the number of paths served by different stations (i.e., the number of paths passing through a particular station) under three deviations in Table 2 to demonstrate the variability of the “workload” of each station (measured by the number of paths served). We note that even for the same location (e.g., the station at node #5), the number of paths served varies with deviation scenarios. Note also that the total number of paths served can be higher or lower than the 552 O-D pairs, i.e., the total number of O-D pairs on the Sioux Falls network. This is due to duplicating counts of a path that goes through multiple stations, (more than 552) or multiple O-D pairs served by the same paths (less than 552). From this table, it is clear that the nodes #5, #8, #11, and #15 are critical locations as they are used in all three deviation scenarios.

Table 2 Number of paths served by different AFS locations
Full size table

As noted in Remark 2, the model yields the minimum number of stations but non-unique locations for a given vehicle range and a deviation. Fig. 4b demonstrates another location solution for the same minimum 12 stations when K = 1 with a vehicle range of 100. This non-uniqueness in location solutions also helps explain why AFS locations can alter when node weight w is differentiated. For example, if the weight of node #3 is set high at 10 (e.g., a high initial installation cost of an AFS in reality) while the weights of other nodes remain, a new location solution is found as shown in Fig. 3c. The total number of stations increases to 13 and the node #3 is not selected due to the high cost. It implies that the node #3 can be replaced with other combinations of nodes on the network.

Fig. 4
figure 4

Multiple location solutions for K = 1 and vehicle range of 100

Full size image

We further analyze the coupled effects of deviations and vehicle ranges on the number of AFSs sited. In particular, we test five different deviation caps at 0 %, 10 %, 15 %, 20 %, and 50 % coupled with seven different vehicle ranges between 100 and 250 with a 25 interval, totaling 35 tests. The results, shown in Fig. 5, indicate that the minimum number of stations needed declines with longer vehicle ranges, which in turn makes deviations less appealing. For example, when the vehicle range is up to 225, only one station is needed and no user needs to deviate their routing. It drops to zero when the vehicle range reaches 250. We also analyze the effects of the K values in the same way and the results plotted in Fig. 6 show similar conclusions.

Fig. 5
figure 5

Effects of deviation caps and vehicle ranges on the minimum numbers of AFSs needed on the Sioux Falls network

Full size image
Fig. 6
figure 6

Effects of K and vehicle ranges on the minimum numbers of AFSs needed on the Sioux Falls network

Full size image

Empirical vehicle ranges can be lower than the theoretical (or anticipated) values, due to a number of prevailing factors, such as traffic conditions, weather, and the variability in users’ anxiety to refuel. We conduct an analysis to understand the impacts of variations in vehicle ranges caused by these factors on the minimum number of stations needed. In particular, we assume a vehicle range of 200 and two levels of deductions, 25 % and 50 %, with resulting vehicle ranges of 150 and 100. The results plotted in Fig. 7 show that the numbers of stations increases significantly from one station to as many as 12 stations with the deductions, varied by deviations. We note that a larger deviation (e.g., K = 3) helps reduce the sensitivity in siting strategies than a lower deviation (e.g., shortest path). In particular, following K = 3 deviation, there are five more stations needed when vehicle range is reduced by 50 % while it requires 10 more stations if the shortest paths are considered.

Fig. 7
figure 7

Effects of the vehicle range deduction on the minimum numbers of AFSs needed on the Sioux Falls network

Full size image

We conduct numerical experiments for comparing the computational performances by models (P) and (P1) under different deviation scenarios, the results of which are reported in Table 3. All these numerical experiments are solved by CPLEX to optimality (i.e., 0 % gap). Here, all the solutions are in terms of number of stations and all computation times are in CPU s. From the results, higher deviations result in longer computing times due to the increased number of variables and constraints. Under all three deviations, both models (P) and (P1) result in identical optimal objective values (i.e., the same minimum number of stations) while model (P1) significantly reduces computing times than model (P) under all deviation scenarios.

Table 3 Comparisons of computational performances of models (P) and (P1)
Full size table

3.2 A 25-Node Network

We implement the model on a 25-node network by using the same three deviation scenarios. The optimal locations are represented by the solid nodes in Fig. 8. With vehicle range of 10, the minimum of numbers of stations are 10, 8, and 9 for deviation scenarios K = 1, K = 3 and 20 % deviation cap, respectively. Compared to the Sioux Falls network, the 25-node network shows lower variations in the station siting strategies, mainly because the link lengths are less varied and the “tail” of the network (i.e., the nodes #22, 23, 24, and 25) requires stations to be located at nodes #14 and #24 regardless.

Fig. 8
figure 8

Locations of AFSs on the 25-node network with a vehicle range of 10 under three deviation scenarios

Full size image

We take the O-D pair #1–#10 as an example to highlight the differences in the used paths under different deviation scenarios. The K = 1 solution is illustrated in Fig. 8a. In the K = 3 solution, this O-D pair is covered via the third shortest path with multi-stop refueling at nodes #4 and #8 as shown in Fig. 8b. With the 20 % deviation cap, both the shortest path #1 → 2 → 3 → 9 → 10 and the fourth shortest path #1 → 5 → 7 → 8 → 10 is used to cover the O-D pair as shown in Fig. 8c.

The effects of deviations coupled with vehicle ranges on the station deployment on the 25-node network are also analyzed with the results plotted in Figs. 9 and 10. Similar observations are made as for the Sioux Falls network. Particularly, an identical number of stations is used when vehicle range is 10 when deviation caps are relatively low (i.e., 10 %, 15 %, and 20 %). A further investigation reveals that only the shortest paths are used in these deviation scenarios. We also identify that the “elbow point” Footnote 2 of vehicle range is 20, implying that a vehicle range of 20 may be the most cost effective in terms of the total cost of building stations. The marginal savings in the total cost (in this case, equivalent to the total number of stations) reduces when the vehicle range is higher than 20.

Fig. 9
figure 9

Effects of the deviation caps and vehicle range on the minimum numbers of AFSs needed on 25-node network

Full size image
Fig. 10
figure 10

Effects of K and the vehicle ranges on the minimum numbers of AFSs needed on 25-node network (note: K = 4 and K = 5 lines are completely overlapped)

Full size image

We conduct a similar analysis on the effects of deducted vehicle ranges on the 25-node network, with the results shown in Fig. 11. These results are based on the vehicle range of 40 and three levels of deductions, i.e., 25 %, 50 %, and 75 %, with respectively resulting vehicle ranges of 30, 20, and 10. Similar to what we have observed for the Sioux Falls network, the deductions in vehicle range require more stations. There is, however, less variability among different deviation scenarios (K = 1, K = 3, and 20 % deviations), due to the lower variability in both the link lengths and the topological structure.

Fig. 11
figure 11

Effects of the vehicle range deduction on the minimum numbers of AFSs needed on the 25-node network

Full size image

3.3 Sensitivity Analysis on user Inconvenience due to Deviations

In general, a reduced number of AFSs deployed on the network increase the average travel distance. We further explore the tradeoffs between the cost of locating stations (in terms of number of stations) and user convenience (in terms of travel distance) with deviations. Our results would provide managerial insights to planners.

As noted in Remark 2, the model (P) sets the objective as to minimize the number of stations, which may not yield unique station locations. For each deviation scenario, the resulting average deviation, defined as the average additional travel distance for the entire network due to deviations, may not be unique. In this analysis, we reformulate the problem to minimize the total deviation in the objective function (13), given the number of stations (i.e., the resulting minimum number of stations from the model (P)) in constraint (14). The new model is denoted as model (P-dev). The average deviation equals the total deviation (i.e., objective value) divided by the total number of paths (including all deviation paths) \( {\displaystyle \sum_{rs,k}{Y}^{rs,k}} \), which is unique with respect to the given number of stations.

Minimize

$$ {\displaystyle \sum_{rs,k}\frac{c^{rs,k}-{c}^{rs,1}}{c^{rs,1}}{Y}^{rs,k}} $$
(13)

Subject to:

$$ {\displaystyle \sum_i{X}_i=}T $$
(14)

Including (3)–(12)

c rs,k::

a parameter, the length of the k th shortest path connecting r and s

T::

a parameter, the minimum number of stations resulted from model (P)

All other notations are the same as in the model (P).

The results are summarized in Table 4, in which zeroes indicate either no deviation (i.e., K = 1) or deviation paths with an identical minimum distance ( in deviation cap scenarios of 10 %, 15 %, and 20 %). The resulting station locations are displayed in the column with heading “Station location #”. In general, a relaxed deviation scenario (e.g., higher K or deviation cap) helps reduce the number of stations with only a slight increase in the average deviation. This finding is most interesting to planners, as it implies that a high level of service to AFV users can be maintained with a low cost through smart planning. For example, for deviation scenarios from K = 1 to K = 5, on the Sioux Falls network, half of the 12 stations have been saved but this 50 % reduction only increases the average travel distance by about 3.3 %. Similarly, on the 25-node network, 30 % (= (10–7) / 10) reduction in the number of stations only causes the average travel distance increased by about 2 %.

Table 4 The average deviation and AFS locations under different deviation scenarios
Full size table

We also notice that for some cases when the same number of stations is sited on the network, a higher deviation helps reduce the average deviation on the network. For example, on the 25-node network, the average deviation with K = 3 drops slightly by about 0.1 % (=1.42 %–1.3 %) from K = 2. This can be explained as following. First, the model (P-dev) minimizes the total deviation on the network, given the total number of AFSs . When the total number of AFSs is identical, the average deviation in a higher deviation scenario should be at least as good as the one in a lower deviation scenario. Second, a higher deviation permits the selection of more deviated paths for some O-D pairs while let other O-D pairs be traversed via shortest paths. The average deviation for the entire network is a result of the trade-offs. As seen from Tables 5 and 6, which report the numbers of shortest and deviation paths used on both networks under different deviation scenarios, the number of shortest paths increases by 5 (=483–478) from K = 3 to K = 2 and the number of deviation paths drops by 5 (=122–117). As a result, the overall average deviation is reduced. Similar explanations apply to the comparisons between K = 5 and K = 4.

Table 5 Numbers of paths used in the Sioux Falls network under different deviation scenarios
Full size table
Table 6 Numbers of paths used in the 25-node network under different deviation scenarios
Full size table

Tables 5 and 6 also indicate that AFS locations are primarily determined based on the use of the shortest paths, which implies that a small number of deviation paths can substantially reduce the number of AFSs needed.

4 Conclusions and Discussions

We develop the multipath refueling station location model (MPRLM) to seek the most cost-effective AFS location strategies on the networks, considering limited vehicle ranges and allowing for multiple deviation paths between O-D pairs. The MPRLM minimizes the total cost of establishing new refueling stations on transportation networks while satisfying demand among all O-D pairs. Our model integrates deviation paths into a flow-based set-covering problem.

We implement the model on two well-known test networks - the Sioux Falls and 25-node networks. The results indicate that the decisions on AFS locations and paths traversed between O-D pairs are interdependent and thus should be determined simultaneously. The use of deviation paths can substantially reduce the total cost of establishing AFSs or the minimum number of stations with a reasonable compromise of users’ convenience. From the sensitivity analysis, we understand that AFS are primarily located based on the use of shortest paths while the use of a small number of deviation paths has substantially reduced the system cost. An “elbow point” rule is also used to identify the most cost effective vehicle range in terms of total cost of building AFSs.

There are two immediate extensions to this study. First, an application of this model to a real-world case study of developing electric vehicle charging corridor in the state of South Carolina is undertaken. In addition to the challenges in data collection and processing, the intractable nature of a large scale model requires developing heuristic solutions. Secondly, to make the model more general and realistic, station capacity design should be an integrated decision set involving modeling traffic flows and the inevitable congestions on the roadways or at stations. A bi-level modeling framework is recommended, in which the strategic system planning decisions are made on the upper level while traffic assignment is incorporated on the lower level. However, the complementarity constraints associated with the user equilibrium conditions in traffic assignment will make the model a Mathematical Problem with Complementarity Constraints (MPCC), which is notoriously difficult to solve. Thus, algorithmic development will be another major effort in the future research.