# Assessing the impact of relocation on the optimal design of electric vehicle sharing systems

Christian Clavijo Lopez, Mouna Kchaou-Boujelben, Céline Gicquel, Khedaoudj Halimi

► To cite this version:

Christian Clavijo Lopez, Mouna Kchaou-Boujelben, Céline Gicquel, Khedaoudj Halimi. Assessing the impact of relocation on the optimal design of electric vehicle sharing systems. 2024 10th International Conference on Control, Decision and Information Technologies (CoDIT), Jul 2024, Vallette, Malta. pp.1329-1334, 10.1109/CoDIT62066.2024.10708229. hal-04811888

HAL Id: hal-04811888

https://hal.science/hal-04811888v1

Submitted on 29 Nov 2024

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.

Public Domain
Assessing the impact of relocation on the optimal
design of electric vehicle sharing systems

Christian Clavijo Lopezª, Mouna Kchaou-Boujelbenª, Céline Gicquelᵇ, Khedaoudj Halimiᵇ

ªUAE University, College of Business and Economics, Emirates Center for Mobility Research, United Arab Emirates

ᵇLaboratoire Interdisciplinaire des Sciences du Numérique, Université Paris Saclay,
France

**Abstract**

Electric vehicle sharing systems deployed in large cities provide alternative means of transportation for non-vehicle owners and visitors. This work considers the optimal design of a one-way station-based electric vehicle sharing system. Location of charging stations is assumed to be known so that the main strategic decisions regard the installation of charging ports at stations and the acquisition of electric vehicles. To assess the future system profitability, the strategic problem modeling should integrate tactical and operational decisions representing how the system will operate on a daily basis. This work investigates whether modeling an operational feature, vehicle relocation by employees, has a strong impact on the quality of the design decisions recommended by the optimization model.

***Keywords:*** Car sharing, electric vehicles, network design, mixed-integer linear programming

# 1. Introduction

Vehicle-sharing systems allow individuals to rent vehicles on a short-term basis, for a rental price charged by the time or the distance driven. These systems have the potential to fulfill the need for alternative transportation means and thus contribute to the development of a multi-modal mobility in cities. In the long-term, vehicle-sharing systems may also contribute in alleviating urban congestion through the reduction of the number of privately owned cars which consume urban space by remaining parked most of the
time [12]. Furthermore, the increased concern about the environmental ef-
fects and health damages caused by conventional fuel vehicles have boosted
the adoption of electric vehicles (EVs). Accordingly, electric vehicle-sharing
systems (EVSS) have recently developed worldwide. For instance, companies
like Mobilize have established car-sharing platforms based on EVs in several
cities across Europe [13].

Establishing a successful EVSS is challenging as we need to simultane-
ously provide a high quality of service to users (with sufficiently charged EVs
available at the right time and location) and a solid business performance
of the system. Moreover, setting up an EVSS requires substantial capital
investment. The strategic design of an EVSS should thus be carefully opti-
mized so as to maximize its profitability and ensure its long-term economic
viability.

This work investigates the optimal design of a one-way station-based
EVSS. In such a system, users must pick up and return shared EVs at one
of the network stations, and the departure and arrival stations of a trip are
not necessarily the same. We assume that the location of each station has
already been decided upon and focus on determining the number of chargers
to be built in each station and the size of the EV fleet. However, to make
these strategic investment decisions, we need to estimate, as best as possible,
the future revenue that the EVSS operator will get by operating the network
on a daily basis. Our study should thus integrate tactical decisions usually
made one day in advance (e.g., trip request acceptance and EV dispatching)
and intra-day operational decisions (e.g., EV charging and relocation). EV
relocation is done by employees of the EVSS operator and consists in moving
EVs during the day from stations where they are not needed to stations where
EVs are missing. Relocation is a way to tackle a frequently encountered diffi-
culty in the operational management of an EVSS: the strong spatio-temporal
imbalances in the users' demand. These imbalances come among others from
daily travelling patterns, with e.g. lots of people commuting from residential
areas to downtown working places in the morning and the other way round
in late afternoon hours. In this case, EVs relocation ensure that vehicles are
available when and where needed throughout the day.

Ideally, we would like to make strategic design decisions while using a
detailed representation of all the tactical and operational aspects, including
relocation, related to the management of an EVSS. This would ensure that
the obtained network, when deployed, has an actual performance close to the
expected one. However, incorporating relocation in the optimization problem
leads to a significant increase of its size and may result in numerical difficulties to solve it. The question thus arises as to whether relocation actually needs to be considered in the modeling of the strategic design problem. This work aims to provide a first answer to this question. We thus would like to determine whether considering EV relocation significantly changes our estimation of the number of accepted trip requests and consequently of the future profitability of the system, and whether it modifies our strategic long-term decisions on the number and location of installed chargers and on the EV fleet size.

