# On the approximability and energy-flow modeling of the electric vehicle
sharing problem

Welverton R. Silva, Fábio L. Usberti, Rafael C. S. Schouery Corresponding
author.

Institute of Computing, University of Campinas
Campinas, São Paulo, Brazil

ABSTRACT. The electric vehicle sharing problem (EVSP) arises from the planning
and operation of one-way electric car-sharing systems. It aims to maximize the
total rental time of a fleet of electric vehicles while ensuring that all of
the demands of the customer are fulfilled. In this paper, we expand the
knowledge on the complexity of the EVSP by showing that it is NP-hard to
approximate it to within a factor of $n^{1-\epsilon}$ in polynomial time, for
any $\epsilon>0$, where $n$ denotes the number of customers, unless P = NP. In
addition, we also show that the problem does not have a monotone structure,
which can be detrimental to the development of heuristics employing
constructive strategies. Moreover, we propose a novel approach for the
modeling of the EVSP based on energy flows in the network. Based on the new
model, we propose a relax-and-fix strategy and an exact algorithm that uses a
warm-start solution obtained from our heuristic approach. We report
computational results comparing our formulation with the best-performing
formulation in the literature. The results show that our formulation
outperforms the previous one concerning the number of optimal solutions
obtained, optimality gaps, and computational times. Previously, $32.7\%$ of
the instances remained unsolved (within a time limit of one hour) by the best-
performing formulation in the literature, while our formulation obtained
optimal solutions for all instances. To stress our approaches, two more
challenging new sets of instances were generated, for which we were able to
solve $49.5\%$ of the instances, with an average optimality gap of $2.91\%$
for those not solved optimally.

Keywords: One-way car-sharing, Electric vehicle, Mixed-integer linear
programming.

##  1 Introduction

Shared mobility is an emerging segment of transportation systems that
advocates for the use of vehicles shared by many users, either concurrently or
sequentially. Car-sharing is one type of shared mobility that rents cars for
short periods, low costs, for multiple users, in a single day. It can improve
the quality of urban transport systems by reducing congestion and the need for
additional parking spaces (Shaheen and Cohen, 2007; Zakaria et al., 2014). As
an added social benefit, car-sharing services also minimize the urban
concentration of polluting particles in the air if the cars are powered by
electricity. In this sense, electric car-sharing represents a transition to
more sustainable models of urban transportation (Gambella et al., 2018).

In station-based car-sharing systems, users can only pick up and drop off
rental cars at dedicated stations. Such systems provide two main types of
sharing models, namely _two-way_ and _one-way_. Users must pick up and drop
off the car at the same station if the system requires two-way trips. If the
system allows one-way trips, however, users can return the car to any station
of their choice as long as the drop-off station and time are specified in
advance (Nourinejad and Roorda, 2015).

In this work, we consider a station-based electric car-sharing system that
allows one-way trips. On this matter, we focus on a combinatorial optimization
problem that arises from the planning of driving operations called the
electric vehicle sharing problem (EVSP), proposed by Silva et al. (2023), and
described next. Given a set of stations, a set of (electric) vehicles
distributed at the stations, and a set of customers with one or more driving
demands, find an assignment plan (as a space-time route) for each vehicle such
that (i) whenever one customer’s demand is fulfilled, all of their other
demands are also fulfilled, (ii) no vehicle runs out of charge before the
customer reaches the drop-off station, (iii) no station exceeds the number of
parked vehicles, and (iv) the total rental time of the assignment plans for
the vehicles is maximized.

The main difference between the EVSP and other electric car-sharing problems
related in the operations research literature is the _customers’ satisfaction
criteria_ , that is, whenever one customer’s driving demand is fulfilled, all
their other demands must also be fulfilled.

Figure 1 illustrates an example where a customer has four driving demands. In
this example, commuting to work, there is one demand to drive from station A
(in a residential area) to station B, located near a subway system, and
another demand to drive from station C to station D (in a central business
district). After a working day, the customer returns to their home with two
additional driving demands.

Station AStation BStation CStation DHomeWorkSubwayBefore a working day

Station DStation CStation BStation AWorkHomeSubwayAfter a working day

Figure 1: An example of a customer with four driving demands in a one-way car-
sharing system.

In that case, not guaranteeing that each of the four customer’s driving
demands will be fulfilled could be detrimental to their needs. For the car-
sharing service provider, in a general context, customers canceling their
driving demands as a result of having some of their demands not guaranteed to
be fulfilled can have a substantial negative impact on the planning of trips,
which includes routes and timetables of the cars.

###  1.1 Previous and related work

The majority of the studies addressing combinatorial optimization in the
literature have focused on vehicle relocation operations (Ait-Ouahmed et al.,
2018; Boyacı et al., 2015, 2017; Bruglieri et al., 2014, 2017; Gambella et
al., 2018; Huang et al., 2020; Qin et al., 2022; Zhao et al., 2018); location
for changing stations (Brandstätter et al., 2017; Çalık and Fortz, 2019; Deza
et al., 2022); and fleet size planning (George and Xia, 2011; Xu and Meng,
2019). In this subsection, we present a brief review of the literature
strictly related to our problem.

The EVSP is a variant of the car-sharing assignment problem first studied by
Böhmová et al. (2016), which aims to maximize the number of served customers.
For a complexity analysis, the authors formally define a particular case of
the problem with two stations, called  _transfers for commuting_ (TFC), in
which each customer has exactly two driving demands that are between the two
stations (in opposite directions). They prove that the TFC problem is an NP-
hard problem, and also an APX-hard problem, even if there is only one car and
all of the demands for rent cars take the same amount of time to move between
the two stations.

Silva and Schouery (2020) presented a mixed-integer linear programming
formulation for the TFC problem, which is modeled as a network flow problem
over time. In their work, the authors propose a preprocessing procedure to
reduce the network size, which implies decreasing the number of binary
variables and constraints in the mixed-integer linear program. They also
provide an additional set of constraints to strengthen the formulation, which
can eliminate integer solutions, but that preserves at least one optimal
solution. To demonstrate the effectiveness of their approaches, computational
experiments were conducted on random instances.

Luo et al. (2020) address the on-line version of the TFC problem, where
customers submit a pair of demands and the scheduler must decide whether to
accept each pair of demands immediately at the time when it is submitted. The
authors investigate the impact of different constraints on the booking time of
demand pairs and provide lower bounds on the competitive ratio. Furthermore,
they propose a $4$-competitive algorithm for this problem with variable
booking times and slotted pick-up times. For a study of two variants of this
on-line version, see the work of Luo et al. (2022).

The EVSP is introduced by Silva et al. (2023), to optimize the operation of a
fleet of electric vehicles for one-way car-sharing systems. The authors
propose four mixed-integer linear programming formulations, based on two main
ideas, namely homogeneous and heterogeneous space-time networks. Also, the
proposed formulations are compared theoretically, in terms of the strength of
their linear programming relaxation, and computationally, in terms of runtime
and solution quality, using benchmark instances based on real data from the
VAMO Fortaleza system (City Hall of Fortaleza – Brazil, 2018).

###  1.2 Problem description

Hereafter, we apply the same notation adopted by Silva et al. (2023), as
described next. In the following, consider the superscript
$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,\leavevmode\nobreak\ \mkern
3.0mu$}}$ as an “outgoing” labeling and the superscript
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\leavevmode\nobreak\
\mkern 3.0mu$}}$ as an “incoming” labeling when specifying that something
(e.g., a vehicle) is leaving or arriving at a location or position (e.g., a
station), respectively.

Let $\matheuler{C}$ and $\matheuler{S}$ be the sets of customers and stations,
respectively, and let $\matheuler{T}=\\{t_{1},\dots,t_{m}\\}$ be a set of
discrete-time instants, not necessarily uniformly distributed, to be
considered in a planning horizon (given in minutes).

