1 Introduction

Electric vehicles (EVs) have gained much attention from the public over the past decades. As a green transport mode, EVs have high energy efficiency and generate significantly fewer emissions compared to traditional transport modes such as gasoline vehicles, yielding a variety of environmental and social benefits. However, the limited driving range and scarce charging facilities hinder the wide adoption of EVs, especially for long-distance trips, during which drivers may need to charge several times to ensure the journey. In addition, steep roads, the variation of driving speed, and the use of auto electrical parts, etc. would lead to more energy consumption and thus call for more frequent charging than normal (De Cauwer et al. 2015). To promote the adoption of EVs, many governments have substantially invested in building public charging facilities. The State Power Grid of China, for example, plans to invest RMB ¥1.1 billion in the charging station construction in Zhejiang Province by the end of 2020 (XinhuaNet 2018).

There are multiple types of charging facilities in the market. These charging stations can be classified into two main types by the power rate used, i.e., fast-charging stations and slow charging stations (Morrow et al. 2008). Fast-charging stations usually use power of over 50kWh, while slow-charging stations use power of less than 20kWh. Compared with a slow-charging station, a fast-charging station offers a much higher charging efficiency but incurs larger procurement and installation cost. For example, a fast-charging station can fully charge a 60kWh battery within an hour, while a slow-charging station needs several hours to fully charge it (Yilmaz and Krein 2012). As for the construction cost, according to the report of the U.S. Energy Department, the costs of building a fast-charging station and a slow-charging station are $8.5 million and $4.25 million, respectively (NREL 2012). In light of the huge investment and characteristics of different types of charging stations, it is imperative to develop an optimization model of deploying multiple types of charging stations so as to fulfill as many charging demands as possible under a limited budget.

1.1 Literature Review

Over the past years, many studies have focused on the refueling facility location problem for EVs and other alternative fuel vehicles. Among these studies, Hodgson (1990) was the first to develop a flow capturing location model (FCLM) to cover as many flows as possible. A flow between an origin-destination(OD) pair was assumed to be covered if there was at least one refueling station along its travel path. Kuby and Lim (2005) extended the FCLM by developing a flow refueling location model (FRLM) where drivers may need to refuel the energy several times to complete a journey. Both the FCLM and FRLM assumed that drivers would travel on the shortest path between an OD pair. Kim and Kuby (2012) later put forward a deviation flow refueling location model (DFRLM) to characterize drivers’ detour behavior for charging. Specifically, drivers were allowed to travel along any deviation path other than the shortest path as long as the distance of the deviation path did not exceed a pre-specified maximal acceptable distance deviation. Since then, many follow-up studies have been conducted on top of FRLM and RFRLM (Capar et al. 2013; Guo et al. 2018; He et al. 2018; Kuby and Lim 2007; Lim and Kuby 2010; Upchurch et al. 2009; Wang and Lin 2009; Xu et al. 2020; Yang et al. 2017).

All the aforementioned studies assumed that EVs would be fully charged upon a charging station. This assumption is reasonable for a battery-swapping station where a depleted battery is swapped to a fully charged one within a few minutes but may not be so for a charging station. In the real world, drivers prone to partially their vehicles at visited stations along the trip. This is because fully charging is costly and time consuming due to the limitation of battery and charging technologies. Fully charging en route largely increases travel time and charging cost, likely leading to late arrival at destinations. Besides, waiting hours at charging stations could make drivers uncomfortable. It is more practical to utilize dwelling time at origins and destinations to fully refuel the battery. These facts have been observed by many empirical and analytical studies such as Lin and Greene (2011); Xu et al. (2017); Chen et al. (2017); Meng et al. (2019); Quirós-Tortós et al. (2018); Quirós-Tortós et al. (2015); Wang et al. (2021); Yuan et al. (2019). Although it is more realistic, to the best of our knowledge, so far, no studies have considered drivers’ partial charging behavior in the deployment of charging stations. Assuming fully charging provides significant convenience for modeling. In particular, all possible travel paths feasible to deviation tolerance are pre-generated and then a path selection model subject to station deployment is established. Under the fully charging assumption, once a path is given, the total charging cost and travel time can be computed by tracking the change of SOC node by node, and the charging amount at the visited station is obtained by the criterion of fully charging. However, this is not the case for partial charging. Since we do not know the charging amount at each station, it is impractical to calculate the charging cost and charging time. On this occasion, the charging amount is a decision variable to be optimized and the location model cannot be developed via path pre-generation. This motivates us to devise a compact model to formulate partial charging behavior without resort to path and charging pattern generation.

Moreover, in the real world, travel demand is generally affected by some external factors, e.g., travel costs. Travelers may switch to other economic transport modes if traveling with EVs is costly (Souche 2010). Among the limited relevant studies, only a few studies have considered nonlinear demand elasticity in the context of refueling station location problem (e.g., Capar et al. (2013); Kim and Kuby (2012)). However, their model is based on path pre-generation. On this occasion, the property (i.e., linear or nonlinear) of the elastic demand function does not affect model solving and the resultant model is a linear MIP model. The reason is that since all feasible travel paths are pre-generated, the travel cost of a particular path is also known a prior. Therefore, the flows along a path are obtained by substituting the travel cost of that path to the elastic demand function. The flow volume of a certain path is essentially a parameter in this case. On the contrary, getting rid of the enumeration method, formulating travel cost and flow volume as decision variables under nonlinear relationship yields a nonlinear MIP model. How to solve the nonlinear MIP model effectively and efficiently deserves further investigation.

1.2 Objective and Contributions

To fill the above research gaps, we investigate the multi-type charging station location (MCSL) problem while considering path deviation, partial charging, and nonlinear elastic demand. We consider a generalized travel cost (GTC) comprised of travel time on the path, charging time and charging fee at the traversed stations. Drivers could take a deviation path other than the shortest path as long as the GTC of the deviation path is within a pre-specified tolerance, which is often referred to as path deviation in the literature. Additionally, instead of fully charging each time, drivers are allowed to charge as much as needed to make the GTC as small as possible. As for the nonlinear elastic demand, the flows between an OD pair are assumed to decline nonlinearly with respect to the GTC. Our goal is to maximize the covered flows of all OD pairs by determining the deployment of multi-type charging stations under a limited budget. To achieve this objective, we first formulate a mixed-integer nonlinear programming model. Instead of generating paths and charging patterns, we develop a compact formulation to model the partial charging logic. The proposed model is then approximated and reformulated by a mixed-integer linear programming model by piecewise linear approximation. To improve the computational efficiency, we employ a refined formulation using Gray code method, which effectively reduces the number of constraints and binary auxiliary variables in the formulation of the piecewise linear approximate function. The ε-optimal solutionFootnote 1 to the MCSL problem is finally obtained by solving the formulation using a state-of-the-art MIP solver.

In all, the contributions of this study are multidimensional. First, we make the first attempt to incorporate drivers’ partial charging behavior and nonlinear elastic demand in the charging station location problem. Second, instead of path and charging pattern enumeration, a compact formulation is put forward to model the partial charging logic. Last, the nonlinearity resulting from the elastic demand is addressed by piecewise linear approximation formulated using an efficient Gray code method.

