A Bilevel Model for Centralized Optimization of Charging Stops for EV on Highways

Abstract

This paper addresses the multi-period problem of fixing the energy charging price at a set of charging stations deployed to support long journeys of electric vehicles along highways. In order to model the problem, we propose a non-linear bilevel program, in which the leader (a single centralized operator) fixes the charging price over the time horizon to maximize its profit and the follower (the operator of the electric vehicles) chooses the optimal assignment of the electric vehicles to the stations so to minimize a cost function. To solve the resulting model, we suggest to adopt an adaption of the Branch-and-Cut algorithm for Mixed Integer Linear Bilevel Programming proposed by Fischetti et al. (2018). Preliminary computational results are provided to show the interesting performance of the new modeling and algorithmic approach.

Supported by PGMO.

1 Introduction

Recently, with the EV driving range¹ (up to 300 km in a single ride) and the deployment of rapid charging stations along highways, the long journey trip becomes more and more possible [2]. The main problem, tackled in this article, is how to deal with the dimensioning of those rapid charge stations. In fact, the autonomy is not sufficient for a long trip without recharging. Therefore, the problem of managing such stations considering how EV customers react is considered in this work. Such complex system involves a two levels hierarchical structure and a specific mathematical problem has to be considered where the manager of the charging station will be at the upper level and the set of EV at the lower level (the decisions of the EV are managed by a single operator, centralized context). In the past few decades, there have been many advances in the field of Operations Research applied to the transport sector to solve planning or pricing problems [3]. In many cases, these applications do not take into account the feedback effects - also called reactions to the optimum- of the third parties of the organ subject to the problem. Typically, this means optimizing the profit of a service provider without taking into account the beneficiary’s reaction, whose decision can potentially vary according to the service provider optimum. Hence, decision problems need to take into account simultaneously two different actors (or agents) who do not have the same objective. The corresponding model has to imply both decision agents interacting sequentially and hierarchically. This type of process can be formulated as a bilevel program [4] where a decision agent, called the leader, integrates explicitly the reaction of another agent, named the follower, when the leader has to make optimal choices. At the upper level, the leader can be for instance faced to a pricing problem as in [5]. At the lower level, on the other hand, the followers can interact in terms of a congestion problem as in [8]. Bilevel models have been proposed recently to address EV problematic. In [9] the authors propose a bilevel optimization framework for designing optimal charging strategies for a fleet of EV. In [10], the authors propose also a bilevel model (here a Stackelberg game), where EV charging station operators compete at the upper level, offering charging prices to attract EV to their station. The present paper proposes an approach for the modeling of the best pricing for charging stations taking into account a set of EV whose decisions are made by a single operator (centralized model). We make this first strong assumption of centralized model because of the following two reasons: (i) the centralized context gives an optimum social bound very interesting in terms of user performances and recharging system; (ii) this bound will help us, for future work, to quantify the price of anarchy obtained in a incitation/information decentralized model. Most of new vehicles, and particularly EV, are basically equipped with GPS driving facilities. Then, it is plausible, and in fact already present in particular EV brands like Tesla, that such GPS system can provide information to drivers on where and how much to charge during the trip. This driving aided system can be computed in a centralized way by an operator of a fleet of EV. Two actors are thus considered, one being the Charging Station Manager (CSM) whose objective is to maximize his profit, the other being the Set of Electric Vehicles (SEV) responsive to the prices assigned to recharging stations and to the waiting times at the charging stations. The SEV is managed by a single operator. The paper is organized as follows. We first state the studied problem in Sect. 2. Section 3 details the bilevel model proposed to formulate both CSM and SEV problems. We establish in Sect. 4 the adaptive exact algorithm implemented to solve our problem. Section 5 is dedicated to numerical experiments. We finally conclude in Sect. 6.

2 Problem Statement

