<figure><img src="image_1.png" /></figure>

HAL
open science

# Optimal Electric Vehicle Charging with Dynamic Pricing, Customer Preferences and Power Peak Reduction

Miguel F Anjos, Luce Brotcorne, Gaël Guillot

► To cite this version:

Miguel F Anjos, Luce Brotcorne, Gaël Guillot. Optimal Electric Vehicle Charging with Dynamic Pricing, Customer Preferences and Power Peak Reduction. INFOR: Information Systems and Operational Research, In press, 10.1080/03155986.2025.2463189. [hal-04812283v2](https://hal.science/hal-04812283v2)

HAL Id: hal-04812283

https://hal.science/hal-04812283v2

Submitted on 7 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Optimal Electric Vehicle Charging with Dynamic Pricing, Customer Preferences and Power Peak Reduction

Miguel F. Anjos¹, Luce Brotcorne², and Gaël Guillot³

¹School of Mathematics, University of Edinburgh, UK; anjos@stanfordalumni.org

²INRIA Lille Nord-Europe, Lille, France; luce.brotcorne@inria.fr

³INRIA Lille Nord-Europe, Lille, France; gael.guillot@inria.fr

## Abstract

We consider a provider of electric vehicle charging stations that operates a network of charging stations and use time varying pricing to maximize profit and reduce the impact on the electric grid. We propose a bilevel model with a single leader and multiple disjoint followers. The customers (followers) make decisions independently from each other. The provider (leader) sets the price of charging for each station at each time slot, and ensures there is enough energy to charge. The charging choice of each customer is represented by a combination of a preference list of (station, time) pairs and a reserve price. The proposed model takes thus into accounts for the heterogeneity of customers with respect to price sensitivity and charging preferences. We define a single-level reformulation based on a reformulation approach from the literature on product line optimization, and we report computational results that highlight the efficiency of the new reformulation and the potential impact of our approach for reducing peaks on the electricity grid.

Electric vehicle charging, Dynamic pricing, Bilevel optimization, Preference list, Reserve price

## 1 Introduction

Due to many political and environmental incentives, the number of electric vehicles (EVs) has increased dramatically in recent years, especially in urban areas. This rapid growth creates a large number of operational challenges for charging service providers. Three issues arising from the rapid increase in the number of EVs are highlighted in [24]: a worsening in the peak-to-valley difference grid load leading to a cost increase and a deterioration in the service quality of the networks and installations, a difficulty in meeting the demand of customers, and an inequitable distribution of customers among the stations leading to congestion.

In this paper we propose a novel pricing model to address these issues. Specifically, we address the problem of an charging provider that operates a network of charging stations and wishes to apply a dynamic pricing strategy to spread the customers in time and space in order to maximize the profit and reduce the negative grid impacts as well as queues at charging stations. We refer to this problem as Dynamic Pricing Electric Vehicles problem (DPEV).
The literature on charging station management may be classified according to three characteristics: design issues, pricing issues, and joint design & pricing issues. We refer to [17] for a survey. In particular, it is important to manage the location of charging stations (see e.g. [12, 2, 16, 20]), the size of the stations to avoid queues (see e.g. [23]), as well as the impact of charging on the electricity grid (see e.g. [18, 21]). For example, the paper [14] is concerned with the location and sizing of charging stations to maximize profit, considering the costs of installation, operation, and maintenance. We note that while the focus in on the infrastructure aspects, the authors take into account the travel times of drivers, the queueing time for charging, and the charging price elasticity of customers. This is done using traffic congestion and demand elasticity models. The authors also point out the importance of power grid and station upgrades to keep pace with increasing charging demand.

Our focus in on pricing. A significant body of research has been carried out on how pricing can better support the use of the charging infrastructure by adjusting the price of charging depending on location and time of day so as to improve the distribution of demand (e.g., [9], [13], [19]). Indeed pricing is a key element in the distribution of customers: too attractive prices result in: i) queues at charging stations; ii) failure to meet the demand; and iii) high peaks on the distribution grid; on the other hand, too high prices deter customers from charging at this time and location and thus reduce the revenue and create potential future grid imbalances. The authors in [17] define different criteria to characterize dynamic pricing and describe multiple implementations.

Our modelling approach is based on the fact that when solving the *DPEV*, charging providers must take into account the response from customers when setting the prices for charging. This motivates the use of bilevel optimization. Bilevel models are well suited to represent hierarchical decision-making processes involving two types of decision agents, and have already been used for addressing questions about charging stations. For example, [4] study the locating of stations for congested traffic networks where users must recharge to complete their trips. This leads to a bilevel setting where the upper-level agent, given a budget, seeks to locate stations to minimize the travel time, and the lower-level agent represents a user equilibrium based on the choice of routes by the users such that no user can achieve a shorter travel time by switching to a different route.

In this vein of research, the recent paper [15] develops a bilevel model to locate stations so as to minimize total costs. This work ingeniously combines a variety of optimization tools. The model simulates vehicle route using a *k*-shortest path arc-based flow model. The user waiting times are modelled following a Poisson distribution, reflecting an M/M/c queuing system, and solved using a logit-based Benders decomposition. The approach considers optimistic and pessimistic user responses, specifically addressing pessimism by bounding waiting times. Finally, the required service levels are enforced using chance constraints.

Like [4] and [15], most papers in the literature related to charging pricing problems are based on the utility maximization paradigm. More precisely, they determine the choice of the path of the customers in the network according to travel time, price of charging, and potential queuing time at stations (see [3],[10],[11],[22] for example). One limitation of this modelling approach is that it assumes that the customer typically makes a decision by measuring some attributes of the product. However, customers may be partially rational or may fail to evaluate all attributes related to an alternative. Another limitation, from the computational perspective, is that the evaluation of the attributes related to the path
choices frequently require the use of tailor-made solution methods to solve large instances
due to the large number of potential paths.

In this paper, we consider a non-parametric ranking-based consumer choice model,
assuming that each customer possesses its own ranking of the candidate charging oppor-
tunities (products), yielding an incomplete list of preferences for each customer. This
alternative approach was recently proposed in [1] where the behaviour of customers is
represented using a preference list and a reserve price (maximum price threshold). The
approach in [1] uses a bilevel optimization formulation in which the upper-level models
the charging service provider that seeks to locate, size and price charging stations to
maximize its profit, while the lower-level models customers who individually select the
first available charging station from their preference list that meets the customer's reserve
price.