For each customer $c\in\matheuler{C}$, let $\matheuler{D}_{c}$ be the set of
demands for customer $c$. All demand in $\matheuler{D}_{c}$ is described by a
quintuple $(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j},\varepsilon)\in(\matheuler{S}\times\matheuler{T})^{2}\times\mathbb{Q}_{>0}$
such that $t_{i}<t_{j}$, with
$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern 3.0mu$}}$ as the
pick-up station, $t_{i}$ as the departure time,
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern 3.0mu$}}$ as the
drop-off station, $t_{j}$ as the arrival time, and $\varepsilon$ as the
estimate of the energy required during the rental. In a set
$\matheuler{D}_{c}$ of demands, there are no overlapping rental periods. In
addition, all demands from customers are grouped into one set. Let
$\matheuler{D}=\bigcup_{c\in\matheuler{C}}\matheuler{D}_{c}$ denote the set of
all demands.

For each station $s\in\matheuler{S}$, let $\matheuler{V}_{s}$ be the set of
EVs initially located at $s$. Each station $s\in\matheuler{S}$ has a capacity
$\textsf{C}_{s}$ and a number $\textsf{R}_{s}$ of charging facilities, such
that $\textsf{R}_{s}\leq\textsf{C}_{s}$ and
$|\matheuler{V}_{s}|\leq\textsf{C}_{s}$. Let
$\matheuler{V}=\bigcup_{s\in\matheuler{S}}\matheuler{V}_{s}$ denote the set of
all EVs in the system.

All EVs and charging facilities are identical, in which
$\mu\in\mathbb{Q}_{>0}$ represents the energy supplied by a charging facility
per time unit (in watts per minute), and L represents the battery capacity (in
watt-minutes). Additionally, let $\textsf{L}^{v}$ denote the amount of energy
that is stored in the battery of vehicle $v\in\matheuler{V}$ at the beginning
of the planning horizon.

The objective of the EVSP is to maximize the total rental time by assigning a
sequence of driving demands to the fleet of vehicles, associated with a
feasible assignment plan, such that whenever one customer’s demand is
fulfilled, all other customer’s demands are also fulfilled.

######  Remark 1.

An  _assignment plan_ for a vehicle $v\in\matheuler{V}$ is feasible if and
only if, for each demand $(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j},\varepsilon)$ in a sequence of driving demands
to be fulfilled, it satisfies the following conditions: the vehicle $v$ is at
the pick-up station $\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$ at time $t_{i}$; the battery energy of $v$ is greater than or equal
to the required energy $\varepsilon$; and there is a parking space at the
drop-off station that is available immediately before time $t_{j}$. Moreover,
the assignment plan must specify if and when the vehicle $v$ is connected to a
charging facility.

To better clarify the EVSP, we give an example with three stations, each with
a capacity for two vehicles, such that one parking space is equipped with a
charging facility while the other is not, and there is only one (fully
charged) vehicle initially available. The vehicle’s battery has a capacity of
$30$ kilowatt-hours (kWh), and the charging facility provides $0.17$ kWh of
energy per minute. The customers’ driving demands are shown in Table 1.

Table 1: Details of the reservation requests for rental.

Customer | Pick-up station | Departure time | Drop-off station | Arrival time | Energy required (kWh)
---|---|---|---|---|---
$c_{1}$ | $s_{1}$ | 7:28 | $s_{2}$ | 8:06 | 6.34
$c_{1}$ | $s_{2}$ | 11:23 | $s_{1}$ | 11:54 | 5.17
$c_{2}$ | $s_{3}$ | 8:35 | $s_{3}$ | 9:32 | 9.00
$c_{3}$ | $s_{1}$ | 9:46 | $s_{3}$ | 10:12 | 4.33
$c_{4}$ | $s_{2}$ | 7:40 | $s_{1}$ | 8:02 | 3.67
$c_{4}$ | $s_{1}$ | 8:54 | $s_{3}$ | 10:28 | 15.66
$c_{5}$ | $s_{2}$ | 7:28 | $s_{1}$ | 8:23 | 9.17
$c_{6}$ | $s_{2}$ | 9:51 | $s_{3}$ | 10:50 | 9.83
$c_{7}$ | $s_{1}$ | 10:12 | $s_{2}$ | 10:46 | 5.67

Each vehicle’s assignment plan is shown in Figure 2 as a sequence of arrows.
The rental and return events are represented by nodes that display pie charts
visualizing the vehicle’s remaining energy; the waiting order is displayed as
a dashed arrow (with a plugin symbol, if it is recharging) when it is
available for rental; and the rental order as a full arrow with a symbol
bearing the customer’s identification when it is fulfilling a customer’s
driving demand.

7:008:009:0010:0011:0012:00$c_{1}$$c_{5}$$c_{2}$$c_{7}$$c_{6}$$c_{1}$$s_{1}$$s_{2}$$s_{3}$Waiting
for the rental and recharging the batteryWaiting for the rentalCurrent energy
of thevehicle’s batteryFulfilling the customer’sdriving demand

Figure 2: Illustration of assignment plans (visualized as a blue, red, and
yellow sequence of arrows) for the rental requests in Table 1.

The assignment plans illustrated in Figure 2 show that customers $c_{3}$ and
$c_{4}$ are turned away (meaning that none of their demands have been
fulfilled), whereas $c_{1}$, $c_{2}$, $c_{5}$, $c_{6}$, and $c_{7}$ are
served. It is worth noting that $c_{1}$ has both of their demands fulfilled by
different vehicles. Despite being used for illustration only, those assignment
plans represent an optimal solution. Additionally, by rearranging the parking
spaces where the vehicles are parked, or by choosing whether to charge them or
not, several optimal solutions can be obtained.

######  Remark 2.

When a driving demand is selected to be fulfilled by a vehicle $v$ from
station $\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern 3.0mu$}}$ to
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern 3.0mu$}}$ ,
starting at time $t_{i}$ and ending at time $t_{j}$, it means that the vehicle
$v$ will be no longer parked in a parking space of the station
$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern 3.0mu$}}$ at time
$t_{i}$ and that it will be parked in a parking space of the station
$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern 3.0mu$}}$ at time
$t_{j}$, in such a way that the fulfilling period means a left-closed and
right-open interval.

In addition, to specify the initial distribution of vehicles, we denote by
$\matheuler{V}^{\prime}_{s}\subseteq\matheuler{V}_{s}$ the set of vehicles
originally placed in the parking spaces equipped with charging facilities. If
the required energy $\varepsilon$ of the demand is not necessary, we omit it
from the notation and denote the demand as a quadruple
$(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D}$.

###  1.3 Our contributions and outline

In this paper, we expand on the findings of Silva et al. (2023) with respect
to the complexity, formulations, and exact solution of the EVSP. More
specifically, we show theoretical results on the inapproximability, a search
space analysis, a new modeling approach for the EVSP, which is a two-index
energy flow formulation — unlike the usual three-index vehicle flow
formulations commonly utilized in the literature (Kek et al., 2009; Jorge et
al., 2015; Gambella et al., 2018). The main contributions of this paper can be
summarized as follows.

  1. (i)

A prove that, for any $\epsilon>0$, it is impossible to approximate EVSP in
polynomial time within a factor of $n^{1-\epsilon}$, where $n$ is the number
of customers, unless P = NP.

  2. (ii)

A novel mathematical formulation for the EVSP, where the energy of each
vehicle is used as continuous flow instead of binary flow in space-time
networks.

  3. (iii)

A relax-and-fix heuristic to produce high-quality solutions.

  4. (iv)

An exact algorithm, which employs two schemes of variable-fixing and a warm-
start solution to efficiently solve instances with several vehicles and
parking spaces.

  5. (v)

Optimal solutions are obtained for all instances of the previous benchmark.

  6. (vi)

A new benchmark is proposed to raise the difficulty bar for future
methodologies.

The remainder of this paper is organized as follows. In Section 2, we present
theoretical results on the inapproximability of the EVSP and briefly address
how it does not have a monotone structure that preserves the feasibility of a
bottom-up (or top-down) search. In Section 3, we describe our proposed mixed-
integer linear programming formulation based on energy flows. In Section 4, we
present a heuristic and an exact approach derived from our formulation. In
Section 5, we present and discuss the computational results. Finally, in
Section 6, we give concluding remarks and an outlook on future research.