The study of this paper addresses the problem of determining the unit charging price at each charging station (CS) in order to influence EV stops in a multi-dimensional case (several CS and several EV), modeling long travel on highways with EV. The pricing adopted by the Charging Station Manager (CSM) is considered to follow a single objective: to maximize its profit by taking into account the unit charging price and the waiting time at its CS. Inline with the case of highways, we consider we consider a rectilinear road that the EV can use.

In this situation, it is essential to take into account the behavior of the SEV since the unit charging price is implicitly dependent on the distribution of vehicles to charging stations. Therefore, it is primordial to know the SEV’s reaction to a pricing decision.

The work here presents a large framework and thus some assumptions limit the complexity of the analysis and allow to focus on implicit CSM/SVE negotiation through an applied Intersection Cuts method [6]. Such method has been recently proposed and is very efficient to solve bilevel problems. The authors suggest the use of basic Branch-and-Bound algorithm first employed for the relaxed bilevel problem (i.e. for a single level problem concerning the upper level where the optimization problem of the lower level is relaxed) called High Point Relaxation (HPR) problem and then an exploration at the node of the search tree is done in order to find a feasible bilevel solution. In addition, the authors suggest for the first time, the use for bilevel program of intersection cuts, initially developed by Balas [1] for Integer Linear Programming. The following hypotheses are then considered: Prices are considered as natural integers and they are also bounded; Time is discrete; Each charging station has only one charging point; EV decisions are managed by a single operator (centralized context).

The main problem for the operator of the SEV is to determine, a priori, where each EV has to stop during his long trip (assuming that each EV has necessary the need to stop in order to reach its destination), considering pricing decisions (the unit charging price) proposed by charging stations operator. In addition, such optimization problem depends on the state-of-charge (SoC) of each vehicle. It also involves a bilevel approach. We present in the next section the bilevel model we have proposed to formulate the problem mentioned. Figure 1 gives an overview of the considered problem. Let us consider $S = 6$ Charging Stations (denoted by S on the figure) and 6 EV (denoted by EV on the figure). Each EV can reach several CS according to its battery level, i.e. its SoC. The decision of each EV will be taken according to the charging price and the waiting time before service at each CS. For instance, let us focus on $EV_1$. $EV_1$ can reach $S_1$ or $S_2$. Then, from $S_1$ the $EV_1$ can reach $S_3$ or from $S_2$ can reach $S_3$ or $S_4$ and so on, until $EV_1$ reaches the last station $S_6$. However, each station has its own charging price, making them more or less attractive, and as a consequence, generating more or less demand. This difference of attractiveness induces different queues between the CS, which is another cost for EV.

Fig. 1.

Possible stopping scenarios for $EV_{1}$ where initial SoC for EV 1 is 10 units of energy which is the maximum value.

3 The Proposed Bilevel Model

In this section, the bilevel model is established and notations are given. The problem is concerned with two decision makers: a recharging station manager (RSM) (the leader) and a Set of EV (SEV) (the follower). The output of the model are the following:

• 1. Leader’s problem: The leader (RSM) manages a set of charging stations S and a unit charging price $p_{s}$ has to be assigned to station s on the overall time duration T, in order to maximize his benefit. This price is assumed to be stationary which is more acceptable for customers in general like flat rate pricing schemes in telecom, but the model can be simply enriched by considering dynamic prices without too much complexity.

• 2. Follower’s problem: The follower (operator of the SEV) has to decide an optimal repartition of the EV over the stations in order to minimize the total charging cost and the waiting time; that is to minimize the cost.

Following notations are considered:

• T is the time interval (time horizon) of the model.

• I is the fleet of EV indexed by i. The EV are initialized to random position (entrance of the road) and SoC within the discrete set $\mathbf{E} :=\{0,\ldots , E\}$.

• S is the discrete set of charging stations (CS) indexed by s and geographically positioned such that the distance between two consecutive CS is d distance units uniformly located on the rectilinear considered road.