In this paper, we define a bilevel optimization model for the *DPEV* representing
the heterogeneous customer decision process as the choice of a location and time to
charge in a predefined preference list related to a reserve price [7]. We consider a single
charging station manager and do not take into account the reaction of the competition.
Unlike in [1] and [7], we fix the locations and sizes of the charging stations are fixed in
advance, and the focus of our work is on determining the optimal prices and quantities
of energy (recharges) to maximize profit, where the profit is the difference between the
revenue from providing recharges to customers and the cost of the required energy. We
provide an efficient solution approach based on the structure of the problem and the
work of [6] for product line optimization. We note that while the structure of the bilevel
model in [6] shares some similarities with our proposed model, there are some important
differences, including our use of preference lists and the time dependence of the decisions.
The resulting single-level reformulation leads to the solution of a mixed-integer linear
optimization problem. We report computational results highlighting the ability of our
approach to solve instances with up to 5000 customers to global optimality in less than
4 minutes. We also discuss sensitivity analysis results related to the tradeoff between
revenue and electrical grid peak reductions.

The remainder of the paper is organized as follows. Section 2 introduces our proposed
formulation for optimal charging. Section 3 presents the single-level reformulations for
the bilevel model, as well as two illustrative examples of the structure of the solutions
to our model. Section 4 reports the results of our computational experiments to assess
the performance of the model and the various solution approaches. Finally, Section 5
concludes the paper.

2 Bilevel Model for DPEV

Problem *DPEV* involves two decision-makers interacting sequentially and hierarchically.
An electricity provider (the leader) needs to define time-varying prices associated with
charging stations as well as the quantity of energy allocated to each station, taking into
account the preferences of the customers (the followers) with respect to the place and
time period to charge.

More precisely, the provider is in charge of a set S of charging stations; each one has
a capacity δs representing the number of charging spots at the station. The electricity
cost for the service provider is denoted by c_t, ∀t ∈ T, where t ∈ T is a time period.
The service provider needs to select the price to charge customers for each pair (station,
time). The possible prices belong to a discrete set Π common to all pairs (station, time). We define a charging unit as the complete charge of a vehicle, and the charging time is not taken into account.

The set of customers is denoted by $U$. Each customer needs to charge exactly one unit of energy during his trip. We introduce a fictitious station $s^A$ that represents the competition to avoid upward pricing due to this constraint. Competition is only introduced to prevent users from being forced to recharge on the network (and therefore accept unreasonable prices), which is why we are not considering capacity constraints for these stations for feasibility reasons. Each customer has a budget $\beta_u$, and we consider that a customer charges in a competing station if the leader's prices exceed his budget. This budget can be seen as a reserve price for the customer.

For fixed price schedules determined by the leader, the customers will select the place and time to charge according to a predefined preference list. The preference list corresponds to an ordered set of station/time pairs where a customer agrees to charge if the leader's price does not exceed his budget. In practice, these preferences may be determined via surveys, or alternatively, for a charging provider that has been in business for some time, the past behaviour of customers may inform how to set up the preference lists.

<figure><img src="image_3.png" /><figcaption>Figure 1: Representation of a customer's route using (station, time) pairs.</figcaption></figure>

Let $R_u$ be the ordered list of pairs (station, time) for customer $u$, and $R_u^\ell$ correspond to the $\ell^{st}$ pair (station,time) in the ordered list $R_u$ ($\forall \ell \in 1, ..., |R_u|$). Customer $u$ prefers to load at pair $R_u^\ell$ rather than $R_u^{\ell'}$ if $\ell < \ell'$ (ordered in decreasing order of preferences). For a given pair $(s, t) \in S \times T$, the set $L_{s,t}$ is defined by all pairs $(u, \ell)$ such that

$$ (u, \ell) \in L_{s,t} \text{ if and only if } R_u^\ell = (s, t). $$

The set $L_{s,t}$ corresponds to all pairs $(u, \ell)$ such that the $\ell^{th}$ choice in the preference list for $u$ is $(s, t)$. For each customer $u \in U$, $\alpha_u$ defines the monetary inconvenience of each pair in his preference list. More precisely, a customer of $u$ undergoes a penalty $\ell \alpha_u$ if he charges at the $\ell^{th}$ choice of his preference list.

The parameters of the model are summarized in Table 1.
<table><caption>Table 1: Model parameters</caption><tr><td>S</td><td>set of charging stations</td></tr><tr><td>T</td><td>time periods</td></tr><tr><td>U</td><td>set of customers</td></tr><tr><td>δ<sub>s</sub></td><td>number of charging spots for station s ∈ S</td></tr><tr><td>s<sup>A</sup></td><td>fictitious station</td></tr><tr><td>Π</td><td>discrete ordered set of prices</td></tr><tr><td>c<sub>t</sub></td><td>cost of one unit of energy available at time period t ∈ T for the leader</td></tr><tr><td>R<sub>u</sub></td><td>preference list of customer u ∈ U</td></tr><tr><td>β<sub>u</sub></td><td>budget of customer u ∈ U</td></tr><tr><td>α<sub>u</sub></td><td>monetary inconvenience for customer u ∈ U</td></tr><tr><td>L<sub>s,t</sub></td><td>set of pairs (customer, choice) corresponding to (s, t), s ∈ S, t ∈ T</td></tr></table>

We next introduce three sets of decision variables:

* Variables $x_s^t$ are the number of energy charging units available (at cost $c_t$) for station $s$ at time $t$.

* Variables $y_u^{\ell,p}, \forall u \in U, \ell \in \{0, ..., |R_u| - 1\}, p \in \{1, ..., |\Pi|\}$ are binary and $y_u^{\ell,p} = 1$ if customer $u$ charges at station and time corresponding to his $\ell^{th}$ choice at the $p^{th}$ price.

* Finally, variables $\theta_p^{s,t}, \forall p \in \{1, ..., |\Pi|\}, s \in S, t \in T$ are binary and $\theta_p^{s,t} = 1$ if the price of station $s$ at time $t$ is fixed to $\Pi_p$.
The problem DPEV can be formulated as:

$$ \textbf{DPEV}: \max_{x,y,\theta} \sum_{u \in U} \sum_{\ell=0}^{|R_u|-1} \sum_{p=1}^{|\Pi|} \Pi_p y_u^{\ell,p} - \sum_{t \in T} \sum_{s \in S} x_s^t c_t \quad (2a) $$

$$ \text{s.t.} \quad \sum_{p=1}^{|\Pi|} \theta_p^{s,t} = 1 \quad \forall (s,t) \in S \times T \quad (2b) $$

$$ \sum_{(u,\ell) \in L_{s,t}} \sum_{p=1}^{|\Pi|} y_u^{\ell,p} \le x_s^t \quad \forall (s,t) \in S \times T \quad (2c) $$

$$ \sum_{(u,\ell) \in L_{s,t}} \sum_{p=1}^{|\Pi|} y_u^{\ell,p} \le \delta_s^t \quad \forall (s,t) \in S \times T \quad (2d) $$

$$ x_s^t \in \mathbb{N}, \quad \forall (s,t) \in S \times T \quad (2e) $$

$$ \theta_p^{s,t} \in \{0,1\}, \quad \forall (s,t) \in S \times T, p \in \{1, \dots, |\Pi|\} \quad (2f) $$

For each $\tilde{u} \in U$:

$$ \min_{y_{\tilde{u}}} \sum_{p=1}^{|\Pi|} \sum_{\ell=0}^{|R_{\tilde{u}}|-1} y_{\tilde{u}}^{\ell,p} (\Pi_p + \ell \times \alpha_{\tilde{u}}) + y_{\tilde{u}}^{s,A} \beta_{\tilde{u}} \quad (2g) $$

$$ \text{s.t.} \quad \sum_{\ell=0}^{|R_{\tilde{u}}|-1} \sum_{p=1}^{|\Pi|} y_{\tilde{u}}^{\ell,p} + y_{\tilde{u}}^{s,A} = 1 \quad (2h) $$

$$ y_{\tilde{u}}^{\ell,p} \le \theta_p^{s(\ell),t(\ell)}, \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\} \quad (2i) $$