##  2 Problem’s complexity

In this section, we study the computational complexity of the EVSP in a
particular case where recharging vehicles is not necessary. Even with this
simplification, we can already obtain some unfavorable complexity results.

###  2.1 Inapproximability results

In this section, we present theoretical findings on the inapproximability of
the EVSP, including a proof that it is not in APX, or simply put, it does not
have a polynomial-time algorithm with constant approximation factor, unless P
= NP. We go even further by showing it is not approximable by a factor of
$n^{1-\epsilon}$, for any $\epsilon>0$, unless P = NP.

If a problem is strongly NP-hard, then it does not have a pseudo-polynomial
time algorithm and it also does not have a fully-polynomial time approximation
scheme (FPTAS), unless P $=$ NP (Vazirani, 2001). Silva et al. (2023) shown a
polynomial reduction from the one-dimensional bin packing problem (BPP), a
well-known strongly NP-hard problem, to the EVSP. As a consequence, we have
the following theorem.

######  Corollary 1 (Silva et al. (2023), Corollary 4).

The EVSP is NP-hard in the strong sense even if every customer has only one
demand and when there is only one station.

Böhmová et al. (2016) have shown that the TFC problem, a special case of the
EVSP without batteries, is APX-hard using an L-reduction from the Max-3SAT(3).

######  Corollary 2 (Böhmová et al. (2016), Theorem 2).

The EVSP is APX-hard even when there are only two stations, every customer
has two demands, the rental time is the same for every demand, and there is
only one vehicle without battery.

On the approximability of the EVSP, an interesting question is whether there
is a polynomial-time algorithm that guarantees a constant approximation
factor. We answer this question by showing that the EVSP is not in APX, unless
P = NP. To this end, we propose a reduction from the maximum independent set
problem, for which it is known that no polynomial-time algorithm can
approximate it to within $n^{1-\epsilon}$ in general graphs with $n$ vertices,
for any $\epsilon>0$, unless P = NP (Håstad, 1999).

Maximum Independent Set Problem (MISP). Given a graph
$\matheuler{G}=(\matheuler{U},\matheuler{E})$, find an independent set in
$\matheuler{G}$ of maximum cardinality, that is, a largest subset of vertices
$\matheuler{U}^{*}\subseteq\matheuler{U}$, such that there is no edge in
$\matheuler{E}$ connecting two vertices in $\matheuler{U}^{*}$.

######  Theorem 1.

There is a polynomial-time reduction from MISP to EVSP.

First we describe a construction and some properties used to prove Theorem 1.

Instance Construction. Let $\matheuler{I}_{\textsf{MISP}}$ denote an arbitrary
instance of the MISP given by a set of vertices
$\matheuler{U}=\\{u_{1},\dots,u_{n}\\}$ and a set of edges
$\matheuler{E}=\\{e_{1},\dots,e_{m}\\}$. The trick is to construct an instance
of the EVSP, denoted by $\matheuler{I}_{\textsf{EVSP}}$, from
$\matheuler{I}_{\textsf{MISP}}$ in such a way that there is a one-to-one
correspondence between the customers in the constructed instance and the
vertices in the instance of the MISP. More precisely, each vertex
$u\in\matheuler{U}$ is associated with a customer, denoted by $c_{u}$. There
is only one station and a single vehicle with enough charge to fulfill all the
driving demands in the system.

In the following, we describe how the demands of the customers are organized
into gadgets. For every edge $e\in\matheuler{E}$, there is a gadget
$\textsf{G}_{e}$ with more than one driving demand starting and ending in it,
but configured so that all demands depart the station at once to ensure that
the rental periods overlap — meaning that at most one demand placed in
$\textsf{G}_{e}$ can be fulfilled. The gadgets are placed sequentially. See
Figure 3 for the exact configuration.

$\displaystyle\dotsc$$\textsf{G}_{e_{m}}$$\textsf{G}_{e_{m-1}}$$\textsf{G}_{e_{2}}$$\textsf{G}_{e_{1}}$

Figure 3: Placement of the gadgets for the given instance of the MISP. For
simplicity, there is only one bolded arrow in each gadget and it represents
all its driving demands.

Let $\matheuler{N}_{u}=\\{u\mkern 0.0mu\raise
2.32501pt\hbox{$\scriptstyle\prime$}\in\matheuler{U}:(u,u\mkern 0.0mu\raise
2.32501pt\hbox{$\scriptstyle\prime$})\in\matheuler{E}\\}$ be the neighborhood
of a vertex $u\in\matheuler{U}$. For each edge $e=(u,u\mkern 0.0mu\raise
2.32501pt\hbox{$\scriptstyle\prime$})\in\matheuler{E}$, customers $c_{u}$ and
$c_{u^{\prime}}$ have a demand placed in $\textsf{G}_{e}$ with the rental
periods equal to $1/|\matheuler{N}_{u}|$ and $1/|\matheuler{N}_{u^{\prime}}|$,
respectively. Note that since any customer $c_{u}$ has exactly
$|\matheuler{N}_{u}|$ demands, the total rental time of their demands is equal
to $1$.

Let $\rho$ be the polynomial time transformation from a MISP instance to a
EVSP instance described above, such that
$\matheuler{I}_{\textsf{EVSP}}=\rho(\matheuler{I}_{\textsf{MISP}})$. The
properties of that transformation are described in the following.

######  Corollary 3.

Let val$(\matheuler{S})$ denote the value of a solution $\matheuler{S}$. Let
$\matheuler{S}_{\textsf{EVSP}}$ denote a solution for
$\matheuler{I}_{\textsf{EVSP}}=\rho(\matheuler{I}_{\textsf{MISP}})$. If a
solution for $\matheuler{I}_{\textsf{MISP}}$, denoted by
$\matheuler{S}_{\textsf{MISP}}$, is constructed from
$\matheuler{S}_{\textsf{EVSP}}$, then val$(\matheuler{S}_{\textsf{EVSP}})=$
val$(\matheuler{S}_{\textsf{MISP}})$.

Proof. The proof follows directly from the construction of
$\matheuler{I}_{\textsf{EVSP}}$. We can use the fact that whenever a customer
$c_{u}$ is served, then any customer $c_{u^{\prime}}$, for $u\mkern
0.0mu\raise 2.32501pt\hbox{$\scriptstyle\prime$}\in\matheuler{N}_{u}$, cannot
be served. $\square$

The above lemma immediately gives us the following corollary.

######  Corollary 4.

Let val$(\matheuler{I}_{\textsf{EVSP}})$ and
val$(\matheuler{I}_{\textsf{MISP}})$ denote, respectively, the value for the
instances $\matheuler{I}_{\textsf{EVSP}}$ and
$\matheuler{I}_{\textsf{MISP}}$, where
$\matheuler{I}_{\textsf{EVSP}}=\rho(\matheuler{I}_{\textsf{MISP}})$. Then
val$(\matheuler{I}_{\textsf{EVSP}})=$ val$(\matheuler{I}_{\textsf{MISP}})$.

Proof (of Theorem 1). It is an immediate consequence of
LABEL:lemma:same_solution and Corollary 4. $\square$

From Theorem 1, we immediately deduce that the EVSP is not in APX, unless P =
NP, and we derive the following result.

######  Corollary 5.

For any fixed $\epsilon>0$, the EVSP cannot be approximated in polynomial
time within a factor of $n^{1-\epsilon}$, where $n$ denotes the number of
customers, unless P $=$ NP, even if there is only one station and one vehicle.

###  2.2 Non-monotone structure of the search space

In the face of the unfavorable results on the complexity and inapproximability
of the EVSP, we can assume that these results provide a theoretical
justification for the employment of heuristics, which are the most popular
approaches to tackling problems like this one. However, as we shall discuss
next, developing effective heuristics for the EVSP is not an easy task.