• All EV are identical and the maximal SoC is denoted by E. The SoC of EV i at time t is denoted by $e_{i,t}$ such that $0 \le e_{i,t} \le E$.

• When EV i stops at a charging station s at time slot t, the EV charging time is denoted by $C_{i,s,t}$ and is equal to $C_{i,s,t}:= \alpha _C \times (E-e_{i,t})$ (recovering full battery level), where $\alpha _C$ represents the ratio of the time needed for a full charge (when at CS) to the one for full discharge (when driving). $\alpha _C \le 1$, and in the context of highways typical values lie in the range [1/20, 1/3]².

• Each charging station s has an unit charging price $p_s$ in the discrete ordered set $P = \{p_0, p_1, ... , p_P\}$ with $p_0 = P_{min}$ and $p_P = P_{max}$.

The proposed bilevel model aims to explore the tradeoff between the charging price and waiting time at the charging station. The pricing approach is inspired from [5] which is standard for congestion control. More precisely our model is based on the following decision variables:

• Pricing of charging stations: the decision variables $p_s$ (upper level) are integer representing the pricing applied at station s per unit of charging time,

• Decision variables of the EV: the variables $y_{i,s,t}$ (lower level) are binaries and determine if EV i has to stop at charging station s, knowing that the vehicle will reach it at time t.

Taking ordering indices for the decision variables allows to determine the stops of an EV along his travel and then deduce the arrival time at each station corresponding to the stopping decision.

Let us describe the objective function of the leader (upper level optimization problem), which is dependent on the stopping decision of the SEV (for charging). The benefit of the leader for one particular charging station s is:

$$\begin{aligned} \sum _i y_{i,s,t} \times C_{i,s,t} \times p_{s}. \end{aligned}$$

(1)

This benefit, coming from EV i who stops at time t in station s, depends on the charging time of this EV that is $C_{i,s,t}$. The maximization problem of the leader who manages all CS is then expressed by:

$$\begin{aligned} max_{p:=(p_1,\ldots ,p_S)}\sum _i^I\sum _s^S\sum _t^T y_{i,s,t} \times C_{i,s,t} \times p_{s}. \end{aligned}$$

(2)

Concerning the follower (the manager of the SEV), it aims to minimize the total charging cost for EV as well as the waiting times at the charging stations (we make a sum of both follower’s objectives). We denote by $\triangle _s$ the total waiting time of all EV who stop at station s, which gives the following objective function:

$$\begin{aligned} min_{y}(\sum _i^I\sum _s^S\sum _t^T y_{i,s,t} \times C_{i,s,t} \times p_{s} + \sum _s^S\triangle _s) \end{aligned}$$

(3)

where

$$\begin{aligned} \triangle _s = \sum _i^I\sum _t^T \delta _{i,s,t} \end{aligned}$$

(4)

This last expression represents the waiting time of EV i arrived at station s at time t, before starting to get served (i.e. to start charging energy). More precisely, if an EV, for example EV i arrives after EV k at the same station s at time t, and if $EV_k$ is still charging then the waiting time for EV i at station s depends on the remaining charging time of EV k like in a queueing system. In addition, $\ell _{i,s,t}$ is the travel time for EV i given its position at time t, to reach station s such that station s is in front of him but not the next one on the travel, and it is determined by:

