Networks
Volume 84, Issue 2 pp. 109-131
SPECIAL ISSUE ARTICLE
Open Access

Maximum flow-based formulation for the optimal location of electric vehicle charging stations

Pierre-Luc Parent, 

Pierre-Luc Parent

CIRRELT and Département d'informatique et de recherche opérationnelle, Université de Montréal, Montréal, Canada

Search for more papers by this author
Margarida Carvalho, 

Margarida Carvalho

CIRRELT and Département d'informatique et de recherche opérationnelle, Université de Montréal, Montréal, Canada

Search for more papers by this author
Miguel F. Anjos, 

Corresponding Author

Miguel F. Anjos

GERAD and School of Mathematics, University of Edinburgh, Edinburgh, UK

Correspondence

Miguel F. Anjos, GERAD and School of Mathematics, University of Edinburgh, Edinburgh, UK.

Email: [email protected]

Search for more papers by this author
Ribal Atallah, 

Ribal Atallah

Institut de Recherche d'Hydro-Québec, Hydro-Québec, Varennes, Canada

Search for more papers by this author
First published: 11 April 2024
https://doi.org/10.1002/net.22219
Citations: 3

Abstract

With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EVs) are one way to diminish these effects, but their widespread adoption is often limited by the insufficient availability of charging stations. In this work, our goal is to expand the infrastructure of EV charging stations, in order to provide a better quality of service in terms of user satisfaction (and availability of charging stations). Specifically, our focus is directed towards urban areas. We first propose a model for the assignment of EV charging demand to stations, framing it as a maximum flow problem. This model is the basis for the evaluation of user satisfaction with a given charging infrastructure. Secondly, we incorporate the maximum flow model into a mixed-integer linear program, where decisions on the opening of new stations and on the expansion of their capacity through additional outlets is accounted for. We showcase our methodology for the city of Montreal, demonstrating the scalability of our approach to handle real-world scenarios. We conclude that considering both spacial and temporal variations in charging demand is meaningful when solving realistic instances.

1 INTRODUCTION

Transportation accounts for 28% of greenhouse gas (GHG) emission in the US [35]. Similarly, in the UK and Canada, the GHG emission from transportation stands at 27% and 28%, respectively [11, 17]. In countries like Canada, where a large percentage of electricity is generated from renewable sources, studies show that electric vehicles (EVs) are a good alternative to fuel-based ones, offering a measure to curtail GHG emissions [2, 38]. To boost EV adoption, it is crucial to expand and improve existing charging infrastructures. Car users' willingness to opt for an EV is closely linked to the vehicles' travel range and the availability of charging stations [30]. The addition of new charging stations can alleviate range anxiety, especially for prospective EV owners [7]. As such, Hydro-Québec, a publicly owned company responsible for most of the electric grid in the province of Quebec, is aiming to improve the charging infrastructure. To this end, Hydro-Québec is investing in more and faster charging stations. In fact, from 2017 to 2022, 1800 new charging stations were added in the province of Quebec. Simultaneously, there was a surge in EV purchases, escalating from 3347 in 2017 to 34 082 in 2022 [31]. This increase in EV purchases is mostly likely influenced by government policies (e.g., [16, 18]). Yet it may also be due to the introduction, in urban areas, of charging stations near homes, workplaces, and public areas, as this is known to be a crucial incentive for EV adoption [20]. Homes can sometimes have access to privately owned chargers [3], but this does not apply to every EV owner. To top it off, public charging infrastructure has been shown to improve EV adoption [10]. This unfortunately leads to the “chicken and egg” dilemma [1]: investors are only willing to supply more infrastructure if adoption is high, while EV purchases are dependent on widespread charging availability. As such, initial investment must come from governments and public institutions.

The motivation behind this work is to assist decision-makers who need to identify where infrastructure improvements are needed. Concretely, given a set of candidate locations for opening new stations and existing ones, infrastructure owners must decide where to install new stations and determine the number of outlets to be added to new and existent stations. This decision must be driven by the EV users demand. In an urban planning context, it is expected that users mostly carry out intracity trips between home, workplace, and public areas. This can serve to identify the areas of infrastructure enhancement. We assume that it is possible to reduce the users' range anxiety by providing them with access to charging stations near their origin and destination places.

Contributions

Motivated by the context presented above, this paper tackles the challenge of optimally locating and sizing EV charging stations in urban areas to maximize the satisfied charging demand. Here, charging demand refers to requests from EV users to charge their vehicle at a public station. To satisfy the demand, it is necessary the availability in both time and space of a charging station with sufficient capacity (supply), matching or exceeding the requested demand. Maximizing the satisfied charging demand is an important tactical planning problem faced by EV infrastructure providers like Hydro-Québec. Hydro-Québec regularly makes decisions on the expansion of its infrastructure to meet the growing charging demand based on current usage. Our first contribution is the formulation of a linear programming model to efficiently evaluate the satisfied demand for a group of existing charging stations. Even though the satisfied demand can be determined from usage data of stations, this model serves two purposes: (i) it also allows us to compute the unsatisfied demand and (ii) it enables us to evaluate the satisfied demand for any set of stations. Expanding upon this, our second contribution is the integration of location and sizing decisions in the formulation. This results in a mixed-integer linear program, which given a list of candidate locations for new stations, models the maximization of the satisfied demand. Lastly, our third contribution involves detailing a case study of the island of Montreal. We base our research on real charging session data and origin-destination (OD) trips across Montreal boroughs. With it, we validate the effectiveness of our approach to solve large-scale instances and we conduct an analysis of the solutions it produces.

Our methodology differs from most papers in the literature in three key ways, underlying the novelty of our contributions.
  1. We solve the problem of determining the charging demand, that is, the assignment of the EV users (demand) to stations. This is done by formulating it as a maximum flow problem. Maximum flow problems have the advantage of being solvable efficiently. Importantly, our maximum flow problem is based on [14] which is different from the flow-based model commonly found in [24] and other papers about the station location problem. To the best of our knowledge, this is the first maximum flow model of its kind used within the context of the EV station location and sizing problem.
  2. Existing EV station placement methods can handle capacities (e.g., [37]), multiple periods (e.g., [43]), already existing infrastructure (e.g., [41]), large instances (e.g., [32]), or exact solutions (e.g., [8]). While the existing literature usually tackles only one or two of these aspects at a time, this paper integrates all of them in the maximum flow formulation.
  3. Thanks to our partnership with Hydro-Québec, we have access to real-world data, including the existing station locations and charging sessions with timestamps and energy consumption for every user. We use this information to generate realistic instances for testing our methodology, and demonstrate our ability to solve large-scale instances with hundreds of stations and the aggregated power demand of thousands of users.

Paper organization

The paper is organized in the following way. In Section 2, we provide an overview of the existing literature on EV charging infrastructure planning, focusing particularly on station placement. In Section 3, we present the linear model for charging station network evaluation in terms of satisfied demand. In this section, we also present the mixed-integer program, including station location and sizing decisions. In Section 4, we describe our case study for the island of Montreal and test our models on realistic instances. Section 5 concludes the paper and proposes potential future research.

2 RELATED LITERATURE

In this section, we begin with a brief review of the literature pertaining to the optimization of charging infrastructure utilization. Then, we delve into the literature's approaches to estimate charging demand, a crucial element for the optimal placement of charging stations. Subsequently, we discuss different location models, objective functions, intracity and intercity case studies, and temporal modeling considerations. Lastly, we position our work within the reviewed literature.

Research has been conducted on optimizing the existing charging infrastructure, particularly, through charging price decisions aimed at managing the distribution of demand (e.g., [13, 22, 28]). However, in our case study of the island of Montreal, prices cannot be changed and the power grid is prepared to handle even the most severe winter day. Therefore, we focus our review on charging station placement.

Decisions on the expansion and opening of charging stations require the knowledge of its potential use. Thus, the estimation of charging demand is important, as it indicates when and where the demand for charging originates. The most common method is based on the use of origin-destination (OD) data to subsequently model how users move between locations. This kind of data often comes from surveys (e.g., [4, 8, 44]). This is the approach adopted in this paper. Nonetheless, it is important to note that our data only covers travels between boroughs (i.e., it is not granular) and it is not exclusive to electric vehicles (EVs). Hence, we complement the demand estimation with other available data.

The location modeling usually falls into one of two categories: node-based or flow-based [36]. In the node-based approach, either a list of candidate locations is provided and the goal is to maximize the coverage (e.g., [15, 34, 41]), or population nodes are used as candidate locations and the goal is to satisfy all the demand at minimum cost, that is, cost of opening stations (e.g., [5, 26, 39, 44]). For the flow-based modeling, flow is assigned OD pairs, and facilities (charging stations in this context) must capture as much flow as possible. This is another variant of maximum coverage proposed by [21]. Using the flow-based modeling, Kuby and Lim [24] are the first to propose the fuel refuelling location problem (FRLP) which seeks to locate a fixed number of refuelling stations on a network so as to maximize the total flow volume refuelled. In our work, since we consider intracity travels, and hence, short trips, we do not consider the routing of EVs. We define a maximum flow problem in the sense of [14] for the location modeling. The key difference with the FRLP is that we treat flow as a variable rather than a parameter. In the FRLP, each OD is assigned a flow volume on the shortest path between the origin and destination. A binary variable is then used to identify whether each flow volume is present or not when maximizing the objective. This is fundamentally different from our approach, since we view flow as a variable which can enter and leave both OD pairs and stations using flow constraints.