In many combinatorial optimization problems, such as the _knapsack problem_ ,
any feasible and consequently optimal solution can be found by starting with
an empty solution and iteratively adding elements (e.g., items), one by one,
in a predetermined order, without making the current solution infeasible. In
this case, we say that the optimization problem has an  _upward-monotone
structure_. Unfortunately, for the EVSP there are instances in which this
property does not hold, taking into account any ordering of the customers.

In a bottom-up search, whenever a new customer is added to a given feasible
solution (or, in a top-down search, after a served customer is removed), a
significant number of assignment plans may need to be reconfigured to maintain
feasibility. Any modification to an assignment plan, including a repair step,
may have a cascading impact that leaves many customers as partially served,
making the current solution infeasible. In the worst case, it will be
necessary to create a new assignment plan for each vehicle.

Figure 4 gives a small example showing that the EVSP does not have a monotone
structure that preserves the feasibility of a bottom-up (or top-down) search.
We first notice that all four depicted customers can be served simultaneously,
assuming that there is initially one vehicle available at each station with
enough charge to fulfill all the driving demands in the system. However, there
is no feasible solution where exactly three customers are served.

$\displaystyle t_{1}$$\displaystyle t_{2}$$\displaystyle t_{3}$$\displaystyle
t_{5}$$\displaystyle t_{4}$$\displaystyle t_{6}$$\displaystyle
t_{7}$$\displaystyle t_{8}$$\displaystyle
t_{9}$$c_{2}$$c_{1}$$c_{2}$$c_{4}$$c_{4}$$c_{3}$$c_{1}$$c_{3}$

Figure 4: An example where the upward-monotone structure does not hold.

All theoretical results presented in this section have ignored the possibility
of recharging the vehicle’s battery. This means that considering the energy
consumption and recharging of vehicle batteries can further increase the
complexity of developing efficient algorithms.

##  3 Mathematical formulation

In this novel formulation for the EVSP, we abstract the explicit assignment of
vehicles to demands, and their energy is modeled as flows in a space-time
network, where the space dimension is represented by parking spaces. When a
demand is selected to be fulfilled, it is modeled as a flow of energy from the
parking space (origin node) at the pick-up station to the parking space
(destination node) at the drop-off station, with a reduction according to the
energy consumed. Further details are presented and discussed in the following
paragraphs.

Let $\matheuler{P}_{s}$ be the set of parking spaces at station $s$, where
$|\matheuler{P}_{s}|=\textsf{C}_{s}$, for each $s\in\matheuler{S}$. Moreover,
for each station $s\in\matheuler{S}$ and each parking space
$\scalebox{0.93}{$p$}\in\matheuler{P}_{s}$, let
$\matheuler{T}^{p}_{\vphantom{0}}=\\{t\in\matheuler{T}:\exists(s,t)\in\Pi\\}$
be the set of time instants for  $p$ , where $\Pi$ is the union of all sets
$\\{(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i}),(\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\\}$, for each
$(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D}$, and let
$\matheuler{T}^{p}_{\,0}=\matheuler{T}^{p}_{\vphantom{0}}\cup\\{t_{0}\\}$ be
an extension of the set of time instants, where time $t_{0}$ indicates the
initial configuration of the system. We denote by
$\matheuler{P}=\bigcup_{s\in\matheuler{S}}\matheuler{P}_{s}$ the set of all
parking spaces.

We define a pair of decision variables $y^{p}_{t}$ and $\ell^{p}_{t}$, for all
$t\in\matheuler{T}^{p}_{\,0}$, where
$\scalebox{0.93}{$p$}\in\matheuler{P}_{s}$, for $s\in\matheuler{S}$. Each
variable $y^{p}_{t}$ is binary and takes the value $1$ if and only if the
parking space  $p$ is occupied by a vehicle at time $t$; whereas each variable
$\ell^{p}_{t}$ is continuous and stores the energy of the vehicle parked on
$p$ at time $t$, such that the energy stored in $\ell^{p}_{t}$ is at most
$\textsf{L}y^{p}_{t}$.

Whenever a demand is fulfilled, an origin parking space must transfer all
stored energy in the form of a flow to a destination parking space, as
explained earlier. We define two sets of decision variables, for each
$d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D}$. One of these sets is
obtained by defining a continuous variable $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}$, for each
$\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$; the other set is obtained by defining a continuous
variable $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}$, for each
$\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$. For example, a parking space  $p$ flows energy at
time $t$ to fulfill a demand $d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j},\varepsilon)$ only if
$\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$, $t_{i}=t$ and $\ell^{p}_{t-1}\geq\varepsilon$,
leading to $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}=\ell^{p}_{t-1}$ and $\ell^{p}_{t}=0$.

We introduce the recharging processes as follows. Let $\textsf{E}^{p}_{\,t}$
denote the amount of energy charged at parking space  $p$ at time
$t\in\matheuler{T}^{p}_{\vphantom{0}}$, such that it is equal to
$\mu(t-t^{\prime})$, for
$t^{\prime}=\max\\{t^{\prime}\\!\in\matheuler{T}^{p}_{\,0}\\!:t^{\prime}\\!<t\\}$,
if $p$ is equipped with a charging facility, and $0$ otherwise, for any
parking space $\scalebox{0.93}{$p$}\in\matheuler{P}$.

Figure 5 illustrates the modeling of the energy flow for a parking space  $p$
at time $t$, which is considered a node. For such node, the incoming energy
flow is either from a vehicle parked at the same parking space $p$ in time
$t-1$ (represented by variable $\ell^{p}_{t-1}$) or from a fulfilled demand
$d$ with parking space $p$ as destination at time $t$ (represented as the sum
of variables $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}$). The incoming flow
$\textsf{E}^{p}_{\,t}$ represents the battery recharge at parking space $p$
and time $t$. The outgoing flows are analogous.

$\ell^{p}_{t-1}$$\textsf{E}^{p}_{\,t}$$\ell^{p}_{t}$${\displaystyle\sum_{d}}\,\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}$${\displaystyle\sum_{d}}\,\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}$$\scalebox{0.93}{$p$},t$ Figure 5: An
illustrative example of the incoming and outgoing energy flows.

We define two additional sets of decision variables that indicate when energy
flows over a demand in a parking space  $p$ at time $t\in\matheuler{T}^{p}$.
We obtain one of these sets by defining a binary variable
$\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t}$ that takes value $1$ if there is a
demand $d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D}$, such that
$\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$ and $t_{i}=t$, and if and only if a demand $d$ is
fulfilled by the vehicle parked on  $p$ . Similarly, another set is obtained
by defining a binary variable $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ if there exists a demand
$d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D}$, such that
$\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$ and $t_{j}=t$, which takes value $1$ if and only if
any demand $d$ is fulfilled and the vehicle used for renting is parked at  $p$
.