$$\begin{aligned} \ell _{i,s,t} = d_{i,s,t} + \sum _{s'=1}^{s-1}\sum _{t}^TC_{i,s',t}y_{i,s',t} + \sum _{s'=1}^{s-1}\sum _{t}^T\delta _{i,s',t}, \end{aligned}$$

(5)

with $d_{i,s,t}=s\times d-pos(i,t)$ is the distance between station s and the current position of EV i at time t denoted by pos(i, t). Indeed, this variable has to take into account the waiting and charging times for EV i in any other charging stations $s'$ where the EV has stopped before reaching station s. If station s is the next one on the travel, the travel time for EV i to reach s is simply:

$$ \ell _{i,s,t} = d-pos(i,t). $$

Let us now describe the constraints of our model. We have to guarantee that only one travel can be taken by an EV. The $y_{i,s,t}$ are the decision variables related to the decision that EV i stops at station s at time t and the order corresponds to the t-th visited charging station since the beginning of the travel. This order allows to guarantee that an EV can not turn back on the road. Let us give a simple example to illustrate our constraints. Let us consider for example EV 1. Let us assume that EV 1 stops at the station 1 at time 1 and then at station 3 at time 3 (recall that $d=1$), consequently $y_{1,1,1} = y_{1,3,3} =1$, and $y_{1,s,t}=0$ $\forall s,t$, that is $y_{1,2,4} =1$ is forbidden. More formally, this constraint can be stated as follows:

$$\begin{aligned} \sum _{s} y_{i,s,t_0} = 1\ \forall \ i. \end{aligned}$$

(6)

That is at $t_0$ $EV_i$ has to choose one and only one station s. Nevertheless, after $t_0$ it has the choice to stop or not to a possible station. The constraints can be expressed as follows:

$$\begin{aligned} (y_{i,s,t} \times \sum _{s'=s+1}^{S} y_{i, s',t+1}) + (\lnot y_{i,s,t} \times (\sum _{s'=s+1}^{S} \lnot y_{i,s',t+1})/S) = 1. \end{aligned}$$

(7)

If $EV_i$ stops at the station s at time t then it has to visit one and only one station $s'$ (corresponding to accessible stations from station s) at time $t+1$ otherwise if $EV_i$ does not visit station s at time t (expressed by $\lnot y_{i,s',t+1}$) then $EV_i$ can not stop at any station $s'$ with $\lnot y_{i,s',t+1}$). Finally constraints which allow link between waiting time and charging price at CS are described hereafter:

$$\begin{aligned} p_s \le \frac{(\varDelta _{max} - \varDelta _s)}{\varDelta _{max}} \times (P_{max} - P_{min}) + P_{min} \ \forall s \in S. \end{aligned}$$

(8)

Indeed, the constraint below aims to fix a price if and only if the waiting time at station s allows it. It can be noticed that if, for instance, the waiting time at station s is such that $\varDelta _s = 0$ then the charging price will be set at maximum value $P_{max}$. On the contrary, the bigger the waiting time is at station s, the lower the charging price at this station. In addition, note that since $\varDelta _s$ includes a product of $y_{i,s,t}$ decision variables, those constraints are quadratic. Note that $\varDelta _{max}$, which is the maximum waiting time at a CS can be pre-calculated. We are now able to establish the proposed non-linear bilevel problem (NLBLP) as follows:

Note that the proposed bilevel model includes characteristics which make it non-standard:

• the objective functions of the leader (2) and follower (3) are not linear;

• constraints (8) relative to the relation between of the price and waiting time are quadratic.

Consequently, the recent exact solution method developed in [6] has been used by linearization of quadratic constraints in order to consider our non-standard (NLBLP). The algorithm is described in the next section.

4 Solution Algorithm for the NLBLP

Our bilevel program solution method is an adaptation of the Branch-and-Cut algorithm proposed by [6] for our non linear problem. The authors have suggested a general exact solution method dealing with Mixed-Integer Bilvel Program (MIBLP) where both objective functions and constraints for leader and follower are linear. The decision variables of the leader which influence the decision of the follower have to be pure integer and bounded. The other decision variables of the leader can be integer or continuous, and the one of the follower are integers. The general (MIBLP) studied in [6] can be written as follows:

$$\begin{aligned} \min F(x,y) \end{aligned}$$

(9)

$$\begin{aligned} \mathrm{s.t.} \end{aligned}$$

$$\begin{aligned} G(x,y) \le 0 \end{aligned}$$

(10)

$$\begin{aligned} g(x,y) \le 0 \end{aligned}$$