In the literature, the objective of the charging station placement problems varies significantly, but it is often closely related to the location modeling choice. Flow-based models often maximize the total amount of flow in the network (e.g., [6, 9, 23, 24]), which is also our case. For node-based modeling, different objectives have been used, such as maximization of the satisfied EV demand (e.g., [8, 34, 41]) and minimization of the costs (e.g., [5, 12, 26, 39, 40, 44, 45]).

A key aspect of the EV charging station placement problem is whether it concerns the intercity or intracity context. The intercity case focuses on long distance travels between cities, with users potentially charging once or more during a trip (e.g., [9, 26, 39]). The intracity case focuses on a city, with users typically charging near homes, workplaces or public areas [20]. The works in [4, 8, 15] are all examples of works on intracity problems. To the best of our knowledge, Anjos, Gendron and Joyce-Moniz [1] are the only authors to handle both intra and intercity cases simultaneously.

Some works include a time component to the EV charging station placement problem. Notably, time periods have been modeled with two different goals: to consider strategical planning, where periods can represent years, and to consider tactical planning, where periods can represent hours. If time is modeled over a certain number of years, the goal is to focus on the adoption of EVs or the evolution of the EV infrastructure (e.g., [1, 9, 25, 26, 39, 43]). If time is modeled over a range of hours, the goal is to reflect high and low demand over certain times and evaluate the infrastructure service quality (e.g., [8, 12, 15, 34]).

In this paper, we propose a flow-based (in the sense of [14]) mixed-integer linear program (MILP) for the EV charging station placement and sizing problem. Baouche et al. [4] investigated a case study of the city of Lyon for their intracity model. They also used OD data to estimate demand, yet the approach is fundamentally different from ours, with their optimization model ensuring that all demand is covered at minimum cost, and without complementing the OD data with EV session data. Filipi et al. [12] emphasized the importance of accounting for spatial and temporal variations in demand, which aligns with the considerations in our study. They adopted a node-based demand model and focused on minimizing installation costs and customers travel distance, subject to satisfying all the demand (which can be assigned to any opened station). This contrasts with our approach in two key ways: firstly, we focus on maximizing the satisfied energy demand; secondly, we use OD data and we limit the feasibility of the charging stations to points near the origin or destination, rather than node-based demand modeling. Lamontagne et al. [25] proposed a MILP for the maximization of EV adoption in the long-term. Their model does not consider the stations' capacity, which is a crucial factor for our tactical problem, maximizing satisfied demand. Cavadas, Correia and Gouveia [8] considered an intracity case study as well as a temporal dimension along with station capacities. Their work differentiates from ours as they use a node-based model rather than flow-based, aiming to minimize walking distance, and using a predefined number of outlets per station. Finally, the direct solving of the various mixed-integer linear programs proposed for the EV placement problem has encountered the issue of scalability (e.g., [1, 25, 43]). However, by leveraging on the maximum flow model for the estimation of the satisfied demand, we are able to solve our MILP for instances based on the real Montreal demand and existing EV infrastructure.

3 MATHEMATICAL FORMULATION

3.1 Problem statement

Our problem involves determining the optimal location and sizing (number of outlets) of EV charging stations in an urban context. The urban area under study can possess existing stations, but it is not required for the correctness of our model. The decision-maker's goal is to maximize the satisfied daily (charging) demand subject to a budget constraint for the infrastructure expansion costs. Certainly, to address this problem, it is crucial to model how current EV users utilize the available charging stations, either existing or newly installed. Hence, we next describe the available information about EV users and the assumptions made in our work.

Since we consider the urban case, we expect EV users to travel between home and work, home and childcare, home and leisure areas, and so on, which are relatively short distances within the range of EVs. Therefore, we can assume that they do not charge along a path but rather at its origin or destination. Hence, the problem of determining how the charging demand is spread over the available stations becomes a matching problem, where we aim to match EV users to stations close to their origin or destination. Maximizing the number of matchings is equivalent to determining the maximum demand that can be satisfied. Given that, in our case study, users have access to an app providing in real-time the information about station occupancy (Le Circuit électrique), it is reasonable to optimize the assignment with this objective function.

Another important aspect of our problem is the consideration of time. Over a day, EV users do not necessarily travel and charge at the same time, nor do charging sessions have the same duration. For instance, we should expect peaks of demand in the evenings in residential areas, and significant charging duration differences between levels 2 and 3 charging stations [29]. Therefore, we discretize the day into a finite number of periods over which the demand varies, and we consider the assignment of users to stations for each of these periods.

In our case study, we have access to the origin-destination matrix for the urban area under investigation, along with charging session data for existing stations.

3.2 Linear model: Assigning demand to stations

In this section, we describe our framework to determine the assignment of EV charging demand to stations. To this end, we first provide a graph modeling and then, a linear programming formulation. Our notation is summarized in Table 1; the elements corresponding to new stations and outlets are only used in the next section.

TABLE 1. Notation.
Type Notation Description
Sets T $$ T $$ Set of time periods
V $$ V $$ Set of vertices { 1 , 2 , … , N } $$ \left\{1,2,\dots, N\right\} $$ where 1 is the source and N is the sink
O $$ O $$ Subset of vertices representing OD pairs
S 1 $$ {S}_1 $$ Subset of vertices representing existing stations
S 2 $$ {S}_2 $$ Subset of vertices representing candidate locations
L $$ L $$ Subset of arcs representing the charging flow demand of users per OD pairs
M $$ M $$ Subset of arcs between OD pairs and stations
R 1 $$ {R}_1 $$ Subset of arcs representing the charging flow supply at an existing station
R 2 $$ {R}_2 $$ Subset of arcs representing the charging flow supply at a candidate location
Parameters A e t $$ {A}_e^t $$ Charging flow demand of an OD in period t $$ t $$ for e ∈ L $$ e\in L $$
C e $$ {C}_e $$ Charging flow supply at an existing station e ∈ R 1 $$ e\in {R}_1 $$
I e ( 2 ) , I e ( 3 ) $$ {I}_e^{(2)},{I}_e^{(3)} $$ Cost of installing an outlet to a new levels 2 or 3 station in location e ∈ R 2 $$ e\in {R}_2 $$
J e ( 2 ) , J e ( 3 ) $$ {J}_e^{(2)},{J}_e^{(3)} $$ Cost of building a new levels 2 or 3 station in location e ∈ R 2 $$ e\in {R}_2 $$
K e $$ {K}_e $$ Cost of adding an outlet to an existing station e ∈ R 1 $$ e\in {R}_1 $$
G $$ G $$ Budget
P e $$ {P}_e $$ Amount of charging flow supply for a single outlet at an existing station e ∈ R 1 $$ e\in {R}_1 $$
Q ( 2 ) , Q ( 3 ) $$ {Q}^{(2)},{Q}^{(3)} $$ Amount of charging flow supply for a single outlet at a new levels 2 or 3 station
Y ( 2 ) , Y ( 3 ) $$ {Y}^{(2)},{Y}^{(3)} $$ Maximum number of outlets in a levels 2 or 3 station
Y e $$ {Y}_e $$ Maximum number of outlets in location e ∈ R 1 $$ e\in {R}_1 $$
Variables a e t $$ {a}_e^t $$ Amount of charging flow demand generated by an OD in period t $$ t $$ for edge e ∈ L $$ e\in L $$
b e t $$ {b}_e^t $$ Amount of charging flow going from an OD to a station in period t $$ t $$ for edge e ∈ M $$ e\in M $$
c e t $$ {c}_e^t $$ Amount of charging flow supply going through an existing station in period t $$ t $$ for edge e ∈ R 1 $$ e\in {R}_1 $$
d e t $$ {d}_e^t $$ Amount of charging flow supply going through a candidate location in period t $$ t $$ for edge e ∈ R 2 $$ e\in {R}_2 $$
x e $$ {x}_e $$ Number of outlets to add to an existing station e ∈ R 1 $$ e\in {R}_1 $$
y e ( 2 ) , y e ( 3 ) $$ {y}_e^{(2)},{y}_e^{(3)} $$ Number of outlets of a new levels 2 or 3 station e ∈ R 2 $$ e\in {R}_2 $$
z e ( 2 ) , z e ( 3 ) $$ {z}_e^{(2)},{z}_e^{(3)} $$ Binary variable indication whether or not to build a new levels 2 or 3 station e ∈ R 2 $$ e\in {R}_2 $$
  • Abbreviation: OD, origin-destination.