$$ y_{\tilde{u}}^{\ell,p} (\Pi_p + \ell \times \alpha_{\tilde{u}}) \le \beta_{\tilde{u}}, \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\} \quad (2j) $$

$$ y_{\tilde{u}}^{\ell,p} \in \{0,1\}, \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\}. \quad (2k) $$

At the upper level, the leader maximizes its profit by determining the prices $\theta_p^{s,t}$ and the quantities of energy $x_s^t$ for each time $t \in T$ and each station $s \in S$. The Profit is the difference between revenue from energy sales to customers and the cost of energy purchases.

Constraints (2b) define a single price for each pair (station, time). The last constraints are capacity constraints, with respect to the demand (2c) and the number of available spots (2d) in the charging stations. At the lower-level, each customer selects the pair in his preference list, minimizing the total cost of charging, including the penalty for the inconvenience due to the order of the choices in the list.

Constraint (2h) defines a customer's choice for charging at a station from the leader or to the competition. Constraints (2i) ensure that customers' choices are consistent with the prices set by the leader. Note that the budget constraints (2j) are redundant with respect to the objective function. Nevertheless, they will be useful for the next reformulations.
DPEV is a linear bilevel optimization problem. One of the particularities DPEV is the definition of constraints (2c) and (2d) at the upper level. The leader sets prices, ensuring that the followers' capacity is satisfied. Note that in the case of the non unicity of the solution of the followers for fixed leader's decisions, we assume that the followers select the solution leading to the highest objective function value of the leader. Thus, we consider the optimistic version of a bilevel optimization problem.

To take into account the impact of the grid peak consumption on the pricing decisions, we introduce a new term in the leader's model. We first define $\tilde{T}$ as the set of critical periods that correspond to the periods of time during which we wish to limit demand because of exogenous constraints (for example, more limited production at night). For each time period $t \in \tilde{T}$, the consumption at that period must be no more than $X^t$.

The new leader's constraints are then given by:

$$ \sum_{s \in S} \sum_{(u, \ell) \in L_{s,t}} \sum_{p=1}^{|\Pi|} y_u^{\ell, p} \leq X^t \quad \forall t \in \tilde{T}. $$

The leader therefore has several constraints on peak consumption over certain periods of time, which may be given by an external player, for example, or to match the energy demand on the rest of the network. The proposed prices must take these constraints into account in order to dispatch users according to these peaks. We call this model DPEV-P:

$$ \textbf{DPEV-P}: \max_{x,y,\theta,X} \sum_{u \in u} \sum_{\ell=0}^{|R_u|-1} \sum_{p=1}^{|\Pi|} \Pi_p y_u^{\ell, p} - \sum_{t \in T} \sum_{s \in S} x_s^t c_t \quad (3a) $$

$$ \text{s.t.} \quad \sum_{s \in S} \sum_{(u, \ell) \in L_{s,t}} \sum_{p=1}^{|\Pi|} y_u^{\ell, p} \leq X^t \quad \forall t \in \tilde{T} \quad (3b) $$

$$ (2b)-(2k) \qquad X^t \in \mathbb{R} \quad \forall t \in \tilde{T}. \quad (3c) $$

# 3 Single-level Reformulations of DPEV

In this section, we first present in Section 3.1 a single-level mixed-integer reformulation of DPEV based on the work of [6] for the product line optimization problem. In Section 3.2, we recall the standard KKT-based single-level reformulations that can also be used to reformulate DPEV, and in Section 3.3 we use illustrative examples to provide some insights into the structure of the solutions of our model.

## 3.1 Linear single-level Reformulation

We define for each customer $u \in U$ an order relation $\leq_u$ which for two pairs $(\ell, p), (\ell', p')$, $\ell, \ell' \in \{0, ..., |R_u| - 1\}$ and $p, p' \in \{1, ..., |\Pi|\}$ defines the most beneficial for the customer. The order relation is given by