We also define two other sets of decision variables indicating the movement of
a vehicle out of and into a station when a demand
$d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})$ is fulfilled, for each $d\in\matheuler{D}$.
One is obtained by defining a binary variable $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}$, for each
$\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$, and the other by defining a binary variable
$\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p^{{}_{\prime}}}_{d}$, for each
$\scalebox{0.93}{$p$}{\mkern 0.0mu\raise
2.32501pt\hbox{$\scriptstyle\prime$}}\in\matheuler{P}_{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$, that takes value $1$ if and only if $d$ is
fulfilled by a vehicle in which it is picked-up at  $p$ and dropped-off at
$p$ $\scriptstyle\prime$, respectively. Finally, we define a binary variable
$w_{c}$ that takes value $1$ if and only if customer $c\in\matheuler{C}$ is
served.

The EVSP is formulated as the following mixed-integer linear programming
problem.

( EVSP 3)

Maximize
$\displaystyle\sum\limits_{\mathclap{\begin{subarray}{c}c\in\matheuler{C}\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\sum\limits_{\mathrlap{\begin{subarray}{c}(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j}\\!)\in\matheuler{D}_{c}\\\
\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\left(t_{j}-t_{i}\right)w_{c}$ (1)
Subject to
$\displaystyle\sum\limits_{\mathrlap{\begin{subarray}{c}p\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}=w_{c}$ $\displaystyle\forall
c\in\matheuler{C},\,\forall d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D}_{c}$ (2)
$\displaystyle\sum\limits_{\mathrlap{\begin{subarray}{c}p\in\matheuler{P}_{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}=w_{c}$ $\displaystyle\forall
c\in\matheuler{C},\,\forall d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D}_{c}$ (3)
$\displaystyle\sum\limits_{\mathrlap{\begin{subarray}{c}d\in\matheuler{D}:s{\scriptscriptstyle=}\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t{\scriptscriptstyle=}t_{i}\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}=\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t}$ $\displaystyle\forall
s\in\matheuler{S},\,\forall\scalebox{0.93}{$p$}\in\matheuler{P}_{s},\,\forall
t\in\matheuler{T}^{p}$ (4)
$\displaystyle\sum\limits_{\mathrlap{\begin{subarray}{c}d\in\matheuler{D}:s{\scriptscriptstyle=}\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t{\scriptscriptstyle=}t_{j}\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}=\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ $\displaystyle\forall
s\in\matheuler{S},\,\forall\scalebox{0.93}{$p$}\in\matheuler{P}_{s},\,\forall
t\in\matheuler{T}^{p}$ (5) $\displaystyle\leavevmode\nobreak\
\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}+y^{p}_{t^{\prime}}\leq 1$
$\displaystyle\forall\scalebox{0.93}{$p$}\in\matheuler{P},\,\forall
t\in\matheuler{T}^{p}\\!,\,t^{\prime}\\!=\max\\{t^{\prime}\\!\in\matheuler{T}^{p}_{\,0}\\!:t^{\prime}\\!<t\\}$
(6) $\displaystyle\leavevmode\nobreak\
y^{p}_{t}=y^{p}_{t^{\prime}}-\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t}+\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$
$\displaystyle\forall\scalebox{0.93}{$p$}\in\matheuler{P},\,\forall
t\in\matheuler{T}^{p}\\!,\,t^{\prime}\\!=\max\\{t^{\prime}\\!\in\matheuler{T}^{p}_{\,0}\\!:t^{\prime}\\!<t\\}$
(7)
$\displaystyle\sum\limits_{\mathrlap{\begin{subarray}{c}p\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\,p}_{d}=\sum\limits_{\mathrlap{\begin{subarray}{c}p\in\matheuler{P}_{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}+\varepsilon w_{c}$ $\displaystyle\forall
d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j},\varepsilon)\in\matheuler{D}$ (8)
$\displaystyle\leavevmode\nobreak\ \\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\,p}_{d}\leq\textsf{L}\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}$ $\displaystyle\forall
d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j},\varepsilon)\in\matheuler{D},\,\forall\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$ (9) $\displaystyle\leavevmode\nobreak\
\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}\leq(\textsf{L}-\varepsilon)\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}$ $\displaystyle\forall
d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j},\varepsilon)\in\matheuler{D},\,\forall\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$ (10)
$\displaystyle\sum\limits_{\mathrlap{\begin{subarray}{c}d\in\matheuler{D}:p\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}\\!,t{\scriptscriptstyle=}t_{i}\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\,p}_{d}+\ell^{p}_{t}\,\leq\,\sum\limits_{\mathrlap{\begin{subarray}{c}d\in\matheuler{D}:p\in\matheuler{P}_{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}\\!,t{\scriptscriptstyle=}t_{j}\vphantom{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\matheuler{E}\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\matheuler{E}\mkern
2.0mu$}}$}\mkern-2.0mu}}}\end{subarray}}}\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}+\min(\ell^{p}_{t^{\prime}}\\!+\\!\textsf{E}^{p}_{\,t},\,\textsf{L}y^{p}_{t^{\prime}})$
$\displaystyle\forall\scalebox{0.93}{$p$}\in\matheuler{P},\,\forall
t\in\matheuler{T}^{p}\\!,\,t^{\prime}\\!=\max\\{t^{\prime}\\!\in\matheuler{T}^{p}_{\,0}\\!:t^{\prime}\\!<t\\}$
(11) $\displaystyle\leavevmode\nobreak\
y^{p}_{t_{0}}=1,\,\ell^{p}_{t_{0}}=\textsf{L}^{v}$
$\displaystyle\scalebox{0.93}{$p$}=\psi(v),\,\forall
v\in\matheuler{V}_{s},\,\forall s\in\matheuler{S}$ (12)
$\displaystyle\leavevmode\nobreak\ y^{p}_{t_{0}}=0,\,\ell^{p}_{t_{0}}=0$
$\displaystyle\forall\scalebox{0.93}{$p$}\in\matheuler{P}\\!\setminus\\!\\{\psi(v):\forall
v\in\matheuler{V}_{s}\\},\,\forall s\in\matheuler{S}$ (13)
$\displaystyle\leavevmode\nobreak\
y^{p}_{t}\in\\{0,1\\},\,\ell^{p}_{t}\in\mathbb{R}_{\geq 0}$
$\displaystyle\forall\scalebox{0.93}{$p$}\in\matheuler{P},\,\forall
t\in\matheuler{T}^{p}_{\,0}$ (14) $\displaystyle\leavevmode\nobreak\
\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}\in\\{0,1\\},\,\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\,p}_{d}\in\mathbb{R}_{\geq 0}$
$\displaystyle\forall d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D},\,\forall\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$ (15) $\displaystyle\leavevmode\nobreak\
\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}\in\\{0,1\\},\,\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,\ell\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,\ell\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}\in\mathbb{R}_{\geq 0}$
$\displaystyle\forall d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D},\,\forall\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}$ (16) $\displaystyle\leavevmode\nobreak\
\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t}\in\\{0,1\\}$
$\displaystyle\forall\scalebox{0.93}{$p$},t\in\matheuler{P}\\!\times\\!\matheuler{T}:\exists
d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D},\,\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}\\!,t=t_{i}$ (17) $\displaystyle\leavevmode\nobreak\
\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}\in\\{0,1\\}$
$\displaystyle\forall\scalebox{0.93}{$p$},t\in\matheuler{P}\\!\times\\!\matheuler{T}:\exists
d=(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D},\,\scalebox{0.93}{$p$}\in\matheuler{P}_{\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}}\\!,t=t_{j}$ (18) $\displaystyle\leavevmode\nobreak\
w_{c}\in\\{0,1\\}$ $\displaystyle\forall c\in\matheuler{C}$ (19)

The objective function (1) maximizes the sum of the rental time. Constraint
sets (2) and (3) ensure that each fulfilled demand uses a pick-up and drop-off
parking space, respectively, and that a customer is served if all of the
customer’s demands are fulfilled. Similarly, constraint sets (4) and (5),
respectively, impose that each parking space is free or occupied when the
demand is fulfilled (i.e., when there is an energy flow that fulfills a
demand). Constraint set (6) imposes the criteria for a parking space to be
occupied, and constraint set (7) ensures that the scheduling of parking spaces
is feasible. Note that to simplify the notation, we omit the existence
conditions for the variables $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ from the constraint sets (4) to (7).

Furthermore, constraint sets (8) to (11) represent the conservation of energy
flows. More specifically, set (8) imposes that for each fulfilled demand, the
outgoing energy flow from the pick-up parking space must be equal to the
incoming energy flow at the drop-off parking space plus the energy consumed by
the rental; whereas sets (9) and (10) limit the energy flow that fulfills a
demand, and the set (11) limits the energy stored in each parking space for
any given time instant to ensure the recharging process and prevent the
battery capacity from being exceeded by charging.

Next, constraint sets (12) to (13) specify an initial state of vehicles at
each station, where $\psi$ is an injection function from $\matheuler{V}_{s}$
to $\matheuler{P}_{s}$, for each $s\in\matheuler{S}$, that assigns each
vehicle to a parking space, such that if a vehicle $v$ belongs to
$\matheuler{V}^{\prime}_{s}$, then $v$ is associated with a parking space
equipped with a charging facility — otherwise, $v$ is associated with a
parking space that is not equipped with a charging facility. Finally,
expressions (14) to (19) are the domain constraints for the variables.