3.2.1 Graph transformation

Let us go into more detail in the description of our assignment problem as it consists of a crucial building block for our methodology. We use a bipartite graph to describe potential matches, that is, assignments of EV user demand to stations. The left side of the bipartite graph is composed of EV users and the right side of stations. Instead of using individual EV users as vertices, it is more efficient to group them based on their trips: users with the same origin-destination (OD) pair are grouped into a single vertex. The edges must represent feasible stations for each OD pair. To decide if a station is feasible for a given OD pair (i.e., whether there is an edge between the vertex representing the OD pair and the vertex representing the station), we define a parameter R $$ R $$ which describes the maximum radius around the origin or the destination of an OD pair. If a station is within either radius, then it is feasible for that OD pair and an edge is created.

The graph model described allows us to identify matchings between OD pairs and stations, but it neglects important aspects. There can exist more than one user per OD pair and a station can charge more than one user at a time; note that a station can have more than one outlet. To fix this, we convert the bipartite graph into a flow graph, and the matching problem into a maximum flow problem. To do so, the edges of the bipartite graph are transformed into arcs from the vertices in set O $$ O $$ to the vertices in set R 1 $$ {R}_1 $$ , a source vertex and a sink vertex are introduced, an arc from the source to each element in set O $$ O $$ is added, and an arc from each element in set R 1 $$ {R}_1 $$ to the sink is added. Finally, to define a maximum flow problem over the resulting graph, restrictions regarding the amount of flow that can pass through each arc and the cost of using those arcs must also be defined. In our problem, there is no cost associated with the use of the arcs. It would be possible to add a cost based on the distance between an origin or destination and a station but this is out of the scope of this paper, since we assume that stations are within a short walking distance. On the other hand, we do define maximum flow capacities to the arcs between the source and the elements in set O $$ O $$ , and between elements in set R 1 $$ {R}_1 $$ and the sink. For the former, the maximum flow capacity represents, at a given period, the amount of charging flow demand for every user traveling on each OD. For the latter, the maximum flow capacity on the arc from a station to the sink represents the maximum amount of charging flow supply available at that station within a period. See Figure 1 for an illustration. A key aspect here is that the charging flow is relative to a period. As such, the (flow) graph can be replicated for a given set of periods T $$ T $$ , where the graph remains the same but the arcs' maximum capacities can change between periods. Specifically, the maximum flow capacities on the arcs from the source to the OD pairs may vary, allowing for the representation of fluctuating number of users traveling on OD pairs at different times of the day. In this way, if we determine the maximum flow from the source to the sink of our graph over a finite time horizon (in our case study, 24 h), we determine the maximum (daily) charging demand that can be satisfied by the current infrastructure.

Details are in the caption following the image
FIGURE 1
Open in figure viewerPowerPoint
Converting a bipartite graph to a flow graph.

Example: The bipartite graph on the left has two origin-destinations (ODs), each with two and three electric vehicle (EV) users, and two stations, each with four outlets; the edges represent the feasible stations. On the right, we have the transformed flow graph, where in some of the arcs we have their maximum flow capacity related to EV demand and station supply; the conversion factors e 1 $$ {e}_1 $$ and e 2 $$ {e}_2 $$ map users demand to flow, while f 1 $$ {f}_1 $$ and f 2 $$ {f}_2 $$ map outlet supply to flow.

Note that, in order to identify if a potential station location is interesting, we can add a list of candidate locations to the flow graph, following a similar approach as with existing stations. For instance, when generating the flow graph, it is possible to encounter OD pairs with no arc connected to a station. The demand from such an OD is referred to as impossible demand. Therefore, it would make sense to have in the list of potential new stations one or more locations close to the said OD pair; if we open at least one of these stations, it would guarantee an increase in the overall satisfied demand.

3.2.2 Formulation

We are ready to provide the linear program corresponding to the maximum flow of the described graph.

Figure 2 provides a visual summary of the notation used for the sets of arcs (continuation of the example of Figure 1).

Details are in the caption following the image
FIGURE 2
Open in figure viewerPowerPoint
Flow model notation.

From left to right, image source (vertex 1), image set L $$ L $$ , image set O $$ O $$ , image set M $$ M $$ , image set S 1 ∪ S 2 $$ {S}_1\cup {S}_2 $$ , image set R 1 ∪ R 2 $$ {R}_1\cup {R}_2 $$ , image sink (vertex N $$ N $$ ).

Our maximum flow problem is the following linear program:
(Program 1) max a , b , c ∑ t ∈ T ∑ e ∈ L a e t $$ \left(\mathrm{Program}\ 1\right)\kern3em \underset{a,b,c}{\max}\kern0.5em \sum \limits_{t\in T}\sum \limits_{e\in L}{a}_e^t\kern0.50em $$ (1a)
s . t . a ( 1 , v ) t = ∑ e ∈ M : e = ( v , i ) b e t ∀ v ∈ O , ∀ t ∈ T $$ s.t.\kern0.80em {a}_{\left(1,v\right)}^t=\sum \limits_{e\in M:e=\left(v,i\right)}{b}_e^t\kern0.50em \forall v\in O,\forall t\in T $$ (1b)
∑ e ∈ M : e = ( i , v ) b e t = c ( v , N ) t ∀ v ∈ S 1 , ∀ t ∈ T $$ \kern0.5em \sum \limits_{e\in M:e=\left(i,v\right)}{b}_e^t={c}_{\left(v,N\right)}^t\kern0.50em \forall v\in {S}_1,\forall t\in T $$ (1c)
0 ≤ a e t ≤ A e t ∀ e ∈ L , ∀ t ∈ T $$ \kern0.5em 0\le {a}_e^t\le {A}_e^t\kern0.50em \forall e\in L,\forall t\in T $$ (1d)
0 ≤ b e t ∀ e ∈ M , ∀ t ∈ T $$ \kern0.5em 0\le {b}_e^t\kern0.50em \forall e\in M,\forall t\in T $$ (1e)
0 ≤ c e t ≤ C e ∀ e ∈ R 1 , ∀ t ∈ T . $$ \kern0.5em 0\le {c}_e^t\le {C}_e\kern0.50em \forall e\in {R}_1,\forall t\in T. $$ (1f)
The objective function (1a) is the sum of charging flow leaving the source. Since the flow Constraints (1b) and (1c) guarantee that the amount of flow reaching the sink is equal to the amount leaving the source, this objective function is equivalent to the total amount of charging flow in the graph. Indeed, the flow Constraints (1b) and (1c) ensure that the amount of charging flow entering into the OD pairs is the same amount leaving and the amount of charging flow entering the stations is the same amount leaving, respectively. Constraints (1d) limit the flow from the source to each OD pair to the charging demand for that specific OD pair within a given period. This charging demand is equal to the number of EV users travelling on that OD pair multiplied by the charging flow demand per user. For example, let a flow f $$ f $$ be the average kilowatt per second consumption of an EV and p $$ p $$ the length of a period in seconds, the charging flow demand of a user is f · p $$ f\cdotp p $$ . If we multiply that value by the number of EV users in an OD, we obtain the complete requested charging flow for that OD. Constraints (1f) limit the amount of charging flow supply that can be provided at each station.

3.3 Mixed-integer model: Placing stations and outlets