The remainder of this paper is organized as follows. The related notations, assumptions, and problem descriptions are illustrated in Section 2. A mixed-integer nonlinear programming model is formulated in Section 3. Section 4 elaborates the piecewise linear approximation with a Gray code method. A case study based on the highway network of Zhejiang Province and impact analysis of the budget are presented in Section 5. Section 6 concludes the paper with recommendations for future research directions.

2 Assumptions, Notations and Problem Description

We consider an intercity road network \( \mathcal{G}=\left(N,A\right) \), where N and A are sets of nodes and directed links, respectively. The electricity consumption and travel time of link (i, j) ∈ A, i, j ∈ N are denoted by eij and dij, respectively, which are assumed to be known in advance. All OD pairs are grouped into a set W. The origin and destination of an OD pair w ∈ W are denoted by o(w) and d(w) ∈ N, respectively. Note that the traffic flows between locations A and B are often bi-directional: one is from A to B and the other is from B to A, referred to as a round trip. Generally, to enable round trips, we can use two direction-supplementary flows of an OD pair as the model input. The EVs are assumed to be homogeneous in terms of the battery capacity, denoted by E. For an OD pair w, the state-of-charge(SOC) of EVs is assumed to be no more than Eo before departing from o(w) and no less than ED after arriving at d(w), where both Eo and ED are pre-defined. Kindly note that we can set EO and ED to be any value and our model is still applicable as EO and ED are parameters. If EVs are of different types and battery capacities, from a modeling point of view, we can introduce several types of flows between an origin and a destination. A certain type of flows between a particular OD pair corresponds to a vehicle type, battery capacity, and even SOC at origins and destinations. In other words, we can augment the set of OD pairs by vehicle types, capacities, and even battery levels.

We consider locating multi-type charging stations at a set of candidate locations, denoted by I ⊆ N. The types of stations are denoted by set K and the cost of building type k ∈ K station at location i ∈ I is bi, k. The charging efficiency and charging price of different stations vary, which will be illustrated in the following subsection. The total budget for building public charging stations is represented by B. For simplicity, we assume that the charging stations are uncapacitated and there is at most one type of station at a candidate location. The “uncapacitated” herein means that an EV can be charged upon entering a station. In other words, the drivers do not need to queue for service. With this assumption, it is reasonable to define the GTC by the sum of charging cost, charging time, and travel time. Incorporating queueing process requires other sophisticated techniques such as queueing theory. Many facility location studies thus adopt “uncapacitated” assumptions for the consideration of modeling (e.g., Capar et al. (2013); Kim and Kuby (2012); Kuby and Lim (2007); Yang and Sun (2015)). Likewise, the focal point of this research is not the modeling queueing process. Therefore, we also use this assumption.

The following subsections elaborate on the partial charging logic, the generalized travel cost, and the nonlinear elastic demand. The notations used throughout this study can be found in Appendix 1.

2.1 Partial Charging Logic

To model drivers’ partial charging behavior without resorting to path and charging pattern enumeration, we need to formulate the partial charging logic explicitly. The partial charging logic refers to the locations chosen for charging and the corresponding charging amount at these stations for each OD pair. To this purpose, we define the following decision variables and auxiliary variables to specify where and how much to charge. Among these variables, we have three binary decision variables as follows: (i)yi, k, ∀ i ∈ I, k ∈ K denoting whether type k station is built at location i; (ii)\( {r}_i^w,\forall i\in I,w\in W \) indicating whether EVs are charged at location i for OD pair w; and (iii)\( {x}_{ij}^w,\forall \left(i,j\right)\in A,w\in W \) representing whether link (i, j) is traversed for OD pair w. We also have a continuous decision variable \( {p}_i^w,\forall i\in I,w\in W \) which represents the charging amount at location i for OD pair w and a continuous auxiliary variable \( {e}_i^w,\forall i\in N,w\in W \) that expresses the vehicle SOC of flows between OD pair w after charging at location i ∈ I (for i ∉ I, it represents the SOC upon arriving at location i). Given these variables, drivers’ partial charging behavior can be formulated as follows.