######  Remark 3.

The sets of binary variables $w_{c}$, $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ can be relaxed to be continuous within the
lower and upper binary bounds since these variables are guaranteed to take a
binary value by constraint sets (2) (and also (3)), (4) and (5), respectively.

It is important to note that the set of binary variables $y^{p}_{t}$ can also
be relaxed, and this can be proven by induction on the time instants, like the
following.

######  Proposition 1.

The formulation 3 has an integer-valued feasible solution even when the
integrality constraint in (14) is relaxed to be continuous.

Proof. This proof is made by induction on $i\in\mathbb{Z}_{\geq 0}$, for
$i\leq n$, here used to index the time instants in
$\matheuler{T}^{p}=\\{t_{0},\dots,t_{n}\\}$, for any $p\in\matheuler{P}$. When
$i=0$ (i.e., for the initial time instant), the variable $y^{p}_{t_{0}}$ can
only be $0$ or $1$, which follows directly from constraint sets (12) and (13).
Let us assume, by induction, that the proposition holds for a given integer
$k$, such that $0\leq k<n$, and consider the case for $i=k+1$. Then, taking
into account the constraint set (7), in which the equation can be rewritten as

$y^{p}_{t_{i}}=y^{p}_{t_{i-1}}-\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t_{i}}+\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t_{i}},$

we will prove that the left-hand term can only be $0$ or $1$.

By the induction hypothesis, we may assume that the variable $y^{p}_{t_{i-1}}$
takes a binary value; and the variables $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t_{i}}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t_{i}}$ take only binary values, even relaxed to
be continuous (see Remark 3). Therefore, the variable $y^{p}_{t_{i}}$ has an
integer value. Since $y^{p}_{t_{i}}$ is within the lower and upper binary
bounds, it can only take a binary value. This completes the proof. $\square$

##  4 3-based solution approaches

In this section, we present two approaches for obtaining high-quality
solutions and reducing the computational effort, both derived from the
formulation 3. Our first approach is a relax-and-fix heuristic based on the
idea of fixing the zero-valued variables in a relaxed solution to reduce the
model size — a similar approach can be found in Yee (1998). Our second
approach is an exact methodology that employs a reduced-cost variable-fixing
technique using the solution of the heuristic as a warm-start solution.

###  4.1 Relax-and-fix heuristic

We can observe in formulation 3 that symmetries arise from the fact that the
variables associated with the parking spaces, equipped or unequipped with a
charging facility, located at the same station and time, can be permuted
without changing the structure of the solution. If we know ahead which
variables are associated with the parking spaces with a low probability of
appearing in an optimal solution, we can heuristically cut out part of the
search space by fixing some of these variables to zero, consequently breaking
part of the symmetry. For this purpose, the knowledge regarding an optimal
fractional solution from the linear programming relaxation can be exploited.

The concept behind this approach is simple. We first relax the integrality
constraints and solve the linear programming to obtain an optimal fractional
solution. From this solution, we fix to zero all the binary variables
associated with the parking spaces whose values are zero — they have a
presumably low likelihood of appearing in a high-quality solution. Then, by
imposing the integrality constraints to obtain a feasible solution for the
EVSP, we optimally solve the resulting model. Another implication of doing
this is that the resulting model also has fewer constraints than the original
one since those constraints consisting solely of the fixed variables are also
inactive. For a better understanding, the following pseudo-code summarizes
this approach.

Algorithm 1 The linear relaxation-based variable-fixing (LRBVF) heuristic.

1:Relax the integrality constraints of all binary variables in the 3 model.

2:Solve the relaxed model to obtain an optimal fractional solution.

3:Fix to zero the variables $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d},\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ if their value in the solution is zero.

4:Restore the integrality constraints for the variables
$\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}$.

5:Solve the resulting model.

6:Return the integer-valued solution achieved.

######  Proposition 2.

The algorithm LRBVF finds a feasible solution to any instance of the EVSP.

Proof. Note first that, given Remark 3 and Proposition 1, only the integrality
of the variables $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}$ is imposed (in step $4$). Since the
algorithm only fixes variables related to fulfilling demands (in step $3$),
the vehicles are free at any time to remain parked in a parking space. Thus,
the LRBVF algorithm ensures that a feasible solution is always found.
$\square$

###  4.2 Exact algorithm with reduced-cost variable-fixing

An optimal solution can be achieved based on the observation that we can just
extend the LRBVF heuristic by using its solution as a warm-starting point,
which can be done by releasing the variables previously fixed and solving the
updated model from the current solved state. To introduce a better exact
approach, we propose an algorithm that extends our heuristic by performing two
additional variable-fixing schemes.

Our first scheme makes use of the reduced-cost variable-fixing technique,
which can be attempted whenever a dual feasible solution and a lower bound
corresponding to a feasible solution are available. Consider the following $0$
-$1$ integer linear programming problem

$\max\bigl{\\{}\boldsymbol{c}^{{}_{\textsf{T}}}\boldsymbol{x}\,:\,\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b},\leavevmode\nobreak\
\boldsymbol{x}\in\\{0,1\\}^{n}\bigr{\\}}{,}$ (P)

where $\boldsymbol{A}\in\mathbb{R}^{m\scaleobj{0.6}{\times}n}$,
$\boldsymbol{b}\in\mathbb{R}^{m}$, and $\boldsymbol{c}\in\mathbb{R}^{n}$, for
some $m\geq n\geq 1$. The dual problem associated with the linear relaxation
of P can be presented in standard form as

$\min\bigl{\\{}\boldsymbol{y}^{{}_{\textsf{T}}}\boldsymbol{b}+\boldsymbol{u}^{{}_{\textsf{T}}}\boldsymbol{1}:\,\boldsymbol{y}^{{}_{\textsf{T}}}\\!\boldsymbol{A}+\boldsymbol{u}-\boldsymbol{v}=\boldsymbol{c},\leavevmode\nobreak\
\boldsymbol{u},\boldsymbol{v}\geq\boldsymbol{0}\bigr{\\}}{,}$ (D)

where $\boldsymbol{y}\in\mathbb{R}^{m}$ is the vector of dual variables,
$\boldsymbol{u},\boldsymbol{v}\in\mathbb{R}^{n}$ are the vectors of dual slack
variables, and $\boldsymbol{0}$ and $\boldsymbol{1}$ are $n$-vectors of zeros
and ones, respectively. Concerning a feasible dual solution
$(\bar{\boldsymbol{y}},\bar{\boldsymbol{u}},\bar{\boldsymbol{v}})$ of D, by
complementary slackness, the primal value
$\boldsymbol{c}^{{}_{\textsf{T}}}\boldsymbol{x}$ can be written as

$\displaystyle\boldsymbol{c}^{{}_{\textsf{T}}}\boldsymbol{x}$
$\displaystyle=(\bar{\boldsymbol{y}}^{{}_{\textsf{T}}}\\!\boldsymbol{A}+\bar{\boldsymbol{u}}-\bar{\boldsymbol{v}})^{{}_{\textsf{T}}}\boldsymbol{x}$
$\displaystyle=\bar{\boldsymbol{y}}^{{}_{\textsf{T}}}\boldsymbol{b}+\bar{\boldsymbol{u}}^{{}_{\textsf{T}}}\boldsymbol{x}-\bar{\boldsymbol{v}}^{{}_{\textsf{T}}}\boldsymbol{x}$
$\displaystyle=\scalebox{1.2}{$\bar{z}$}+\bar{\boldsymbol{u}}^{{}_{\textsf{T}}}(\boldsymbol{x}-\boldsymbol{1})-\bar{\boldsymbol{v}}^{{}_{\textsf{T}}}\boldsymbol{x},$