In the previous section, we described our model for the assignment of the demand to stations. Next, our objective is to introduce new stations and outlets that remain available throughout all periods, with the aim of diminishing the existing unsatisfied demand (or, equivalently, increase the satisfied demand). It is worth noting that our approach assumes that all stations and outlets are built from the beginning, rather than gradually over time. We integrate into Program (1a-1f) the decisions related to the opening of new stations and addition of outlets, leading to the following mixed-integer program:
(Program 2) max a , b , c , d , x , y , z ∑ t ∈ T ∑ e ∈ L a e t $$ \left(\mathrm{Program}\ 2\right)\kern2em \underset{a,b,c,d,x,y,z}{\max}\kern0.5em \sum \limits_{t\in T}\sum \limits_{e\in L}{a}_e^t\kern0.50em $$ (2a)
s . t . ∑ e ∈ R 2 I e ( 2 ) y e ( 2 ) + J e ( 2 ) z e ( 2 ) + I e ( 3 ) y e ( 3 ) + J e ( 3 ) z e ( 3 ) + ∑ e ∈ R 1 K e x e ≤ G $$ s.t.\kern0.5em \sum \limits_{e\in {R}_2}\left({I}_e^{(2)}{y}_e^{(2)}+{J}_e^{(2)}{z}_e^{(2)}+{I}_e^{(3)}{y}_e^{(3)}+{J}_e^{(3)}{z}_e^{(3)}\right)+\sum \limits_{e\in {R}_1}{K}_e{x}_e\le G\kern0.50em $$ (2b)
( 1 b ) − ( 1 e ) ∑ e ∈ M : e = ( i , v ) b e t = d ( v , N ) t ∀ v ∈ S 2 , ∀ t ∈ T $$ {\displaystyle \begin{array}{lll}\hfill & \left(1\mathrm{b}\right)-\left(1\mathrm{e}\right)\kern0em & \hfill \\ {}\hfill & \sum \limits_{e\in M:e=\left(i,v\right)}{b}_e^t={d}_{\left(v,N\right)}^t\kern0em & \hfill \forall v\in {S}_2,\forall t\in T\end{array}} $$ (2c)
0 ≤ c e t ≤ C e + P e x e ∀ e ∈ R 1 , ∀ t ∈ T $$ \kern0.5em 0\le {c}_e^t\le {C}_e+{P}_e{x}_e\kern0.50em \forall e\in {R}_1,\forall t\in T $$ (2d)
0 ≤ d e t ≤ Q ( 2 ) y e ( 2 ) + Q ( 3 ) y e ( 3 ) ∀ e ∈ R 2 , ∀ t ∈ T $$ \kern0.5em 0\le {d}_e^t\le {Q}^{(2)}{y}_e^{(2)}+{Q}^{(3)}{y}_e^{(3)}\kern0.50em \forall e\in {R}_2,\forall t\in T $$ (2e)
x e ≤ Y e − C e P e ∀ e ∈ R 1 $$ \kern0.5em {x}_e\le {Y}_e-\frac{C_e}{P_e}\kern0.50em \forall e\in {R}_1 $$ (2f)
y e ( 2 ) ≤ Y ( 2 ) z e ( 2 ) ∀ e ∈ R 2 $$ \kern0.5em {y}_e^{(2)}\le {Y}^{(2)}{z}_e^{(2)}\kern0.50em \forall e\in {R}_2 $$ (2g)
y e ( 3 ) ≤ Y ( 3 ) z e ( 3 ) ∀ e ∈ R 2 $$ \kern0.5em {y}_e^{(3)}\le {Y}^{(3)}{z}_e^{(3)}\kern0.50em \forall e\in {R}_2 $$ (2h)
z e ( 2 ) + z e ( 3 ) ≤ 1 ∀ e ∈ R 2 $$ \kern0.5em {z}_e^{(2)}+{z}_e^{(3)}\le 1\kern0.50em \forall e\in {R}_2 $$ (2i)
x e ∈ ℕ ∀ e ∈ R 1 $$ \kern0.5em {x}_e\in \mathbb{N}\kern0.50em \forall e\in {R}_1 $$ (2j)
y e ( 2 ) , y e ( 3 ) ∈ ℕ , z e ( 2 ) , z e ( 3 ) ∈ { 0 , 1 } ∀ e ∈ R 2 . $$ \kern0.5em {y}_e^{(2)},{y}_e^{(3)}\in \mathbb{N},{z}_e^{(2)},{z}_e^{(3)}\in \left\{0,1\right\}\kern0.50em \forall e\in {R}_2. $$ (2k)
The objective function is the same as before. The constraint (2b) enforces the costs of new stations and outlets to be below a given budget. Constraints (2c) are the same as Constraints (1c) but for candidate stations instead. Constraints (2d) adapt Constraints (1f) to account for newly added outlets. The number of new outlets is multiplied by a factor P e $$ {P}_e $$ to convert them into flow. Constraints (2e) limit the maximum amount of flow that can travel to candidate stations by the amount of new levels 2 or 3 outlets. Constraints (2f) limit the maximum amount of newly added outlets to an existing station by subtracting the already existing number of outlets from the maximum number possible. The parameters Y e $$ {Y}_e $$ and the variables x e $$ {x}_e $$ are relative to the level of the station e $$ e $$ they are associated with. If a station is level 2, only level 2 outlets can be installed and the same applies to level 3. Constraints (2g) and (2h) limit the number of outlets according to whether a new levels 2 or 3 station is built. Due to Constraints (2i), a new station can only be levels 2 or 3 but not both. In the rare case where there are levels 2 and 3 outlets at an existing station, that station is considered as two separate stations in the same location. Constraints (2j) and (2k) set the domains for variables x , y , z $$ x,y,z $$ .

4 COMPUTATIONAL EXPERIMENTS

In this section, we aim to validate the use of our linear program to estimate station demand and the efficiency of solving our mixed-integer model for real-world instances. Hence, we start in Section 4.1 by detailing our case study of the island of Montreal. Then, in Section 4.2, we show experimental results of our linear model when it comes to matching users to existing stations. Finally, in Section 4.3, we provide experimental results for solving our mixed-integer program, modeling the addition of new stations and outlets. All experiments are run on an Intel i7-10700F CPU @ 2.90 GHz with 8 cores and 16 GB of RAM. We use CPLEX Optimization Studio V22.1.0 on a single thread per instance, with a 30 min time limit and the default values for all the other solver parameters.

4.1 Montreal case

4.1.1 Data

We focus our experiments on the island of Montreal. For this case study, we obtained data about the location, level and number of outlets for existing public stations of the Le Circuit électrique and the time, duration and average kilowatts per second (kW/s) for charging sessions at these stations. In our data, there are 841 level 2 stations and 41 level 3 stations on the island. The maximum number of outlets within a station is 16 and 7 for levels 2 and 3 stations, respectively. Figure 3 provides the distribution of outlets per station.

Details are in the caption following the image
FIGURE 3
Open in figure viewerPowerPoint
Distribution of the number of outlets per station. (A) Level 2. (B) Level 3.

We tested two sets of periods: (1) a single time horizon of 24 h and (2) the same horizon discretized into 6-h periods. The goal is to find the impact of relaxing the demand over 24 h, that is, of assuming that the demand can be satisfied at any moment of the day. Figure 4 shows that for level 2 stations, a substantial percentage of the energy provided is to users who leave their vehicles to charge overnight. However, level 3 stations are used uniformly throughout the day as they are more expensive and thus less popular for overnight charging. As such, accounting for fluctuations of the charging demand over the day will result in more accurate modeling of the satisfied demand, which is expected to better inform the placement and sizing of stations. Indeed, using a 24-h relaxation should overestimate the satisfied demand in comparison with the same discretized horizon, since users can be forced to charge at inconvenient times.

Details are in the caption following the image
FIGURE 4
Open in figure viewerPowerPoint
Distribution of the daily average percentage of energy supplied per station per 6-h period. (A) Level 2. (B) Level 3.

We also used the publicly available data of the 2018 OD survey of the Montreal region collected by the ARTM. This data provides the average number of trips between each pair of Montreal boroughs within a day. These trips are not limited to EVs, but can be used as a reasonable approximation of users' movements. We only consider the boroughs within Montreal which leaves us with 32 different boroughs (see Figure 5).

Details are in the caption following the image
FIGURE 5
Open in figure viewerPowerPoint
Map of Montreal boroughs.

4.1.2 Generation of instances

Based on the described data, we now detail the process used to generate instances, namely, the sets and parameters of Table 1. To begin, we need to decide on two parameters: R $$ R $$ and W $$ W $$ . Recall that the parameter R $$ R $$ indicates the maximum distance a user is willing to walk between their origin or destination and a charging station. In our framework, each OD pair could have its own radius, however, we use the same radius for all of them since we do not dispose of individual user information related to their willingness to walk. We limit our radius between 400 and 700 m based on research done on the acceptable walking distance for public transit stops and stores [19, 27, 33, 42]. The parameter W $$ W $$ stands for the number of randomly generated (latitude, longitude) points in an instance. More concretely, these randomly generated points serve to create OD pairs, where each point is both an origin and a destination. We generate points relative to the density of EV users charging in each borough (session data). In principle, we want to have a number of points W $$ W $$ capable of covering the entirety of the urban area relative to the radius R $$ R $$ . In practice, however, this would require far too many points or an unrealistically large radius. As such, we try a different number of (randomly generated) points to test the sensibility of our model. In the rest of this section, we provide a simple example to explain each step of our instance generation process and conclude with a summary of the combination of parameters used to generate instances.

Figure 6 is a simple map with two borrows ( Ω $$ \Omega $$ and Λ $$ \Lambda $$ ), containing three randomly generated points in red and two stations represented by the blue squares. Each point has the same radius R $$ R $$ . We can convert Figure 6 into a bipartite graph. Figure 7 gives a visual representation of the transformation.

Details are in the caption following the image
FIGURE 6
Open in figure viewerPowerPoint
Example of an instance.
Details are in the caption following the image
FIGURE 7
Open in figure viewerPowerPoint
The bipartite graph representation of Figure 6.

Our model provides the option to use any kind of data as the flow. We use kW since our dataset contains the kW/s per charging session. To calculate the maximum flow capacity of existing stations, we use the session data to estimate the average kW/s per session for each outlet. For each station, we sum up the outlets' kW/s per session to get the maximum kW/s per station. This value can be multiplied by the length of the periods to obtain the maximum flow capacity per period of a station.