$$ \sum \limits_{j\in N:\left(i,j\right)\in A}{e}_{ij}{x}_{ij}^w\le {e}_i^w\le E,\kern0.5em \forall w\in W,i\in N $$
(1)
$$ {r}_i^w\le \sum \limits_{k\in K}{y}_{i,k},\kern0.5em \forall w\in W,i\in I $$
(2)
$$ {p}_i^w\le E{r}_i^w,\kern0.5em \forall w\in W,i\in I $$
(3)
$$ {e}_j^w-{p}_j^w-{e}_i^w+{e}_{ij}\left\{\begin{array}{c}\le \mathrm{M}\left(1-{x}_{ij}^w\right)\\ {}\ge \mathrm{M}\left({x}_{ij}^w-1\right)\end{array}\right.\kern2em \forall w\in W,j\in I,i\in N:\left(i,j\right)\in A $$
(4)
$$ {e}_j^w-{e}_i^w+{e}_{ij}\left\{\begin{array}{c}\le \mathrm{M}\left(1-{x}_{ij}^w\right)\\ {}\ge \mathrm{M}\left({x}_{ij}^w-1\right)\end{array}\right.\kern2em \forall w\in W,j\in N\backslash I,i\in N:\left(i,j\right)\in A $$
(5)

where M is a sufficiently large positive number.

It can be seen that Eq. (1) ensures the link feasibility. Eq. (2) suggests that drivers can only charge at the locations where charging stations are built. Eq. (3) indicates that the charging amount cannot exceed the battery capacity if any. Equation (4) establishes the SOC relationship between a candidate location and its adjacent locations. Specifically, if link (i, j) is traversed for OD pair w, i.e., \( {x}_{ij}^w=1 \), then Eq. (4) reduces to \( {e}_j^w-{p}_j^w={e}_i^w-{e}_{ij} \), where the left-hand-side(LHS) represents the SOC before charging at location j and the right-hand-side(RHS) expresses the SOC upon arriving at location j. The LHS and the RHS are equivalent in essence. As for the case of \( {x}_{ij}^w=0 \), Eq. (4) becomes redundant. Likewise, Eq. (5) works for the locations that are not candidate locations, i.e., N\I.

2.2 Generalized Travel Cost

Without loss of generality, we consider a generalized travel cost (GTC) comprised of three components, i.e., travel time on the path, charging time and charging fee at the traversed stations. Drivers are assumed to have a pre-specified value of time (VOT), denoted by ν. The cost converted from the travel time on the path for OD pair w using the VOT can be represented as follows:

$$ {d}^w=\sum \limits_{i\in N}\sum \limits_{j\in N:\left(i,j\right)\in A}\nu {d}_{ij}{x}_{ij}^w,\kern0.5em \forall w\in W $$
(6)

As for the cost resulting from charging activities, we consider both a fixed charging cost and a variable cost. Specifically, for station type k and charging amount p, the cost incurred by charging can be represented by ck + μkp, where ck is the fixed cost of charging at type k station and μk is the charging-amount-dependent cost of charging at type k station per unit amount of charging. The cost incurred by charging over the entire trip for OD pair w can be represented by charging locations, charging amount, and station type as follows:

$$ {c}^w=\sum \limits_{i\in I}\sum \limits_{k\in K}{y}_{i,k}\left({c}_k{r}_i^w+{\mu}_k{p}_i^w\right),\kern0.5em \forall w\in W $$
(7)

Based on the above descriptions, the GTC of OD pair w will become

$$ {t}^w={d}^w+{c}^w,\kern0.5em \forall w\in W $$
(8)

2.3 Path Deviation and Nonlinear Elastic Demand

The drivers of an OD pair are assumed to have a pre-specified tolerance for the path cost deviation. In other words, only the paths whose cost deviation from the GTC of the shortest path between that OD pair is within the tolerance can be chosen by the drivers. For OD pair w, let Tw denote the GTC of the shortest path in the network and let δw represent drivers’ tolerance for path cost deviation. The GTC of a feasible path cannot exceed (1 + δw)Tw. In addition, we also consider drivers’ demand elasticity by assuming that the flows between an OD pair decline nonlinearly with respect to the GTC. In the spirit of the inverse distance function proposed by Kim and Kuby (2012) to describe demand elasticity in the context of refueling station location problems, we employ an inverse cost function in this study. Specifically, the nonlinear elastic demand function for OD pair w takes the following form:

$$ {f}^w\left({t}^w\right)={F}^w{e}^{-{\theta}^w\left({t}^w-{T}^w\right)},\kern0.5em \forall w\in W,{t}^w\in \left[{T}^w,\left(1+{\delta}^w\right){T}^w\right] $$
(9)

where Fw is the flow volume when the GTC equals Tw, i.e., the maximum flow volume. If travelers need to pay more than the minimum GTC to complete trips, the flow volume will decrease. The minimum GTC is defined as below. First, we site fast-charging stations at all candidate locations. Then, we compute the GTC of each OD pair under such generous charging resources. Since the GTC cannot be further reduced by providing more charging resources, we define the resultant GTC in this setting as the minimum GTC. The parameter θw indicates the degree of drivers’ demand elasticity, and a large value of θw implies that the flow volume decreases fast as the GTC increases. Both Fw and θw can be obtained by an empirical or analytical analysis of historical data. Figure 1 illustrates the proposed nonlinear elastic demand function, in which the flow volume declines nonlinearly with respect to the GTC.

Fig. 1
figure 1

Illustration of the nonlinear elastic demand function

Full size image

In operations management (e.g., Wang et al. (2004) and Whitin (1955)) and marketing science (e.g., Noble and Gruca (1999) and Soysal and Krishnamurthi (2012)), it is prevalent to model customers’ purchasing willingness and product prices by a nonlinear function, referred to as nonlinear elastic demand. It captures the variation of customers’ demand regarding the change of costs. In the context of facility location problems, the number of travelers willing to use EVs is “demand” and the GTC is “cost”. Consequently, it is assumed that the flows between an OD pair are assumed to decline nonlinearly with respect to the GTC”. In fact, this assumption – nonlinear elastic demand – has been adopted by many studies on transportation in various problems (e.g., Cantarella (1997), Yang (1997), and Yang and Meng (1998)).

The objective of the MCSL problem is to deploy multiple types of public charging stations in an intercity road network under a limited budget so that (i) the flows between each OD pair travel on a path satisfying tw ≤ (1 + δw)Tw if any; (ii) the flow volume of an OD pair follows the nonlinear elastic demand function with respect to the GTC; and (iii) the covered flow volume of all OD pairs is maximized. Given that the objective is to maximize the covered flows, for a particular layout of charging stations, the optimality of the model implies that drivers will travel on a range-feasible path with the minimal GTC among all feasible deviation paths, which aligns with the travel behavior of drivers.

3 Optimization Model Building

3.1 Model Formulation

In view of the situation in which some OD pairs may be uncovered due to the limited budget and driving range, we introduce a binary auxiliary variable πw,  ∀ w ∈ W to represent whether OD pair w is covered. The MCSL problem can be formulated by the following model:

[OP ∙ I]:

$$ \max\ {\mathrm{Demand}}^{\mathrm{I}}=\sum \limits_{w\in W}{f}^w\left({t}^w\right){\pi}^w $$
(10)

subject to Eqs. (1)–(9) and

$$ \sum \limits_{i\in I}\sum \limits_{k\in K}{b}_{i,k}{y}_{i,k}\le B $$
(11)
$$ \sum \limits_{k\in K}{y}_{i,k}\le 1,\kern0.5em \forall i\in I $$
(12)
$$ {\sum}_{j\in N:\left(i,j\right)\in A}{x}_{ij}^w-{\sum}_{j\in N:\left(j,i\right)\in A}{x}_{ji}^w=\left\{\begin{array}{c}{\pi}^w,\kern0.5em \forall i=o(w)\\ {}0,\kern0.5em \forall i\in N\setminus \left\{o(w),d(w)\right\}\\ {}-{\pi}^w,\kern0.5em \forall i=d(w)\end{array}\right.\kern2em \forall w\in W $$
(13)
$$ {e}_{o(w)}^w\le {E}_o,\kern0.5em \forall w\in W:o(w)\notin I $$
(14)
$$ {e}_{o(w)}^w-{p}_{o(w)}^w\le {E}_o,\kern0.5em \forall w\in W:o(w)\in I $$
(15)
$$ {e}_{d(w)}^w\ge {E}_D{\pi}^w,\kern0.5em \forall w\in W $$
(16)
$$ {e}_{d(w)}^w\ge {E}_D{\pi}^w,\kern0.5em \forall w\in W $$
(17)
$$ {x}_{ij}^w,{\pi}^w\in \left\{0,1\right\},\kern0.5em \forall w\in W,i,j\in N:\left(i,j\right)\in A $$
(18)
$$ {y}_{i,k},{r}_i^w\in \left\{0,1\right\},\kern0.5em \forall w\in W,i\in I,k\in K $$
(19)
$$ {p}_i^w,{e}_j^w,{t}^w\in {\mathbb{R}}_{+},\kern0.5em \forall w\in W,i\in I,j\in N $$
(20)

where ℝ+ denotes the set of non-negative real numbers.

The objective function shown by Eq. (10) represents the total covered flow volume of all OD pairs. Constraint (11) restricts that the total cost of building charging stations cannot exceed the pre-defined budget. Constraint (12) indicates that at most one type of station will be built at a candidate location. Constraint (13) is for flow conservation. Constraints (14)–(16) require that the SOC is no more than Eo before departure and no less than ED after arrival. Note that if the origin of an OD pair is a candidate location, i.e., o(w) ∈ I, the SOC may be replenished by the amount of \( {p}_{o(w)}^w \) as shown in Constraint (15). Constraint (17) indicates drivers’ tolerance for path cost deviation. Constraints (18)–(20) specify the domains of decision variables \( {x}_{ij}^w \), yi, k,\( {r}_i^w \), \( {p}_i^w \) and auxiliary variables πw, \( {e}_i^w \), tw.

3.2 Model Properties

The proposed formulation for drivers’ partial charging behavior explicitly models the charging location choices and charging amount without resorting to path and charging pattern enumeration. Furthermore, it is linear and has a polynomial number of constraints. Specifically, the number of constraints in the formulation is fixed given a network. It overcomes the prohibitively large memory consumption as reported by Kim and Kuby (2012), which resulted from the exponential growth of constraints with respect to drivers’ tolerance and EV driving range.

The model [OP ∙ I] is nonlinear due to the nonlinear objective function and the bilinear terms in Eq. (7). Fortunately, the bilinear terms can be easily linearized by introducing two kinds of continuous proxy variables (\( {c}_{w,i,k}^1={\mu}_k{p}_i^w{y}_{i,k} \) and \( {c}_{w,i,k}^2={c}_k{r}_i^w{y}_{i,k},\kern0.5em \forall w\in W,i\in I,k\in K\Big) \)and imposing the following linear constraints:

$$ {c}^w=\sum \limits_{i\in I}\sum \limits_{k\in K}{c}_{w,i,k}^1+{c}_{w,i,k}^2,\kern0.5em \forall w\in W $$
(21)
$$ \left\{\begin{array}{c}{c}_{w,i,k}^1\ge 0\\ {}\ {c}_{w,i,k}^1\le {\mu}_kE{y}_{i,k}\\ {}\ {c}_{w,i,k}^1\ge {\mu}_k{p}_i^w+{\mu}_kE\left({y}_{i,k}-1\right)\\ {}\ {c}_{w,i,k}^1\le {\mu}_k{p}_i^w\end{array}\right.\kern2em \forall w\in W,i\in I,k\in K $$
(22)
$$ \left\{\begin{array}{c}\ {c}_{w,i,k}^2\ge 0\\ {}\ {c}_{w,i,k}^2\le {c}_k{y}_{i,k}\\ {}\ {c}_{w,i,k}^2\ge {c}_k\left({r}_i^w+{y}_{i,k}-1\right)\\ {}\ {c}_{w,i,k}^2\le {c}_k{r}_i^w\end{array}\right.\kern1.75em \forall w\in W,i\in I,k\in K $$
(23)

We shall then show that the approximation of the bilinear terms is also exact at the boundaries. The term \( {c}_{w,i,k}^1={\mu}_k{p}_i^w{y}_{i,k} \) contains a continuous variable \( {p}_i^w \) and a binary variable yi, k. If yi, k = 0, then \( {c}_{w,i,k}^1=0 \). In this case, Eq. (22) becomes

$$ \left\{\begin{array}{c}\ {c}_{w,i,k}^1\ge 0\\ {}\ {c}_{w,i,k}^1\le 0\\ {}\ {c}_{w,i,k}^1\ge {\mu}_k{p}_i^w-{\mu}_kE\\ {}\ {c}_{w,i,k}^1\le {\mu}_k{p}_i^w\end{array}\right. $$

which indicates \( {c}_{w,i,k}^1=0 \). If yi, k = 1, then \( {c}_{w,i,k}^1={\mu}_k{p}_i^w \). On this occasion, Eq. (22) is

$$ \left\{\begin{array}{c}\ {c}_{w,i,k}^1\ge 0\\ {}\ {c}_{w,i,k}^1\le {\mu}_kE\\ {}\ {c}_{w,i,k}^1\ge {\mu}_k{p}_i^w\\ {}\ {c}_{w,i,k}^1\le {\mu}_k{p}_i^w\end{array}\right. $$

which implies that \( {c}_{w,i,k}^1={\mu}_k{p}_i^w \). Clearly, Eq. (22) is identical to \( {c}_{w,i,k}^1={\mu}_k{p}_i^w{y}_{i,k} \). With a similar approach, we can prove Eq. (23) is equivalent to \( {c}_{w,i,k}^2={c}_k{r}_i^w{y}_{i,k} \). Particularly, when yi, k = 0, we have

$$ \left\{\begin{array}{c}{c}_{w,i,k}^2\ge 0\\ {}\ {c}_{w,i,k}^2\le 0\\ {}\ {c}_{w,i,k}^2\ge {c}_k\left({r}_i^w-1\right)\\ {}\ {c}_{w,i,k}^2\le {c}_k{r}_i^w\end{array}\right. $$

suggesting \( {c}_{w,i,k}^2=0 \); when yi, k = 1, we have

$$ \left\{\begin{array}{c}\ {c}_{w,i,k}^2\ge 0\\ {}\ {c}_{w,i,k}^2\le {c}_k\\ {}\ {c}_{w,i,k}^2\ge {c}_k{r}_i^w\\ {}\ {c}_{w,i,k}^2\le {c}_k{r}_i^w\end{array}\right. $$

which means \( {c}_{w,i,k}^2={c}_k{r}_i^w \).

As for the nonlinear objective function, we will employ a piecewise linear approximation method to address its nonlinearity, which will be elaborated in the next section.

4 Solution Approach

In this section, we employ a piecewise linear approximation method to address the nonlinearity in the objective function of the model [OP ∙ I]. A Gray code method is employed to establish the approximation function. Compared with the traditional piecewise linear formulation to approximate nonlinear function, the Gray code method uses significantly fewer binary auxiliary variables and constraints, thereby improving computational efficiency.

4.1 Piecewise Linear Approximation

Piecewise linear approximation is a classic solution approach to nonlinear optimization problems, which has been applied in many transportation problems (Daganzo and Laval 2005; Ekström et al. 2012; Farhi 2012; Przybyla et al. 2015). In particular, a univariate continuous function can be approximated by a piecewise linear function with the approximation error being controlled by the number of linear segments (Wolsey and Nemhauser 1999). For instance, we consider the nonlinear elastic demand function for OD pair w, i.e., fw(tw), tw ∈ [Tw, (1 + δw)Tw], which is to be approximated by a piecewise linear function \( {\overset{\acute{\mkern6mu}}{f}}^w\left({t}^w\right) \) as shown in Fig. 2. To this end, we need to first generate V(w) breakpoints, denoted by \( {t}_n^w,\kern0.5em n=1,\dots, V(w) \), based on the required solution quality to specify the piecewise linear function \( {\overset{\acute{\mkern6mu}}{f}}^w\left({t}^w\right) \) (see Subsection 4.2). The flow volumes corresponding to each breakpoint are \( {f}^w\left({t}_n^w\right),\kern0.5em n=1,\dots, V(w) \). Then it follows that any tw ∈ [Tw, (1 + δw)Tw] can be represented by

$$ {t}^w={\sum}_{n=1}^{V(w)}{\lambda}_n^w{t}_n^w $$
(24)
$$ {\sum}_{n=1}^{V(w)}{\lambda}_n^w=1 $$
(25)
$$ {\lambda}_n^w\in {\mathbb{R}}_{+},\kern0.5em n=1,\dots, V(w) $$
(26)
Fig. 2
figure 2

Illustration of the piecewise linear approximate function

Full size image

Notice that in Eqs. (24)–(26) the values of \( {\lambda}_n^w \) are not unique. However, if we have \( {t}^w\in \left[{t}_n^w,{t}_{n+1}^w\right] \) and \( {\lambda}_n^w \) such that \( {t}^w={\lambda}_n^w{t}_n^w+{\lambda}_{n+1}^w{t}_{n+1}^w \) and \( {\lambda}_n^w+{\lambda}_{n+1}^w=1 \), then it follows that \( {\overset{\acute{\mkern6mu}}{f}}^w\left({t}^w\right)={\lambda}_n^w{f}^w\left({t}_n^w\right)+{\lambda}_{n+1}^w{f}^w\left({t}_{n+1}^w\right) \). In other words,

$$ {\overset{\acute{\mkern6mu}}{f}}^w\left({t}^w\right)={\sum}_{n=1}^{V(w)}{\lambda}_n^w{f}^w\left({t}_n^w\right) $$
(27)

if at most two of \( {\lambda}_n^w \) are positive and if two of \( {\lambda}_n^w \) are positive, they must be adjacent. This condition is referred to as SOS2 condition in the literature. The SOS2 condition is often formulated by introducing the binary auxiliary variables ξn, n = 1, …, V(w) − 1 (where ξn equals 1 if \( {t}^w\in \left[{t}_n^w,{t}_{n+1}^w\right] \) and 0 otherwise) as shown in Fig. 2 and imposing the following constraints:

$$ {\lambda}_1^w\le {\xi}_1 $$
(28)
$$ {\lambda}_n^w\le {\xi}_{n-1}+{\xi}_n,\kern0.5em n=2,\dots, V(w)-1 $$
(29)
$$ {\lambda}_{V(w)}^w\le {\xi}_{V(w)-1} $$
(30)
$$ {\sum}_{n=1}^{V(w)-1}{\xi}_n=1 $$
(31)
$$ {\xi}_n\in \left\{0,1\right\},\kern0.5em n=1,\dots, V(w)-1 $$
(32)

Although the piecewise linear approximation is easy to apply to various nonlinear problems, its low computational efficiency is widely criticized due to introducing too many additional binary auxiliary variables and constraints in the formulation of SOS2 condition. Specifically, if we use V(w) breakpoints to specify a piecewise linear approximate function, then V(w) − 1 binary auxiliary variables and V(w) + 1 constraints are required to formulate SOS2 condition. Many studies have been conducted to find more efficient reformulation of SOS2 condition, among which the Gray code method is very promising. The Gray-code method was developed by Vielma and Nemhauser (2011). It approximates nonlinear functions with significantly fewer auxiliary binary variables and constraints in comparison with the classic formulation of piecewise linear approximation. In fact, their reformulation of SOS2 condition using Gray code method requires only ⌈log2(V(w) − 1)⌉ binary auxiliary variables and 2⌈log2(V(w) − 1)⌉ linear constraints. Thus, we will employ the Gray code method to address the nonlinearity of the objective function.

To reformulate SOS2 condition by Gray code method, we need to introduce a type of special parameters, i.e., Gray code. It is a class of specially ordered multi-digit vectors with binary elements such that any two adjacent Gray codes differ in only one digit. Figure 3 illustrates Gray codes with a different number of digits, e.g., 4 two-digit Gray codes and 16 four-digit Gray codes. It can be seen that any adjacent Gray codes, e.g., the eighth four-digit Gray code {0, 1, 0, 0}. and the ninth four-digit Gray code {1, 1, 0, 0}, only differ in one digit.

Fig. 3
figure 3

Example of Gray codes

Full size image

To apply the Gray code method, the feasible path cost range of OD pair w, i.e., [Tw, (1 + δw)Tw], is first partitioned into V(w) − 1 intervals by V(w) pre-generated breakpoints. Each interval is then labeled by a Gray code in sequence. Therefore, we need a total of V(w) − 1 Gray codes. To have such number of Gray codes, we need to generate these Gray codes with at least ⌈log2(V(w) − 1)⌉ digits. Let Gn, n = 1, …, V(w) − 1 denote the sequential Gray codes with ⌈log2(V(w) − 1)⌉ digits that we generated. For the nth interval, which is specified by the breakpoints \( {t}_n^w \) and \( {t}_{n+1}^w \), this interval is labeled by the Gray code Gn as shown in Fig. 2.

To reformulate SOS2 condition using the Gray code method, we need to further introduce a binary auxiliary variable \( {\xi}_z^w \) and two sets H+(z, w) and H−(z, w) for each OD pair and each digit, i.e., ∀w ∈ W, z = 1, …, ⌈log2(V(w) − 1)⌉, which are defined as follows:

$$ {\displaystyle \begin{array}{c}{H}^{+}\left(z,w\right)=\left\{n=1,\dots, V(w)|\begin{array}{c}\left(n=1\wedge {G}_{2,z}^w=1\right)\cup \left({G}_{n-1,z}^w=1\wedge {G}_{n,z}^w=1\right)\\ {}\cup \left(n=V(w)\wedge {G}_{V(w)-1,z}^w=1\right)\end{array}\right\},\\ {}\forall w\in W,z=1,\dots, \left\lceil {\log}_2\left(V(w)-1\right)\right\rceil \end{array}} $$
(33)
$$ {\displaystyle \begin{array}{c}{H}^{-}\left(z,w\right)=\left\{n=1,\dots, V(w)|\begin{array}{c}\left(n=1\wedge {G}_{2,z}^w=0\right)\cup \left({G}_{n-1,z}^w=0\wedge {G}_{n,z}^w=0\right)\\ {}\cup \left(n=V(w)\wedge {G}_{V(w)-1,z}^w=0\right)\end{array}\right\}\\ {}\forall w\in W,z=1,\dots, \left\lceil {\log}_2\left(V(w)-1\right)\right\rceil \end{array}} $$
(34)

where \( {G}_{n,z}^w \) denotes the value of the zth digit of the nth Gray code for OD pair w. Then SOS2 condition can be enforced by the following inequalities:

$$ \sum \limits_{n\in {H}^{+}\left(z,w\right)}{\lambda}_n^w\le {\xi}_z^w,\kern0.5em \forall w\in W,z=1,\dots, \left\lceil {\log}_2\left(V(w)-1\right)\right\rceil $$
(35)
$$ \sum \limits_{n\in {\mathrm{H}}^{-}\left(z,w\right)}{\lambda}_n^w\le 1-{\xi}_z^w,\kern0.5em \forall w\in W,z=1,\dots, \left\lceil {\log}_2\left(V(w)-1\right)\right\rceil $$
(36)
$$ {\xi}_z^w\in \left\{0,1\right\},\kern0.5em \forall w\in W,z=1,\dots, \left\lceil {\log}_2\left(V(w)-1\right)\right\rceil $$
(37)

Hereafter, we use a sample example to illustrate the Gray code method. Suppose we use 10 pre-generated breakpoints to specify a piecewise linear approximate function, the feasible path cost range is first partitioned into 9 intervals and each interval is then labeled by a Gray code. Therefore, we need at least 4 digits for these 9 Gray codes. The generation of Gray code is a recursive procedure. To generate the four-digit Gray codes, we need to first generate all three-digit Gray codes. Specifically, given the two-digit Gray codes {0, 0}, {0, 1}, {1, 1}, and {1, 0} as shown in Fig. 3, the first 4 three-digit Gray codes can be obtained by adding “0” to the heads of {0, 0}, {0, 1}, {1, 1}, and {1, 0}, i.e., {0, 0, 0}, {0, 0, 1}, {0, 1, 1}, and {0, 1, 0}. By rearranging the two-digit Gray codes in inverse order, we get {1, 0}, {1, 1}, {0, 1}, and {0, 0}. The last 4 three-digit Gray codes can be obtained by adding “1” to the heads of {1, 0}, {1, 1}, {0, 1}, and {0, 0}, i.e., {1, 1, 0}, {1, 1, 1}, {1, 0, 1}, and {1, 0, 0}. Since we use four-digit Gray codes to label the intervals, 4 binary auxiliary variables are required. According to Eqs. (33) and (34), we have H+(1) = {10}, H−(1) = {1, 2, 3, 4, 5, 6, 7, 8}, H+(2) = {6, 7, 8, 9, 10}, H−(2) = {1, 2, 3, 4}, H+(3) = {4, 5, 6}, H−(4) = {1, 2, 8, 9, 10}, H+(4) = {3, 7}, and H−(4) = {1, 5, 9, 10}. In this case, Constraints (35) and (36) can be represented by:

$$ \left\{\begin{array}{c}\ {\lambda}_{10}\le {\xi}_1\\ {}\ {\lambda}_1+{\lambda}_2+{\lambda}_3+{\lambda}_4+{\lambda}_5+{\lambda}_6+{\lambda}_7+{\lambda}_8\le 1-{\xi}_1\\ {}\ {\lambda}_6+{\lambda}_7+{\lambda}_8+{\lambda}_9+{\lambda}_{10}\le {\xi}_2\\ {}\ {\lambda}_1+{\lambda}_2+{\lambda}_3+{\lambda}_4\le 1-{\xi}_2\\ {}\ {\lambda}_4+{\lambda}_5+{\lambda}_6\le {\xi}_3\\ {}\ {\lambda}_1+{\lambda}_2+{\lambda}_8+{\lambda}_9+{\lambda}_{10}\le 1-{\xi}_3\\ {}\ {\lambda}_3+{\lambda}_7\le {\xi}_4\\ {}\ {\lambda}_1+{\lambda}_5+{\lambda}_9+{\lambda}_{10}\le 1-{\xi}_4\end{array}\right. $$
(38)

Based on the above discussions, the model [OP ∙ I] can be approximated and reformulated by the piecewise linear approximation using the reformulation of SOS2 condition as follows:

[OP ∙ II]:

$$ \max {\mathrm{Demand}}^{\mathrm{II}}=\sum \limits_{w\in W}{\overset{\acute{\mkern6mu}}{f}}^w $$
(39)

subject to Eqs. (1)–(6), (8), (9), (11)–(23), (33)–(36), and

$$ {\overset{\acute{\mkern6mu}}{f}}^w={\sum}_{n=1}^{V(w)}{\lambda}_n^w{f}^w\left({t}_n^w\right),\kern0.5em \forall w\in W $$
(40)
$$ {t}^w={\sum}_{n=1}^{V(w)}{\lambda}_n^w{t}_n^w,\kern0.5em \forall w\in W $$
(41)
$$ {\sum}_{n=1}^{V(w)}{\lambda}_n^w\le {\pi}^w,\kern0.5em \forall w\in W $$
(42)
$$ {\lambda}_n^w\in {\mathbb{R}}_{+},{\xi}_z^w\in \left\{0,1\right\},\kern0.5em \forall w\in W,n=1,\dots, V(w),z=1,\dots, \left\lceil {\log}_2\left(V(w)-1\right)\right\rceil $$
(43)

The objective function shown by Eq. (39) represents the approximate covered flow volume of all OD pairs. Constraints (40)–(42) follow the traditional formulation of the piecewise linear approximation except that the sum of \( {\lambda}_n^w \) is upper bounded by πw as shown in Eq. (42). The domains of variables \( {\lambda}_n^w \) and \( {\xi}_z^w \) are defined by Constraint (43).

It can be seen that the model [OP ∙ II] is a mixed-integer linear programming model and therefore, can be readily solved by state-of-the-art MIP solvers like CPLEX. In the following subsection, we will elaborate on how to generate the breakpoints based on the required solution quality.

4.2 Breakpoint Generation

In the aforementioned approximation method, a piecewise linear curve overestimating the covered flow volume is generated for each OD pair. In theory, with sufficiently many breakpoints, the approximate curve will be very close to the objective function curve and the error can be controlled as small as possible. However, this will result in more linear segments and more variables in the expression of SOS2 condition, and in turn an over enlarged model that is computationally intensive. To balance the computational efficiency and solution quality, in this subsection, we illustrate how to generate a reasonably sized set of breakpoints to obtain the ε-optimal solution to the problem.

The idea that underlies the generation of a reasonably sized set of breakpoints is the solution quality of the model [OP ∙ II] can be calibrated by controlling the approximation error of each piecewise linear approximate function \( {\overset{\acute{\mkern6mu}}{f}}^w\left({t}^w\right),w\in W \), which can be summarized by the following proposition:

Proposition 1

Let \( {\mathrm{Demand}}^{{\mathrm{I}}^{\ast }} \) and \( {\mathrm{Demand}}^{{\mathrm{II}}^{\ast }} \) denote the optimal objective values of the models [OP ∙ I] and [OP ∙ II], respectively. Given a pre-defined positive tolerance ε, the ε-optimal solution to the model [OP ∙ I] can be obtained by solving the model [OP ∙ II], i.e.,

$$ {\mathrm{Demand}}^{{\mathrm{I}}^{\ast }}\le {\mathrm{Demand}}^{{\mathrm{I}\mathrm{I}}^{\ast }}\le {\mathrm{Demand}}^{{\mathrm{I}}^{\ast }}+\upvarepsilon $$
(44)

if the generated breakpoints satisfy

$$ {\varepsilon}_n^w\le \frac{\upvarepsilon}{\left|W\right|},\kern0.5em \forall w\in W,n=1,\dots, V(w)-1 $$
(45)

where \( {\varepsilon}_n^w \) represents the approximation error in the interval \( \left[{t}_n^w,{t}_{n+1}^w\right] \) for OD pair w.

The first inequality suggests the lower bound and the upper bound on the optimal objective. In particular, it is no smaller than the optimal objective value and meanwhile is no bigger than a pre-specified error plus the optimal objective. For the lower bound, as shown in Fig. 2, it is trivial to find that the piecewise linear approximate function is above the nonlinear curve except at breakpoints. Regarding the upper bound, we note that the total approximation error is the sum of errors on all elastic demand functions. The second inequality limits the approximation error on each elastic demand function within a given threshold. Hence, once Eq. (45) holds, we can conclude that the total approximation error is also bounded by a given threshold. We then formally prove Proposition 1 as below.

Proof

Let \( \overline{W} \) denote the set of covered OD pairs. Without loss of generality, we assume that for an OD pair \( w\in \overline{W} \) its real GTC tw falls into the interval specified by the breakpoints \( {t}_{n^{\ast}}^w \) and \( {t}_{n^{\ast }+1}^w \), i.e., \( {t}^w\in \left[{t}_{n^{\ast}}^w,{t}_{n^{\ast }+1}^w\right] \). Then we have

$$ {\displaystyle \begin{array}{c}{\mathrm{Demand}}^{{\mathrm{I}}^{\ast }}=\sum \limits_{w\in \overline{W}}{f}^w\left({t}^w\right)\le \sum \limits_{w\in \overline{W}}{\overset{\acute{\mkern6mu}}{f}}^w\left({t}^w\right)\kern0.5em ={\mathrm{Demand}}^{{\mathrm{I}\mathrm{I}}^{\ast }}\\ {}=\sum \limits_{w\in \overline{W}}\left({f}^w\left({t}^w\right)+{\varepsilon}_{n^{\ast}}^w\right)\le \sum \limits_{w\in \overline{W}}\left({f}^w\left({t}^w\right)+\frac{\upvarepsilon}{\left|W\right|}\right)\\ {}={\mathrm{Demand}}^{{\mathrm{I}}^{\ast }}+\frac{\left|\overline{W}\right|}{\left|W\right|}\upvarepsilon \le {\mathrm{Demand}}^{{\mathrm{I}}^{\ast }}+\upvarepsilon \end{array}} $$
(46)

This concludes the proof. □.

To generate a certain number of breakpoints that satisfy Condition (45) we will employ an iterative procedure to search for new breakpoints one by one. Let \( {\mathcal{S}}^w \) denote the set of breakpoints for OD pair w. First, we initialize \( {\mathcal{S}}^w \) by adding the endpoints of the feasible path cost range, i.e., Tw and (1 + δw)Tw, into it. Then, we search the interval that is specified by two adjacent breakpoints for a new breakpoint, which is associated with the maximum approximation error in the interval. Specifically, given interval \( \left[{t}_n^w,{t}_{n+1}^w\right] \), the maximum error in this interval can be obtained by solving the following problem:

$$ \underset{t_n^w\le {t}^w\le {t}_{n+1}^w}{\max }{\overset{\acute{\mkern6mu}}{f}}^w\left({t}^w\right)-{F}^w{e}^{-{\theta}^w\left({t}^w-{T}^w\right)} $$
(47)

It is easy to find that the target breakpoint is

$$ {\hat{t}}_n^w={T}^w-\frac{1}{\theta^w}\ln \frac{-{\varpi}_n^w}{F^w{\theta}^w} $$
(48)

and the maximum approximation error in the interval is

$$ {\hat{\varepsilon}}_n^w=\left({\varpi}_n^w{\hat{t}}_n^w+{\sigma}_n^w\right)-{F}^w{e}^{-{\theta}^w\left({\hat{t}}_n^w-{T}^w\right)} $$
(49)

where \( {\varpi}_n^w \) and \( {\sigma}_n^w \) denote the slope and intercept of the linear function of \( {\overset{\acute{\mkern6mu}}{f}}^w\left({t}^w\right) \) in interval \( \left[{t}_n^w,{t}_{n+1}^w\right] \). If \( {\hat{\varepsilon}}_n^w\le \upvarepsilon /\left|W\right| \), this interval is labeled as qualified and will not be examined anymore; otherwise, the point \( {\hat{t}}_n^w \) will be added into the set \( {\mathcal{S}}^w \) and the interval is then divided into two parts by \( {\hat{t}}_n^w \), i.e., \( \left[{t}_n^w,{\hat{t}}_n^w\right] \) and \( \left[{\hat{t}}_n^w,{t}_{n+1}^w\right] \), both of which will be examined in a similar way next. The above procedure iteratively examines all existing intervals until no new breakpoints can be found. The pseudo-code of the breakpoint generation is outlined as follows:

figure a

5 Case Study

In this section, a case study based on the highway network of Zhejiang Province of China is conducted to examine the applicability of the proposed model and solution approach. The impact analysis of the budget on flow coverage and optimal station selections is also performed. The model is coded in MATLAB 2019a calling IBM ILOG CPLEX 12.9 on a personal desktop with Intel Core i7 4.0 GHz CPU.

5.1 Highway Network of Zhejiang Province and Parameter Settings

As reported by XinhuaNet (2018), the State Power Grid of China plans to invest RMB ¥1.1 billion in building public charging facilities in Zhejiang Province by the end of 2020. The proposed MCSL problem is expected to provide some practical insights into deploying public charging stations for the investor. The highway network of Zhejiang Province can be represented by a graph consisting of 34 nodes and 96 directed links as shown in Fig. 4. The parameters of EVs are based on BYD-EV6, which is popular with the Chinese market. Specifically, the EV battery capacity is 60kWh and the electricity consumption rate is 0.2kWh/km (BYD 2018). According to the electricity consumption rate, the speed of 120 km/h, and link distances, we can obtain the electricity consumption and travel time of each link. Following the convention in the literature, the initial/final SOC before/after departure/arrival is set to be no bigger/smaller than half of the battery capacity, i.e., 30kWh. The reason for assuming the initial/final SOC no bigger/smaller than 50% of battery capacity is that this SOC setting enables round trips. In particular, the drivers can travel from the destination to the origin along the same route of the inbound trip if the aforesaid SOC condition is fulfilled. Many previous studies also adopted this SOC setting to conduct numerical experiments, e.g., Kim and Kuby (2012), Kuby and Lim (2005, 2007), and Lim and Kuby (2010).

Fig. 4
figure 4

Highway network of Zhejiang Province of China

Full size image

All 34 nodes in the network are candidate locations for building charging stations. The construction cost of a slow−/fast- charging station is set to be one/two unit cost for simplicity. The drivers’ value of time is assumed to be $10/h. For slow−/fast- charging stations, the charging-amount-dependent cost and the fixed charging cost are $0.5/kWh/$1.8/kWh and $1/$1, respectively The largest 20 cities (more than one million people) of Zhejiang Province are chosen as origins and destinations for generating OD pairs and then 190 OD pairs are obtained. The flow volume of each OD pair is obtained in the gravity model (Hodgson 1990) with the city population. To reduce trivial and unrealistic cases, we exclude the cases of few flows and less electricity consumption (no more than 30kWh). Finally, we remain 50 OD pairs with 23,497 flows, which account for 88.7% of total flows. As for the degree of drivers’ demand elasticity θw, it is obtained by assuming the flow volume declines from Fw to 0.2Fwas the GTC rises from Tw to 1.5Tw.

The approximation error in the piecewise linear approximation using the Gray code method is set to be 50, i.e., less than one for each OD pair. Based on this error tolerance, the required numbers of breakpoints, Gray codes, digits of Gray codes, continuous auxiliary variables, binary auxiliary variables, and linear constraints are shown by Columns 2–7 of Appendix 2. The numbers of saved binary auxiliary variables and constraints are presented by Columns 8 and 9 of Appendix 2. To analyze the impact of budget on covered flows of all OD pairs, we set the budget to be {2, 4, 6, 8, …, 28}. To further investigate the influence of drivers’ tolerance for path cost deviation, the tolerance is set to be {0, 20%, 50%}. The computational time limit (elapsed time) of each instance is set to be 24 h. The experimental results of the 42 instances are displayed in Appendix 3.

5.2 Impact Analysis of Budget on Flow Coverage and Covered OD Pairs

Figures 5 and 6 present the flow coverage and the number of covered OD pairs under three tolerances as the budget varying from 2 to 28 unit cost. When the tolerance equals zero, drivers will travel on the shortest path in the network. When the tolerance becomes 20% and 50%, drivers could take a deviation path as long as the path cost deviation is within the tolerance. It can be seen that in Fig. 5 the flow coverage follows an upward trend and has a near-concave shape, suggesting that the increment rate of flow coverage decreases gradually, i.e., the marginal benefit of investment is declining. In addition, given the same budget available, the flow coverage under a high tolerance is usually bigger than that under a low tolerance. For example, given 10 unit cost, the flow coverage under zero tolerance is only 49.03%, while these numbers under 20% and 50% tolerances are 55.83% and 60.99%, respectively. From another point of view, the planner needs less investment to attain the same flow coverage if drivers accept a higher path cost deviation. For instance, if the target flow coverage is 60%, only 10 unit cost is required under 50% tolerance while 12 unit cost is required under zero tolerance. As for the number of covered OD pairs, it also embraces an upward trend but displays fluctuation. It can be seen that in Fig. 6 the fluctuation is especially obvious under 50% tolerance. Like the relationship of flow coverage under different tolerances, the number of covered OD pairs under a high tolerance is usually bigger than that under a low tolerance. Based on the above analysis, we can get some practical insights, i.e., a good understanding of drivers’ tolerance for path cost deviation contributes to saving the budget or satisfying more charging demands.

Fig. 5
figure 5

Flow coverage

Full size image
Fig. 6
figure 6

Covered OD pairs

Full size image

5.3 Impact Analysis of Budget on Optimal Station Selection

The number of slow−/fast- charging stations as the budget rises from 2 to 28 unit cost under three tolerances is displayed by Figs. 7, 8, and 9. The number of fast-charging stations increases with respect to the budget and tends to be stable after the budget exceeds 16 unit cost. By contrast, the number of slow-charging stations fluctuates as the budget varies from 2 to 16 unit cost and then rises almost linearly after the budget goes beyond 16 unit cost. Moreover, under three tolerances, the numbers of two types of stations go across several times, yielding many intersection points. For instance, under 20% tolerance as shown in Fig. 8, there are 3 intersection points, i.e., 6, 9, and 18 unit cost. The planner needs to locate more slow-charging stations if the budget is smaller than 9 unit cost or bigger than 18 unit cost; otherwise, more fast-charging stations should be built. In practice, the planner may prefer to build more slow-charging stations since fast-charging stations generally call for more maintenance and operation costs. Fortunately, the above results suggest that even if they need to cover all flows, only 7 fast-charging stations are required.

Fig. 7
figure 7

No. of stations under zero tolerance

Full size image
Fig. 8
figure 8

No. of stations under 20% tolerance

Full size image
Fig. 9
figure 9

No. of stations under 50% tolerance

Full size image

5.4 Impact Analysis of Driving Ranges on Flow Coverage and Station Deployment

In this section, we aim to investigate how the driving range (also battery capacity) of EVs affects the covered flow volume as well as the deployment of sited charging stations. To this end, we let the driving ranges of EVs be three values, namely 300 km, 400 km, and 500 km. The drivers’ tolerance for travel cost deviation is assumed to be 0.5% of their minimum GTC and we then vary the total budget from 2 unit cost to 28 unit cost (increasing 2 unit cost sequentially). To vividly showcase the impact of driving ranges on flow coverage, we visualize the experimental results under the three given ranges on the same figure as follows (P.S.: FC_D300 denotes the curve of flow coverage under the driving range of 300 km) (Figs. 10, 11, and 12).

Fig. 10
figure 10

Variations of flow coverage under three driving ranges as the growth of budget

Full size image
Fig. 11
figure 11

Station deployment under range 300 km

Full size image
Fig. 12
figure 12

Station deployment under range 400 km

Full size image

Basically, the three curves perform a near-concave shape as the available budget increases. In particular, they all first rise stably and then tend to be a constant, i.e., 100% of flow coverage. The interesting point is that the flow coverage under a higher driving range attains 100% of flow coverage more early, that is, all travelers’ charging demand is fulfilled with a smaller investment. This fact aligns with our expectation that with a longer driving range, there is no need for governments to build too many charging facilities as EVs can cruise a long distance without being replenished en route. This observation also provides valuable insights for governments into promoting green transportation. Advancing battery technologies not only boosts the development and adoption of EVs but also saves investment in building charging facilities, which is green for the environment and economy. We also present the charging station distributions under driving ranges of 300 km and 400 km and 14 unit budget below to see how stations are sited under different driving ranges.

The blue circles denote fast-charging stations; the green circles represent slow-charging stations; the black circles imply no charging stations at that node. Under the driving range of 300 km, we site five fast-charging stations at locations 1, 2, 3, 4, 5, and four slow-charging stations at locations 6, 8, 9, 23, while under the driving range of 400 km, we have four fast-charging stations located at 1, 2, 3, 22, and five slow-charging stations located at 4, 5, 6, 8, 9, 23. All locations that fast-charging stations locate are big cities of Zhejiang Province. For example, locations 1, 2, 3, 4, 5 are the biggest five cities of Zhejiang, and locations 6, 8, 9, 23 are also med-size cities. This observation coincides with our experience that fast-charging stations are generally sited in big cities. Interestingly, when a larger driving range is accessible, we only have four fast-charging stations and use the saved budget to build two additional slow-charging stations. This could attribute to that when EVs can cruise a longer distance, drivers do not need to refuel energy multiple times and slow-charging stations are also welcome for them. This is an encouraging finding since slow-charging stations have less burden on the electricity grid and incur fewer operational costs in the long run. This finding also motivates the governments to explore more cutting-edge battery technologies.

6 Conclusions

In this study, we aim to optimally locate multi-type charging stations, e.g., fast-charging stations and slow-charging stations, for maximizing the covered flows while taking into account path deviation, partial charging, and nonlinear elastic demand. This problem is first formulated as a mixed-integer nonlinear programming model and then reformulated as a mixed-integer linear programming model by the piecewise linear approximation. In addition, a compact formulation is put forward to model the partial charging logic instead of generating paths and charging patterns. To improve the computational efficiency, we employ a refined formulation of SOS2 condition using Gray code method, which effectively reduces the number of constraints and binary auxiliary variables in the formulation of the piecewise linear approximate function. A breakpoint generation scheme is finally proposed according to the requirement of solution quality. Finally, the applicability of the proposed model and the impact of the budget on flow coverage and optimal station selections are examined based on the highway network of Zhejiang Province of China.

Future studies may be undertaken in several directions. First, the efficiency of the proposed model depends on the network size and the number of OD pairs. It is thus necessary to develop an efficient algorithm applicable to large networks. For instance, as pointed out by Vielma and Nemhauser (2011), a branch-and-cut algorithm could be developed in which the Eqs. (35) and (36) play the role of valid inequalities. Second, drivers may need to wait for charging due to limited charging spots. A queueing model can be useful to incorporate waiting costs into the present model. Last, the fear of batteries running out of power en-route, namely range anxiety, will affect drivers’ charging and routing behaviors. Hence, it is worthwhile to investigate the impact of range anxiety in the future.