where  $\bar{z}$ is the dual value from a feasible dual solution. Let
$\underaccent{\bar}{z}$ be a lower bound on the optimal value of P. Note that
if $u_{i}>\scalebox{1.2}{$\bar{z}$}-\scalebox{1.2}{$\underaccent{\bar}{z}$}$,
then
$\boldsymbol{c}^{{}_{\textsf{T}}}\bar{\boldsymbol{x}}<\scalebox{1.2}{$\underaccent{\bar}{z}$}$
for any feasible solution $\bar{\boldsymbol{x}}$ with $\bar{x}_{i}=0$, and if
$v_{i}>\scalebox{1.2}{$\bar{z}$}-\scalebox{1.2}{$\underaccent{\bar}{z}$}$,
then
$\boldsymbol{c}^{{}_{\textsf{T}}}\bar{\boldsymbol{x}}<\scalebox{1.2}{$\underaccent{\bar}{z}$}$
for any feasible solution $\bar{\boldsymbol{x}}$ with $\bar{x}_{i}=1$. Hence,
adapted for our purposes, we use the following theorem.

######  Theorem 2 (Mitchell (1997), Theorem 1).

Let $(\bar{\boldsymbol{y}},\bar{\boldsymbol{u}},\bar{\boldsymbol{v}})$ be a
feasible solution of D with value  $\bar{z}$ , and  $\underaccent{\bar}{z}$ be
a known lower bound on the optimal value of P. Thus, the following two
properties hold.

  1. (a)

If
$\bar{u}_{i}>\scalebox{1.2}{$\bar{z}$}-\scalebox{1.2}{$\underaccent{\bar}{z}$}$,
then $x_{i}$ is equal to one in any optimal integer solution.

  2. (b)

If
$\bar{v}_{i}>\scalebox{1.2}{$\bar{z}$}-\scalebox{1.2}{$\underaccent{\bar}{z}$}$,
then $x_{i}$ is equal to zero in any optimal integer solution.

Bearing in mind that the reduced cost $r_{i}$ of a variable $x_{i}$ is given
by
$r_{i}=c_{i}-\bar{\boldsymbol{y}}^{{}_{\textsf{T}}}\boldsymbol{A}_{{}^{\scalebox{1.2}{$.$}}i}=\bar{u}_{i}-\bar{v}_{i}$,
where $\boldsymbol{A}_{{}^{\scalebox{1.2}{$.$}}i}$ denotes the $i$-th column
of $\boldsymbol{A}$, and that at most one of the dual slack variables
$\bar{u}_{i}$ and $\bar{v}_{i}$ can be non-zero, we have the relations: when
$x_{i}=1$, $r_{i}$ is equal to $\bar{u}_{i}$, and when $x_{i}=0$, $r_{i}$ is
equal to $-\bar{v}_{i}$. As a result, the variable $x_{i}$ can be fixed at $1$
when $r_{i}>\scalebox{1.2}{$\bar{z}$}-\scalebox{1.2}{$\underaccent{\bar}{z}$}$
and at $0$ when
$-r_{i}>\scalebox{1.2}{$\bar{z}$}-\scalebox{1.2}{$\underaccent{\bar}{z}$}$
without loss of optimality. In our approach, we are only interested in fixing
the variables $w_{c}$, which is useful to carry out the second variable-fixing
scheme.

Our second scheme consists in fixing to zero variables related to the parking
spaces. Let $\matheuler{C}^{\prime}\subseteq\matheuler{C}$ denote the set of
customers whose variables $w_{c}$, for $c\in\matheuler{C}^{\prime}$, have not
been previously fixed to zero. Additionally, for each $s\in\matheuler{S}$, let
$\matheuler{P}^{\prime}_{s}=\\{\scalebox{0.93}{$p$}\in\matheuler{P}_{s}:\scalebox{0.93}{$p$}\neq\psi(v),\forall
v\in\matheuler{V}_{s}\\}$ denote the set of parking spaces (also called
_absent parking spaces_) that are empty at the beginning. By using the set
$\matheuler{C}^{\prime}$, iteratively by the time instant, we can know the
maximum amount of vehicles that can enter the station $s\in\matheuler{S}$ or,
more specifically, the maximum amount of parking spaces that can be taken into
account in any feasible solution, and then these parking spaces are taken off
from $\matheuler{P}^{\prime}_{s}$. Thus, the variables $y^{p}_{t}$,
$\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t}$, and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ associated with the remaining parking spaces
in $\matheuler{P}^{\prime}_{s}$ can be fixed to zero.

Algorithm 2 outlines the fixing of such variables, which can exclude some
optimal solutions but are guaranteed not to eliminate all optimal solutions.
In this algorithm, we use the threshold $k$ as an upper bound on the total
amount of parking spaces without charging facilities to be removed from the
current set of remaining parking spaces (i.e., the subset $\matheuler{U}$ of
$\matheuler{P}^{\prime}_{s}$). When the initial value of $k$ (step $4$) is
less than or equal to $0$, this means that all of the parking spaces without
charging facilities will have their variables fixed at zero at any time
instant. Note that in the innermost loop (steps $5$ to $15$), we look for the
maximum amount of vehicles that can enter the station $s$ at time $t$ (step
$6$), to help determine the number of parking spaces to be removed from
$\matheuler{E}$ and $\matheuler{U}$ (steps $9$ and $12$, respectively). If
there exist parking space  $p$ in $\matheuler{E}\cup\matheuler{U}$, the value
of $y^{p}_{t}$, $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t}$, and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ are then set to zero (step $15$).

Algorithm 2 The subroutine for fixing variables associated with the parking
spaces.

1:For each station $s$ in $\matheuler{S}$ do

2: Let $\matheuler{D}^{\prime}_{s}$ denote the set of all
$(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D}_{c}$, such that
$\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}\neq\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}}=s$, for each $c\in\matheuler{C}^{\prime}$.

3: Let
$\matheuler{E}=\\{\scalebox{0.93}{$p$}\in\matheuler{P}^{\prime}_{s}:\scalebox{0.93}{$p$}\text{
is equipped with a charging facility}\\}$ and
$\matheuler{U}=\matheuler{P}^{\prime}_{s}\\!\setminus\\!\matheuler{E}$ denote
subsets of $\matheuler{P}^{\prime}_{s}$.

4: Set the initial value of the threshold $k$ equal to
$\min(|\matheuler{D}^{\prime}_{s}|-|\matheuler{E}|,|\matheuler{U}|)$.

5: For each time $t$ in $\matheuler{T}$ (given in ascending order) do

6: Let $\textsf{M}=|\\{(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{i},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,s\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,s\mkern
2.0mu$}}$}\mkern-2.0mu}},t_{j})\in\matheuler{D}^{\prime}_{s}\\!:t_{j}=t\\}|$
be the maximum number of vehicles at time $t$.

7: If M is greater than zero then

8: If $\min(|\matheuler{E}|,\textsf{M})$ is greater than zero then

9: Remove $\min(|\matheuler{E}|,\textsf{M})$ parking spaces from
$\matheuler{E}$.

10: If $k$ is greater than zero then

11: Set $n$ equal to $\min(k,\textsf{M})$.

12: Remove $n$ parking spaces from $\matheuler{U}$.

13: Decrease the threshold $k$ by $n$, i.e., $k\leftarrow k-n$.

14: If $\matheuler{E}\cup\matheuler{U}$ is not empty then

15: Fix to zero the value of $y^{p}_{t}$, $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ for all remaining parking space
$\scalebox{0.93}{$p$}\in\matheuler{E}\cup\matheuler{U}$.

It should be noted that the maximum number of absent parking spaces from
$\matheuler{P}^{\prime}_{s}$, for each station $s\in\matheuler{S}$, used in
any optimal solution, is given by
$\min(|\matheuler{P}^{\prime}_{s}|,|\matheuler{D}^{\prime}_{s}|)$. To best
explain Algorithm 2, keep in mind before the loop in step $5$ starts,
$\min(|\matheuler{P}^{\prime}_{s}|,|\matheuler{D}^{\prime}_{s}|)=2m+r$, where
$m=\min(k,|\matheuler{E}|)$ is the number of times where parking spaces with
and without charging facilities are taken into account simultaneously in the
innermost loop of the algorithm. More specifically, one parking space from
$\matheuler{E}$ and $\matheuler{U}$ is removed for the first $m$ possible
vehicle arrivals, and one parking space from $\matheuler{E}$ or
$\matheuler{U}$ is removed for the last $r$ possible vehicle arrivals.