To calculate the C e $$ {C}_e $$ parameters of our example, we take the average of kW/s per session from Table 2 for each station: 5 kW/s for station 1 and 4 kW/s for station 2. If we let our time horizon be a single 24-h period, then the total flow supply is 5 · 3600 · 24 = 432   000 $$ 5\cdotp 3600\cdotp 24=432\;000 $$  kW and 4 · 3600 · 24 = 345   600 $$ 4\cdotp 3600\cdotp 24=345\;600 $$  kW for stations 1 and 2, respectively. For our example, we assume that each station only has one outlet.

TABLE 2. Example of session data.
Station Duration (s) kW/s
1 110 5
2 100 3
2 10 5

To calculate the maximum flow capacity per OD (i.e., the demand), we start by calculating the daily average kW that is being used within a period for each station. We sum this supplied kW for each borough; this gives us the amount of supply per borough. From there, we need to convert the supply into its original demand per borough. Here, we combine the use of session data with the Montreal OD data to calculate the percentage of EV users travelling between two boroughs. This forms a set of linear equations: ∑ i ∈ H q i p i j = r j $$ {\sum}_{i\in H}{q}_i{p}_i^j={r}_j $$ ∀ j ∈ H $$ \forall j\in H $$ where H $$ H $$ is the set of Montreal boroughs. In this set of equations, r j $$ {r}_j $$ represents the total amount of supply at each station within borough j $$ j $$ . The coefficient p i j $$ {p}_i^j $$ is the percentage of people travelling from borough i $$ i $$ to j $$ j $$ . Our variable is q i $$ {q}_i $$ which is the total amount of demand in borough i $$ i $$ . To calculate the amount of demand on each OD, we simply compute q i · p i j + q j · p j i $$ {q}_i\cdotp {p}_i^j+{q}_j\cdotp {p}_j^i $$ for each borough i $$ i $$ and j $$ j $$ . We assume that most people leave in the morning and come back at night, resulting in bidirectional flow. This assumption is realistic, as most intracity trips occur between home, work and public places. If we want to account for unidirectional trips (which would allow to enforce users to charge only at the origin or only at the destination), we would simply need to duplicate each OD vertex. We distribute the previously computed demand uniformly between each OD pair with the same origin and destination. We also account for trips within the same borough by computing q i · p i i $$ {q}_i\cdotp {p}_i^i $$ .

In this way, to calculate the A e t $$ {A}_e^t $$ parameters of our example, we can take the average session duration from Table 2 per station over our 24-h period. We assume for this example that all sessions are from the same day. This implies 110 · 5 = 550 $$ 110\cdotp 5=550 $$  kW for station 1 and 100 · 3 + 10 · 5 = 350 $$ 100\cdotp 3+10\cdotp 5=350 $$  kW for station 2. We sum all supplied kW within the same borough. Since stations 1 and 2 are in different boroughs, the Λ $$ \Lambda $$ borough has 550 kW of supply and the Ω $$ \Omega $$ borough has 350 kW. Using the OD matrix of Table 3, we can write two equations: 0 . 5 q Ω + 0 . 25 q Λ = 350 $$ 0.5{q}_{\Omega}+0.25{q}_{\Lambda}=350 $$ and 0 . 5 q Ω + 0 . 75 q Λ = 550 $$ 0.5{q}_{\Omega}+0.75{q}_{\Lambda}=550 $$ . Solving this set of equations gives us q Ω = 500 $$ {q}_{\Omega}=500 $$ and q Λ = 400 $$ {q}_{\Lambda}=400 $$ . This implies that we have 500 kW of demand in borough Ω $$ \Omega $$ and 400 kW in Λ $$ \Lambda $$ . The resulting demand flow is as follow: between Ω $$ \Omega $$ and Ω $$ \Omega $$ , 0 . 5 q Ω = 250 $$ 0.5{q}_{\Omega}=250 $$  kW, between Ω $$ \Omega $$ and Λ $$ \Lambda $$ , 0 . 5 q Ω + 0 . 25 q Λ = 350 $$ 0.5{q}_{\Omega}+0.25{q}_{\Lambda}=350 $$  kW and between Λ $$ \Lambda $$ and Λ $$ \Lambda $$ , 0 . 75 q Λ = 300 $$ 0.75{q}_{\Lambda}=300 $$  kW. We combine the flow from Ω $$ \Omega $$ to Λ $$ \Lambda $$ and from Λ $$ \Lambda $$ to Ω $$ \Omega $$ , since we make the assumption that our flow is bidirectional. Finally, we split these flows between each point to obtain the flow for each OD pair: A C $$ AC $$ has 250 kW, A B $$ AB $$ has 175 kW and B C $$ BC $$ has 175 kW. It is worth noting that in this example, we lost 300 kW of demand because we cannot represent the flow between Λ $$ \Lambda $$ and Λ $$ \Lambda $$ since we only have a single point in that borough. In practice, we generate a critical mass of points to guarantee at least two points in each borough. This gives us the final flow graph in Figure 8.

Details are in the caption following the image
FIGURE 8
Open in figure viewerPowerPoint
Example of a flow graph.
TABLE 3. Example of an origin-destination (OD) matrix.
Ω $$ \Omega $$ Λ $$ \Lambda $$
Ω $$ \Omega $$ 50% 50%
Λ $$ \Lambda $$ 25% 75%

We do not have a list of potential locations, so we use impossible demand to create candidate locations. Recall that impossible demand is the demand generated by an OD vertex with no edges to any station in the bipartite graph. This demand cannot be satisfied, and as such, considering a candidate location near it is likely a good possibility. To do so, we add two candidate locations for each impossible OD demand: one at the origin and one at the destination. Note that any OD vertex within the defined radius R $$ R $$ of a candidate location gets an outgoing arc to that location, including the OD vertex related with the impossible demand. In our example, the OD pair A B $$ AB $$ does not have any valid station. As such, we would add two candidate locations: one at A $$ A $$ and one at B $$ B $$ . This means both OD pairs A C $$ AC $$ and B C $$ BC $$ would also gain a new station. The kW/s given to the new station is based on an average across all stations of the same level. If we assume all stations in our example are of the same level then a new station would have ≈ $$ \approx $$ 4.33 kW/s.

We do not have data about the cost of adding outlets or building new stations since the price can vary widely based on the location and electricity grid availability. As such, for our testing, we use arbitrary costs guided by reasonable considerations. We attribute to the addition of a level 2 outlet (to an existing station or a new one) a cost of 1. A level 3 outlet is twice that. Building a new level 2 station is 10 and a level 3 is 100. To account for these arbitrary costs, we run our experiments on multiple budgets ranging from 0 to 700 to perform a sensibility analysis of our MILP.

Having described our process for utilizing the data to generate the flow graphs and established the budget constraint, we now proceed to outline the various instances we create in accordance with the aforementioned procedure. We consider instances with R ∈ { 400 , 500 , 600 , 700 } $$ R\in \left\{400,500,600,700\right\} $$ , where the unit is meters, and with W ∈ { 100 , 150 , 200 , 250 , 300 } $$ W\in \left\{100,150,200,250,300\right\} $$ . For each combination of the R $$ R $$ and W $$ W $$ values, we generated five instances, where only the location of the W $$ W $$ random OD points differ. In each instance, the set S 1 $$ {S}_1 $$ contains the same 882 stations, while the set of candidate locations S 2 $$ {S}_2 $$ can vary depending on the OD pairs (recall the description above). For W = 100 , 150 , 200 , 250 $$ W=100,150,200,250 $$ and 300, the instances have 4950, 11 175, 19 900, 31 125, and 44 850 ODs (i.e., the cardinality of set O $$ O $$ ) and an average of 43.4, 65.8, 92.2, 117.4, and 141.8 candidate locations, respectively. In the next sections, we provide average results over the five generated instances for each ( R , W ) $$ \left(R,W\right) $$ pair. All the results are shown as a percentage of the total (average) kW charging demand, that is, ∑ t ∈ T ∑ e ∈ L A e t $$ {\sum}_{t\in T}{\sum}_{e\in L}{A}_e^t $$ .

4.2 Assigning demand to stations

Our first tests are meant to evaluate the impact of the radius R $$ R $$ and of the number of points W $$ W $$ on Program (1a-1f). The goal is to assess the sensitivity of satisfied and impossible demand to those parameters, analyze the service of the current infrastructure, as well as to identify a suitable value of W $$ W $$ that balances the model accuracy and computational efficiency when incorporating location and sizing decision. Note that larger values of W $$ W $$ allow a greater diversity of OD scenarios, but lead to larger optimization problems.