$$ (\ell, p) \leq_u (\ell', p') \text{ if } \Pi_p + \ell\alpha_u \geq \Pi_{p'} + \ell'\alpha_u. $$
The set of pairs $(\ell', p')$ preferred to $(\ell, p)$ for a customer $u$ is defined by:

$$ \mathcal{B}_{u,\ell,p} = \{(\ell', p'), \ell' \in R_u | (\ell, p) \preceq_u (\ell', p')\}. \quad (4) $$

Finally, we define an indicator of whether the competition is more beneficial than the pair $(\ell, p)$ or not.

$$ \forall u \in U, \ell \in R_u, p \in \{1, \dots, |\Pi|\}, C_{u,l,p} = \begin{cases} 1, & \text{if}(\ell \times \alpha_u) + \Pi_p \ge \beta_u \\ 0, & \text{otherwise.} \end{cases} \quad (5) $$

**Proposition 1** For each customer $u$, a feasible vector $y_u$ is optimal for the lower-level problem if the following constraints are satisfied:

$$ \sum_{(\ell', p') \in \mathcal{B}_{u, \ell, p}} y_u^{\ell', p'} + C_{u, \ell, p} y_u^{s^A} \ge \theta_p^{s(\ell), t(\ell)}, \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\}. $$

Let $y_u$ be a feasible vector satisfying the constraints. Since $y_u$ is a feasible solution for customer $u$, we know that there exists a unique pair $(\ell, p)$ such as $y_u^{\ell, p} = 1$ (constraint 2h). To obtain a contradiction, suppose that $y_u$ is not optimal for customer $u$, then there exists a pair $(\ell^*, p^*)$ such as $(\Pi_{p^*} + \ell^* \times \alpha_u) < (\Pi_p + \ell \times \alpha_u)$ (given by the objective function) and $\theta_{p^*}^{s(\ell^*), t(\ell^*)} = 1$ (given by (2i)). By (4), $(\ell, p) \notin \mathcal{B}_{u, \ell^*, p^*}$. As a consequence, the constraint corresponding to $(\ell^*, p^*)$ is not respected:

$$ \sum_{(\ell', p') \in \mathcal{B}_{u, \ell^*, p^*}} y_u^{\ell', p'} + C_{u, \ell^*, p^*} y_u^{s^A} = 0 \text{ and } \theta_{p^*}^{s(\ell^*), t(\ell^*)} = 1. $$

Using Proposition 1, the single-level reformulation is:

$$ \textbf{DPEV}^{SL}: \max_{x,y,\theta} \sum_{u \in U} \sum_{\ell=0}^{|R_u|-1} \sum_{p=1}^{|\Pi|} \Pi_p y_u^{\ell,p} - \sum_{t \in T} \sum_{s \in S} x_s^t c_t \quad (6a) $$

$$ \text{s.t.} \quad (2b), (2c), (2d), (2h), (2j) $$

$$ \sum_{(u, \ell) \in L_{s,t}} y_u^{\ell, p} \le \theta_p^{s,t} |U| \quad \forall (s,t) \in S \times T, p \in \{1, \dots, |\Pi|\} \quad (6b) $$

$$ \sum_{(\ell', p') \in \mathcal{B}_{u, \ell, p}} y_u^{\ell', p'} + C_{u, \ell, p} y_u^{s^A} \ge \theta_p^{s(\ell'), t(\ell')}, \forall u \in U, \ell \in R_u, p \in \{1, \dots, |\Pi|\} \quad (6c) $$

$$ x_s^t \in \mathbb{N} \quad (6d) $$

$$ \theta_p^{s,t} \in \{0, 1\}, \quad \forall (s,t) \in S \times T, p \in \{1, \dots, |\Pi|\} \quad (6e) $$

$$ y_u^{\ell, p} \in \{0, 1\} \quad \forall u \in U, \ell \in \{0, \dots, |R_u| - 1\}, p \in \{1, \dots, |\Pi|\}. \quad (6f) $$

Optimality conditions for the lower-level are given by (6c). Constraint (6b) ensures consistency between the prices set by the leader and the prices chosen by the customers. Constraint (6b) corresponds to the aggregation of constraints 2i.
Problem DPEV<sup>SL</sup> can be solved with a mixed-integer linear solvers. As we have not added a constraint in the follower problem, we can use the same reformulation for the problem (DPEV − P).

$$
\mathbf{DPEV} - \mathbf{P}^{SL}: \max_{x,y,\theta,X} \sum_{u \in U} \sum_{\ell=0}^{|R_u|-1} \sum_{p=1}^{|\Pi|} \Pi_p y_u^{\ell,p} - \sum_{t \in T} \sum_{s \in S} x_s^t c_t \quad (7a)
$$

$$
\text{s.t.} \quad \sum_{s \in S} \sum_{(u,\ell) \in L_{s,t}} \sum_{p=1}^{|\Pi|} y_u^{\ell,p} \le X^t \quad \forall t \in \tilde{T} \quad (7b)
$$

$$
(2b), (2c), (2d), (2h), (2j), (6b), (6c), (6d), (6e), (6f)
$$

$$
X^t \in \mathbb{R} \quad \forall t \in \tilde{T}. \qquad (7c)
$$

3.2 Classical single-level reformulation based on KKT optimality con-
ditions

In this section, we present a classical reformulation of a bilevel optimization problem as a
single-level one based on the Karush-Kuhn-Tucker optimality conditions. We first prove
that the linear relaxation of the lower-level problem is equivalent to the initial one.

**Proposition 2** For each follower problem SP<sub>u</sub>, the linear relaxation is equivalent to the initial problem.

Each sub-problem can be formulated as a min-cost flow problem in a graph. The upper-level variables $\theta^{\ell,p}$ represent the arc capacity. The cost of an arc is given by its contribution to the objective function. A final arc, of capacity 1, represents the competition. Because the constraint matrix of this type of problem is totally unimodular, the optimal solution of the linear relaxation is always integer.

<figure><img src="image_4.png" /><figcaption>Figure 2: Representation of the follower problem as a min-cost flow problem.</figcaption></figure>

The KKT optimal conditions can replace each follower sub-problem. In this approach,
the lower-level’s optimality conditions (stationarity, primal feasibility, dual feasibility,
complementary slackness) are added to the upper level to yield an equivalent single-level
formulation. Linearization techniques need to be applied to obtain a mixed-integer linear
program.
The second-level variable integrality constraints are next reintroduced into the leader problem. Because the lower-level problem is totally unimodular, there are always optimal lower-level solutions that meet the integrality requirements, and these, according to the 'optimistic' assumption, can be selected by the leader. In the following, we describe the conditions obtained for one customer. Recall that the sub-problem for customer $\tilde{u}$ is given by:

$$ \min_{y_{\tilde{u}}} \sum_{p=1}^{|\Pi|} \sum_{\ell=0}^{|R_{\tilde{u}}|-1} y_{\tilde{u}}^{\ell,p} (\Pi_p + \ell * \alpha_{\tilde{u}}) + y_{\tilde{u}}^{s^A} \beta_{\tilde{u}} \quad (8a) $$

$$ \sum_{\ell=0}^{|R_{\tilde{u}}|-1} \sum_{p=1}^{|\Pi|} y_{\tilde{u}}^{\ell,p} + y_{\tilde{u}}^{s^A} = 1 \quad (8b) $$

$$ y_{\tilde{u}}^{\ell,p} \le \theta_p^{s^A(\ell),t(\ell)}, \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\} \quad (8c) $$

$$ y_{\tilde{u}}^{\ell,p} (\Pi_p + \ell \times \alpha_{\tilde{u}}) \le \beta_{\tilde{u}}, \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\} \quad (8d) $$

$$ y_{\tilde{u}}^{\ell,p} \ge 0, \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\} \quad (8e) $$

$$ y_{\tilde{u}}^{s^A} \ge 0. \quad (8f) $$

**Remark 1** Integrality constraints are replaced by (8e). The condition $y_{\tilde{u}}^{\ell,p} \le 1$ is induced by (8b) and (8e).

The dual feasibility, complementary slackness, and stationarity are given by:

**Complementary slackness:**

$$ (y_{\tilde{u}}^{\ell,p} - \theta_p^{s^A(\ell),t(\ell)}) \mu_{\tilde{u}}^{\ell,p} = 0 \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\} \quad (9a) $$

$$ (y_{\tilde{u}}^{\ell,p} (\Pi_p + \ell \times \alpha_{\tilde{u}}) - \beta_{\tilde{u}}) \phi_{\tilde{u}}^{\ell,p} = 0 \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\} \quad (9b) $$

$$ y_{\tilde{u}}^{\ell,p} \Delta_{\tilde{u}}^{\ell,p} = 0 \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\} \quad (9c) $$

$$ y_{\tilde{u}}^{s^A} \Delta_{\tilde{u}}^{s^A} = 0. \quad (9d) $$

**Stationarity:**

$$ \Pi_p + \ell * \alpha_{\tilde{u}} + \lambda_{\tilde{u}} + \mu_{\tilde{u}}^{\ell,p} + \phi_{\tilde{u}}^{\ell,p} (\Pi_p + \ell \times \alpha_{\tilde{u}}) - \Delta_{\tilde{u}}^{\ell,p} = 0 \quad \forall \ell \in \{0, \dots, |R_{\tilde{u}}| - 1\}, p \in \{1, \dots, |\Pi|\} \quad (10a) $$