######  Proposition 3.

Let $\matheuler{C}^{\prime}\subseteq\matheuler{C}$ be an arbitrary subset of
customers. If there is at least one optimal solution such that only the
customers in $\matheuler{C}^{\prime}$ are served, then Algorithm 2 does not
eliminate all optimal solutions.

Proof. It should be noted that the algorithm gives priority to using absent
parking spaces with charging facilities. Hence, we consider from now on that
the optimal solutions make the most of the parking spaces with charging
facilities. Now, note that for a given iteration $s$ (step $1$ of Algorithm
2), considering each potential arrival of a vehicle from a station other than
$s$, there are three cases:

  1. (i)

If the initial value of $k$ is less than or equal to $0$, then only parking
spaces in $\matheuler{P}^{\prime}_{s}$ with charging facilities will be
considered, and as long as $\matheuler{E}$ is not empty, one of these parking
spaces is always chosen to be taken into account in a solution.

  2. (ii)

If there are only parking spaces in $\matheuler{P}^{\prime}_{s}$ without
charging facilities, then the initial value of the threshold $k$ is equal to
$\min(|\matheuler{D}^{\prime}_{s}|,|\matheuler{U}|)$, and as long as
$\matheuler{U}$ is not empty, one of the parking spaces is always chosen to be
taken into account in a solution.

  3. (iii)

Otherwise, while $k$ and $|\matheuler{E}|$ are positive values, one parking
space with and another without a charging facility are concurrently chosen to
be taken into account in a solution. After that, is chosen to be considered at
most one of the parking spaces from $\matheuler{U}$ (if $k$ is greater than
$0$) or $\matheuler{E}$ (if it is not empty).

Without loss of generality, we assume that cases (i) and (ii) do not occur,
and we will show that case (iii) does not eliminate all optimal solutions.

Let $\matheuler{E}^{\scalebox{0.63}{$($}t\scalebox{0.63}{$)$}}$ and
$\matheuler{U}^{\scalebox{0.63}{$($}t\scalebox{0.63}{$)$}}$ denote the sets of
all the parking spaces that have been taken away from $\matheuler{E}$ and
$\matheuler{U}$ in steps $9$ and $12$, respectively, up until the time $t$
along the innermost loop. For each time $t$, by the pigeonhole principle, the
larger value for the number of absent parking spaces with and without charging
facilities that an optimal solution uses results in at most
$|\matheuler{E}^{\scalebox{0.63}{$($}t\scalebox{0.63}{$)$}}|$ and
$|\matheuler{U}^{\scalebox{0.63}{$($}t\scalebox{0.63}{$)$}}|$, respectively.
As a result, we can assure that, given a subset
$\matheuler{C}^{\prime}\subseteq\matheuler{C}$ as stated, Algorithm 2 will
lead to at least an optimal solution. $\square$

Now that the variable-fixing schemes have been introduced, we present our
exact approach, which is described in the following pseudo-code.

Algorithm 3 The reduced-cost-based variable-fixing (RCBVF) algorithm.

1:Apply the variable-fixing on the parking spaces (call Algorithm 2 with
$\matheuler{C}$ as input).

2:Relax the integrality constraints of all binary variables in the 3 model.

3:Solve the relaxed model to obtain an optimal fractional solution.

4:$\triangleright$ The model is solved using the dual simplex method.

5:Let

$\bar{z}^{*}$

be the optimal value of the linear relaxation.

6:Calculate the reduced costs $r_{c}$ associated with the variables $w_{c}$.

7:Fix to zero the variables $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d},\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ if their value in the solution is zero.

8:$\triangleright$ This is done by setting the upper bound of these variables
to zero.

9:Restore the integrality constraints for the variables
$\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}$.

10:Solve the resulting model for at most T${}_{{}^{\text{{MAXRUN}}}}$ seconds.

11:If not failed to find any integer feasible solution then

12: Set
$(\bar{\boldsymbol{w}},\bar{\boldsymbol{x}},\bar{\boldsymbol{y}},\bar{\boldsymbol{z}},\bar{\boldsymbol{\ell}})$
to be the best solution found during the solving process.

13:Else

14: Build a feasible solution using the assignment plans construction
heuristic of Silva et al. (2023).

15: Set
$(\bar{\boldsymbol{w}},\bar{\boldsymbol{x}},\bar{\boldsymbol{y}},\bar{\boldsymbol{z}},\bar{\boldsymbol{\ell}})$
to be the heuristic solution.

16:Let

$\underaccent{\bar}{z}$

be the corresponding objective value of the solution
$(\bar{\boldsymbol{w}},\bar{\boldsymbol{x}},\bar{\boldsymbol{y}},\bar{\boldsymbol{z}},\bar{\boldsymbol{\ell}})$.

17:Apply the reduced cost variable-fixing as follows:
$w_{c}=\begin{cases}1\text{, if satisfies
}r_{c}>\scalebox{1.2}{$\bar{z}$}^{*}\\!-\scalebox{1.2}{$\underaccent{\bar}{z}$}\\\
0\text{, if satisfies
}\\!-\\!r_{c}>\scalebox{1.2}{$\bar{z}$}^{*}\\!-\scalebox{1.2}{$\underaccent{\bar}{z}$}\end{cases}$

18:Release the variables $\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d},\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d}$ and $\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{t}$ previously fixed.

19:$\triangleright$ This is done by setting the upper bound of the fixed
variables to one.

20:Let $\matheuler{C}^{\prime}\subseteq\matheuler{C}$ denote the set of
customers whose variables $w_{c}$ have not been fixed to zero.

21:Apply the variable-fixing on the parking spaces (call Algorithm 2 with
$\matheuler{C}^{\prime}$ as input).

22:Repair the solution
$(\bar{\boldsymbol{w}},\bar{\boldsymbol{x}},\bar{\boldsymbol{y}},\bar{\boldsymbol{z}},\bar{\boldsymbol{\ell}})$,
if necessary.

23:Solve the resulting model using
$(\bar{\boldsymbol{w}},\bar{\boldsymbol{x}},\bar{\boldsymbol{y}},\bar{\boldsymbol{z}},\bar{\boldsymbol{\ell}})$
as a warm-start solution.

24:Return the solution achieved.

 _Note._ The vectors $\bar{\boldsymbol{w}}$, $\bar{\boldsymbol{x}}$,
$\bar{\boldsymbol{y}}$, $\bar{\boldsymbol{z}}$, and $\bar{\boldsymbol{\ell}}$
denote the values of $(w_{c})$, $(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{d},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,x\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\reflectbox{$\scriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\reflectbox{$\scriptscriptstyle\vec{\reflectbox{$\mkern-2.0mu\scriptscriptstyle\,x\mkern
2.0mu$}}$}\mkern-2.0mu}}^{p}_{d})$, $(y^{p}_{t})$,
$(\\!\\!\smash{\mathchoice{\mkern
3.0mu\mbox{$\displaystyle\vec{\mbox{$\mkern-3.0mu\displaystyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\mbox{$\textstyle\vec{\mbox{$\mkern-3.0mu\textstyle\,\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
2.0mu\mbox{$\scriptstyle\vec{\mbox{$\mkern-2.0mu\scriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}{\mkern
2.0mu\mbox{$\scriptscriptstyle\vec{\mbox{$\mkern-2.0mu\scriptscriptstyle\,\,z\mkern
2.0mu$}}$}\mkern-2.0mu}}^{\>\\!p}_{t},\\!\smash{\mathchoice{\mkern
3.0mu\reflectbox{$\displaystyle\vec{\reflectbox{$\mkern-3.0mu\displaystyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern
3.0mu\reflectbox{$\textstyle\vec{\reflectbox{$\mkern-3.0mu\textstyle\,z\mkern
3.0mu$}}$}\mkern-3.0mu}{\mkern