In Figures 9 (the y-axis of figure (A) begins at 60% for better readability) and 10, we present our results for the satisfied and impossible demand separately for two cases: one where a single period is considered, and the other where a day is discretized into four periods. In both cases, we observe that the satisfied demand increases as the number of points ( W $$ W $$ ) increases, and then stabilizes. This is to be expected since the closer the number of points gets to the real number of EV users, the more accurately we depict the coverage of the territory by the existing infrastructure. Importantly, it appears that a relatively low value of W $$ W $$ suffices to capture the prevailing charging station coverage, which has a direct impact on the number of variables and constraints of Program (2a-2k), analyzed in the next section. Similarly, an increase in the radius R $$ R $$ results in an increase in satisfied demand. This can be attributed to the fact that a larger radius provides each OD with a greater number of station options to choose from. However, in contrast to the number of points W $$ W $$ , opting for a larger radius distances us from reality, given that fewer individuals are expected to be willing to walk 700 m compared to 400 m. The larger radius can also be perceived as a compromise in service quality (coverage). Independently of that, any increase in the number of points or radius is limited by the amount of demand that can be satisfied. If the stations provide enough supply, the limiting factor becomes the impossible demand. It is worth noting that since our demand generation is closely related to the amount of supply (recall Section 4.1), it makes sense that we are able to satisfy most of the demand for these instances. On the flip side, increasing the radius reduces the impossible demand. This can be explained by the fact that a larger radius increases the covered area, meaning ODs are less likely to have no nearby stations. A less intuitive result is the fact that increasing the number of points does not affect the impossible demand. The reason behind this comes from the stochastic nature of our points' generation. If we have two instances with 100 points and 20% of impossible demand each, if we assume that both instances do not have overlapping points which is statistically likely, then combining both instances into one leads to a 200 points instance with 20% impossible demand. This only works if the 100 points instances are correctly predicting the total impossible demand of the network from the start.

Details are in the caption following the image
FIGURE 9
Open in figure viewerPowerPoint
Single period results for program (1a-1f). (A) Percentage of satisfied demand. (B) Percentage of impossible demand.
Details are in the caption following the image
FIGURE 10
Open in figure viewerPowerPoint
Multi-period results for program (1a-1f). (A) Percentage of satisfied demand. (B) Percentage of impossible demand.

The main difference between the two cases in these figures is in a slightly lower satisfied demand when we consider the four 6-h periods. This is because the unsatisfied demand in each period cannot be satisfied in others, modeling an implicit constraint on when users are willing to charge. In the 24 h instances, users can charge at any point of the day which is unrealistic. With four blocks of 6 h, we can more easily reflect when users are looking for a station. However, it should be noted that adopting a more granular discretization would lead to more variables and constraints in our models. Moreover, this might also necessitate the incorporation of charging over consecutive periods (if time blocks are small). The impossible demand is exactly the same in both cases. This is because the impossible demand does not change within a day (we have the same OD pairs over the time horizon).

Tables 4 and 5 give a brief overview of the amount of demand satisfied at each period. The purpose of these results is to analyze their similarity with regards to the actual satisfied demand of Table 6. In other words, we aim to understand if the charging habits over the time periods are similar. In our results, we note that level 3 stations tend to mirror the satisfied demand of level 2 stations. This is because we do not model charging habits, that is, users preferences. For instance, during the period 0–6 h, level 3 satisfies more demand than in the other periods because in our instances (and session data) there is more demand over this period and there is no user preference making users to favour level 2. This could be improved to better match reality by either changing the capacity of level 3 stations during certain periods or introducing flow costs associated with the use of certain stations. For the tables with the other radii, we refer to Appendix A.1; the result trend is analogous. Figure 11 shows a solved instance, where all points with unsatisfied and impossible demand are visible. The impossible demand becomes more prevalent as we go west, away from downtown. The closer we get to downtown, the impossible demand turns to unsatisfied demand. Near downtown, the unsatisfied demand is nonexistent with no points visible since all demand is satisfied.

Details are in the caption following the image
FIGURE 11
Open in figure viewerPowerPoint
Map of the unsatisfied and impossible demand per point ( R = 400 , W = 300 $$ R=400,W=300 $$ ).

The points' size represents the unsatisfied demand and the color represents the impossible demand (the larger and darker, the higher). Remark that points can have both unsatisfied and impossible demand as they are related to a set of origin-destination (OD) pairs.

TABLE 4. Percentage of satisfied demand assigned to level 2 stations per time period with a 400 m radius.
# of randomly generated points
Period 100 150 200 250 300
18–24 h 24.57% 24.24% 23.90% 23.66% 23.59%
12–18 h 23.44% 22.68% 22.20% 21.94% 21.74%
6–12 h 23.78% 23.08% 22.76% 22.49% 22.32%
0–6 h 28.22% 30.00% 31.14% 31.91% 32.36%
TABLE 5. Percentage of satisfied demand assigned to level 3 stations per time period with a 400 m radius.
# of randomly generated points
Period 100 150 200 250 300
18–24 h 23.45% 20.63% 22.92% 24.65% 21.91%
12–18 h 20.27% 20.57% 19.98% 17.30% 18.97%
6–12 h 21.77% 21.46% 20.55% 20.96% 19.30%
0–6 h 34.51% 37.34% 36.55% 37.09% 39.81%
TABLE 6. Percentage of demand per station for each time period (Figure 4).
Period Level 2 Level 3
18–24 h 23.64% 23.91%
12–18 h 21.92% 28.35%
6–12 h 22.46% 24.82%
0–6 h 31.96% 22.91%

In this section, we analyzed the solutions of Program (1a-1f) across instances with varying number of demand points ( W $$ W $$ ), the extent to which EV users are willing to deviate from their origin or destination to visit a station (radius R $$ R $$ ), and scenarios involving both single and multiple periods. The results, notably the estimation of satisfied demand, are mostly sensible to the number of demand points. Nevertheless, a fairly modest number of demand points suffices to obtain a robust estimate.

4.3 Adding and expanding stations

Our second set of tests is meant to evaluate the computational performance when solving our model, Program (2a-2k), for the installation of new stations and outlets. For these experiments, we exclusively focus on instances with R = $$ R= $$ 400 meter radius, as it offers the greatest flexibility to users. In other words, this radius allows for a concentration of stations in close proximity to users. We take the instances with W = $$ W= $$ 100, 150, and 200 random points to analyze the sensitivity of the optimal objective value (satisfied demand) to the number of points, while keeping the size of Program (2a-2k) reasonable. As explained in Section 4.1, we use the impossible demand to identify a list of candidate locations S 2 $$ {S}_2 $$ .

Figures 12 and 13 provide our results for the case with a single period and for the case with four periods. We can remark two trivial cases. The first is when the budget is 0, which simply results in the linear model since no station or outlet can be added. The second is when the budget is so large ( G ≥ 700 $$ G\ge 700 $$ ) that we can add as many stations and outlets as necessary to satisfy all the demand, both unsatisfied and impossible. The interesting cases lie in the middle, where instances with different numbers of points W $$ W $$ have similar percentages. This can be explained by the fact that the impossible demand is relatively stable among instances (recall Figures 9B and 10B for R = $$ R= $$ 400 m) and, as such, adding a budget reduces impossible demand by similar amounts. We can observe that solving instances with an increasing number of points W $$ W $$ , tens to lead to higher computational times and optimality gaps. Therefore, going beyond a W $$ W $$ value exceeding 200 points is anticipated to substantially increase computational times. The dips in the graphs are related to the high variance between instances (refer to the Appendix A.2 for detailed results).

Details are in the caption following the image
FIGURE 12
Open in figure viewerPowerPoint
Single period results for program (2a-2k). (A) Percentage of satisfied demand. (B) Optimality gap. (C) Computational time.
Details are in the caption following the image
FIGURE 13
Open in figure viewerPowerPoint
Multi-period results for program (2a-2k). (A) Percentage of satisfied demand. (B) Optimality gap. (C) Computational time.

In Figures 12 and 13, the main difference between the single and the multi-period cases is on the solving times and optimality gaps, with the multi-period one performing worst on both metrics. This is not surprising as the multi-period instances result in larger mixed-integer programs. With respect to the percentage of satisfied demand, the single and multi-period instances seem similar. In fact, the satisfied demand in the multi-period case is overall lower by at most 4.23% and on average 1% less. Although these differences are small, it is important to note that this comparison is not entirely fair, given that the instances are fundamentally distinct due to their utilization of different time discretizations. For this reason, we evaluate the location and sizing decisions of solutions derived from single-period instances within the more realistic multi-period program, resulting in Figure 14. We observe a discrepancy of up to 5.28% and an average of 2.75% less satisfied demand compared to the multi-period solution (Figure 13). This shows that accounting for the time component of the charging location and sizing problem is meaningful.

Details are in the caption following the image
FIGURE 14
Open in figure viewerPowerPoint
Single period results with multi-periods evaluation. (A) 100 points. (B) 150 points. (C) 200 points.

While analyzing the solutions to our instances, we observed that for the Montreal case, our model tends to prioritize the addition of level 2 outlets to existing stations and the addition of level 2 stations, as we increase the budget. In fact, among the solved instances, no solution included the addition of level 3 outlets or stations. This can be explained by the fact that the existing infrastructure is mostly sufficient to sustain the already existing demand. As such, the majority of the budget is spent providing a sparse amount of supply in undersupplied areas. Based on our cost parameters, level 3 stations are simply too expensive for this specific use case. Figure 15 is an example of this behavior.