$$ \lambda_{\tilde{u}} - \Delta_{\tilde{u}}^{s^A} + \beta_{\tilde{u}} = 0 \quad (10b) $$

$$ \lambda_{\tilde{u}} \in \mathbb{R} \quad (10c) $$

$$ \mu_{\tilde{u}}^{\ell,p}, \phi_{\tilde{u}}^{\ell,p}, \delta_{\tilde{u}}^{\ell,p} \ge 0 \quad \forall \ell, p \quad (10d) $$

$$ \Delta_{\tilde{u}}^{s^A} \ge 0. \quad (10e) $$

The resulting problem is not linear because of the complementarity slackness. These constraints can be linearized using the big-M approach or solved directly using SOS1 constraints [5].
## 3.3 Illustrative examples

To give insight into the solution structure, we illustrate the impact of the model on small instances. Let us consider a first example involving three customers where only one customer will be able to charge during each time slot.

<figure><img src="image_5.png" /><figcaption>Figure 3: Illustration of an example with 3 customers with a preference list of 2 choices.</figcaption></figure>

$$R_{u_0} = \{(S_0, t_0); (S_0, t_1)\}$$
$$\beta_{u_0} = 110; \alpha_{u_0} = 30$$

$$R_{u_1} = \{(S_0, t_0); (S_1, t_0)\}$$
$$\beta_{u_1} = 150; \alpha_{u_1} = 10$$

$$R_{u_2} = \{(S_0, t_0); (S_1, t_0)\}$$
$$\beta_{u_2} = 90; \alpha_{u_2} = 15$$

$$\Pi = \{80; 100; 130\}$$

To capture customer $u_2$ (with a low budget), the price needs to be lower than 80, which corresponds to the pair $(S_0, t_0)$. This pair is also the preferred choice of the other two customers. As the number of chargers $\delta = 1$, it is impossible to set a price equal to 80 otherwise all customers will charge at $(S_0, t_0)$. Customer $u_2$ needs thus to go to the competing station in order to allow higher prices and higher revenue for the other customers. Customers $u_0$ and $u_1$ have the same first choice in their preference list but a different second choice. The prices need to be defined in such a way that at least one of them charges at his second choice. The optimal solution is given by:

$$\bullet \theta_{2}^{0,0} = \theta_{0}^{0,1} = \theta_{2}^{1,0} = \theta_{0}^{1,1} = 1$$

$$\bullet y_{0}^{1,0} = y_{1}^{1,2} = y_{2}^{s^{A}} = 1$$

and depicted in Figure 4. Note that this solution corresponds to an optimistic solution: the customer $U_0$ can charge at a competing station for the same price, but that solution is less advantageous for the leader.
<figure><img src="image_6.png" /><figcaption>Figure 4: Optimal solution of each customer with optimal prices.</figcaption></figure>

In some cases, bilevel feasibility is not guaranteed when pricing strategies do not lead to a distribution of customers in accordance with the charging stations' capacity constraints. More precisely, as the capacity limits are leader constraints, customers are not concerned with available spots at charging stations when they select their time and location charging pair. We illustrate how to remedy this drawback in the following example involving identical preference lists for all customers.

<figure><img src="image_7.png" /><figcaption>Figure 5: Bilevel infeasible example with two customers</figcaption></figure>

One way to guarantee bilevel feasibility is to include a very high price in $\Pi$ that makes a station/time pair unattractive to all customers. All the customers will then charge at the competition leading to a feasible solution. Such a price can be interpreted as the closure of a charging station.

**Proposition 3** If there exists $p \in \{0, ..., |\Pi|\}$ such that $\Pi_p > \max_{u \in U} \beta_u$, then problem
DPEV is bilevel feasible.

If all prices are set at $max_{u \in U} \beta_u$, all customers will charge at the competition, and capacity constraints will be satisfied. This solution is always bilevel feasible.

# 4 Computational experiments

In this section, we compare the performance of four solution approaches for DPEV on randomly generated instances and provide an extensive sensitivity analysis with respect to the parameter $\tilde{d}$ associated with the maximum consumption peak in the leader's objective function.

## 4.1 Instances and methods definition

We first describe the instance generation process. The number of stations and times are defined in such a way that the number of available units of energy is greater than the number of customers, i.e., $S \times T \times \delta > |U|$. Even if it is realistic to assume that the provider can satisfy all the demand, this condition is not necessary because feasibility is guaranteed in the worst case by Proposition 3.

We have generated instances ranging from 10 to over 5,000 customers.