The impact of relocation on the operational performance of EVSS has been highlighted by several studies (see [2] for an overview) but these works did not consider strategic design decisions. Some studies sought to integrate EV relocation into the modeling of the fleet sizing problem [3, 4]. Furthermore, several recent works focusing on the strategic network design incorporated relocation decisions into the problem modeling and developed solution algorithms to handle the resulting combinatorial optimization problem: see e.g. [5, 6, 7, 8, 9, 10, 11]. However, to the best of our knowledge, none of these works investigated whether modeling relocation has a strong impact on the strategic decisions.

Our contributions are thus threefold. First, we propose a new extension of the model recently introduced by [1] in order to incorporate relocation into it. Second, we provide numerical results obtained on small-size randomly generated instances showing that design decisions, together with the estimation of the future profit, may significantly differ when relocation during the day is incorporated in the model. Third, we show that incorporating relocation in the design problem is particularly important when the users' demand displays strong spatio-temporal imbalances. The remaining of the paper is organized as follows. Section 2 provides a detailed description of the optimization problem under study. Section 3 presents its mathematical formulation as a mixed-integer linear program. Numerical results are provided in Section 4 while some conclusions are devised in Section 5.

## 2. Problem description

We study the problem of optimally designing an EVSS given an established network comprising a set $S$ of stations whose location has already been determined. These stations need to be equipped with chargers to enable EVs to be recharged between two trips. Installing a charger incurs a fixed cost $F_c$ and the maximum number of chargers that can be installed at station
$i \in S$ is given by $C_i$. Furthermore, a set $H$ of EVs may be bought in order to operate the system. All the available EVs are assumed to be identical with a battery capacity $B_{max}$ and an unit acquisition cost $F_v$. The design decisions thus consist in determining the number of chargers to be built in each station and the number of EVs to be bought.

However, in order to make these design decisions, we need to estimate the future revenue that we may get by operating the proposed system on a daily basis. To this aim, we consider a single typical day, model how the system will be operated during this day, and assume that the activity during this typical day will be replicated identically throughout the strategic planning horizon of $Y$ years. Note that such an assumption has been used by e.g. [1, 7, 8]. Furthermore, the EVSS is assumed to be active at daytime and to shutdown during the night. The daily opening time is divided into a set $T = \{1, ..., t^{max}\}$ of periods of equal duration.

We consider a reservation-based system in which users wishing to carry out a trip should request a vehicle at least one day in advance and the operator has the possibility to reject a trip request in case it cannot be satisfied. The list of trip requests $K$ is thus known beforehand. Each trip $k \in K$ is described by its origin station $o_k$, destination station $d_k$, starting period $s_k$, ending period $e_k$, duration $D_k$, battery consumption $b_k$, and estimated revenue $p_k$. It is assumed that all EVs are returned by users before the end of the working day, i.e. $e_k \le t^{max}$, and that the energy required by a trip does not exceed the maximum energy provided by a fully charged battery, i.e. $b_k \le B_{max}$. We denote by $K_t = \{k \in K | s_k \le t < e_k\}$ the set of trips starting or on-going at period $t$. The main tactical decisions, to be made one day in advance, thus consist in deciding which trip requests should be accepted or rejected. Another important decision at this level is EV dispatching which consists in allocating EVs to stations at the beginning of the day. We assume that, every night, the system is reset in the same initial state (in terms of EV allocation to stations) and thus need to define how EVs should be dispatched to the stations at the beginning of time period 1. Note that EVs dispatched at the beginning of the day are assumed to be fully charged.

Finally, at the operational level, decisions involve assigning an EV to each accepted trip request, deciding when each EV will stay parked at a station and be recharged, and determining which relocations should be carried out. When assigning an EV to an accepted trip request $k$, we need to ensure that this EV will be available at the origin station $o_k$ at the start time $s_k$ with a battery state of charge higher than $b_k$. Furthermore, while defining these EV-
trip assignments, we should make sure that the sequence of trips/relocations assigned to a given EV forms a connected route, i.e., is such that an EV assigned a trip ending at station *i* at time *t* either is assigned to another trip starting from *i* after period *t*, or is relocated by the system operator to the station *j* at which its next trip starts, or stays parked at station *i* till the end of the day.