Details are in the caption following the image
FIGURE 15
Open in figure viewerPowerPoint
Map of Montreal with only new stations and new outlets ( R = 400 , W = 200 , G = 100 $$ R=400,W=200,G=100 $$ ).

The blue points represents existing level 2 stations and the orange ones are new level 2 stations. The size of the points corresponds to the number of outlets added. No level 3 stations are expanded or opened.

In this section, we showed that incorporating expansion decisions results in computationally demanding optimization problems. The inclusion of a budget constraint for the expansion decisions can significantly increase solving times, even when dealing with a low number of demand points, in contrast to the zero-budget scenario. Unlike the preceding section, our findings underscore the relevance of factoring in multiple periods when determining the optimal expansion decisions.

5 CONCLUSION

In this work, we propose a maximum flow-based formulation for modeling the problem of locating and sizing EV charging stations in an intracity context. By solving our mathematical programming model, we are able to optimize the placement of new stations as well as to evaluate their expected usage (i.e., the charging demand they satisfy), within a densely populated city. Such evaluation can be computationally expensive due to the large number of users, existing stations, and potential new locations. Our key contribution is the transformation of the charging demand assignment to stations into a maximum flow problem. The latter allows for the scalability of our approach. To the best of our knowledge, we present the first approach capable of handling realistically-sized instances, including multi-period instances, with an exact algorithm. This improves upon single-period, exact methodologies (e.g., [32, 40]) and multi-period, heuristic methodologies (e.g., [1, 43]) from the existing literature.

Our mathematical programming models are run based on real-world data. Concretely, the linear model can evaluate the service quality of an existing network of stations in terms of satisfied demand. Moreover, it can be used to identify impossible demand and hence, locations where the installation of new stations would be desirable. Given a budget, the mixed-integer model can identify the most promising locations from a list of candidate locations and increase the capacity of the already existing infrastructure. We also demonstrate the impact of discretizing a 24-h period to account for highs and lows in demand over a day.

For the application of our approach to the case study of the island of Montreal, the data needed was the charging session records of all the existing infrastructure and the daily OD travels across all boroughs. We show that the current infrastructure would not require a large increase in supply to satisfy all the demand at the moment. However, despite offering enough supply, the network does not provide uniform quality of service across the island. This results in certain regions having limited access to public charging facilities.

In practice, our methodology is particularly valuable for infrastructure owners to identify limitations in their provision of charging, namely, regions with impossible and unsatisfied demand. The direct use of our optimal expansion decisions must be cautiously analyzed for each specific application as simplifications were made for sake of tractability.

Further research could focus on the integration of our maximum flow model into EV charging stations placement problems using other objectives such as cost minimization. This would result in a bi-level program with a maximum flow problem at the lower level. Another important aspect would be the integration of power grid constraints, which could restrict candidate locations. Concerning the modeling of the assignment of the demand to stations, an aspect for future consideration is to account for user preferences over stations (or locations), instead of assuming that the demand is effectively spread (e.g., through a real-time app). This could be potentially done by assigning weights to the arcs of our flow network. Another line of research could be to further explore the best way to discretize a day to properly reflect reality. On the same topic, although we consider a time horizon for our flow model, we do not allow for flow to travel between consecutive periods, which could occur in practice. Finally, expanding our approach to handle both the intracity and intercity cases would allow for a more complete modeling of the optimal location and sizing of EV charging stations problem.

ACKNOWLEDGMENTS