The customer parameters are chosen randomly such that each customer possesses at least one charging option, satisfying the budget constraint (each customer's budget is greater than the lowest price from the set of possible prices).

We define probabilities to the (station, time) pairs selection process to avoid homogeneous distribution. In other words, some (station, time) pairs are more attractive for several customers and have a greater chance of being selected.

We next compare the performance of four solution approaches for DPEV (without the penalty on the grid peaks). The first one consists in applying the generic bilevel solver (GBS) proposed by [8] on the bilevel optimization formulation. The second and third methods consist in solving the MIP reformulation based on the KKT presented in Section 4 using two types of linearization techniques: the linearization based on big M (KKT BIGM), and the linearization using SOS1 constraints (KKT SOS). Finally the last one consists in solving the single-level reformulation defined in Section 3. Tests were performed on Intel Core i5-8350U 1.70 GHz 8GB for results on Table 2 and on a Mac Book Pro M1 with 16 Gb and CPLEX 20.1 as a MIP solver for the other.

## 4.2 Efficiency on solution methods on model DPEV

This section is focused on the study of the solution methods to solve model DPEV. For simplicity reasons we do not consider the term related to the peak in the leader's objective function. We first compare in Table 2 the results obtained by solving the single-level formulation $DPEV^{SL}$ defined in Section 3 by the MIP with the results obtained with a generic bilevel solver GBS.
<table><caption>Table 2: Comparison of the results obtained with our reformulation **DPEV<sup>SL</sup>** and a generic bilevel solver GBS. The number of instances solved to the optimum in 1 hour and the average solving time for 5 instances solved to the optimum are given for instances with each of 10, 20, and 30 customers.</caption><thead><tr><th>Instances</th><th colspan="2">DPEV<sup>SL</sup></th><th colspan="2">GBS</th></tr><tr><th>#customers</th><th>#OPT (1h)</th><th>Mean Time (solved)</th><th>#OPT (1h)</th><th>Mean Time (solved)</th></tr></thead><tbody><tr><td>10</td><td>5 / 5</td><td>0.04</td><td>5 / 5</td><td>6.22</td></tr><tr><td>20</td><td>5 / 5</td><td>0.03</td><td>4 / 5</td><td>628.91</td></tr><tr><td>30</td><td>5 / 5</td><td>0.03</td><td>2 / 5</td><td>1989.58</td></tr></tbody></table>

The bi-level solver is only able to solve instances with up to 30 customers in less than 1 hour. These experiments do not question the quality of the GBS but show the complexity to solve **DPEV**. Solving the reformulation **DPEV<sup>SL</sup>** leads to better performance and underlines the importance of taking the structure of the problem into account when designing solution methods. Note that both methods determine optimal solutions.

Table 3 shows the results obtained with the reformulation based on KKT conditions.

<table><caption>Table 3: Comparison of the results obtained with our reformulation **DPEV<sup>SL</sup>**, KKT reformulation using BigM, and KKT reformulation using SOS1 constraints. All instances are solved to the optimum in 1 hour. The average solving time and the standard deviation are given for instances with 10, 20, and 30 customers (10 instances for each category) and 50 customers (30 instances).</caption><thead><tr><th rowspan="2"></th><th colspan="2">DPEV<sup>SL</sup></th><th colspan="2">KKT BigM</th><th colspan="2">KKT SOS1</th></tr><tr><th>Mean Time (sec)</th><th>SD</th><th>Mean Time (sec)</th><th>SD</th><th>Mean Time (sec)</th><th>SD</th></tr></thead><tbody><tr><td>10</td><td>0.02</td><td>0.01</td><td>0.05</td><td>0.02</td><td>0.18</td><td>0.18</td></tr><tr><td>20</td><td>0.03</td><td>0.02</td><td>0.09</td><td>0.02</td><td>0.96</td><td>1.92</td></tr><tr><td>30</td><td>0.04</td><td>0.02</td><td>0.22</td><td>0.11</td><td>2.29</td><td>1.90</td></tr><tr><td>50</td><td>0.06</td><td>0.02</td><td>0.39</td><td>0.15</td><td>1285.55</td><td>927.57</td></tr></tbody></table>

The computation time of solution of **DPEV** with KKT reformulations using SOS1 constraint are drastically more significant than those of KKT reformulation with BigM. However, they ensure the accuracy of the method. Indeed, the results obtained using BigM may be unfeasible if the value of BigM is too large (or non-optimal if it is too small). Bounds on BigM are difficult to compute due to their link with the dual variables. In all cases, the reformulation defined in Section 3 leads to better results than the KKT reformulations. Table 4 reports the results of tests carried out on the largest instances and supports this observation.
<table><caption>Table 4: Comparison of the results obtained with our reformulation $DPEV^{SL}$ and KKT reformulation (using BigM). The number of instances solved to the optimum in 30 minutes and the average solving time for instances solved to the optimum is given for instances with 100, 200, and 500 customers (20 instances for each category).</caption><thead><tr><th rowspan="2"></th><th colspan="2">DPEV<sup>SL</sup></th><th colspan="2">KKT BigM</th></tr><tr><th>#OPT</th><th>Mean Time (sec)</th><th>#OPT</th><th>Mean Time (sec)</th></tr></thead><tbody><tr><td>100</td><td>20/20</td><td>0.16</td><td>20/20</td><td>4.79</td></tr><tr><td>200</td><td>20/20</td><td>0.44</td><td>20/20</td><td>11.70</td></tr><tr><td>500</td><td>20/20</td><td>2.28</td><td>20/20</td><td>242.04</td></tr></tbody></table>

Finally, we present in Table 5 the results obtained on very large instances with up to 5000 customers. These results show that instances involving thousands of customers can be solved using the reformulation presented in Section 3. This highlights the strong potential for this approach, going beyond the performances obtained using classic reformulation approaches from the literature.

<table><caption>Table 5: Number of instances solved to the optimum with a time limit of one hour, average time for instances solved to the optimum, and average number of clients served in the optimal solution for instances with 2000, 3000, 4000, and 5000 customers using our reformulation $DPEV^{SL}$.</caption><thead><tr><th># customers</th><th># Optimal</th><th>Mean Time (sec)</th><th># customers served</th></tr></thead><tbody><tr><td>2000</td><td>15/15</td><td>33.16</td><td>796.33</td></tr><tr><td>3000</td><td>15/15</td><td>71.65</td><td>1242.13</td></tr><tr><td>4000</td><td>10/10</td><td>141.09</td><td>2116.3</td></tr><tr><td>5000</td><td>10/10</td><td>216.08</td><td>2624.1</td></tr></tbody></table>

## 4.3 Impact of peak reduction

We next study the impact of including constraints on the energy consumption during critical periods. We compare the solutions obtained with $DPEV^{SL}$ and $DPEV - P^{SL}$ for different parameter values. The instances being randomly generated, we first identify critical periods in the optimal solution of the problem without constraints on the consumption. More precisely, we choose $\tilde{t}$ as the desired number of critical periods and we set $\tilde{d}$ as the target percentage reduction in consumption during the critical periods. We define $\tilde{T}$ as the set of $\tilde{t}$ periods with the highest consumption levels in the optimal solution of $DPEV^{SL}$, and we set the values $X^t = \bar{X}^t \times \tilde{d}, t \in \tilde{T}$, with $\bar{X}^t, t \in \tilde{T}$ the corresponding consumption level at those periods in the optimal solution.

We first present in Table 6 the average profit reduction and standard deviations of the profit obtained for instances with 500 and 1000 users. The results are based on 10 instances for each type, with each type corresponding to a different set of parameters: number of charging stations, budget, number of choices in the preference list, penalization, and weighting of pairs (station, time). (Details on how the instances were generated are defined in the Appendix.)

We observe an average profit reduction of 0.8% for $\tilde{d} = 80\%$ and 3.5% for $\tilde{d} = 50\%$. We observe a more significant decrease for T_4 type instances, along with a larger standard deviation. This occurs because this type of instance is designed so that users
<table><caption>Table 6: Average reduction and standard deviation of the profit for 8 types of instances with 10 instances of each type.</caption><thead><tr><th rowspan="2">#Users</th><th rowspan="2">Type</th><th colspan="2">Average profit reduction (%)</th><th colspan="3">Standard deviation (%)</th></tr><tr><th>d̃ = 80%</th><th>d̃ = 50%</th><th>DPEV<sup>SL</sup></th><th>d̃ = 80%</th><th>d̃ = 50%</th></tr></thead><tbody><tr><td rowspan="4">500</td><td>T_1</td><td>-0.8</td><td>-3.3</td><td>8.2</td><td>8.3</td><td>8.5</td></tr><tr><td>T_2</td><td>-0.6</td><td>-2.7</td><td>5.6</td><td>5.6</td><td>5.8</td></tr><tr><td>T_3</td><td>-0.8</td><td>-3.3</td><td>8.0</td><td>8.1</td><td>8.3</td></tr><tr><td>T_4</td><td>-0.9</td><td>-4.5</td><td>12.4</td><td>12.4</td><td>12.8</td></tr><tr><td rowspan="4">1000</td><td>T_1</td><td>-0.6</td><td>-2.8</td><td>4.9</td><td>4.9</td><td>5.2</td></tr><tr><td>T_2</td><td>-0.5</td><td>-2.4</td><td>5.2</td><td>5.3</td><td>5.4</td></tr><tr><td>T_3</td><td>-0.6</td><td>-2.5</td><td>9.2</td><td>9.3</td><td>9.4</td></tr><tr><td>T_4</td><td>-1.7</td><td>-6.3</td><td>18.7</td><td>19.0</td><td>19.3</td></tr></tbody></table>

tend to have more similar preference lists. Consequently, it becomes more challenging to distribute users effectively. To better understand user distribution, Table 7 reports the average number of users served and the average number of users charging at the first choice of their preference list.

<table><caption>Table 7: Average number of users served and average number of users charging at the first choice of their preference list, with 10 instances of each type.</caption><thead><tr><th rowspan="2">#Users</th><th rowspan="2">Type</th><th colspan="3">Average # users served</th><th colspan="3">Average # first choice</th></tr><tr><th>DPEV<sup>SL</sup></th><th>d̃ = 80%</th><th>d̃ = 50%</th><th>DPEV<sup>SL</sup></th><th>d̃ = 80%</th><th>d̃ = 50%</th></tr></thead><tbody><tr><td rowspan="4">500</td><td>T_1</td><td>454</td><td>452.4</td><td>446.1</td><td>285.2</td><td>286.2</td><td>277.1</td></tr><tr><td>T_2</td><td>468.3</td><td>467.7</td><td>465.1</td><td>251.1</td><td>255.4</td><td>249.5</td></tr><tr><td>T_3</td><td>419.9</td><td>418.3</td><td>413</td><td>209.3</td><td>210.1</td><td>204.8</td></tr><tr><td>T_4</td><td>325</td><td>321.6</td><td>311.2</td><td>152.1</td><td>148.6</td><td>141.7</td></tr><tr><td rowspan="4">1000</td><td>T_1</td><td>919.4</td><td>918.8</td><td>908.1</td><td>550.6</td><td>561.4</td><td>543.8</td></tr><tr><td>T_2</td><td>926.6</td><td>922.6</td><td>914.7</td><td>440.3</td><td>452.4</td><td>444</td></tr><tr><td>T_3</td><td>862.4</td><td>837.8</td><td>818.4</td><td>509.6</td><td>488.8</td><td>457.2</td></tr><tr><td>T_4</td><td>302.1</td><td>295.5</td><td>282.4</td><td>97.8</td><td>95.8</td><td>89.6</td></tr></tbody></table>

The average number of users served and the average number of users charging at their first choice remains stable despite the peak reduction (and even increases in some cases). We also observe that the optimal solutions for type T_4 instances have a lower average number of users served compared to other types, which is also due to the higher similarity of the preference lists.

We illustrate in Figure 6 the impact of the peak reduction on the energy consumption levels for all time periods for one instance of 1000 users. In this instance, there are three critical periods at time periods 5, 13 and 18. We can see in Figure 6 that the energy consumption at those three periods exactly reflects the enforced reduction. We also see that the charging levels change for most of the other time periods, and that the peak of some periods is increased, as is the case for period 14, for example. The overall quantity
of energy consumed may increase or decrease, depending on the number of users served (reported in Table 7), as we assume that each user charges exactly one unit of energy.

<figure><img src="image_8.png" /><figcaption>Figure 6: Evolution of the peak for each hour on an instance of 1000 users, with $\tilde{t} = 3$.</figcaption></figure>

Finally, we compare the solution obtained with $\mathbf{DPEV} - \mathbf{P}^{SL}$ to the case where prices are uniform across all stations, and customers charge at the (station, time) pair ranked first in their preference list. Unsurprisingly, this case, called *static* in the following, generates the maximum consumption peak. It is important to note that in the *static* case, the number of customers charging at a given (station,time) pair can exceed the station's maximum capacity, as charging station constraints are not considered in the greedy solution. Figure 7 depicts the maximum peaks over all periods of the optimal solutions of $\mathbf{DPEV}^{SL}$ and $\mathbf{DPEV} - \mathbf{P}^{SL}$ with different $\tilde{d}$ compared with the *static* case.
<figure><img src="image_9.png" /><figcaption>Figure 7: Maximum peak obtained for 30 instances of 500 customers, with different values of parameter $\tilde{d}$ and static case.</figcaption></figure>

We observe that reducing the consumption during critical periods may lead to an increase in the maximum peak across all periods (for example in instance 23). This occurs because limiting the number of users charging in certain periods will lead to some or all of them charging in other periods, and this may raise the resulting energy peak over all periods. Of course this will not happen if all periods are considered as critical periods but this may be unduly restrictive. Nevertheless, we find that for all our instances, the use of dynamic pricing results in users being distributed over their various preferences and drastically reduces the energy peak of the (static) solution without dynamic pricing.

# 5 Conclusion and Future Research

In this paper, we presented a new bilevel optimization model for an electric vehicle charging station pricing problem that takes customer preferences into account. The model integrates dynamic pricing which makes it possible to distribute users across the various charging stations and have them charge at various times. The model can also integrate reduction in energy consumption for a given set of critical time periods, which generally results in lower peaks of energy consumption. We solved the bilevel model using an efficient single-level linear reformulation approach based on linear lower-level optimality conditions. Our computational results show that the performance of our approach compares advantageously to standard reformulations based on the KKT optimality conditions, and that our approach is able to solve very large instances with up to 5000 users. We also demonstrate the flexibility of our model by extending it to integrate the ability to reduce consumption peaks over a set of critical periods. The results show that these peaks can be reduced significantly while only slightly degrading the profit of the provider.

In future work, we plan to integrate the uncertainty in the customer behaviour in the modelling of the preference lists. We also plan to add energy storage (such as batteries) to the charging stations together with renewable energy generation, either locally at the
stations or at grid level. More generally, dynamic pricing of charging has the potential to mitigate the stochasticity of renewable generation and demand. As the reformulation is only based on the lower-level, we can add complexity to the upper-level without changing the validity of the reformulation.

## References

[1] Miguel F Anjos, Ikram Bouras, Luce Brotcorne, Alemseged G Weldeyesus, Clémence Alasseur, and Riadh Zorgati. Integrated location, sizing and pricing for ev charging stations. In Teodor Gabriel Crainic, Michel Gendreau, and Antonio Frangioni, editors, *Contributions to Combinatorial Optimization and Applications*, International Series in Operations Research & Management Science. Springer Nature, 2024.

[2] Miguel F Anjos, Bernard Gendron, and Martim Joyce-Moniz. Increasing electric vehicle adoption through the optimal deployment of fast-charging stations for local and long-distance travel. *European Journal of Operational Research*, 285(1):263–278, 2020.

[3] Elliot Anshelevich, Koushik Kar, Shreyas Sekar, and Zaid Tariq. Balancing social utility with aggregator profit in electric vehicle charging. In *2017 IEEE International Conference on Smart Grid Communications (SmartGridComm)*, pages 369–374. IEEE, 2017.

[4] Zhaoyao Bao and Chi Xie. Optimal station locations for en-route charging of electric vehicles in congested intercity networks: A new problem formulation and exact and approximate partitioning algorithms. *Transportation Research Part C: Emerging Technologies*, 133:103447, 2021.

[5] Evelyn Martin Lansdowne Beale and John A Tomlin. Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. *OR*, 69(447-454):99, 1970.

[6] Sebastián Dávila, Martine Labbé, Vladimir Marianov, Fernando Ordónz, and Frédéric Semet. Product line optimization with multiple sites. *Computers & Operations Research*, 148:105978, 2022.

[7] Vivek F Farias, Srikanth Jagabathula, and Devavrat Shah. A nonparametric approach to modeling choice with limited data. *Management science*, 59(2):305–322, 2013.

[8] Matteo Fischetti, Ivana Ljubić, Michele Monaci, and Markus Sinnl. Intersection cuts for bilevel optimization. In *Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings 18*, pages 77–88. Springer, 2016.

[9] Christoph M. Flath, Jens P. Ilg, Sebastian Gottwalt, Hartmut Schmeck, and Christof Weinhardt. Improving Electric Vehicle Charging Coordination Through Area Pricing. *Transportation Science*, 2014.
[10] Bahman Gharesifard, Tamer Başar, and Alejandro D Domínguez-García. Price-based distributed control for networked plug-in electric vehicles. In *2013 American Control Conference*, pages 5086–5091. IEEE, 2013.

[11] Arnob Ghosh and Vaneet Aggarwal. Menu-based pricing for charging of electric vehicles with vehicle-to-grid service. *IEEE Transactions on Vehicular Technology*, 67(11):10268–10280, 2018.

[12] Yawei He, Kara M Kockelman, and Kenneth A Perrine. Optimal locations of US fast charging stations for long-distance trip completion by battery electric vehicles. *Journal of cleaner production*, 214:452–461, 2019.

[13] Zechun Hu, Kaiqiao Zhan, Hongcai Zhang, and Yonghua Song. Pricing mechanisms design for guiding electric vehicle charging to fill load valley. *Applied Energy*, 2016.

[14] Yantao Huang and Kara M Kockelman. Electric vehicle charging station locations: Elastic demand, station congestion, and network equilibrium. *Transportation Research Part D: Transport and Environment*, 78:102179, 2020.

[15] Ömer Burak Kınay, Fatma Gzara, and Sibel A Alumur. Charging station location and sizing for electric vehicles under congestion. *Transportation Science*, 57(6):1433–1451, 2023.

[16] Steven Lamontagne, Margarida Carvalho, Emma Frejinger, Bernard Gendron, Miguel F Anjos, and Ribal Atallah. Optimising electric vehicle charging station placement using advanced discrete choice models. *INFORMS Journal on Computing*, 2023.

[17] Steffen Limmer. Dynamic pricing for electric vehicle charging—a literature review. *Energies*, 12(18):3574, 2019.

[18] Francisco Manríquez, Enzo Sauma, José Aguado, Sebastián de la Torre, and Javier Contreras. The impact of electric vehicle charging schemes in power system expansion planning. *Applied Energy*, 262:114527, 2020.

[19] Zeinab Moghaddam, Iftekhar Ahmad, Daryoush Habibi, and Mohammad AS Masoum. A Coordinated Dynamic Pricing Model for Electric Vehicle Charging Stations. *IEEE Transactions on Transportation Electrification*, 2019.

[20] Pierre-Luc Parent, Margarida Carvalho, Miguel F Anjos, and Ribal Atallah. Maximum flow-based formulation for the optimal location of electric vehicle charging stations. *arXiv preprint arXiv:2312.05980*, 2023.

[21] Syed Rahman, Irfan Ahmed Khan, Ashraf Ali Khan, Ayan Mallik, and Muhammad Faisal Nadeem. Comprehensive review & impact analysis of integrating projected electric vehicle charging load to the existing low voltage distribution system. *Renewable and Sustainable Energy Reviews*, 153:111756, 2022.

[22] Florian Salah and Christoph M Flath. Deadline differentiated pricing in practice: marketing ev charging in car parks. *Computer Science-Research and Development*, 31:33–40, 2016.
[23] Dan Xiao, Shi An, Hua Cai, Jian Wang, and Haiming Cai. An optimization model for electric vehicle charging infrastructure planning considering queuing behavior with finite queue length. *Journal of Energy Storage*, 29:101317, 2020.

[24] Xiaomin Xu, Dongxiao Niu, Yan Li, and Lijie Sun. Optimal pricing strategy of electric vehicle charging station for promoting green behavior based on time and space dimensions. *Journal of Advanced Transportation*, 2020:1–16, 2020.

## A Instance generation

This section describes the parameters used for random instance generation. The number of time slot is fixed to 24, and the budget is randomly choose between 80 and 200. The table 8 shows the possible sets of values for each parameter. The column "Weighting" corresponds to the weight and the number of pairs (station, time) on which the weight is applied (a weight of 20 means that an pair has 20 times more chance of being chosen when the preference lists are generated).

<table><caption>Table 8: Possible values for instance generation.</caption><thead><tr><th># users</th><th>Type</th><th># stations</th><th>δ</th><th># choices</th><th>α</th><th>Weighting</th></tr></thead><tbody><tr><td rowspan="4">500</td><td>T_1</td><td>[10,15]</td><td>[5-10]</td><td>[2,3]</td><td>[2,30]</td><td>20 on 5 pairs</td></tr><tr><td>T_2</td><td>[10,20]</td><td>[5,10]</td><td>[2,4]</td><td>[2,15]</td><td>20 on 5 pairs</td></tr><tr><td>T_3</td><td>[10,20]</td><td>[5,10]</td><td>[2,4]</td><td>[2,30]</td><td>60 on 5 pairs</td></tr><tr><td>T_4</td><td>[10,20]</td><td>[5,10]</td><td>[2,4]</td><td>[2,30]</td><td>40 on 15 pairs</td></tr><tr><td rowspan="4">1000</td><td>T_1</td><td>[20,40]</td><td>[5,10]</td><td>[2,4]</td><td>[2,30]</td><td>20 on 10 pairs</td></tr><tr><td>T_2</td><td>[20,40]</td><td>[5,10]</td><td>[2,6]</td><td>[2,15]</td><td>20 on 10 pairs</td></tr><tr><td>T_3</td><td>[10,20]</td><td>[10,20]</td><td>[2,6]</td><td>[2,30]</td><td>20 on 10 pairs</td></tr><tr><td>T_4</td><td>[10,20]</td><td>[10,20]</td><td>[2,6]</td><td>[2,30]</td><td>60 on 40 pairs</td></tr></tbody></table>