Whenever an EV is rented by a customer or is relocated by the system operator, the state of charge of its battery decreases by a given amount. When an EV arrives at a station, it is plugged into one of the available chargers to be charged with an amount of energy up to $B_{max}$ (kWh) using a linear charging rate $\rho$ (kWh/period). The corresponding energy cost depends linearly on the charged electricity: let $c_d$ (resp. $c_n < c_d$) be the unit charging cost at daytime (resp. nighttime). The relocation of an EV by an employee between stations *i* and *j* requires $\Delta_{ij}$ time periods, consumes $\beta_{ij}$ kWh and incurs a personnel cost $R_{ij}$.

Finally, the EVSS network design problem aims at finding the strategic decisions that will maximize the total profit obtained over the planning horizon. This one is calculated as the difference between the operational profit made in the typical day times the total number of days in the planning horizon, and the strategic investment costs.

### 3. Mathematical Formulation

This section introduces a mixed-integer linear programming formulation (MILP) for the problem under study. This formulation can be seen as an extension of the one recently proposed by [1] to consider EV relocation. Note that, in view of the additional complexity coming from the introduction of relocation into the problem modeling, we simplify the model by assuming that the station locations have already been fixed.

#### 3.1. *Time-expanded location graph*

The problem modeling relies on a time-expanded location graph, denoted by $G = (N, A)$, to represent the spatio-temporal dynamics of the system during the considered typical day. This graph is used to track the movements of each EV $h \in H$ during the day and to monitor the state (in terms of number of occupied chargers) of each station $i \in S$ in each time period $t \in T$.
For each station $i \in S$, we first define $T_i^+ = \{t \in T | \exists k \in K \text{ st } i = o_k, t = s_k\}$ (resp. $T_i^- = \{t \in T | \exists k \in K \text{ st } i = d_k, t = e_k\}$) the subset of time points at which a trip can start (resp. end) at station $i$. $T_i = T_i^+ \cup T_i^-$ represents the set of relevant time points for station $i$, i.e., the set of time points at which the state of the station may change and should thus be monitored. Let $t_i^{\min}$ and $t_i^{\max}$ be the earliest and latest relevant time points for station $i$. Furthermore, to model the relocations taking place at nighttime to reset the EVSS in the same state as its initial one, we introduce an extra period $t^{\text{end}}$ defined as the point of time during the night by which all trips and relocations have ended. Accordingly, we define $\bar{T} = \cup_{i \in S} T_i \cup \{t^{\text{end}}\}$, the set of time points at which the status of an EV may change, i.e., at which its SOC should be monitored.

The set of nodes $N$ is then defined as follows. We introduce a node, denoted by $i_t$, for each station $i \in S$ and each period $t \in T_i$. Let $N_i = \{i_t, t \in T_i\}$ be the subset of nodes related to station $i$. Furthermore, we introduce a node $i_{t^{\text{end}}}$ representing the final state of station $i$ once all EV relocations (including those carried out at nighttime) have finished. Finally, we introduce a root node $r$ and a sink node $s$ to represent the beginning and end of the day. Hence, the set of nodes $N$ is given by: $N = \cup_{i \in I} N_i \cup \cup_{i \in I} \{i_{t^{\text{end}}}\} \cup \{r\} \cup \{s\}$, The set of arcs $A$ comprises 5 different subsets:

- $A^I = \{(r, i_t^{\min}) | i \in S\}$: set of initialization arcs representing the dispatching of EVs at the beginning of the day.