(11)

$$\begin{aligned} x,y \in R^n \end{aligned}$$

(12)

$$\begin{aligned} f(x,y) \le \phi (x) \end{aligned}$$

(13)

where for a given $x\in R^{n_1}$ the follower value function is:

$$\begin{aligned} \phi (x) = \min _{y \in R^{n_2}} \{f(x,y) : g(x,y) \le 0\} \end{aligned}$$

(14)

When constraint (14) is relaxed, the program is called High Point Relaxation (HPR) which is assumed to be feasible. This is a strong property that our model has to satisfy. The authors suggest a finitely-convergent branch-and-bound algorithm based on the two following assumptions: (i) the variables x and y have finite lower and upper bounds in (HPR) and in the follower (MILP); (ii) the continuous leader variables (if they exist) do not appear in the follower problem.

We apply [6] to our bi-level program. Actually, even if the objective function of the leader is non-linear, it is convex then it can be dealt by CPLEX. In addition, since we deal with (HPR) the problem concerning the non linearity of the objective function of the follower disappears. Concerning the quadratic constraints, a linearization is possible by the use of classical and well-known crossed quadratic terms linearization techniques developed by Glover [7]. Consequently, both assumptions (i) and (ii) established by Fischetti et al. are satisfied in our context, we are then allow to use their Branch-and-Cut algorithm.

5 Preliminary Experiments

In this last section, preliminary experiments are conducted in order to illustrate the performance of the Branch-and-Cut algorithm used to solve our non-standard (NLBLP). MILP problems have been solved using IBM ILOG CPLEX 12.6.3 using callbacks. We have implemented the algorithm in C++ language. Numerical examples were run on a bi-xeon 3.4 Ghz with 4Go of main memory computer. For all instances, maximal SoC is $E=17$ kWh, $d=5$ Km for the distance between two consecutive stations, $\alpha _C = 1$ (that is one unit of energy is consumed when traveling and one unit is recharged when charging, per unit of time) and all initial SoC have been randomly determined. We have conducted several tests with a number of EV and CS taking respectively their value in the following discrete sets $\{2;4;8;16;32;64\}$ and $\{2;4;6;8;10\}$.

Table 1 displays: (i) the CPU times (in seconds) required by the exact algorithm (B&C) we have coded, (ii) the CPU times (in seconds) needed by a feasible solution method (HEUR) and (iii) the relative gap in percentage (Gap = (Optimum – Lower Bound)/Lower Bound). The Lower Bound is provided by the heuristic denoted by (HEUR) which corresponds to the first feasible bilevel solution found in the Branch-and-Bound algorithm. Each line of Table 1 is an average on ten random instances. The (B&C) and the heuristic are very fast on small instances (2 EV). Moreover, the lowest relative gap (${\le }1\%$) is obtained for this size of instances. Such good performance comes from the first step consisting in finding a first feasible solution very quickly, which is a key step here in our approach. When the number of EV increases, both methods become more time consuming and the relative gap between the solutions of both methods also increases. Note that our heuristic can be helpful when the exact solution can not provide the optimum solution like for the instance (#EV, #$CS)=(8,4)$. Obviously, more experiments have to be conducted in future work in order to provide a precise size limit of the instances.

Table 1. Average computational time (in sec.) of the B&C algorithm and our heuristic

6 Conclusion

This work deals with the problem of managing a set of EV into different charging stations, taking into account the charging and the waiting costs. The charging price at each station is settled by a central controller, with the aim to induce an optimal profit. The global problem is a non-linear bi-level problem (NLBLP). The use of a recent tool is possible in our context and significant speedup of the computational time of our heuristic has been obtained without losing the performance. This work then shows on a simple example that managing optimally many EV for long distance travel is possible trough the use of bi-level programs. Many perspectives are possible, for example to take into account a network topology and also to integrate decentralized decision taken by EV individually.