We are grateful to Jean-Luc Dupré from the Direction Mobilité of Hydro-Québec for sharing his knowledge about our case study, and to Steven Lamontagne for his insights about the project. This research was supported by Hydro-Québec, NSERC Collaborative Research and Development grant CRDPJ 536757-19, and the FRQ-IVADO Research Chair in Data Science for Combinatorial Game Theory. All the map figures presented in this paper were created using geojson.io and the open source graphing library for Python plotly.

    APPENDIX A: FURTHER COMPUTATIONAL RESULTS

    A.1 Detailed results of Section 4.2

    Figure A1 provides an illustration on the variation of the satisfied demand over each block of 6 h. Tables A1–A6 provide further details on the average satisfied demand for each value of R $$ R $$ .

    TABLE A1. Percentage of satisfied demand assigned to level 2 stations per time period with a 500 m radius.
    # of randomly generated points
    Period 100 150 200 250 300
    18–24 h 24.17% 23.90% 23.59% 23.44% 23.41%
    12–18 h 22.60% 22.04% 21.76% 21.64% 21.54%
    6–12 h 23.13% 22.54% 22.32% 22.19% 22.16%
    0–6 h 30.10% 31.52% 32.34% 32.72% 32.89%
    TABLE A2. Percentage of satisfied demand assigned to level 3 stations per time period with a 500 m radius.
    # of randomly generated points
    Period 100 150 200 250 300
    18–24 h 23.23% 21.46% 22.17% 23.71% 22.20%
    12–18 h 21.24% 20.31% 20.05% 18.73% 19.53%
    6–12 h 21.34% 21.92% 20.79% 19.89% 20.36%
    0–6 h 34.19% 36.31% 36.98% 37.67% 37.91%
    TABLE A3. Percentage of satisfied demand assigned to level 2 stations per time period with a 600 m radius.
    # of randomly generated points
    Period 100 150 200 250 300
    18–24 h 23.68% 23.39% 23.44% 23.36% 23.25%
    12–18 h 22.02% 21.52% 21.54% 21.62% 21.43%
    6–12 h 22.60% 22.10% 22.21% 22.17% 22.02%
    0–6 h 31.70% 32.99% 32.82% 32.85% 33.30%
    TABLE A4. Percentage of satisfied demand assigned to level 3 stations per time period with a 600 m radius.
    # of randomly generated points
    Period 100 150 200 250 300
    18–24 h 24.14% 23.61% 22.71% 23.02% 23.81%
    12–18 h 21.55% 22.09% 21.20% 19.58% 21.10%
    6–12 h 21.67% 22.71% 21.15% 20.68% 21.80%
    0–6 h 32.64% 31.60% 34.94% 36.71% 33.29%
    TABLE A5. Percentage of satisfied demand assigned to level 2 stations per time period with a 700 m radius.
    # of randomly generated points
    Period 100 150 200 250 300
    18–24 h 23.27% 23.35% 23.27% 23.34% 23.21%
    12–18 h 21.45% 21.45% 21.44% 21.58% 21.52%
    6–12 h 22.06% 22.05% 22.10% 22.11% 22.13%
    0–6 h 33.22% 33.16% 33.19% 32.97% 33.13%
    TABLE A6. Percentage of satisfied demand assigned to level 3 stations per time period with a 700 m radius.
    # of randomly generated points
    Period 100 150 200 250 300
    18–24 h 23.99% 22.76% 23.70% 22.87% 23.95%
    12–18 h 21.88% 21.19% 21.55% 19.99% 20.41%
    6–12 h 22.40% 21.77% 21.77% 21.44% 21.12%
    0–6 h 31.73% 34.28% 32.98% 35.69% 34.52%
    Details are in the caption following the image
    FIGURE A1
    Open in figure viewerPowerPoint
    Example of satisfied demand over time periods ( R = 700 , W = 300 $$ R=700,W=300 $$ ). (A) 0–6 h. (B) 6–12 h. (C) 12–18 h. (D) 18–24 h.

    A.2 Detailed results for Section 4.3

    Tables A7–A12 provide detailed results with respect to the satisfied demand, solving times and optimality gap for each of our instances.

    TABLE A7. Satisfied demand for Program (2a-2k) over a single period.
    Budget
    0 100 200 300 400 500 600 700
    100 points
    Instance 1 62.38% 89.14% 95.48% 98.85% 99.86% 99.99% 100.00% 100.00%
    Instance 2 67.84% 88.43% 95.79% 98.73% 99.90% 99.99% 100.00% 100.00%
    Instance 3 57.72% 84.21% 93.54% 97.88% 99.64% 99.99% 100.00% 100.00%
    Instance 4 67.81% 92.85% 97.90% 99.79% 100.00% 100.00% 100.00% 99.99%
    Instance 5 65.85% 85.46% 93.54% 97.62% 99.60% 100.00% 100.00% 100.00%
    150 points
    Instance 1 76.49% 90.04% 95.07% 97.73% 99.24% 99.87% 99.99% 100.00%
    Instance 2 69.97% 86.27% 93.51% 97.23% 98.90% 99.75% 99.99% 100.00%
    Instance 3 67.54% 83.65% 91.04% 95.15% 97.85% 99.24% 99.88% 99.99%
    Instance 4 76.47% 91.74% 95.81% 98.11% 99.44% 99.91% 100.00% 100.00%
    Instance 5 75.85% 87.30% 93.43% 96.86% 98.81% 99.63% 99.96% 99.99%
    200 points
    Instance 1 77.00% 88.84% 92.87% 95.91% 97.61% 98.84% 99.53% 99.92%
    Instance 2 74.86% 86.25% 91.79% 95.35% 97.42% 98.66% 99.47% 99.88%
    Instance 3 71.38% 83.16% 89.46% 93.48% 96.01% 97.92% 99.02% 99.67%
    Instance 4 79.68% 91.13% 94.77% 96.90% 98.45% 99.27% 99.79% 99.97%
    Instance 5 76.56% 86.06% 91.46% 94.88% 97.07% 98.54% 99.32% 99.81%
    TABLE A8. Computing time (s) for Program (2a-2k) over a single period.
    Budget
    0 100 200 300 400 500 600 700
    100 points
    Instance 1 0.078 7.156 447.078 80.485 95.047 0.546 0.437 0.469
    Instance 2 0.063 7.625 10.079 27.375 19.578 1.016 0.5 0.406
    Instance 3 0.078 6.672 16.609 29.156 91.062 7.297 0.343 0.375
    Instance 4 0.063 5.282 55.266 14.563 0.281 0.328 0.328 0.422
    Instance 5 0.063 6.047 18.282 926.094 88.515 6.063 0.406 0.344
    150 points
    Instance 1 0.14 413.594 103.828 1800 861.797 1536.781 23.718 0.735
    Instance 2 0.172 33.578 133.328 64.75 657.157 655.625 830.922 0.906
    Instance 3 0.172 418.547 42.125 1800 587.137 1800 1031.094 2.453
    Instance 4 0.171 14.468 78.828 959.875 503.063 1800 1.578 0.75
    Instance 5 0.172 228.953 92.187 312.156 258.016 942.156 693.094 0.969
    200 points
    Instance 1 0.328 254.719 1800 1800 1800 1800 1800 1800
    Instance 2 0.282 11.719 413.36 1224.313 1428.156 1800 1800 1800
    Instance 3 0.421 665.766 468.86 1800 1800 1800 1800 1800
    Instance 4 0.36 12.235 61.734 1800 1090 1800 1800 1800
    Instance 5 0.344 64.187 94.297 813.891 1800 1800 1800 1800
    TABLE A9. Optimal gap for Program (2a-2k) over a single period.
    Budget
    0 100 200 300 400 500 600 700
    100 points
    Instance 1 0.00% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00% 0.00%
    Instance 2 0.00% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00%
    Instance 3 0.00% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00%
    Instance 4 0.00% 0.01% 0.01% 0.01% 0.00% 0.00% 0.00% 0.01%
    Instance 5 0.00% 0.01% 0.00% 0.01% 0.01% 0.00% 0.00% 0.00%
    150 points
    Instance 1 0.00% 0.01% 0.01% 0.02% 0.01% 0.01% 0.01% 0.00%
    Instance 2 0.00% 0.00% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00%
    Instance 3 0.00% 0.01% 0.01% 0.07% 0.01% 0.10% 0.01% 0.01%
    Instance 4 0.00% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00%
    Instance 5 0.00% 0.01% 0.01% 0.01% 0.01% 0.01% 0.01% 0.01%
    200 points
    Instance 1 0.00% 0.01% 0.33% 0.02% 0.45% 0.84% 0.36% 0.08%
    Instance 2 0.00% 0.00% 0.01% 0.01% 0.01% 0.48% 0.24% 0.09%
    Instance 3 0.00% 0.01% 0.01% 0.01% 0.23% 0.19% 0.58% 0.33%
    Instance 4 0.00% 0.01% 0.01% 0.06% 0.01% 0.42% 0.13% 0.02%
    Instance 5 0.00% 0.01% 0.01% 0.01% 0.09% 0.09% 0.38% 0.14%
    TABLE A10. Satisfied demand for Program (2a-2k) over multiple periods.
    Budget
    0 100 200 300 400 500 600 700
    100 points
    Instance 1 62.28% 84.66% 92.94% 97.24% 99.36% 99.97% 100.00% 100.00%
    Instance 2 66.20% 84.82% 93.56% 97.35% 99.56% 99.98% 100.00% 100.00%
    Instance 3 57.30% 79.99% 89.82% 95.76% 98.73% 99.91% 100.00% 100.00%
    Instance 4 67.32% 89.24% 96.26% 99.12% 99.97% 100.00% 100.00% 100.00%
    Instance 5 63.91% 80.23% 89.48% 95.71% 98.66% 99.87% 100.00% 100.00%
    150 points
    Instance 1 74.87% 87.65% 93.26% 96.79% 98.59% 99.60% 99.97% 100.00%
    Instance 2 69.85% 84.17% 91.67% 96.09% 98.19% 99.49% 99.93% 100.00%
    Instance 3 66.03% 80.83% 88.18% 93.23% 96.55% 98.57% 99.63% 99.97%
    Instance 4 75.62% 89.24% 94.38% 97.23% 98.87% 99.73% 99.99% 100.00%
    Instance 5 74.39% 85.71% 91.73% 95.92% 98.17% 99.40% 99.87% 99.99%
    200 points
    Instance 1 76.12% 87.07% 91.73% 94.82% 97.00% 98.13% 99.34% 99.78%
    Instance 2 74.03% 84.38% 90.70% 94.28% 96.50% 98.13% 99.17% 99.76%
    Instance 3 70.63% 81.66% 87.76% 91.96% 95.03% 97.21% 98.50% 99.46%
    Instance 4 78.51% 89.43% 93.77% 96.27% 97.88% 99.00% 99.67% 99.87%
    Instance 5 76.33% 85.31% 90.39% 94.09% 96.45% 98.14% 99.12% 99.72%
    TABLE A11. Computing time (s) for Program (2a-2k) over multiple periods.
    Budget
    0 100 200 300 400 500 600 700
    100 points
    Instance 1 0.313 9.657 34.235 720.25 1037.297 1308.797 1.922 1.781
    Instance 2 0.344 20.422 52.828 1800 222.047 946.719 1.844 1.906
    Instance 3 0.422 10.203 41.359 210.234 833.25 743.031 2.234 2.25
    Instance 4 0.375 19.437 24.532 97.797 266.703 1.406 1.625 2.188
    Instance 5 0.36 51.422 185.687 181.938 1800 1800 2.25 2.343
    150 points
    Instance 1 0.922 152.844 1006.859 1421.375 1800 1800 1800 9.109
    Instance 2 1.39 55.203 455.813 802.36 1800 1800 1800 29.891
    Instance 3 1.047 43.203 1116.75 1800 1800 1800 1800 1800
    Instance 4 1.969 34.469 224.922 669.594 1800 1800 218.344 4.781
    Instance 5 1.563 73.453 1800 1800 1800 1800 1800 9.969
    200 points
    Instance 1 2.156 496.344 1800 1800 1800 1800 1800 1800
    Instance 2 2.046 158.906 1765.328 1800 1800 1800 1800 1800
    Instance 3 6.375 97.516 1800 1800 1800 1800 1800 1800
    Instance 4 2.984 117.078 839.344 1800 1800 1800 1800 1800
    Instance 5 3.75 221.328 1800 1800 1800 1800 1800 1800
    TABLE A12. Optimal gap for Program (2a-2k) over multiple periods.
    Budget
    0 100 200 300 400 500 600 700
    100 points
    Instance 1 0.00% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00%
    Instance 2 0.00% 0.01% 0.01% 0.09% 0.01% 0.01% 0.00% 0.00%
    Instance 3 0.00% 0.01% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00%
    Instance 4 0.00% 0.01% 0.01% 0.01% 0.01% 0.00% 0.00% 0.00%
    Instance 5 0.00% 0.01% 0.01% 0.01% 0.14% 0.05% 0.00% 0.00%
    150 points
    Instance 1 0.00% 0.01% 0.01% 0.01% 0.95% 0.40% 0.03% 0.00%
    Instance 2 0.00% 0.01% 0.01% 0.01% 0.44% 0.44% 0.07% 0.00%
    Instance 3 0.00% 0.01% 0.01% 0.23% 1.56% 1.17% 0.37% 0.03%
    Instance 4 0.00% 0.01% 0.01% 0.01% 0.66% 0.27% 0.01% 0.00%
    Instance 5 0.00% 0.01% 0.09% 0.03% 0.07% 0.45% 0.13% 0.01%
    200 points
    Instance 1 0.00% 0.01% 0.31% 2.34% 2.33% 1.90% 0.66% 0.22%
    Instance 2 0.00% 0.01% 0.01% 2.26% 2.24% 1.82% 0.84% 0.24%
    Instance 3 0.00% 0.01% 0.34% 3.21% 3.69% 2.85% 1.52% 0.54%
    Instance 4 0.00% 0.01% 0.01% 1.15% 0.97% 0.99% 0.33% 0.13%
    Instance 5 0.00% 0.01% 0.46% 2.79% 2.73% 1.89% 0.88% 0.28%

    DATA AVAILABILITY STATEMENT

    The data that supports the findings of this study cannot be shared due to privacy, ethical, and ownership restrictions.

    The full text of this article hosted at iucr.org is unavailable due to technical difficulties.