- $A^W = \{(i_t, i_{t'}) | i \in S, t \in T_i, t' \in T_i \cup \{t^{\text{end}}\}, t'$ is the immediate successor of $t$ in $T_i \cup \{t^{\text{end}}\}$: set of waiting arcs representing the parking of EVs at stations. Note that the immediate successor of $t_i^{\max}$ in $T_i \cup \{t^{\text{end}}\}$ is $t^{\text{end}}$.

- $A^T = \{(i_t, j_{t'}) | i = o_k, j = d_k, t = s_k, t' = e_k, k \in K\}$: set of trip arcs representing the rental of EVs to users.

- $A^{DR} = \{(i_t, j_{t'}) | (i, j) \in S^2, i \neq j, t \in T_i, t' \in T_j \mid t'$ is the smallest period in $T_j$ satisfying $t' \ge t + \Delta_{i,j}\}$: set of arcs representing the relocation of EVs by employees at daytime.

- $A^{NR} = \{(i_t, j_{t'}) | (i, j) \in S^2, i \neq j, t = t_i^{\max}, t' = t^{\text{end}}\}$: set of arcs representing the relocation of EVs by employees at nighttime.

- $A^F = \{(i_{t^{\text{end}}}, s) | i \in S\}$: set of finalization arcs representing the allocation of EVs to stations at the end of the day.
Finally, we introduce the following notation.
$\delta^{-}(n)$ Set of arcs ending at node $n$

$\delta^{+}(n)$ Set of arcs originating from node $n$

$a_k$ Trip arc corresponding to trip $k$

$A^R$ Set of all relocation arcs: $A^R = A^{DR} \cup A^{NR}$

$\sigma_a, \epsilon_a$ Starting and ending periods of a relocation arc $a$

$A_t^R$ Subset of relocation arcs such that $\sigma_a < t \le \epsilon_a$

Fig. 1 represents the time-expanded location graph obtained for a small illustrative instance involving $|S| = 3$ stations, $t_{max} = 4$ scheduling periods and $|K| = 5$ trip requests. Note that a feasible spatio-temporal evolution of the EVSS during the considered typical day will be given not by $G$ itself but rather by a feasible multi-commodity flow in $G$.

<figure><img src="image_1.png" /><figcaption>Figure 1: Time-expanded location graph for a small illustrative example</figcaption></figure>

## 3.2. MILP Formulation

We introduce the following design and operational variables:

- $z_i \in \mathbb{Z}$: number of chargers to install at station $i \in S$,

- $x_h \in \{0, 1\}$: $x_h = 1$ if EV $h$ is purchased, $x_h = 0$ otherwise.

- $f_a^h \in \{0, 1\}$: $f_a^h = 1$ if EV $h \in H$ crosses arc $a \in A$, $f_a^h = 0$ otherwise,

- $g_t^h \in \mathbb{R}^+$: state of charge of EV $h \in H$ at $t \in \tilde{T}$.

Note that the practical interpretation of variables $f_a^h$ depends on the nature of arc $a$. Thus, $f_a^h = 1$ represents the initial dispatching of EV $h$ to station $i$ (in case $a = (r, i_{t_{min}}) \in A^I$), the parking of $h$ at station $i$ (in case $a =$
$(i_t, i_{t'}) \in A^W)$, the rental of $h$ to carry out trip $k$ (in case $a = a_k \in A^T$), the relocation of $h$ between two stations $i$ and $j$ (in case $a = (i_t, j_{t'}) \in A^R$) and the parking at station $i$ at the end of the day (in case $a = (i_{tend}, s) \in A^F$. Moreover, note that the value of the expression $\sum_{h \in H} f_{a_k}^h$ indicates whether trip $k$ is accepted or not. Similarly, $\sum_{h \in H} f_a^h$ for a given initialization arc $a = (r, i_t^{min})$ gives the number of EVs to be dispatched to station $i$ at the beginning of the day.

This leads to the following MILP formulation.
$$
\begin{align}
\max Z = & \left( \sum_{k \in K} \sum_{h \in H} p_k f_{ak}^h - \sum_{h \in H} \sum_{a \in A^R} R_a f_a^h \right. \nonumber \\
& \left. - c_d \sum_{h \in H} (g_{tend}^h - B^{max} + \sum_{k \in K} b_k f_{ak}^h + \sum_{a \in A^R} \beta_a f_a^h) \right. \nonumber \\
& \left. - c_n \sum_{h \in H} (B^{max} - g_{tend}^h) \right) \times 365 \times Y \nonumber \\
& - \sum_{i \in S} F_c z_i - \sum_{h \in H} F_v x_h \tag{1}
\end{align}
$$

$$
\sum_{h \in H} f_{ak}^{h} \leq 1 \qquad \forall k \in K \quad (2)
$$

$$
\sum_{k \in K_t} f_{ak}^h \le x_h \qquad \forall h \in H, t \in \cup_{i \in S} T_i^+ \quad (3)
$$

$$
\sum_{h \in H} \sum_{a \in \delta^{-}(i_t) \cap (A^W \cup A^I)} f_a^h \le z_i \qquad \forall i \in S, t \in T_i \quad (4)
$$

$$
\sum_{a \in \delta^{+}(r)} f_{a}^{h} = x_{h} \qquad \forall h \in H \quad (5)
$$

$$
\sum_{a \in \delta^{-}(s)} f_{a}^{h} = x_{h} \qquad \forall h \in H \quad (6)
$$

$$
\sum_{a \in \delta^{-}(n)} f_{a}^{h} - \sum_{a \in \delta^{+}(n)} f_{a}^{h} = 0 \qquad \forall h \in H, n \in N \setminus \{r, s\} \quad (7)
$$

$$
\sum_{h \in H} f_{(r, i_{tmin})}^{h} = \sum_{h \in H} f_{(i_{tend}, s)}^{h} \qquad \forall i \in S \quad (8)
$$

$$
g_{e_k}^h - g_{s_k}^h \le -b_k f_{ak}^h + \rho(e_k - s_k) (1 - f_{ak}^h) \quad \forall h \in H, k \in K \quad (9)
$$

$$
g_{e_k}^h - g_{s_k}^h \ge -b_k f_{ak}^h - M(1 - f_{ak}^h) \qquad \forall h \in H, k \in K \quad (10)
$$

$$
g_{\epsilon_a}^h - g_{\sigma_a}^h \leq -\beta_a f_a^h
$$
$$+ \rho (\epsilon_a - \sigma_a) (1 - f_a^h) \qquad \forall h \in H, a \in A^R \quad (11)$$

$$g_{\epsilon_a}^h - g_{\sigma_a}^h \geq -\beta_a f_a^h - M (1 - f_a^h) \qquad \forall h \in H, a \in A^R \quad (12)$$

$$g_{\pi(t)}^h - g_t^h \leq \rho (\pi(t) - t) (1 - \sum_{k \in K_{\pi(t)}} f_{ak}^h - \sum_{a \in A_t^R} f_a^h) \qquad \forall h \in H, t \in \tilde{T} \quad (13)$$

$$g_{\pi(t)}^h - g_t^h \geq - \sum_{k \in K_{\pi(t)}} b_k f_{ak}^h - \sum_{a \in A_t^R} \beta_a f_a^h \qquad \forall h \in H, t \in \tilde{T} \quad (14)$$

$$g_0^h = B^{max} \qquad \forall h \in H \quad (15)$$

$$g_{tend}^h \geq B_{max} (1 - x_h) \qquad \forall h \in H \quad (16)$$

$$g_t^h \in \mathbb{R}^+, \quad g_t^h \leq B^{max} \qquad \forall h \in H, t \in \tilde{T} \quad (17)$$

$$z_i \in \mathbb{Z}^+, \quad z_i \leq C_i \qquad \forall i \in S \quad (18)$$

$$x_h, f_a^h \in \{0, 1\} \qquad \forall h \in H, a \in A \quad (19)$$

The objective function (1) maximizes the total profit over the long-term horizon comprising Y years by computing the difference between the total profit (i.e. profit made in a typical day multiplied by the total number of days) and the initial investment costs required to set up the EVSS. The daily profit is calculated as the revenue obtained by renting EVs minus the recharging and relocation costs. Regarding the recharging costs, recall that there are different unit electricity costs for charging at daytime or nighttime. The amount of electricity charged during the day in EV h is given by $g_{tend}^h - (B_{max} - \sum_{k \in K} b_k f_{ak}^h - \sum_{a \in A^R} \beta_a f_a^h)$, the one charged during the night by $(B^{max} - g_{tend}^h)$.

Constraints (2)-(8) link the design and operational decision variables and ensure consistent trip-EV assignment and EV movements. Constraints (2) thus state that a trip, if accepted, is carried out by at most one EV. Likewise,
Constraints (3) guarantee that an EV $h$, if purchased, is assigned to at most one trip in each period $t$. Constraints (4) ensure that the number of EVs that remain parked at station $i$ at time $t$, computed as the total flow on the waiting and initialization arcs entering node $i_t$ in $G$, does not exceed the number of chargers $z_i$ installed at this station. Constraints (5)-(6) guarantee that each purchased EV is assigned to a single station at the beginning of the day and remains parked at a single station at the end of the day. Constraints (7) are the flow conservation constraints. They ensure that, for each node $i_t \in N \setminus \{s, t\}$ and each EV $h \in H$, the sum of incoming flows is equal to the sum of outgoing flows. Finally, Constraints (8) ensure that the number of EVs present at each station $i \in S$ is the same at the beginning and the end of the day, thus guaranteeing that the network is reset to its initial state each night.

Constraints (9)-(14) manage the evolution of the battery SOC of each EV during the day by relying on the continous variables $g_t^h$. Constraints (9)-(10) ensure that when EV $h$ carries out trip $k$, i.e. when $f_{ak}^h = 1$, its battery SOC between the starting period $s_k$ of the trip and its ending period $e_k$ decreases by exactly $b_k$; these constraints are inactive when $f_{ak}^h = 0$. Similarly, Constraints (11)-(12) ensure that the battery SOC of an EV undergoing a relocation decreases by the right amount of energy. Note that the value of the constant $M$ appearing in Constraints (10) and (12) can be set to $M = \max(\max_{k' \in K}\{b_{k'}\}, \max_{a' \in A^R}\{\beta_{a'}\})$. Constraints (13)-(14) track the evolution of the battery SOC of EV $h$, between two consecutive time points $t$ and $\pi(t)$ in $\tilde{T}$. If an EV is carrying out a trip or being relocated over this interval, i.e. if $\sum_{k \in K_{\pi(t)}} f_{ak}^h - \sum_{a \in A_t^R} f_a^h = 1$, its battery SOC should decrease according to the trip's consumption or relocation consumption over the period $(\pi(t) - t)$. Otherwise, the EV is parked, in which case the battery SOC can only increase by at most $\rho(\pi(t) - t)$.

Constraints (15) indicate that the battery SOC of every EV is initialized at $B_{max}$ at the beginning of the planning day, and Constraints (16) ensure that EVs that are not purchased remain with a full battery. Finally, Constraints (17)-(19) define the nature and range of decision variables.

# 4. Numerical results

We now seek to numerically assess the impact of incorporating relocation into the problem modeling on the optimal design of an EVSS.
### 4.1. Instances

We randomly generated a set of 30 small-size instances of the problem. We used a planning horizon of $Y = 7$ years and divided the typical day into $T = 13$ one-hour periods. We considered 6 groups of 5 instances, each one corresponding to different values of the number of stations and trips parameters. The EV number is $|H| = \lfloor(\frac{1}{3}|K|)\rfloor$, with $B_{max} = 36.5$ kWh.

<table><thead><tr><th>Instance group</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><th>|S|</th><td colspan="6">6</td></tr><tr><th>|K|</th><td>60</td><td>80</td><td>100</td><td>32</td><td>48</td><td>64</td></tr></tbody></table>

For each instance, the coordinates of EV sharing stations are randomly selected in $[0, 50]^2$ according to a uniform distribution. Each station is randomly assigned a label (work or residence). We then randomly generate a set of trip requests (described by the origin, destination and departure time). To account for demand seasonality during the day, we vary the probability of occurrence of a trip according to the period of the day (morning, middle day, evening) and to the station labels. For instance, a trip from a residence to a work location is more likely to happen in the morning, while the opposite is more likely to occur in the evening. Finally, the duration and energy consumption associated to each trip are randomly generated according to a uniform distribution. The duration lies between the minimum travel time calculated based on the origin/destination distance as well as the average EV speed, while the maximum travel time corresponds to a full battery autonomy. The consumption lies between the minimum consumption calculated based on the origin/destination distance and the average consumption per unit distance, while the maximum consumption corresponds to driving during the whole trip duration.

### 4.2. Impact of EV daytime relocation on the EVSS long-term profitability

We first seek to assess the general impact of daytime EV relocation on the profitability of an EVSS. To this aim, we solved each considered instance with two variants of the MILP model presented in Section 3:

- the first variant, called EMDR, considers the model as such and allows both daytime and nighttime EV relocation through flows circulating on arcs of $A^R$,

- the second variant, called EMNR, considers the same model, allows nighttime relocation in order to reset the EVSS in its initial state after shutdown
but forbids any daytime relocation by setting $f_a^h = 0$ for all $h \in H$ and $a \in A^{DR}$.

Both models were solved using the IBM ILOG CPLEX (v12.8) mathematical solver under the default settings. The tests were done on a computer running with processor 1.6GHz Dual-Core Intel Core™ i5 and 8 Gb RAM memory.

For each instance and each model, we record the value of the total profit, operational profit and investment cost. We also compute the value of the service level defined as the proportion of accepted trips. For each of these attributes, we then compute the percentage variation between the EMDR and the EMNR model, i.e. the relative difference between the value of the attribute in the optimal solution of EMDR model and its value in the optimal solution of EMNR model. The corresponding results are reported in Table 1 in which each line corresponds to the average value over each group of 5 instances.

<table><caption>Table 1: Gains from implementing EVSS design with day relocation</caption><thead><tr><th>Group</th><th>Total Profit</th><th>Op. Profit</th><th>Inv. Costs</th><th>Service level</th></tr></thead><tbody><tr><td>1</td><td>+20.2 %</td><td>+5.9 %</td><td>-6.33 %</td><td>+15.1 %</td></tr><tr><td>2</td><td>+15.6 %</td><td>+3.2 %</td><td>-11.09 %</td><td>+11.1 %</td></tr><tr><td>3</td><td>+11.9 %</td><td>+4.4 %</td><td>-3.89 %</td><td>+14.4 %</td></tr><tr><td>4</td><td>+27.9 %</td><td>+10.4 %</td><td>-3.44 %</td><td>+23.0 %</td></tr><tr><td>5</td><td>+26.0 %</td><td>+5.9 %</td><td>-13.59 %</td><td>+17.5 %</td></tr><tr><td>6</td><td>+16.9 %</td><td>+4.0 %</td><td>-11.52 %</td><td>+15.7 %</td></tr></tbody></table>

Results from Table 1 first indicate that the EVSS long-term total profit is significantly increased by an average value of 19.75% (1st column) when daytime relocation is considered. This improvement can be explained by an increase in the daily operational profit (2nd column) coming from a higher trip acceptance rate (4th column) which translates into more revenue. Thus, even if the daily operational costs go up due to rising relocation and recharging costs, this increase is overcompensated by the additional revenue. Furthermore, we also observe an overall decrease in the investment cost. Whereas the fleet size displays only small variations between the EMDR and EMNR optimal solutions, the total number of installed chargers significantly decreases when daytime relocation is allowed. This can be expected as, in this case, EVs are more likely to be on the road than parked at stations. Thus, in a nut-
shell, considering daytime relocation in the EVSS design problem enables a better utilization of the EV fleet and a better demand coverage, and this with a smaller number of installed chargers. It thus leads to a strong increase of the long-term profitability of the EVSS estimated by the optimization model.

### 4.3. Value of daytime relocation for the EVSS design problem

We now seek to assess the value of considering daytime relocation in the modeling of the EVSS strategic design problem. To this aim, we used the following procedure for each of the 30 considered instances:

- We first solve the problem using the EMNR model and record the design decisions it recommends into vectors $x^{EMNR}$ and $z^{EMNR}$.

- We then add constraints $x = x^{EMNR}$ and $z = z^{EMNR}$ into the formulation of the EMDR model and solve the obtained MILP. Let $Z'_{EMDR}$ be its optimal value: $Z'_{EMDR}$ represents the profit one may get from the EVSS designed by the EMNR model overlooking daytime relocation when relocation is in fact used in practice.

- We finally compute the value of day relocation as $VDR = (Z_{EMDR} - Z'_{EMDR})/Z_{EMDR}$.

<table><caption>Table 2: Value of considering daytime relocation</caption><thead><tr><th>Group</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>VDR(%)</td><td>5.92</td><td>4.20</td><td>2.61</td><td>8.29</td><td>8.43</td><td>5.58</td></tr></tbody></table>

Table 2 displays the average value of $VDR$ over the 5 instances belonging to each group. We note that, overall, the average value of $VDR$ is 5.84%. This means that using the EMDR model explicitly considering daytime relocation to design an EVSS may lead to design decisions providing a significantly better profitability that the one of design decisions recommended by the EMNR model overlooking daytime relocation. This thus shows that, in general, incorporating day relocation into the problem modeling has a strong impact on the quality of the design decisions.

### 4.4. Effect of demand spatio-temporal imbalances on the value of day relocation

We noticed that the observed value of the VDR over the 30 instances displays a significant variability, with values ranging from 0.2% to 20.6%. In this subsection, we show that this strong variability may be partly due to
the fact that the demand (i.e. the trip requests) displays variable levels of
spatio-temporal demand imbalance across the instances.

We thus introduce a new measure quantifying the level of demand imbal-
ances defined as follows. We first partition the scheduling horizon T into P
disjoint time intervals. Let $T_p \subset T$ be the time interval $p$. We then compute,
for each station $i$ and each interval $p$, an imbalance measure coefficient de-
fined as follows: $\theta_{(i,p)} = \text{abs}(\sum_{t \in T_p} \frac{(|\delta^{-}(i_t)| - |\delta^{+}(i_t)|)}{(|\delta^{-}(i_t)| + |\delta^{+}(i_t)|)})$.

$\theta_{(i,p)}$ thus computes the ratio of the difference between the number of incom-
ing arcs and the number of leaving arcs over the total number of arcs. Note
that $\theta_{(i,p)} \in [0, 1]$, with 0 corresponding to a perfectly demand balance and 1
to the highest demand imbalance possible. Finally, we compute the average
value of $\theta_{(i,p)}$ over all time intervals and stations: $\Theta = \frac{1}{|S||P|} \sum_{i \in S} \sum_{p \in P} \theta_{(i,p)}$.

The scatter plot provided in Figure 2 gives the value of VDR as a function
of the value of Θ for the 30 studied instances. We graphically observe that the
data points slope upwards from the lower-left corner of the chart towards the
upper-right. Furthermore, the linear correlation coefficient is equal to 0.67
and was shown to be significantly different from 0 by a Student t-test. This
suggests that, for a given instance, one may use the value of the imbalance
mesure coefficient Θ as a good indicator of whether day relocation should be
included in the strategic design problem modeling. When demand imbalance
is low (typically Θ is below 0.40), day relocation may be overlooked without
any major consequence on the long-term profitability of the designed network.
But when there are strong demand imbalances (typically Θ is above 0.40),
incorporating day relocation into the problem modeling is key to obtain good-
quality design decisions.

**5. Conclusion**

This work considered the optimal design of an EVSS and investigated
whether explicitly modeling an operational feature, the EV relocation of
cars during the day by employees, is needed to obtain good-quality design
decisions. We provided a numerical assessment of the value of integrating
relocation operations into the problem modeling and showed that this value
can be significant, especially when there are strong spatio-temporal imbal-
ances in the trip requests. However, these results were obtained on small-size
instances. Future research might thus focus on the development of efficient
solution approaches for this problem so as to be able to extend this analysis
to larger instances.
<figure><img src="image_2.png" /><figcaption>Figure 2: Value of daytime relocation as the function of the demand spatio-temporal imbalances</figcaption></figure>
**Acknowledgment** This work was supported by a public grant as part of the French Investissement d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH and by a strategic research grant from United Arab Emirates University, Emirates Center for Mobility Research, reference 12R149.

**References**

[1] G. Brandstatter, M. Leitner, I. Ljubic, "Location of Charging Stations in Electric Car Sharing Systems" Transportation Science, vol. 54/5, pp. 1408-1438, 2020.

[2] G. Brandstatter, C. Gambella, M. Leitner, E. Malaguti, F. Masini, J. Puchinger, M. Ruthmair, D. Vigo, "Overview of Optimization Problems in Electric Car-Sharing System Design and Management", in Dynamic Perspectives on Managerial Decision Making, vol 22. Springer, Cham, pp 441–471, 2016.

[3] M. Xu, T. Wu, Z. Tan, "Electric vehicle fleet size for carsharing services considering on-demand charging strategy and battery degradation", Transportation Research Part C, vol. 127, pp. 103146, 2021.

[4] M. Xu, Q. Meng, "Fleet sizing for one-way electric carsharing services considering dynamic vehicle relocation and nonlinear charging profile", Transportation Research Part B, vol. 128, pp. 23–49, 2019.

[5] B. Boyaci, K.G. Zografos, N. Geroliminis, "An optimization framework for the development of efficient one-way car-sharing systems", European Journal of Operational Research, vol. 240, pp. 718–733, 2015.

[6] J. Chang, M. Yu, S. Shen, M. Xu, "Location Design and Relocation of a Mixed Car-Sharing Fleet with a CO2 Emission Constraint", Service Science, vol. 9/3, pp.205–218, 2017.

[7] Y. Hua, D. Zhao, X. Wang, X. Li, "Joint infrastructure planning and fleet management for one-way electric car sharing under time-varying uncertain demand", Transportation Research Part B, vol. 128, pp. 185–206, 2019.

[8] K. Huang, K. An, G.H. de Almeida Correia, "Planning station capacity and fleet size of one-way electric carsharing systems with continuous
state of charge functions", European Journal of Operational Research, vol. 287, pp. 1075-1091, 2020.

[9] S. Bekli, B. Boyaci, K.G. Zografos, "Enhancing the performance of one-way electric carsharing systems through the optimum deployment of fast chargers", Transportation Research Part B, vol. 152, pp. 118-139, 2021.

[10] A. Deza, K. Huang, M.R. Metel, "Charging station optimization for balanced electric car sharing", Discrete Applied Mathematics, vol. 308, pp. 187-197, 2022.

[11] Y. Zou, C. Yang, J. Yang, "EV-sharing station location and vehicle relocation with parking rewards and punishments mechanism", International Journal of Sustainable Transportation, vol. 15/4, pp. 306-322, 2021.

[12] M. Nicholas, M.R. Bernard, "Success factors for electric car-sharing", International council on clean transportation (ICCT), Working Paper 2021-30, August 2021.

[13] Car-sharing for all. Mobilize. https://www.mobilize.com/en/mobility-services/individuals-and-companies/car-sharing-for-all/ (accessed Mar. 3, 2024)